A Commentary Boxes
算出$N pmod M$
然后分别讨论是加还是减
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#define int long long
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, M, A, B;
main() {
N = read(); M = read(); A = read(), B = read();
int res = N % M;
printf("%lld", min((M - res) * A, res * B));
}B Micro-World
排序之后用一个栈维护当前的病毒
然后不断吞就好了
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#define int long long
using namespace std;
const int MAXN = 1e6 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, K;
int a[MAXN], s[MAXN], top = 0;
main() {
N = read(); K = read();
for(int i = 1; i <= N; i ) a[i] = read();
sort(a 1, a N 1);
int ans = 0;
s[ top] = a[1];
for(int i = 2; i <= N; i ) {
while(top > 0 && (a[i] > s[top]) && (a[i] <= s[top] K))
ans , top--;
s[ top] = a[i];
}
printf("%d", N - ans);
}C Bracket Sequences Concatenation Problem
类似于$)($的肯定是不管与谁都无法匹配
$(($这样的只能匹配$))$，反过来同理
$()$这样合法的于合法的都能匹配
然后记录一下乘法原理统计答案
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 3e5 10;
int N, M, A, B;
int s[MAXN];
LL top = 0, L[MAXN], R[MAXN], can, limit = 0;
char ss[MAXN];
main() {
//freopen("a.in", "r", stdin);
//freopen("c.out", "w", stdout);
int N;
scanf("%d", &N);
for(int i = 1; i <= N; i ) {
scanf("%s", ss 1);
top = 0;
int Len = strlen(ss 1);
bool flag = 0;
for(int j = 1; j <= Len; j ) {
if(ss[j] == '(') s[ top] = 1;
if(ss[j] == ')') {
if(top > 0 && s[top] == 1) top--;
else s[ top] = 2;
}
}
for(int j = 2; j <= top; j )
if(s[j] != s[j - 1])
{flag = 1; break;}
if(flag == 1) continue;
limit = max(limit, top);
if(top == 0) {L[0] ; R[0] ; continue;}
if(s[top] == 2) R[top] ;
if(s[top] == 1) L[top] ;
}
LL ans = 0;
for(int i = 0; i <= limit; i )
ans = 1ll * L[i] * R[i];
printf("%lldn", ans);
}D Graph And Its Complement
第一次遇到构造题
首先当$a,b$同时不唯一的时候一定是无解的，
证明：假设原图的联通块数不为$1$，那么原图中不同联通块之间的点在反图中一定有边， 这样原图中的不同联通块之间的点可以通过新边到达其他联通块， 然后再通过其他联通块的新边回到原来的联通块
这样我们假设$a=1$（若不满足可以交换）
设$b=x$
首先我们把原图中的边全都连上，然后在原图中任意$N-x$对点的边断开就好
注意要特判$N=2$和$N=3$的情况
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#define LL long long
using namespace std;
const LL MAXN = 1001, INF = 1e18 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
char ans[MAXN][MAXN];
main() {
int N = read(), A = read(), B = read();
if(A != 1 && B != 1) { printf("NO"); return 0;}
char a = '1', b = '0';
if(A != 1) swap(a, b), swap(A, B);
if((N == 2 || N == 3) && B == 1) { printf("NO"); return 0;}
printf("YESn");
for(int i = 1; i <= N; i )
for(int j = 1; j <= N; j )
if(i != j) ans[i][j] = a;
else ans[i][j] = '0';
for(int i = 1; i <= (N - B); i )
ans[i][i 1] = b,
ans[i 1][i] = b;
for(int i = 1; i <= N; i , puts(""))
for(int j = 1; j <= N; j )
putchar(ans[i][j]);
}E Post Lamps
预处理出障碍，
直接暴力枚举选哪个
时间复杂度为调和级数$O(klogn)$
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#define LL long long
using namespace std;
const LL MAXN = 1e6 10, INF = 1e18 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, M, K;
int block[MAXN], sum[MAXN], a[MAXN], cnt[MAXN];
main() {
N = read(); M = read(); K = read();
for(int i = 1; i <= M; i ) block[read()] = 1;
if(block[0]) {printf("-1"); return 0;}
for(int i = 1; i <= K; i ) a[i] = read();
int mx = 0;
for(int i = 1, j; i <= 1e6; i = j 1) {
j = i; int num = 0;
while(block[j]) mx = max(cnt[j] = num, mx), j ;
}
LL out = INF;
for(int i = mx 1; i <= K; i ) {
LL now = 0, spend = 0;
while(now < N) {
if(block[now]) now = now - cnt[now];
else now = now i, spend = spend a[i];
}
out = min(out, spend);
}
printf("%lld", out == INF ? -1 : out);
}总结
第一次打cf，确实有很多不适应的地方，第一题上来把$n$和$m$看反了，然后特判的时候写的是$M % N$，直接wa到飞
T2秒的比较快
T3也秒的比较快，不过写代码的时候把$)($判成了$()$，又wa成傻逼。
T4没看，不过zbq秒了(不过他考场上没判$n=3$..)，然后赛后做了做
T5最后几分钟看了看，当时感觉比较可做，但是思路一直纠结在如何处理障碍上，我一直以为障碍的范围是$10^9$然后纠结要不要开map
怎么说呢，感觉自己最近真的太浮躁了，很多时候连范围都没看清楚就开始做。
希望自己往后打cf的时候能沉下心来一句一句的读题目吧。
