CTSC/APIO时间太宽松，感觉很无聊，就来水水CF吧
虽然都是很水的题但还是WA了很多次，，，
A
直接模拟
#include<cstdio>
#include<iostream>
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 main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
int N = read(), K = read();
while(K != 0) {
if(N % 10 > 0) N--, K--;
else N /= 10, K--;
}
printf("%d", N);
return 0;
}
B
用string预处理出来然后直接暴力比较
$O(N^2)$
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 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 s[MAXN];
string a[MAXN];
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
int N = read();
scanf("%s", s + 1);
for(int i = 1; i <= N - 1; i++)
a[i] += s[i], a[i] += s[i + 1];
int mx = 0; string mxs;
for(int i = 1; i <= N - 1; i++) {
int now = 0;
for(int j = 1; j <= N - 1; j++)
if(a[i] == a[j])
now++;
if(now > mx) mx = now, mxs = a[i];
}
cout<<mxs;
return 0;
}
C
对序列排序之后判断$k$和$k+1$位置是否相等
注意当$k=0$的时候有两种特殊情况，需要特判
#include<cstdio>
#include<iostream>
#include<algorithm>
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, M;
int a[MAXN];
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read(); M = read();
for(int i = 1; i <= N; i++)
a[i] = read();
sort(a + 1, a + N + 1);
if((a[M] == a[M + 1]) || (M > N) || (M == 0 && a[1] == 1)) puts("-1");
else if(M == 0) printf("1");
else printf("%d",a[M]);
return 0;
}
D
将满足条件的两个点连边
然后BFS即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdlib>
#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, M;
vector<int>v[MAXN];
int inder[MAXN],a[MAXN], vis[MAXN], ans[MAXN], tot = 0;
void dfs(int now) {
ans[++tot] = a[now];
if(tot == N) {
for(int i = 1; i <= tot; i++)
printf("%lld ", ans[i]);
exit(0);
}
for(int i = 0; i < v[now].size(); i++)
if(!vis[v[now][i]]) vis[v[now][i]] = 1, dfs(v[now][i]), vis[v[now][i]] = 0;
tot--;
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read();
for(int i = 1; i <= N; i++)
a[i] = read();
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
if((a[i] / 3 == a[j] && a[i] % 3 == 0) || a[i] * 2 == a[j])
v[i].push_back(j), inder[j]++;
for(int i = 1; i <= N; i++)
dfs(i);
}
E
很容易观察出一条性质：一张图内的点满足情况，当切仅当每个点的度数都为$2$
然后DFS判断每个点的联通性就可以了
用栈维护联通块中的元素
#include<iostream>
#include<vector>
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, M;
vector<int>v[MAXN];
int vis[MAXN], s[MAXN], top = 0, inder[MAXN];
void dfs(int x) {
s[++top] = x;
for(int i = 0; i < v[x].size(); i++) {
int nxt = v[x][i];
if(!vis[nxt]) vis[nxt] = 1, dfs(nxt);
}
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read(), M = read();
for(int i = 1; i <= M; i++) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
inder[x]++; inder[y]++;
}
int Ans = 0;
for(int i = 1; i <= N; i++) {
if(!vis[i]) {
top = 0;
vis[i] = 1;
dfs(i);
for(int i = 1; i <= top; i++)
if(inder[s[i]] != 2) {Ans--;break;}
// for(int i = 1; i <= top; i++)
// printf("%d %d
", s[i], vis[s[i]]);
Ans++;
}
}
printf("%d", Ans);
return 0;
}
F
此题有毒
考虑到值域很大，直接用map DP
但是DP的过程中不能记录位置，因为每个值出现的位置是无序的
这样我们可以在求出最优值后重新遍历一下数组
#include<iostream>
#include<vector>
#include<map>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
using namespace std;
const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 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;
map<int, int>f;
int a[MAXN], ans[MAXN], tot = 0, mxnum, mx;
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read();
for(int i = 1; i <= N; i++) {
a[i] = read();
f[a[i]] = f[a[i] - 1] + 1;
if(f[a[i]] > mxnum) mx = a[i], mxnum = f[a[i]];
}
printf("%d
", f[mx]);
for(int i = N; i >= 1; i--)
if(a[i] == mx)
ans[++tot] = i, mx--;
for(int i = tot; i >= 1; i--)
printf("%d ", ans[i]);
return 0;
}