首页 > 代码库 > 3.9

3.9

2024-09-08 03:57:27   216人阅读

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题

没有给出的题目是我还没有还没有写，以后再补上.

 

3.9


联系
我们