http://codeforces.com/gym/101243

A題

思路：一條魚有兩面，所以當N<=K時間是2倍的單位時間。否則的話應該是N*2/k向上取整。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int main() 7 { 8 freopen("input.txt","r",stdin); 9 freopen("output.txt","w",stdout); 10 int n,k; 11 while(cin>>n>>k) 12 { 13 if(n<=k) cout<<2<<endl; 14 else{ 15 if((n*2)%k==0) 16 cout<<n*2/k<<endl; 17 else cout<<(n*2/k)+1<<endl;} 18 } 19 return 0; 20 } View Code

?

B題

還沒有看懂題意

C題

?

思路：從上面圖片可以看出來，如果W是奇數時，w=1的部分會被單獨列出來，然后從2--W每兩個進行計數，最后兩行被單獨計算。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 struct node 7 { 8 int x; 9 int y; 10 } a[250000]; 11 int cmp(const node &a,const node &b) 12 { 13 if(a.x!=b.x) 14 return a.x<b.x; 15 else 16 return a.y<b.y; 17 } 18 int main() 19 { 20 int n,m; 21 freopen("input.txt","r",stdin); 22 freopen("output.txt","w",stdout); 23 while(~scanf("%d%d",&n,&m)) 24 { 25 if(m==1||n==1) 26 { 27 printf("0\n"); 28 continue; 29 } 30 if(m==2||n==2) 31 { 32 if(m==2) 33 { 34 printf("%d\n",n-1); 35 for(int i=1; i<n; i++) 36 printf("%d %d\n",i,1); 37 } 38 else 39 { 40 printf("%d\n",m-1); 41 for(int i=1; i<m; i++) 42 printf("%d %d\n",1,i); 43 } 44 continue; 45 } 46 int k=0; 47 if(m%2==1) 48 { 49 for(int i=1; i<n; i+=2) 50 { 51 a[k].x=i; 52 a[k].y=1; 53 k++; 54 } 55 } 56 for(int i=1; i<=n-2; i++) 57 { 58 for(int j=m%2+1; j<=m; j+=2) 59 { 60 a[k].x=i; 61 a[k++].y=j; 62 } 63 } 64 for(int j=m%2+1; j<=m-1; j++) 65 { 66 a[k].x=n-1; 67 a[k++].y=j; 68 } 69 sort(a,a+k,cmp); 70 printf("%d\n",k); 71 for(int i=0; i<k; i++) 72 printf("%d %d\n",a[i].x,a[i].y); 73 } 74 return 0; 75 } View Code

D題

