Educational Codeforces Round 102 (Rated for Div. 2)
A. Replacing Elements
题意
给一个正整数数组，每次可以选三个不同位置，把其中一个数换成另外两个数的和。问能不能让所有数都不超过 。
思路
如果已经都不超过 ，当然直接结束。否则就看最小的两个数加起来能不能不超过 。
能的话，保留这两个数，拿它们的和替换所有超标的数。连最小的两个数都加大了，第一次操作就造不出一个不超过 的数，后面也帮不上忙。排序后判断，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 1e3 + 17;
int T, n, a[maxn], d;
int main() {
cin >> T;
while(T--) {
cin >> n >> d;
int flg = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] > d) flg = 1;
}
if(flg) {
sort(a + 1, a + 1 + n);
if(a[1] + a[2] <= d) flg = 0;
}
puts(flg ? "NO" : "YES");
}
return 0;
}B. String LCM
题意
给两个字符串，找最短的非空字符串，使它既能由第一个串重复得到，也能由第二个串重复得到。如果不存在就输出 -1。
思路
分别找出两个串最短的循环节。先枚举循环节长度，只有能整除串长的长度才考虑，再逐段比较。
循环节不同就拼不到一起。相同的话，假设两边各重复了 次，再把这个循环节重复 次就行。这里串很短，直接枚举和比较就够了。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int T;
inline int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int main() {
cin >> T;
while(T--) {
string s1, s2;
cin >> s1; cin >> s2;
int len1 = s1.length(), len2 = s2.length();
int l1 = 0, l2 = 0;
for(l1 = 1; l1 <= len1; l1++) {
if(len1 % l1) continue;
int flg = 1;
for(int i = l1; i < len1;) {
for(int j = 0; j < l1; j++, i++) {
if(s1[i] != s1[j]) flg = 0;
}
}
if(flg) break;
}
for(l2 = 1; l2 <= len2; l2++) {
if(len2 % l2) continue;
int flg = 1;
for(int i = l2; i < len2;) {
for(int j = 0; j < l2; j++, i++) {
if(s2[i] != s2[j]) flg = 0;
}
}
if(flg) break;
}
if(l1 == l2) {
int flg = 1;
for(int i = 0; i < l1; i++) {
if(s1[i] != s2[i]) flg = 0;
}
if(flg) {
int x = len1 / l1, y = len2 / l2;
int rep = x * y / gcd(x, y);
for(int i = 1; i <= rep; i++) {
for(int j = 0; j < l1; j++) printf("%c", s1[j]);
}
printf("\n");
}
else {
puts("-1");
}
}
else puts("-1");
}
return 0;
}C. No More Inversions
题意
序列先从 1 升到 ，再降到 ，总长为 。要找一个 的排列 ，用 替换每一项，要求逆序对不增加，并让新序列字典序最大。
思路
设 。小于 的数只出现一次，后面的数除了 都出现两次。
对后面这组数，两个不同的数不管谁大，贡献的逆序对数都一样；和中间只出现一次的 比，也始终贡献一次。所以这组可以随便换顺序，直接倒过来让前面的数尽量大。
前面只出现一次的部分原本没有逆序对，动它只会增加，保留升序就行。最后输出 1...r-1，再输出 k...r，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int T, n, k;
int main() {
cin >> T;
while(T--) {
cin >> n >> k;
for(int i = 1; i < 2 * k - n; i++) printf("%d%c", i, " \n"[i == k]);
int j = k;
for(int i = 2 * k - n; i <= k; i++, j--) printf("%d%c", j, " \n"[i == k]);
}
return 0;
}D. Program
题意
变量从 0 开始，程序里的 +、- 分别让它加 1、减 1。每个询问独立删掉一段指令，问执行剩下的程序时一共出现过多少种值，包括初始的 0。
思路
每次只走 1，最小值和最大值之间的整数都会经过，所以只要求出这两个端点。
先求前缀和，用 ST 表查区间最大最小值。删掉 后，前半段不变，后半段整体减去 s[r] - s[l-1]，把两边的极值和 0 合起来，答案就是 mx - mn + 1。
建表花 。这里查表前用循环找对数，每次询问是 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 17;;
int T, n, m, a[maxn], s[maxn], dmax[maxn][20], dmin[maxn][20];
void initMax(int n,int d[])
{
for(int i=1;i<=n;i++)dmax[i][0]=d[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
}
int getMax(int L,int R)
{
int k=0;
while((1<<(k+1))<=R-L+1)k++;
return max( dmax[L][k],dmax[R-(1<<k)+1][k] );
}
void initMin(int n,int d[])
{
for(int i=1;i<=n;i++)dmin[i][0]=d[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
dmin[i][j]=min( dmin[i][j-1],dmin[i+(1<<(j-1))][j-1] );
}
int getMin(int L,int R)
{
int k=0;
while((1<<(k+1))<=R-L+1)k++;
return min( dmin[L][k],dmin[R-(1<<k)+1][k] );
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
string str;
cin >> str;
for(int i = 1; i <= n; i++) a[i] = (str[i - 1] == '+' ? 1 : -1);
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
initMin(n, s);
initMax(n, s);
for(int i = 1; i <= m; i++) {
int l, r;
scanf("%d%d", &l, &r);
int tmp = s[r] - s[l - 1];
int mx = 0, mn = 0;
if(l > 1) {
mx = max(mx, getMax(1, l - 1));
mn = min(mn, getMin(1, l - 1));
}
if(r < n) {
mx = max(mx, getMax(r + 1, n) - tmp);
mn = min(mn, getMin(r + 1, n) - tmp);
}
printf("%d\n", mx - mn + 1);
}
}
return 0;
}