技術文章 » [題解] Codeforces Global Round 22 1738 A B C D E F 題解

[題解] Codeforces Global Round 22 1738 A B C D E F 題解

2022-10-01 15:19:06

很久沒rated打過cf的比賽了，這次打得還行，至少進前100了

求點贊

點我看題

A. Glory Addicts

把型別0的數放進陣列a裡，型別1的數放進陣列b裡。如果\(|a|=|b|\)，你可以把所有數裡最小的放在第一個，其他的交錯排列，這樣除了最小的其他都能取到2的係數。這個需要特判。否則假設\(|a|>|b|\)，則可以把a中最小的放第一個，然後分別把b和a中最大的\(|b|\)個拿出來交替排列，這樣能使b和a中最大的\(|b|\)個都取到2的係數。容易發現沒有更好的排法了。

時間複雜度\(O(nlogn)\)。

點選檢視程式碼 
#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 mpr make_pair
#define pb push_back

using namespace std;

LL t,n,tt[100010],vv[100010];
vector <LL> a,b;

int main()
{
  cin>>t;
  rep(tn,t)
  {
    scanf("%lld",&n);
    a.clear();b.clear();
    rep(i,n) scanf("%lld",&tt[i]);
    rep(i,n) scanf("%lld",&vv[i]);
    LL ans=0;
    LL mn=1e18;
    rep(i,n)
    {
      if(tt[i]==0) a.pb(vv[i]);else b.pb(vv[i]);
      ans+=vv[i];
      mn=min(mn,vv[i]);
    }
    sort(a.begin(),a.end());reverse(a.begin(),a.end());
    sort(b.begin(),b.end());reverse(b.begin(),b.end());
    if(a.size()==b.size())
    {
      printf("%lld\n",ans*2-mn);
      continue;
    }
    LL sz=min(a.size(),b.size()),v1=0,v2=0;
    rep(i,sz) v1+=a[i];rep(i,sz) v1+=b[i];
    ans+=v1;
    printf("%lld\n",ans);
  }
	return 0;
}

B. Prefix Sum Addicts

應該是比較容易錯的題吧，我最後幾分鐘想著來不及做G了就去叉這題，結果叉了兩個都失敗了，喜提-100pts

首先k=1的時候一定是YES。否則a陣列最後的k-1項已經確定了，先看已經確定的有沒有違反不降。令a的第\(n-k+2\)項為x(已經確定了)。則它前面的數最大隻能都是x。所以就看\(x \cdot (n-k+1)\)是否\(\geq s_{n-k+1}\)就行了。最後就是注意要開long long。

