文章目錄

• 前言
• CF104A Blackjack
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF103A Testing Pants for Sadness
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF103B Cthulhu
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF103C Russian Roulette
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF103D Time to Raid Cowavans
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF103E Buying Sets
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Description}$

前言

比較水的遠古比賽
104A、103A、103B是水題
103C是兼有細節處理和思維含量
103D是小清新簡單分塊題
103E是神仙網絡流（強烈推薦）

CF104A Blackjack

$\text{Description}$

Blackjack 是一個撲克牌游戲。

Blackjack 使用除了兩張王以外的全部 52 張卡牌，也就是 $2,3,4,5,6,7,8,9,10,J,Q,K,A$。其中規定 $2,3,4,5,6,7,8,9,10$ 的點數為 $2,3,4,5,6,7,8,9,10$，$J,Q,K$ 的點數均為 $10$，$A$ 的點數同時為 $1$ 或 $11$，這取決于玩家的意愿。雖然撲克牌有花色，但是一張卡牌的點數與其花色無關。這個游戲的規則很簡單：拿兩張牌，如果這兩張牌的點數之和等于 $n$，玩家就贏了，否則玩家就輸了。

現在玩家已經拿了一張黑桃 $Q$，求在其他牌中再抽一張，能使玩家贏得游戲的方案數。

$\text{Solution}$

垃圾水題。
分情況特判一下即可。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,k,m;signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endif//debug("sdsa");n=read()-10;if(n<=0) printf("0");else if(n<=9) printf("4");else if(n==10) printf("15");else if(n==11) printf("4");else printf("0");return 0; } /* */

CF103A Testing Pants for Sadness

$\text{Description}$

有個人要做 $n$ 道選擇題，必須按 $1～n$ 的順序答題，第 $i$ 題有 $a_i$ 個選項。不幸的是，這些題這個人一道也不會，只能猜選項，但是他的記憶非常好，可以記住所有題曾經的正確選項。當他做錯一道題時，他就必須從 $1$ 重新開始選，假設題目的正確選項不會變，在最壞的情況下，若要做對所有題，他一共選了多少次選項？

$1\le n\le 100,1\le a_i\le 10^9$

$\text{Solution}$

個人心中簽到題的榜樣。
沒碼量，又有一點點思維。
對于第 $i$ 關單獨考慮考慮。
首先，每個錯誤選項都會且只會選一次，也就是 $1\times (a_i?1)$。
對于正確選項，它會被選做到這一關的次數，換句話說就是之后答錯的次數 $+1$，也就是 ${\sum }_{j=i+1}^n(a_j?1)+1$
全加起來即可，后綴和優化一下，時間復雜度 $O(n)$。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,k,m; ll a[N],suf[N],ans; signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();for(int i=1;i<=n;i++) a[i]=read();suf[n+1]=1;for(int i=n;i>=1;i--) suf[i]=suf[i+1]+a[i]-1;for(int i=1;i<=n;i++) ans+=a[i]-1+suf[i+1];printf("%lld\n",ans);return 0; } /* */

CF103B Cthulhu

$\text{Description}$

給出一個圖，判斷它是不是一個環的大小不小于 $3$ 的奇環樹。

$\text{Solution}$

這題的唯一難度可能僅在于耐著性子把英語題面看完…
看懂題面后就幾乎沒有難度了。
dfs 一遍即可。
別忘了判連通性。
（后來看題解才想起來本題根本就沒有重邊，所以根本不需要 dfs，并查集判一下連通性就可以了。）

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; }int n,m; int flag; int vis[N]; vector<int>v[N]; void dfs(int x,int fa){vis[x]=1;for(int to:v[x]){if(to==fa) continue;if(vis[to]) flag=1;else dfs(to,x);}return; } signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();if(m!=n){printf("NO");return 0;}for(int i=1;i<=m;i++){int x=read(),y=read();v[x].push_back(y);v[y].push_back(x);}dfs(1,0);if(!flag) printf("NO");else{for(int i=1;i<=n;i++){if(!vis[i]){printf("NO");return 0;}}printf("FHTAGN!");}return 0; } /* */

CF103C Russian Roulette

$\text{Description}$

兩個傻瓜玩俄羅斯輪盤（輪流開槍，直到一方死亡），$n$ 個位置里有 $k$ 個子彈，請你填裝這 $k$ 個子彈，使先開槍者死亡的概率最小，在滿足該條件的情況下最小化方案的字典序（空彈夾字典序更小）。
每次詢問位置 $x$ 是否裝有子彈。
$k\le n\le 10^{18}$

$\text{Solution}$

有點小細節的一道題。
（樣例真心良心）
有子彈的地方先手必然死，所以我們就是讓空彈夾先手死的盡可能少就行了。

通過觀察樣例二可以發現，從后往前，隔一個放一顆子彈是一種很好的方案。
但是觀察樣例三可以發現，在剛才那種構造的基礎上，有的時候可以把一枚最前面的子彈挪到后面挨著放，死亡概率不變，但字典序更小。
具體的，這種情況是在前面空出的連續空白段長度為偶數時成立，這時候前面去掉一個必勝位置的數量不變。

