山东鲁中公路建设有限公司网站,帮做3d模型的网站,wordpress app模板下载,中卫网站网站建设这道模拟题出的我毫无脾气2333 最重要的是先要发现操作顺序不影响最后的答案#xff0c;也就是每次随便挑一个2的数进行操作最后总是可以得到同样的数列。 (这个还不太难想qwq) 但是最骚的是接下来的模拟。。。。 我们考虑从左到右消#xff0c;假设目前在i#xff0c;1… 这道模拟题出的我毫无脾气2333 最重要的是先要发现操作顺序不影响最后的答案也就是每次随便挑一个2的数进行操作最后总是可以得到同样的数列。 (这个还不太难想qwq) 但是最骚的是接下来的模拟。。。。 我们考虑从左到右消假设目前在i1~i-1的已经都消成了0或1。 可以发现无非就是一下几种情况 1.a[i]2不用管它 2.i1那么就 a[i1]a[i]/2, a[i] 1. 3.左边都是1这样的话推一推会发现可以将一轮视为 a[1] 0a[i]-- a[i1] 4.左边是1推一推会发现这样相当于让 最近的一个0右移一位然后a[i]--, a[i1] 5.左边是0直接算a[i-1],a[i]-2,a[i1]会减少一个0位置 如果我们用一个栈记录一下从左到右0的位置那么就可以很方面的做上面的操作了。 接下来是非常炫酷的复杂度分析 1操作的复杂度是O(N) 2操作的复杂度是 O(1) 3操作的最多次数不到初始所有a[]的和(因为每操作一次总和就--) 4操作可以优化成一次位移最大(也就是要么把a[i]减成2的要么把0移到i-1)如果移到i-1然后再结合5操作的话它的次数 5操作的次数否则因为a[i]1了扫描线会右移。所以这一部分的总次数 2*n 3操作的次数。 5操作每次会让栈的大小-1所以最多次数 3操作的次数 n。 于是这个算法的复杂度是O(N) 的(并且算复杂度很多地方都是取的极限的情况所以实际跑起来飞快)非常的优秀 雾 #includeiostream
#includecstdio
#includecstring
#define ll long long
using namespace std;
const int N20000005;int a[N],n,s[N],tp;
char S[N];int main(){freopen(simulate.in,r,stdin);freopen(simulate.out,w,stdout);scanf(%s,S1),nstrlen(S1);for(int i1;in;i) a[i]S[i]-0;if(a[1]2) a[2]a[1]1,a[1]1;if(!a[1]) s[tp]1;for(int i2,L;in;i){while(a[i]2)if(!tp) a[i1],a[i]--,s[tp]1,a[1]0;else if(s[tp]i-1) a[i]-2,a[s[tp]]1,tp--,a[i1];else{Li-s[tp]-1;if(a[i]L) a[i1]a[i]-1,a[s[tp]]1,s[tp]a[i]-1,a[s[tp]]0,a[i]1;else a[i1]L,a[s[tp]]1,s[tp]L,a[s[tp]]0,a[i]-L;}if(!a[i]) s[tp]i;}for(int i1;in;i) putchar(a[i]0);return 0;
}转载于:https://www.cnblogs.com/JYYHH/p/9244562.html
