感覺(jué)這套比賽題目比較容易，沒(méi)有以前做過(guò)的某次codechef那么兇殘。題目還是很有意思的，最好的是有中文翻譯。

?

?

CSUB：簽到題，直接從左往右掃一遍即可，維護(hù)前面出現(xiàn)過(guò)多少個(gè)1.

#include <cstdio> #include <cstring> #define maxn 100100 using namespace std;char s[maxn]; long long ans; int cur,T,n;int main() {scanf("%d",&T);while (T--){scanf("%d%s",&n,s);ans=cur=0;for (int i=0; s[i]; i++)if (s[i]=='1') ans+=++cur;printf("%lld\n",ans);}return 0; }

?

?

RETPO：簡(jiǎn)單找規(guī)律。注意一開(kāi)始的朝向，同時(shí)根據(jù)對(duì)稱(chēng)性，所有的點(diǎn)都可以對(duì)稱(chēng)到第一象限來(lái)。要走彎路的話，第一個(gè)單位距離消耗3步，第二個(gè)單位距離消耗1步，第三個(gè)消耗3步，第四個(gè)1步，依次類(lèi)推即可。

#include <iostream> #include <cstdio> #include <cstring> using namespace std;long long x,y,n,ans; int T;int main() {scanf("%d",&T);while (T--){scanf("%lld%lld",&x,&y);if (x<0) x=-x;if (y<0) y=-y;n=y-x;if (n>=0 && n<=1) ans=x+y;else {if (n<0) n=-n;if (y>x) ans=2*min(x,y)+(n/2)*4+(n&1)*1;else ans=2*min(x,y)+(n/2)*4+(n&1)*3;}printf("%lld\n",ans);}return 0; }

?

?

FROGV：氺題。對(duì)于每只青蛙，f[i]保存它向右最遠(yuǎn)可以傳遞到那一只青蛙，假設(shè)當(dāng)前我們計(jì)算第i只青蛙，對(duì)于j>i，且i可以傳遞信息給j，那么f[i]=max(f[j])。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100100 using namespace std;int g[maxn],f[maxn]; int n,m,k,x,y;struct node{int x,id; }a[maxn];bool cmp(node n1,node n2) {return n1.x<n2.x; }int main() {scanf("%d%d%d",&n,&k,&m);for (int i=1; i<=n; i++) scanf("%d",&a[i].x),a[i].id=i;sort(a+1,a+1+n,cmp);for (int i=1; i<=n; i++) g[a[i].id]=i;f[n]=n;for (int i=n-1; i>0; i--)if (a[i+1].x-a[i].x<=k) f[i]=f[i+1];else f[i]=i;while (m--){scanf("%d%d",&x,&y);x=g[x],y=g[y];if (x>y) swap(x,y);if (y<=f[x]) puts("Yes");else puts("No");}return 0; }

?

?

SGARDEN：數(shù)學(xué)題。對(duì)于一種置換，它里面一定構(gòu)成了若干個(gè)環(huán)。所有人都回到原地的步數(shù)就是所有環(huán)長(zhǎng)度的lcm值。由于這個(gè)lcm值很大，必須對(duì)于每個(gè)環(huán)長(zhǎng)度進(jìn)行因數(shù)分解，保存每個(gè)質(zhì)數(shù)出現(xiàn)的次數(shù)就可。最后取模計(jì)算。

#include <iostream> #include <cstdio> #include <cstring> #include <map> #define maxn 100100 typedef long long ll; using namespace std;const int M=1000000007; int a[maxn],T,n,cur,N; bool b[maxn]; ll ans; map<int,int> ss;void dfs(int x) {if (b[x]) return;cur++,b[x]=true;dfs(a[x]); }void deal(int x) {for (int i=2; i*i<=x; i++){if (x%i) continue;N=0;while (x%i==0) x/=i,N++;ss[i]=max(ss[i],N);}if (x>1) ss[x]=max(ss[x],1); }int main() {scanf("%d",&T);while (T--){ss.clear();ans=1;scanf("%d",&n);for (int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=false;for (int i=1; i<=n; i++)if (!b[i]){cur=0;dfs(i);deal(cur);}for (int i=2; i<=n; i++)while (ss[i]--) ans=(ans*i)%M;printf("%lld\n",ans);}return 0; }

