Codeforces Round 1280 简要题解

A. Cut and Paste

略

B. Beingawesomeism

略

C. Jeremy Bearimy

略

D. Miss Punyverse

令点$i$的权值$c_i=w_i?b_i$，则一个连通块有贡献当且仅当$\sum c_i>0$。
考虑一个显然的DP，设$F[i][j][k]$表示考虑点$i$为根的子树，除根结点所在的连通块恰有$j$个，其中有$k$个是有贡献的情况下，根节点所在的连通块（可能会跟父亲合并）的最大权值和，转移直接做背包即可。
这样复杂度太高了，但可以发现对于两个状态$F[i][j][k_1]$和$F[i][j][k_2]$，若$k_1<k_2$则$F[i][j][k_1]$转移到的最终的答案不会超过$F[i][j][k_2]$转移到的，因此对于$k$这一维只用保留最大的即可。具体的，令$G[i][j]$考虑点$i$为根的子树，除根结点所在的连通块恰有$j$个的情况下，最大的一个（其中有贡献的连通块数目，根节点所在的连通块权值和）的pair。
简单分析可以知道单组数据时间复杂度为$\mathcal{O}(nm)$。

#include <bits/stdc++.h>
#define MOD 1000000007
#define FR first
#define SE second
#define inf 0x3f3f3f3f3f3f3f3fLLusing namespace std;typedef long long ll;
typedef pair<int,ll> pr;inline pr merge(pr x,pr y) {
    return pr(x.FR+y.FR,x.SE+y.SE);
}vector <int> e[3005];
int num[3005];pr f[3005][3005];
int k,ans;int dfs(int x,int fa) {
    static pr g[3005];int s=0;f[x][0]=pr(0,0);for(int i=0;i<e[x].size();i++)if (e[x][i]!=fa) {
    int u=e[x][i];int t=dfs(u,x);for(int j=0;j<=s+t;j++) g[j]=pr(0,-inf);for(int j=0;j<=s;j++)for(int k=0;k<=t;k++) g[j+k]=max(g[j+k],merge(f[x][j],f[u][k]));for(int j=0;j<=s+t;j++) f[x][j]=g[j];s+=t;}if (x==1) ans=f[1][k-1].FR+(f[1][k-1].SE+num[1]>0);f[x][s+1]=pr(f[x][s].FR+(f[x][s].SE+num[x]>0),0);for(int i=s;i>0;i--) f[x][i]=max(pr(f[x][i].FR,f[x][i].SE+num[x]),pr(f[x][i-1].FR+(f[x][i-1].SE+num[x]>0),0));f[x][0].SE+=num[x];s++;return s;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int n;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {
    e[i].clear();num[i]=0;}for(int i=1;i<=n;i++) {
    int x;scanf("%d",&x);num[i]-=x;} for(int i=1;i<=n;i++) {
    int x;scanf("%d",&x);num[i]+=x;}for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}dfs(1,0);printf("%d\n",ans);}return 0;
} 

E. Kirchhoff’s Current Loss

