題目鏈接：點擊查看

題目大意：給出 n 張疊在一起的紙，現在將其連續從左向右折疊 k 次，再從上到下標上序號，問展開后的序號是怎么樣的

題目分析：比賽時一直在找規律，確實是有規律，但是我找不到。。去請教了一下zx學長，zx學長和我說vector暴力模擬即可

這里放一張比賽時畫的一張紙折疊四階的圖，提供給想找規律的朋友用吧，有點丑：

如果模擬的話，借用題解給出的示意圖：

稍微提一下模擬的實現，上圖中紅色序號表示的是層的編號，初始時為 1 ~ limit ，limit = 2 * n * 2^k，藍色的橫線表示的是每次截斷的位置，我們需要進行 k 次展開（ 因為折疊了k次嘛 ），對于每次展開，我們挑選當前最中間的位置作為 mid ，將上半段翻轉一下貼到下半段的左邊，上圖中就演示了連續展開兩次后的情況，直接用 vector 暴力維護整個過程就好了，最后剩下的 2 * n 層就是我們需要的答案了，按照順序輸出即可，注意這個題卡了 PE ，末尾不要有多余的空格

時間復雜度的話，題解說的是 O( n * k * 2^n ) ，我不太會算，反正是 O( 能過 ) 就好了

代碼：
?

#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> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;vector<int>node[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,k;scanf("%d%d",&n,&k);int limit=2*n*(1<<k);for(int i=1;i<=limit;i++)node[i].clear();for(int i=1;i<=limit;i++){int num;scanf("%d",&num);node[i].push_back(num);}int mid=1;while(k--){mid=mid+limit>>1;for(int j=mid+1;j<=limit;j++){int pos=mid-(j-(mid+1));reverse(node[pos].begin(),node[pos].end());node[j].insert(node[j].begin(),node[pos].begin(),node[pos].end());node[pos].clear();}}bool first=true;for(int i=limit-2*n+1;i<=limit;i++)for(int j=0;j<node[i].size();j++){if(first)first=false;elseputchar(' ');printf("%d",node[i][j]);}puts("");}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU多校5 - 6816 Boring Game(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

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