ZROI 2022CSP7连测 Round5 解题报告
100 + 90 + 100 + 35,rk 33.
挂分捏。
A
人口普查题。注意使用 getline
和 string
.
string s;
bool chk1(char c) {
if (c <= '9' && c >= '0') return 1;
else return 0;
}
bool chk2(char c) {
if (c <= 'z' && c >= 'a') return 1;
else if (c <= 'Z' && c >= 'A') return 1;
else return 0;
}
signed main() {
getline(cin,s);
int n = s.size();
for (int i = 0;i < n;++i) {
if (chk1(s[i]) && chk2(s[i-1])) printf(" ");
if (chk2(s[i]) && chk1(s[i-1])) printf(" ");
printf("%c",s[i]);
}
return 0;
}
B
首先考虑一个性质:Alice/Bob 每次必然取的都是从大到小排序后的一段前缀。
这个的证明暂时不会,不过可以感性理解。
所以我们考虑 DP。令
这个的意义是显然的,直接做 DP,时间复杂度为
const int N = 1e5 + 10;
ll a[N],ans,n,f[2][N],pre[N];
bool flag = 0;
vector <ll> res;
signed main() {
read(n);
for (int i = 1;i <= n;++i) read(a[i]),flag |= (a[i] < 0);
if (!flag || n == 1) {
for (int i = 1;i <= n;++i) ans += a[i];
printf("%lld\n",ans);
return 0;
}
sort(a + 1,a + 1 + n);reverse(a + 1,a + 1 +n);
for (int i = 1;i <= n;++i) pre[i] = pre[i-1] + a[i];
f[1][0] = -1e18;
for (int i = 1;i <= n;++i) {
f[1][i] = max(f[0][i-1],f[1][i-1]) + a[i];
f[0][i] = f[1][i-1];
}
printf("%lld\n",max(f[0][n],f[1][n]));
return 0;
}
C
考虑枚举这个平均数
总时间复杂度
const int N = 2e5 + 10;
const int D = 1e7;
int n,a[N],pre[N],minn = 0x3f3f3f3f,maxx,b[N];
int buc[20000010];
ll ans;
signed main() {
read(n);
for (int i = 1;i <= n;++i) read(a[i]),minn = min(minn,a[i]),maxx = max(maxx,a[i]);
for (int x = minn;x <= maxx;++x) {
for (int i = 1;i <= n;++i) {
b[i] = a[i] - x;
pre[i] = pre[i-1] + b[i];
}
for (int i = 1;i <= n;++i) {
ans += (ll)buc[pre[i] + D];
buc[pre[i-1] + D]++;
}
for (int i = 1;i <= n;++i) {
buc[pre[i-1] + D] = 0;
}
}
ans += n;
printf("%lld\n",ans);
return 0;
}
D
本题本质:给定
我们考虑对于一个大小为
接下来我们判断出来了可行性,考虑如何构造。参考题解,我们需要注意的是:
- 首先是我们钦定需要处于同一强连通分量内的点,应当真的属于同一强连通分量 可以通过造一个环来满足强连通
- 强连通分量之间的边不能成环。解决办法也很简单:给每个强连通分量任意定一个编号,只从编号小的分量往编号大的分量 连边,就不会成环
时间复杂度应当是
//Autumn leaves falling down like pieces into place
//And I can picture it after all these days
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const ll mod = 998244353;
const double eps = 1e-10;
inline int add(int x, int y) {return (x += y) >= mod ? x - mod : x;}
inline int dec(int x, int y) {return (x -= y) < 0 ? x + mod : x;}
inline int mul(int x, int y) {return (ll)x * y % mod;}
const int N = 5e5 + 10;
int n,x,q,f[N];
ll m;
vector <int> G[N],poi[N];
vector <vector<int> > p;
int find(int x) {return x == f[x] ? f[x] : f[x] = find(f[x]);}
bool cmp(vector <int> a,vector <int> b) {
return a.size() < b.size();
}
signed main() {
read(n,m,x,q);
for (int i = 1;i <= n;++i) f[i] = i;
for (int i = 1;i <= q;++i) {
int x,y;read(x,y);
f[find(x)] = find(y);
}
for (int i = 1;i <= n;++i) {
poi[find(i)].push_back(i);
}
for (int i = 1;i <= n;++i) {
if (poi[i].size()) p.push_back(poi[i]);
}
sort(p.begin(),p.end(),cmp);
if (p.size() < x) {
puts("-1");
return 0;
}
while (p.size() > x) {
auto &a = p[p.size() - 2],&b = p[p.size() - 1];
swap(a,b);
a.insert(a.end(),b.begin(),b.end());
p.pop_back();
}
ll l = 0,r = 0,pre = 0;
for (auto &now : p) {
l += (now.size() == 1 ? 0 : now.size());
r += (ll)(now.size() * (now.size() - 1 + pre));
pre += now.size();
}
if (m < l || m > r) {
puts("-1");
return 0;
}
for (auto &now : p) {
int orz = now.size();
if (orz == 1) continue;
for (int i = 0;i < orz;++i) printf("%d %d\n",now[i],now[(i + 1) % orz]);
}
m -= l;
vector <int> lst;
for (auto &now : p) {
int orz = now.size();
for (int i = 0;i < orz;++i) {
for (int j = 0;j < orz;++j) {
if (i != j && j != (i + 1) % orz) {
printf("%d %d\n",now[i],now[j]);
if ((--m) == 0) {return 0;}
}
}
for (auto j : lst) {
printf("%d %d\n",now[i],j);
if ((--m) == 0) {return 0;}
}
}
lst.insert(lst.end(),now.begin(),now.end());
}
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
atw 好评!