感觉难度比去年大，也可能是我变菜了
第一场
1001迷失
1003 鸽子
1004 萌新
void solve(){ ll a=read,b=read; if(b>a) swap(a,b); ll tmp=a-b; ll res_max=a-b,res_min=0; if(!tmp) res_max=a,res_min=2; rep(i,2,tmp/i){ if(tmp%i==0){ res_min=i;break; } } if(!res_min) res_min=tmp; if(res_min<=1||res_max<=1){ printf("-1 -1\n"); return ; } printf("%lld %lld\n",res_min,res_max); } int main(){ int _=read; while(_--) solve(); return 0; }
1006 毒瘤数据结构题
思路：
首先对于查询操作，是满足单调性的，我们可以二分答案，那么怎么c h e c k呢，如果对于当前的m i d，[ 1 , m i d − 1 ]的和为m i d − 1，说明该点符合题意，还可以更大，l ll指针右移。
对于修改操作，相当于单点修改。
大体思路就是对答案进行二分，借用某数据结构维护单点修改和区间求和。
容易想到的是线段树跟树状数组，赛时是用树状数组写的，复杂度O ( n l o g 2 n )
交了后宇巨说第二个查询的答案一定是单调递增的，所以应该有O ( n )的写法。
然后h d u o j评测机的问题导致O ( n )的写法都会T L E,知道思想就好了。
代码：
const int maxn=5e6+7,maxm=210000; ll n,a[maxn],tr[maxn]; ll lowbit(ll x){ return x&-x; } void update(ll pos,ll val){ while(pos<=n){ tr[pos]+=val; pos+=lowbit(pos); } } ll query(ll pos){ ll res=0; while(pos){ res+=tr[pos]; pos-=lowbit(pos); } return res; } bool check(int x){ int t=query(x-1); if(t!=x-1) return 0; return 1; } int main(){ n=read; rep(i,1,n){ int op=read,x=read; if(op==1&&a[x]!=1) a[x]=1,update(x,1); else if(op==2){ //rep(j,1,n){ // cout<<a[j]<<" "; //} //puts(""); if(a[x]!=1) update(x,1); int l=1,r=n,res; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ res=mid;l=mid+1; } else r=mid-1; } //cout<<i<<"******"; printf("%d\n",res); if(a[x]!=1) update(x,-1); } } return 0; }
1008 猎人杀
思路：
模拟；要注意的点为：
1.狼人可以杀死自己，猎人不可以杀死自己
2.注意每次杀人的时候都是选择最靠前并且未死亡的，所以每次要从1开始遍历
代码：
int a[55],now[55],st[55]; int w[55][55]; int main(){ int _=read; while(_--){ int n=read,pos; rep(i,1,n){ a[i]=read; if(a[i]) pos=i; now[i]=1;st[i]=0; } rep(i,1,n){ rep(j,1,n){ w[i][j]=read; } } int cnt=n; int id=pos,flag=0; while(1){ now[id]=1; while(now[id]<=n&&st[w[id][now[id]]]) now[id]++; st[w[id][now[id]]]=1;// die int t=w[id][now[id]]; //cout<<now[id]<<"*****"<<t<<endl; if(t==pos){ flag=1;break; } else{ id=t;cnt--; } if(cnt<=2){ flag=0;break; } } if(flag) puts("lieren"); else puts("langren"); } return 0; }
第二场
1001 签到
- 思路
找规律，写出前7 77项就好了
| 项数 | a | b |
| 0 | a | b |
| 1 | a+b | a-b |
| 2 | 2a | 2b |
| 3 | 2a+2b | 2a-2b |
| 4 | 4a | 4b |
| 5 | 4a+4b | 4a-4b |
| 6 | 8a | 8b |
| 7 | 8a+8b | 8a-8b |
分奇偶讨论一下就好了，注意取模。
- 代码：
const ll mod=998244353 ; int main(){ int _=read; while(_--){ ll a=read,b=read,k=read; if(k%2==0){ int t=k/2; ll tmp=ksm(2,t,mod); printf("%lld %lld\n",tmp*a%mod,tmp*b%mod); } else{ int t=(k-1)/2; ll tmp=ksm(2,t,mod); ll x=(a-b+mod)%mod; printf("%lld %lld\n",tmp*(a+b)%mod,tmp*x%mod); } } return 0; }
1002 随机题意
思路：
对于每个b [ i ]的范围为[ a i − k , a i + k ]
排序后从头开始扫，贪心的选择。
每次都尽量选择每个区间最左边的。
代码：
int n,a[maxn],k; struct node{ int l,r; }b[maxn]; bool cmp(node a,node b){ if(a.l==b.l) return a.r<b.r; return a.l<b.l; } int main(){ int _=read; while(_--){ n=read,k=read; rep(i,1,n){ a[i]=read; b[i].l=a[i]-k,b[i].r=a[i]+k; } sort(b+1,b+1+n,cmp); int res=1,now=b[1].l+1; rep(i,2,n){ if(now<=b[i].r){ now=max(now+1,b[i].l+1); res++; } } printf("%d\n",res); } return 0; }
1003 魔怔
1004 净化
思路：
首先，尽量找到分界点，在分界点之后，所有的负数都不会使得遍历完的答案减少，也就是说，分界点之后的每次的变化都是固定的，设为c n t。
其次，如果这时候已经满足x > = m，就输出答案；不满足的话，就计算出每次增加c n t，直至x > = m的次数。
但是这样会出现一个问题，有可能在某次遍历的过程中，x > = m已经满足了，但是后面有负数，就导致了这次遍历完成后，x > = m又不满足了，这样就使得答案增大。
解决方案是提前记录前缀和的最大值，在计算每次增加c n t增加多少次能够满足x > = m的时候，提前将最大值减去。
代码：
const int maxn=1e5+7,maxm=210000; ll n,m,a[maxn]; int main(){ int _=read; while(_--){ n=read,m=read; ll sum=0,maxx=-inf; rep(i,1,n) a[i]=read,sum+=a[i],maxx=max(maxx,sum); ll x=0,res=0,lasx=0,cnt=0,lascnt=-1; while(1){ rep(i,1,n){ x=max(0ll,x+a[i]); if(x>=m) break; } res++; if(x>=m) break; cnt=x-lasx; if(lascnt==cnt) break; lascnt=cnt,lasx=x; } if(x>=m) printf("%lld\n",res); else{ if(cnt==0){ puts("-1");continue; } if(maxx==cnt){ ll t=m-x; res+=t/cnt; if(t%cnt) res++; printf("%lld\n",res); } else{ ll t=m-x-maxx; //cout<<t<<" "<<cnt<<" "<<res<<endl; res+=t/cnt+1; //cout<<t/cnt<<endl; if(t%cnt) res++; printf("%lld\n",res); } } } return 0; }
