CF构造题练习记录

发现自己构造太菜了

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

不定期更新

是CF上2000-2500的构造题

CF1506F

题意太长不翻译了(

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

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

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

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

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

#include 
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 
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;
}

 CF1513D

题意:

$gcd(a_i,a_{i+1}...a_j)==min(a_i,a_{i+1}...a_j)==min(a_i,a_{i+1}...a_j)$，则有一条$i -> j$的边，权值为这个$gcd$

对每个$i -> i+1$还有一条长度为$p$的边

问最小生成树权值

sol:
考虑krusual的过程，问题的瓶颈在于找到这个最小值

我们可以从小到大的枚举这个最小值，并且向两边扩展，进行krusual的过程

然后可以发现，每个点只会被访问到一次

为什么？

因为我们是从小到大的枚举的$a_i$，如果一个$a_i$在被访问过还能被扩展的话，那么显然，这个被扩展的数可以被扩展这个数的数继续扩展出去。

然后就暴力模拟这个过程即可。

如果$a_i > p$ ，按$p$一个个连过去就行

$O(n log n)$ ,$log$是并查集

#include 
using namespace std;
int N;
long long p,b[200005],ans;
bool pd[200005],vis[200005];
int fa[200005];
struct Node{
    int pos;
    long long val;
}a[200005];
bool temp(Node a,Node b){
    return a.val<b.val;
}
int Getfa(int x){
    return (x==fa[x])?x:fa[x]=Getfa(fa[x]);
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
    ans=0;
    scanf("%d%lld",&N,&p);
    for (int i=1;i<=N;i++){
        scanf("%lld",&a[i].val);
        b[i]=a[i].val;
        a[i].pos=i;
        fa[i]=i;
    }
    sort(a+1,a+N+1,temp);
    for (int i=1;i<=N;i++){
        if (vis[a[i].pos]) continue;
        int rt=a[i].pos;
        int x=a[i].pos-1;
        long long nww=a[i].val;
        if (nww>=p) break;
        while (x>0&&__gcd(nww,b[x])==a[i].val){
            if (Getfa(rt)==Getfa(x)) {x--;continue;}
            else fa[Getfa(x)]=Getfa(rt),ans+=nww;
            vis[x]=true;
            x--;
        }
        x=a[i].pos+1;
        nww=a[i].val;
        while (x<=N&&__gcd(nww,b[x])==a[i].val){
            if (Getfa(rt)==Getfa(x)) {x++;continue;}
            else fa[Getfa(x)]=Getfa(rt),ans+=nww;
            vis[x]=true;
        x++;
        }
    }
    for (int i=1;i)
        if (Getfa(i)==Getfa(i+1)) continue;
        else{
            ans+=p;
            fa[Getfa(i)]=Getfa(i+1);
        }
    for (int i=1;i<=N;i++)
        pd[i]=vis[i]=false;
        printf("%lld\n",ans);
    }
    return 0;
}

 CF1494E

题意：

$n$个点，有向图，每个边上有一个字母

动态增加删除边，每次给定$k$，问有没有一种方案能找到一条$k$个点的序列，按照序列跑图上的边，正跑反跑是同一个字符串

sol：

发现这个定义有点类似于回文串，于是考虑分奇偶讨论

为了讨论的方便，我分析的时候是先把边权扔到点上，然后再重新接回去的

对于长度为奇数的列来说

我们发现，如果出现$A ---- C ---- A$这样形式的点权，一定是可以形成回文串的

只需不断遍历$A C A C A ... $即可

考虑把点权放回边上

其实就是两个为$A$的缩成一个点，变成两个点之间的边是双向边即可。

对于偶数的情况:

出现$A----A$这样的形式即可。

那么意思就是，存在两个点之间是双向边且双向边上字符相等

至于其他可以形成回文串的情况

其实我们可以发现，如果你能形成别的回文串，那么对于中心字符来说，一定是满足上面这些条件的

所以这东西是充分必要的

暴力跑这个即可。