?

?

DISHOWN：一看這個(gè)題目就是一個(gè)典型的并查集了。每次查找盤(pán)子的主人，然后兩個(gè)主人之間的比較無(wú)非就是改變一下指針而已了，路徑壓縮，所有的操作都是O(1)的。

#include <iostream> #include <cstdio> #include <cstring> #define maxn 10010 using namespace std;int a[maxn],f[maxn]; int n,q,T;int father(int x) { return f[x]==x?f[x]:f[x]=father(f[x]); }int main() {int ope,x,y;scanf("%d",&T);while (T--){scanf("%d",&n);for (int i=1; i<=n; i++) scanf("%d",&a[i]),f[i]=i;scanf("%d",&q);while (q--){scanf("%d",&ope);if (ope==0){scanf("%d%d",&x,&y);x=father(x),y=father(y);if (a[x]==a[y]){if (x==y) puts("Invalid query!");continue;}if (a[x]>a[y]) f[y]=x;else f[x]=y;}else {scanf("%d",&x);printf("%d\n",father(x));}}}return 0; }

?

?

LEPAINT：這個(gè)題目我一開(kāi)始以為我會(huì)T。沒(méi)想到寫(xiě)了一發(fā)最最暴力的居然都A掉了。不過(guò)我覺(jué)得這個(gè)應(yīng)該是被卡掉的，只是數(shù)據(jù)不夠強(qiáng)吧。優(yōu)化可以是這樣的，對(duì)于物品，直接預(yù)處理它染色多少次后，為某種顏色的概率。同時(shí)，后面的區(qū)間染色就用掃描區(qū)間的方法，直接得出，直接求和即可。對(duì)于題目所說(shuō)的取子集的問(wèn)題，就相當(dāng)于在這個(gè)范圍里面每一個(gè)物品都有0.5的概率被染色。

#include <iostream> #include <cstdio> #include <cstring> using namespace std;double f[55][111],tmp[111],ans; int L,R,n,m,c,T;int main() {scanf("%d",&T);while (T--)//10 {scanf("%d%d%d",&n,&c,&m);for (int i=1; i<=n; i++){for (int j=0; j<c; j++) f[i][j]=0;f[i][1]=1;}while (m--)//50 {scanf("%d%d",&L,&R);for (int i=L; i<=R; i++)//50 {for (int j=0; j<c; j++) f[i][j]/=2,tmp[j]=f[i][j];for (int j=0; j<c; j++)//100for (int k=0; k<c; k++)//100f[i][j*k%c]+=tmp[j]/c;}}ans=0; for (int i=1; i<=n; i++)for (int j=0; j<c; j++) ans+=f[i][j]*j;printf("%.9f\n",ans);}return 0; }

?

?

GNUM：很好的一個(gè)題目。一開(kāi)始我就看準(zhǔn)了這個(gè)題目，花時(shí)間最多的一個(gè)題目。讀完題目后直接想到的就是二分圖取匹配。顯然是T。可以建模來(lái)解。以a[i]<b[j]且滿(mǎn)足gcd條件的點(diǎn)位左邊點(diǎn)，連接源點(diǎn)，以a[i]>b[j]且滿(mǎn)足gcd條件的點(diǎn)為右點(diǎn)，連接匯點(diǎn)。中間是gcd出現(xiàn)過(guò)的質(zhì)數(shù)，分別連接相應(yīng)的左右點(diǎn)，所有的邊流量都是1，跑最大流即可。這個(gè)做法肯定是沒(méi)有錯(cuò)的。但是還是有一些問(wèn)題存在。點(diǎn)太多了。咋解決？縮點(diǎn)，分別把左右邊的點(diǎn)中含有相同的質(zhì)因子種類(lèi)的點(diǎn)縮成一個(gè)點(diǎn)，邊容量累加。再跑最大流，縮點(diǎn)后，點(diǎn)數(shù)的級(jí)別也就1000吧，可以ac。

