Educational Codeforces Round 85 (Rated for Div. 2)
A：
int T, n, a[N], b[N];
int main() {
scanf("%d", &T);
while(T --) {
scanf("%d", &n);
bool tag = 1;
for(int i = 1; i <= n; i ++) {
scanf("%d%d", a + i, b + i);
tag &= a[i] >= b[i];
if(i > 1) {
tag &= a[i] >= a[i - 1];
tag &= b[i] >= b[i - 1];
tag &= a[i] - a[i - 1] >= b[i] - b[i - 1];
}
}
puts(tag ? "YES" : "NO");
}
return 0;
}
B：假设答案为(k)，肯定是选最富的(k)个人均分一下，排序check一下即可。
int T, n, x, a[N];
int main() {
scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &x);
int res = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", a + i);
}
sort(a + 1, a + n + 1, greater<int>());
ll sum = 0;
for(int i = 1; i <= n; i ++) {
sum += a[i];
if(sum >= 1ll * x * i) {
res = i;
}
}
printf("%d
", res);
}
return 0;
}
C：先确定最先打哪个怪(x)，然后最优打怪方案肯定是(x,x+1,...,n,1,..,x-1)，断环为链即可。
int T, n;
ll a[N], b[N], sum[N];
int main() {
scanf("%d", &T);
while(T --) {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%lld%lld", a + i, b + i);
a[i + n] = a[i]; b[i + n] = b[i];
}
for(int i = 1; i <= 2 * n; i ++) {
sum[i] = sum[i - 1] + max(0ll, a[i] - b[i - 1]);
}
ll ans = 2e18;
for(int i = 1; i <= n; i ++) {
ans = min(ans, sum[i + n - 1] - sum[i] + a[i]);
}
printf("%lld
", ans);
}
return 0;
}
D：自己模拟一下，发现最优路径是：
(1,2,1,3,..,1,n)；(2,3,2,4,2,...,2,n)；(...)；(1)。
直接模拟即可。
int T, n, len, seq[N];
ll l, r;
void getseq(int u) {
for(int i = u + 1; i <= n; i ++) {
seq[++ len] = u;
seq[++ len] = i;
}
}
int main() {
scanf("%d", &T);
while(T --) {
scanf("%d%lld%lld", &n, &l, &r);
bool tag = 0;
if(r == n * (n - 1ll) + 1) {
r --; tag = 1;
}
ll sum = 0, pre = 0; len = 0;
for(int i = 1; i <= n; i ++) {
if(r <= sum) break ;
sum += 2 * (n - i);
if(sum >= l) {
getseq(i);
} else {
pre += 2 * (n - i);
}
}
l -= pre; r -= pre;
for(int i = l; i <= r; i ++)
printf("%d ", seq[i]);
if(tag) printf("1 ");
puts("");
}
return 0;
}
E：题意转化就是(p_1^{c_1}p_2^{c_2}...p_k^{c_k})，把(c_p)加一或减一，代价是(prod_{i ot = p}(c_i+1))。猜结论：先降再升，降和升的顺序无所谓，就一可重排列方案。
int pc;
ll p[N], d, fac[N] = {1ll}, fav[N] = {1ll}, a[N], b[N];
int main() {
for(int i = 1; i < N; i ++) {
fac[i] = fac[i - 1] * i % mod;
fav[i] = qpow(fac[i], mod - 2);
}
scanf("%lld", &d);
for(ll i = 2; i * i <= d; i ++) {
if(d % i == 0) {
p[++ pc] = i;
while(d % i == 0) d /= i;
}
}
if(d > 1) p[++ pc] = d;
int t; scanf("%d", &t);
while(t --) {
ll u, v;
scanf("%lld%lld", &u, &v); a[0] = b[0] = 0;
for(int i = 1; i <= pc; i ++) {
ll tu = u, tv = v, cu = 0, cv = 0;
while(tu % p[i] == 0) {
tu /= p[i]; cu ++;
}
while(tv % p[i] == 0) {
tv /= p[i]; cv ++;
}
if(cu == cv) continue ;
if(cu < cv) {
a[++ a[0]] = cv - cu;
} else {
b[++ b[0]] = cu - cv;
}
}
ll a1 = 0, b1 = 0, x = 1, y = 1;
for(int i = 1; i <= b[0]; i ++) b1 += b[i], x = x * fav[b[i]] % mod;
x = x * fac[b1] % mod;
for(int i = 1; i <= a[0]; i ++) a1 += a[i], y = y * fav[a[i]] % mod;
y = y * fac[a1] % mod;
printf("%lld
", x * y % mod);
}
return 0;
}
F：题意转化为保留(a)中价值和最大的一些数，使得前缀max构成的不可重集合为(b)。
先写出dp方程：(f_i)表示选出的数形成的前缀max集合是(b)不超过(a_i)的数构成的子集，注意(i)可以选(i)后面的数。
(f_i = p_i + max(f_j + q(j,i,a_j)),j<i,exists k, a_i=b_k,a_j=b_{k-1})。
其中(q(j,i,a_j))表示((j,i))中满足(p > 0)且(aleq a_j)的(p)之和。
那维护两个数组(x,y)，(x[i])表示(i)后面(aleq a_i,p>0)的(p)只和。(y[i])表示(aleq L,p>0)的(p)之和，其中(L)表示b数组中(a_i)的上一个元素。这两个数组可以从后往前用树状数组求出。
然后直接对值dp。(dp[v])表示以(v)结尾的答案，(L)表示(a_i=v)在(b)中上一个数。(dp[v] = max(dp[v], dp[L] - y[i] + x[i] + p[i]))
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const ll INF = 1e18;
int n, m, a[N], b[N], c[N], pre[N];
ll sum, dp[N], x[N], y[N];
ll bit[N];
void bitadd(int u, ll v) {
for(; u <= n; u += u & (-u)) {
bit[u] += v;
}
}
ll bitqry(int u) {
ll ans = 0;
for(; u >= 1; u &= u - 1) {
ans += bit[u];
}
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) { scanf("%d", a + i); pre[a[i]] = -1; }
for(int i = 1; i <= n; i ++) { scanf("%d", c + i); sum += c[i]; }
scanf("%d", &m);
for(int i = 1; i <= m; i ++) { scanf("%d", b + i); pre[b[i]] = b[i - 1]; }
for(int i = n; i >= 1; i --) {
if(~ pre[a[i]]) {
x[i] = bitqry(a[i]);
y[i] = bitqry(pre[a[i]]);
}
if(c[i] > 0) bitadd(a[i], c[i]);
}
dp[0] = 0; fill(dp + 1, dp + n + 1, -INF);
for(int i = 1; i <= n; i ++) {
if(~ pre[a[i]] && dp[pre[a[i]]] != -INF) {
dp[a[i]] = max(dp[a[i]], dp[pre[a[i]]] - y[i] + x[i] + c[i]);
}
}
if(dp[b[m]] == -INF) { puts("NO"); return 0; }
printf("YES
%lld
", sum - dp[b[m]]);
return 0;
}
G：记原串(a)，转换后是(b)，匹配相当于(sum (a_i-t_i)^2(b_i-t_i)^2)，拆式子用NTT卷积。
#include <cstring>
#include <cstdio>
#include <random>
#include <ctime>
using namespace std;
typedef long long ll;
const int N = 524288 | 10, mod = 998244353, g = 3;
int rev[N], len, w[N], inv_w[N];
int qpow(int a, int b) {
int ans = 1;
for(; b >= 1; b >>= 1, a = (ll) a * a % mod)
if(b & 1) ans = (ll) ans * a % mod;
return ans;
}
void InitNTT(int n) {
int k = 0;
for(len = 1; len <= n; len <<= 1) k ++;
for(int i = 1; i < len; i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
w[0] = inv_w[0] = 1;
int v = qpow(g, (mod - 1) / len);
for(int i = 1; i < len; i ++)
inv_w[len - i] = w[i] = (ll) w[i - 1] * v % mod;
}
void NTT(int *a, const int *w) {
for(int i = 1; i < len; i ++)
if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < len; i <<= 1) {
for(int j = 0, t = len / (i << 1); j < len; j += i << 1) {
const int *wn = w;
for(int k = j; k < j + i; k ++, wn += t) {
int t1 = a[k], t2 = (ll) *wn * a[k + i] % mod;
a[k] = (t1 + t2) % mod; a[k + i] = (t1 - t2) % mod;
}
}
}
if(w == inv_w)
for(int i = 0, v = - (mod - 1) / len; i < len; i ++)
a[i] = (ll) a[i] * v % mod;
}
int n, m, Map[30], a[N], b[N], c[N], sum[N], ans[N];
char s[N], t[N];
void multi(int *x, int *y) {
fill(x + n, x + len, 0); fill(y + m, y + len, 0);
NTT(x, w); NTT(y, w);
for(int i = 0; i < len; i ++) x[i] = (ll) x[i] * y[i] % mod;
NTT(x, inv_w);
}
int main() {
mt19937 rnd(time(0));
static int p[30];
for(int x, i = 1; i <= 26; i ++) scanf("%d", &x), p[x] = i;
for(int i = 1; i <= 26; i ++) Map[i] = (Map[i - 1] + rnd() % mod) % mod;
scanf("%s%s", t, s); n = strlen(s); m = strlen(t);
for(int i = 0; i < n; i ++) a[i] = Map[s[i] - 'a' + 1], b[i] = Map[p[s[i] - 'a' + 1]];
for(int i = 0; i < m; i ++) c[i] = Map[t[i] - 'a' + 1];
int x = 0;
for(int i = 0; i < m; i ++) (x += qpow(c[i], 4)) %= mod;
for(int i = 0; i < n - m + 1; i ++) ans[i] = x;
for(int i = 0; i < n; i ++) {
sum[i] = (ll) a[i] * b[i] % mod * a[i] % mod * b[i] % mod;
if(i) (sum[i] += sum[i - 1]) %= mod;
}
for(int i = 0; i < n - m + 1; i ++) {
(ans[i] += sum[i + m - 1]) %= mod;
if(i) (ans[i] += mod - sum[i - 1]) %= mod;
}
static int ta[N], tb[N]; InitNTT(n + m);
for(int i = 0; i < n; i ++) ta[i] = ((ll) a[i] * a[i] + (ll) b[i] * b[i]) % mod;
for(int i = 0; i < m; i ++) tb[m - 1 - i] = (ll) c[i] * c[i] % mod;
multi(ta, tb);
for(int i = m - 1; i < n + m - 1; i ++) {
(ans[i - m + 1] += ta[i]) %= mod;
}
for(int i = 0; i < n; i ++) ta[i] = (a[i] + b[i]) % mod;
for(int i = 0; i < m; i ++) tb[m - 1 - i] = (ll) c[i] * c[i] % mod * c[i] % mod;
multi(ta, tb);
for(int i = m - 1; i < n + m - 1; i ++) {
(ans[i - m + 1] += -2ll * ta[i] % mod) %= mod;
}
for(int i = 0; i < n; i ++) ta[i] = ((ll) a[i] * a[i] % mod * b[i] % mod + (ll) a[i] * b[i] % mod * b[i] % mod) % mod;
for(int i = 0; i < m; i ++) tb[m - 1 - i] = c[i];
multi(ta, tb);
for(int i = m - 1; i < n + m - 1; i ++) {
(ans[i - m + 1] += -2ll * ta[i] % mod) %= mod;
}
for(int i = 0; i < n; i ++) ta[i] = (ll) a[i] * b[i] % mod;
for(int i = 0; i < m; i ++) tb[m - 1 - i] = (ll) c[i] * c[i] % mod;
multi(ta, tb);
for(int i = m - 1; i < n + m - 1; i ++) {
(ans[i - m + 1] += 4ll * ta[i] % mod) %= mod;
}
for(int i = 0; i < n - m + 1; i ++) {
// printf("%lld !
", ans[i]);
putchar(ans[i] == 0 ? '1' : '0');
}
return 0;
}