感覺難度比去年大，也可能是我變菜了

第一場

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 毒瘤數據結構題

• 思路：
  首先對于查詢操作，是滿足單調性的，我們可以二分答案，那么怎么$check$呢，如果對于當前的$mid$，$[1,mid?1]$的和為$mid?1$，說明該點符合題意，還可以更大，$l$指針右移。
  對于修改操作，相當于單點修改。
  大體思路就是對答案進行二分，借用某數據結構維護單點修改和區間求和。
  容易想到的是線段樹跟樹狀數組，賽時是用樹狀數組寫的，復雜度$O(nlo{g}^{2}n)$
  交了后宇巨說第二個查詢的答案一定是單調遞增的，所以應該有$O(n)$的寫法。
  
  然后$hduoj$評測機的問題導致$O(n)$的寫法都會$TLE$,知道思想就好了。
• 代碼：

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;// dieint 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$項就好了

項數ab

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 凈化

• 思路：
  首先，盡量找到分界點，在分界點之后，所有的負數都不會使得遍歷完的答案減少，也就是說，分界點之后的每次的變化都是固定的，設為$cnt$。
  其次，如果這時候已經滿足$x>=m$，就輸出答案；不滿足的話，就計算出每次增加$cnt$，直至$x>=m$的次數。
  但是這樣會出現一個問題，有可能在某次遍歷的過程中，$x>=m$已經滿足了，但是后面有負數，就導致了這次遍歷完成后，$x>=m$又不滿足了，這樣就使得答案增大。
  解決方案是提前記錄前綴和的最大值，在計算每次增加$cnt$增加多少次能夠滿足$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; }

總結

以上是生活随笔為你收集整理的2021 年百度之星·程序设计大赛 - 初赛一、二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。