時間複雜度\(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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

using namespace std;

LL t,n,k,s[100010];

int main()
{
  cin>>t;
  rep(tn,t)
  {
    scanf("%lld%lld",&n,&k);
    for(int i=n-k+1;i<=n;++i) scanf("%lld",&s[i]);
    LL lst=1e12,ok=1;
    for(int i=n-1;i>=n-k+1;--i)
    {
      LL cur=s[i+1]-s[i];
      if(cur>lst)
      {
        ok=0;
        break;
      }
      lst=cur;
    }
    LL can=(n-k+1)*lst;
    if(can<s[n-k+1]) ok=0;
    puts(ok==1 ? "YES":"NO");
  }
	return 0;
}

C. Even Number Addicts

一開始以為是要觀察什麼神奇的性質，結果一看資料範圍哦豁\(n\leq 100\)，那不是直接暴力算就行嘛

Alice想要儘量取到偶數個奇數，Bob想要儘量讓Alice取到奇數個奇數。\(dp_{player,val,o,e}\)表示當前玩家是player(值為0/1 表示Alice/Bob)，當前Alice取到的奇數個數奇偶性為val，還剩o個奇數沒取，e個偶數沒取，此時的先手能不能勝利。轉移也是很簡單的，列舉接下來取奇數還是偶數就行。如果能轉移到的狀態有任意一個是必敗，那當前狀態就是必勝；否則當前狀態為必敗。邊界情況就是\(o=e=0\)，根據player和val的值確定勝敗即可。可以在所有詢問之前先\(O(100^2)\)把dp的表打出來。

時間複雜度\(O(100^2)\)。

點選檢視程式碼 
#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 mpr make_pair
#define pb push_back

using namespace std;

int t,n,a[110],dp[2][2][110][110];

int dfs(int p,int v,int o,int e)
{
  int &ret=dp[p][v][o][e];
  if(ret!=-1) return ret;
  if(o==0&&e==0)
  {
    if(p==0) return ret=(v==0 ? 1:0);
    return ret=(v==1 ? 1:0);
  }
  ret=0;
  if(p==0)
  {
    if(o>0) ret|=(dfs(1,v^1,o-1,e)==0);
    if(e>0) ret|=(dfs(1,v,o,e-1)==0);
  }
  else
  {
    if(o>0) ret|=(dfs(0,v,o-1,e)==0);
    if(e>0) ret|=(dfs(0,v,o,e-1)==0);
  }
  return ret;
}

int main()
{
  rep(i,2) rep(ii,2) rep(j,105) rep(k,105) dp[i][ii][j][k]=-1;
  rep(i,2) rep(ii,2) rep(j,103) rep(k,103) if(dp[i][ii][j][k]==-1) dfs(i,ii,j,k);
  cin>>t;
  rep(tn,t)
  {
    cin>>n;
    int o=0,e=0;
    rep(i,n)
    {
      scanf("%d",&a[i]);
      if(abs(a[i])%2!=0) ++o;
      else ++e;
    }
    puts(dp[0][0][o][e]==1 ? "Alice":"Bob");
  }
	return 0;
}

D. Permutation Addicts

把數值分成2類，\(\leq k\)的和\(>k\)的。觀察題目中的定義可知，\(b_i\)的含義是：在a序列中，從值為i的元素往前找，第一個與i不同類的元素的值。最終的a序列是會被劃分成若干塊的，每一塊內的元素型別都相同，且相鄰兩個塊內的元素型別不同。發現\(b_i=0或n+1\)，當且僅當i在第一塊內。所以我們可以快速地找出第一塊內的所有元素(通過檢查\(b_i\))。但是每一塊內的所有元素順序也不能亂排，其實每一塊內有且僅有1個元素x，滿足存在若干y使得\(b_y=x\)(最後一塊除外)，這也是容易看出的(回顧\(b_i\)的含義)。這個x必須排在當前塊的最後一個，而塊內其他元素可以按任意順序排。同時發現，所有滿足\(b_y=x\)的y就是下一塊的所有元素。到這裡這題就做完了，按照上面說的模擬即可。

時間複雜度\(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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

using namespace std;

int t,n,b[100010],k,ans[100010];
vector <int> v[100010];

int main()
{
  cin>>t;
  rep(tn,t)
  {
    scanf("%d",&n);
    rep(i,n+3) v[i].clear();
    repn(i,n)
    {
      scanf("%d",&b[i]);
      v[b[i]].pb(i);
    }
    int curnode,startpos=1,stat;
    if(v[0].size()>0) curnode=0,stat=1;
    else curnode=n+1,stat=0;
    k=0;
    while(startpos<=n)
    {
      int nxt=-1;vector <int> tmp;
      rep(i,v[curnode].size())
      {
        int u=v[curnode][i];
        if(v[u].size()>0) nxt=u;
        else tmp.pb(u);
      }
      rep(i,tmp.size()) ans[startpos+i]=tmp[i];
      ans[startpos+tmp.size()]=nxt;
      if(stat==0) k+=v[curnode].size();
      startpos+=v[curnode].size();
      curnode=nxt;
      stat^=1;
    }
    printf("%d\n",k);
    repn(i,n) printf("%d ",ans[i]);
    puts("");
  }
	return 0;
}

E. Balance Addicts

似乎有很多群友寫的很煩還被卡，我的做法還是比較好寫的。

原陣列下標從1開始。題目中的劃分序列，其實等價於：

  • 選出2個序列x、y(下標從1開始)，長度都為k(\(k>0\))，滿足x嚴格遞增，y嚴格遞減，x和y中的所有元素都在[1,n]中
  • 並且滿足\(x_k<y_k\)
  • 那麼我們就可以把\([1,x_1]和[y_1,n]\)各縮成一個數並匹配；\([x_1+1,x_2]和[y_2,y_1-1]\)各縮成一個數並匹配\(\cdots\)\([x_{k-1}+1,x_k]和[y_k,y_{k-1}-1]\)各縮成一個數並匹配。這裡還要要求每兩個匹配區間內的數之和相等。
  • \(x_k和y_k\)之間如果還有空隙，把中間的數縮成一個，作為迴文序列的最中間一個數。

發現每一對合法的(x,y)都對應了一種劃分序列的方案。還要加上整個序列合併成一個數的1種方案。

可以令\(dp_{i,j}\)表示當前已經選擇了x和y的一段長度都為p的字首，其中\(x_p=i,y_p=j\)的方案數。如果p=0則用\(dp_{0,n+1}\)表示。發現每個\(dp_{i,j}\)可以從某些滿足條件的\(dp_{i',j'}(i'<i,j'>j)\)轉移。但是有這些還是沒法寫這題的

處理出原序列的字首和和字尾和。發現對於每一對合法的(x,y)和任意i，都滿足\(x_i\)位置的字首和=\(y_i\)位置的字尾和。因此可以按照值從小到大，列舉每一段極長連續且相等的字首和，令其範圍為[l,r]，字首和值為val。顯然，\(a_l \neq 0\)，區間內其他位置都滿足\(a_i=0\)。如果沒有任何一個位置滿足其字尾和為val，則跳過這個區間。否則，令值為val的極長字尾和區間為[l',r']。如果[l,r]和[l',r']不相交，我們可以在這兩個區間內分別選擇相同數量的位置，並分別接在之前提到的x序列和y序列的最後。可以記錄一個變數pre，表示滿足x序列的最後一個數<l，且y的最後一個數>r'的(x,y)的數量。令在[l,r]和[l',r']內選擇>0個數的方案數為wys，每次令\(pre+=pre \cdot wys\)即可。如果[l,r]和[l',r']相交，那麼肯定滿足l'=l+1,r'=r+1，我們在[l,r']中選擇偶數個位置即可。並且我們就不能再接著列舉字首和的值了，因為我們對(x,y)的要求是x的最後一個數 < y的最後一個數。此時需要break。

時間複雜度\(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 <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if((a&1)==1) ret=ret*res%MOD;
		a>>=1;
		res=res*res%MOD;
	}
	return ret;
}

