CF810(div2) B

题意

一个聚会要从 $n$ 个人中邀请一部分人，如果第 $i$ 个人未被邀请，将会获得不高兴值 $a[i]$ 。这 $n$ 个人中有 $m$ 对朋友，每对朋友来了以后，都会吃一个蛋糕。要求吃的蛋糕的数量必须为偶数，求这种条件下的最小不高兴值。

思路

n,m很大。应该考虑删哪些点，而不是选哪些！！

如果 $m$ 为偶数，就可以邀请所有人；如果 $m$ 为奇数，那么要么不邀请一个有奇数个朋友关系的人；要么不邀请一对彼此相连，且度数同奇偶的点。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <math.h>
using namespace std;
typedef long long LL;
int d[100010],a[100010],x,y;
pair<int,int> pi[100010];
LL sum,ans;
int m1,m2;
int t;
int n,m;
int main()
{
    scanf("%d",&t);
    while(t--){
        cin>>n>>m;
        ans=sum=0;
        m1=m2=0x3f3f3f3f;
        for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            pi[i]={x,y};
            d[x]++,d[y]++;
        }
        if(m%2){
            for(int i=1;i<=n;i++){
                if(d[i]%2) m1=min(m1,a[i]);
            }
            for(int i=1;i<=m;i++){
                if(d[pi[i].first]%2==d[pi[i].second]%2){
                    m2=min(m2,a[pi[i].first]+a[pi[i].second]);
                }
            }
            ans=min(m1,m2);
        }

        cout<<min(ans,sum)<<endl;
        for(int i=1;i<=n;i++) d[i]=0;
    }
    return 0;
}

CF810(div2) C

题意

给一个 $n*m$ 的矩阵，和 $k$ 种染料，每种染料最多可以染 $a[i]$ 个格子。问有没有一种染色方法，对于矩阵中的每个点，它的周围四个点（可以穿过矩阵去矩阵的另一边)至少有三个和它颜色相同。

上图为(1,2)周围的四个点。

思路

发现这些染料要么按行染，要么按列染，而且至少染两行（列）。所以需要分行列讨论两次。

那么哪些情况不能染色成功呢：

可染行数大于等于2的颜色，将他们可染行数加起来，如果小于列数，一定无法染色。
如果大于，需考虑删行。
- 因为至少染2行，如果存在一个大于等于3行的颜色，那么一定存在一种删法，可以得到任何数。
- 反之如果所有颜色都只能染2行，那么通过删除，最终只能得到偶数。
- 所以：当且仅当 n 为奇数且所有颜色都只能染2行时，false。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <math.h>
using namespace std;
typedef long long LL;
LL a[100010],mx[100010];
int t;
LL n,m,k;
LL xx,yy;
bool fg,fg2,ji;

bool gogo(LL x,LL y){
    LL sum=0,fl=0;
    for(int i=1;i<=k;i++){
        mx[i]=a[i]/x;
        if(mx[i]>=2){
            sum+=mx[i];
            if(mx[i]>2) fl=1;
        }
    }

    if(sum>=y && (fl || y%2==0)) return true;
    return false;
}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int i=1;i<=k;i++)  scanf("%lld",&a[i]);

        if(gogo(n,m)||gogo(m,n)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

总结

思路中加粗部分在比赛时没想到，想复杂了。另外记得开long long。

CF817 (Div. 4) E

题意

有 n 个长方形，高为 h ，宽为 w 。接下来有 q 次询问，每次给定 hs,ws,hb,wb ，都要求输出所有满足 hs<h<hb,ws<h<wb 的长方形面积之和

思路

考虑到，h，w 都不大，可以用二维前缀和来解决问题， fij 存储所有 h≤i,w≤j 的长方形面积之和。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <cstring>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
LL t,n,q,h1,h2,w1,w2;
LL sm[1010][1010];

int main() {
    scanf("%lld",&t);
    while(t--){
        memset(sm,0,sizeof sm);
        scanf("%lld %lld",&n,&q);
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&h1,&w1);
            sm[h1][w1]+=((LL)h1*(LL)w1);
        }
        for(int i=1;i<=1000;i++){
            for(int j=1;j<=1000;j++){
                sm[i][j] += sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];
            }
        }
        for(int i=0;i<q;i++){
            scanf("%lld%lld%lld%lld",&h1,&w1,&h2,&w2);
            printf("%lld\n",sm[h2-1][w2-1]-sm[h1][w2-1]-sm[h2-1][w1]+sm[h1][w1]);
        }
    }

    return 0;
}

CF817 (Div. 4) G

题意

构造一个长度为 n 的元素互不相同的数列，使得数列所有奇数下标元素的亦或和等于数列所有偶数下标元素的异或和。

思路

方法一

可以每 4 个数字一考虑，因为对于奇数 x,y ， x⊕(x−1)=1,y⊕(y−1)=1 ，把这四个数字分别安排在奇数位和偶数位就可以了。如果 n mod 4 有余数 r ，那就需要构造出一个长度为 4+r 的满足要求的数列，样例正好都给了，那就直接抄上就好了。

方法二

由于奇数位异或和=偶数位异或和，所以可以得到奇数位异或和 xor 偶数位异或和=0

问题就可以转化为构造一个长度为n 异或和为0的序列，这样任何排列顺序都是满足答案的。

由于元素互不相同，可以令前n-3个数按顺序输出，并记录异或结果sum，后面三个分别为：1<<29，1<<30，sum^(1<<29)^(1<<30)。(因为sum可能为0，所以需要额外考虑3个数)

方法二代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N =100000,MOD = 1e9+7;
int t;
int main()
{
    scanf("%d",&t);
    while(t--){
        int n;cin>>n;
        int sum=0;
        for(int i=1;i<n-2;i++)
        {
            printf("%d ",i);
            sum^=i;
        }
        printf("%d %d ",(1<<29),(1<<30));
        printf("%d\n",sum^(1<<29)^(1<<30));
    }
    return 0;
}