CF构造题练习记录

本文主要是介绍CF构造题练习记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

发现自己构造太菜了

于是决定上cf按tag找题来做

不定期更新

是CF上2000-2500的构造题

CF1506F

题意太长不翻译了(

 把原图路径画一画，大概是一堆这样的东西

构造路径的时候，按照斜线分组

如果两个点在同一组的话，那么看它是奇数还是偶数

奇数的话要把所有的路径变向，否则消耗为0

如果不在同一组，那么产生的消耗就是跨越组的消耗。

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int r,c,d;
}a[200005];
int temp(Node a,Node b){
    return a.r<b.r;
};
int ans=0;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int N;
        ans=0;
        scanf("%d",&N);
        a[0].r=1,a[0].c=1,a[0].d=0;
        for (int i=1;i<=N;i++)
            scanf("%d",&a[i].r);
        for (int i=1;i<=N;i++)
            scanf("%d",&a[i].c);
        sort(a+1,a+N+1,temp);
        for (int i=1;i<=N;i++)
            a[i].d=a[i].r-a[i].c;        
        for (int i=1;i<=N;i++){
            if (a[i].d==a[i-1].d){
                if (!(a[i].d%2))
                    ans+=a[i].c-a[i-1].c;
            }
            else{
                if (a[i-1].d%2){
                    ans+=(a[i].d-a[i-1].d+1)/2;
                }
                else ans+=(a[i].d-a[i-1].d)/2;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
} 

 CF925C

题意：

给你一堆数字，排列这些数字，让他们前缀异或和递增

sol:

考虑当前获得了异或和$sum$

那么，对下一个数字的情况做分类讨论

情况1:下一个数字位数比自己高

那么肯定比这个大

情况2：

下一个数字和这个数字的最高位一样，都是$1$

那么显然是变小的

情况3：

下一个数字和$sum$在最高位不同，且$sum$在某个位置上是$0$

那么，其实我们找到一个最高位是这个位置的数字，把它放上去就好了，新的数字肯定比这个数字大

那么我们就得到了一个做法

枚举$N$个位置，记录当前的$sum$，每次从低位到高位考虑，找到一个$0$，找最高位为这个位置的数字，有就塞，没有就继续找就行了。

#include <bits/stdc++.h>
using namespace std;
int N;
long long  a[100005];
vector<long long> anss;
queue<long long >bit[65]; 
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;i++){
        scanf("%lld",&a[i]);
        for (int j=60;j>=0;j--)
            if ((a[i]>>j)&1ll) {
            bit[j].push(a[i]);
            break;
        }
    }
    sort(a+1,a+N+1);
    long long  ans=0;
    for (int i=1;i<=N;i++){
        bool flag=false;
        for (int j=0;j<=60;j++){
            if (!((ans>>j)&1ll)&&!(bit[j].empty())) {
                long long x=bit[j].front();
                bit[j].pop();
                ans^=x;
                flag=true;
                anss.push_back(x);
                break;
            }
        }
        if (!flag) {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    for (auto x:anss){
        printf("%lld ",x);
    }
    return 0;
}

这篇关于CF构造题练习记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！