cf round433
A
题目要求
每个医生有开始上班的时间s和时间间隔d 即他在s s+d s+2d···天上班
现给出n个医生 必须按顺序(1-n)访问每个医生 问访问到最后一个医生时是多少天
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| using namespace std; int n; int s[maxn],d[maxn]; int main(){ // freopen("input.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&s[i],&d[i]); int cur=0; for(int i=1;i<=n;i++){ if(s[i]>cur) cur=s[i]; else{ int j=(cur-s[i])/d[i]; cur=s[i]+d[i]*(j+1); } } printf("%d\n",cur); return 0; }
|
思路
暴力模拟
题目关键是按顺序访问 cur记录天数 直接模拟每一个医生即可
B
题目要求
n个人比赛 每个人有一个能力值 能力值大的获胜
每次站在对头的人和后一个人比 赢的人继续在对头和下一个人比 输的人去队尾
现问第一个获得k场胜利的人的能力值是多少
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| using namespace std; struct node{ int power; LL num; node(int power,LL num):power(power),num(num){} }; int a[maxn]; int n; LL k; deque<node>q; int main(){ // freopen("input.txt","r",stdin); scanf("%d%lld",&n,&k); int Max=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); Max=max(Max,a[i]); q.push_back(node(a[i],0)); } if(k>=1000){ printf("%d\n",Max); return 0; } int ans=0; while(1){ node x=q.front(); q.pop_front(); if(x.num==k){ ans=x.power; break; } node y=q.front(); q.pop_front(); if(x.power>y.power){ q.push_front(node(x.power,x.num+1)); q.push_back(node(y.power,y.num)); } else if(x.power<y.power){ q.push_front(node(y.power,y.num+1)); q.push_back(node(x.power,x.num)); } } printf("%d\n",ans); return 0; }
|
思路
双端队列直接模拟
注意n最多只有500 所以经过500场之后能力值最大的人会一直站在对头 所以k大于500直接输出最大能力值即可
C
题目要求
有n次操作 形式是| & ^加上一个数字
现在要求简化结果 最多k行 形式和上面相同 要求最后得到的结果相同
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| using namespace std; int n,op; char s[10]; int main(){ // freopen("input.txt","r",stdin); scanf("%d",&n); int x=0,y=0x3ff; for(int i=1;i<=n;i++){ scanf("%s %d",s,&op); if(s[0]=='|'){ x|=op; y|=op; } else if(s[0]=='&'){ x&=op; y&=op; } else if(s[0]=='^'){ x^=op; y^=op; } } int or_num=0,and_num=0,xor_num=0; for(int i=0;i<10;i++){ int bit=1<<i; if(bit&x){ if(bit&y) or_num|=bit,and_num|=bit; else xor_num|=bit,and_num|=bit; } else{ if(bit&y) and_num|=bit; } } printf("3\n& %d\n| %d\n^ %d\n",and_num,or_num,xor_num); return 0; }
|
思路
最后结果肯定可以简化成三行 或一个数字 与一个数字 异或一个数字 分别记录每种操作对应的二进制数即可
最多只有四种情况
1.0->0,1->0，则f[i]=“&0,|0,^0”，即a[i]=0,b[i]=0,c[i]=0
2.0->0,1->1，则f[i]=“&1,|0,^0”，即a[i]=1,b[i]=0,c[i]=0
3.0->1,1->0，则f[i]=“&1,|0,^1”，即a[i]=1,b[i]=0,c[i]=1
4.0->1,1->1，则f[i]=“&1,|1,^0”，即a[i]=1,b[i]=1,c[i]=0
x和y分别记录三种操作对应的0是否变1 1是否变0
然后判断是四种情况里的哪一种