思路：計算字符串中包含多少個（NE、NW、SE、SW）賦值給k，結果是(2^k)%(10^9+7),因為k比較小，所以直接計算或者用快速冪都是可以的。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <map> 7 using namespace std; 8 const int maxn=100005; 9 const int inf=1000000007; 10 char s[maxn]; 11 int main() 12 { 13 freopen("input.txt","r",stdin); 14 freopen("output.txt","w",stdout); 15 //printf("%d\n",inf); 16 while(~scanf("%s",s)) 17 { 18 int len=strlen(s); 19 int k=0; 20 for(int i=0;i<len;i++) 21 { 22 if(s[i]=='N'&&i<len-1) 23 { 24 if(s[i+1]=='W'||s[i+1]=='E') 25 { 26 k++; 27 } 28 } 29 if(s[i]=='S'&&i<len-1) 30 { 31 if(s[i+1]=='W'||s[i+1]=='E') 32 { 33 k++; 34 } 35 } 36 } 37 long long ans=1,tmp=2; 38 while(k) 39 { 40 if(k&1) 41 ans=((ans*tmp)%inf+inf)%inf; 42 tmp=(tmp*tmp)%inf; 43 k=k/2; 44 } 45 printf("%lld\n",ans); 46 } 47 return 0; 48 } View Code

?

E題

思路：判斷當除了最大值之外其他都拿一個蛋糕cet1，和所有人都拿最多的蛋糕時cet2，剛好計算到i=t-1時是否滿足cet1<=k<=cet2,是的話打印YES，否則打印NO

1 #include <iostream> 2 #include<cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 7 using namespace std; 8 int a[100005]; 9 long long ans1,ans2; 10 int solve(int n,int k,int t) 11 { 12 long long tmp1,tmp2,cnt1,cnt2,cet1,cet2; 13 if(k>=t&&k<=ans2) return 1; 14 tmp1=t; 15 tmp2=ans2; 16 cnt1=n+a[t]-1; 17 cnt2=ans1; 18 for(int i=1;; i++) 19 { 20 cet1=tmp1+cnt1*i; 21 cet2=tmp2+cnt2*i; 22 if(cet1<=k&&k<=cet2) 23 return 1; 24 if(cet1>k) 25 break; 26 } 27 return 0; 28 29 } 30 int main() 31 { 32 freopen("input.txt","r",stdin); 33 freopen("output.txt","w",stdout); 34 int n,k; 35 while(~scanf("%d%d",&n,&k)) 36 { 37 for(int i=0; i<n; i++) 38 { 39 scanf("%d",&a[i]); 40 ans1+=a[i]; 41 } 42 int t=max_element(a,a+n)-a; 43 for(int i=0; i<t; i++) 44 ans2+=a[i]; 45 if(solve(n,k,t)) printf("YES\n"); 46 else printf("KEK\n"); 47 } 48 return 0; 49 } View Code

?

F題

思路：先使用并查集對于‘=’的x，y進行預處理，然后對‘<'和’>'所對應的集合進行處理，然后依據大小填入對應的RBW，最后對于未填入RBW的位置進化判斷，如果無法判斷填入？

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=1005; 7 int x[maxn*maxn],y[maxn*maxn],dp[maxn][maxn],flag[maxn],out[maxn],in[maxn]; 8 char ch[maxn],s[maxn*maxn]; 9 int find(int x) 10 { 11 if(flag[x]==x) 12 return x; 13 else 14 return find(flag[x]); 15 } 16 int init(int a,int b) 17 { 18 a=find(a); 19 b=find(b); 20 flag[a]=b; 21 return 0; 22 } 23 int main() 24 { 25 freopen("input.txt","r",stdin); 26 freopen("output.txt","w",stdout); 27 int n,m; 28 while(~scanf("%d%d",&n,&m)) 29 { 30 memset(dp,0,sizeof(dp)); 31 memset(in,0,sizeof(in)); 32 memset(out,0,sizeof(out)); 33 memset(ch,0,sizeof(ch)); 34 for(int i=0;i<=n;i++) 35 flag[i]=i; 36 for(int i=1;i<=m;i++) 37 { 38 scanf("%d%c%d",&x[i],&s[i],&y[i]); 39 } 40 for(int i=1;i<=m;i++) 41 if(s[i]=='=') 42 init(x[i],y[i]); 43 for(int i=1;i<=m;i++) 44 { 45 if(s[i]=='<') 46 { 47 int yy=find(y[i]); 48 int xx=find(x[i]); 49 dp[yy][xx]=1; 50 out[yy]++; 51 in[xx]++; 52 } 53 else if(s[i]=='>') 54 { 55 int yy=find(y[i]); 56 int xx=find(x[i]); 57 dp[xx][yy]=1; 58 out[xx]++; 59 in[yy]++; 60 } 61 } 62 for(int i=1;i<=n;i++) 63 { 64 if(out[i]!=0&&in[i]!=0) 65 { 66 ch[i]='R'; 67 for(int j=1;j<=n;j++) 68 { 69 if(dp[i][j]==1) 70 { 71 int p=find(j); 72 ch[p]='B'; 73 } 74 if(dp[j][i]==1) 75 { 76 int p=find(j); 77 ch[p]='W'; 78 } 79 } 80 } 81 } 82 for(int i=1;i<=n;i++) 83 { 84 int p=find(i); 85 if(ch[p]!=0) 86 ch[i]=ch[p]; 87 else 88 ch[i]='?'; 89 } 90 for(int i=1;i<=n;i++) 91 printf("%c",ch[i]); 92 printf("\n"); 93 } 94 return 0; 95 } View Code

G題

思路：先使用素數篩找出（10467397/6)中的素數，然后從1--m（素數的最大個數）找出n的3個因子

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <map> 7 using namespace std; 8 const int maxn=10467397/6; 9 int prime[maxn]; 10 bool isprime[maxn]; 11 int sieve(int n) 12 { 13 int p=0; 14 for(int i=0;i<=n;i++) isprime[i]=true; 15 isprime[0]=isprime[1]=false; 16 for(int i=2;i<=n;i++) 17 { 18 if(isprime[i]) 19 { 20 prime[p++]=i; 21 for(int j=2*i;j<=n;j+=i) isprime[j]=false; 22 } 23 } 24 return p; 25 } 26 int main() 27 { 28 int ans=sieve(maxn); 29 int n; 30 freopen("input.txt","r",stdin); 31 freopen("output.txt","w",stdout); 32 //printf("%d\n",prime[131212]); 33 while(~scanf("%d",&n)) 34 { 35 int k=0; 36 for(int i=0;prime[i]<=n&&i<131212;i++) 37 { 38 if(n%prime[i]==0) 39 { 40 n=n/prime[i]; 41 k++; 42 } 43 if(k==3&&n==1) 44 break; 45 if(k>3) 46 break; 47 } 48 if(k==3&&n==1) 49 printf("YES\n"); 50 else 51 printf("NO\n"); 52 } 53 return 0; 54 } View Code

?

H題

思路：當n<10時，a[i]=a[i-1]*10-a[i-1],當n>=10時就打印a[9]再在后面補（n-9）個0

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int main() 7 { 8 freopen("input.txt","r",stdin); 9 freopen("output.txt","w",stdout); 10 11 int n; 12 long long ans; 13 while(cin>>n) 14 { 15 if(n<=9) 16 { 17 ans=1; 18 for(int i=1;i<n;i++) 19 ans=ans*9; 20 ans=ans*8; 21 cout<<ans<<endl; 22 } 23 else 24 { 25 cout<<344373768; 26 for(int i=10;i<=n;i++) cout<<0; 27 cout<<endl; 28 } 29 } 30 return 0; 31 } View Code

?

I題

思路：因為只有一條線進行分割，所以只有三種可能（n+2=m+k? n+3=m+k? n+4=m+k),分別意味著兩點連成一條線、一點和線上一點連成一條線、兩條線段之間連一條線。

