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;

}

巴特西

Codeforces Round #829 (Div. 2)/CodeForces1754

CodeForces1754

Technical Support

解析：

题目大意

思路：

code

Kevin and Permutation

解析：

题目大意：

思路：

code：

Make Nonzero Sum (easy version)

解析：

题目大意

思路：

code

Make Nonzero Sum (hard version)

解析：

题目大意：

思路：

code：

Factorial Divisibility

解析：

题目大意：

思路：

code：

Wish I Knew How to Sort

解析：

题目大意：

思路：

code：

F

解析：

题目大意

思路：

code

最新文章

热门文章