先忽略每个叶子的阻值要是整数的限制，考虑在实数域上做这个最优化问题。
对于点$i$，令$f_i(x)$表示考虑点$i$子树，最小的叶子阻值和关于点$i$的阻值的函数，容易归纳证明$f_i(x)$是一个正比例函数（我们显然可以对子树做常数倍放缩）。
定义$c$为$f_i(x)$的斜率，令点$i$的儿子的函数斜率分别为$c_1,c_2,...,c_k$。
对于叶子显然有$c_i=1$。
对于串联显然有$c_i={\min }_{i=1}^k{c}_i$，此时只保留$c_i$最小的儿子。
并联稍微有点麻烦。分析一下，考虑令点$i$的阻值为$1$，此时点$i$的儿子的阻值分别为$R_1,R_2,...,R_k$，那么就是要最小化$c={\sum }_{i=1}^k{c}_i{R}_i$，且${\sum }_{i=1}^k\frac{1}{R_i}=1$。用拉格朗日乘数法，可以求解出当$R_i=\frac{{\sum }_{i=1}^k\sqrt{c_i}}{\sqrt{c_i}}$时取到最小值，此时$\sqrt{c}={\sum }_{i=1}^k\sqrt{c_i}$。
注意到每个点的$\sqrt{c}$都是整数，因此$f_1(r)$也是整数。再分析一下可以发现，令$1$号点的$\sqrt{c}$为$v$，则$f_1(r)=v^{2}r$，取到最优解时每个阻值非$0$的叶子阻值均为$vr$，也是整数。因此事实上整数的限制可以忽略。
直接求出$v$并dfs出所有阻值非$0$的叶子即可，单组数据时间复杂度$\mathcal{O}(n)$。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;vector <int> e[200005];int f[200005],id[200005],dfs_cnt;
bool col[200005],ban[200005];void dfs1(int x) {
    if (!e[x].size()) {
    id[x]=++dfs_cnt;f[x]=1;return;}if (!col[x]) {
    int minn=0;for(int i=0;i<e[x].size();i++) {
    int u=e[x][i];dfs1(u);if (f[u]<f[minn]) minn=u;}f[x]=f[minn];for(int i=0;i<e[x].size();i++)if (e[x][i]!=minn) ban[e[x][i]]=1;}else {
    for(int i=0;i<e[x].size();i++) {
    int u=e[x][i];dfs1(u);f[x]+=f[u];}}
}bool vis[200005];void dfs2(int x) {
    if (!e[x].size()) {
    vis[id[x]]=1;return;}for(int i=0;i<e[x].size();i++)if (!ban[e[x][i]]) dfs2(e[x][i]);
}char str[2000005];
int st[2000005];void build(int n) {
    int sz=0,top=0;for(int i=1;i<=n;i++)if (str[i]=='(') {
    e[++sz].clear();if (top) e[st[top]].push_back(sz);st[++top]=sz;ban[sz]=vis[sz]=f[sz]=0;}else if (str[i]=='*') {
    e[++sz].clear();ban[sz]=vis[sz]=f[sz]=0;if (top) e[st[top]].push_back(sz);}else if (str[i]=='S') col[st[top]]=0;else if (str[i]=='P') col[st[top]]=1;else if (str[i]==')') top--;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int r;scanf("%d",&r);cin.getline(str,2e6);int len=strlen(str+1);build(len);dfs_cnt=0;f[0]=inf;dfs1(1);dfs2(1);int s=0;for(int i=1;i<=dfs_cnt;i++) s+=vis[i];printf("REVOLTING ");for(int i=1;i<=dfs_cnt;i++) printf("%lld ",(vis[i])?(ll)s*r:0LL);printf("\n");}return 0;
} 

F. Intergalactic Sliding Puzzle