J題

思路：首先把和相同的 i 和 j 存入二維數組中，然后不斷地進行判斷在滿足之前的條件下是否仍然有 i 和 j 能夠相連，如果有的話就進行再次儲存

1 #include <iostream> 2 #include<cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 7 using namespace std; 8 int n,m; 9 int a[2][105],b[2][105],x[105],y[105]; 10 int dp[105][105],vis[105],cnt[105]; 11 int cont(int x) 12 { 13 return x%10+(x/10)%10+x/100; 14 } 15 int dfs(int x) 16 { 17 for(int i=0; i<m; i++) 18 { 19 if(!vis[i]&&dp[x][i]) 20 { 21 vis[i]=1; 22 if(cnt[i]==-1||dfs(cnt[i])) 23 { 24 cnt[i]=x; 25 return 1; 26 } 27 } 28 } 29 return 0; 30 } 31 int solve() 32 { 33 int ans=0; 34 memset(cnt,-1,sizeof(cnt)); 35 for(int i=0; i<n; i++) 36 { 37 memset(vis,0,sizeof(vis)); 38 if(dfs(i)) 39 ans++; 40 } 41 return ans; 42 } 43 int main() 44 { 45 freopen("input.txt","r",stdin); 46 freopen("output.txt","w",stdout); 47 while(~scanf("%d%d",&n,&m)) 48 { 49 for(int i=0; i<n; i++) 50 { 51 scanf("%d",&x[i]); 52 a[0][i]=cont(x[i]/1000); 53 a[1][i]=cont(x[i]%1000); 54 } 55 for(int i=0; i<m; i++) 56 { 57 scanf("%d",&y[i]); 58 b[0][i]=cont(y[i]/1000); 59 b[1][i]=cont(y[i]%1000); 60 } 61 memset(dp,0,sizeof(dp)); 62 for(int i=0; i<n; i++) 63 { 64 for(int j=0; j<m; j++) 65 if(a[0][i]==b[1][j]||a[1][i]==b[0][j]) 66 dp[i][j]=1; 67 } 68 printf("%d\n",solve()); 69 for(int i=0;i<m;i++) 70 { 71 int next=cnt[i]; 72 if(next!=-1) 73 { 74 if(a[0][next]==b[1][i]) 75 printf("AT %d %d\n",x[next],y[i]); 76 else if(a[1][next]==b[0][i]) 77 printf("TA %d %d\n",y[i],x[next]); 78 } 79 80 } 81 82 } 83 return 0; 84 } View Code

K題

沒有給出的題目是我還沒有還沒有寫，以后再補上.

?

轉載于:https://www.cnblogs.com/wang-ya-wei/p/6535964.html

總結

以上是生活随笔為你收集整理的3.9的全部內容，希望文章能夠幫你解決所遇到的問題。

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