目錄

• Codeforces 1009
  • A.Game Shopping
  • B.Minimum Ternary String
  • C.Annoying Present
  • D.Relatively Prime Graph
  • E.Intercity Travelling(遞推)
    • \(Description\)
    • \(Solution\)
  • F.Dominant Indices(啟發(fā)式合并)
  • G.Allowed Letters(Hall定理 位運(yùn)算)
    • \(Description\)
    • \(Solution\)

---

Codeforces 1009

比賽鏈接

hack好給力啊233

A.Game Shopping

#include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() const int N=1e3+5;int n,m,cost[N],A[N];inline int read() {register int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; }int main() {n=read(), m=read();for(int i=1; i<=n; ++i) cost[i]=read();for(int i=1; i<=m; ++i) A[i]=read();int now=1,ans=0;for(int i=1; i<=n && now<=m; ++i)if(cost[i]<=A[now]) ++ans, ++now;printf("%d\n",ans);return 0; }

B.Minimum Ternary String

#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #define gc() getchar() const int N=1e5+7;int n; char s[N],ans[N];int main() {scanf("%s",s+1), n=strlen(s+1);int cnt[5],now;cnt[0]=cnt[1]=cnt[2]=0;for(now=1; now<=n; ++now)if(s[now]!='2') ++cnt[s[now]-'0'];else break;for(int i=1; i<=cnt[0]; ++i) ans[i]='0';for(int i=cnt[0]+1; i<=cnt[0]+cnt[1]; ++i) ans[i]='1';cnt[0]=cnt[1]=cnt[2]=0;for(int i=now; i<=n; ++i) ++cnt[s[i]-'0'];for(int i=now; i<now+cnt[1]; ++i) ans[i]='1';s[n+1]='3';for(int i=now+cnt[1]; i<=n; ++i){while(s[now]=='1') ++now;ans[i]=s[now++];}puts(ans+1);return 0; }/* 102012012 */

C.Annoying Present

#include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() #define eps 1e-8 typedef long long LL; const int N=1e5+7;inline int read() {register int now=0,f=1;register char c=gc();for(;!isdigit(c);c=='-'&&(f=-1),c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f; }int main() {int n=read(), m=read();LL sum=0, sumX=0, C1, C2=1ll*n*(n-1)>>1;//n/2寫成n>>1略顯亂 if(n&1) C1=1ll*(n>>1)*((n>>1)+1);else C1=1ll*(n>>1)*((n>>1)+1)-1ll*(n>>1);LL x,d;for(int i=1; i<=m; ++i){x=read(), d=read(), sumX+=x;if(d>0) sum+=C2*d;else if(d<0) sum+=C1*d;}printf("%.8lf",1.0*(sum+1ll*n*sumX)/n);return 0; }

D.Relatively Prime Graph

靠 欺負(fù)我讀英文題目不仔細(xì)嗎 圖必須連通。。
于是WA*3。看了數(shù)據(jù)才A。。
這破題 rank1000+了啊啊啊

而且這題n^2純暴力都能過 太沒意思了吧

#include <cmath> #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() #define pr std::pair<int,int> #define mp std::make_pair const int N=1e5+7;int n,m,cnt,P[N],fac[N],sum; pr A[3000005]; bool not_P[N];int gcd(int x,int y){return y?gcd(y,x%y):x; } void Pre(int n) {for(int i=2; i<=n; ++i){if(!not_P[i]) P[++cnt]=i;for(int j=1; j<=cnt&&i*P[j]<=n; ++j){not_P[i*P[j]]=1;if(!(i%P[j])) break;}}for(int i=2; i<=n; ++i)if(!not_P[i]) fac[i]=i;else{for(int j=2; j<=i; ++j)if(!(i%j)) {fac[i]=j; break;}} }int main() {scanf("%d%d",&n,&m);// printf("%d\n",m);if(m<n-1) return puts("Impossible"),0;//...Pre(n);for(int i=2; i<=n && sum<m; ++i) A[++sum]=mp(1,i);for(int x=1; x<=cnt && sum<m; ++x){int i=P[x];for(int j=i+1; j<=n && sum<m; ){int k=std::min(j+fac[i]-1,n+1);//n+1!for(int l=j; l<k && sum<m; ++l) A[++sum]=mp(i,l);j=k+1;}}for(int i=4; i<=n && sum<m; ++i){if(!not_P[i]) continue;for(int j=i+1; j<=n && sum<m; ){int k=std::min(j+fac[i]-1,n+1);for(int l=j; l<k && sum<m; ++l)if(gcd(i,l)==1) A[++sum]=mp(i,l);j=k+1;}}if(sum<m) puts("Impossible");else{puts("Possible");for(int i=1; i<=m; ++i)printf("%d %d\n",A[i].first,A[i].second);}return 0; }

