比赛地址:https://ac.nowcoder.com/acm/contest/9667
出题人题解:https://ac.nowcoder.com/discuss/575975
A-黑白边
知识点:并查集
优先选择黑边然后再选白边,选择$n-1$条边可使图连通。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n, m;
int u[MAXN], v[MAXN], w[MAXN];
int fa[MAXN];
int get(int i) {
if(fa[i] == i) return i;
return fa[i] = get(fa[i]);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; i++) fa[i] = i;
int sum = 0;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u[i], &v[i], &w[i]);
if(w[i] == 0) {
int x = get(u[i]);
int y = get(v[i]);
if(x != y) {
fa[x] = y;
sum++;
}
}
}
int cnt = 0;
for(int i = 0; i < m; i++) {
if(w[i] == 1) {
int x = get(u[i]);
int y = get(v[i]);
if(x != y) {
fa[x] = y;
cnt++;
sum++;
}
}
}
if(sum != n - 1) puts("-1");
else printf("%d\n", cnt);
return 0;
}
B-最好的宝石
知识点:线段树
线段树裸题,不会请看这篇文章线段树从零开始。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
struct node {
int x;
int cnt;
} tree[MAXN * 4];
int n, m;
int a[MAXN];
void push_up(int i) {
int l = i * 2, r = i * 2 + 1;
if(tree[l].x > tree[r].x) {
tree[i].x = tree[l].x;
tree[i].cnt = tree[l].cnt;
} else if(tree[l].x < tree[r].x) {
tree[i].x = tree[r].x;
tree[i].cnt = tree[r].cnt;
} else {
tree[i].x = tree[l].x;
tree[i].cnt = tree[l].cnt + tree[r].cnt;
}
}
void build(int i, int l, int r) {
if(l == r) {
tree[i].x = a[l];
tree[i].cnt = 1;
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
push_up(i);
}
void update(int i, int l, int r, int p, int x) {
if(l == r) {
tree[i].x = x;
tree[i].cnt = 1;
return;
}
int mid = (l + r) / 2;
if(p <= mid) update(i * 2, l, mid, p, x);
if(mid < p) update(i * 2 + 1, mid + 1, r, p, x);
push_up(i);
}
node query(int i, int l, int r, int left, int right) {
if(left <= l && r <= right) {
return tree[i];
}
node ret;
ret.x = -1;
ret.cnt = 0;
int mid = (l + r) / 2;
if(left <= mid) {
node ll = query(i * 2, l, mid, left, right);
ret = ll;
}
if(mid < right) {
node rr = query(i * 2 + 1, mid + 1, r, left, right);
if(rr.x > ret.x) ret = rr;
else if(rr.x == ret.x) ret.cnt += rr.cnt;
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
int l, r;
char op[7];
while(m--) {
scanf("%s%d%d", op, &l, &r);
if(op[0] == 'A') {
node ans = query(1, 1, n, l, r);
printf("%d %d\n", ans.x, ans.cnt);
} else {
update(1, 1, n, l, r);
}
}
return 0;
}
C-滑板上楼梯
知识点:贪心
选择先3阶再1阶的跳法,剩下的再单独判断。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
LL n;
int main() {
scanf("%lld", &n);
LL a = n / 4 * 2;//周期所需的次数
LL b = n % 4; //剩下所需的次数
if(b == 3) b = 1;
cout << a + b << endl;
return 0;
}
D-GCD
知识点:质数
极限情况下$k$个数由1和质数构成,所以只要$k>前n个数里质数的个数+1$则一定能满足条件。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n;
int a[MAXN];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) a[i] = 1;
for(int i = 2; i <= n; i++) {
if(a[i] == 1) {
for(int j = i + i; j <= n; j += i) a[j] = 0;
}
a[i] += a[i - 1];
//printf("%d = %d\n",i,a[i]);
}
if(a[n] == n) puts("-1");
else printf("%d\n", a[n] + 1);
return 0;
}
E-牛牛的加法
知识点:模拟
对于长度不同的数可以添加前导零使得运算更方便。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
string a, b, c;
int main() {
cin >> a >> b;
int n = max(a.length(), b.length());
while(a.length() < n) a = "0" + a;
while(b.length() < n) b = "0" + b;
for(int i = 0; i < n; i++) {
int x = (a[i] - '0' + b[i] - '0') % 10;
c += '0' + x;
}
for(int i = 0; i < n; i++) {
if(c[i] != '0') {
cout << c.substr(i) << endl;
break;
}
if(i == n - 1) puts("0");
}
return 0;
}
F-石子合并
知识点:贪心
每次都选取最大的那堆与相邻的进行操作。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n;
LL a[MAXN];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
sort(a, a + n);
LL sum = 0;
for(int i = 0; i < n - 1; i++) sum += a[i];
printf("%lld\n", sum + a[n - 1] * (n - 1));
return 0;
}
G-滑板比赛
知识点:双指针
对$a$和$b$排序之后,双指针扫一遍,对每个$a[i]$选择最小的满足条件的$b[i]$。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n, m;
int a[MAXN], b[MAXN];
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < m; i++) scanf("%d", &b[i]);
sort(a, a + n);
sort(b, b + m);
for(int i = 0, j = 0; i < m; i++, j++) {
while(j < n && a[j] <= b[i]) j++;
if(j == n) {
printf("%d\n", i);
break;
}
if(i == m - 1) {
printf("%d\n", i + 1);
break;
}
}
return 0;
}
H-第K小
知识点:堆
维护一个大小为$k$的大根堆,堆顶即为第$k$小的数。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n, m, k;
int op, x;
priority_queue<int> q;
int main() {
scanf("%d%d%d", &n, &m, &k);
while(n--) {
scanf("%d", &x);
q.push(x);
while(q.size() > k) q.pop();
}
while(m--) {
scanf("%d", &op);
if(op == 1) {
scanf("%d", &x);
q.push(x);
while(q.size() > k) q.pop();
} else {
if(q.size() < k) puts("-1");
else printf("%d\n", q.top());
}
}
return 0;
}
I-区间亦或
知识点:枚举
注意$n$的范围不超过$3000$,先枚举所有的区间并记录对应区间长度的最大值。
再对区间长度维护前缀最大值,对于每次询问二分查询答案。
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e6 + 117;
const int MAXM = 1e6 + 117;
int n, m;
int a[MAXN];
int ans[MAXN];
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum ^= a[j];
ans[j - i + 1] = max(ans[j - i + 1], sum);
}
}
for(int i = 1; i <= n; i++) ans[i] = max(ans[i], ans[i - 1]);
while(m--) {
int x;
scanf("%d", &x);
int id = lower_bound(ans + 1, ans + n + 1, x) - ans;
if(id > n) puts("-1");
else printf("%d\n", id);
}
return 0;
}
J-小游戏
知识点:$dp$
注意$a[i]$不超过$2e5$,先统计每个数出现的次数,设$dp[i][0/1]$表示前$i$个数里第$i$个数取和不取的最大分数,则有状态转移方程:
- $dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])$
- $dp[i][1] = dp[i - 1][0] + i * a[i]$
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;
int n;
int x;
LL a[MAXN];
LL dp[MAXN][2];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &x);
a[x]++;
}
for(int i = 1; i <= 200000; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + i * a[i];
}
printf("%lld\n", max(dp[200000][0], dp[200000][1]));
return 0;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/159/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。