Problem L. 网络预选赛
签到，直接模拟即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<string>a(n);for(int i=0;i<n;i++){cin>>a[i];}int sum=0;for(int i=0;i<n-1;i++){for(int j=0;j<m-1;j++){if(a[i][j]=='c'&&a[i][j+1]=='c'&&a[i+1][j]=='p'&&a[i+1][j+1]=='c'){sum++;}}}cout<<sum<<endl;return 0;
}
Problem B. 军训 II
显然排序后的结果最优，注意数组全等的情况
点击查看代码
#include <bits/stdc++.h>template<typename T>
auto constexpr MAX = std::numeric_limits<T>::max();auto main() -> int
{std::ios::sync_with_stdio(false),std::cin.tie(nullptr);int n;std::cin >> n;auto a = std::vector<int>(n,0);for(auto& v : a) {std::cin >> v;}std::sort(a.begin(),a.end());auto ans = 0ull;for(auto l = 0; l != n; ++l) {auto [min,max] = std::make_pair(a[l],a[l]);for(auto r = l + 2; r <= n; ++r) {min = std::min(min,a[r - 1]);max = std::max(max,a[r - 1]);ans += max - min;}}auto cnt = 1ull;auto map = std::map<int,int>{};for(auto v : a) {++map[v];}using i64 = long long;auto fact = std::vector<i64>(n + 1,i64{});fact[0] = fact[1] = 1;auto constexpr MOD = 998244353;for(auto i = 2; i < n + 1; ++i) {fact[i] = i * fact[i - 1] % MOD;}for(auto [v,ct] : map) {if(ct == 1) {continue;}cnt *= fact[ct];cnt %= MOD;}cnt = std::max(cnt,1ull);if(map.size() > 1) {cnt *= 2;}cnt %= MOD;std::cout << ans << ' ' << cnt << '\n';}
Problem K. 取沙子游戏
当 \(n\) 是奇数时，先手直接取 \(1\) 即可；
当 \(n\) 是偶数时，纸上打表发现当 \(lowbit(n) ~<=~ k\) 时，先手直接取 \(lowbit(n)\) 即可，否则后手赢
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;int lowbit(int x){return x&-x;
}void solve(){int n,k;cin>>n>>k;if(n&1){cout<<"Alice\n";}else{if(lowbit(n)<=k) cout<<"Alice\n";else cout<<"Bob\n";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
Problem D. 编码器-解码器
区间 DP，\(dp[i] [l] [r]\) 表示，在第 \(i\) 层字符串中，有多少个子序列是\(T[l,r]\)
逐层转移即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){string s,t;cin>>s>>t;int n=t.size();t=" "+t;s=" "+s;int ans=0;vector<vector<int>> val(n+1,vector<int>(n+1));for(int i=1;i<=n;i++){if(t[i]==s[1]){val[i][i]=1;}}for(int i=2;i<s.size();i++){vector<vector<int>> tv(n+1,vector<int>(n+1));for(int l=1;l<=n;l++){for(int r=l;r<=n;r++){// cout<<"cal l,r: "<<l<<" "<<r<<endl;//不考虑a[i]的// cout<<"不考虑a[i]: "<<endl; for(int k=l-1;k<=r;k++){int t1=1,t2=1;if(k>=l){t1=val[l][k];// cout<<"["<<l<<","<<k<<"]"<<' ';}if(k+1<=r){t2=val[k+1][r];// cout<<"["<<k+1<<","<<r<<"]";}// if(i==2 && l==2 && r==2) cout<<t1<<" ---- "<<t2<<endl;tv[l][r]+=t1*t2;tv[l][r]%=mod;// cout<<endl;}//考虑a[i]// cout<<"考虑a[i]: "<<endl;for(int k=l;k<=r;k++){if(t[k]!=s[i]) continue;int t1=1,t2=1;if(k-1>=l){t1=val[l][k-1];// cout<<"["<<l<<","<<k-1<<"]"<<' ';}if(k+1<=r){t2=val[k+1][r];// cout<<"["<<k+1<<","<<r<<"]";}tv[l][r]+=t1*t2;tv[l][r]%=mod;// cout<<endl;}}}val=tv;}cout<<val[1][n];
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}
Problem J. 找最小
记原始 \(a,b\) 数组分别异或的结果是 A,B
如果交换位置 \(i\)，等价于 A,B 分别异或 \((a[i]~xor~b[i])\)
将所有的 \((a[i]~xor~b[i])\) 插入线性基
从高位到低位利用线性基尝试减小 A,B 的值即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;class XorBasis {//基于高斯消元，逐个插入值
public:const int BITS = 62;vector<long long> basis; // 存储线性基的基底int k; // 基底中向量的个数bool has_zero; // 标记原数集中是否能异或出 0XorBasis() : basis(BITS + 1, 0), k(0), has_zero(false) {}void insert(long long num) {for (int i = BITS; i >= 0; i--) {if (!((num >> i) & 1)) {continue;}if (!basis[i]) {basis[i] = num;k++;return;}num ^= basis[i];}// 如果 num 最终变为 0，说明 num 可以由基底中的数异或表示// 这意味着原集合中存在线性相关的向量，可以异或出 0has_zero = true;}
};void solve(){int n;cin>>n;vector<int> a(n+1),b(n+1),c(n+1);int t1=0,t2=0;XorBasis xb;for(int i=1;i<=n;i++){cin>>a[i];t1^=a[i];}for(int i=1;i<=n;i++){cin>>b[i];t2^=b[i];c[i]=a[i]^b[i];xb.insert(c[i]);}for(int j=xb.BITS;j>=0;j--){if(xb.basis[j]==0) continue;if(max(t1^xb.basis[j], t2^xb.basis[j]) < max(t1,t2)){t1^=xb.basis[j];t2^=xb.basis[j];} }cout<<max(t1,t2)<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
Problem E. 随机过程
每一层，最多有 \(min(n,26^i)\) 个节点
每一层的 \(26^i\) 个可能出现的节点，每个节点不出现的概率是 \((1-1/26^i)^n\)
则可以计算出每个节点出现的概率，累加即为期望
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;/*支持define int long long 的自动取模类*/
template<const int T>
struct ModInt {const static int mod = T;int x;ModInt(signed x = 0) : x(x % mod) {}ModInt(long long x) : x((int)x % mod) {} int val() { return x; }ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }ModInt operator / (const ModInt &a) const { return *this * a.inv(); }bool operator == (const ModInt &a) const { return x == a.x; };bool operator != (const ModInt &a) const { return x != a.x; };void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }void operator /= (const ModInt &a) { *this = *this / a; }friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}ModInt pow(int64_t n) const {ModInt res(1), mul(x);while(n){if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}ModInt inv() const {int a = x, b = mod, u = 1, v = 0;while (b) {int t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}if (u < 0) u += mod;return u;}};
using mint = ModInt<mod>;int qmi(int a,int b,int p){int res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}void solve(){int n,m;cin>>n>>m;mint mx=0,e=0;for(int i=0;i<=m;i++){if(i>=5) mx+=n;else mx+=min(n,qmi(26,i,mod));int p1=qmi(26,i,mod);p1=qmi(p1,mod-2,mod);int p2=1-p1+mod;p2%=mod;int p3=qmi(p2,n,mod);int p4=1-p3+mod;p4%=mod;e+=qmi(26,i,mod)*p4;}cout<<mx<<" "<<e<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}
Problem C. 种树
想不到的贪心
对于以 \(u\) 为根且 \(u\) 已经种过树，且子树中其他节点未种树的子树，记未种树的节点个数尾 \(sz\)
则需要 \((sz+1)/2\) 次操作，让这个子树全部节点种上树
而当 \(sz\) 是奇数时，还可以给 \(u\) 的父节点种上树
如果 \(u\) 也不是根，则直接把 \(sz[u]\) 传递给父节点即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,m;cin>>n>>m;vector<int> a(n+1);int root;while(m--){int u;cin>>u;a[u]=1;root=u;}vector<vector<int>> g(n+1);for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}vector<int> sz(n+1);int ans=0;auto dfs=[&](auto dfs,int u,int pre)-> void {for(auto v:g[u]){if(v==pre) continue;dfs(dfs,v,u);sz[u]+=sz[v];}if(a[u]){ans+=(sz[u]+1)/2;if(pre!=0 && sz[u]&1){a[pre]=1;}sz[u]=0;}else{sz[u]++;}};dfs(dfs,root,0);cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}