HDU多校5 - 6816 Boring Game(模拟)

题目链接：点击查看

题目大意：给出 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(模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。