#include 
using namespace std;
mapint,int>,char>col; 
int N,T;
int eans,oans;
int main(){
    cin>>N>>T;
    while (T--){
        char opt;
        cin>>opt;
        if (opt=='+'){
            int u,v;
            char c;
            cin>>u>>v;
            cin>>c;
            pair<int,int> nw={u,v};
            col[nw]=c;
            nw=make_pair(v,u);
            if (col.find(nw)==col.end()||col[nw]=='?') continue;
            oans++;
            if (col[nw]==c){
                eans++;
            }
        }else
        if (opt=='-'){
            int u,v;
            char c;
            cin>>u>>v;
            pair<int,int> nw=make_pair(u,v);
            c=col[nw];
            col[nw]='?';
            nw=make_pair(v,u);
            if (col.find(nw)==col.end()||col[nw]=='?') continue;
            oans--;
            if (col[nw]==c){
                eans--;
            }
        }else
        if (opt=='?'){
            int k;
            cin>>k;
            getchar();
            if (k&1) {
                if (eans||oans) printf("YES\n");
                else printf("NO\n");
            }
            else{
                if (eans) printf("YES\n");
                else printf("NO\n");
            }
        }
    }
    return 0;
}

 CF1559D2

好神仙的题(

官方的做法没太看懂，看到了一个很厉害的做法

考虑最终答案的局面，一定有一个最大的树，我们称之为$rt$集合

于是我们随便指定一个点，让它作为最大的那个树中的元素，其他点优先向它连边

接下来分类讨论，考虑一个点

如果两边都不在各自的$rt$集合里，那么直接向$rt$接上就好了。

否则一定是一边在$rt$中，一边不在$rt$中，这种情况我们后续讨论

还有一种两边都已经在$rt$中，不管就好了。

然后对于那些一边在$rt$中，一边不在$rt$中的

考虑从左边的向右边的连边

为什么这是对的呢？

因为这两个集合是完全不交叉的(定义)

如果连边了，就意味着我选择了其中的一边，加入了$rt$集合里

我们贪心的选择，能加入$rt$集合就加入，如果不能加入$rt$集合的一定在也没有办法加入$rt$集合，因为冲突了。

这样的话我们就保证了$rt$集合尽可能地大，也就是散块尽可能地少。

也就保证了生成树中没有被接上的边最少，也就保证了接上的边最多。

#include 
using namespace std;
int N,M1,M2;
queue<int> a;
queue<int> b;
int fa1[100005],fa2[100005];
vectorint,int> >ans;
void init(){
    for (int i=1;i<=N;i++) fa1[i]=fa2[i]=i;
}
int Getfa1(int x){ return (x==fa1[x])?x:fa1[x]=Getfa1(fa1[x]); }
int Getfa2(int x){ return (x==fa2[x])?x:fa2[x]=Getfa2(fa2[x]); }
void Merge1(int x,int y){
    int fx=Getfa1(x),fy=Getfa1(y);
    fa1[fx]=fy;
}
void Merge2(int x,int y){
    int fx=Getfa2(x),fy=Getfa2(y);
    fa2[fx]=fy;
}
int main(){
    scanf("%d%d%d",&N,&M1,&M2);
    init();
    for (int i=1;i<=M1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        Merge1(u,v);
    }
    for (int i=1;i<=M2;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        Merge2(u,v);
    }
    int rt=1;
    for (int i=1;i<=N;i++){
        int rt1=Getfa1(rt),rt2=Getfa2(rt);
        int fx=Getfa1(i),fy=Getfa2(i);
        if (rt1!=fx && rt2!=fy){
            Merge1(rt1,i),Merge2(rt2,i);
            ans.push_back({rt,i});
        }
        else if (rt1!=fx && rt2==fy) 
            a.push(i);
        else if (rt1==fx && rt2!=fy)
            b.push(i);
    }
    while (!a.empty() && !b.empty()){
        while (!a.empty()){
            int x=a.front();
            if (Getfa1(x)==Getfa1(rt)) a.pop();
            else break;
        }
        while (!b.empty()){
            int x=b.front();
            if (Getfa2(x)==Getfa2(rt)) b.pop();
            else break;
        }
        if (a.empty()||b.empty()) break;
        int x=a.front(),y=b.front();
        a.pop(),b.pop();
        Merge1(x,y),Merge2(x,y);
        ans.push_back({x,y});
    }
    printf("%d\n",ans.size());
    for (auto nw:ans){
        printf("%d %d\n",nw.first,nw.second);
    }
    return 0;
}