2021牛客練習賽90

• B.寒冬信使
• C.盾與戰錘

B.寒冬信使

題目鏈接：https://ac.nowcoder.com/acm/contest/11180/B


code:

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() {int t;cin>>t;for(int i=1;i<=t;i++){string s;cin>>s;ll sum=0;for(int i=0;i<s.length();i++){if(s[i]=='1')sum+=i+1;}if(sum%2==1)cout<<"T"<<"\n";else cout<<"X"<<"\n";}return 0; }

這道題是個博弈題，一道很有趣的題目。題目的大意是：兩個人輪流選一個白色格子并翻轉它，以及翻轉這個白色格子的前一個格子（翻轉指得是變成相反的顏色，即白變黑，黑變白），無法操作者敗，如果先手的人一定能勝則輸出"T",否則輸出"X"。這題的解法我很快就想出來了，但一直猶豫要不要交上去，因為感覺這樣寫太簡單了，而且當時只有80個人寫出來了，所以我猶豫了10分鐘，等到我試了很多特殊例子后都是正確的我才交了，然后過了。都是題外話，現在說正解。我的想法是如果總共操作了奇數次，那么先手必贏。所以我統計了字符串中每個1的位置，并將它們加起來，如果是奇數，則輸出"T"，否則輸出"X"。那么為什么可以這樣寫呢？我舉個例子吧，首先如果操作時不存在兩個1靠在一起的情況，比如0101，從左往右依次把1變成0，那么總共操作了偶數次，2+4=6，那么先手必敗（這個應該不用我解釋吧，模擬試試就知道了），如果操作時存在兩個1靠在一起的的情況，還是拿之前的0101舉例子，0101->0110->0000，在這個過程中我們可以發現，兩個1靠在一起的情況所貢獻的操作次數還是奇數，畢竟i+(i+1)=2*i+1為奇數，加上之前的一次操作總共就是偶數次，于是我們就可以有理由的得出一個結論：位置相加的奇偶數情況決定輸出情況。

C.盾與戰錘

題目鏈接：https://ac.nowcoder.com/acm/contest/11180/C


code:

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e6+10; ll a[N],b[N]; bool compare(ll x,ll y) {return x>y; } int main() {ll n,s;cin>>n>>s;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);ll ans=0; sort(a+1,a+1+n,compare);for(int i=1;i<=2*n;i++){b[i]=b[i-1]+a[i];}for(ll k=1;k<=n;k++){ans=0;for(ll t=0;;t++){ans=max(ans,b[t*k]-t*s);if(t*k>=n) break;}printf("%lld\n",ans);} return 0; }

這道題我一直無法理解這里的子序列的定義。題目中也不給個解釋，于是用了錯誤的理解一直找不出來解決方法。我的理解是相對位置不變，也就是說在原序列5，2，4，1中可以選5，2，4，但不能5，4，2，而答案卻是可以的。。。這道題的解法是：對于每個k,枚舉破盾數t，范圍是0~n/k，但其實破盾數最大可為n/k+1，這就要在枚舉中做些小優化了，具體見代碼：

for(ll t=0;;t++){ans=max(ans,b[t*k]-t*s);if(t*k>=n) break;}

然后把前最大的t?k個數相加減去t?s，就是當前破盾數所對應的傷害，然后更新最大的傷害即可，我們可以用前綴和預處理前t?k大的數。這里要注意的是數組的長度和前綴和循環的范圍須定義為2倍的n的最大值，即2e6+10，因為如果是1e6+10的話，數組會越界的。那么為什么會越界呢？假設k=n-1，那么按照我們上述寫法，當t=2時，2*k就是2?(n-1)了，所以必須定義為2e6的級別，那么，這就有人回問了，我們別這樣判斷了，直接這樣寫不就行了嗎：

for(ll t=0;t*k<=n;t++){ans=max(ans,b[t*k]-t*s);}

你一交就會發現只過了30%的例子，這是為什么呢？其實就是我在上面所說，t是可以為n/k+1的！也就是說我們必須得循環到第一個大于或等于n/k的數才能退出循環。那么為什么可以為n/k+1呢？舉個例子你就清楚了，n=10,k=4的時候：

五角星為破盾時所在的位置，1~10這些數為從大到小排序后的數所在的位置，從這張圖我們可以看出有三個破盾點，而不是10/4=2了，最后一個破盾后所選取的范圍已經超過了n了，也能解釋為什么數組大小為n會越界了。
還有一點要說明的是這種做法的時間復雜度是O(nlogn)，證明見下圖：

總結

以上是生活随笔為你收集整理的2021牛客练习赛90的全部內容，希望文章能夠幫你解決所遇到的問題。

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