E-Both Sides Merger
给你一个序列，支持两种操作，直到序列中只有一个数时停下来，使得剩下数最大，并输出选数方案。
操作1：扔掉一个最前端或最后端的元素。操作2：选取一个不在边界上的元素，取其相邻两个数的和替换它，并删去它相邻的两个数。
n<=1000,|ai|<=1e9。
结论1：最后留下的数是原序列若干个数的和，并且这些数的下标同奇偶。
证明：一次两边往中间合并的过程等价于右边那个加在左边那个上，并删去中间的和右边的。由此发现整个数列下标的奇偶性都不变。
因为最后选择的两个数下标同奇偶，而这两个是由与它们下标同奇偶的另一些数构成的，因此所有选择的数同奇偶。
结论2：任意一种合法的取数方法，都可以构造成功。
证明：每两个待选数中间有奇数个数，可以一直用操作2使得每两个数相隔一位。再选择中间的元素合并即可。
取奇数/偶数的正数和较大的进行构造。选数方案从后往前选可以使得前面的下标不变，比较好处理。
对整个序列都是负数的特判一下。注意Max要设为负数。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1005; 4 int n,Max,pos,tot,ans[N],a[N]; 5 vector<int> vec; 6 typedef long long ll; 7 ll sum1,sum2; 8 int main() 9 { 10 scanf("%d",&n);Max=-1e9-1;//注意max要赋值成负的！ 11 for (int i=1;i<=n;i++) 12 { 13 scanf("%d",&a[i]);if (a[i]>Max) Max=a[i],pos=i; 14 if (i&1) sum1+=(a[i]>0)?a[i]:0; 15 else sum2+=(a[i]>0)?a[i]:0; 16 } 17 if (Max<0) 18 { 19 printf("%d %d ",Max,n-1); 20 for (int i=n;i>pos;i--) printf("%d ",i); 21 for (int i=1;i<pos;i++) puts("1"); 22 return 0; 23 } 24 for (int i=(sum1>sum2?1:2);i<=n;i+=2) if (a[i]>0) vec.push_back(i); 25 printf("%lld ",max(sum1,sum2)); 26 for (int i=n;i>vec[vec.size()-1];i--) ans[++tot]=i; 27 for (int i=vec.size()-1;i>=1;i--) 28 { 29 int t=(vec[i]-vec[i-1])/2-1; 30 while (t--) ans[++tot]=vec[i-1]+2; 31 ans[++tot]=vec[i-1]+1; 32 } 33 for (int i=1;i<vec[0];i++) ans[++tot]=1; 34 printf("%d ",tot); 35 for (int i=1;i<=tot;i++) printf("%d ",ans[i]); 36 return 0; 37 }
F-Two Faces Edges
对于每一条边问反转方向后图中连通块的个数会否改变？n<=1000.
对于一条边u->v来说，考虑两个判定条件：1.v->u是否成立。2.u->v不经过(u,v)是否成立。
当这两个判定有且仅有一个成立时连通块个数会改变。第一个dfs一下。第二个按照邻接表正反dfs一下，并记录到达某个点的前驱，若从u开始的两次dfs中v的前驱有一个不为u，那么判定2成立。
O(n^2）。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read() 4 { 5 int x=0,f=1;char ch=getchar(); 6 while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} 7 while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); 8 return x*f; 9 } 10 const int N=1005; 11 const int M=200005; 12 vector<int> vec[N]; 13 int now,x[M],y[M],n,m,vis1[N][N],vis2[N][N]; 14 void dfs1(int x,int fa) 15 { 16 for (int i=0;i<vec[x].size();i++) 17 if (vec[x][i]!=fa) 18 if (!vis1[now][vec[x][i]]) vis1[now][vec[x][i]]=x,dfs1(vec[x][i],x); 19 } 20 void dfs2(int x,int fa) 21 { 22 for (int i=vec[x].size()-1;i>=0;i--) 23 if (vec[x][i]!=fa) 24 if (!vis2[now][vec[x][i]]) vis2[now][vec[x][i]]=x,dfs2(vec[x][i],x); 25 } 26 int main() 27 { 28 n=read();m=read(); 29 for (int i=1;i<=m;i++) x[i]=read(),y[i]=read(),vec[x[i]].push_back(y[i]); 30 for (int i=1;i<=n;i++) 31 { 32 now=i;vis1[now][now]=vis2[now][now]=1;//注意把起点的vis标记！ 33 dfs1(i,-1); 34 dfs2(i,-1); 35 } 36 for (int i=1;i<=m;i++) 37 puts(((vis1[y[i]][x[i]]!=0)^(vis1[x[i]][y[i]]!=x[i]||vis2[x[i]][y[i]]!=x[i]))?"diff":"same"); 38 return 0; 39 }