---

比賽結(jié)束后

E.Intercity Travelling(遞推)

\(Description\)

　　Leha從0出發(fā)前往n。給定數(shù)組\(a[]\)。路上可能會有一些休息點(diǎn)，Leha會在這些地方停下休息。如果當(dāng)前所在休息點(diǎn)\(i\)，而上一個休息點(diǎn)是\(j\)，那他會得到\(a_{i-j}\)的困難值（包括在n點(diǎn)停下也要計算，路程上所有累加）。休息點(diǎn)一共有\(2^{n-1}\)種可能分布，求所有可能中整段路程所得到的困難值的期望\(e\times 2^{n-1}\mod\ 998244353\)。

\(Solution\)

　　要求一個線性做法，我們嘗試遞推求它。
　　對每一個位置\(i\)，我們可以寫出它作為休息點(diǎn)時得到困難值的期望：\(e_i=\frac{a_1}{2}+\frac{a_2}{2^2}+\ldots+\frac{a_{i-1}}{2^{i-1}}+\frac{a_i}{2^{i-1}}\)。最后一項(xiàng)的概率是\(2^{i-1}\)，因?yàn)槭菑?號點(diǎn)出發(fā)。
　　那么就可以得到\(e_1=a_1，e_{i+1}=e_i-\frac{a_i}{2^i}+\frac{a_{i+1}}{2^i}\)。

//93ms 7700KB #include <cstdio> #include <cctype> #define gc() getchar() #define mod (998244353) const int N=1e6+5;int n,A[N],pw[N];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; }int main() {n=read();for(int i=1; i<=n; ++i) A[i]=read();pw[0]=1;for(int i=1; i<=n; ++i) pw[i]=pw[i-1]<<1, pw[i]>=mod&&(pw[i]-=mod);long long now=1ll*A[1]*pw[n-1]%mod, ans=now;for(int i=1; i<n; ++i){now=(now-1ll*A[i]*pw[n-1-i]%mod+1ll*A[i+1]*pw[n-1-i]%mod+mod)%mod,ans+=now;}printf("%I64d\n",ans%mod);return 0; }

F.Dominant Indices(啟發(fā)式合并)

顯然對于\(d_{x,i}\)，我們有\(d_{x,i}=\sum_{v=son[x]}d_{v,i-1}\)
Dominant Indices就是最大的\(d_{x,i}\)中下標(biāo)最小的\(i\)。我們可以利用啟發(fā)式合并求\(d_x\)。啟發(fā)式合并一般的復(fù)雜度是\(O(n\log n)\)的，但在本題中，復(fù)雜度只與深度較小的點(diǎn)的深度有關(guān)，而不是點(diǎn)數(shù)。所以復(fù)雜度是\(O(n)\)的。
我們還需要將數(shù)組整體右移，以便插入一個\(d_{x,0}=1\)。可以用map(\(O(n\log n)\))，也可以用vector倒序存儲，這樣就是\(O(n)\)的了。
也可以直接用個大點(diǎn)的(\(O(n)\)其實(shí)就夠了)數(shù)組，每個點(diǎn)維護(hù)在數(shù)組中的位置。

[Update]這就是dsu on tree或者長鏈剖分啊。

//546ms 89700KB #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() const int N=1e6+5;int n,Enum,H[N],nxt[N<<1],to[N<<1],Ans[N],A[N],pos[N],len[N],mx[N],mxpos[N];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } inline void AddEdge(int u,int v) {to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum; } void Merge(int x,int y)//x<-y {if(len[x]<len[y]){std::swap(pos[x],pos[y]), std::swap(len[x],len[y]), std::swap(mx[x],mx[y]), std::swap(mxpos[x],mxpos[y]);}for(int i=0,ly=len[y],px=pos[x],py=pos[y]; i<ly; ++i){A[px+i]+=A[py+i]; //A[px+i+1]+=A[py+i];if(A[px+i]>mx[x]) mx[x]=A[px+i], mxpos[x]=i;else if(A[px+i]==mx[x] && i<mxpos[x]) mxpos[x]=i;} } void DFS(int x,int f) {A[pos[x]]=1, len[x]=1, mx[x]=1, mxpos[x]=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f){pos[v]=pos[x]+len[x]+1, DFS(v,x);//給v騰出一位，合并前將v右移一位。否則len[x]==len[v]時會重疊。。A[--pos[v]]=0, ++len[v], ++mxpos[v], Merge(x,v);}Ans[x]=mxpos[x]; }int main() {n=read();for(int i=1; i<n; ++i) AddEdge(read(),read());pos[1]=1, DFS(1,1);for(int i=1; i<=n; ++i) printf("%d\n",Ans[i]);return 0; }

