菜鸡的$div2$补题现场……
A:Dreamoon and Ranking Collection
1.题目描述:
给你一个$n$和$x$,然后有$n$个数据,这个人从$1$开始比赛,$n$组数据包含着这个人进行的比赛,未进行的比赛可以用$x$补全,但$x$也要相应$-1$
问:他能够到达的最大比赛次数是多少?
input:
1 2 3 4 5 6 7 8 9 10 11
| 5 6 2 3 1 1 5 7 10 1 100 100 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 57 80 60 40 20
|
output:
2.思路
我们可以从$1$开始往后扫一边,对应的$ans += 1$,如果这个地方是空,我们给他填上,并且$x$相应$-1$,直到$x == 0$,看此时的$ans$就是我们可以得到的最大的比赛值。
这里存储的是每一场比赛对应的值,我们可以用一个$map$来存储。
注意:
- 变量全局定义,记得初始化。
- $for$循环的判断条件
- $map$的清空[不然多组样例会wa掉]
3.代码:
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
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f using namespace std; const int maxn = 100 + 5; int t, n, x, temp,cnt; int main() { IOS cin >> t; while(t--) { n = x = temp = cnt = 0; map<int, int>mp; cin >> n >> x; for(int i = 1; i <= n; i++) { cin >> temp; mp[temp] = 1; }
for(int i = 1; ; i++) { if(x == 0) { break; } if(mp[i] == 0) { x -= 1; mp[i] = 1; } }
for(int i = 1; mp[i] != 0; i++) { cnt++; } cout << cnt << endl; } return 0; }
|
B:Dreamoon Likes Permutations
1.题目描述
定义一个$permutation$,如果对于一个序列,包含了从$1$到$n$的每一项,则该序列称为$permutation$.
有两个符合$permutation$的序列$p1, p2$, 长度分别为$l1, l2$。现在连接成为一个长度为$l1 + l2$的序列$a$,第一个$l1$元素是$p1$, 下一个$l2$元素是$p2$.
现在给你一个序列$a$,让你找两个符合$permutation$的序列$p1, p2$,找到还原它们的所有方法。
输出存在的方法并输出$p1$ 和 $p2$的长度.
input:
1 2 3 4 5 6 7 8 9 10 11 12 13
| 6 5 1 4 3 2 1 6 2 4 1 3 2 1 4 2 1 1 3 4 1 3 3 1 12 2 1 3 4 5 6 7 8 9 1 10 2 3 1 1 1
|
output:
1 2 3 4 5 6 7 8 9 10
| 2 1 4 4 1 1 4 2 0 0 1 2 10 0
|
2.思路:
u1s1,一开始看到题意有点懵,读了两遍题,才大致了解了一下。
我们可以想一下,对于一个序列,如果它是符合$permutation$这个条件的,则其最大值我们设定是$ma$,如果$a$序列可以分割,则其最大值为$max(len1, len2)$
所以会有两种解决方案:
- $len1 = ma, len2 = n - ma$
- $len1 = n - ma, len2 = ma$
我们只需要检查这两种分割方式是否符合$permutation$即可。
我们可以用一个标记数组$vis$来判断该序列从$1$到$len1$是否全部出现即可。
注意 :序列两部分的断点 ,不要去考虑原数组,只需要考虑$vis$是否符合$permutation$即可。
提供一组样例:【需要特判!!!】
input:
output:
3.代码:
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std; const int maxn = 200000 + 5; int t, n; int a[maxn], vis[maxn], ans[maxn][2]; bool check(int l1, int l2) { for(int i = 1; i <= n; i++) { vis[i] = 0; } for(int i = 1; i <= l1; i++) { vis[a[i]] = 1; } for(int i = 1; i <= l1; i++) { if(vis[i] == 0) { return 0; } } for(int i = 1; i <= n; i++) { vis[i] = 0; } for(int i = l1 + 1; i <= n; i++) { vis[a[i]] = 1; } for(int i = 1; i <= l2; i++) { if(vis[i] == 0) { return 0; } } return 1; } int main() { IOS cin >> t; while(t--) { int ma = -1; memset(a, 0, sizeof(a)); memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; ma = max(ma, a[i]); } int cnt = 0; if(check(ma, n - ma)) { cnt++; ans[cnt][0] = ma; ans[cnt][1] = n - ma; } if(ma * 2 != n && check(n - ma, ma)) { cnt++; ans[cnt][0] = n - ma; ans[cnt][1] = ma; } cout << cnt << endl; for(int i = 1; i <= cnt; i++) { cout << ans[i][0] << " " << ans[i][1] << endl; } } system("pause"); return 0; }
|
C. Dreamoon Likes Coloring
1.题目描述
给你一个长度为$n$的长条单元格让你涂色,可以进行$m$次涂色操作,分别给定$l_1, l_2, \ldots, l_m$。
对第$i$次操作,你可以选择一个$p_i$在$[1, n - l_i + 1]$ 范围内,并对$p_i$到$p_i + l_i -1$所有的单元格进行涂色。后来涂色的单元格颜色可以覆盖之前进行的涂色。
你的任务:在$m$次操作后:
- 所有的颜色出现一次
- 并所有单元格都有颜色。[即有m种颜色…..]
input:
1 2 3 4 5 6
| first: 5 3 3 2 2 second: 10 1 1
|
output:
2.思路:
乱搞图片…
[规范解答]【感觉有点难以理解】靠……
我们首先考虑可能输出$-1$的情况,类似这种题目,我们先寻找可能不满足的条件,再寻找解决方案。
- 设$m$次涂色的单元格长度之和$sum$ ,当$sum < n$时,显然不满足第二种条件,不能涂满整个单元格长条。
- 对任意$i$,要满足$l_i + i - 1 > n$,即如果$n - l_i < i - 1$,那么我们进行完$i$次操作后,只有$n - l_i$个单元格没有被第$i$中颜色着色。所以进行完之后,至少$i - 1$种以前的颜色会消失。
我们要找到的就是涂色的位置$pos$。
[贪心做法]
我们与上边的第一种条件一样,先加起来,如果$sum < n$那么一定不成立。
然后我们采取一种贪心方式来涂,保证从第一次涂开始,操作尽可能小比并且涂满。
然后我们每一种颜色的长度缩小,这取决于$sum$的大小,然后更新$pos$和$sum$.
当$l_i+pos-1>n$时,如果我们从$pos$开始涂色,那么颜色的末尾就会超过$n$,所以我们必须在$pos$之前涂色。
但我们前边的操作保证是最小解,所以该操作会覆盖掉前边的方案,不成立。
3.代码:
[做法1]
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
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std; const int maxn = 100000 + 5; int n, m; int a[maxn]; ll p[maxn]; int main() { IOS cin >> n >> m; for(int i = 1; i <= m; i++) { cin >> a[i]; if(a[i] + i - 1 > n) { puts("-1"); return 0; } } for(int i = m; i > 0; i--) { p[i] = p[i + 1] + a[i]; } if(p[1] < n) { puts("-1"); return 0; } for(int i = 1; i <= m; i++) { printf("%lld", max((ll)i, n - p[i] + 1)); if(i < m) { putchar(' '); } else { puts(""); } } return 0; }
|
[做法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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
#include <bits/stdc++.h> #define IOS {ios::sync_with_stdio(false);cin.tie(0);} #define ll long long #define INF 0x3f3f3f3f
using namespace std; const int maxn = 100000 + 5; int n, m, pos; ll sum; int a[maxn], ans[maxn]; bool flag; int main() { IOS cin >> n >> m; for(int i = 1; i <= m; i++) { cin >> a[i]; sum += a[i]; } if(sum < n) { cout << "-1" << endl; return 0; } pos = 1; sum -= n; flag = false; for(int i = 1; i <= m; i++) { if(a[i] + pos - 1 > n) { flag = 1; break; } if(sum >= a[i]) { sum -= a[i] - 1; a[i] = 1; } else { a[i] -= sum; sum = 0; } ans[i] = pos; pos += a[i]; } if(flag) { cout << "-1" << endl; } else { for(int i = 1; i < m; i++) { cout << ans[i] << " "; } cout << ans[m] << endl; } return 0; }
|