CF1239E. Turtle
神秘贪心+dp题。
首先假设第一行和第二行所选的数已经定了，只用考虑摆放顺序。
设\(w_i\)为从第\(i\)行拐入第二行的答案。
对于第一行，假设有\(a_{1,i}>a_{1,i+1}\)时，交换\(a_{1,i}\)和\(a_{1,i+1}\)，发现此时\(w_{1\sim i-1}\)不变，\(s_{i+1\sim n}\)也不变，只有\(w_i\)变小，所以答案会变小或不变，总之不会变劣。
所以第一行一定是\(a_{1,1}\)到\(a_{1,n}\)从小到大排序，同理可得第二行一定是从大到小排序。
接下来可以研究\(w_i\)的差分数组\(c_i\)的单调性。
\(c_i=a_{1,i}-a_{2,i-1}\)，所以\(c_i\)单调递增，所以\(w_i\)具有凸性，且顶点处为最小值，所以最大值仅会出现在\(w_1\)和\(w_n\)之中。
发现\(w_1=\sum_{i=1}^{n}a_{2,i}+a_{1,1}=\sum_{i=1}^{2}\sum_{j=1}^{n}a_{i,j}-\sum_{i=1}^{n}a_{1,i}+a_{1,1}\)，\(w_n=\sum_{i=1}^{n}a_{1,i}+a_{2,n}\)都只和第一列的和有关，故可以用DP来求出第一行数的所有可能以及方案，复杂度\(O(n\sum a)\)但我们还需要枚举\(a_{1,1}\)和\(a_{2,n}\)复杂度需要多加\(n^2\)，无法通过。
此时我们可以发现\(a_{1,1}\)和\(a_{2,n}\)两个数在每一种路径中都会经过，所以取最小的两个数一定不劣。那么总时间就可以在\(O(n\sum a)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define il inline
struct IO
{static const int Size=(1<<21);char buf[Size],*p1,*p2;int st[105],Top;~IO(){clear();}il void clear(){fwrite(buf,1,Top,stdout);Top=0;}il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2)?EOF:*p1++;}il void pc(const char c){Top==Size&&(clear(),0);buf[Top++]=c;}il IO& operator >>(char& c){while(c=gc(),c==' ' || c=='\n' || c=='\r');return *this;}template<typename T>il IO& operator >>(T& x){x=0;bool f=0;char c=gc();while(!isdigit(c)){if(c=='-') f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}f?x=-x:0;return *this;}il IO& operator >>(string& s){s="";char c=gc();while(c==' ' || c=='\n' || c=='\r') c=gc();while(c!=' ' && c!='\n' && c!='\r' && c!=EOF) s+=c,c=gc();return *this;}il IO& operator <<(const char c){pc(c);return *this;}template<typename T> il IO& operator <<(T x){if(x<0) pc('-'),x=-x;do st[++st[0]]=x%10,x/=10;while(x);while(st[0]) pc(st[st[0]--]+'0');return *this;}il IO& operator <<(const string s){for(auto c:s) pc(c);return *this;}il IO& operator <<(const char* c){for(int i=0;c[i];i++) pc(c[i]);return *this;}
} fin,fout;
const int N=30,inf=1e9;
int a[N<<1],dp[N][N<<16],pre[N][N<<16],vis[N<<1],ans[2][N];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);int n;fin>>n;for(int i=1;i<=n*2;i++) fin>>a[i];sort(a+1,a+1+2*n);dp[1][a[1]]=1;pre[1][a[1]]=1;for(int i=3;i<=2*n;i++){for(int j=n;j>=2;j--){for(int k=a[i];k<=a[2*n]*n;k++){if(dp[j][k]) continue;dp[j][k]|=dp[j-1][k-a[i]];if(dp[j-1][k-a[i]]) pre[j][k]=i;}}}int sum=0,mn=inf,idx=0;for(int i=1;i<=2*n;i++) sum+=a[i];for(int i=1;i<=min(n*a[n*2],sum);i++){if(!dp[n][i]) continue;int val=max(i+a[2],sum-i+a[1]);if(val<mn) idx=i,mn=val;}for(int i=n;i>=1;i--){vis[pre[i][idx]]=1;ans[0][i]=a[pre[i][idx]];idx-=a[pre[i][idx]];}int now=n;for(int i=1;i<=n*2;i++){if(!vis[i]) ans[1][now--]=a[i];}for(int i=0;i<=1;i++){for(int j=1;j<=n;j++) fout<<ans[i][j]<<" ";fout<<"\n";}return 0;
}
CF521E Cycling City
首先我们会发现符合条件的点对的样子大概是环上加一条边的这条边上的两个点。对于这种带环的图论题，第一反应是找出一个生成树然后再生成树树跑路径，手玩几组会发现如果两个路径有边的交集，那么就可以构造出一组解。大概长这个样子
其中绿色为树边，红黄蓝三色为三条路径，及重合树边一条，绕到第一条非树边上的一条，绕到第二条非树边上的一条。
代码实现是可以直接暴力，因没有重合时复杂度和枚举每条树边的复杂度相等，有重合就可以直接统计答案了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
struct IO
{static const int Size=(1<<21);char buf[Size],*p1,*p2;int st[105],Top;~IO(){clear();}il void clear(){fwrite(buf,1,Top,stdout);Top=0;}il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2)?EOF:*p1++;}il void pc(const char c){Top==Size&&(clear(),0);buf[Top++]=c;}il IO& operator >>(char& c){while(c=gc(),c==' ' || c=='\n' || c=='\r');return *this;}template<typename T>il IO& operator >>(T& x){x=0;bool f=0;char c=gc();while(!isdigit(c)){if(c=='-') f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}f?x=-x:0;return *this;}il IO& operator >>(string& s){s="";char c=gc();while(c==' ' || c=='\n' || c=='\r') c=gc();while(c!=' ' && c!='\n' && c!='\r' && c!=EOF) s+=c,c=gc();return *this;}il IO& operator <<(const char c){pc(c);return *this;}template<typename T> il IO& operator <<(T x){if(x<0) pc('-'),x=-x;do st[++st[0]]=x%10,x/=10;while(x);while(st[0]) pc(st[st[0]--]+'0');return *this;}il IO& operator <<(const string s){for(auto c:s) pc(c);return *this;}il IO& operator <<(const char* c){for(int i=0;c[i];i++) pc(c[i]);return *this;}
} fin,fout;
const int N=200010;
int f[N],h[N],tot,vis[N],d[N],F[N],col[N],ff[20][N];
struct node
{int nxt,to;
} e[N<<1];
struct edge
{int u,v;
} E[N];
vector<int> huan[N];
void add(int u,int v)
{tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
int fnd(int x)
{if(f[x]==x) return x;return f[x]=fnd(f[x]);
}
void dfs(int u,int fa)
{d[u]=d[fa]+1;F[u]=fa;ff[0][u]=fa;for(int i=1;i<=19;i++) ff[i][u]=ff[i-1][ff[i-1][u]];for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa) continue;dfs(v,u);}
}
int get_lca(int u,int v)
{if(d[u]<d[v]) swap(u,v);for(int i=19;i>=0;i--){if(d[ff[i][u]]>=d[v]) u=ff[i][u];}if(u==v) return u;for(int i=19;i>=0;i--){if(ff[i][u]!=ff[i][v]) u=ff[i][u],v=ff[i][v];}return ff[0][u];
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);int n,m;fin>>n>>m;for(int i=1;i<=m;i++) fin>>E[i].u>>E[i].v;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){int u=E[i].u,v=E[i].v;if(fnd(u)!=fnd(v)){vis[i]=1;f[fnd(u)]=fnd(v);add(u,v);add(v,u);}}for(int i=1;i<=n;i++) if(f[i]==i) dfs(i,0);vector<int> tmp,tmp2;for(int i=1;i<=m;i++){if(!vis[i]){int u=E[i].u,v=E[i].v,lca=get_lca(u,v);int idx=0,lst=0;while(u!=lca){huan[i].push_back(u);if(col[u] && !idx) idx=col[u];if(col[u] && col[u]==idx) tmp.push_back(u),lst=F[u];col[u]=i;u=F[u];}int fl=0;if(lst) tmp.push_back(lst);if(lst==lca) fl=1;huan[i].push_back(lca);vector<int> tmp3;lst=0;while(v!=lca){tmp3.push_back(v);if(col[v] && !idx) idx=col[v];if(col[v] && col[v]==idx) tmp2.push_back(v),lst=F[v];col[v]=i;v=F[v];}if(lst){if(lst!=lca) tmp2.push_back(lst);else if(!fl) tmp.push_back(lst);}reverse(tmp3.begin(),tmp3.end());for(int j:tmp3) huan[i].push_back(j);if(idx){fout<<"YES\n";reverse(tmp2.begin(),tmp2.end());for(int j:tmp2) tmp.push_back(j);fout<<tmp.size()<<" ";for(int j:tmp) fout<<j<<" ";fout<<"\n";vector<int> ans;u=tmp[0],v=tmp[(int)tmp.size()-1];reverse(huan[i].begin(),huan[i].end());fl=0;for(int j:huan[i]){if(j==u) fl=1;if(fl) ans.push_back(j);}for(int j:huan[i]){ans.push_back(j);if(j==v) break;}fout<<ans.size()<<" ";for(int j:ans) fout<<j<<" ";fout<<"\n";int idx1=0,idx2=0;for(int j=0;j<(int)huan[idx].size();j++){if(huan[idx][j]==u) idx1=j;if(huan[idx][j]==v) idx2=j;}if(idx1<idx2) reverse(huan[idx].begin(),huan[idx].end());vector<int> ().swap(ans);fl=0;for(int j:huan[idx]){if(j==u) fl=1;if(fl) ans.push_back(j);}for(int j:huan[idx]){ans.push_back(j);if(j==v) break;}fout<<ans.size()<<" ";for(int j:ans) fout<<j<<" ";fout<<"\n";return 0;}}}fout<<"NO";return 0;
}
CF1142E Pink Floyd
这是啥必做的交互吗。