codeforces 794E Choosing Carrot

目录

codeforces 794E Choosing Carrot题意题解Ｃｏｄｅ

codeforces 794E Choosing Carrot

题目传送门

题意

给出一个长度为\(n\)的序列，\(A\)和\(B\)开始玩游戏，每次可以从序列的两端删除一个数，直到删除到最后一个数，\(A\)想要使最后一个数尽量的大，而\(B\)想要使最后一个数尽量的小，\(A\)先手，问最后剩下的数是多少。然后问如果\(A\)先进行\(k (k=1...n-1)\)次操作，那么结果是多少。

题解

感觉这个E题有点水首先我们考虑不进行先手操作，那么答案是多少。我们根据题目可以发现这题一定是和\(n\)的奇偶有关系的，因为这关系到\(A\)是否会多取一次。然后由于这是个博弈，所以我们需要考虑什么状态下某个人是优的或者必胜的。然后我们仔细思考可以知道在\(n\)为偶数的情况下，最后剩下的一个数一定是\(a[n/2]\)和\(a[n/2+1]\)这之中较大的一个。因为由于\(B\)需要阻挠\(A\)删去那些小的数最后得到大的数，并且\(B\)是后手，所以它每次取一定都会取上次\(A\)取的那端的另一端，然后最后就会只剩下两个数，那么\(A\)就只能选择较大的那个了。 同样，当\(n\)为奇数的时候，\(A\)先手取了一个，那么就会转换成\(n\)为偶数并且\(B\)先手的情况了。由于最开始的那一步\(A\)有两种取法，那么最后剩下的两个数会是\(a[(n+1)/2-1]、a[(n+1)/2]\)和\(a[(n+1)/2]、a[(n+1)/2+1]\)。由于这样最后一步会是\(B\)进行选择，所以\(B\)一定会选择较小的那个，那么最后的两种情况一定是\(min(a[(n+1)/2-1],a[(n+1)/2])\)和\(min(a[(n+1)/2],a[(n+1)/2+1])\)。然而\(A\)先手，就一定会选择这两个之中较优的情况，所以最后答案一定是\(max(min(a[(n+1)/2-1],a[(n+1)/2]),min(a[(n+1)/2],a[(n+1)/2+1]))\)。 写了这么多终于写完初始情况了23333。接下来我们考虑进行先手操作之后，答案会进行怎样的变化。由于我们考虑初始情况的时候是分奇偶讨论的，而进行先手操作完之后的状况实际上是与初始状况一样的，所以我们在这里仍然是要分奇偶讨论。观察一下之前的结论，我们先把未经过先手操作的答案列出来：\[ half=\begin{cases} (n+1)/2 & n\&1=1 \\ n/2 & n\&1=0 \end{cases}\]

\[ res=\begin{cases} max(min(a[half-1],a[half]),min(a[half],a[half+1])) & n\&1=1 \\ max(a[half],a[half+1]) & n\&1=0 \end{cases}\] 我们可以发现，答案总是与这个中心点\(half\)有关，而进行先手操作的意义就是在于使得这个\(half\)值能够改变。我们记\(half\)的活动区间\([l,r]\)表示\([l,r]\)区间的每个数都是可以成为答案的\(half\)的。而先手操作的次数每增加２，就会使这个\(half\)的\([l,r]\)向左向右拓宽１个长度。这样我们只需要枚举先手操作的次数\(k\)，然后就将新拓宽区间的答案与\(k-2\)的答案取\(max\)，就是当前的答案。当然，这也是要分奇偶的。我们记\(ans1\)、\(ans2\)分别表示进行\(k\)次先手操作之后，\(n-k\)分别为奇数和偶数的答案。为了方便计算，我们记\(res[i][0]=max(min(a[i-1],a[i]),min(a[i],a[i+1]))\)，\(res[i][2]=max(a[i],a[i+1])\)，\(res[i][2]=max(a[i-1],a[i])\)。 记\(L1,R1,L2,R2\)分别为\(n-k\)为奇数和偶数时的活动区间。 然后我们就可以进行转移了，若\(n-k\)为奇数，那么这样更新：\(ans1=max(ans1,max(res[L1--][0],res[R1++][0]))\) 若\(n-k\)为偶数，则这样转移：\(ans2=max(ans2,max(res[L2--][2],res[R2++][3]))\) 最后注意特判一下\(k=n-1\)和\(k=n-2\)的情况，这两种情况\(A\)都可以直接取完\(n-1\)个数，所以直接输出\(a[]\)中最大的那个就行了。

如果还不懂的话可以看题解

Ｃｏｄｅ

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ #define PAUSE printf("Press Enter key to continue..."); fgetc(stdin); const int N=3e5+500; int n; int a[N],res[N][3]; int ans1,ans2,L1,R1,L2,R2,Mx; /*==================Define Area================*/ int main() { read(n); for(int i=1;i<=n;i++) { read(a[i]);Mx=max(Mx,a[i]); } for(int i=1;i<=n;i++) { if(i==1) res[i][0]=res[i][2]=a[i],res[i][5]=max(a[i],a[i+1]); else if(i==n) res[i][0]=res[i][6]=a[i],res[i][2]=max(a[i],a[i-1]); else res[i][0]=max(min(a[i],a[i-1]),min(a[i],a[i+1])),res[i][7]=max(a[i],a[i+1]),res[i][2]=max(a[i],a[i-1]); } if(n<=2) { for(int i=1;i<=n;i++) printf("%d\n",Mx); return 0; } if(n==3) { printf("%d %d %d\n",res[2][0],Mx,Mx); return 0; } if(n&1) { ans1=res[(n+1)/2][0]; ans2=max(res[(n+1)/2][8],res[(n+1)/2][2]); L1=L2=(n+1)/2-1;R1=R2=(n+1)/2+1; printf("%d %d ",ans1,ans2); } else { ans2=res[n/2][9]; ans1=max(res[n/2][0],res[n/2+1][0]); L2=n/2;R2=n/2+1;L1=n/2-1;R1=n/2+2; printf("%d %d ",ans2,ans1); } // printf("%d %d %d %d\n",L1,R1,L2,R2); for(int i=2;i<n-2;i++) { if((n-i)&1) { ans1=max(ans1,max(res[L1--][0],res[R1++][0])); printf("%d ",ans1); } else { ans2=max(ans2,max(res[L2--][2],res[R2++][10])); printf("%d ",ans2); } } printf("%d %d\n",Mx,Mx); return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/9556696.html