還有一些其它邊邊角角的情況，在 $2k\ge n$ 時，后面挨著放前面隔著放即可；還要注意 $n=1$ 的時候不能“把最前面的一個挪到后面挨著放”（因為一共就只有一個）

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; }ll n,k,m; int op; signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();k=read();m=read();ll pl(0);if(k*2>=n){op=1;pl=2*(n-k);}else if((n-2*k)%2==0||k<=1){op=2;pl=n-2*k;}else{op=3;pl=2*k-2;}for(int i=1;i<=m;i++){ll x=read();if(op==1){if(x>pl||(x&1)==0) printf("X");else printf(".");}else if(op==2){if(x<=pl||((x-pl)&1)) printf(".");else printf("X");}else{x=n-x+1;if(x<=2||(x<=pl&&x%2==0)) printf("X");else printf(".");}}return 0; } /* */

CF103D Time to Raid Cowavans

$\text{Description}$

一個序列 $a$ ，$m$ 次詢問，每次詢問給出 $t,k$。求 $a_t+a_{t+k}+a_{t+2k}+?+a_{t+pk}$ 其中 $t+pk\le n$ 且 $t+(p+1)k>n$。

$n,m\le 300000,a_i\le 10^9$

$\text{Solution}$

似乎題解有對前綴和進行分塊優化空間從而在線的神仙做法？
但是這題離線就挺香的了
不難想到根號分治，對于 $k>\sqrt{n}$ 的詢問，直接暴力即可。
對于 $k\le \sqrt{n}$ 的詢問，離線下來對于 $\sqrt{n}$ 個可能的 $k$ 分別處理前綴和就可以 $O(1)$ 回答所有詢問。
時間復雜度 $O(n\sqrt{n})$，空間復雜度 $O(n)$。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=3e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; }int n,m;ll sum[N],a[N]; struct query{int st,d,id;bool operator < (const query o)const{return d<o.d;} }q[N]; int tot; ll ans[N]; signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();int w=sqrt(n);for(int i=1;i<=n;i++) a[i]=read();m=read();for(int i=1;i<=m;i++){int aa=read(),b=read();if(b>w){ll res(0);for(int j=aa;j<=n;j+=b) res+=a[j];ans[i]=res;}else q[++tot]=(query){aa,b,i};}sort(q+1,q+1+tot);int now(0);for(int i=1;i<=tot;i++){if(now!=q[i].d){now=q[i].d;for(int j=1;j<=n;j++){sum[j]=a[j];if(j>now) sum[j]+=sum[j-now];} }int id=q[i].id,st=q[i].st,d=q[i].d,ed=st+(n-st)/d*d;ans[id]=sum[ed];if(st>now) ans[id]-=sum[st-now];}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0; } /* */

CF103E Buying Sets

$\text{Description}$

有一個大小為 $n$ 的全集，每個元素是一個數，有 $n$ 個子集。題目保證任意 $k$ 個子集的并的大小 $?k$ 。

每個子集有一個可正可負的權值，你需要選出一些子集使得這些子集并的大小等于子集個數，且所選子集的權值和最小。可以為空集。
$n\le 300$

$\text{Solution}$

一道網絡流比較神的題。
首先可以補集轉化，選的權值最小，轉化為不選的權值最大。
然后由于這種題大多數都是轉成最小割，所以把所有權值取反。

然后就是關鍵的建圖：
原點向所有集合連容量等于集合權值 $INF$ 的邊，集合向包含的數字連 $INF$ 的邊，數字向匯點連 $INF$ 的邊。
顯然，斷數字和集合之間的邊是不優的；而其中集合斷邊相當于不選，數字斷邊相當于選。
這樣，考慮任意一種割的方案，都說明選擇了所有的集合和他們的數字的并集。

但是怎么保證數字數量等于集合數量呢？
假設左邊斷了 $x$ 條邊，剩的 $n?x$ 個集合必然連向不少于 $n?x$ 個數，所以右邊斷邊不少于 $n?x$ 條，總斷邊數不少于 $n$ 條。
同時，只斷 $n$ 條的方案顯然存在（只砍一邊就行），又由于每條邊的權值加上了 $INF$，所以顯然最終的答案就會斷 $n$ 條。
回到剛才斷邊的定義，就是：未選集合+選取元素=n，也就是選取集合數等于選取元素數。
得證。

$\text{Description}$

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=3e5+100; #define ll long long #define ui unsigned int inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; }int n,m;#define inf 1000000000ll struct node{int to,nxt,cap; }p[N]; int fi[N],cur[N],cnt; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],w};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0};fi[y]=cnt;return; } int s,t; int bel[N],q[N],st,ed; bool bfs(){q[st=ed=1]=s;memset(bel,0,sizeof(bel));bel[s]=1;while(st<=ed){int now=q[st++];for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap||bel[to]) continue;bel[to]=bel[now]+1;q[++ed]=to;}}return bel[t]?1:0; } int dfs(int x,int lim){if(!lim||x==t) return lim;int res(0);for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap||bel[to]!=bel[x]+1) continue;int add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(!res) bel[x]=-1;return res; } ll dinic(){ll flow(0),tmp(0);while(bfs()){while((tmp=dfs(s,2e9))) flow+=tmp;}return flow; }signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();ll sum(0);s=2*n+1;t=s+1;for(int i=1;i<=n;i++) addline(i+n,t,inf);for(int i=1;i<=n;i++){int k=read();for(int j=1;j<=k;j++){int x=read();addline(i,x+n,inf);}}for(int i=1;i<=n;i++){int w=read();sum-=w;addline(s,i,inf-w);}printf("%lld\n",(dinic()-1ll*n*inf)-sum);return 0; } /* */

總結

以上是生活随笔為你收集整理的CodeForces:103(div1)104(div2)的全部內容，希望文章能夠幫你解決所遇到的問題。

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