LL t,n,a[100010],pref[100010],suf[100010],fac[100010],inv[100010];
vector <pair <LL,pii> > v;
map <LL,pii> mp;

LL C(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}

int main()
{
  fac[0]=1;repn(i,100005) fac[i]=fac[i-1]*i%MOD;
  rep(i,100003) inv[i]=qpow(fac[i],MOD-2);
  cin>>t;
  rep(tn,t)
  {
    scanf("%lld",&n);
    repn(i,n)
    {
      scanf("%lld",&a[i]);
      pref[i]=pref[i-1]+a[i];
    }
    suf[n+1]=0;
    for(int i=n;i>0;--i) suf[i]=suf[i+1]+a[i];
    v.clear();
    repn(i,n)
    {
      int p=i;
      while(p+1<=n&&pref[p+1]==pref[i]) ++p;
      v.pb(mpr(pref[i],mpr(i,p)));
      i=p;
    }
    mp.clear();
    for(int i=n;i>0;--i)
    {
      int p=i;
      while(p-1>0&&suf[p-1]==suf[i]) --p;
      mp[suf[i]]=mpr(p,i);
      i=p;
    }
    LL pre=1;
    rep(i,v.size()) if(mp.find(v[i].fi)!=mp.end())
    {
      LL l1=v[i].se.fi,r1=v[i].se.se,l2=mp[v[i].fi].fi,r2=mp[v[i].fi].se;
      if(r1<l2)
      {
        LL tot=0;
        repn(cho,min(r1-l1+1,r2-l2+1)) (tot+=C(r1-l1+1,cho)*C(r2-l2+1,cho))%=MOD;
        (pre+=tot*pre)%=MOD;
      }
      else
      {
        LL tot=0;
        repn(cho,(r2-l1+1)/2) (tot+=C(r2-l1+1,cho+cho))%=MOD;
        (pre+=tot*pre)%=MOD;
        break;
      }
    }
    printf("%lld\n",pre);
  }
	return 0;
}

