Codeforces Round #549 (Div. 2)

A. The Doors

题意数列中 0 和1 哪个最先没有输出位置

思路：模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 250007;
 4 typedef long long ll;
 5 const int mod=1e9+7;
 6 int a[maxn];
 7 #define  pb push_back
 8 int main(){
 9     int n;
10     scanf("%d",&n);
11     int z1=1,z2=1;
12     int tmp;
13     for(int i=1;i<=n;i++){
14         scanf("%d",&tmp);
15         if(tmp==0)z1=max(z1,i);
16         if(tmp==1)z2=max(z2,i);
17     }
18     cout<<min(z1,z2)<<endl;
19 
20     return 0;
21 }

View Code

B. Nirvana

题意：1---n 中取一个数每个数字乘起来得最大值是多少

思路：从个位把每位取9 暴力即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 250007;
 4 typedef long long ll;
 5 const int mod=1e9+7;
 6 int a[50];
 7 int b[50];
 8     int flag=0;
 9     ll ans=0;
10 void solve(int x){
11 
12     if(x==0)return ;
13     if(a[x]!=9&&a[x]>=0){
14         a[x]=9;
15         a[x-1]--;
16     }
17     else {
18         if(a[x]<0)a[x]+=10,a[x-1]--;
19     }
20     ll tmp=1;
21     for(int i=0;i<flag;i++)
22     {
23         if(a[i]!=0)tmp*=a[i];
24     }
25     ans=max(tmp,ans);
26     solve(x-1);
27 }
28 int main(){
29     ll n;
30     scanf("%lld",&n);
31     while(n){
32         a[flag++]=n%10;
33         n/=10;
34     }
35     for(int i=0;i<flag/2;i++){
36         int tmp=a[i];
37         a[i]=a[flag-i-1];
38         a[flag-i-1]=tmp;
39     }
40     ans=1;
41     for(int i=0;i<flag;i++)ans*=a[i];
42     solve(flag-1);
43     cout<<ans<<endl;
44         
45     return 0;
46 }

View Code

C. Queen

题意：给出一个树有多少个标记点的所以子节点是标记了的父节点也是标记的从小到大输出

思路：直接dfs即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 250007;
 4 typedef long long ll;
 5 struct Node{
 6     int to,next;
 7 }edge[maxn];
 8 int p[maxn],c[maxn];
 9 int head[maxn];
10 int size=0;
11 void add(int x,int y){
12     edge[size].next=head[x];
13     edge[size].to=y;
14     head[x]=size++;
15 }
16 set<int>s;
17 void dfs(int x,int flag){
18     int ok=1;
19     for(int i=head[x];i!=-1;i=edge[i].next){
20         int y=edge[i].to;
21         if(c[y]==0)ok=0;
22         dfs(y,c[y]);
23     }
24     if(ok&&flag)s.insert(x);
25 
26 }
27 int main(){
28     int n;
29     memset(head,-1,sizeof(head));
30     scanf("%d",&n);
31     int root;
32     for(int i=1;i<=n;i++){
33         scanf("%d%d",&p[i],&c[i]);
34         if(p[i]==-1)root=i;
35         else {
36             add(p[i],i);
37         }
38     }
39 //    cout<<root<<endl;
40     dfs(root,0);
41 if(s.empty()){
42     cout<<-1;
43     return 0;
44 }
45     for(auto&p:s){
46         cout<<p<<" ";
47     }
48 
49 
50 return 0;
51 }

View Code

D. The Beatles

题意：一共有n*k个点从第一个点开始每k个点是一个餐厅每次从s点出发每次走l步最后回到l的时候停止

并且给出出发点s离最近餐厅距离 a走了第一个l步后离餐厅最近的距离b 问最少和最多分别要多少步才能回到s

思路：走多少步为 n*k/gcd(n*k,l) l 分别四种情况例如在刚好相邻的第一个起点区间里面 1---2 a可以在 1的左右 2也一样

即 a-----1------a-----b----2---b 所以l有四种情况 l=k-(a+b) l=k-(a-b) l=k-(b-a) l=k-(-a-b) 然后再加上区间差 xk 暴力区间差即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 250007;
 4 typedef long long ll;
 5 set<int>s1,s2;
 6 int main(){
 7     int n,k;
 8     scanf("%d%d",&n,&k);
 9     int a,b;
10     ll x=1ll*n*k,y=0;
11     scanf("%d%d",&a,&b);
12     for(ll i=1;i<=n;i++){
13         x=min(x,1ll*n*k/__gcd(1ll*n*k,a+b+i*k));
14         x=min(x,1ll*n*k/__gcd(1ll*n*k,a-b+i*k));
15         x=min(x,1ll*n*k/__gcd(1ll*n*k,-a-b+i*k));
16         x=min(x,1ll*n*k/__gcd(1ll*n*k,-a+b+i*k));
17         y=max(y,1ll*n*k/__gcd(1ll*n*k,a+b+i*k));
18         y=max(y,1ll*n*k/__gcd(1ll*n*k,a-b+i*k));
19         y=max(y,1ll*n*k/__gcd(1ll*n*k,-a+b+i*k));
20         y=max(y,1ll*n*k/__gcd(1ll*n*k,-a-b+i*k));
21     }
22     cout<<x<<" "<<y<<endl;
23     return 0;
24 }