day3

模擬賽，看了看a組題，發(fā)現(xiàn)是博弈論，非常開心（因?yàn)楹猛?#xff09;，于是做的a組。結(jié)果差點(diǎn)爆零，死命糾結(jié)t1的sg函數(shù)，但其實(shí)只是一個(gè)dp，不用扯到sg函數(shù)的那種。

?

t1：

Description

被污染的灰灰草原上有羊和狼。有N只動(dòng)物圍成一圈，每只動(dòng)物是羊或狼。
該游戲從其中的一只動(dòng)物開始，報(bào)出[1,K]區(qū)間的整數(shù)，若上一只動(dòng)物報(bào)出的數(shù)是x，下一只動(dòng)物可以報(bào)[x+1,x+K]區(qū)間的整數(shù)，游戲按順時(shí)針方向進(jìn)行。每只動(dòng)物報(bào)的數(shù)字都不能超過M。若一只動(dòng)物報(bào)了M這個(gè)數(shù)，它所在的種族就輸了。問以第i只動(dòng)物為游戲的開始，最后哪種動(dòng)物會(huì)贏？
?

Input

第一行輸入三個(gè)正整數(shù)N，M，K。
接下來一行N個(gè)正整數(shù)，分別表示N只動(dòng)物的種類，以順時(shí)針的方向給出。0代表羊，1代表狼。
?
?

Output

一行輸出N個(gè)整數(shù)，表示若從第i只動(dòng)物開始，贏的動(dòng)物的種類。同上，0代表羊，1代表狼。

就是dp,f[i][j]表示第i個(gè)動(dòng)物報(bào)數(shù)最大為j是否必勝。然后加一個(gè)后綴和（應(yīng)該能叫后綴和吧）（或者說區(qū)間和？）優(yōu)化。

?

中間還wa了一次，因?yàn)樵谔幚韘數(shù)組時(shí)減去的那個(gè)f數(shù)組越界了，需要特判一下。

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,kk; int f[10010][5010],a[10010],s[10010][5010]; int main() { freopen("vode.in","r",stdin); freopen("vode.out","w",stdout); scanf("%d%d%d",&n,&m,&kk); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int p=1; for(int i=n+1;i<=n+m;i++) { if(p>n) p=1; a[i]=a[p]; p++; } for(int i=n+m-1;i>=1;i--) for(int j=m-1;j>=1;j--) { if(a[i]==a[i+1]) { s[i][j]=s[i][j+1]; if(j+kk<m) s[i][j]-=f[i][j+kk]; if(s[i+1][j+1]>0) { f[i][j]=1; s[i][j]++; } } else { s[i][j]=s[i][j+1]; if(j+kk<m) s[i][j]-=f[i][j+kk]; if(s[i+1][j+1]==0) { f[i][j]=1; s[i][j]++; } } } for(int i=1;i<=n;i++) for(int j=1;j<=kk;j++) if(f[i][j]) { printf("%d ",a[i]); break; } else if(j==kk) { printf("%d ",a[i]^1); } fclose(stdin); fclose(stdout); return 0; }

?

不想改a組了，先寫了一個(gè)b組t3玩。

Description

話說，?小X是個(gè)數(shù)學(xué)大佬，他喜歡做數(shù)學(xué)題。有一天，小X想考一考小Y。他問了小Y一道數(shù)學(xué)題。題目如下：
??????對(duì)于一個(gè)正整數(shù)N，存在一個(gè)正整數(shù)T（0<T<N），使得

的值是正整數(shù)。
??????小X給出N，讓小Y給出所有可能的T。如果小Y不回答這個(gè)神奇的大佬的簡(jiǎn)單數(shù)學(xué)題,他學(xué)神的形象就會(huì)支離破碎。所以小Y求你幫他回答小X的問題。

Input

一個(gè)整數(shù)N。

Output

第一個(gè)數(shù)M，表示對(duì)于正整數(shù)N，存在M個(gè)不同的正整數(shù)T，使得

是整數(shù)。
后面是M個(gè)數(shù)，每一個(gè)數(shù)代表可能的正整數(shù)T（按從小到大的順序排列）。

