「解题报告」Codeforces Round 594 (Div. 2)

可怜的小cj被卡死在C题……

A. PolandBall and Hypothesis

Source

不难发现只有形如y=x+b1和y=-x+b2的函数会有交点。
联立x+b1 = -x+b2,有x = (b2-b1)/2。这个东西为整数，当且仅当b2-b1为偶数。也就是说现在我们要统计∀i∈[1,n],j∈[1,m] , (bj-bi) ≡ 0 (mod 2)的数量。
我们发现我们关注的只是bj-bi的奇偶性，而并不是这个式子具体的值。考虑什么情况下两数相减会出现偶数：偶-偶 或 奇-奇 。
考虑用乘法解决这个问题，那我们设c1表示bi(i∈[1,n])$中奇数的数量，c2表示bj(j∈[1,m])中奇数的数量，那么答案显然就是c1×c2 + (n-c1)×(m-c2)。
于是做完了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int CN = 1e5+5;
LL read(){
    LL s = 0,ne = 1; char c = getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne = -1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}
LL t,n,m;
int main()
{
    //freopen("a.in","r",stdin);
    t = read();
    while(t--){
        LL cnt1 = 0,cnt2 = 0,ans;
        n = read();
        for(int i=1;i<=n;i++) {int pi = read(); if(pi % 2) cnt1++;}
        m = read();
        for(int i=1;i<=m;i++) {int qi = read(); if(qi % 2) cnt2++;}
        ans = cnt1 * cnt2 + (n-cnt1) * (m-cnt2);               
        printf("%I64d\n",ans);
    }
    return 0;
}

B. Grow The Tree

Source

不能有连续的两段就是让你把这些边分成大小分别为⌊n/2⌋，⌈n/2⌉的两组。
一个并不显然但是是正确的的贪心思路：小的分一组，大的分一组。然后就做完了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; 
#define LL long long 
const int CN = 1e5+5; 
LL read(){
    LL s = 0,ne = 1; char c = getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne = -1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
} 
int n; LL a[CN],sum[CN]; 
LL Pow(LL u) {return u*u;} 
int main()
{
    //freopen("b.in","r",stdin); 
    n = read(); 
    for(int i=1;i<=n;i++) a[i] = read(); 
    
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) sum[i] = sum[i-1]+a[i];
    
    LL ans = Pow(sum[_n]) + Pow(sum[n]-sum[_n]);
    int _n = n/2; 
    if(_n * 2 != n) ans = max(ans, Pow(sum[_n+1])+Pow(sum[n]-sum[_n+1])); 
    
    printf("%I64d",ans); 
    
    return 0;
}

C. Ivan the Fool and the Probability Theory

Source

考虑第一行。固定第一个格子的颜色，那么方案数是一个fibonacci数列。
推广到整个矩阵：

1. 当第一行不存在相邻元素时，也就是说它长这样：10101… 这个时候仅需要相邻三行互不相同。把每一行理解成一个元素，实际上又回到了上面的那个问题，这个方案数又是一个fibonacci数列。因此此时答案是 1×f[m] 。
2. 当第一行存在相邻元素时，那么下面的整个矩阵实际上已经确定了，因为下面的每一行都只能是上面一行把每位都取反的结果。此时答案为 (f[n]-1)×1 。

因此答案总数为 1×f[m] + (f[n]-1)×1 = f[n]+f[m]-1 。考虑第一个格子有两种情况，因此答案是 2×(f[n]+f[m]-1) 。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int CN = 1e5+5;
const int R = 1e9+7;
int n,m,f[CN];
int main()
{
    scanf("%d%d",&n,&m);
    f[0] = 2,f[1] = 2;
    for(int i=2;i<=max(n,m);i++) f[i] = (f[i-1]+f[i-2]) % R;
    printf("%d", (f[n]+f[m]-2) % R);
    return 0;
}

D1. The World Is Just a Programming Task (Easy Version)

Source

显然是枚举方案，剩下的问题是怎么找“循环匹配”个数。设’(‘代表 1 ，’)’代表 -1 ，于是我们得到一串数列。有一个结论是说“循环匹配”个数恰好等于这个数列的前缀和最小值的数量，感性理解一下，这个东西很有道理，然后就做完了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 550;

int abs(int x) {return x > 0 ? x : -x;}

int n; char ch[CN];

int ans = 0,ansi = 1,ansj = 1;
int GetAns(){
    int cnt = 0,sum = 0,mn = 0;
    for(int i=0;i<n;i++){
        if(ch[i] == '(') cnt++;
            else cnt--;
        mn = min(mn, cnt);
    }
    for(int i=0;i<n;i++){
        if(ch[i] == '(') cnt++;
            else cnt--;
        if(cnt == mn) sum++;
    }
    return sum;
}
bool checker(){
    int a = 0,b = 0;
    for(int i=0;i<n;i++) if(ch[i] == '(') a++; else b++;
    return a == b;
}

int main()
{
    scanf("%d",&n); cin>>ch;
    
    if(!checker()) printf("0\n1 1");
    else{
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                swap(ch[i],ch[j]);
                if(GetAns() > ans) {ans = GetAns(); ansi = i+1; ansj = j+1;}
                swap(ch[j],ch[i]);
            }        
        printf("%d\n%d %d",ans,ansi,ansj);
    }
    
    return 0;
}