前言
Codeforces Round 836 (Div. 2)
C. Almost All Multiples
这题挺妙的。
很容易发现 $ n% x==0$ 时无解。
让 \(p[x]=n,p[1]=x,p[n]=1\) 就是一个可行解。
但此题要求字典序最小，我们以 \(8,2\) 为例。
现在的序列：
2 8 3 4 5 6 7 1
字典序最小的序列：
2 4 3 8 5 6 7 1
可以发现每次都把 \(n\) 向后移，而且这个可以交换的位置构成了一个链：\(x,x_1,x_2 \cdots n\)，这个链的所有值满足 \(p[x_i] \mod x_{i-1} = 0,p[x_{i-1}] \mod x_i=0\)。
按照上面的判定条件跑一遍即可。
code。
D. Range = √Sum
我们先看当 \(n\) 为偶数的情况。
设 \(mid=n/2\)，可以构造出 \(mid,mid+1,\cdots n-1,n+1,n+1,\cdots n+mid\)。
这里很好证明。
\(max-min=n\)。
\(sum=\dfrac{(mid+mid+n)\times (n+1)}{2}-n=n^2\)。
\(sqrt{sum}=max-min=n\)。
那把它推展到奇数。
观察一下 \(4\) 构成的序列：
2 3 5 6
想办法变成 \(3\) 个数，最好操作的就是把 \(3\) 去掉，其余的加一。变成：
3 6 7
满足条件。
推广到整个正奇数集，先构造出 \(n+1\) 的序列，然后把 \(n\) 去掉，其余的加一。
证明：
因为 \(n\) 一定被包含于 \(n+1\) 的序列中，可以去掉 \(n\)。
为了保持总和不变，剩下的 \(n\) 个数都加一。
由于 \(n+1\) 的序列中的数各不相同，都加一后也一定不同，保证了 \(n\) 的序列的不重性。
code。
E. Tick, Tock
待补。
F. Decent Division
待补。
Codeforces Round 840 (Div. 2)
C.Another Array Problem
可以发现：
-
\(n==2\)，\(ans=max(a[1] + a[2], 2 * abs(a[1] - a[2]))\)。
-
\(n==3\)，\(ans=max(1ll * a[1] + 1ll * a[2] + 1ll * a[3], max(1ll * 3 * a[1], max(1ll * 3 * abs(a[2] - a[3]), max(1ll * 3 * abs(a[1] - a[2]), 1ll * a[3] * n))))\)
-
\(n>3\)，\(ans=maxx*n\)。
因为只要对一个区间连续两次操作就可以变成 \(0\)，\(n>3\) 时无论怎么变都不如把所有数变成最大值(有点不好发现)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, maxx;
int a[N];
void solve()
{
scanf("%d", &n);
maxx = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
maxx = max(maxx, a[i]);
}
if (n >= 4)
return printf("%lld\n", 1ll * n * maxx), void();
if (n == 2)
return printf("%d\n", max(a[1] + a[2], 2 * abs(a[1] - a[2]))), void();
if (n == 3)
return printf("%lld\n", max(1ll * a[1] + 1ll * a[2] + 1ll * a[3], max(1ll * 3 * a[1], max(1ll * 3 * abs(a[2] - a[3]), max(1ll * 3 * abs(a[1] - a[2]), 1ll * a[3] * n))))), void();
printf("%d\n", a[1]);
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
solve();
}
D. Valid Bitonic Permutations
看到有好几种方法，用组合数可达到 \(O(n)\)。
但这里还是用 \(O(n^2)\) 的 dp。
可以知道峰顶一定是 \(n\)，那就可以枚举峰顶来解决。
设 \(f[i][j]\) 表示填 \(i\) 时，左边填了 \(j\) 个数的方案数。
对于不是 \(X,Y\) 的数：
\(f[i][j]+=f[i-1][j],f[i][j+1]+=f[i][j]\)
如果这个数是 \(X\)。
如果 \(X \ge I\)，\(f[i][I]+=f[i-1][I-1]\)，因为 \(I\) 前面最多放 \(I-1\) 个数。
如果 \(X \ge n-I+1\)，\(f[i][X-(n-I+1)]+=f[i-1][X-(n-I+1)]\)，因为 \(I\) 后面最多填 \(n-I+1\) 个，前面就填 \(X-(n-I+1)\)。
\(Y\) 同理。
最后统计答案时如果 \(Y\) 为 \(n\) 时就输出 \(f[n-1][J-1]\)，否则就求 \(\sum_{i=1}^{n-2} f[n-1][i]\)。
还有一种更好写的，alex wei 的记忆化搜索：code。
Codeforces Round 948 (Div. 2)
B. Binary Colouring
卡我一个小时。
先二进制拆分，求出 \(01\) 序列。
考虑有相邻的如 \(14\)。
\(0,1,1,1\)
可以知道：\(2^x+2^{x+1}=2^{x+2}-2^{x}\)。
那上序列可改为：\(0,-1,0,2\)。
有知道 \(2\times 2^x=2^{x+1}\)。
序列又可改为 \(0,-1,0,0,1\)。
此题解决。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[40];
void solve()
{
scanf("%d",&n);
memset(a,0,sizeof a);
int now=n,m=0;
for(int i=31;i>=0;i--)
{
if(now-(1<<i)>=0)
{
now-=(1<<i);
a[i]=1;
m=max(m,i);
}
}
for(int i=0;i<=m;i++)
{
if(a[i]==2) a[i]=0,a[i+1]++;
if(a[i]==1&&a[i+1]==1)
{
a[i]=-1,a[i+1]=0,a[i+2]++;
}
}
if(a[m+1]) m++;
printf("%d\n",m+1);
for(int i=0;i<=m;i++)
printf("%d ",a[i]);
puts("");
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
C. Nikita and LCM
先排序，计算所有值的 lcm 记为 \(ss\)，当 \(ss \neq a[n]\)，或再计算时就大于 \(10^9\)，答案为 \(n\)。
由于 \(ss\) 一定小于 \(10^9\)，可以枚举 \(ss\) 的因数作为序列的 lcm，所有它的因数加进来只会使最小公倍数大，且不会超过枚举的最小公倍数。
最后判断是否与枚举 lcm 的相同，记录答案即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2020;
int n, a[N], ans;
map<long long, int> vis;
int gcd(int x, int y)
{
if (!y)
return x;
return gcd(y, x % y);
}
void check(int x)
{
int res = 1, cnt = 0;
for (int i = 1; i <= n; i++)
{
if (x % a[i] == 0)
{
int d = gcd(res, a[i]);
res = res / d * a[i];
cnt++;
}
}
if (res == x)
ans = max(cnt, ans);
}
void solve()
{
scanf("%lld", &n);
vis.clear(), ans = 0;
int ss = 1;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
{
vis[a[i]] = 1;
int d = gcd(ss, a[i]);
ss = ss / d;
ss *= a[i];
if (ss > 1e9)
{
printf("%lld\n", n);
return;
}
}
if (ss != a[n])
{
printf("%lld\n", n);
return;
}
for (int i = 1; i * i <= ss; i++)
{
if (ss % i == 0)
{
if (!vis[i])
check(i);
if (!vis[ss / i])
check(ss / i);
}
}
printf("%lld\n", ans);
}
signed main()
{
int T;
scanf("%lld", &T);
while (T--)
solve();
return 0;
}
D. XORificator
很有意思的一道题。
可以知道当确定 \((i,j)\) 为 \(1\)，且该列是特殊列时，可以确定剩下的操作数，枚举 \(n*m\) 次。
此时的问题时每变化一次如何 \(O(1)\) 的求出特殊列数，用到 hash。
用 hash 记录下枚举每一个位置操作的 01 串，放到桶中记录次数，记录最多的即可。
code 是标程，配上注释。
标程用的 Zobrist hashing。
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<bool>> table(n, vector<bool>(m));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
char c;
cin >> c;
table[i][j] = c - '0';
}
}
vector<long long> rands(n), rands2(n);//双 hash
for (int i = 0; i < n; ++i)//生成记录操作 01 序列的每个位置的随机数
{
rands[i] = rnd();
rands2[i] = rnd();
}
map<pair<long long, long long>, int> ans;//双 hash 的桶
int res = 0;
pair<int, int> ind_ans = {0, 0};
for (int j = 0; j < m; ++j)
{
long long summ = 0, summ2 = 0;
for (int i = 0; i < n; ++i)//记录如果全部变为 $0$ 的操作序列
{
if (table[i][j])
{
summ ^= rands[i];
summ2 ^= rands2[i];
}
}
for (int i = 0; i < n; ++i)//一位一位枚举
{
summ ^= rands[i];
summ2 ^= rands2[i];
ans[{summ, summ2}]++;
if (res < ans[{summ, summ2}])
{
res = ans[{summ, summ2}];
ind_ans = {j, i};
}
summ ^= rands[i];
summ2 ^= rands2[i];//记得复原
}
}
cout << res << "\n";
string inds(n, '0');
for (int i = 0; i < n; ++i)//确定操作方案
{
if (table[i][ind_ans.first])
{
if (i != ind_ans.second)
{
inds[i] = '1';
}
}
else if (ind_ans.second == i)
{
inds[i] = '1';
}
}
cout << inds << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--)
solve();
return 0;
}
E 题交互题不会。
Educational Codeforces Round 165 (Rated for Div. 2)
B. Shifts and Sorting
模拟一下，把 \(1\) 向后并到下一个 \(1\) 上，依次类推，统计答案即可。记得开 long long。
C. Minimizing the Sum
首先可以想到 dp。
定义：\(f[j][i]\) 为 \([0,i]\) 这个区间操作了 \(j\) 次的最小值。
可以知道这 \(j\) 次操作的位置一定是一段一段的，可以看到此题的 \(k<10\)，那么就可以预处理连续操作一段的值。
定义 \(pre[i][j]\) 为 \([i,i+j]\) 这个区间操作 \(j\) 次的总和，预处理即可。
这样就可以推出式子：
\[f[j][i]=min(f[j-h][i-h-1]+pre[i-h][h]),h \in[0,min(i-1,j)] \]code:
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 10;
int n, a[N], k;
long long f[12][N], pre[12][N];
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
pre[0][i] = 1ll * a[i];
for (int j = 1; j <= k; j++)
pre[j][i] = min(pre[j - 1][i], 1ll * a[i + j]);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
pre[j][i] *= (j + 1);
for (int i = 1; i <= n; i++)
{
f[0][i] = f[0][i - 1] + a[i];
for (int j = 1; j <= k; j++)
{
f[j][i] = f[j][i - 1] + a[i];
for (int h = 1; h <= min(i - 1, j); h++)
f[j][i] = min(f[j][i], f[j - h][i - h - 1] + pre[h][i - h]);
}
}
cout << f[k][n] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
D. Shop Game
先看 Bob 的策略：在 Alice 购买的中挑选卖出价最大的 \(k\) 个免费，剩下付钱。
就看 Alice 如何挑才能使利润最大。
先按卖出价从大到小排序，当一个一个放进 Alice 的挑选集合中，可以保证前 \(k\) 个一定是最大的。
但我们可以发现，只要确定免费的 \(k\) 个，后面只要有利润，Alice 把它挑入一定是最优的，可以预处理后缀 suc[i] 表示从 \(i\) 到 \(n\) 的利润和。
最后枚举，把枚举的买入价加入大根堆中，超过 \(k\) 个就 \(pop()\)，因为 Alice 一定想让免费的少一些。
#include "bits/stdc++.h"
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 2e5 + 10;
int n, k, suc[N];
pii a[N];
bool cmp(pii x, pii y)
{
if (x.second != y.second)
return x.second > y.second;
return x.first > y.first;
}
void solve()
{
memset(suc,0,sizeof suc);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].first;
for (int i = 1; i <= n; i++)
cin >> a[i].second;
sort(a + 1, a + 1 + n, cmp);
for (int i = n; i >= 1; i--)
suc[i] = suc[i + 1] + max(0ll, a[i].second - a[i].first);
if (!k)
return cout << suc[1] << "\n", void();
priority_queue<int> q;
int sum = 0, ans = 0;
for (int i = 1; i <= n; i++)
{
q.push(a[i].first);
sum += a[i].first;
if (!q.empty() && q.size() > k)
sum -= q.top(), q.pop();
if (q.size() == k)
ans = max(ans, suc[i + 1] - sum);
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--)
{
solve();
}
return 0;
}
E. Unique Array
可以知道，当改变了一个数后，跨越这个数的区间都是合法的，我们把区间分为一段一段的，每一段区间中的任何子区间都是合法的，所以这道题就是找最小的划分区间的方法使每一个区间都合法。
显然每加入一个数就判断这个区间是否合法，如果不合法就划区间，这样可以使段数最少。
用线段树维护区间 \([l,r]\) 中仅出现一次的数的个数。
用两个数组 t1,t2，记录某个数出现的上两次，当加入一个数时让 \([t1[x]+1,t2[x]]\) 减一，因为这个区间 \(x\) 这个数出现了两次，让 \([t2[x]+1,i]\) 加一，因为这个区间出现了一个新数出现了一次。
询问 \([pre,i]\) 的个数，pre 表示这一段的开始。
线段树只需要区间修改与区间查询最小值。
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 10;
struct node
{
int minn, tag, son[2];
} t[N << 2];
int n, t1[N], t2[N];
void pushup(int x)
{
t[x].minn = min(t[x << 1].minn, t[x << 1 | 1].minn);
}
void pushdown(int x)
{
if (!t[x].tag)
return;
int ls = x << 1, rs = x << 1 | 1;
t[ls].minn += t[x].tag, t[rs].minn += t[x].tag;
t[ls].tag += t[x].tag, t[rs].tag += t[x].tag;
t[x].tag = 0;
}
void build(int p, int l, int r)
{
t[p].son[0] = l, t[p].son[1] = r, t[p].minn = 0, t[p].tag = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void change(int p, int x, int y, int val)
{
if (x > y)
return;
if (t[p].son[0] > y || t[p].son[1] < x)
return;
if (x <= t[p].son[0] && t[p].son[1] <= y)
{
t[p].tag += val;
t[p].minn += val;
return;
}
pushdown(p);
int mid = (t[p].son[0] + t[p].son[1]) >> 1;
if (x <= mid)
change(p << 1, x, y, val);
if (mid < y)
change(p << 1 | 1, x, y, val);
pushup(p);
}
int ask(int p, int x, int y)
{
if (x <= t[p].son[0] && t[p].son[1] <= y)
return t[p].minn;
pushdown(p);
int mid = (t[p].son[0] + t[p].son[1]) >> 1, res = n;
if (x <= mid)
res = min(res, ask(p << 1, x, y));
if (mid < y)
res = min(res, ask(p << 1 | 1, x, y));
return res;
}
void solve()
{
cin >> n;
for (int i = 0; i <= n; i++)
t1[i] = t2[i] = 0;
build(1, 1, n);
int pre = 1, ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
change(1, t1[x] + 1, t2[x], -1);
change(1, t2[x] + 1, i, 1);
t1[x] = t2[x];
t2[x] = i;
if (ask(1, pre, i) == 0)
{
ans++;
pre = i + 1;
}
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}