前言
开局掉线30min比较搞心态，不过比赛延迟了1个小时，但是后面也一直没过题，如果时间再少点可能排名还更好看。最后是8题前面，这里简单讲一下我有写的题，队友写的题就放一下队友的赛时代码，大家自己看看吧。
B
队友写的，签到，但是数据范围 \(n\) 给 \(10^3\) 给队友整不自信了，因为答案的那个结论成立的话很显然可以 \(nlogn\) 做，可能是为了让大家能 \(n^2\) 求不整齐度吧。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const int M = 998244353;
int frac(int n){
int re=1;
for(int i=1;i<=n;i++)re=re*i%M;
return re;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin>>n;
set<int>s;
map<int,int>mp;
int a[n];
for(int i=0;i<n;i++)cin>>a[i],mp[a[i]]++,s.insert(a[i]);
sort(a,a+n);
int ans=0;
int cnt=1;
for(auto [p,t]:mp)cnt=cnt*frac(t)%M;
if(s.size()>1)cnt*=2;
for(int i=0;i<n;i++)
for(int j=i;j<n;j++){
ans+=a[j]-a[i];
}
cout<<ans<<" "<<cnt%M;
// system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
D
队友写的，区间DP
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int N = 109;
const int mod = 998244353;
int dp[N][N][N], n, m;
string S, T;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> S >> T;
n = S.length();
m = T.length();
S = ' ' + S;
T = ' ' + T;
for(int i = 0; i <= n; i++)
for(int j = 1; j <= m+1; j++)
for(int t = 0; t < j; t++)
dp[i][j][t] = 1;
for(int i = 1; i <= n; i++){
for(int l = 1; l <= m; l++)
for(int r = l; r <= m; r++){
for(int k = l-1; k <= r; k++)
dp[i][l][r] = (dp[i][l][r] + dp[i-1][l][k] * dp[i-1][k+1][r]) % mod;
for(int k = l-1; k < r; k++)
if(S[i] == T[k+1])
dp[i][l][r] = (dp[i][l][r] + dp[i-1][l][k] * dp[i-1][k+2][r]) % mod;
}
}
cout << dp[n][1][m] << '\n';
//system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
E
和队友一起推的式子，我写的代码，这里可以稍微讲讲。
对于trie树上的一个节点，表示的是一个前缀。那么这个节点存在，说明 \(n\) 个字符串里至少有一个串包括这个前缀即可，那么概率就是 \(1- P(这个前缀不出现)\)，而这个前缀不出现，则所有 \(n\) 个串都不能有这个前缀。显然这 \(n\) 个串是独立的，所以只需要求出一个串不包含这个前缀的概率，拿去 \(n\) 次方即可。那么对于一个串，不包含这个前缀的概率，又等于 \(1 - P(包含这个前缀的概率)\)，包含这个前缀(假设长度为 \(i\))的概率显然为 \((\frac{1}{26} ^ i)\)。又因为所有长度为 \(i\) 的前缀都是等价的，所以还要再最外面考虑乘一个 \(26^i\)表示所有长度为 \(i\) 的前缀的数量。综上，最后trie树的期望节点数就是
至于最多的节点数，则分层考虑，第一层最多有 26 个，第二层最多有 \(26^2\)个，以此类推，第 \(i\) 层最多有 \(26^i\) 个，而且因为每一层都至少对应这 \(n\) 个串中的1个，所以每一层最多的结点数还要跟 \(n\) 取个最小值，所以最后的答案就是:
\[1 + \sum{i = 1}{m}min(26^i, n) \]代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e5 + 1000;
const int mod = 998244353;
int mi26[maxn];
int ksm(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * a % mod) {
if (b & 1) res = res * a % mod;
}
return res;
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
mi26[0] = 1;
for (int i = 1; i < maxn; i++)
mi26[i] = mi26[i - 1] * 26 % mod;
int inv26 = ksm(26, mod - 2);
int n, m; cin >> n >> m;
int ans1 = 1;
for (int i = 1; i <= m; i++) {
ans1 += mi26[i] * ((1 - ksm((1 - ksm(inv26, i) + mod) % mod, n) + mod) % mod) % mod;
ans1 %= mod;
}
int ans2 = 1, tem = 1;
for (int i = 1; i <= m; i++) {
tem *= 26;
if (tem < n) ans2 += tem, ans2 %= mod;
else {
ans2 += (m - i + 1) * n % mod;
ans2 %= mod;
break;
}
}
cout << ans2 << " " << ans1 << "\n";
system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
G
队友写的，网络流
看到数据范围 \(10^3\) 就开始考虑可能是一些科技东西，就往网络流考虑了，然后发现那些限制刚好也很符合网络流，具体建图不太清楚，好像是先考虑一下打车钱，然后两个人一起付钱就可以建虚点啥的，最后看能不能跑满最大流，直接看代码吧。
代码
点击查看代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int N = 3e3+99;
const int mod = 998244353;
struct Edge{
int v, nxt, w;
}e[N*10];
int head[N], cur[N], tot = 1, s, t, dist[N], gap[N], sz;
ll dfs(int u, ll rest) {
if (u == t) return rest;
ll sum = 0;
for (int &i = cur[u]; i; i = e[i].nxt) {
if (dist[u] == dist[e[i].v] + 1 && e[i].w) {
ll ret = dfs(e[i].v, min(rest, e[i].w));
rest -= ret;
sum += ret;
e[i].w -= ret;
e[i ^ 1].w += ret;
if (rest == 0) return sum;
}
}
gap[dist[u]]--;
if (gap[dist[u]] == 0) dist[s] = sz + 1;
dist[u]++;
gap[dist[u]]++;
cur[u] = head[u];
return sum;
}
ll isap() {
gap[0] = sz;
ll ans = 0;
while (dist[s] < sz) ans += dfs(s, inf);
return ans;
}
void add(int u, int v, int w, int t = 1){
e[++tot] = (Edge){v, head[u], w};
head[u] = tot;
if(t) add(v, u, 0, 0);
}
int a[N], val[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i] >> val[i];
s = n + m + 1, t = s + 1;
sz = t;
int sum = 0, flow = 0;
for(int i = 1; i <= m; i++){
int x, y, w;
cin >> x >> y >> w;
add(x, n + i, inf);
add(y, n + i, inf);
add(n + i, t, w);
flow += w;
if(x == 1 || y == 1) sum += w;
}
sum = min(a[1], sum + val[1]);
bool flag = 1;
add(s, 1, sum - val[1]);
for(int i = 2; i <= n; i++){
a[i] = min(a[i], sum-1);
if(a[i] < val[i]){
flag = 0;
break;
}
add(s, i, a[i] - val[i]);
}
if(!flag || isap() < flow)
cout << "NO\n";
else
cout << "YES\n";
//system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
I
队友写的，是个三次方的dp，好像是预处理一个数组 \(ans[i]\) 表示拿到行李时间大等于 \(i\) 的方案数，这个数组是用三方的dp来求的，最后就可以差分得出每个时间的方案数，再求和啥的。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const int M = 998244353;
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
int a[n + 1]{}; // xingli
int b[m + 1]{}; // ren
int ans[606]{};
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
for (int k = 0; k <= 500; k++) {
int dp[505][505]{};
dp[0][0] = 1;
int a1[n + 1]{};
int pre[1050]{};
for (int i = 1; i <= n; i++)
a1[i] = a[i] + k, pre[a1[i]]++;
for (int i = 1; i <= 500; i++)
pre[i] += pre[i - 1];
for (int j = 1; j <= m; j++)
for (int i = 0; i <= 500; i++) {
if (i - pre[b[j]] + pre[b[j - 1]] >= 0)
dp[i][j] += dp[i - pre[b[j]] + pre[b[j - 1]]][j - 1];
if (i - pre[b[j]] + pre[b[j - 1]] + 1 >= 0)
dp[i][j] += dp[i - pre[b[j]] + pre[b[j - 1]] + 1][j - 1] *
(i + 1) % M;
dp[i][j] %= M;
}
for (int i = 0; i <= n; i++)
ans[k] += dp[i][m], ans[k] %= M;
}
int res = 0;
for (int i = 1; i <= 500; i++) {
res += (ans[i - 1] - ans[i] + M) % M * (i - 1) % M;
res %= M;
}
cout << res;
// system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
J
和队友一起讨论出来，最后我写的，首先转化题意
两个数组分别异或，得到 sum1 和 sum2，容易发现如果交换 \(a_i\) 和 \(b_i\) 则 \(sum1 - sum1 ^ a[i] ^ b[i]\)，sum2同理，所以题意转化为，有两个数sum1 和 sum2，还有 \(n\)个数 \(a_i \oplus b_i\) 你可以任意选择这 \(n\) 个数的若干个数，让 sum1 和 sum2同时异或上它们，问 \(max(sum1, sum2)\) 的最小值是多少。
由于是任意选择若干个数异或，显然可以考虑线性基，然后从高到低按位贪心考虑。如果sum1 和sum2这一位都是0，则不操作，若这一位都是1，则去异或线性基的这一位。难点在于一个1一个0的情况，这时候选不选择去异或，都不影响答案的这一位，但是选择异或，可能会对后面的位产生影响。
这时候一开始我有个错误的思路，碰到这样的数，我就不去异或，而是把线性基里的对应数去掉当前位，重新插入线性基。然而wa了之后队友发现这样假了，随便比如111和000，假如线性基里都有数，那么我就都不操作了，而明显可以通过交换这两个数的这一位可以使较大的数减小一些。
所以思路就有了，遇到一个0一个1的情况，可以通过异或线性基的这一位，交换这两个数的这一位。那么该怎么交换合理，又要考虑前面的位，如果已经有不一样的，那么大的数肯定一直都大(因为二进制下，从高到低第一个不同的位决定了数的大小)，所以后面可以选择交换0、1的地方，就把1都分配给较小的数，所以后面这样的决策都是确定的。如果前面的位都一样呢？这里我是直接比较暴力的，把异或和不异或两种情况都跑一次，取个最小值，因为这一位开始，后面的决策也都确定，所以跑2次复杂度也是正确的。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int p[33];
int a[maxn], b[maxn];
void insert(int x) {
for (int i = 31; i >= 0; i--) {
if ((x >> i) == 0) continue;
if (!p[i]) {
p[i] = x;
break;
} else x = x ^ p[i];
}
}
int dfs(int pos, int sum1, int sum2) {
if (pos == -1) return max(sum1, sum2);
int x1 = ((sum1 >> pos) & 1);
int x2 = ((sum2 >> pos) & 1);
if (x1 == 0 && x2 == 0) return dfs(pos - 1, sum1, sum2);
if (x1 == 1 && x2 == 1) return dfs(pos - 1, sum1 ^ p[pos], sum2 ^ p[pos]);
if ((x1 == 1 && sum1 > sum2) || (x2 == 1 && sum2 > sum1)) {
return dfs(pos - 1, sum1 ^ p[pos], sum2 ^ p[pos]);
} else {
return dfs(pos - 1, sum1, sum2);
}
}
void solve() {
memset(p, 0, sizeof p);
int n; cin >> n;
int sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++) cin >> a[i], sum1 ^= a[i];
for (int i = 1; i <= n; i++) cin >> b[i], sum2 ^= b[i];
for (int i = 1; i <= n; i++) {
insert(a[i] ^ b[i]);
}
for (int i = 31; i >= 0; i--) {
int x1 = ((sum1 >> i) & 1);
int x2 = ((sum2 >> i) & 1);
if (x1 == 0 && x2 == 0) continue;
if (x1 == 1 && x2 == 1) sum1 ^= p[i], sum2 ^= p[i];
else {
if ((sum1 >> (i + 1)) != (sum2 >> (i + 1))) {
if ((x1 == 1 && sum1 > sum2) || (x2 == 1 && sum2 > sum1)) {
cout << dfs(i - 1, sum1 ^ p[i], sum2 ^ p[i]) << "\n";
} else {
cout << dfs(i - 1, sum1, sum2) << "\n";
}
return;
}
else {
int ans = min(dfs(i - 1, sum1, sum2), dfs(i - 1, sum1 ^ p[i], sum2 ^ p[i]));
cout << ans << "\n";
return;
}
}
}
cout << max(sum1, sum2) << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
solve();
// system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
K
签到，首先容易发现，奇数，先手肯定取1，之后就都只能拿1，先手胜。拓展一下就可以考虑所有 \(n\) 的因数，如果有奇数个它，那么先手就取这个数，后手无论怎么选，先手都可以取一样的数模仿。然后考虑哪个因数使得 \(n\) / 它是奇数，发现似乎是2的若干次幂，进而发现是 \(lowbit(n)\)，所以最后只要判断一下 \(lowbit(n)\) 和 \(k\) 的大小，就可以直接输出了。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
void solve() {
int n, k; cin >> n >> k;
if ((n & (-n)) <= k)
cout << "Alice\n";
else
cout << "Bob\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
solve();
// system("pause"); // 交之前记得注释一下，关流的时候不会显示输出
return 0;
}
L
纯模拟，暴力找，没什么好说的
代码
点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 5e2 + 10;
const int mod = 998244353;
char ch[maxn][maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> ch[i][j];
}
int ans = 0;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++) {
if (ch[i][j] == 'c' && ch[i][j + 1] == 'c' && ch[i + 1][j] == 'p' && ch[i + 1][j + 1] == 'c')
ans++;
}
cout << ans << endl;
// system("pause");
return 0;
}