A
注意到：
\(\sum_{i=0}^{n}x_i*10^i \equiv \sum_{i=0}^{n}x_i*(-1)^i (\text{mod} \ 11)\)
\(\sum_{i=0}^{n}x_i*10^i \equiv \sum_{i=0}^{n}x_i (\text{mod} \ 3)\)
所以无论是删去连续的 2 个 33 还是减去 33 都不会改变 \(x\text{ mod} \ 33\) 的值。
于是可以得出能让 \(x\) 值为 0 的充要条件为 \(x \equiv 0 \ (\text{mod} \ 33)\)
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int x; cin >> x;
if (x >= 33 && x % 33 == 0)cout << "Yes\n";
else cout << "No\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|
B
对于所有长度为 \(k\) 的子数组，一个数最多出现 \(k\) 次，那么要想充分地去利用那些较小的值，显然的构造就是在下标为 \(ik(ik<=n)\) 的位置填 \(i\)，这样就达到下界了。
其余数随意填即可。
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int n, k; cin >> n >> k;
vector<int>ans(n + 1);
int j = 1;
for (int i = k; i <= n; i += k)ans[i] = j++;
for (int i = 1; i <= n; i++) {
if (i % k == 0)continue;
ans[i] = j++;
}
for (int i = 1; i <= n; i++)cout << ans[i] << ' ';
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|
C
先证明一个性质：最优解一定有一个串为其本身。
对于非全 0 串，我们总能找到一组最优解的较长串的首位为 1，此时对该串往左右扩展都是不劣的。
对于全 0 串，结论显然成立。
然后从贪心的角度来考虑，我们总是想让更高位的 0 变为 1，而这个 0 可能变为 1 的 条件就是它前面有 1。
那自然有了一个算法，从左往右找到第一个符合条件的 0 ，让它和前面的每一个 1 对齐，然后从中取出最大的就是答案。
如果不存在这样的 0 （即全 0 串或全 1 串，答案是显然的）。
对上面的所有可能答案暴力比较可以得到 \(O(n^2)\) 算法。
仔细分析这个 0 的性质可以得出 \(O(n)\) 算法。因为这个 0 前面必须是一串连续 1 和 一串连续的 0，假设连续的 1 有 \(p\) 个，同时我们设这个 0 所在的那段 0 有 q 个，
那么可以确定与 0 配对的 1 的距离为 \(min(p,q)\)。更长的情况或更短的情况会导致 0 不够或者高位 1 丢失。
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
string s; cin >> s;
bool ok = 0;
int q = 0, p = 0, n = s.size();
for (int i = 0; i < s.size(); i++) {
if (!ok) {
if (s[i] == '0')continue;
else ok = 1, p++;
}
else {
if (s[i] == '1')p++;
else {
int j = i;
while (j < s.size() && s[j] == '0')q++, j++;
cout << 1 << ' ' << n << ' ';
cout << i - min(p, q) + 1 << ' ' << n - min(p, q) << '\n';
return;
}
}
}
cout << 1 << ' ' << n << ' ' << n << ' ' << n << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|
D
我们先为每个题目定义一个价值：当题目能被 1 号解决时，价值为 0 ，否则定义为能解决这道题目的人数。
这个价值可以双指针求出。设从小到大排序后第i个题目价值为 \(val[i]\)。
当每场比赛题目数为 \(k\)，可以确定一定是从小到大选不断地选 \(k\) 个题目作为一场比赛，并且该处比赛排名为所选题目最大价值加一，也就是说答案为 \(\sum_{i=1}^{\lfloor m/k \rfloor}(val[ik]+1)\)。
直接暴力枚举即可，时间复杂度为调和级数 \(O(nlnn)\)。
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int n, m; cin >> n >> m;
vector<int>a(n), b(m);
for (int i = 0; i < n; i++)cin >> a[i];
int pos = a[0];
sort(a.begin(), a.end());
for (int i = 0; i < m; i++)cin >> b[i];
sort(b.begin(), b.end());
vector<int>v;
int i = m - 1, val = 0, j = n - 1;
while (i >= 0 && b[i] > pos) {
while (a[j] >= b[i])val++, j--;
v.push_back(val);
i--;
}
while (i >= 0)v.push_back(0), i--;
sort(v.begin(), v.end());
for (int i = 1; i <= m; i++)
{
ll res = 0;
for (int j = i - 1; j < m; j += i)
{
res += b[j] + 1;
}
cout << res << " ";
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|
E
因为要求不能存在同色环。所以如果我们只考虑某一种颜色的边的话，整张图就是一个森林。那图恰好为一颗树时边数最大为 \(2n+m-1\)。
考虑所有颜色，我们最多存在 \(n*(2n+m-1)\) 条边。这个数要大于等于 \(2nm\) 。即：
\(\(m\leq2n-1\)\)
说明当 \(m\geq2n\) 时必然无解。
注意到 \(n\) 一定时，如果较大的 \(m\) 有解，那么较小的 \(m\) 也有解。所以我们尝试构造 \(m=2n-1\) 的情况，\(m\) 更小的情况直接截取部分边即可。这是一个很紧的条件，它要求每张图都是一颗树。
将左部点编号为\([1,2n]\)，右部点编号\([2n+1,2n+m]\)。
我们从最简单的链出发，很容易想到如下的一种颜色的链构造：
\[ 1,2n+1 ,2 , \cdots ,2n-1 ,2n+n-1 ,2n\]
也就是将右部点插在左部点中间。
对于 \(n-1\) 种颜色的构造，我们只需要做如下的对左部点的循环移位的操作即可：
\[ 3,2n+1 ,4 , \cdots , 2n,2n+n-2,1 ,2n+n-1 ,2\]
累积做 \(n-1\) 次循环移位。
分析可以确定每条边恰好被染成一种颜色，这是一种合法的构造。
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int n, m; cin >> n >> m;
if (m >= 2 * n)cout << "No\n";
else {
cout << "Yes\n";
vector<vector<int>>ans(2 * n, vector<int>(2 * n - 1));
for (int c = 0; c < n; c++)
{
vector<int>v;
for (int j = 0; j < 2 * n - 1; j++)
{
v.push_back((2 * c + j) % (2 * n));
v.push_back(j);
}
for (int i = 1; i < v.size(); i++) {
if (i & 1)ans[v[i - 1]][v[i]] = c;
else ans[v[i]][v[i - 1]] = c;
}
ans[(2 * c + 2 * n - 1) % (2 * n)][v.back()] = c;
}
for (int i = 0; i < 2 * n; i++)
{
for (int j = 0; j < m; j++)cout << ans[i][j] + 1 << ' ';
cout << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|
F
先对题意做一个转化：注意到 \(\lceil x/k\rceil -1 = \lfloor (x-1)/k\rfloor\) 。
也就是与 1 的差值在操作中是下取整除法，所以让 \(a[i] = a[i] - 1\) ，要求转化为使 \(a[i]\) 均为 0 。
钦定一个 \(x\) 使得 \(b_x\) 为所操作的区间的最小值，贪心可以确定我们操作的区间会扩展到单侧第一个大于 \(b_i\) 的点或边界。
这是一个经典的笛卡尔树思路，我们以 \(b_i\) 为小根堆建出树。这样所有的操作都是作用在一颗子树上。
考虑树上DP：\(dp[i][j]\)表示对以 \(i\) 为根的子树共操作 \(j\) 次，所有可能情况的最大值的最小值。
转移时，先不考虑 \(u\) 本身，这个过程就是对左右儿子做 \(min-max\) 卷积（若不存在左右儿子则全为 0），即：
\[dp[u][k]=min_{i+j=k}max(dp[ls][i],dp[rs][j])\]
因为 \(dp[u][i]\) 是关于 \(i\) 单调不增的，可以用类似归并排序的思路以 \(O(log)\) 的复杂度完成卷积。
更具体的就是，假设 \(dp[u][k]\) 的最小值为 \(max(dp[ls][i],dp[rs][j])\) ，当 \(k\) 扩展到 \(k+1\) 时，
我们让 \(dp[ls][i]\) 和 \(dp[rs][j]\) 较大的那个的第二维去加 1。
然后把 \(u\) 考虑上，我们同样可以以 \(O(log)\) 复杂度完成转移。就是讨论是否存在作用在 \(u\) 为根的子树上的操作。即：
\[ dp[u][i] = max(dp[u][i],\lfloor dp[u][i-1]/b[u]\rfloor)\]
事实上上式成立还需要一个条件，就是可以随意调换操作顺序。这可以由 \(\lfloor \lfloor x/a\rfloor/b\rfloor=\lfloor x/(ab)\rfloor\) 保证。
这里的 \(dp[u][i-1]\) 是已经考虑上 \(u\) 的结果。特别的 \(dp[u][0] = max(dp[u][0],a[u])\) 。
答案就是最小的 \(i\) 满足 \(dp[root][i]=0\) 。（其中root为笛卡尔树的根）
代码
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const ll INF = 1e18 + 1;
ll dp[N][61], a[N], b[N];
int ln[N], rn[N], n, rt;
void dfs(int u)
{
for (int i = 0; i <= 60; i++)dp[u][i] = 0;
if (ln[u] != -1) {
dfs(ln[u]);
for (int i = 0; i <= 60; i++)dp[u][i] = dp[ln[u]][i];
}
if (rn[u] != -1) {
dfs(rn[u]);
int i = 0, j = 0;
ll g[61];
memcpy(g, dp[u], sizeof g);
for (int k = 0; k <= 60; k++)
{
if (i + j < k) {
if (i == 60)j++;
else if (j == 60)i++;
else if (g[i] >= dp[rn[u]][j])i++;
else j++;
}
dp[u][k] = max(g[i], dp[rn[u]][j]);
}
}
dp[u][0] = max(dp[u][0], a[u]);
for (int i = 1; i <= 60; i++)dp[u][i] = min(max(dp[u][i], a[u]), dp[u][i - 1] / b[u]);
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i], a[i]--;
for (int i = 0; i < n; i++)cin >> b[i];
for (int i = 0; i < n; i++)ln[i] = rn[i] = -1;
vector<int>stk;
for (int i = 0; i < n; i++)
{
int last = -1;
while (!stk.empty() && b[stk.back()] > b[i])last = stk.back(), stk.pop_back();
if (!stk.empty())rn[stk.back()] = i;
if (last != -1)ln[i] = last;
stk.push_back(i);
}
rt = stk[0];
dfs(rt);
for (int i = 0; i <= 60; i++) {
if (dp[rt][i] == 0) {
cout << i << '\n';
return;
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
|