A
题解:
行为偶数可以这样输出:
行为奇数可以这样输出:
按照以上格式输出即可,还有别的输出格式,打表可观察出。
时间复杂度:。
代码:
正解:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int op[2][4][4] = {{{1, 1, 0, 0}, {0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}}, {{1, 0, 1, 0}, {1, 0, 1, 0}, {0, 1, 0, 1}, {0, 1, 0, 1}}};
void solve() {
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << op[n % 2][i % 4][j % 4];
}
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
// std::cin >> _;
while (_--) {
solve();
}
return 0;
}
c++代码(暴力打表找规律代码):
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
bool check(int n, int m) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum += a[i][j];
}
}
if (abs(sum - (n * m - sum)) > 1) return false;
for (int i = 2; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == a[i - 1][j] && a[i - 1][j] == a[i - 2][j]) return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = 2; j < m; j++) {
if (a[i][j] == a[i][j - 1] && a[i][j - 1] == a[i][j - 2]) return false;
}
}
for (int i = 2; i < n; i++) {
for (int j = 2; j < m; j++) {
if (a[i][j] == a[i - 1][j - 1] && a[i - 1][j - 1] == a[i - 2][j - 2]) return false;
}
}
for (int i = 2; i < n; i++) {
for (int j = m - 3; j >= 0; j--) {
if (a[i][j] == a[i - 1][j + 1] && a[i - 1][j + 1] == a[i - 2][j + 2]) return false;
}
}
return true;
}
void prf(int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j];
}
cout << '\n';
}
}
void solve() {
int n, m; cin >> n >> m;
int s = n * m;
int op = 1;
for (int i = 0; i < 1 << s; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
a[j][k] = (i >> (j * m + k) & 1);
}
}
if (check(n, m)) {
cout << "ans: " << i << '\n';
prf(n, m);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
// std::cin >> _;
while (_--) {
solve();
}
return 0;
}
/*
1010101
1010101
0101010
0101010
1010101
*/
B
题解:
操作一每次都是奇数变偶数、偶数变奇数,所以最终的奇数次数和偶数次数会一直保持不变。
现在考虑操作二是找值互质的两个下标数对,已知 ,故我们可以使得值相邻的数形成一个奇数集合或者偶数集合
例如:
这样我们通过操作一拉进两个奇偶不同的数值之间的距离,当距离之差为 时,我们再通过操作二化为一个集合,最后化为全一样的形式。
先特判一开始一样的情况;再特判只有偶数的情况;再特判只有奇数的情况,如果有某对下标满足 ,那么就能凑出至少一个奇数和偶数,这样就一定满足,如果没有满足的,就无法做到。
所以这题只要即有奇数又有偶数即可完成全一样。
时间复杂度:。
代码:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n; cin >> n;
vector<int> a(n + 1);
int d = 0, sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i]; sum += (a[i] & 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (std::gcd(a[i], a[j]) == 1) d = 1;
}
}
sort(a.begin() + 1, a.end());
if (a[1] == a[n]) {
cout << "YES\n";
return;
}
if (sum == 0 || (sum == n && !d)) {
cout << "NO\n";
return;
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
std::cin >> _;
while (_--) {
solve();
}
return 0;
}
C
题解:
特判一种特殊情况,就是形如数组 为
这种形式,那么说明数组
。
现在假设数组 里面有出现重复数字,令其为
,那么这个
一定是原数组
中所有数的
,所以:
- 若
,说明
,且这个数
只能恰好出现一次,因为删除这个数后,导致整体的
变小了;
- 若
,说明
这个数要么
且出现了多次,要么是
的数,然后在这里我们肯定要先贪心
的情况,先将没有出现的
出现多次,这里多次我们可以选择先让
出现两次,假设最后贪心完所有的
的数,其他数我们就直接用大于
的数替代即可,若还有数没贪心完或者贪心的那个数只出现了一次,那么我们就直接输出
-1即可。
时间复杂度:。
代码:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n; cin >> n;
vector<int> a(n + 1), vis(n);
bool fg = false;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] >= n) fg = true;
else vis[a[i]]++;
}
if (fg) {
cout << "-1\n";
return;
}
int sum = 0;
for (int i = 0; i < n; i++) sum += (vis[i] > 0);
if (sum == n) {
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << '\n';
return;
}
int m = -1;
for (int i = n - 1; i >= 0; i--) {
if (!vis[i]) continue;
if (m == -1) {
if (vis[i] == 1) {
cout << "-1\n";
return;
}
m = i;
} else {
if (vis[i] > 1) {
cout << "-1\n";
return;
}
}
}
vector<int> b(n + 1, -1), vis2(n);
for (int i = 1; i <= n; i++) {
if (a[i] != m) {
b[i] = a[i];
vis2[a[i]] = 2;
}
}
int tot = 0;
for (int i = 1; i <= n; i++) {
if (b[i] != -1) continue;
while (tot < m && vis2[tot] == 2) tot++;
if (tot != m) {
b[i] = tot;
vis2[tot]++;
} else {
b[i] = m + 1;
}
}
while (tot < m && vis2[tot] == 2) tot++;
if (tot != m) {
cout << "-1\n";
return;
}
for (int i = 1; i <= n; i++) {
cout << b[i] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
std::cin >> _;
while (_--) {
solve();
}
return 0;
}
D和E
题解:
对于D
操作定义为:若父节点为 0 且子节点为 1,则可以交换。这意味着:
-
单向性:权值为
的棋子只能从子树向根节点方向移动,不能向下移动。
-
合法性:最终状态下,若节点
的条件
,则该位置不能放置权值
(即
必须为
)。换言之,所有的
最终必须停留在
的节点上。
-
子树限制:由于
只能向上走,对于任何一棵子树,其最终拥有的
的数量不能超过其初始时拥有的
的数量。
本题要求计算不同合法最终状态的数量。
状态
:表示在节点
的子树中,最终放置了
个权值为
的棋子的方案数。
:节点
子树内初始时权值为
的棋子总数。
转移
树形背包dp:
-
合并子树:遍历
的每个子节点
,将
的状态合并到
中:
在合并过程中,需保证
(子树
分到的
不能超过其初始值)。
-
处理根节点
: 在合并完所有子树后,考虑节点
本身。 如果
,说明
可以放置一个
。此时,子树内有
个
的方案可以转化成子树内有
个
的方案(即将一个
留在根节点
):
答案为 ,其中
是整棵树初始时
的总数。
对于E
本题要求所有合法最终状态的 最小操作次数之和。
- 最小操作次数:由于
只能向上移动,从初始状态
到最终状态
的最小步数等于每个
移动的距离之和。
- 边贡献法:对于树上的每一条边
,其被跨越的次数等于:初始时子树
内
的数量 - 最终留在子树
内
的数量。 设初始数量为
,最终数量为
,则该边对总步数的贡献为
。
状态
:方案数(同 D 题)。
:在
的子树内,所有合法方案的 内部边贡献总和。
转移
在合并子节点 到父节点
时,我们需要维护方案数和步数和:
-
方案数更新(同背包合并):
-
步数和更新: 当子树
分配了
个
时,边
的贡献是
。
-
:原
子树的步数和乘以新子树的方案数。
-
:新
子树的步数和乘以原子树方案数。
-
:跨越边
产生的额外步数。
-
-
处理根节点
: 同
题,若
,则节点
可以选择接纳一个从下方移动上来的
:
代码:
D题直接输出即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
inline int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
inline int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
void solve() {
int n; cin >> n;
vector<vector<int>> g(n + 1);
vector<int> a(n + 1), s(n + 1);
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int k = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
k += a[i];
}
for (int i = 1; i <= n; i++)
cin >> s[i];
vector<int> siz(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(n + 1)), dpc(n + 1, vector<int>(n + 1));
function<void(int, int)> dfs = [&](int u, int fa) {
dp[u][0] = 1;
for (int &v : g[u]) {
if (v == fa) continue;
dfs(v, u);
for (int i = siz[u] + siz[v]; i >= 0; i--) {
dpc[u][i] = add(1LL * dpc[u][i] * dp[v][0] % mod, 1LL * dp[u][i] * add(dpc[v][0], 1LL * dp[v][0] * siz[v] % mod) % mod);
dp[u][i] = 1LL * dp[u][i] * dp[v][0] % mod;
for (int j = min(i, siz[v]); j >= max(1, i - siz[u]); j--) {
dpc[u][i] = add(dpc[u][i], add(1LL * dpc[u][i - j] * dp[v][j] % mod, 1LL * dp[u][i - j] * add(dpc[v][j], 1LL * dp[v][j] * (siz[v] - j) % mod) % mod));
dp[u][i] = add(dp[u][i], 1LL * dp[u][i - j] * dp[v][j] % mod);
}
}
siz[u] += siz[v];
}
if (s[u]) {
for (int i = siz[u]; i >= 0; i--) {
dp[u][i + 1] = add(dp[u][i + 1], dp[u][i]);
dpc[u][i + 1] = add(dpc[u][i + 1], dpc[u][i]);
}
}
siz[u] += a[u];
};
dfs(1, 0);
cout << dpc[1][k] << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
std::cin >> _;
while (_--) {
solve();
}
return 0;
}
F
题解:
我们知道对于任意的 ,都有
,并且它们之间是互不影响的,所以我们可以把每个位置看成一个多项式,对于位置
,看成
,那么将前面
个位置乘积起来就是:
因为 的次幂对应的就是当前前缀所选正序对数,我们需要选取
个数给前面进行正序对排列,后面
个数任意全排列即可,所以对于每组询问
,对应的方案数便是:
前面那部分可用前缀乘和前缀乘逆元预处理,现在考虑后面部分的求和,由欧拉五边形定理可知:
令 为:
当 时,有:
当 时,由于
,所以
,那么可以通过容斥去重得:
然后可以预处理多项式 的前缀和,就可以
的时间复杂度得到多项式
的对应系数。
令 ,是常见的生成函数求逆元,得:
故:
由于已知多项式 和多项式
的对应系数,故我们可以通过
算法来实现多项式之间的乘积,时间复杂度为
。
然后对询问进行离线处理,按照 从小到大排序,依次求出每个
对应的多项式
,然后前缀和预处理系数再差分得到每次询问的答案。
最终总时间复杂度为:(
是计算去重后的之和)。
代码:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 998244353;
const int D = 21;
const int N = (1 << D) + 1;
const int M = 1e6 + 5;
const int g = 3;
inline int add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
inline int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}
int qp(int a, int b) {
int res = 1;
for (; b; b >>= 1LL, a = 1LL * a * a % mod) {
if (b & 1) res = 1LL * res * a % mod;
}
return res;
}
int c[N], pc[N], fac[M], invfac[M], inv[N];
int G[N], H[N], rev[N], GG[2][D][N >> 1];
int C(int n, int m) {
if (n < m) return 0;
return 1LL * fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}
const int invg = qp(g, mod - 2);
void init() {
c[0] = 1;
for (int k = 1; ; k++) {
int x = k * (3 * k - 1) / 2;
int y = k * (3 * k + 1) / 2;
if (x >= N && y >= N) break;
int v = (k & 1) ? mod - 1 : 1;
if (x < N) c[x] = v;
if (y < N) c[y] = v;
}
pc[0] = c[0];
for (int i = 1; i < N; i++) pc[i] = add(pc[i - 1], c[i]);
inv[1] = 1;
for (int i = 2; i < N; i++) {
inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
}
for (int p = 0; p < D; ++p) {
int buf0 = qp(g, (mod - 1) / (1 << (p + 1)));
int buf1 = qp(invg, (mod - 1) / (1 << (p + 1)));
GG[0][p][0] = GG[1][p][0] = 1;
for (int i = 1; i < (1 << p); ++i) {
GG[0][p][i] = 1LL * GG[0][p][i - 1] * buf0 % mod;
GG[1][p][i] = 1LL * GG[1][p][i - 1] * buf1 % mod;
}
}
fac[0] = invfac[0] = 1;
for (int i = 1; i < M; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
invfac[M - 1] = qp(fac[M - 1], mod - 2);
for (int i = M - 2; i >= 1; i--) {
invfac[i] = 1LL * invfac[i + 1] * (i + 1) % mod;
}
}
void NTT_init(int n) {
for (int i = 0; i < n; ++i) {
rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0));
}
}
void H_init(int t, int n) {
H[0] = 1;
for (int i = 1; i < n; i++) {
H[i] = 1LL * H[i - 1] * (t + i - 1) % mod * inv[i] % mod;
}
}
void G_init(int t, int n) {
for (int i = 0; i < n; i++) {
G[i] = c[i];
}
for (int i = t + 1; i < n; i++) {
G[i] = add(c[i], pc[i - t - 1]);
}
}
void NTT(int *a, int n, int op) {
assert(n < N);
for (int i = 0; i < n; i++) {
if (i < rev[i]) swap(a[i], a[rev[i]]);
}
for (int d = 1, p = 0; d < n; d <<= 1, p++) {
for (int i = 0; i < n; i += d << 1) {
int *wn = GG[op][p];
for (int k = 0; k < d; k++, ++wn) {
int x = a[i + k];
int y = 1LL * (*wn) * a[i + d + k] % mod;
a[i + k] = add(x, y);
a[i + d + k] = sub(x, y);
}
}
}
if (op) {
int invn = qp(n, mod - 2);
for (int i = 0; i < n; ++i) {
a[i] = 1LL * a[i] * invn % mod;
}
}
}
void Poly_Mul(int *f, int *h, int n) {
int m = (n << 1) - 1;
int lim = 1;
while (lim < m) lim <<= 1;
for (int i = n; i < lim; i++) {
f[i] = h[i] = 0;
}
NTT_init(lim);
NTT(f, lim, 0);
NTT(h, lim, 0);
for (int i = 0; i < lim; i++) {
f[i] = 1LL * f[i] * h[i] % mod;
}
NTT(f, lim, 1);
}
void solve() {
int n, q;
cin >> n >> q;
vector<array<int, 4>> Q(q);
for (int i = 0; i < q; i++) {
cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
Q[i][3] = i;
}
sort(Q.begin(), Q.end());
int pre = -1;
vector<int> ans(q);
for (int i = 0; i < q; i++) {
auto [t, l, r, id] = Q[i];
int m = min(1LL * (t - 1) * t / 2, 2LL * t);
if (pre != t) {
pre = t;
G_init(t, m + 1);
H_init(t, m + 1);
Poly_Mul(G, H, m + 1);
for (int j = 1; j <= m; j++) {
G[j] = add(G[j], G[j - 1]);
}
}
if (l > m) {
ans[id] = 0;
continue;
}
r = min(r, m);
ans[id] = 1LL * sub(G[r], l == 0 ? 0 : G[l - 1]) * fac[n] % mod * invfac[t] % mod;
}
for (int i = 0; i < q; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _ = 1;
// std::cin >> _;
init();
while (_--) {
solve();
}
return 0;
}
G
题解:
考虑根号分治。对于长度小于 的
,
做法是平凡的。对于长度大于等于
的
(最多有
个)。对
建后缀自动机,并计算一个长度为
的数组
,其中
,这可以简单Z函数得到。考虑后缀自动机上的一个节点
,令其对应结束下标集合为
。对于任意一个长度
,如果后缀自动机上存在一个节点
,使得
,则长度为
的前缀是美丽的。先对后缀link树做一次dfs求出
,然后把
放在后缀自动机上匹配。对于一个
,设其匹配到的节点为
,则只需要查询其后缀link树上的祖先的上式最大值即可。最终复杂度
。
代码:
#include <bits/stdc++.h>
using namespace std;
template<int sig = 26>
struct SAM {
struct node {
int len, link;
array<int, sig> next;
node(int len, int link = -1) : len(len), link(link) {
next.fill(-1);
}
};
int last;
vector<node> tr;
SAM() { init(); }
void init() {
tr.emplace_back(0, -1);
last = 0;
}
int extend(int c) {
int cur = tr.size();
tr.emplace_back(tr[last].len + 1);
int p = last;
while (p != -1 && tr[p].next[c] == -1) {
tr[p].next[c] = cur;
p = tr[p].link;
}
if (p == -1) {
tr[cur].link = 0;
} else {
int q = tr[p].next[c];
if (tr[p].len + 1 == tr[q].len) {
tr[cur].link = q;
} else {
int clone = tr.size();
tr.emplace_back(tr[p].len + 1, tr[q].link);
tr.back().next = tr[q].next;
while (p != -1 && tr[p].next[c] == q) {
tr[p].next[c] = clone;
p = tr[p].link;
}
tr[q].link = tr[cur].link = clone;
}
}
last = cur;
return last;
}
int size() {
return tr.size();
}
int len(int u) {
return tr[u].len;
}
int link(int u) {
return tr[u].link;
}
int next(int u, int c) {
return tr[u].next[c];
}
};
constexpr int M = 700;
vector<int> get_lcp(string& s, string& t) {
string p = t + "$" + s;
int sz = p.size();
vector<int> z(sz);
for (int i = 1, l = 0, r = 0; i < sz; i++) {
if (i <= r && z[i - l] < r - i + 1) {
z[i] = z[i - l];
} else {
z[i] = max(0, r - i + 1);
while (i + z[i] < sz && p[z[i]] == p[i + z[i]]) z[i]++;
}
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
vector<int> lcp(s.size() + 1, 0);
for (int i = 0; i < (int)s.size(); i++) {
lcp[i] = z[t.size() + 1 + i];
}
return lcp;
}
void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
SAM<26> sam;
vector<int> pos(n);
for (int i = 0; i < n; i++) pos[i] = sam.extend(s[i] - 'a');
int k = sam.size();
vector<int> f(k, -1);
for (int i = 0; i < n; i++) f[pos[i]] = i;
vector<vector<int>> g(k);
for (int i = 1; i < k; i++) g[sam.link(i)].push_back(i);
vector<int> a(k), b(k);
while (q--) {
string t;
cin >> t;
int m = t.size();
if (m >= M) {
auto lcp = get_lcp(s, t);
auto dfs1 = [&](auto &&self, int u) -> void {
if (f[u] != -1) a[u] = lcp[f[u] + 1];
else a[u] = 0;
for (auto v : g[u]) {
self(self, v);
a[u] = max(a[u], a[v]);
}
};
dfs1(dfs1, 0);
b[0] = a[0];
auto dfs2 = [&](auto &&self, int u) -> void {
for (auto v : g[u]) {
b[v] = max(b[u], a[v] + sam.len(v));
self(self, v);
}
};
dfs2(dfs2, 0);
int u = 0;
int len = 0;
for (int i = 0; i < m; i++) {
int c = t[i] - 'a';
while (u && sam.next(u, c) == -1) {
u = sam.link(u);
len = sam.len(u);
}
if (sam.next(u, c) != -1) {
len++;
u = sam.next(u, c);
}
int mx = len + a[u];
if (u) mx = max(mx, b[sam.link(u)]);
if (mx >= i + 1) cout << 1;
else cout << 0;
}
cout << "\n";
} else {
for (int j = 1; j <= m; j++) {
int u = 0, len = 0;
int f = 0;
for (int i = 0; i < 2 * j - 1; i++) {
int c = t[i >= j ? (i - j) : i] - 'a';
while (u && sam.next(u, c) == -1) {
u = sam.link(u);
len = sam.len(u);
}
if (sam.next(u, c) != -1) {
len++;
u = sam.next(u, c);
}
if (len >= j) {
f = 1;
break;
}
}
cout << f;
}
cout << "\n";
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
全部评论
(0) 回帖