Atcoder 杂题三道
T1 Integers on a Tree
大意：给你一棵树，开局已经确定了某些点的权值，要求在 O(n) 的时间内，判定是否存在一种安排权值的方案使得相邻点等权值恰好相差一，输出方案
题解：可以观察到，从已知的某个点等限制向外扩展，到达的点的限制必定是公差为2的等差数列，于是遍历一遍整棵树，把每个点的限制处理出来即可，需要维护等操作是合并两个等差数列（取交集），以及这个等差数列稍微变一下
1 #include<bits/stdc++.h> 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++) 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--) 4 #define mem(i,j) memset(i,j,sizeof(i)) 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxxt[j]) 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define pii pair<int,int> 10 #define MP make_pair 11 using namespace std; 12 typedef long long ll; 13 const int N=2e5+5; 14 int n,tmp1,tmp2,k,vv[N],p[N],col[N],tag[N],ans[N]; 15 int tot=0,f[N],nxxt[N<<1]; 16 struct E 17 { 18 int u,v; 19 }e[N<<1]; 20 inline void add(int u,int v) 21 { 22 tot++; 23 nxxt[tot]=f[u]; 24 f[u]=tot; 25 e[tot]=(E){u,v}; 26 return; 27 } 28 inline int read() 29 { 30 int x=0,f=1; 31 char c=getchar(); 32 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} 33 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} 34 return f*x; 35 } 36 inline void write(int x) 37 { 38 if (x<0) putchar('-'),x=-x; 39 if (x>9) write(x/10); 40 putchar(x%10+'0'); 41 return; 42 } 43 struct data 44 { 45 int first,siz; 46 inline data work() 47 { 48 data ret; 49 ret.first=first-1; 50 ret.siz=siz+1; 51 return ret; 52 } 53 inline void merge(data x) 54 { 55 if (first==-1&&siz==-1) {first=x.first;siz=x.siz;return;} 56 if (((x.first+2*n)%2)!=((first+2*n)%2)) {first=0;siz=0;return;} 57 int min1=first,max1=first+(siz-1)*2,min2=x.first,max2=x.first+(x.siz-1)*2; 58 int mn=max(min1,min2),mx=min(max1,max2); 59 if (mn>mx) {first=0,siz=0;return;} 60 first=mn; 61 siz=(mx-mn)/2+1; 62 return; 63 } 64 inline void Print() 65 { 66 write(first),putchar(' '),write(siz),putchar('\n'); 67 return; 68 } 69 }s[N]; 70 inline void no() 71 { 72 printf("No\n"); 73 exit(0); 74 } 75 inline data dfs(int u,int fa) 76 { 77 if (s[u].siz==0) no(); 78 data tmp,ret; 79 data nxt=s[u].work(); 80 GO(u) 81 { 82 int v=e[j].v; 83 if (v==fa) continue; 84 s[v].merge(nxt); 85 tmp=dfs(v,u); 86 s[u].merge(tmp); 87 if (s[u].siz==0) no(); 88 } 89 ret=s[u].work(); 90 return ret; 91 } 92 inline void debug() 93 { 94 FOR(i,1,n) 95 { 96 printf("%d : ",i); 97 s[i].Print(); 98 } 99 return; 100 } 101 inline void confirm(int u,int fa) 102 { 103 if (s[u].first==-1) s[u]=(data){1,1}; 104 ans[u]=s[u].first; 105 s[u].siz=1; 106 data nxt=s[u].work(); 107 GO(u) 108 { 109 int v=e[j].v; 110 if (v==fa) continue; 111 s[v].merge(nxt); 112 confirm(v,u); 113 } 114 return; 115 } 116 int main() 117 { 118 mem(f,-1); 119 n=read(); 120 FOR(i,1,n-1) tmp1=read(),tmp2=read(),add(tmp1,tmp2),add(tmp2,tmp1); 121 k=read(); 122 FOR(i,1,k) vv[i]=read(),p[i]=read(),col[vv[i]]=p[i],tag[vv[i]]=1,s[vv[i]]=(data){p[i],1}; 123 FOR(i,1,n) if (!tag[i]) s[i]=(data){-1,-1}; 124 dfs(vv[1],0); 125 confirm(vv[1],0); 126 printf("Yes\n"); 127 FOR(i,1,n) write(ans[i]),putchar('\n'); 128 return 0; 129 }
T2 Shik and Travel
大意：给一棵二叉树，所有非叶子的儿子数为二，从根搜索一遍这棵树，最小化从一个叶子到下一个叶子的路径和的最大值
题解：
- 最小化最大值，二分这个答案
- 在每个点记录这个点等所有状态，从下往上合并，每个状态是一个二元组 (a,b) ,表示这个点下去到第一个叶子的距离是a，最后一个叶子回到这个点的距离是b，这个两个值待和其他状态合并
- 由于状态数过多，考虑舍弃必定不如已有状态优等状态，对于 (a,b) 和 (c,d) ，若我们把 a 和 c 拼在一起，就得到了 (a,d) ，同理另外一种得到了 (c,b) ，以前者为例，对于固定的 a，在 (b+c) 符二分出等权值时，我们希望最小的 d,于是合并的时候先排序，然后 two pointers 扫一扫就行了
1 #include<bits/stdc++.h> 2 #define FOR(i,a,b) for (register ll i=(a);i<=(b);i++) 3 #define For(i,a,b) for (register ll i=(a);i>=(b);i--) 4 #define mem(i,j) memset(i,j,sizeof(i)) 5 #define GO(u) for (register ll j=f[u];j!=-1;j=nxt[j]) 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define pii pair<ll,ll> 10 #define MP make_pair 11 using namespace std; 12 typedef long long ll; 13 const ll N=150000; 14 ll n,a[N],v[N],mn[20000005],L,R,MID,du[N]; 15 vector <pii> F[N]; 16 ll tot=0,f[N],nxt[N<<1]; 17 struct E 18 { 19 ll u,v,w; 20 }e[N<<1]; 21 inline void add(ll u,ll v,ll w) 22 { 23 tot++; 24 nxt[tot]=f[u]; 25 f[u]=tot; 26 e[tot]=(E){u,v,w}; 27 return; 28 } 29 inline ll read() 30 { 31 ll x=0,f=1; 32 char c=getchar(); 33 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} 34 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} 35 return f*x; 36 } 37 inline void write(ll x) 38 { 39 if (x<0) putchar('-'),x=-x; 40 if (x>9) write(x/10); 41 putchar(x%10+'0'); 42 return; 43 } 44 bool cmpfi(const pii x,const pii y) {return x.fi<y.fi;} 45 bool cmpse(const pii x,const pii y) {return x.se<y.se;} 46 inline void update(vector<pii> &G,ll ls,ll rs) 47 { 48 ll siz1=F[ls].size(),siz2=F[rs].size(); 49 if ((!siz1)||(!siz2)) return; 50 if (siz1>siz2) swap(ls,rs),swap(siz1,siz2); 51 sort(F[ls].begin(),F[ls].end(),cmpfi); 52 sort(F[rs].begin(),F[rs].end(),cmpse); 53 mn[0]=F[rs][0].fi; 54 FOR(i,1,siz2-1) mn[i]=min(mn[i-1],F[rs][i].fi); 55 for (register ll i=0,pt=siz2-1;i<siz1;i++) 56 { 57 while (pt>-1&&F[ls][i].fi+F[rs][pt].se>MID) pt--; 58 if (pt>=0) G.pb(MP(mn[pt],F[ls][i].se)); 59 } 60 sort(F[ls].begin(),F[ls].end(),cmpse); 61 sort(F[rs].begin(),F[rs].end(),cmpfi); 62 mn[0]=F[rs][0].se; 63 FOR(i,1,siz2-1) mn[i]=min(mn[i-1],F[rs][i].se); 64 for (register ll i=0,pt=siz2-1;i<siz1;i++) 65 { 66 while (pt>-1&&F[ls][i].se+F[rs][pt].fi>MID) pt--; 67 if (pt>=0) G.pb(MP(F[ls][i].fi,mn[pt])); 68 } 69 return; 70 } 71 inline void dfs(ll u,ll fa) 72 { 73 int lson=0,rson=0; 74 F[u].clear(); 75 if (du[u]==1){F[u].pb(MP(0,0));return;} 76 GO(u) 77 { 78 ll v=e[j].v; 79 if (v==fa) continue; 80 if (!lson) lson=v; 81 else rson=v; 82 dfs(v,u); 83 } 84 GO(u) 85 { 86 ll v=e[j].v; 87 if (v==fa) continue; 88 FOR(i,0,(ll)F[v].size()-1) 89 { 90 F[v][i].fi+=e[j].w; 91 F[v][i].se+=e[j].w; 92 } 93 } 94 update(F[u],lson,rson); 95 return; 96 } 97 int main() 98 { 99 // freopen("data.in","r",stdin); 100 mem(f,-1); 101 n=read(); 102 FOR(i,2,n) a[i]=read(),v[i]=read(),add(i,a[i],v[i]),add(a[i],i,v[i]),du[i]++,du[a[i]]++; 103 L=0,R=1e9; 104 while (L<R) 105 { 106 MID=(L+R)>>1; 107 dfs(1,0); 108 if (F[1].size()) R=MID; 109 else L=MID+1; 110 } 111 write(L); 112 return 0; 113 }
T3 Mole and Abandoned Mine
大意：给出一个15个点的无向带权图，问最少花费多少的代价删边，使得从1到n有唯一的简单路径
题解：
- 假如我们知道了最终那条从1到n的路径，那么连接路径上相邻两个点的边必定是桥，即每个点下面可以挂一个连通块
- 设计状态 dp[i][S] 表示从1到 i 的路径，其中安排了 S 这么多点，最多能保留的边权
转移：dp [ j ][ T ] = max{ dp [ i ] [ S ] + w+ val [ T ^ S ] }
1 #include<bits/stdc++.h> 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++) 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--) 4 #define mem(i,j) memset(i,j,sizeof(i)) 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j]) 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define pii pair<int,int> 10 #define MP make_pair 11 using namespace std; 12 typedef long long ll; 13 const int N=20; 14 const int M=500; 15 const int P=1<<16; 16 int n,m,x,y,z,dp[N][P],G[N][N],tot,sum=0,g[P],ans; 17 inline int read() 18 { 19 int x=0,f=1; 20 char c=getchar(); 21 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} 22 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} 23 return f*x; 24 } 25 inline void write(int x) 26 { 27 if (x<0) putchar('-'),x=-x; 28 if (x>9) write(x/10); 29 putchar(x%10+'0'); 30 return; 31 } 32 int main() 33 { 34 // freopen("data.in","r",stdin); 35 mem(G,-1); 36 n=read(),m=read(); 37 FOR(i,1,m) 38 { 39 x=read(),y=read(),z=read(); 40 sum+=z; 41 G[x][y]=G[y][x]=z; 42 } 43 tot=(1<<n)-1; 44 FOR(i,1,tot) 45 FOR(j,0,n-1) if ((i>>j)&1) 46 FOR(k,j,n-1) if ((i>>k)&1) 47 if (G[j+1][k+1]!=-1) g[i]+=G[j+1][k+1]; 48 mem(dp,-1); 49 dp[1][1]=0; 50 FOR(S,1,tot) 51 { 52 FOR(i,0,n-1) if (((S>>i)&1)&&dp[i+1][S]!=-1) 53 { 54 int ss=(tot xor S)|(1<<i); 55 for (register int s=ss;s;s=(s-1)&ss) 56 { 57 if (!((s>>i)&1)) continue; 58 dp[i+1][S|s]=max(dp[i+1][S|s],dp[i+1][S]+g[s]); 59 } 60 FOR(j,0,n-1) 61 { 62 if ((S>>j)&1) continue; 63 if (G[i+1][j+1]==-1) continue; 64 dp[j+1][S|(1<<j)]=max(dp[j+1][S|(1<<j)],dp[i+1][S]+G[i+1][j+1]); 65 } 66 } 67 } 68 ans=sum-dp[n][tot]; 69 write(ans); 70 return 0; 71 }