就是把式子化簡(jiǎn)一下，設(shè)比值為k，然后會(huì)發(fā)現(xiàn)T=(2K-2)/(2K-1)*N,我們要讓t為正整數(shù)，同時(shí)（2K-2）/(2K-1)又不能為一，2k-1就一定為n的因子。k為正整數(shù)，所以2k-1為奇數(shù)，然后就可以n?枚舉找n的奇因子了。注意一下2k-2不能為零，也就是2k-1不能為1。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; long long n,a[1000010],cnt; int main() { freopen("math.in","r",stdin); freopen("math.out","w",stdout); scanf("%lld",&n); long long sn=sqrt(n); for(long long i=1;i<=sn;i++) if(!(n%i)) { if((i%2)&&i!=1) a[++cnt]=(n/i)*(i-1); if((n/i)%2&&(n/i)!=1) a[++cnt]=i*(n/i-1); } cout<<cnt<<" "; sort(a+1,a+1+cnt); for(int i=1;i<=cnt;i++) printf("%lld ",a[i]); fclose(stdin); fclose(stdout); return 0; }

?

然后我終于改了a組t2：

Description

有一副n*m的地圖，有n*m塊地，每塊是下列四種中的一種：
墻：用#表示，墻有4個(gè)面，分別是前面，后面，左面，右面。
起點(diǎn)：用C表示，為主角的起點(diǎn)，是一片空地。
終點(diǎn)：用F表示，為主角的目的地，是一片空地。
空地：用?. 表示。
其中除了墻不能穿過，其他地方都能走。
?
主角有以下3種操作：
1.移動(dòng)到相鄰的前后左右的地方，花費(fèi)一個(gè)單位時(shí)間。
2.向前后左右其中一個(gè)方向發(fā)射子彈，子彈沿直線穿過，打在最近的一堵墻的一面，然后墻的這面就會(huì)形成一個(gè)開口通往秘密通道。同一時(shí)間最多只能有兩個(gè)開口，若出現(xiàn)有3個(gè)開口，出現(xiàn)時(shí)間最早的開口會(huì)立即消失。該操作不用時(shí)間。
3.可以從一個(gè)與開口相鄰的空地跳進(jìn)去，進(jìn)入秘密通道，從另外一個(gè)開口正對(duì)的空地跳出來。這個(gè)過程花費(fèi)一個(gè)單位時(shí)間。

地圖四周都是墻，問主角最少用多少時(shí)間從C走到F。C和F
只會(huì)出現(xiàn)一次。
?

Input

第一行輸入兩個(gè)正整數(shù)n，m。
接下來n行，每行m個(gè)字符描述地圖。
?

Output