注意到操作是可逆的，并且如果$E$在某一行一定可以移到中间。我们称一个$E$在第二行中间的状态为标准状态，那么可以将初态和终态均移成标准状态，并且要求在标准状态间转移。这样的转移只能是一个旋转操作（旋两行左半边和第一行中间；两行右半边和第一行中间；全部）。
考虑从上到下，从左到右写下当前状态的每个数字，得到一个$4k+1$的排列$P$。注意到旋转操作旋转的长度都是奇数，因此不会改变$P$的奇偶性。那么若$P$是奇排列显然无解，偶排列的话我们下面给出构造。
对于左半边的两个数$a$和$b$，右半边的数$c$，我们可以先将$b$旋到中间（旋左半边）；再将$c$旋到中间（旋右半边）；再将$a$选到中间（旋左半边）；再将$b$旋到中间，此时$a$到了原来$c$的位置；再将$b$旋到原来$a$的位置，此时$c$恰好到了原来$b$的位置。注意到这样操作相当于$(a,b,c)$变成了$(b,c,a)$，当$b$在右半边的时候也类似。
有了这个操作就很好做了。考虑先将$k+1$旋到第一行中间。然后对于当前在左半边但终态不该在的数，跟右半边终态不该在的数一一匹配，用上面的操作即可交换（分别设为$a$和$c$，随便找个$b$就好了）。
对于左半边的数字$(a,b)$和右半边的数字$(c,d)$，依次使用上面的操作$(a,b),(c,d)$->$(b,d),(c,a)$->$(b,a),(d,c)$，于是可以每次在两边分别做一个对换。注意到整个排列是偶排列，因此两边内部做对换达到终态次数的奇偶性相同，那么直接做就好了。
把左旋和右旋写成shortcut，那么单组数据时间复杂度和压缩后操作序列长度都是$\mathcal{O}(k^2)$。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;int num[70];
string ans;bool init(int n) {
    ans.clear(); int id[70];memset(id,0,sizeof(id));for(int i=1;i<=n;i++) id[n-i+1]=i;for(int i=n+1;i<=2*n;i++) id[n+i+1]=i;for(int i=2*n+1;i<=3*n;i++) id[i-n+1]=i;for(int i=3*n+1;i<=4*n;i++) id[7*n+2-i]=i;id[n+1]=4*n+1;for(int i=1;i<=4*n+2;i++) num[i]=id[num[i]];int u=0;for(int i=1;i<=4*n+2;i++)if (!num[i]) {
    u=i;break;}if (u<=n) {
    for(int i=1;i<=u;i++) ans+="r";ans+="d";for(int i=u;i>1;i--) swap(num[i],num[i-1]);swap(num[1],num[4*n+1]);swap(num[4*n+1],num[4*n+2]);}else if (u<=2*n) {
    for(int i=u;i<=2*n;i++) ans+="r";for(int i=u;i<2*n;i++) swap(num[i],num[i+1]);swap(num[2*n],num[4*n+2]);}else if (u<=3*n) {
    for(int i=u;i>2*n;i--) ans+="l";ans+="d";for(int i=u;i>2*n+1;i--) swap(num[i],num[i-1]);swap(num[2*n+1],num[4*n+1]);swap(num[4*n+1],num[4*n+2]);}else if (u<=4*n) {
    for(int i=u;i<=4*n;i++) ans+="l";for(int i=u;i<4*n;i++) swap(num[i],num[i+1]);swap(num[4*n],num[4*n+2]);}else if (u==4*n+1) {
    ans+="d";swap(num[4*n+1],num[4*n+2]);}bool s=0;for(int i=1;i<=4*n+1;i++)for(int j=i+1;j<=4*n+1;j++)if (num[i]>num[j]) s^=1;return s^1; 
}void gettrans(int n) {
    printf("A ");putchar('u');for(int i=1;i<=n;i++) putchar('l');putchar('d');for(int i=1;i<=n;i++) putchar('r');printf("\n");printf("B ");for(int i=1;i<=n;i++) putchar('l');putchar('u');for(int i=1;i<=n;i++) putchar('r');putchar('d');printf("\n");printf("C ");putchar('u');for(int i=1;i<=n;i++) putchar('r');putchar('d');for(int i=1;i<=n;i++) putchar('l');printf("\n");printf("D ");for(int i=1;i<=n;i++) putchar('r');putchar('u');for(int i=1;i<=n;i++) putchar('l');putchar('d');printf("\n");
}void swap1(int x,int y,int z,int n) {
    z-=2*n;for(int i=1;i<=y;i++) ans+="A";for(int i=1;i<=z;i++) ans+="C";for(int i=1;i<=(x-y+2*n+1)%(2*n+1);i++) ans+="A";for(int i=1;i<=z;i++) ans+="D";for(int i=1;i<=x;i++) ans+="B";z+=2*n;swap(num[x],num[z]);swap(num[y],num[x]);
}void swap2(int x,int y,int z,int n) {
    x-=2*n;y-=2*n; for(int i=1;i<=y;i++) ans+="C";for(int i=1;i<=z;i++) ans+="A";for(int i=1;i<=(x-y+2*n+1)%(2*n+1);i++) ans+="C";for(int i=1;i<=z;i++) ans+="B";for(int i=1;i<=x;i++) ans+="D";x+=2*n;y+=2*n;swap(num[x],num[z]);swap(num[y],num[x]);
}void solve(int n) {
    int id=0;for(int i=1;i<=4*n+1;i++)if (num[i]==4*n+1) {
    id=i;break;}if (id<=2*n) {
    for(int i=1;i<=id;i++) {
    ans+="A";swap(num[4*n+1],num[1]);for(int j=1;j<2*n;j++) swap(num[j],num[j+1]);}}else if (id<=4*n) {
    for(int i=1;i<=id-2*n;i++) {
    ans+="C";swap(num[4*n+1],num[2*n+1]);for(int j=2*n+1;j<4*n;j++) swap(num[j],num[j+1]);}}for(;;) {
    int u=0,v=0;for(int i=1;i<=2*n;i++) {
    if (num[i]>2*n) u=i;if (num[2*n+i]<=2*n) v=2*n+i;}if (!u) break;if (u==1) swap1(u,2,v,n);else swap1(u,1,v,n);}pr a[70],b[70];bool vis[70];memset(vis,0,sizeof(vis));int sz1=0,sz2=0;for(int i=1;i<=2*n;i++)if (!vis[i]) {
    int x=i,cur[70],cnt=0;do {
    cur[++cnt]=x;vis[x]=1;x=num[x];} while (x!=i);for(int j=cnt;j>1;j--) a[++sz1]=pr(cur[j-1],cur[j]);}for(int i=2*n+1;i<=4*n;i++)if (!vis[i]) {
    int x=i,cur[70],cnt=0;do {
    cur[++cnt]=x;vis[x]=1;x=num[x];} while (x!=i);for(int j=cnt;j>1;j--) b[++sz2]=pr(cur[j-1],cur[j]);}while (sz1<sz2) a[++sz1]=pr(1,2);while (sz2<sz1) b[++sz2]=pr(2*n+1,2*n+2);for(int i=1;i<=sz1;i++) {
    swap1(a[i].FR,a[i].SE,b[i].SE,n);swap2(b[i].SE,b[i].FR,a[i].SE,n);}for(int i=1;i<=n;i++) ans+="r";
}int rd() {
    string s;cin>>s;if (s[0]=='E') return 0;return atoi(s.c_str());
}int b[70];
string cur;bool check(int n) {
    cur.clear();int id=0;for(int i=1;i<=4*n+2;i++)if (!b[i]) {
    id=i;break;}for(int i=0;i<ans.size();i++)if (ans[i]>='a'&&ans[i]<='z') cur+=ans[i];else if (ans[i]=='A') {
    cur+="u";for(int i=1;i<=n;i++) cur+="l";cur+="d";for(int i=1;i<=n;i++) cur+="r";}else if (ans[i]=='B') {
    for(int i=1;i<=n;i++) cur+="l";cur+="u";for(int i=1;i<=n;i++) cur+="r";cur+="d";}else if (ans[i]=='C') {
    cur+="u";for(int i=1;i<=n;i++) cur+="r";cur+="d";for(int i=1;i<=n;i++) cur+="l";}else {
    for(int i=1;i<=n;i++) cur+="r";cur+="u";for(int i=1;i<=n;i++) cur+="l";cur+="d";}for(int i=0;i<cur.length();i++)if (cur[i]=='l') {
    if (id==1||id==2*n+2) return 0;swap(b[id],b[id-1]);id--;}else if (cur[i]=='r') {
    if (id==2*n+1||id==4*n+2) return 0;swap(b[id],b[id+1]);id++;}else if (cur[i]=='u') {
    if (id!=2*n+2&&id!=3*n+2&&id!=4*n+2) return 0;swap(b[id],b[id-2*n-1]);id-=2*n+1;}else {
    if (id!=1&&id!=n+1&&id!=2*n+1) return 0;swap(b[id],b[id+2*n+1]);id+=2*n+1;}for(int i=1;i<=4*n+1;i++)if (b[i]!=i) return 0;return 1;
}int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int n;scanf("%d",&n);for(int i=n;i>0;i--) num[i]=rd();num[4*n+1]=rd();for(int i=2*n+1;i<=3*n;i++) num[i]=rd();for(int i=n+1;i<=2*n;i++) num[i]=rd();num[4*n+2]=rd();for(int i=4*n;i>3*n;i--) num[i]=rd();/*for(int i=1;i<=n;i++) b[i]=num[n-i+1];b[n+1]=num[4*n+1];for(int i=n+2;i<=2*n+1;i++) b[i]=num[i+n-1];for(int i=2*n+2;i<=3*n+1;i++) b[i]=num[i-n-1];b[3*n+2]=num[4*n+2];for(int i=3*n+3;i<=4*n+2;i++) b[i]=num[7*n+3-i];*/if (!init(n)) {
    puts("SURGERY FAILED");continue;}puts("SURGERY COMPLETE");solve(n);cout<<ans<<endl;gettrans(n);puts("DONE");//assert(check(n));}return 0;
}