F. Connectivity Addicts

稍微有點詐騙。

我們染色的要求是，同種顏色必須連通，每種顏色都滿足度數之和\(\leq\)點數的平方。這啟發我們可以拿出度數最大的點(注意度數序列是題目初始時輸入的)，直接詢問出所有與他相連的點，並把這些所有點都染成同一種顏色。此時被染成這種顏色的點集大小已經超過了其中點的度數的最大值，所以就算我們不斷向點集中加入到原來點集中的點有邊的其他點(不管加多少都行)，點集仍然滿足度數之和\(\leq\)點數的平方(稱其為萬能點集，每個萬能點集中的點顏色都相同)。把度數最大的點和他所連線的點都染色後，我們再拿出沒被染色的點中度數最大的，令其為點x。仍然是詢問出所有與x連線的點，如果所有這些點都沒被染色，那麼恭喜，你又找到一個"萬能點集"，可以把其中的點再都染成同一種顏色，以後也可以再向其中加點。如果詢問過程中發現有一個連到的點y已經被染色，那麼幹脆把x，以及在詢問y之前詢問到的所有點(都是沒染色的)，都加到y所屬的萬能點集中(可以用並查集)，與y染成同一種顏色。容易發現這是符合題目中的染色規則的。重複找出度數最大的未染色點並詢問的這種操作，直到沒有未染色點。我們每詢問一次，都有至少1個點被染色。所以總詢問次數不會超過n。

時間複雜度\(O(nlogn)\)。

點選檢視程式碼 
#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 mpr make_pair
#define pb push_back

using namespace std;

int t,n,d[1010],fa[1010],c[10010];
bool con[1010];
set <pii> st;

int qry(int u)
{
  cout<<"? "<<u<<endl;
  cout.flush();
  int x;cin>>x;return x;
}

int Find(int x)
{
  if(fa[x]!=x) fa[x]=Find(fa[x]);
  return fa[x];
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  cin>>t;
  rep(tn,t)
  {
    cin>>n;
    repn(i,n) cin>>d[i];
    repn(i,n) fa[i]=i,con[i]=0;
    st.clear();
    repn(i,n) st.insert(mpr(-d[i],i));
    LL cnt=0;
    while(cnt<n)
    {
      pii bg=*st.begin();st.erase(st.begin());
      bg.fi=-bg.fi;
      con[bg.se]=true;
      ++cnt;
      rep(i,bg.fi)
      {
        int v=qry(bg.se);
        if(con[v])
        {
          fa[Find(bg.se)]=Find(v);
          break;
        }
        con[v]=true;fa[Find(v)]=Find(bg.se);
        st.erase(mpr(-d[v],v));
        ++cnt;
      }
    }
    cout<<"! ";
    int len=0;
    repn(i,n) if(Find(i)==i) c[i]=++len;
    repn(i,n) if(Find(i)!=i) c[i]=c[Find(i)];
    repn(i,n) cout<<c[i]<<' ';cout<<endl;
    cout.flush();
  }
	return 0;
}

有一說一，H不僅有原題而且據說還是板子。。。有群友半小時不到就切了/fad
LOJ原題連結
原題是這題的強化版？