题目链接：https://codeforces.com/contest/1249/problem/A
A. Yet Another Dividing into Teams
题意：n个学生，分成任意组，要求每组中任意两名学生的技能值相差不等于1，问最小分组。
思路：易得答案非 1 即 2 ，排序完for一遍判断相邻差值等于 1 是否存在即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e5 +50;
4 int a[maxn];
5 int main()
6 {
7 std::ios::sync_with_stdio(false);
8 int t;
9 cin >> t;
10 while(t--)
11 {
12 int n;
13 cin >> n;
14 for(int i = 0;i < n;i++)
15 {
16 cin >> a[i];
17 }
18 sort(a, a + n);
19 bool flag = false;
20 for(int i = 1;i < n;i++)
21 {
22 if(a[i] - a[i - 1] == 1)
23 {
24 flag = true;
25 break;
26 }
27 }
28 if(flag) cout << 2 << endl;
29 else cout << 1 << endl;
30 }
31 return 0;
32 }
View Code
B2. Books Exchange (hard version)
题意：n个学生，每个学生有单独的一本书，每天学生 i 会把 书给 ai，问每个学生重新拿到自己的书经过的天数。
思路：对于每个学生 i , dfs一遍找到回到自身需要的天数，容易发现对于同一个环内的学生，他们拿到书的天数是相同的，所以可以在dfs返回是直接求出答案，复杂度可以降到O（n）;
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 5e5 +50;
4 int f[maxn];
5 int ans[maxn];
6 int flag;
7 int vis[maxn];
8 int cnt;
9 void dfs(int x,int k)
10 {
11 // cout << f[x] << " cnt =" << cnt << endl;
12 if(f[x] == k)
13 {
14 cnt++;
15 ans[x] = cnt;
16 return;
17 }
18 else cnt++,dfs(f[x], k);
19 vis[x] = 1;
20 ans[x] = cnt;
21 }
22 int main()
23 {
24 std::ios::sync_with_stdio(false);
25 int t;
26 cin >> t;
27 while(t--)
28 {
29 int n;
30 cin >> n;
31 fill(vis,vis + n + 50,0);
32 for(int i = 1;i <= n;i++)
33 {
34 cin >> f[i];
35 }
36 for(int i = 1;i <= n;i++)
37 {
38 if(!vis[i])
39 {
40 flag = 0;
41 cnt = 0;
42 dfs(i, i);
43 }
44 }
45 for(int i = 1;i <= n;i++)
46 {
47 cout << ans[i] << " ";
48 }
49 cout << endl;
50 }
51 return 0;
52 }
View Code
C2. Good Numbers (hard version)
题意：求大于n的m，m有不同的3的次幂。
思路：先把 n 内所以3的不同次幂减去，保存在一个ans里面，然后从小到大找一个找出没使用过的3的次幂，使它大于n，加入答案。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 100;
5 ll a[maxn];
6 int vis[100];
7 int main()
8 {
9 std::ios::sync_with_stdio(false);
10 int t;
11 a[0] = 1LL;
12 for(int i = 1;i <= 38; i++)a[i] = a[i - 1] * 3LL;
13 cin >> t;
14 while(t--)
15 {
16 ll n;
17 cin >> n;
18 ll ans = 0;
19 for(int i = 0;i <= 38;i++)vis[i] = 0;
20 for(int i = 38;i >= 0;i--)
21 {
22 if(n > a[i])
23 {
24 n -= a[i];
25 ans += a[i];
26 vis[i] = 1;
27 }
28 }
29 for(int i = 0;i <= 38;i++)
30 {
31 if(vis[i]){
32 ans -= a[i];
33 }
34 else{
35 ans += a[i];
36 break;
37 }
38 }
39 cout << ans << endl;
40 }
41 return 0;
42 }
View Code
D2. Too Many Segments (hard version)
思路：将所有线段用set维护，然后从小到大枚举端点，将左端点覆盖到这个点的线段加入set中，当线段的数量大于k，移出r最大的线段，最后将右端点等于这个点的线段全部移出；
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef pair<int ,int > pii;
4 const int maxn = 2e5+ 5;
5 vector<pii> a[maxn];
6 int main()
7 {
8 std::ios::sync_with_stdio(false);
9 int n, k;
10 cin >> n >> k;
11 for(int i = 1;i <= n;i++)
12 {
13 int l, r;
14 cin >> l >> r;
15 a[l].push_back({r,i});
16 }
17 set<pii> st;
18 vector<int> ans;
19 for(int i = 0;i < maxn;i++)
20 {
21 for(int j = 0;j < a[i].size();j++) st.insert(a[i][j]);
22 while(st.size() > k)
23 {
24 ans.push_back(st.rbegin() -> second);
25 st.erase(--st.end());
26 }
27 while(!st.empty() && st.begin()->first == i) st.erase(st.begin());
28 }
29 printf("%d\n", ans.size());
30 for(int i=0;i<ans.size();i++) printf("%d ", ans[i]);
31 return 0;
32 }
View Code
E. By Elevator or Stairs?
思路：设F[i][0]是在第i层在楼梯里的最小值，F[i][1]表示第i层在电梯里的最小值，初始f[0][0] = 0；电梯不可到达f[0][1]= INF，按题目DP一下；
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5 + 50;
5 int f[maxn][2];//1是在电梯里，0是在楼梯里；
6 int a[maxn], b[maxn];
7 int main()
8 {
9 std::ios::sync_with_stdio(false);
10 int n, c;
11 cin >> n >> c;
12 n--;
13 for(int i = 1;i <= n;i++) cin >> a[i];
14 for(int i = 1;i <= n;i++) cin >> b[i];
15 f[0][1] = 1e9;
16 for(int i = 1;i <= n;i++){
17 f[i][0] = min(f[i - 1][0], f[i - 1][1]) + a[i];
18 f[i][1] = min(f[i - 1][0] + c, f[i - 1][1] ) + b[i];
19 }
20 cout << "0 ";
21 for(int i = 1;i <= n;i++)
22 cout << min(f[i][0],f[i][1]) << " ";
23 cout << endl;
24 return 0;
25 }
View Code