CodeForces1754
注：所有代码均为场上所书
Technical Support
解析：
题目大意
给定一个只包含大写字母 \(\texttt{Q}\) 和 \(\texttt{A}\) 的字符串，如果字符串里的每一个 \(\texttt{Q}\) 都能与在其之后的 \(\texttt{A}\) 一一对应地匹配，则输出字符串 \(\texttt{Yes}\)，否则输出字符串 \(\texttt{No}\)。注意，可以有 \(\texttt{A}\) 没有被匹配，但每个 \(\texttt{Q}\) 必须成功地匹配。
思路：
变相的考了括号序列，如果令 Q 为 1，A 为 -1，那么原序列最终的和必须 \(\leq 0\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
inline int read ()
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar (); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar (); }
return x * f;
}
int n, sum;
bool solve ()
{
n = read (); sum = 0;
for (int i = 1; i <= n; i++)
{
char ch = getchar ();
if (ch == 'Q') sum++;
else sum--;
sum = max (0, sum); // 不可能回答了负数个问题
}
if (sum <= 0) return true;
else return false;
}
signed main()
{
int t = read ();
while (t--) puts(solve () ? "Yes" : "No");
return 0;
}
Kevin and Permutation
解析：
题目大意：
求一个 \(1\sim n\) 的排列 \(p\)，使得 \(\min\limits_{i=1}^{n-1}\lvert p_{i+1}-p_i\rvert\) 最大。
思路：
首先最大值一定是 \(\lfloor\frac{n}{2}\rfloor\)，考虑构造：
\(\lfloor\frac{n}{2}\rfloor,2\times\lfloor\frac{n}{2}\rfloor,3\times\lfloor\frac{n}{2}\rfloor,\cdots\lfloor\frac{n}{2}\rfloor-1,2\times \lfloor\frac{n}{2}\rfloor-1,\cdots,2,\lfloor\frac{n}{2}\rfloor+2,\cdots,1,\lfloor\frac{n}{2}\rfloor+1\)。
不懂看代码。
code：
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
inline int read ()
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar (); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar (); }
return x * f;
}
int n;
void solve ()
{
n = read (); int x = n / 2;
for (int j = x; j >= 1; j--)
for (int i = j; i <= n; i += x) printf ("%d ", i);
puts ("");
}
signed main()
{
int t = read ();
while (t--) solve ();
return 0;
}
Make Nonzero Sum (easy version)
解析：
题目大意
给你一个数组 \([a_1,a_2,...a_n]\) ,其中每一项 \(a_i\) 都为 \(1\) 或 \(-1\) ，你需要构造一个划分 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 使得：
-
将每一个区间内的数按照以下方法计算出\(s_i=a_{l_i}-a_{l_i+1}+a_{l_i+2}-a_{l_i+3}+...\pm a_{r_i}\)
-
对于一个合法的划分，所有的 \(s_i\) 之和为 \(0\)
如果存在这样的划分，输出任何一个，否则输出 -1 ，代表无解。
称一组区间 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 为数组 \([a_1,a_2,...a_n]\) 的划分当且仅当 \(1=l_1\leq r_1,l_2\leq r_2,l_3\leq r_3,...,,l_k\leq r_k = n\) 且对于 \(1\leq i \leq k-1\) ,均有 \(r_i+1=l_{i+1}\)
注意在本题中，你不需要最小化 \(k\)。
思路：
首先发现长度大于 \(2\) 的区间是没有意义的，因为你可以拆成若干个长度为 \(1,2\) 区间的并。
考虑现在有 \(n\) 个区间 \([1,1],[2,2],[3,3],\cdots[n,n]\)，现在要合并一些区间，使最终代价为 0。我们对数组求和，如果序列的和为奇数，显然无解，因为你最多只能拼出来 \(1/-1\)。
考虑和大于 0 的情况，那么和小于 0 只需要把原数组取反即可。
我们设 \(b_i\in\{0,1\}\) 表示第 \(i\) 个位置是否被一个长度为 \(2\) 的区间包括。那么如果有 \(b_{i-1}=0\and b_i=0\and a_i=1\)，那么可以把 \([i-1,i-1]\) 和 \([i,i]\) 拼成 \([i-1,i]\)。这样第二个 1 在算贡献的时候就从 \(+1\) 变成了 \(-1\)。
code
#include <bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define mk make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pii;
const int N = 2e5 + 10;
inline int read ()
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar (); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int n;
int a[N];
bool vis[N];
vector <pii> ans;
void solve ()
{
n = read (); int sum = 0;
for (int i = 1; i <= n; i++) a[i] = read (), sum += a[i];
if (sum & 1) return puts("-1"), void ();
if (sum < 0) { sum = -sum; for (int i = 1; i <= n; i++) a[i] = -a[i]; } sum /= 2;
for (int i = 2; i <= n && sum; i++)
{
if (a[i] > 0 && !vis[i - 1])
{
vis[i - 1] = vis[i] = true;
ans.eb (i - 1, i);
sum--;
}
}
for (int i = 1; i <= n; i++) if (!vis[i]) ans.eb (i, i);
sort (ans.begin (), ans.end ());
printf ("%d\n", (int)ans.size ());
for (auto i : ans) printf ("%d %d\n", i.fi, i.se);
ans.clear ();
for (int i = 1; i <= n; i++) vis[i] = false;
}
signed main ()
{
int t = read ();
while (t--) solve ();
return 0;
}
Make Nonzero Sum (hard version)
解析：
题目大意：
本题目是CF1753A1的困难版本，不同之处为困难(hard)版本中 \(a\) 数组包含\(0\)。
思路：
长度为偶数的极长连续 0 段是没有意义的，可以忽略，长度为奇数的极长连续 0 段 可以合并成一个 0，其余做法见 C1。
code：
#include <bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define mk make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pii;
const int N = 2e5 + 10;
const int INF = LLONG_MAX;
inline int read ()
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar (); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int n;
int a[N];
pii pos[N];
bool vis[N];
vector <pii> ans;
void clear () { ans.clear (); for (int i = 1; i <= n; i++) vis[i] = false; }
void solve ()
{
n = read ();
int s = 0, len = 0; bool flag = false;
for (int i = 1; i <= n; i++)
{
int x = read ();
if (x)
{
if (s & 1) a[++len] = 0, pos[len] = mk (i - s, i - 1);
a[++len] = x;
pos[len] = mk (i - (s & 1 ? 0 : s), i);
s = 0; flag = true;
}
else s++;
}
if (s) a[++len] = 0, pos[len] = mk (n - s + 1, n);
if (!flag) return printf ("1\n1 %d\n", n), void ();
n = len;
int sum = 0;
for (int i = 1; i <= n; i++) sum += a[i];
if (sum & 1) return puts("-1"), void ();
if (sum < 0) { sum = -sum; for (int i = 1; i <= n; i++) a[i] = -a[i]; }
sum /= 2;
for (int i = 2; i <= n && sum; i++)
{
if (a[i] > 0 && !vis[i - 1])
{
vis[i - 1] = vis[i] = true;
ans.eb (pos[i - 1].fi, pos[i].se);
sum--;
}
}
for (int i = 1; i <= n; i++) if (!vis[i]) ans.eb (pos[i].fi, pos[i].se);
sort (ans.begin (), ans.end ());
printf ("%d\n", ans.size ());
for (auto i : ans) printf ("%d %d\n", i.fi, i.se);
clear ();
}
signed main ()
{
int t = read ();
while (t--) solve ();
return 0;
}
Factorial Divisibility
解析：
题目大意：
给定两个正整数 \(n\) 和 \(x\) 和一个正整数序列 \(a_1 \sim a_n\)。
请问 \(\sum_{i = 1}^n a_i!\) 是否能被 \(x!\) 整除。如果能则输出一个字符串 \(\texttt{Yes}\)，不能则输出字符串 \(\texttt{No}\)。
思路：
考虑合并，\(i+1\) 个 \(i!\) 可以合并成一个 \((i+1)!\)，考虑从小到大合并，如果合并之后存在一个 \(i!\)，且 \(i<x\)，那么无解，否则有解。
code：
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int N = 5e5 + 10;
const int INF = LLONG_MAX;
inline int read ()
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar (); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int n, x;
int bottle[N];
signed main ()
{
n = read (); x = read ();
for (int i = 1; i <= n; i++) bottle[read()]++;
for (int i = 1; i < x; i++)
{
if (bottle[i] % (i + 1)) return puts("No"), 0;
bottle[i + 1] += bottle[i] / (i + 1);
}
puts("Yes");
return 0;
}
Wish I Knew How to Sort
解析：
题目大意：
给定一个长度为 \(n\) 的 01 序列 \(a\) 和一种操作（\(1\le n\le2\times 10^5,\ a_i\in \{0,1\}\)），你需要用如下操作将序列从小到大排序。
- 等概率随机选取两个位置 \(i,j\ (i<j)\)，若 \(a_i>a_j\)，则交换 \(a_i,a_j\)。
注意：当 \(a_i\le a_j\) 时，不进行交换，也算作一次操作。
请你求出操作被执行的期望次数。对 998244353 取模。
思路：
考虑 CF1151F，因为 0 的个数一定，设 0 的个数有 \(cnt\) 个，考虑 \(dp_{i}\) 表示前 \(cnt\) 位有 \(i\) 个 0 的期望操作次数，那么答案为 \(dp_{cnt}\)。
考虑从 \(i-1\) 转移到 \(i\) 的过程，我们需要在 \(\frac{n\times (n-1)}{2}\) 种不同的 \((i,j)\) 中（设 \(total=\frac{n\times (n-1)}{2}\)），在 \([1,cnt]\) 中任选一个 1，在 \((cnt,n]\) 中选一个 \(0\)，此时前 \(cnt\) 个中有 \(i-1\) 个 0，这样的对数有 \([cnt-(i-1)]^2\) 种。
考虑转移：
\[dp_{i}=(dp_{i-1}+1)\times \frac{[cnt-(i-1)]^2}{total}+(dp_{i}+1)\times \frac{total-[cnt-(i-1)]^2}{total}\\ dp_{i}=dp_{i-1}\times \frac{[cnt-(i-1)]^2}{total}+\frac{[cnt-(i-1)]^2}{total}+dp_{i}\times \frac{total-[cnt-(i-1)]^2}{total}+\frac{total-[cnt-(i-1)]^2}{total}\\ dp_{i}=dp_{i-1}\times \frac{[cnt-(i-1)]^2}{total}+dp_{i}\times \frac{total-[cnt-(i-1)]^2}{total}+1\\ dp_{i}\times \frac{[cnt-(i-1)]^2}{total}=dp_{i-1}\times \frac{[cnt-(i-1)]^2}{total}+1\\ dp_{i}=(dp_{i-1}\times \frac{[cnt-(i-1)]^2}{total}+1)\times \frac{total}{[cnt-(i-1)]^2}\\ dp_{i}=dp_{i-1}+ \frac{total}{[cnt-(i-1)]^2}\\ \]至此，我们已经可以 \(\mathcal O(n\log V)\) 计算答案（其中 \(\log V\) 是快速幂求逆元）。
code：
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N = 5e5 + 10;
const int mods = 998244353;
typedef pair <int, int> pii;
inline int read ( )
{
int x = 0, f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {if (ch == '-') f = - 1; ch = getchar ();}
while (ch >= '0' && ch <='9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar (c);}
return x * f;
}
int n;
int a[N];
int dp[N];
inline int qpow (int a, int p)
{
int res = 1;
while (p)
{
if (p & 1) res = (res * a) % mods;
p >>= 1;
a = (a * a) % mods;
}
return res;
}
void solve ()
{
n = read (); int cnt = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) a[i] = read (), cnt += !(a[i]);
for (int i = 1; i <= cnt; i++) cnt2 += !(a[i]);
int total = (n * (n - 1) / 2) % mods;
for (int i = cnt2 + 1; i <= cnt; i++)
{
int t = (cnt - (i - 1)) * (cnt - (i - 1));
dp[i] = (dp[i - 1] + (total * qpow (t, mods - 2)) % mods) % mods;
}
printf ("%lld\n", dp[cnt]);
for (int i = 1; i <= cnt; i++) dp[i] = 0;
}
signed main()
{
int t = read ();
while (t--) solve ();
return 0;
}
F
解析：
题目大意
题意没读，题解没写，题目没补，留坑。
思路：
code