#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <map> #define maxn 2002000 #define maxpri 100100 using namespace std;int pri[maxpri],pnum=0,antipri[maxpri]; int z[1888][30],Z[1888],a[1888],aa[1888]; int to[maxn],c[maxn],next[maxn],first[maxn],edge,node; int tag[maxn],d[maxn],Q[maxn],bot,top,TAG=520; int f[566666][30],Tf; bool can[maxn]; int T,n,tmp,s,t,ans,cas; map<int,int> ss,pos,Ttime;//è′¨?�°?ˉ1?o�?��?�1?��??�?�·int gcd(int A,int B) { return B==0?A:gcd(B,A%B); }void getprim() {for (int i=2; i<maxpri; i++){if (antipri[i]==-1) continue;pri[++pnum]=i; antipri[i]=pnum;for (int j=i+i; j<maxpri; j+=i) antipri[j]=-1;} }int addnode() {node++;first[node]=-1;return node; }void _init() {ss.clear(),pos.clear(),Ttime.clear();edge=-1,node=0,Tf=0;s=addnode(),t=addnode();ans=0; }void addedge(int U,int V,int W) {edge++;to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;edge++;to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge; }void deal(int x) {Z[x]=0,tmp=a[x],aa[x]=tmp;for (int i=1; pri[i]<=tmp/pri[i]; i++)if (tmp%pri[i]==0){z[x][++Z[x]]=pri[i];while (tmp%pri[i]==0) tmp/=pri[i];}if (tmp>1) z[x][++Z[x]]=tmp;for (int i=1; i<=Z[x]; i++)while (((aa[x]/z[x][i])%z[x][i])==0) aa[x]/=z[x][i]; }void buildedge() {for (int x=1; x<=n; x++)for (int y=n+1; y<=n+n; y++)if (a[x]<a[y] && gcd(aa[x],aa[y])>1){ int cur=gcd(aa[x],aa[y]); if (pos[cur]) { Ttime[cur]=Ttime[cur]+1; continue; }pos[cur]=++Tf,f[Tf][0]=0,Ttime[cur]=1;for (int i=1; i<=Z[x]; i++)if (aa[y]%z[x][i]==0) f[Tf][++f[Tf][0]]=z[x][i]; f[Tf][f[Tf][0]+1]=cur;}for (int i=1; i<=Tf; i++){int cur=f[i][f[i][0]+1],tc=Ttime[cur],Nd=addnode();//Nd??o??�?��gcd??￡è?¨?��?�1?�� addedge(s,Nd,tc);for (int j=1; j<=f[i][0]; j++){if (ss[f[i][j]]==0) ss[f[i][j]]=addnode();addedge(Nd,ss[f[i][j]],tc);}}pos.clear(),Tf=0;for (int x=1; x<=n; x++)for (int y=n+1; y<=n+n; y++)if (a[x]>a[y] && gcd(aa[x],aa[y])>1){ int cur=gcd(aa[x],aa[y]);if (pos[cur]) { Ttime[cur]=Ttime[cur]+1; continue; }pos[cur]=++Tf,f[Tf][0]=0,Ttime[cur]=1;for (int i=1; i<=Z[x]; i++)if (aa[y]%z[x][i]==0) f[Tf][++f[Tf][0]]=z[x][i];f[Tf][f[Tf][0]+1]=cur;}for (int i=1; i<=Tf; i++){int cur=f[i][f[i][0]+1],tc=Ttime[cur],Nd=addnode();//Nd??o??�?��gcd??￡è?¨?��?�1?�� addedge(Nd,t,tc);for (int j=1; j<=f[i][0]; j++){if (ss[f[i][j]]==0) continue;addedge(ss[f[i][j]],Nd,tc);}} }bool bfs() {TAG++;Q[bot=top=1]=t,d[t]=0,tag[t]=TAG,can[t]=false;while (bot<=top){int cur=Q[bot++];for (int i=first[cur]; i!=-1; i=next[i])if (c[i^1]>0 && tag[to[i]]!=TAG){tag[to[i]]=TAG,Q[++top]=to[i],d[to[i]]=d[cur]+1,can[to[i]]=false;if (to[i]==s) return true;}}return false; }int dfs(int cur,int num) {if (cur==t) return num;int tmp=num,k;for (int i=first[cur]; i!=-1; i=next[i])if (c[i]>0 && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && can[to[i]]==false){k=dfs(to[i],min(num,c[i]));if (k) num-=k,c[i]-=k,c[i^1]+=k;//if (num==0) return tmp; }if (num) can[cur]=true;return tmp-num; }int main() {getprim(); scanf("%d",&T); while (T--){scanf("%d",&n);for (int i=1; i<=2*n; i++) scanf("%d",&a[i]),deal(i);_init();buildedge(); while (bfs()) ans+=dfs(s,maxn);printf("%d\n",ans);}return 0; }

