\(PS:\)手速局，由于晚点了15分钟左右就没打，赛后补题。
比赛链接
每个题目的链接直接点标题就好了，\(F1F2\)白天补。
给定一个字符串，是否有间断的相同字符序列。
直接枚举然后存一下出现次数就好了。
int n, m;
bool st[30];
int main()
{
int T;
cin >> T;
while (T -- )
{
memset(st, 0, sizeof st);
string s;
cin >> n >> s;
bool flag = false;
st[s[0] - ‘A‘] = true;
for (int i = 1; i < n; i ++ )
if (s[i] != s[i - 1] && st[s[i] - ‘A‘])
{
flag = true;
break;
}
else if (s[i] != s[i - 1] && !st[s[i] - ‘A‘]) st[s[i] - ‘A‘] = true;
if (flag) puts("NO");
else puts("YES");
}
return 0;
}
给定一个\(n\)，输出从\(1\)到\(n\)中由相同数字构成的数的个数。
直接枚举一下由每个数字构成的数即可，最多有\(9\)位。
int n, m;
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
int res = 0;
for (int i = 1; i <= 9; i ++ )
{
LL t = i;
while (t <= n)
{
res ++ ;
t = t * 10 + i;
}
}
cout << res << endl;
}
return 0;
}
给定一个\(n * n\)的棋盘，要求将\(1\)到\(n * n\)的数放到棋盘中，并且相邻的格子里的数不能相邻。
先放奇数，再放偶数，放偶数的时候判断一下，若不能放则输出\(-1\)。
const int N = 110;
int n, m;
int res[N][N];
bool put(int &x, int &y, int t)
{
for (int i = x; i <= n; i ++ )
{
int j = y;
if (i != x) j = 1;
for (; j <= n; j ++ )
{
res[i][j] = t;
t += 2;
if (abs(res[i - 1][j] - res[i][j]) == 1 && i != 1) return false;
if (t > n * n)
{
x = i;
y = j;
return true;
}
}
}
return true;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
int x = 1, y = 1;
put(x, y, 1);
y ++ ;
if (!put(x, y, 2)) puts("-1");
else
{
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
cout << res[i][j] << ‘ ‘;
cout << endl;
}
}
}
return 0;
}
给定一个长度为\(n\)的序列，要求输出使得\(a_j-a_i=j-i\)的数对的个数。
式子变形一下可以得到\(a_j-j=a_i-i\)，则使得原式子成立的数对必定有当前的数减去下标得到的值是相等的，因此我们只需要统计一下\(a_i-i\)出现的个数，然后从其中选出两个能得到的对出即可。
typedef long long LL;
const int N = 200010;
int n, m;
int g[N];
LL cnt[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> g[i], cnt[i] = 0;
cnt[0] = 0;
for (int i = 1; i <= n; i ++ )
if (g[i] - i >= 0)
cnt[g[i] - i] ++ ;
LL res = 0;
for (int i = 0; i <= n; i ++ )
res += cnt[i] * (cnt[i] - 1) / 2;
cout << res << endl;
}
return 0;
}
给定一个字符串，要求输出将字符串中的\({ * }\)全部放到一起所需要的最小步数，注意，只有当移动的位置是空（\(.\)）才可以移动。
两种做法
\(fl[i][j]\)表示将第\(i\)个位置前的\({ * }\)排在一起，并且队头是第\(i\)个位置所需要的步数，\(fr[i][j]\)表示将第\(i\)个位置后的\({ * }\)排在一起，并且队尾是第\(i\)个位置所需要的步数。最后遍历一遍取\(min\)就好了。
我们发现，中位数的性质，就是其余所有的点到中位数的路程是最短的,所以说我们要找中位数。然后两边依次排到中位数两边即可。
两种做法没有本质区别，中位数无非就是挖掘出了\(dp\)做法中某些性质。
typedef long long LL;
const int N = 1000010;
int n, m;
LL fl[N];
LL fr[N];
char s[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> s + 1;
for (int i = 1; i <= n + 1; i ++ ) fl[i] = 0, fr[i] = 0;
LL cnt = 0;
for (int i = 1; i <= n; i ++ )
if (s[i] == ‘*‘)
{
fl[i] = fl[i - 1];
cnt ++ ;
}
else fl[i] = fl[i - 1] + cnt;
cnt = 0;
for (int i = n; i >= 1; i -- )
if (s[i] == ‘*‘)
{
fr[i] = fr[i + 1];
cnt ++ ;
}
else fr[i] = fr[i + 1] + cnt;
LL res = 1e18;
for (int i = 1; i <= n; i ++ )
res = min(res, min(fl[i] + fr[i + 1], fl[i - 1] + fr[i]));
cout << res << endl;
}
return 0;
}
typedef long long LL;
const int N = 200010;
int n, m;
string s;
int main()
{
int T;
cin >> T;
while (T -- )
{
string s;
cin >> n >> s;
int sum = 0, cnt = 0;
for (int i = 0; i < n; i ++ )
if (s[i] == ‘*‘) sum ++ ;
sum = (sum + 1) / 2;
int t = -1;
for (int i = 0; i < n; i ++ )
if (s[i] == ‘*‘)
{
cnt ++ ;
if (cnt == sum)
{
t = i;
break;
}
}
LL res = 0;
cnt = 0;
for (int i = 0; i < n; i ++ )
if (s[i] == ‘*‘)
{
cnt ++ ;
res += abs(t - i) - abs(sum - cnt);
}
cout << res << endl;
}
return 0;
}
Codeforces Round #719 (Div. 3)题解
原文：https://www.cnblogs.com/wanshu/p/14733621.html