Codeforces Global Round 14

A 构造

显然当$tot=x$时无解。

当$tot\ne x$时肯定有解，考虑当$prefix(i)=x$时，因为题目限制$a_i$各不相同，所以我们交换$a_i,a_{i+1}$，注意到因为$a_n\ne x$，所以$i<n,i+1$存在。

B 数学

考虑面积的合法性：设用了$n$个三角形，边长为：$a+\sqrt{2}b$，因为只有这两种长度。

$n\times \dfrac{1}{2}=(a+\sqrt{2}b)^2=a^2+2b^2+\sqrt{2}ab$。

显然$\sqrt{2}ab=0$，且$n$为偶数才成立。

所以要么$a=0$，要么$b=0$。

当$b=0$，

边长为1的正方形

由若干个$1\times 1$的正方形拼成，即答案为$2x$，$x$是平方数。

同理：当$a=0$时，答案是$4x$。

C 贪心

依题意，必定有解，可用反证法证，然后贪心每次选当前最小的加。

D 贪心

先把已经匹配的丢掉，然后不妨设剩下的$l\ge r$，因为等价，然后在维持$l\ge r$下，每次计算把相同颜色对数折半贡献。这样的正确性是如果不维持$l\ge r$，就会导致多算一段贡献，因为最后还是要把剩下的$l,r$相等。

for(int i=1; i <= n; i++) lc[i] = rc[i] = 0;
        for(int i=1; i <= n; i++) cin>>c[i];
        for(int i=1; i <= l ;i++) lc[c[i]]++;
        for(int i = l+1; i <= n ;i++) rc[c[i]]++;
        ll ans=0;
        for(int i=1 ;i<=n;i++){
            int mn=min(lc[i],rc[i]);
            lc[i]-=mn,rc[i]-=mn;
            l-=mn,r-=mn;
        }
        if(l<r) swap(l,r),swap(lc,rc);
        for(int i=1 ;i <= n; i++){
            int cha = l - r;
            int ke = lc[i] >> 1;
            int mn = min(cha , ke << 1);
            ans += mn>>1,l -= mn;
        }
        ans+=(l-r)/2+(l+r)/2;
        cout<<ans<<'\n';