C
题解
方法一
知识点：思维.
Count the numbers that don't appear first,Each can be placed anywhere,So it is used as a replacement.
Shift the original array one place to the left as the predetermined answer array,Then start checking.If the same as the original array,Fill it with digits,If not, don't move.
Doing so is sure to construct a valid array,Because after shifting to the left, no matter whether the number is repeated or not, there must be one that is different from the corresponding position,So that number was used.因此,All numbers that appear in the original array can have one in place,The remaining positions are duplicates of the answer array,It must be able to give the supplementary digits.
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
方法二
知识点：思维.
先构造一个 \([1,...,n]\) An array of predetermined answers,Then start to check whether the corresponding position is repeated.If it is repeated, use the next number to swap with this number,It must be ensured that this position is not repeated.This can be constructed \(n-1\) 位置,The last position requires special treatment,Because if it is repeated, there is no subsequent number to change,Need to find an exchange from the front.
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007];
bool vis[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) vis[i] = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i];
vis[a[i]] = 1;
}
vector<int> v;
int cnt = 0;
for (int i = 1;i <= n;i++) {
if (!vis[i]) v.push_back(i);
else vis[i] = 0, cnt++;
}
if (cnt == 1) return false;
cout << "YES" << '\n';
for (int i = 2;i <= n;i++) {
if (vis[a[i]] || a[i] == a[i - 1]) {
cout << v.back() << ' ';
v.pop_back();
}
else {
cout << a[i] << ' ';
vis[a[i]] = 1;
}
}
if (v.empty()) cout << a[1] << '\n';
else cout << v.back() << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007], b[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a[i];
b[i] = i;
}
bool ok = true;
for (int i = 2;i <= n;i++)
ok &= a[i] == a[i - 1];
if (ok) return false;
for (int i = 1;i <= n - 1;i++)
if (a[i] == b[i]) swap(b[i], b[i + 1]);
if (a[n] == b[n]) {
for (int i = 1;i <= n - 1;i++) {
if (a[i] != b[n]) {
swap(b[i], b[n]);
break;
}
}
}
cout << "YES" << '\n';
for (int i = 1;i <= n;i++) cout << b[i] << ' ';
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
F
题解
方法一
知识点：模拟,贪心.
Store numbers in an array,The other array is indexed to the simulated linked list,Each time the deletion is completed, the subscript points to be modified,as a chain.Use an array to record whether it has been deleted.
由于是从左往右遍历,To expand to the left, use a linked list array,Expansion to the right just adds one.If the right endpoint touches the number that was deleted before, it can end directly,Because the number is only possible to extend here to the left through the previous one,That is to say, all numbers after that are deleted,不需要继续了.
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
方法二
知识点：贪心.
A simplest way of writing,Process the entered points directly online.Use a deque to store numbers,Enter a number and match it with the end of the queue to see if it can be deleted,If it cannot be deleted, it will be stored;If the team is empty, it is also directly deposited.
Finally finished typing,We only dealt with numbers that can be deleted to the left,No handling of the right tail-to-head looping nature is removed,So need to continue processing.
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
int a[100007], p[100007];
bool vis[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, x;
cin >> n >> x;
int cnt = 0;
for (int i = 0;i < n;i++) cin >> a[i];
for (int i = 0;i < n;i++) p[i] = (i - 1 + n) % n;
for (int t = 0;t < n;t++) {
if (vis[t]) continue;
int i = t, j = (t + 1) % n;
if (vis[j]) break;
while (i != j && (a[i] == a[j] || a[i] + a[j] == x)) {
vis[i] = 1;
vis[j] = 1;
cnt++;
i = p[i];
j = (j + 1) % n;
if (vis[j]) break;
}
p[j] = i;
}
cout << cnt << '\n';
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, x;
cin >> n >> x;
deque<int> dq;
int cnt = 0;
for (int i = 0, tmp;i < n;i++) {
cin >> tmp;
if (!dq.empty() && (dq.back() == tmp || dq.back() + tmp == x)) dq.pop_back(), cnt++;
else dq.push_back(tmp);
}
while (dq.size() >= 2 && (dq.front() == dq.back() || dq.front() + dq.back() == x)) {
dq.pop_front();
dq.pop_back();
cnt++;
}
cout << cnt << '\n';
return 0;
}
G
题解
知识点：字符串,模拟.
分类讨论一下.
\(n=1\) ,最短长度 \(2\) , a 和 . ,\(2\) 种.
\(n=2\) ,最短长度 \(2\) ,ab 、 a. 、 .b 、 .. 、 .* 、 .+ ;It's ok if the two letters are the same,a+ 、 a* ,\(6\) 或 \(8\) 种.
\(n\geq3\) ,最短长度 \(2\) ,.* 、 .+ ;It's ok if the letters are the same,a+ 、a* ,\(2\) 或 \(4\) 种.
也就是说,( ) | ? 都没用,\(998244353\) 也没用.Fraud questionqwq.
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
while (q--) {
string s;
cin >> s;
int n = s.size();
if (n == 1) cout << 1 << ' ' << 2 << '\n';
else if (n == 2) {
cout << 2 << ' ';
if (s[0] == s[1]) cout << 8 << '\n';
else cout << 6 << '\n';
}
else if (n >= 3) {
bool ok = true;
for (auto c : s) ok &= s[0] == c;
cout << 2 << ' ';
if (ok) cout << 4 << '\n';
else cout << 2 << '\n';
}
}
return 0;
}
J
题解
知识点：计数dp,排列组合.
The first is the transformation of a routine interval sum problem into a prefix sum end point problem.As the range of numbers is \([0,k-1]\) ,在 \(\mod k\) The prefix sum below is uniquely corresponding,That is, a prefix sum sequence can uniquely determine an original sequence,So we can do this by directly considering prefixes and sequences,Instead consider the original sequence.
The topic requires interval and can be \(k\) Divisible intervals are contributing,That is, two different endpoints of the prefix and the sequence \(i,j\) 满足 \(sum[i] \equiv sum[j](\mod k)\) It corresponds to an interval satisfaction.特别地,当 \(sum[i] = 0\) 时,That is, single-point division,Oneself can become a zone to be judged.
Let's take a look at a simple version first,A sequence is given,Find an interval that satisfies the interval sum can be \(k\) 整除的个数,即贡献.根据上面说的,This sequence corresponds to a unique prefix and sequence,Whereas prefixes and sequences only need two distinct endpoints to satisfy the modulo \(k\) The remainder is the same or a point can be removed by itself \(k\) 整除即可.因此,找出 \([0,k-1]\) The number of times each number appears in the prefix sum sequence \(cnt_i\),So the contribution of each number is \(\sum C_{cnt_i}^2\) ,Then we will judge the case of single-point divisibility \(C_{cnt_0}^1 = cnt_0\) .
Looking back at the original question,Find the structure by \([0,k-1]\) the length of the composition \(n\) 的序列,And the interval sum is satisfied in all intervals \(k\) 整除的个数（贡献）为 \(t\) 的方案数.We can add one to the solution of the original problemdpPrefix and sequence process,Converted to a countdp.
\(dp[i][j][u]\) Expressed as taking into account the first \(i\) 个数,已经选了 \(j\) The number goes into the prefix sum sequence, 贡献为 \(u\) 的方案数.
初始状态是 \(dp[0][0][0] = 1\).
对于 \(dp[i-1][j][u]\) 的下一个状态,在 \(i > 1\) 时,That is, the selected number is greater than \(0\) ,Don't think about the problem of its own interval,因此选了 \(v\) 个第 \(i\) The status after the number is \(dp[i][j+v][u+C_v^2]\) ,Because the newly selected number has nothing to do with the previous number, it will only be combined with itself,Contributions just need to be added \(C_v^2\) 即可;而 \(i = 1\) ,即选 \(0\) 时,Because it can represent a length of itself alone \(1\) 合法区间,So the next state is \(dp[i][j+v][u+C_{v+1}^2]\) ,其中 \(C_{v+1}^2 = C_{v}^{2} + C_{v}^{1}\) ,It can be understood that there is one before the prefix and the first element of the sequence \(0\) 元素可以匹配.
Next is the state transition equation,由于 \(dp[i-1][j][u]\) All scenarios for this state have been represented,And newly added \(v\) The number only needs to be in \(v+j\) select the location \(v\) 个放入,The plan for the remaining numbers is exactly that \(dp[i-1][j][u]\) ,So the number of scenarios for the next state is \(C_{v+j}^{v}dp[i-1][j][u]\) .So the transfer equation is ：
In the end, writing directly in this way will time out,Because there are many branches that are unnecessary,发现 \(dp[i-1][j][0] = 0\) When there is no need to choose the number at all, there is one less \(v\) 循环.In fact, this method of state transition is called the brush table method,Updates all states it can reach through the previous state;And form filling method,Update yourself through the current state to find the state related to it.This question cannot be optimized using the form-filling method,With the brush table method, you can immediately see the optimization point.
注意数组的 \(u\) Dimension should be doubled \(t\) 的大小,也就是 \(n^2\) ,防止 \(u+v = t+c[n][2] \approx n^2\) 的情况出现.
Combinations are available \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\) 递推.
时间复杂度 \(O(n^2tk)\)
空间复杂度 \(O(ntk)\)
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int c[70][70];
int dp[70][70][70 * 70];///考虑到 i-1 个数字 ,已经选了j个,贡献k;70*70比2t大,不用担心u+c[v][2]越界
///Because of the range of numbers[0,k-1]So there is a one-to-one correspondence between the original array and the prefix and array,So consider enumerating prefixes and arrays,Convert interval sums to endpoint judgments
///interval and can bekDivide the corresponding endpointi,j有sum[i]%k = sum[j]%k（i!=j）
///特殊地,当sum[i] = 0时,You can also qualify yourself,因此要特判
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k, t;
cin >> n >> k >> t;
for (int i = 0;i <= n + 1;i++) {
for (int j = 0;j <= i;j++) {
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
///The brush table method can prune branches,The tabulation method cannot
dp[0][0][0] = 1;
for (int i = 1;i <= k;i++) {
for (int j = 0;j <= n;j++) {
for (int u = 0;u <= t;u++) {
if (!dp[i - 1][j][u]) continue;
if (i == 1) {
for (int v = 0;v + j <= n;v++)
dp[i][j + v][u + c[v + 1][2]] = (dp[i][j + v][u + c[v + 1][2]] + 1LL * c[j + v][v] * dp[i - 1][j][u]) % mod;
///原本是c[v][2] 但 0Can be one of its own,所以是c[v][2] + v = c[v+1][2] ,Can be understood as a prefix sum0There is a number0匹配
}
else {
for (int v = 0;v + j <= n;v++) {
dp[i][j + v][u + c[v][2]] = (dp[i][j + v][u + c[v][2]] + 1LL * c[j + v][v] * dp[i - 1][j][u]) % mod;
}
}
}
}
}
cout << dp[k][n][t] << '\n';
return 0;
}