G.Allowed Letters(Hall定理 位運(yùn)算)

\(Description\)

給定長為n、由小寫字母a~f組成的字符串s。有m個限制，每個限制為：在\(pos_i\)處只能是某些字母(\(pos_i\)兩兩不同)。
你可以任意交換原串兩個字母的位置，問是否能得到滿足限制的串，若能，輸出滿足限制的最小字典序的字符串。

\(Solution\)

有n個字符，每個字符可以放在某些位置，要求這些字符全部放置->完備匹配。
可以跑網(wǎng)絡(luò)流，檢查最大流是否等于n，連邊比較好想。然后假設(shè)想要讓i位置放字符c，如果原最大流不需要c->i這條邊，那么可以；否則讓這條邊退流，容量-1，再檢查最大流是否等于n。
如果決定了位置i放字符c，那么要使c->i這條邊的容量-1.
沒寫，萬一調(diào)不出來有點(diǎn)。。Tutorial里說復(fù)雜度\(O(n*2^A*A^2)\)(A為字符集大小)，不知道\(2^A\)是為什么。。（好像也是判子集合法？）

可以考慮Hall定理。對于任意一個字符的子集，其中字符個數(shù)要<=能夠匹配其中字符的位置個數(shù)。
這樣的話對于同一種字符，顯然只需要檢驗(yàn)包含它最多的子集（位置數(shù)不會變）。所以我們要檢查的子集只有\(2^A=64\)個(A為字符集大小)。
任意子集包含字符的個數(shù)sum可以\(O(A*2^A)\)或\(O(2^A)\)算。對于(只要)能夠匹配某子集s中任意字符 的位置數(shù)我們可以去算：位置總數(shù)-只能匹配除s中字符外的位置數(shù)。
除s中字符外的子集可以表示為2^A-1-s，預(yù)處理其包含的所有子集的位置數(shù)即可，記為f[]。
如果現(xiàn)在要確定i位置放什么，那要先減掉i對f的貢獻(xiàn)，即枚舉所有包括 位置i可放字符子集 的子集，依次-1。要放某字符首先要能放，然后數(shù)量-1，再Check就行了。

//62ms 400KB #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #define gc() getchar() #define lb(i) (i&-i) const int N=1e5+7;int n,num[7],can[N],sum[69],f[69],bit[69]; char s[N],tmp[N];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } bool Check() {for(int i=1; i<64; ++i){sum[i]=sum[i^lb(i)]+num[bit[lb(i)]];if(sum[i]>f[63]/*not n，or n也-1*/-f[63-i]) return 0;}return 1; }int main() {scanf("%s",s+1), n=strlen(s+1);for(int i=1; i<=n; ++i) can[i]=63, ++num[s[i]-'a'];for(int m=read(),p; m--; ){can[p=read()]=0, scanf("%s",tmp+1);for(int j=1,l=strlen(tmp+1); j<=l; ++j)can[p]|=1<<tmp[j]-'a';}for(int i=1; i<=n; ++i) ++f[can[i]];for(int i=0; i<6; ++i)//求其包含的所有子集 先枚舉i！for(int j=1; j<64; ++j)if(j>>i & 1)f[j]+=f[j^(1<<i)];for(int i=0; i<6; ++i) bit[1<<i]=i;if(!Check()) return puts("Impossible"),0;for(int i=1; i<=n; ++i){for(int s=can[i]; s<=63; s=(s+1)|can[i]) --f[s];for(int j=0; j<6; ++j){if(!(can[i]>>j&1)) continue;--num[j];if(Check()) {putchar(j+'a'); break;}++num[j];}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/9311498.html

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 47 (Div 2) (A~G)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。