链接：https://ac.nowcoder.com/acm/contest/9983
来源：牛客网
开学后才补的题解……寒假时懒得补，做专题/玩去了……
D - Happy New Year!（签到）
题目描述
还有一个周就要过年啦！这一天牛牛盯着新的台历出神，他突然想知道对于第$n$年来说，大于$n$且与$n$的数位和相同的最小年份是多少。
一个数字的数位和等于他各数位上的数字之和，例如2021\text 20212021的数位和等于$2+0+2+1=5$。
输入描述:
1
2
| 一个正整数n。
2021 <= n <= 2030.
|
输出描述:
示例1
输入
复制;)
输出
复制;)
说明
1
| 2034是比2025大的且数位和等于9的最小正整数
|
分析
我直接签到AC
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
if(n == 2021) cout << 2030;
if(n == 2022) cout << 2031;
if(n == 2023) cout << 2032;
if(n == 2024) cout << 2033;
if(n == 2025) cout << 2034;
if(n == 2026) cout << 2035;
if(n == 2027) cout << 2036;
if(n == 2028) cout << 2037;
if(n == 2029) cout << 2038;
if(n == 2030) cout << 2102;
return 0;
}
|
E - 买礼物（线段树+链表+思维）
题目描述
在卖礼物的超市中有$\mathit n$个柜子，每个柜子里都摆放了一个礼物，每个礼物有自己的一个编号，第$i$个柜子里的礼物编号为$a_i$。
茶山牛想给牛牛和牛妹买相同编号的礼物，但礼物有可能在某个时刻被其他人买走，而且柜子数量太多，因此茶山牛在某个时刻只想知道某一个柜子区间是否能买到两件相同编号的礼物。
具体来说，有$q$次操作，格式如下：
$ 1\space x$，第$x$个柜子里的礼物被买走，保证此时这个柜子里的礼物还在。
$2\ l\ r$，茶山牛询问第$l$到第$r$个柜子未被买走的礼物中是否有两个礼物编号相同。
输入描述:
1
2
3
4
5
6
| 第一行以空格分隔的两个正整数n,q\mathit n,qn,q。
接下来一行以空格分隔的n\mathit nn个正整数aia_{i}ai。
接下来q\mathit qq行每行一个操作。
1≤n,q≤5×1051\leq n,q \leq 5×10^{5}1≤n,q≤5×105
1≤ai≤1061\leq a_{i} \leq 10^{6}1≤ai≤106
1≤x,l≤r≤n1\leq x,l \leq r \leq n1≤x,l≤r≤n
|
输出描述:
1
| 对每次茶山牛的询问输出一行一个整数，如果在指定的区间内有两个礼物编号相同则输出1，否则输出0。
|
示例1
输入
复制;)
1
2
3
4
5
6
7
| 5 5
1 2 1 2 1
2 2 4
2 2 5
1 2
2 2 4
2 2 5
|
输出
复制;)
说明
1
| 第一次询问的时候可以买到两件编号为2的礼物。第三次询问的时候由于第二件礼物被买走，所以2到4柜子里只有一件编号为1的礼物和一件编号为2的礼物。第四次询问的时候可以买到两件编号为1的礼物。
|
分析
需要的知识：简单线段树，链表
询问的要求是区间内存在2个相同礼物。不妨开一个数组$pre[]$，让$pre[i]$表示和第$i$个礼物相同的礼物在$i$右边最近出现的位置。区间内存在2个相同礼物当且仅当区间$(l,r)$内存在$Next[i] \leq r$.
因此，用线段树维护区间内所有$Next$的最小值.当这个最小值也小于等于r时符合要求。
更新操作：我们用双向链表$Next$和$Last$模拟同种礼物之间的关系。把礼物$i$买走时，更改一下状态。由于$i$已经空了， $Next[i]$无意义，将其标记为$n+1$（或者其他大于n的数，总之无意义即可）。并将$Last[Next[i]]$设为$Last[i]$，$Next[Last[i]]$设为$Next[i]$.接着更新线段树，记得pushdown.
代码
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
#define lson k<<1
#define rson k<<1|1
using namespace std;
const int maxn = 1e6 + 1;
const int inf = 0x7fffffff;
int n, q;
struct edge
{
int l, r, mn;
}a[maxn << 1];
int num[maxn];
int Next[maxn];
int Last[maxn];
inline void pushup(int k)
{
a[k].mn = min(a[lson].mn, a[rson].mn);
}
void build(int k, int l, int r)
{
a[k].l = l, a[k].r = r;
if(l == r){
a[k].mn = Next[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(k);
return;
}
int query(int k, int l, int r)
{
if(a[k].l >= l && a[k].r <= r) return a[k].mn;
int mid = (a[k].l + a[k].r) >> 1;
if(r <= mid) return query(lson, l, r);
else if(l > mid){
return query(rson, l, r);
}
else return min(query(lson, l, mid), query(rson, mid + 1, r));
}
void buy(int k, int p, int x)
{
if(a[k].l == a[k].r){
a[k].mn = x;
return;
}
int mid = (a[k].l + a[k].r) >> 1;
if(p <= mid) buy(lson, p, x);
else buy(rson, p, x);
pushup(k);
}
map<int, int> pos;
int main()
{
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i){
scanf("%d", &num[i]);
Last[i] = 0, Next[i] = n + 1;
}
for(int i = 1; i <= n; ++i){
if(pos.count(num[i])) Last[i] = pos[num[i]];
pos[num[i]] = i;
}
pos.clear();
for(int i = n; i > 0; --i){
if(pos.count(num[i]) && pos[num[i]] != 0) Next[i] = pos[num[i]];
else Next[i] = n + 1;
pos[num[i]] = i;
}
build(1, 1, n);
int u, v, w;
while(q--)
{
scanf("%d", &u);
if(u == 1){
scanf("%d", &v);
int lst = Last[v], nst = Next[v];
Last[nst] = Last[v],
Next[lst] = Next[v];
buy(1, lst, nst);
Next[v] = inf;
buy(1, v, inf);
}
else{
scanf("%d%d", &v, &w);
if(query(1, v, w) <= w){
printf("1\n");
}
else printf("0\n");
}
}
build(1, 1, n);
return 0;
}
|
G - 买糖果（并查集）
题目描述
在一个幼儿园里面有n\mathit nn个小朋友，分别编号1,2,…,n\text 1,2,…,n1,2,…,n。在这些小朋友中有一些小朋友互为朋友关系，总共有m\mathit mm对朋友。
作为幼儿园老师，你想买一些糖果分给小朋友，你知道第i\mathit ii个小朋友想要至少aia_{i}ai个糖果，否则他就会不开心。
同时，如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数，他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢？
输入描述:
第一行以空格分隔的两个整数$n,m$。
第二行以空格分隔的$n$个正整数$a_i$ 。
接下来m行每行以空格分隔的两个正整数u,v，代表u是v的朋友，v是u的朋友。
$1\leq n\leq 10^{6} $
$0\leq m\leq 10^{6}$
$1\leq a_{i} \leq 10^{9}$
$1\leq u,v \leq n,u≠v$
输出描述:
购买的最少糖果数以保证每个小朋友都不会不开心。
示例1
输入
复制;)
输出
复制;)
说明
1
| 给第三个小朋友买3个糖果，前两个小朋友都买2两个糖果，总共至少买7个糖果。注意如果给第一个小朋友只买了1个糖果，那么他在看到自己的好朋友2有2个糖果的情况下，他就会不开心。
|
分析
注意，咋一看，朋友的朋友不是朋友，但需求有传递性。例如，A与B互为朋友，B与C互为朋友，B与C的需求都是max(B,C), 而A与B的需求都是是max(A, B)，因此三者的需求都会是max(A,B,C).
不妨使用并查集，将互为朋友的并到一起，他们需要的糖果数等于他们所在的并查集生成的树中所有需求的最大值。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 500;
ll a[maxn+5];
ll fa[maxn];
ll find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(ll i = 1; i <= n; ++i) cin >> a[i], fa[i] = i;
ll x, y;
for(ll i = 0; i < m; ++i){
cin >> x >> y;
ll fx = find(x), fy = find(y);
fa[fx] = fy;
a[fx] = a[fy] = max(a[fx], a[fy]);
}
ll ans = 0;
for(ll i = 1; i <= n; ++i) ans += a[find(i)];
cout << ans;
return 0;
}
|
H - 数字串（贪心，思维）
链接：https://ac.nowcoder.com/acm/contest/9983/H
来源：牛客网
题目描述
牛牛发现了一种方法可以将只包含小写字母的字符串按照以下方式使其转换成一个数字串：
取其中的每个字母，$a$转换为1，$b$转换为2……$z$转换为26，然后将这些数字拼接起来。
例如，$abcz$可以转换为$12326$。
现在给出一个只包含小写字母的字符串$S$，你需要找到一个只包含小写字母的字符串$T$，使得两个 串不相同但是能转换成相同的数字串。
输入描述:
一行一个长度不超过$10^{6}$的小写字母字符串$S$。
输出描述:
示例1
输入
复制;)
输出
复制;)
说明
示例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
| #include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<int> t;
for(int i = 0; i < s.size(); ++i)
t.push_back(s[i] - 'a' + 1);
int flag = 0;
int pos;
for(int i = 0; i < t.size(); ++i)
{
if(!flag && (t[i] > 10 && t[i] != 20)){
flag = 1;
pos = i;
}
else if(!flag && (t[i] == 1 || t[i] == 2))
{
if(i != t.size() - 1 && t[i + 1] <= 6){
flag = 2;
pos = i;
}
}
}
if(!flag) cout << -1;
else{
string ans;
for(int i = 0; i < t.size(); ++i){
if(i == pos){
if(flag == 1){
ans += 'a' + t[i] / 10 - 1;
ans += 'a' + t[i] % 10 - 1;
}
else if(flag == 2){
int p = t[i] * 10;
p += t[++i];
ans += 'a' + p - 1;
}
}
else ans += 'a' + t[i] - 1;
}
cout << ans;
}
}
|
I - 序列的美观度（动态规划 or 贪心）
题目描述
设一个长度为$m$的序列$S$的美观度等于有多少个整数$i$满足$1≤i≤m−1$且$Si=S_{i+1}$，其中$S_i$代表 序列$S$的第$i$个元素。
给出一个长度为$n$的序列$a$，问在他的所有子序列美观度最大是多少。
某个序列的子序列是从最初序列通过去除某些元素（也可以不去除，即序列本身也是子序列）但不破坏余下元素的相对位置（在前或在后）而形成的新序列。
输入描述:
第一行一个正整数$n$。
接下来一行$n$个以空格分隔的正整数$a_i$。
$2≤n≤10^6$
$1\leq a_{i} \leq 10^{6}$
输出描述:
示例1
输入
复制;)
输出
复制;)
说明
示例2
输入
复制;)
输出
复制;)
分析
首先理解好题意。
$dp$做法：
类似于LIS问题.在求$dp[i]$时，找$a_i$是否可以接在$a_j(i>j)$后面（二者相同）以提升美观度，是就$dp[i] = dp[j]+1$，否则$dp[i] = dp[i - 1]$.但看看数据规模达到了$1e6$，尝试优化.开一个新数组，将每个数的相同数上一次出现的位置存进去，然后直接调用这个数组就可以找到， 不需要遍历$0$到$i-1$. 即：$dp[i] = max(dp[pre[i]] + 1, dp[i - 1])$.
代码（dp）
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
const int inf = 0x3f3f3f3f;
int a[maxn];
int dp[maxn];
int pre[maxn];
int last[maxn];
int main()
{
int n;
cin >> n;
memset(last, 0x3f, sizeof(last));
memset(pre, 0x3f, sizeof(pre));
for(int i = 0; i < n; ++i){
cin >> a[i];
pre[i] = last[a[i]];
last[a[i]] = i;
}
dp[0] = 0;
int ans = 0;
for(int i = 1; i < n; ++i){
dp[i] = 0;
if(pre[i] != inf) dp[i] = max(dp[pre[i]] + 1, dp[i - 1]);
else dp[i] = dp[i - 1];
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
|
贪心做法：
如果我们已经完成了对前面某个子列的求解，现在看向后面一段。
从后面一段找符合条件的数字，如果找到了很多，那么一定把靠前的放入答案数组，这样一定不会比只放入后面的差。
证明：
首先举两个例子。
例如，序列是1112211.首先得到子列111，现在美观度是2.然后考虑后面，有22和11.将他们接过来都能使美观度+1. 如果我们接2211，那么得到1112211，美观度就会是5.如果只接11，那么得到11111，美观度是5. 这样二者都最优。
然而如果序列是1112233，如果我们只接33，得到11133，美观度就只有4了，此时得到1112233依然是5.
考虑更一般的情况。如果我们把最近的可以增加美观度的数字拼接了得到$str_1$，或者不拼接最近的，而是次近的得到$str_2$，那么$str1$和$str2$的美观度至少相等. 此时$str1$后面剩下的数字更多，我们有更多选择，因此选择$str1$总是优于$str2$的.
那么实现思路就是维护一个数字表示当前已生成的答案序列的最后一个的下标.然后遍历，依次把符合条件的接上来，复杂度$O(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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
const int inf = 0x3f3f3f3f;
int a[maxn];
int pre[maxn];
int last[maxn];
int main()
{
memset(pre, 0x3f, sizeof(pre));
memset(last, 0x3f, sizeof(last));
int ans = 0;
int n; cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
pre[i] = last[a[i]];
last[a[i]] = i;
}
int now = 0;
for(int i = 1; i < n; ++i){
if(pre[i] != inf && now <= pre[i]){
now = i;
ans++;
}
}
cout << ans;
return 0;
}
|
J - 加法和乘法
题目描述
有一天牛牛和牛妹在做游戏，规则如下：
桌面上摆着$n$张纸牌，每张纸牌上写着一个正整数，由牛牛先手轮流执行以下操作：
1.如果桌面上只剩一张纸牌，游戏结束，这张纸牌上的数字如果是奇数则牛牛胜利，反之牛妹胜利。
2.当前行动玩家选择两张纸牌，设上面的数字分别为X,Y\mathit X,YX,Y，接下来玩家从加法和乘法中选择一个并应用到这两个数字上，得到结果为Z\mathit ZZ，接下来将选择的两张纸牌丢弃，并拿一张新的纸牌放到桌面上，在上面写上Z\mathit ZZ。
假设双方均以最优策略行动，最后谁会赢？
输入描述:
第一行一个正整数n，代表开始的纸牌数。
第二行n个空格分隔的正整数a[i]代表开始纸牌上的数字。
$1\leq n \leq 10^{6}$
$1\leq a_{i} \leq 10^{9}$
输出描述:
如果牛牛能赢，输出NiuNiu，否则输出NiuMei。
示例1
输入
复制;)
输出
复制;)
示例2
输入
复制;)
输出
复制;)
分析
比较简单的博弈论。
首先把奇数偶数之间各种加减得到的数的奇偶性都想好，然后再开始讨论。
首先发现：牛牛最优的做法也只是通过（奇+偶=奇）来减少一个偶数，而无法减少2个偶数，也无法使奇数增加。反观牛妹，只要场上还有奇数牌，她就可以减少1个甚至两个奇数牌，而且还能生成一个偶数。由此看来，当牛妹的偶数牌只有一张时，牛牛只需要一次（奇+偶=奇）就能赢下比赛。
反之若牛妹的偶数牌多于一张：
只要牛牛的奇数多于一张，那么牛妹就可以通过减少2张奇数牌来生成一个偶数牌，牛牛只能减少一个偶数，永远无法跟上牛妹的速度！而当牛牛的奇数只有一张时，牛妹只需要一次合成就赢下比赛了。
综上，若偶数牌>1，牛妹必胜，若偶数牌=1，牛牛必胜。
再看偶数牌=0的情况。
若奇数牌的个数是奇数个，那么只要不为1，牛妹必胜。这是因为每当到了牛牛的回合时，他会把奇数个牌变成奇数-1个牌，也就是偶数个牌；而最后只剩下2张牌时就一定是牛妹的回合，这时牛妹不管这两张牌是什么，她总能得到偶数。
而若奇数牌的个数是偶数个，那么最后一个回合一定是牛牛的，而且由于牛妹每次最多也只生成一个偶数牌，牛牛肯定能把这个偶数牌卸下来，故最后不可能是全偶。剩下的两张牌一定有奇数。只要有奇数，那么牛牛就可以得到奇数了，也就是牛牛赢。
综上，当偶数牌>1时，牛妹赢；当偶数牌=1时，牛牛赢；当偶数牌=0且奇数牌有大于1的奇数个时，牛妹赢；当偶数牌=0且奇数牌个数为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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d", &n);
ll x;
int odd = 0, even = 0;
while(n--)
{
scanf("%lld", &x);
if(x % 2 == 0) even++;
else odd++;
}
if(odd == 0){
cout << "NiuMei";
}
else{
if(even == 0){
if(odd == 1) cout << "NiuNiu";
else if(odd % 2 == 0) cout << "NiuNiu";
else cout << "NiuMei";
}
else if(even > 1){
cout << "NiuMei";
}
else cout << "NiuNiu";
}
return 0;
}
|
