2020-7-31解题报告

狸狸养的敏敏 · 2020-07-31 16:29:25 · 个人记录

T1

可以通过微扰法证明操作的顺序不影响最终结果，因此我们考虑状压 dp

用 f[s] 表示让 s 二进制下为 1 的位全部成为朋友的代价（例如 101010 表示第 2,4,6 位上的人成为了朋友），可能会有一个想法，就是把已经成为朋友的点压缩成一个点，但是这种做法并不正确，只有与当前点开始时就直接相连的点才能在一次操作后成为朋友

以以下样例为例：

如果我们用矩阵存下这个图，矩阵应该长

我们发现，对 2 进行一次操作，对 4 进行一次操作，似乎整张图连通了，但是 (2,4)(1,5) 之间并没有满足要求，原因是我们操作了 2 之后，我们发现 4 并不在图中，因此此时不能直接对 4 进行操作

注意到这个细节之后，只需要正常的用状压 dp 进行转移就行

#include<bits/stdc++.h>
#define reg register
#define i64 long long
using namespace std;
int read(){int x=0,f=0;char ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();return f?-x:x;}
void Ot(int x){if(x<0)putchar('-'),x=-x;if(x>=10)Ot(x/10);putchar(x%10+48);}
void Print(int x,char til='\n'){Ot(x);putchar(til);}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int Abs(int x){return x<0?-x:x;}
const int MAXN=23,INF=0x3f3f3f3f;
int n,m,L;
int f[1<<MAXN],pre[1<<MAXN],res[1<<MAXN];
int mp[MAXN];
priority_queue<int>que; 
void PT(int x){if(pre[x])PT(pre[x]);/*que.push(-res[x]);*/Print(res[x]);}
signed main(){
    #ifndef ONLINE_JUDGE
//      freopen("C:/Users/Administrator/Desktop/data.txt","r",stdin);
//      freopen("C:/Users/Administrator/Desktop/out.txt","w",stdout);
    #endif
//  freopen("party.in","r",stdin);
//  freopen("party.out","w",stdout); 
    memset(f,0x3f,sizeof(f));
    n=read(),m=read(),L=(1<<n)-1;
    for(reg int i=1;i<=n;i++)mp[i]=(1<<(i-1));
    for(reg int i=1;i<=m;i++){
        int x=read(),y=read();
        mp[x]|=(1<<(y-1)),mp[y]|=(1<<(x-1));
    }
    bool flag=1;
    for(reg int i=1;i<=n;i++){
        f[mp[i]]=1,res[mp[i]]=i;
        if(mp[i]!=L)flag=0;
    }if(flag){return Print(0),0;}
    for(reg int i=1;i<=L;i++)
        if(f[i]!=INF)
            for(reg int j=1;j<=n;j++)
                if(((i>>(j-1))&1)&&(f[i]+1<f[i|mp[j]]))
                    f[i|mp[j]]=f[i]+1,pre[i|mp[j]]=i,res[i|mp[j]]=j;
    Print(f[L]);PT(L);
//  while(!que.empty())Print(-que.top(),' '),que.pop(); 
    #ifndef ONLINE_JUDGE
        fclose(stdin);fclose(stdout);
//      system("C:/Users/Administrator/Desktop/out.txt");
    #endif
    return 0;
}
/*
5 4
1 2
2 3
3 4
4 5

3
2 3 4
*/

T2

用了很玄学的方法过了=-=

我们发现 dist(u,v),\gcd(u,v),\min(u,v) 中，dist(u,v) 是递增的，\gcd(u,v) 是递减的，\min(u,v) 是递减的（至少是不增的），因此我们可以求出 dist(u,v) 的上界，也就是树的直径，然后进行剪枝，时间复杂度并不正确，但是确实是 N^2 过了

#include<bits/stdc++.h>
#define reg register
#define int long long
#pragma GCC optimize(2)
using namespace std;
int read(){int x=0,f=0;char ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();return f?-x:x;}
void Ot(int x){if(x<0)putchar('-'),x=-x;if(x>=10)Ot(x/10);putchar(x%10+48);}
void Print(int x,char til='\n'){Ot(x);putchar(til);}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int Abs(int x){return x<0?-x:x;}
const int MAXN=101010;
int tot,head[MAXN],a[MAXN];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
struct Edge{int v,w,nxt;}edge[MAXN<<1];
void addedge(int u,int v,int w){edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;}
struct Node{int x,val;};
bool mark[MAXN];
int lgst,ans,Top,n;
int Bfs(int x,int t){
    memset(mark,0,sizeof(mark));
    queue<Node>que;
    que.push((Node){x,0});
    reg int mx=0,mid=0;
    while(!que.empty()){
        Node h=que.front();
        que.pop();
        if(h.val>mx)mx=h.val,mid=h.x;
        for(reg int i=head[h.x];i;i=edge[i].nxt)
            if(!mark[edge[i].v]){
                que.push((Node){edge[i].v,h.val+edge[i].w});
                mark[edge[i].v]=1;          
            }
    }if(t)return mx;return mid;
}
void dfs(int x,int fa,int s,int g,int m){
    if(2*lgst*g*m<ans)return;//可以把剪枝限制放宽一点 
    if(s*g*m>ans)ans=s*g*m;
    for(reg int i=head[x];i;i=edge[i].nxt)
        if(edge[i].v!=fa)dfs(edge[i].v,x,s+edge[i].w,gcd(g,a[edge[i].v]),Min(m,a[edge[i].v])); 
}
signed main(){
    #ifndef ONLINE_JUDGE
//      freopen("C:/Users/Administrator/Desktop/data.txt","r",stdin);
//      freopen("C:/Users/Administrator/Desktop/out.txt","w",stdout);
    #endif
//  freopen("path.in","r",stdin);
//  freopen("path.out","w",stdout);
    for(reg int T=read();T;T--){
        memset(head,0,sizeof(head));
        n=read();ans=tot=lgst=0;
        for(reg int i=1;i<=n;i++)a[i]=read();
        for(reg int i=1;i<n;i++){
            int x=read(),y=read(),w=read();
            addedge(x,y,w);addedge(y,x,w); 
        }
        lgst=Bfs(Top=Bfs(1,0),1);
        dfs(Top,Top,0,a[Top],a[Top]);
        for(reg int i=1;i<=n;i++)dfs(i,i,0,a[i],a[i]);
        Print(ans);
    }
    #ifndef ONLINE_JUDGE
        fclose(stdin);fclose(stdout);
//      system("C:/Users/Administrator/Desktop/out.txt");
    #endif
    return 0;
}