輸出1個(gè)整數(shù)，表示最短時(shí)間完成路途。如果無解輸出nemoguce 我當(dāng)時(shí)打了bfs，然后愉悅爆零。哇的一下哭出聲。 這個(gè)題是把每一個(gè)非墻點(diǎn)與相鄰點(diǎn)連邊權(quán)為1的邊，然后找到四個(gè)方向的墻，連一條邊權(quán)為min（dis（此點(diǎn)，墻邊傳送門的點(diǎn)））+1的邊（其實(shí)和最近的傳送門點(diǎn)應(yīng)該連邊權(quán)為dis的邊，但可以從邊權(quán)為1的邊走過去，不影響答案）。然后跑spfa，求起點(diǎn)到終點(diǎn)最短路即可。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,m,s,t,cnt,head[250010],dis[250010],vis[250010]; char mp[510][510]; struct Edge { int v,nxt,val; }e[10000010]; void add(int u,int v,int val) { e[++cnt].v=v; e[cnt].nxt=head[u]; e[cnt].val=val; head[u]=cnt; } int num(int x,int y) { return (x-1)*m+y; } void spfa() { memset(dis,0x3f3f3f3f,sizeof(dis)); queue<int>q; dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(dis[v]>dis[u]+e[i].val) { dis[v]=dis[u]+e[i].val; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } int main() { freopen("portal.in","r",stdin); freopen("portal.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>mp[i][j]; if(mp[i][j]=='C') s=num(i,j); else if(mp[i][j]=='F') t=num(i,j); } for(int i=2;i<n;i++) for(int j=2;j<m;j++) if(mp[i][j]!='#') { int x1=i,x2=i,y1=j,y2=j; int mindis=0x3f3f3f3f; while(mp[x1+1][j]!='#') x1++; while(mp[x2-1][j]!='#') x2--; while(mp[i][y1+1]!='#') y1++; while(mp[i][y2-1]!='#') y2--; mindis=min(x1-i,min(i-x2,min(y1-j,j-y2))); mindis++; add(num(i,j),num(x1,j),mindis); add(num(i,j),num(x2,j),mindis); add(num(i,j),num(i,y1),mindis); add(num(i,j),num(i,y2),mindis); if(mp[i+1][j]!='#') add(num(i,j),num(i+1,j),1); if(mp[i-1][j]!='#') add(num(i,j),num(i-1,j),1); if(mp[i][j+1]!='#') add(num(i,j),num(i,j+1),1); if(mp[i][j-1]!='#') add(num(i,j),num(i,j-1),1); } spfa(); if(dis[t]==0x3f3f3f3f) cout<<"nemoguce"; else cout<<dis[t]; fclose(stdin); fclose(stdout); return 0; }

其實(shí)題目不是不可做，就是考試死活想不到正路上......dalao炒雞多啊我的天，orz。

然而我還是改完了t3：

Description

有n個(gè)城市，標(biāo)號(hào)為1到n，修建道路花費(fèi)m天，第i天時(shí)，若gcd(a,b)=m-i+1，則標(biāo)號(hào)為a的城市和標(biāo)號(hào)為b的城市會(huì)建好一條直接相連的道路，有多次詢問，每次詢問某兩座城市最早什么時(shí)候能連通。
?

Input

第一行輸入三個(gè)正整數(shù)n,m,q，其中q表示詢問個(gè)數(shù)。
接下來q行，每行兩個(gè)正整數(shù)x，y，表示詢問城市x和城市y最早什么時(shí)候連通。
?

Output

輸出q行，每行一個(gè)正整數(shù)，表示最早連通的天數(shù)
?

?并查集，按秩合并，把時(shí)間賦為點(diǎn)權(quán)（我之前糾結(jié)了半天怎么連邊權(quán)2333），在并查集樹上找max點(diǎn)權(quán)就行。

?

re了好幾次，最后發(fā)現(xiàn)freopen文件名打錯(cuò)了......

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,q,fa[100010],dep[100010],siz[100010],tim[100010],x,y; int find_fa(int x) { if(fa[x]==x) return x; return find_fa(fa[x]); } void update(int x) { if(fa[x]==x) return; update(fa[x]); dep[x]=dep[fa[x]]+1; } int query(int a,int b) { int res=0; if(dep[a]<dep[b]) swap(a,b); while(dep[a]>dep[b]) { res=max(res,tim[a]); a=fa[a]; } while(a!=b) { res=max(res,max(tim[a],tim[b])); a=fa[a]; b=fa[b]; } return res; } int main() { freopen("pictionary.in","r",stdin); freopen("pictionary.out","w",stdout); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; for(int i=1;i<=m;i++) { int r=n/(m-i+1); int p=m-i+1; for(int j=2;j<=r;j++) { int f1=find_fa(p*(j-1)); int f2=find_fa(p*j); if(f1!=f2) { if(siz[f1]<siz[f2]) swap(f1,f2); fa[f2]=f1; tim[f2]=i; siz[f1]=max(siz[f1],siz[f2]+1); } } } for(int i=1;i<=n;i++) update(i); for(int i=1;i<=q;i++) { scanf("%d%d",&x,&y); printf("%d\n",query(x,y)); } fclose(stdin); fclose(stdout); return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Eternal-Glory/p/9452002.html

總結(jié)

以上是生活随笔為你收集整理的纪中2018暑假培训day3提高a组改题记录（混有部分b组）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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