题目链接 传送门
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
Problem G
签到
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
int n;
int c[10];
char s[10];
int ans = 0;
int main(){
scanf("%d", &n);
rep(i, 1, n){
scanf("%s", s + 1);
rep(j, 1, 7) c[j] += (s[j] == '1');
}
rep(i, 1, 7) ans = max(ans, c[i]);
printf("%d
", ans);
return 0;
}
Problem H
令$f[i]$为从左往右把$a[1]$到$a[i]$变成严格递增序列所需的最小代价。
$g[i]$为从右往左把$a[n]$到$a[i]$变成严格递减序列所需的最小代价。
$c[i]$为从左往右把$a[1]$到$a[i]$变成严格递增序列花费最小代价的时候$a[i]$的值。
$d[i]$为从左往右把$a[n]$到$a[i]$变成严格递减序列花费最小代价的时候$a[i]$的值。
枚举一下答案。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL a[N], c[N], d[N], f[N], g[N];
LL ans;
int main(){
scanf("%d", &n);
rep(i, 1, n) scanf("%lld", a + i);
c[1] = a[1]; f[1] = 0;
rep(i, 2, n){
if (a[i] > c[i - 1]){
f[i] = f[i - 1];
c[i] = a[i];
}
else{
c[i] = c[i - 1] + 1;
f[i] = f[i - 1] + c[i] - a[i];
}
}
d[n] = a[n]; g[n] = 0;
dec(i, n - 1, 1){
if (a[i] > d[i + 1]){
g[i] = g[i + 1];
d[i] = a[i];
}
else{
d[i] = d[i + 1] + 1;
g[i] = g[i + 1] + d[i] - a[i];
}
}
ans = 1e18;
rep(i, 2, n - 1) ans = min(ans, f[i - 1] + g[i + 1] + (max(max(c[i - 1] + 1, d[i + 1] + 1), a[i])) - a[i]);
ans = min(ans, f[n]);
ans = min(ans, g[1]);
printf("%lld
", ans);
return 0;
}
Problem I
对于每一种噪音，上限为$2.6e7$
所以一种噪音最多传播到距离他$30$个单位的格子里；
直接暴力BFS即可。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second
typedef long long LL;
const int N = 255;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct node{
int x, y;
int dis;
LL cnt;
};
LL q, p;
LL c[N][N];
int a[N][N];
int n, m;
char s[N];
int vis[N][N];
int ans = 0;
inline bool check(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != -1 && vis[x][y] == 0;
}
void solve(int x, int y){
queue <node> qq;
queue < pair <int, int> > clr;
while (!qq.empty()) qq.pop();
qq.push({x, y, 0, q * a[x][y]});
vis[x][y] = 1;
clr.push(make_pair(x, y));
while (!qq.empty()){
node now = qq.front(); qq.pop();
int x = now.x, y = now.y;
int dis = now.dis;
LL cnt = now.cnt;
c[x][y] += cnt;
rep(i, 0, 3){
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny)){
int newdis = dis + 1;
LL newcnt = cnt / 2;
if (newcnt > 0){
qq.push({nx, ny, newdis, newcnt});
vis[nx][ny] = 1;
clr.push(MP(nx, ny));
}
}
}
}
while (!clr.empty()){
int x = clr.front().fi, y = clr.front().se;
vis[x][y] = 0;
clr.pop();
}
}
int main(){
scanf("%d%d%lld%lld", &n, &m, &q, &p);
rep(i, 1, n){
scanf("%s", s + 1);
rep(j, 1, m){
if (s[j] >= 'A' && s[j] <= 'Z') a[i][j] = (int)s[j] - 64;
else if (s[j] == '.') a[i][j] = 0;
else a[i][j] = -1;
}
}
rep(i, 1, n) rep(j, 1, m) if (a[i][j] > 0) solve(i, j);
rep(i, 1, n) rep(j, 1, m) if (c[i][j] > p) ++ans;
printf("%d
", ans);
return 0;
}
Problem J
Problem K
Problem L
构造题。
读入稍微有点麻烦
设$c[i][j]$为假设i和j之间有边并且如果把$i$和$j$断开的话那么$j$这个连通块的大小。
显然当$c[i][j] + c[j][i] = n$的时候$i$和$j$之间就真的有边了。
无解的情况为某个点的给定度数和实际做出来的度数不一样。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
const int N = 1010;
int c[N][N], f[N][N];
int deg[N];
int n;
int x, y;
int main(){
scanf("%d", &n);
rep(i, 1, n){
while (scanf("%d:", &x)){
++deg[i];
rep(j, 1, x - 1){
scanf("%d,", &y);
f[i][y] = x;
}
scanf("%d", &y);
f[i][y] = x;
if (getchar() != '-') break;
}
}
rep(i, 1, n - 1){
rep(j, i + 1, n){
if (f[i][j] + f[j][i] == n) c[i][j] = c[j][i] = 1;
}
}
rep(i, 1, n){
rep(j, 1, n) if (c[i][j]) --deg[i];
if (deg[i]) return 0 * puts("-1");
}
printf("%d
", n - 1);
rep(i, 1, n - 1){
rep(j, i + 1, n) if (c[i][j]) printf("%d %d
", i, j);
}
return 0;
}
Problem M
签到
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
int a[200010];
int n;
set <int> s;
int main(){
scanf("%d", &n);
rep(i, 1, n) scanf("%d", a + i);
rep(i, 1, n - 1) s.insert(a[i + 1] - a[i]);
if ((int)s.size() == 1) printf("%d
", a[n] - a[n - 1] + a[n]);
else printf("%d
", a[n]);
return 0;
}