T3

考虑如何选取两条边

首先我们对这个图任意生成一棵树，在树上的边我们称为树边，不在树上的边我们称为非树边，首先我们选取的两条边必定有一条是树边，因为就算把非树边全部删完也不会影响图本身的连通性

看到题目要求孤立出若干个点，由此我们想到割边的定义，考虑下面的情况

显然 (1,2) 这条边是图中的割边，一条边是割边，当且仅当他没有被任何非树边覆盖过，那么这个时候我们只需要选取这条割边，然后再任意选取一条其他的边即可

剩下我们考虑如下图的情况

显然如果我们的生成树是 1-2-3 那么在这张图中，我们可以通过删除两条树边 (1,2),(2,3) 来让点 2 孤立出来，类似的，如果把 2 号点再拆成若干个点，让这条路径再长一些，比如

那么此时，我们从 (1,2)(2,3)(3,4)(4,5) 中任选两条边删除都是符合题意的

由上面的分析我们可以发现，当覆盖两条树边的非树边集合相同时，删除这两条树边就是一种合法的方案

如何计算覆盖该树边的非树边集合，我们可以对每条非树边的两个端点之间的路径上的树边进行处理，使用类似 Hash 的方法，由于涉及路径上的操作，我们可以采用树上差分进行处理

#include<bits/stdc++.h>
#define reg register
#define int long long
#define ull unsigned long long 
using namespace std;
int read(){int x=0,f=0;char ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();return f?-x:x;}
void Ot(int x){if(x<0)putchar('-'),x=-x;if(x>=10)Ot(x/10);putchar(x%10+48);}
void Print(int x,char til='\n'){Ot(x);putchar(til);}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int Abs(int x){return x<0?-x:x;}
const int MAXN=100500;
struct Edge{int v,w,nxt;}edge[MAXN<<2];
struct Node{
    ull x,y;
    bool operator<(const Node &rhs)const {
        if(x==rhs.x)return y<rhs.y;
        return x<rhs.x;
    }
    Node operator^(const Node &rhs)const {
        Node n=(Node){x^rhs.x,y^rhs.y};
        return n;
    }
    bool operator==(const Node &rhs)const {
        return x==rhs.x&&y==rhs.y;
    } 
}val[MAXN],eval[MAXN];
int head[MAXN],tot;
int fa[MAXN];
void addedge(int u,int v,int w){edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;}
int getf(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
void dfs(int x,int fa){
    for(reg int i=head[x];i;i=edge[i].nxt)
        if(edge[i].v!=fa){
            dfs(edge[i].v,x),val[x]=val[x]^val[edge[i].v],eval[edge[i].w]=val[edge[i].v];
        }
}
int u[MAXN<<2],v[MAXN<<2];
ull GNB(){return 1ull*rand()*rand()*rand()*rand();}//Give me a number 
int n,m;
int ans;
signed main(){
    #ifndef ONLINE_JUDGE
//      freopen("C:/Users/Administrator/Desktop/data.txt","r",stdin);
//      freopen("C:/Users/Administrator/Desktop/out.txt","w",stdout);
    #endif
//  freopen("lutree.in","r",stdin);
//  freopen("lutree.out","w",stdout);
    srand(time(NULL));
    n=read(),m=read();
    for(reg int i=1;i<=n;i++)fa[i]=i;
    for(reg int i=1;i<=m;i++){
        u[i]=read(),v[i]=read();
        int fx=getf(u[i]),fy=getf(v[i]);
        if(fx!=fy)addedge(u[i],v[i],i),addedge(v[i],u[i],i),fa[fy]=fx;
        else eval[i]=(Node){GNB(),GNB()};//双Hash可以尽可能保证正确性
    }
    for(reg int i=1;i<=m;i++)
        if(eval[i].x||eval[i].y)val[u[i]]=val[u[i]]^eval[i],val[v[i]]=val[v[i]]^eval[i];//非树边的处理
    dfs(1,0);
    sort(eval+1,eval+m+1);
    for(reg int i=1,nt=0;i<=m;i=nt){
        if(!eval[i].x&&!eval[i].y)ans+=m-i,nt=i+1;//割边
        else {
            for(nt=i;nt<=m&&eval[i]==eval[nt];nt++);
                ans+=(nt-i)*(nt-i-1)/2;//覆盖集合相同的边
        }
    }
    Print(ans);
    #ifndef ONLINE_JUDGE
        fclose(stdin);fclose(stdout);
//      system("C:/Users/Administrator/Desktop/out.txt");
    #endif
    return 0;
}