Educational Codeforces Round 110 (Rated for Div. 2)

题目入口

思路
找出最大和次大模拟即可

代码

#include
using namespace std;
int a[5];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int maxx=-1,max2=-1;
        for(int i=1;i<=4;i++)
        {
            cin>>a[i];
            maxx=max(maxx,a[i]);
        }
        for(int i=1;i<=4;i++)
            if(a[i]>max2&&a[i]!=maxx) max2=a[i];
        int tmp1=max(a[1],a[2]);
        int tmp2=max(a[3],a[4]);
        if(maxx==tmp1&&max2==tmp2||maxx==tmp2&&max2==tmp1) cout<<"YES"< 
B. Array Reodering 
题目入口
 
思路
 我们发现若两数不互质，则换位置对他们没有影响，有影响的只是aj前面的系数2，由于只有偶数在前能使因子2发挥作用，因此按偶在前奇在后来排序，最后遍历所有的奇数，找出不互质的奇数对个数即可
 
代码
 
#include
using namespace std;
const int N=2005;
int t,n,a[N];
vector odd;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    cin>>t;
    while(t--)
    {
        odd.clear();
        cin>>n;
        int res=0;
        int cnt1=0,cnt2=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]%2)
            {
                cnt2++;
                odd.push_back(a[i]);
            }
            else cnt1++;
        }
        res+=(n-1+n-cnt1)*cnt1/2;
        for(int i=0;i1) res++;
            }
        }
        cout< 
C. Unstable String 
题目入口
 
思路
 这题我们只要遍历字符串，找到以每个位置为结尾的满足条件的子串长度，设左有边界分别为l和r，则每次答案加上r-l+1即可，而求满足条件的最大字串我们用DP来求，dp[i][j]表示以i为结尾，是s[i]为j的最长字串长度
 
代码
 
#include
#define int long long
using namespace std;
const int N=2e5+5;
int t,dp[N][3];
char s[N];
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>s+1;
        int res=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;s[i];i++)
        {
            if(s[i]=='0') dp[i][0]=dp[i-1][1]+1;
            else if(s[i]=='1') dp[i][1]=dp[i-1][0]+1;
            else
            {
                dp[i][0]=dp[i-1][1]+1;
                dp[i][1]=dp[i-1][0]+1;
            }
            res+=max(dp[i][0],dp[i][1]);
        }
        cout<