安利一个vscode打cf的插件：Codeforces
使用教程网上搜一下就有，极大提升cf体验。
总之就是水，水一水就过去了。
n行m列
1 3 5
2 4 6
第\(i\)个数就处在第 \((i-1) \mod n+1\)行和\((i-1)/n+1\)列。
n行m列
1 2 3
4 5 6
第\(i\)个数就处在第 \((i-1) \mod n+1\)行和\((i-1)/m+1\)行。
稍微处理一下就可以了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read()
{
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve()
{
ll n = read(), m = read(), x = read();
ll i = (x - 1) % n + 1, j = (x - 1) / n + 1;
cout << (i - 1) * m + j << endl;
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
给出一串字符串（这场的人好像很喜欢字符串），字符串由‘.‘, ‘‘组成。
要求输出一个字符串，满足其中的一部分‘‘被‘x‘替换并且两个‘x‘之间的距离不超过k。
求替换的最小次数。
模拟一下就可以了，水。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int read()
{
char ch=getchar();
int x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve()
{
int n = read(), k = read();
string s; cin >> s;
int l = 0, r = 0;
for (int i = 0; i < n; i++) if(s[i] == ‘*‘) {s[i] = ‘x‘; l = i; break;}
for (int i = n-1; i > 0; i--) if(s[i] == ‘*‘) {s[i] = ‘x‘; r = i; break;}
if (l > r) {cout << 1 << endl; return;}
for (int i = l; i + k < r; )
{
for (int j = i + k; j > i; j--) if (s[j] == ‘*‘) {s[j] = ‘x‘; i = j; break;}
}
int ans = 0;
for (int i = 0; i < n; i++) if (s[i] == ‘x‘) ans++;
cout << ans << endl;
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
找两个串的子串相同的最大长度
利用string类的性质有一种十分巧妙的解法（虽然本质是暴力，但是这样写会优雅一些。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read()
{
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve()
{
string a, b;
cin >> a >> b;
int lena = a.length(), lenb = b.length();
int ans = 0;
for (int i = 0; i < lena; i++)
for (int j = i; j < lena; j++)
if(b.find(string(a.begin()+i, a.begin()+j+1)) != -1) ans = max(ans, j - i + 1);
cout << lena + lenb - ans*2 << endl;
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
卡了许久。题意来说就是给你一串数组，每次删除可以从中删除不相同的两个元素。
显然在一开始就是要先map计算出数组中各个数字出现的个数，然后离散化套到优先队列里搞一搞。
我以为每次都处理两个不相同的数字集合，没有想到遇到了221133这种数据就不知道怎么做。标解是直接每次计算两个数。复杂度差不多是On但是我光顾着优化，没有想那么多。结果就卡了好久。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int read()
{
char ch=getchar();
int x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve()
{
int n = read();
int a[maxn] = {0};
map<int, int> mp;
int sz = n;
for (int i = 1; i <= n; i++) a[i] = read(), mp[a[i]]++;
sort(a+1, a+1+n);
n = unique(a+1, a+1+n)-(a+1);
priority_queue<int, vector<int>, less<int> > q;
for (int i = 1; i <= n; i++)
{
q.push(mp[a[i]]);
}
while(q.size() > 1)
{
int cur = q.top(); q.pop();
int nex = q.top(); q.pop();
cur--;
nex--;
if(cur) q.push(cur);
if(nex) q.push(nex);
sz -= 2;
//cout << cur << " " << nex << endl;
}
cout << sz << endl;
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
E比D要简单，只是用数组模拟会T，用优先队列搞一搞复杂度On就过了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read()
{
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
ll n, a[maxn], mp[maxn];
void solve()
{
n = read();
memset(a, 0, sizeof(a));
memset(mp, 0, sizeof(mp));
for (int i = 1; i <= n; i++) a[i] = read(), mp[a[i]] = 1;
a[0] = 0;
int pos = 1;
for (int i = 1; i <= n; i++)
{
if (a[i] != a[i-1]) cout << a[i] << " ";
else{
while(mp[pos]) pos++;
cout << pos << " ";
pos++;
}
}
puts("");
priority_queue<int, vector<int>, less<int> > q;
for (int i = 1; i <= n; i++)
{
if (a[i] != a[i-1])
{
cout << a[i] << " ";
for (int j = a[i-1] + 1; j <= a[i] - 1; j++) q.push(j);
}
else{
cout << q.top() << " "; q.pop();
}
}
puts("");
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
要做F先要把可以走通的路径图画出来，然后就模拟贪心一下就可其实挺水的。时间基本花在画图上（
这样基本能说明问题，然后对点(i,j)进行分类：
设从(i, j) 走到(i + a, j + b)的位置，要对a, b进行分类讨论。
然后分四类就行。本质上是模拟。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read()
{
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
struct P
{
ll x, y;
}p[maxn];
int cmp (P a, P b) {return a.x < b.x;}
void solve()
{
ll n = read();
for (int i = 1; i <= n; i++) p[i].x = read();
for (int i = 1; i <= n; i++) p[i].y = read();
p[0].x = p[0].y = 1;
sort(p + 1, p + 1 + n, cmp);
int ans = 0;
for (int i = 1; i <= n; i++)
{
int dx = p[i].x - p[i-1].x, dy = p[i].y - p[i-1].y;
if (dx == dy)
{
if (((p[i-1].x - p[i-1].y) & 1) == 0) ans += dx;
}
else if((dx - dy) & 1)
{
if((p[i-1].x - p[i-1].y) & 1) ans += (dx - dy + 1) / 2;
else ans += (dx - dy) / 2;
}
else {
ans += (dx - dy) / 2;
}
//cout << " " << p[i].x << " " << p[i].y << " " << dx << " " << dy << " " << ans << endl;
}
cout << ans << endl;
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}
Codeforces Round #710 (Div. 3) A-F
原文：https://www.cnblogs.com/clo91eaf/p/14584671.html