2020-2021:teams:wangzai_milk:codeforces_global_round_8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:wangzai_milk:codeforces_global_round_8 [2020/06/30 16:23] zars19 创建 |
2020-2021:teams:wangzai_milk:codeforces_global_round_8 [2020/06/30 23:56] (当前版本) zars19 |
||
|---|---|---|---|
| 行 173: | 行 173: | ||
| puts(""); | puts(""); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
| + | |||
| + | ====== F. Lamps on a Circle ====== | ||
| + | |||
| + | 交互。$n$个灯围成一圈，初始全灭，每回合你可以打开若干盏灯（也可以选择结束游戏），而对方可以使得连续的、相同数量的一段中的灯全部灭掉。要使得结束游戏时打开的灯的数量是双方采用最优策略情况下的最多。 | ||
| + | |||
| + | 题解：梦幻贪心。想象一下，最后一个回合中你会打开$k$盏灯，之后对方关掉连续长度为$k$的一段，而这个过程开灯数是增加了的。所以，打开$k$盏灯后的形态应该是“不存在长度为$k$的连续一段灯全部打开”，所以至多连续$k-1$盏灯打开。 | ||
| + | |||
| + | 灯最多的情形将会是以$k-1$亮$1$灭为循环（但第$n$盏必灭）。比如$n=17$的情况下（$k=3$）$\mathsf{11011011011011010}$，在对方关完后变为$\mathsf{00011011011011010}$（一种可能）即最优解。故可以先枚举$k$算出$R(n)=\max_k \left(n - k -\left\lceil\frac{n}{k}\right\rceil + 1\right)$。 | ||
| + | |||
| + | 交互过程中每次点亮补全至“被以$1$灭隔开的若干$k-1$亮段”（$\mathsf{11011011011011010}$）的相同局面即可，直至到达到最优$R(n)$。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | #define pii pair<int,int> | ||
| + | #define mp make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define ll long long | ||
| + | int n,r,k,a[1005],t,x; | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%d",&n); | ||
| + | for(int i=1;i<=n;i++) | ||
| + | if(n-n/i-(n%i!=0)-i+1>r)r=n-n/i-(n%i!=0)-i+1,k=i; | ||
| + | while(t<r) | ||
| + | { | ||
| + | printf("%d ",r+k-1-t); | ||
| + | for(int i=1;i<n;i++) | ||
| + | if(i%k&&!a[i])a[i]=1,printf("%d ",i); | ||
| + | puts(""),fflush(stdout); | ||
| + | scanf("%d",&x); | ||
| + | int g=0; | ||
| + | for(int i=0,j=x;i<r+k-1-t;i++,j=(j+1>n)?1:j+1) | ||
| + | g+=a[j],a[j]=0; | ||
| + | t=r+k-1-g; | ||
| + | } | ||
| + | puts("0"); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| \\ | \\ | ||
2020-2021/teams/wangzai_milk/codeforces_global_round_8.1593505399.txt.gz · 最后更改: 2020/06/30 16:23 由 zars19
