B. BSUIR Open X

從$n$個字符串中任選兩個進行拼接，求拼接成"BSUIROPENX"的方法數。

思路：
首先統計各字符串的出現次數，
再對"BSUIROPENX"進行拆分，
拆分所得兩字符串出現此時之積即為答案

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> P; const int mod=1e9+7; unordered_map<string,ll>mp; string t="BSUIROPENX"; int main(){int n;cin>>n;for(int i=0;i<n;i++){string s;cin>>s;mp[s]++;}ll ans=0;for(int i=0;i<t.size();i++){string a=t.substr(0,i);string b=t.substr(i);ans+=mp[a]*mp[b];}cout<<ans<<endl;return 0; }

L. Long integer

給定一個十進制數$x_0$和$q$次查詢，每次查詢可以實現以下兩種操作：
1、在原數字的最右邊加上一個數字$d$
2、刪除現有數字最右邊那一位上的數字
每次輸出$x$變化之后，對1e9+7取余的結果。

思路：
一邊計算，一遍取模
（也可不用字符串，用棧來維護頂部增減數字，時間會省很多很多）

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> P; typedef pair<P,int> PP; const int mod=1e9+7; ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; } int main(){string s;cin>>s;int q;cin>>q;ll ans=0;ll div=ksm(10,mod-2);//逆元for(int i=0;i<s.size();i++){ans=(ans*10+s[i]-'0')%mod;}while(q--){char ch;cin>>ch;if(ch=='+'){char t;cin>>t;s+=t;ans=(ans*10+t-'0')%mod;}else{int l=s.size();int k=s[l-1]-'0';ans=(ans-k+mod)%mod;ans=ans*div%mod;s=s.substr(0,l-1);} cout<<ans<<endl;}return 0; }

C. Crossed out letter

給出兩個字符串$s_0$和$s_1$，其中，$s_0$是由字符串$s$刪除某個特定的字符$x$得到的，$s_1$也是是由字符串$s$刪除相同位置的字符$x$或者刪除其他不同位置上的字符$x$得到的。試求能通過相應操作得到上述字符串的$s$，如果這樣的$s$不存在，則輸出“IMPOSSIBLE”。

思路：
這道題關鍵是讀題。。。題目意思沒有完全審清導致被卡了很久很久，無用功也做了不少。

some single character某一個字符
而不是一些字符，如果some是“一些”的意思，“character”應該是復數啊！！！
沒想到敗在了這么簡單的單詞上邊。。。

如果讀懂了，只能刪除一個字符的話，那就相當于給你這樣兩個字符串：
(刪除不同位置的X)

X…
…X
直接遍歷兩個字符串，當出現不同字符時，說明該位置存在字符的刪除

需要正序、倒序各遍歷一次，找到兩個存在字符刪除的位置，然后將被刪除的字符（出現不同的字符）重新插入。
如果是刪除相同位置的X，那么一定會得到兩個完全相同的字符串，這種情況在$s_0$的基礎上再隨便加一個字符輸出就好啦！

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int main(){string a,b;cin>>a>>b;if(a==b){a+="b";cout<<a<<endl;return 0;}int len=a.size();int l=0,r=len-1;while(l<len&&a[l]==b[l]) l++;while(r>=0&&a[r]==b[r]) r--;if(a.substr(l+1,r-l)==b.substr(l,r-l)){string ans=a.substr(0,l)+a[l]+b.substr(l,r-l)+b[r]+b.substr(r+1);cout<<ans<<endl;}else if(a.substr(l,r-l)==b.substr(l+1,r-l)){string ans=a.substr(0,l)+b[l]+a.substr(l,r-l)+a[r]+a.substr(r+1);cout<<ans<<endl; } else{cout<<"IMPOSSIBLE\n";}return 0; }

I. Items in boxes

現有$2^n$個不同的盒子，每個盒子里面放有$a$個不同的物品，試求從沒個盒子里恰好都取出一個物品的方案數$x$
輸出$x\%2^{n+2}$的值

思路：
枚舉一些情況，推出公式
打表找規律

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> P; typedef pair<P,int> PP; const int mod=1e9+7; /* ll ksm(ll a,ll b,ll mod){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; } */ int main(){/*打表for(int n=1;n<=10;n++){for(int a=0;n<=10;n++){cout<<ksm(a,1<<n,1<<(n+2))<<" ";}cout<<endl;}*/ll n,m;cin>>n>>m;if(n==1){ll a=m%4;if(a==0) cout<<"0\n";else if(a==1||a==3) cout<<"1\n";else if(a==2) cout<<"4\n";}else{if(m&1) cout<<"1\n";else cout<<"0\n";}return 0; }

K. K-ones xor

給n,m,k,和一個長度為n的數組$a$，在$[0，2^m)$范圍內尋找一個$x$,且$x$的二進制表示中1的個數不能超過$k$個。
對數組進行如下修改：
$a_i=max(a_i,a_i\oplus x)$
求能夠讓數組和達到最大的$x$，如果這樣的$x$不止一個，則輸出最小的那個。
數據范圍：
$1\le n\le 10^5$
$1\le m\le 30$
$0\le k\le m$
$0\le a_i\le 2^m$

思路：
$x$的二進制表示中1的個數不能超過$k$個
且k的值不會超過30，可以考慮二進制枚舉，
$x$最多$m$位，每一次枚舉，考慮將$x$的哪一位變為1，數組和可以變大；
相當于每一次枚舉，$x$的二進制多一個1（如果不能找到使數組和變大的，也有可能不變），最多k個1。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const int mod=1e9+7; int n,m,k; ll a[maxn]; ll cal(ll x){ll ans=0;for(int i=0;i<n;i++){ans+=max(a[i],a[i]^x);}return ans; } int main(){ cin>>n>>m>>k;for(int i=0;i<n;i++){cin>>a[i];}ll ans=0;ll mmax=cal(ans);//注意不能初始化為0while(k--){int idx=-1;for(int i=0;i<m;i++){if(ans&(1<<i)) continue;//二進制的第i位是否有1ll sum=cal(ans+(1<<i));if(sum>mmax){//能使數組和變大，則標記該位mmax=sum;idx=i;}}if(idx!=-1){ans+=(1<<idx);}else break;}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的2019-2020 10th BSUIR Open Programming Championship. Semifinal 补题的全部內容，希望文章能夠幫你解決所遇到的問題。

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