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 }
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 }
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 }
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 }
以我的经历，我的带教有十几年工作经验，做过运维、后端开发、web测试，现在是高级软测，是行走的避坑指南