战绩:
有铁头娃
A. Chip Game
猜了个结论,第一次猜的是n==m,第二次猜的是n+m的奇偶性。
严格证明也比较简单。
由于只能向右向上,我们每次移动相当于缩减问题规模。
那么n和m两个都为奇数或者偶数的情况下,能够移动到一奇一偶的情况,而一奇一偶的情况也能移动到两个都为奇数或者偶数的状态。
最后移动到(1,1)的为赢家因此先手一奇一偶就赢了。
B. Mathematical Circus
取模之后答案大于4的k,对于答案只有k%4的影响。
按照这个思路我们发现,只有四种情况。
并且,样例全列出来了。。。
输出出来即可
C. Fighting Tournament
如果一个人前面有比它大的数字,这个人一定没法赢。
如果一个人的数字是最大的,那么只要轮到它它就能一直赢。
对于其他的情况,他们能赢的局数是轮到他的那一局直到它和后面第一个比它大的接触为止,这个局数是它的上限。而如果局数在这期间用完了,那么当前统计的答案就是结果。
如此模拟就可以。
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<ctime> #include<stack> #define N 150000 #define ll long long using namespace std; ll n,T,m; ll a[N]; bool winn[N]; ll b[N],tp; stack<int> s; //��� inline void read(ll &p) { p=0;ll f=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') p=p*10+(ch-'0'),ch=getchar(); p*=f; } int main() { read(T); while(T--) { ll maxx=-1; read(n);read(m); while(!s.empty()) s.pop(); for(int i=1;i<=n;i++) //ǰ���Ƿ��б������ { read(a[i]); b[i]=0; winn[i]=1; if(a[i]>maxx) maxx=a[i],tp=i; else winn[i]=0; } while(!s.empty()) s.pop(); //�����һ��������� for(int i=n;i>=1;i--) { while(!s.empty()) { if(a[i]>a[s.top()]) s.pop(); else break; } if(!s.empty()) b[i]=s.top(); s.push(i); } while(m--) { ll l,k; read(l);read(k); if(!winn[l]) cout<<0<<endl; else { if(l==tp) printf("%lld\n",max(1ll*0,k-max(1ll*0,l-2))); else { if(k<(l-1)) cout<<0<<endl; else { ll ans=(b[l]-1-l); //��������Ӯ if(l==1) printf("%lld\n",min(ans,k)); else { ans++; k-=(l-1); if(k<0) cout<<0<<endl; //û�ֵ� else if(k==0) cout<<1<<endl; //�ոյ� else { if(k>=(b[l]-1-l)) cout<<ans<<endl; else cout<<k+1<<endl; } } } } } } } return 0; }View Code
但是实际上这样子细节比较多,导致我的答案一直在WA
我们可以率先把第一大的位置移动到最前面,记录需要的局数,和这期间每个人赢得次数,然后这之后的答案都只有最大的会变。判断预处理局数和已用局数的大小关系即可。
D1. Burenka and Traditions (easy version)
我们发现一些事实:
1.选取一次三个以上区间和我们选取两个+一个组成的等长区间所消耗的花费是一样的。
也就是说我们最多变换的时候选取长度为2的区间。
2.有一种方式,每一位都异或自己变为0,那么答案上限就是n。
3.如果我们每次都连续选择两位进行异或那么能够优化的方式就是异或两个数字中的第一个数,将其变为0,然后第二个数字就会变为a1^a2,当a1^a2不为0的时候,我们实际上和一个一个异或自己相比没有答案上的优化,因此我们做完连续两位的异或操作时,一定要恰好保证答案都变为0,此时相比一位一位做,答案会少1.
也就是说,如果有一段区间[l,r],使得al^al+1^al+2^...^ar==0,我们就能对这段区间进行优化。
我们n^2枚举寻找区间,统计答案即可。
void ac() { int n; cin >> n; vector<int> inp(n + 1); finc(i, 1, n + 1) cin >> inp[i]; int index = 1, ans = 0; finc(i, 1, n + 1) { int key = 0; fdec(j, index, i + 1) { key ^= inp[j]; if (key == 0) { ans += i - index, index = i + 1; break; } } } ans += n - index + 1; cout << ans << endl; }View Code
D2. Burenka and Traditions (hard version)
标签:ch,ll,异或,局数,补题,答案,Div,include,814 From: https://www.cnblogs.com/ztlsw/p/16599867.html