2021 ICPC Southeastern Europe Regional Contest

A題簽到

A. King of String Comparison

題意：給兩個字符串，找出有多少對（l，r），滿足在l到r區間內，s1的子串字典序小于s2的子串字典序。

思路：一眼題，首字母滿足字典序小后面拼上的都小，格外注意前方有好多字母字典序一致的情況。
比如:
aaaabcd
aaaacde

維護一個l和一個r，l到r為可以選擇的左端點，r到n為可以選擇右端點，雙指針掃描即可。
特別要注意不要讓你選擇區間重復。

#include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long const int N = 2e5+100;char s[N],t[N]; signed main() {int n;cin>>n;cin>>(s+1)>>(t+1);int ans=0ll;for(int l=1,r=1;r<=n&&l<=n;r++){if(s[r]<t[r]){ans+=(r-l+1)*(n-r+1);l=r+1;}if(s[r]>t[r]){l=r+1;}}cout<<ans;return 0; }

F. to Pay Respects

題意：勇者斗惡龍

進行n回合，每回合按如下順序進行
1.惡龍可以吟唱治療魔法
2.勇者可以吟唱傷害魔法
3.勇者物理攻擊
4.所有魔法生效.

對于魔法：
1.雙方吟唱一次魔法，使得對應的效果層數加一
2.勇者吟唱魔法后，如惡龍有治療魔法效果，則還會讓治療魔法效果層數減一

最終每輪造成的傷害為: 物理傷害+傷害魔法層數 * 傷害魔法數值-治療魔法層數 * 治療魔法數值

我們還會給出一個01串
如果此串第i項為1代表惡龍第i回合吟唱治療魔法

問最大造成多少傷害

思路：唯一的一個點就是要知道，傷害魔法低效的治療魔法的治療效果可以視為傷害魔法造成的傷害。

所以第i回合魔法造成的傷害就是（n-i+1）*（p+r *（s[i]==‘1’））

#include <iostream> #include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 1e6+100;char s[N]; int ans[N]; bool cmp(const int &a,const int &b) {return a>b; } signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n,x,r,p,k;cin>>n>>x>>r>>p>>k;cin>>(s+1);int res=x*n;for(int i=1;i<=n;i++){if(s[i]=='1'){ans[i]=(n-i+1)*(p+r);res-=(n-i+1)*r;}else{ans[i]=(n-i+1)*p;}}sort(ans+1,ans+n+1,cmp);for(int i=1;i<=k;i++){res+=ans[i];}cout<<res<<endl;return 0; }

G. Max Pair Matching

題意：給定2n個二元組，從里面調出n對二元組，每對的貢獻是
求n對二元組的貢獻總值最大是多少

思路：我們不妨先把max(…)里面的絕對值拆了，也就是二元組內部變得有序，滿足a<b即可

然后如何使得n對的貢獻最大呢？

我們知道如果讓i去減j的二元組，那么如果想要保證取得較大的價值(相對于j減去i來講)
就要滿足bi-aj>bj-ai移項后就是bi+ai>bj+aj
所以排序后讓前n個的b減去后n個的a即可。

#include <iostream> #include <algorithm> using namespace std; #define int long long #define endl '\n' const int N = 2e5+100;struct node {int a,b; }; bool cmp(const node &a,const node &b) {return a.a+a.b<b.a+b.b; } node a[N]; signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n;cin>>n;n<<=1;for(int i=1;i<=n;i++){cin>>a[i].a>>a[i].b;if(a[i].a>a[i].b)swap(a[i].a,a[i].b);}sort(a+1,a+n+1,cmp);int res=0;n>>=1;for(int i=1;i<=n;i++){res+=a[i+n].b-a[i].a;}cout<<res<<endl;return 0; }

J. ABC Legacy

括號排序好題
題意：給定一個僅包含’A’,‘B’,'C’的長度為2n的字符串，并且有如下配對規則‘AB’，‘BC’，‘AC’。
問整個字符串能否劃分為n對。

思路:我們將A視為左括號，C視為右括號。B視為特殊括號。

統計A的個數，如果個數小于n，那么說明前n-cnta個B要變成特殊的左括號（對于括號匹配，我們有貪心結論：左括號越是靠左越容易匹配成功）

然后分別用兩個棧來維護括號匹配即可。在匹配的過程中，如果還有需要變成左括號的B就進入到sb棧，碰到a進入sa站。如果已經不需要b變成做括號了，那么碰到B就用sa中的a去匹配，碰到c先用sb中的b去匹配，再用sa中的a去匹配，

