Codeforces Round #479
一月 28, 2020
Codeforces 977 C Less or Equal
题意
找到一个数 \(x\) 满足数列中恰好有 \(k\) 个数小于等于 \(x\) 。
分析
显然，只需要排序以后判断第 \(k\) 个数与第 \(k+1\) 个数是否相等即可。
- 如果相等，显然不存在这样的 \(x\)；
- 如果不想等，显然输出 \(x\) 就是满足要求的答案。
需要注意特别处理 \(k=0\) 和 \(k=n\) 的情况（无法比较第 \(k\) 个数与第 \(k+1\) 个数）。
特别地，当 \(k=0\) 的时候
- 如果最小的数是 \(1\) ，由于要求 \(x\) 必须在 \([1,10^9]\) 范围内，则不存在这样的 \(x\) ，输出 \(-1\) ；
- 否则输出最小的数 \(-1\) 即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<bits/stdc++.h> using namespace std; #define LL long long int n,k,a[200010]; int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); if (k==n) printf("%d\n",a[k]); else if (k==0) { if (a[1]==1) puts("-1"); else printf("%d\n",a[1]-1); } else if (a[k]==a[k+1]) puts("-1"); else printf("%d\n",a[k]); return 0; } |
Codeforces 977 D Divide by three, multiply by two
题意
一个数 \(x\) 有两种变化方式：
- 如果 \(x\) 是 \(3\) 的倍数，变成 \(x/3\) ；
- 变成 \(2x\)
给出一个数列，将这个数列重组，满足上述的变化方式。
分析
将每个数看作一个点，满足变化方式的点之间连有向边。
以每一个点作为根跑一遍 dfs ，求出任意一条长度为 \(n\) 的链就是答案。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<bits/stdc++.h> using namespace std; #define LL long long int n,d[200]; LL a[200]; vector<int> e[200]; void dfs(int x) { for (auto y:e[x]) if (d[y]==0) { d[y]=d[x]+1; dfs(y); } } bool check() { for (int i=1;i<=n;i++) if (d[i]==n) return true; return false; } void print(int x) { for (int i=1;i<=n;i++) if (d[i]==x) printf("%lld",a[i]); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (a[i]==a[j]/2&&a[j]%2==0) e[i].push_back(j); if (a[i]==a[j]/3&&a[j]%3==0) e[j].push_back(i); } for (int i=1;i<=n;i++) { memset(d,0,sizeof(d)); d[i]=1;dfs(i); if (check()) { for (int j=1;j<n;j++) print(j),putchar(' '); print(n),puts(""); } } return 0; } |
Codeforces 977 E Cyclic Components
题意
询问图中有多少联通块是一个简单环。
分析
对于一个联通块，如果他是一个简单环，当且仅当每一个点的度数都为 \(2\) 。
于是我们用 dfs 将每一个联通块标记出来，计算每一个联通块的最小度数和最大度数。
如果一个联通块满足最小度数 \(=\) 最大度数 \(=2\) ，那么这个联通块就是一个简单环，统计这样的数量即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> using namespace std; #define LL long long int n,m,v[200010],d[200010],Min[200010],Max[200010]; vector<int> e[200010]; bool check(int x) { for (int i=1;i<=n;i++) if (v[i]==x&&d[i]!=2) return false; return true; } void dfs(int x,int c) { v[x]=c; for (auto y:e[x]) if (!v[y]) dfs(y,c); } int main() { scanf("%d%d",&n,&m); int x,y; for (int i=1;i<=m;i++) scanf("%d%d",&x,&y), e[x].push_back(y), e[y].push_back(x), d[x]++,d[y]++; int ans=0; for (int i=1;i<=n;i++) if (!v[i]) dfs(i,i),Min[i]=d[i],Max[i]=d[i]; for (int i=1;i<=n;i++) Min[v[i]]=min(Min[v[i]],d[i]), Max[v[i]]=max(Max[v[i]],d[i]); for (int i=1;i<=n;i++) if (Min[i]==2&&Max[i]==2) ans++; printf("%d\n",ans); return 0; } |
Codeforces 977 F Consecutive Subsequence
题意
求数列中最长的连续子序列。
分析
显然，对于一个数 \(x\) 之前如果存在若干个 \(x-1\) ，我们一定会从最靠后的 \(x-1\) 转移过来，因为相对来说，越靠后，最长的连续子序列可能越长。
于是我们只需要知道，每一个数最后出现的位置进行转移。
因为数范围是 \([1,10^9]\) ，我们用 map 辅助转移即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> using namespace std; #define LL long long int n,a[200010],f[200010],pre[200010]; map<int,int> m; void print(int x) { if (x==0) return ; print(pre[x]); printf("%d ",x); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { if (m.find(a[i]-1)!=m.end()) { int x=m[a[i]-1]; f[i]=f[x]+1; pre[i]=x; } else { f[i]=1; pre[i]=0; } m[a[i]]=i; } int Max=1,ans=1; for (int i=2;i<=n;i++) if (f[i]>Max) Max=f[i],ans=i; printf("%d\n",f[ans]); print(ans); return 0; } |