?

?

SEAEQ：為什么這是整場(chǎng)比賽通過(guò)人數(shù)最少的題目？我覺(jué)得在平時(shí)比賽這種難度的題目也就算中等吧？此題讓我想去去年杭州賽的那個(gè)題。深坑吶。解法是這樣的，dp預(yù)處理長(zhǎng)度為i的排列有不超過(guò)j個(gè)逆序數(shù)對(duì)的情況有多少種！這個(gè)可以dp好好想想就知道了，剩下的就是逆推枚舉了，直接枚舉區(qū)間長(zhǎng)度，位置，對(duì)于兩個(gè)排列其他的位置都是全排列即可。對(duì)于題目的那個(gè)要求就是在規(guī)定區(qū)間內(nèi)，每個(gè)位置的相對(duì)大小相同即可，這個(gè)只需要保證對(duì)于預(yù)處理的種類(lèi)數(shù)乘一次，對(duì)于取組合數(shù)和全排列數(shù)乘以?xún)纱渭纯伞２浑y理解，自己想想就很清楚了。一開(kāi)始取模打成了1000000009，都怪前幾天打的那場(chǎng)acdream，坑死啦。

#include <iostream> #include <cstdio> #include <cstring> #define maxn 502 typedef long long ll; using namespace std;const int M=1000000007; int n,e,T,ans; int sum[maxn][(maxn*maxn-maxn)/2];//????????￥?o?|?￥???????????????￥?o????|????°?￥?ˉ?1?|????° ll P[maxn],C[maxn][maxn];int main() {P[0]=1,C[0][0]=1;for (int i=1; i<maxn; i++) P[i]=(P[i-1]*i)%M;for (int i=1; i<maxn; i++){C[i][0]=1;for (int j=1; j<=i; j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;}int last=0,next;sum[1][0]=1;for (int i=2; i<maxn; i++){next=last+i-1;sum[i][0]=1;for (int j=1; j<i; j++){sum[i][j]=sum[i][j-1]+sum[i-1][j];if (sum[i][j]>=M) sum[i][j]-=M;}for (int j=i; j<=last; j++){sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-i];if (sum[i][j]>=M) sum[i][j]-=M;if (sum[i][j]<0) sum[i][j]+=M;}for (int j=last+1; j<=next; j++){sum[i][j]=sum[i][j-1]+sum[i-1][last]-sum[i-1][j-i];if (sum[i][j]>=M) sum[i][j]-=M;if (sum[i][j]<0) sum[i][j]+=M;}last=next;}scanf("%d",&T);while (T--){scanf("%d%d",&n,&e);ans=0;for (int i=1; i<=n; i++){int cur=min((i*i-i)/2,e);cur=sum[i][cur];ll tmp=(C[n][i]*P[n-i])%M;tmp=((tmp*tmp)%M*cur)%M;ans+=(tmp*(n+1-i))%M;if (ans>=M) ans-=M;}printf("%d\n",ans);}return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的Codechef_JULY14的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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