#include <bits/stdc++.h> #define endl '\n' using namespace std; const int N = 2e5+100;char s[N]; pair<int,int> ans[N]; signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n;cin>>n;n<<=1;cin>>(s+1);int cnt=0;for(int i=1;i<=n;i++){if(s[i]=='A')cnt++;}cnt=n/2-cnt;if(cnt<0){cout<<"NO"<<endl;return 0;}stack<int> sa,sb,sc;int con=0;for(int i=1;i<=n;i++){if(s[i]=='A'){sa.push(i);}if(s[i]=='B'){if(cnt){cnt--;sb.push(i);}else{if(sa.empty()){cout<<"NO"<<endl;return 0;}ans[++con]={sa.top(),i};sa.pop();}}if(s[i]=='C'){if(sa.empty()&&sb.empty()){cout<<"NO"<<endl;return 0;}else if(!sb.empty()){ans[++con]={sb.top(),i};sb.pop();}else{ans[++con]={sa.top(),i};sa.pop();}}}cout<<"YES"<<endl;for(int i=1;i<=con;i++){cout<<ans[i].first<<" "<<ans[i].second<<'\n';}return 0; }

N. A-series

題意：有n種紙片，每種紙片的大小是下一種的兩倍長，所以我們可以通過一次折疊將一張紙變成兩張下一種紙。
現在給出現有的n中紙片個數和需要的n種紙片個數。
問：需要至少操作幾次才能滿足需求。（如果不能滿足求則輸出-1）

思路：沒啥好講的吧，非要說就是利用了減法的思維，這題其實可以改編成二進制減法。

#include <iostream>using namespace std; #define int long long const int N = 2e5+100; int a[N]; int b[N]; signed main() {int n;cin>>n;n++;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}int cnt=0;for(int i=n;i>=1;i--){if(b[i]>a[i]){if(i==1){cout<<-1<<endl;return 0;}else{cnt+=(b[i]-a[i])/2+(b[i]-a[i])%2;b[i-1]+=(b[i]-a[i])/2+(b[i]-a[i])%2;}}}cout<<cnt<<endl;return 0; }

L. Jason ABC（前綴和+雙指針)
題意：給定一個只由有ABC三種字母構成的字符串，你每次可以選擇一段區間讓這段區間的所有字母都變成某一個字母，問最少幾次操作能夠使得字符串中ABC三種字母的數目都是n

輸出：一個正整數n
第二行：一個長度為3*n的字符串。

輸出：第一行一個整數x代表需要的次數
接下來x行每行兩個數字l r代表本次操作修改的區間，然后一個字母代表要變成什么字母。

思路：首先對于一個字符串到底需要幾次才能變成符合要求的呢。
如果只修改一次那么必定就有這樣一段區間滿足如下條件
1.修改的這段區間字母變為 ‘X’（X為任意字母）
2.修改這段區間之后，區間之外的另外兩個字母的出現次數一定是n（我們沒有必要判斷修改的這段區間是否是n長度，因為只要另外兩個是n就能保證第三者是n）

如果修改兩次，我們找到第一個位置pos，這個位置滿足如下條件
1.從1到pos的區間內，某一個字母出現了n次

只要滿足這個條件，我們就能把從pos到n的區域劃分成兩塊來滿足另外兩個字母出現n次的條件。

分析之后發現并不需要再多的操作步驟了。
具體實現：利用前綴和+雙指針維護區間即可。

#include <bits/stdc++.h>using namespace std; const int N = 3e6+100; char s[N]; int cnt[3][N]; int n; bool change(int c) {int ans=c;for(int l=1,r=1;l<=n&&r<=n;){if(l>r)r=l;while((cnt[(ans+1)%3][r]-cnt[(ans+1)%3][l-1]<cnt[(ans+1)%3][n]-n/3||cnt[(ans+2)%3][r]-cnt[(ans+2)%3][l-1]<cnt[(ans+2)%3][n]-n/3)&&r<=n)//必須滿足這個區間包含的另外兩個字母數量不能低于多出來的數值r++;if(cnt[(ans+1)%3][r]-cnt[(ans+1)%3][l-1]==cnt[(ans+1)%3][n]-n/3&&cnt[(ans+2)%3][r]-cnt[(ans+2)%3][l-1]==cnt[(ans+2)%3][n]-n/3){cout<<1<<endl;cout<<l<<" "<<r<<" "<<(char)('A'+ans);return 1;}elsel++;}return 0; } int main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n;n*=3;for(int i=1;i<=n;i++){cin>>s[i];cnt[0][i]=cnt[0][i-1]+(s[i]=='A');cnt[1][i]=cnt[1][i-1]+(s[i]=='B');cnt[2][i]=cnt[2][i-1]+(s[i]=='C');}if(cnt[0][n]==cnt[1][n]&&cnt[1][n]==cnt[2][n]){cout<<0<<endl;return 0;}else if(change(0)||change(1)||change(2)){return 0;}else{for(int i=1;i<=n;i++){for(int j=0;j<=2;j++){if(cnt[j][i]==n/3){cout<<2<<endl;cout<<i+1<<" "<<i+n/3-cnt[(j+1)%3][i]<<" "<<(char)('A'+(j+1)%3)<<endl;cout<<i+n/3-cnt[(j+1)%3][i]+1<<" "<<n<<" "<<(char)('A'+(j+2)%3)<<endl;return 0;}}}}return 0; }

K. Amazing Tree（DFS+樹）
待補
C. Werewolves（樹形背包）
待補

總結

以上是生活随笔為你收集整理的2021 ICPC Southeastern Europe Regional Contest（更新至六题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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