.gif)
Codeforces Round 1020 (Div. 3) CF 2106 A~G2 題解
人生第一次打過jiangly
A. Dr. TC
原串中每一個\(1\)最終的出現次數是\(n-1\)，而每個\(0\)最終的出現次數是\(1\)。因此直接統計即可。
時間復雜度\(O(n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n;
string s;
int main()
{
//fileio();
cin>>t;
while(t--)
{
cin>>n>>s;
int ans=0;
rep(i,n) if(s[i]=='1') ans+=n-1;else ++ans;
cout<<ans<<endl;
}
return 0;
}
B. St. Chroma
為了讓\(x\)盡早作為MEX出現，我們先把小于\(x\)的元素一股腦塞在序列最前面。塞完這些元素之后MEX就是\(x\)了，為了保持，我們接下來優先放\(>x\)的元素，把\(x\)放最后即可。注意特判\(x=n\)的情況。
時間復雜度\(O(n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n,x;
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n>>x;
if(n==x)
{
rep(i,n) cout<<i<<' ';
cout<<endl;
continue;
}
rep(i,x) cout<<i<<' ';
for(int i=x+1;i<n;++i) cout<<i<<' ';
cout<<x<<endl;
}
return 0;
}
C. Cherry Bomb
首先如果\(b\)中有\(\neq -1\)的元素，那\(ab\)中對應的兩個數之和\(x\)的值就已經確定了，對\([1,n]\)中每個位置檢查是否合法即可。如果\(b\)中只有-1，易發現\(x\)的取值范圍是\([max\{a_i\},k-min\{a_i\}]\)，直接計算即可。
時間復雜度\(O(n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n,k,a[200010],b[200010];
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n>>k;
rep(i,n) cin>>a[i];
rep(i,n) cin>>b[i];
int sum=-1,ok=1;
rep(i,n) if(b[i]>-1)
{
if(sum==-1) sum=a[i]+b[i];
else if(sum!=a[i]+b[i]) ok=0;
}
if(ok==0)
{
cout<<0<<endl;
continue;
}
if(sum>-1)
{
rep(i,n) if(b[i]==-1&&sum-a[i]>k||sum-a[i]<0) ok=0;
cout<<ok<<endl;
}
else
{
int mxa=-1,mna=1e9;
rep(i,n)
{
mxa=max(mxa,a[i]);
mna=min(mna,a[i]);
}
cout<<mna+k-mxa+1<<endl;
}
}
return 0;
}
D. Flower Boy
下面解析中數組下標從1開始。
如果序列\(a\)已經固定，我們想要檢查是否能摘到足夠的花，可以采用從開頭開始貪心匹配\(a,b\)序列的方法。即如果\(a_i\geq b_j\)，其中\(j-1\)是目前摘的花的數量，那就摘下這朵花并向前走一步；否則，直接向前走一步。方便起見，我們將一對序列\((a_0,b_0)\)使用這種貪心方法摘到的花的數量稱為匹配數。
首先對原序列\((a,b)\)做一次這種匹配，如果匹配數為\(m\)，則答案為0。否則，令\(pref_i(i\in[0,n])\)表示\(a\)的前\(i\)個元素與\(b\)的匹配數，\(suf_i(i\in[0,n])\)表示 \(a\)的后\(i\)個元素組成的反向后的序列 與 \(b\)反向后的序列 的匹配數。若插入一個beauty\(=k\)的花能解決問題的話，注意到必存在\(i\)滿足\(pref_i+suf_{n-i}=m-1\)，我們此時需要把新的花插入在第\(i\)盆花之后，且它的beauty\(\leq b_{pref_i+1}\)。若這樣的\(i\)不存在，則無解。
時間復雜度\(O(n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n,m,a[200010],b[200010],pref[200010],suf[200010];
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n>>m;
rep(i,n) cin>>a[i];
rep(i,m) cin>>b[i];
pref[0]=(a[0]>=b[0] ? 1:0);
repn(i,n-1)
{
if(pref[i-1]==m) pref[i]=m;
else if(a[i]>=b[pref[i-1]]) pref[i]=pref[i-1]+1;
else pref[i]=pref[i-1];
}
suf[n-1]=(a[n-1]>=b[m-1] ? 1:0);
for(int i=n-2;i>=0;--i)
{
if(suf[i+1]==m) suf[i]=m;
else if(a[i]>=b[m-suf[i+1]-1]) suf[i]=suf[i+1]+1;
else suf[i]=suf[i+1];
}
if(pref[n-1]==m)
{
cout<<0<<endl;
continue;
}
int ans=INT_MAX;
if(pref[n-1]==m-1) ans=b[m-1];
if(suf[0]==m-1) ans=min(ans,b[0]);
rep(i,n-1) if(pref[i]+suf[i+1]==m-1) ans=min(ans,b[pref[i]]);
if(ans==INT_MAX) cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
E. Wolf
下面解析中數組下標從1開始。
令\(pos_i\)表示值\(i\)在原序列中的位置。對于一次詢問，若\(pos_x\notin[l,r]\)，則顯然無解。否則，我們模擬一下在\([l,r]\)上二分的過程，發現其中存在\(O(log_2n)\)個"關鍵位置"，即每次二分中的\(m\)，這些位置上的值是決定二分是否成功的關鍵。具體來說，對于其中一些位置我們要求其上的值\(>x\)，方便起見我們稱之為B位；對于另一些位置我們要求其上的值\(<x\)，稱之為S位。
若\([1,n]\)中\(>x\)的數的數量小于B位的數量，則無論我們如何操作，都不可能達成目標，此時直接判無解。對于S位也是類似。
對于位置上的數原本就\(>x\)的B位以及位置上的數原本就\(<x\)的S位(稱它們為好位)，我們不去動他們是最好的，比較省操作。對于位置上的數\(<x\)的B位以及位置上的數\(>x\)的S位(稱它們為壞位)，令其數量依次為\(b,s\)。稱除了好位、壞位和\(pos_x\)的位置為普通位。注意到，我們需要從普通位中叫一些"外援"，把這些外援劃到我們選擇出來并shuffle的\(d\)個元素中。觀察發現至少需要叫\(|b-s|\)個外援才能滿足所有B/S位的"要求"，并且一定能選出來(選不出來的情況已經在前面被判無解了)。因此答案為\(2\cdot max(b,s)\)。
時間復雜度\(O(n+qlog_2n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n,q,p[200010],pos[200010];
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n>>q;
repn(i,n) cin>>p[i],pos[p[i]]=i;
while(q--)
{
int l,r,x;
cin>>l>>r>>x;
int targ=pos[x],big=n-x,sml=x-1,nbig=0,nsml=0,nsbig=0,nssml=0;
if(targ<l||targ>r)
{
cout<<-1<<' ';
continue;
}
while(l<r)
{
int mid=(l+r)/2;
if(mid==targ) break;
if(mid<targ)
{
++nsml;
if(p[mid]>x) ++nsbig;
l=mid+1;
}
else
{
++nbig;
if(p[mid]<x) ++nssml;
r=mid-1;
}
}
if(nbig>big||nsml>sml)
{
cout<<-1<<' ';
continue;
}
cout<<max(nsbig,nssml)*2<<' ';
}
cout<<endl;
}
return 0;
}
F. Goblin
想象一條向右移動的"掃描線"，每次刷新出這個矩陣的一列。注意到每一列中要么只有一個0，要么只有一個1。令掃描線上一個位置的答案表示在掃描線及其左側，包括這個位置的最大的全0連通塊的大小(若這個位置的值為1，則答案為0)。同時，對于掃描線上連續的一堆值為0的位置，它們的答案相同。因此任意時刻，可以把掃描線分成三個區間，其中中間區間的長度為1，滿足每個區間中各位置的答案相同。令這三個區間的答案為\(dp_{i,0/1/2}\)(隨便吧，怎么表示都行)。然后在掃描線相鄰的兩個位置之間就可以用非常無腦的方式進行\(dp\)轉移，這里不再贅述。最終答案對所有\(dp\)值取最大值即可。
時間復雜度\(O(n)\)。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
LL t,n;
string s;
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n>>s;
LL l,m,r,ans;
if(s[0]=='1') m=1,l=r=0,ans=1;
else l=m=0,r=n-1,ans=n-1;
repn(i,n-1)
{
LL u=i,d=n-i-1;
if(s[i-1]=='1'&&s[i]=='1') l=r=0,m=1;
else if(s[i-1]=='1'&&s[i]=='0') l=m+u,m=0,r=d;
else if(s[i-1]=='0'&&s[i]=='1') l=0,m=r+1,r=0;
else l+=u,m=0,r+=d;
ans=max(ans,max(l,m));
if(i<n-1) ans=max(ans,r);
}
cout<<ans<<endl;
}
return 0;
}
G2. Baudelaire (hard version)
n+200次操作？還是在樹上？這一眼就是個重心分治相關。
注意到如果我們已經知道了根的位置，我們只需要對每個結點做一次\(k=1\)的1類型詢問，就可以算出每個點的權值。因此考慮怎么使用200次左右的操作找到根的位置。
我們挑出樹上的任意一條邊來觀察一下。令其直接連接的點為\(a,b\)。將這條邊切斷，樹就分為了 與\(a\)連接的點 和 與\(b\)連接的點 兩個集合。方便起見，稱其為 \(a\)子樹中的點 和 \(b\)子樹中的點。如何判斷樹根在哪個子樹中呢？很簡單，我們先對\(a\)子樹中所有點做一次1詢問，接下來用2詢問改變\(b\)的權值，然后再對\(a\)子樹中所有點做一次1詢問，如果兩次1詢問結果的差值絕對值是 \(a\)子樹中結點個數\(\times 2\)，則根在\(b\)子樹中，否則在\(a\)子樹中。這是因為只有在詢問1中涉及的每個結點到根的路徑都經過權值被改變的結點時，詢問結果差值絕對值才會\(=\)詢問結點個數\(\times2\)。
那么能不能每次切斷一條邊直到根可能位于的結點只剩一個呢？不能，因為不存在一個叫邊分治的東西，隨便來一個菊花圖你復雜度就爆炸了。
考慮重心分治，每輪遞歸嘗試判斷根位于重心的哪個子樹內，或者是不是就是重心本身。分以下幾種情況：
- 連通塊只剩一個點。那根就是重心本身。
- 重心(在當前連通塊內)只有一個子樹。那說明連通塊內只有2個點，對重心本身做一次1詢問，若結果為1或-1則重心是根，否則另一個點是根。
- 重心有不止一個子樹。可能出現以下兩種情況：
- 重心不是根。考慮在一堆子樹中進行二分，每次用類似上面"判斷根在\(a\)的子樹還是\(b\)的子樹中"的方法來判斷根在 左邊的一堆子樹中 還是 右邊的一堆子樹中(即"先對左邊一堆子樹中所有點做一次1詢問，接下來用2詢問改變重心的權值，然后再對左邊一堆子樹中所有點做一次1詢問")，此時我們可以知道根是否在左邊一堆子樹中，因此可以縮小二分范圍。一輪遞歸使用的詢問數量大約為\(3\cdot log_2(重心的子樹數量)\)。
- 重心是根。在上面那種情況的第一次二分之前，我們先用相同的方法判斷一下，根有沒有一種可能，我是說可能，不在左邊的一堆子樹中，也不在右邊的一堆子樹中。這時候說明重心就是根。
這樣就優雅地找到了根。接下來用\(n\)次詢問問出每個結點的權值就行了。
總操作數大約\(n+O(log_2^2n)\)，反正肯定是在限制內的。
其實如果再出惡心一點的話，可以強制要求你"利用"上面找根過程中的詢問，來代替掉這\(n\)個詢問中的一部分。我瞎說的。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void termin()
{
std::cout<<"\n\nEXECUTION TERMINATED";
exit(0);
}
using namespace std;
int t,n,sz[1010],pref[1010],ans[1010],root;
vector <int> g[1010],subtroots,tmp;
vector <vector <int> > subts;
bool vis[1010];
int qry(vector <int> nds)
{
cout<<"? 1 "<<nds.size()<<' ';
rep(i,nds.size()) cout<<nds[i]<<' ';
cout<<endl;
cout.flush();
int ret;cin>>ret;return ret;
}
void qry2(int pos)
{
cout<<"? 2 "<<pos<<endl;
cout.flush();
}
void getSz(int pos,int par)
{
sz[pos]=1;
rep(i,g[pos].size()) if(!vis[g[pos][i]]&&g[pos][i]!=par)
{
getSz(g[pos][i],pos);
sz[pos]+=sz[g[pos][i]];
}
}
pii getMn(int pos,int par,int tot)//{max subtree size, node}
{
int mx=1e9,cursz=tot-sz[pos];
pii ret={mx,114514};
rep(i,g[pos].size()) if(!vis[g[pos][i]]&&g[pos][i]!=par)
{
ret=min(ret,getMn(g[pos][i],pos,tot));
cursz=max(cursz,sz[g[pos][i]]);
}
ret=min(ret,{cursz,pos});
return ret;
}
void getNodes(int pos,int par)
{
tmp.pb(pos);
rep(i,g[pos].size()) if(!vis[g[pos][i]]&&g[pos][i]!=par) getNodes(g[pos][i],pos);
}
bool isInOther(int lb,int ub,int par)
{
int tot=pref[ub+1]-pref[lb];
vector <int> nds;
for(int i=lb;i<=ub;++i) rep(j,subts[i].size()) nds.pb(subts[i][j]);
int res=qry(nds);
qry2(par);
int res2=qry(nds);
return abs(res-res2)==tot*2;
}
int findRoot(int pos)
{
getSz(pos,-1);pos=getMn(pos,-1,sz[pos]).se;
subts.clear();subtroots.clear();
rep(i,g[pos].size()) if(!vis[g[pos][i]])
{
tmp.clear();
getNodes(g[pos][i],pos);
subts.pb(tmp);
subtroots.pb(g[pos][i]);
}
rep(i,subts.size()) pref[i+1]=pref[i]+subts[i].size();
if(subts.size()==0) return pos;
if(subts.size()==1)
{
int res=qry({pos});
if(res==1||res==-1) return pos;
else return subts[0][0];
}
int lb=0,ub=subts.size()-1,mid;
while(lb<ub)
{
mid=(lb+ub)/2;
bool res=isInOther(0,mid,pos);
if(lb==0&&ub==subts.size()-1)
{
bool res2=isInOther(mid+1,ub,pos);
if(res&&res2) return pos;
}
if(res) lb=mid+1;
else ub=mid;
}
vis[pos]=true;
return findRoot(subtroots[lb]);
}
void getAns(int pos,int par,int parval)
{
int res=qry({pos});
ans[pos]=res-parval;
rep(i,g[pos].size()) if(g[pos][i]!=par) getAns(g[pos][i],pos,res);
}
int main()
{
//fileio();
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n;
rep(i,n+5) g[i].clear(),vis[i]=false;
int x,y;
rep(i,n-1)
{
cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
root=findRoot(1);
getAns(root,0,0);
cout<<"! ";
repn(i,n) cout<<ans[i]<<' ';
cout<<endl;
cout.flush();
}
return 0;
}
浙公網安備 33010602011771號