題目鏈接：點擊查看

題目大意：給出一個環狀的燈泡，標號為 1 ~ n ，初始時全部為熄滅狀態，現在兩個人開始玩游戲，第一個人可以選擇繼續游戲，也可以選擇結束游戲，繼續游戲的話首先選擇一個正整數 k ，然后點亮?k 個熄滅的燈泡，第二個人可以選擇連續的 k 個燈泡將其全部熄滅，如此往復，設 R( n ) 是 n 個燈泡的情況下，經過兩人的數輪操作后可以亮著的最大燈泡數，第一個人可以在第二個人操作完后，亮著的燈泡不小于 R( n ) 時結束游戲

題目分析：一道需要制定貪心策略的題目，首先需要求出 R( n ) 為多少，首先假設當前亮著的燈泡數為 x ，第一個人選擇的數字為 k ，這樣下一輪第一個人經過操作后，亮著的燈泡數變為了 x + k ，因為第二個人可以選擇 k 個連續的燈泡熄滅，如果本輪操作可以提供貢獻的話，必須保證這 x + k 中最長的連續的亮著的燈泡是小于等于 k - 1 個的，這樣第二個人熄滅連續的 k 個燈泡后，本輪的貢獻仍然是 x + 1 ，我們需要求出這個 x?

因為一共 x + k 個亮著的燈泡，極限情況就是每 k - 1 個亮著的燈泡分成一組，又因為最長的連續的燈泡個數必須小于等于 k - 1 ，所以每兩段之間需要有一個熄滅的燈泡隔開，畫個圖就是這樣的：

淺藍色表示的是環狀的燈泡分布，深藍色的是連續的 k - 1 個亮著的燈泡，紅色的是熄滅的燈泡

這樣顯然熄滅的燈泡個數為?，亮著的燈泡個數為 x + k ，總燈泡個數為 n ，所以列出不等式：

解得?，因為我們這個 x 的含義是，最后一次放之前亮著的燈的個數，所以在最后一次操作時，又放置了 k 個燈泡，對手拿走了 k - 1 個燈泡，此時達到 R( n ) 的局面，換句話說，其實??才對

這樣我們可以枚舉 k 維護出最大的 R( n ) ，找到 k 后貪心就好了，就像上面那個圖一樣，為了方便處理，我們設起點從 0 開始，不能放置的位置都為 i % k == 0 ，其余位置貪心填滿就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;set<int>s;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);int mmax=0,k=1;for(int i=1;i<=n;i++){int temp=n-(n+i-1)/i-i+1;if(temp>mmax){mmax=temp;k=i;}}for(int i=0;i<n;i++)if(i%k)s.insert(i);while(s.size()>=k){printf("%d ",k);for(int i=0;i<k;i++){printf(" %d",*s.begin()+1);s.erase(s.begin());}puts("");fflush(stdout);int pos;scanf("%d",&pos);pos--;for(int i=0;i<k;i++)if((pos+i)%n%k)s.insert((pos+i)%n);}puts("0");fflush(stdout);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1368F Lamps on a Circle(交互+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。