A(军训I)
大分类讨论
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1010;
char a[N][N];
void solve()
{
int n,m,k;
cin>>n>>m>>k;
if(k>=14) {cout<<"No\n";return ;}
bool change = false;
if(n>m) swap(n,m), change = true;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j] = '-';
bool ok = true;
if(n==1)
{
if(m==1)
{
if(k==1) ok = true, a[1][1] = '*';
else ok = false;
}
else if(m==2)
{
if(k==1) ok = true, a[1][1] = a[1][2] = '*';
else if(k==2) ok = true, a[1][1] = '*';
else ok = false;
}
else if(m>=3)
{
if(k==1) {ok = true; for(int i=1;i<=m;++i) a[1][i] = '*';}
else if(k==2) ok = true, a[1][1] = '*';
else if(k==3) ok = true, a[1][2] = '*';
else ok = false;
}
}
else if(n==2)
{
if(m==2)
{
if(k==1) {ok = true; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j] = '*';}
else if(k==2) {ok = true; for(int i=1;i<=n;++i) a[i][1] = '*';}
else if(k==3) ok = false;
else if(k==4) ok = true, a[1][1] = '*';
else if(k==5) ok = true, a[1][1] = '*', a[2][2] = '*';
else ok = false;
}
//大概率只有这个分类了
else
{
if(k==1) {ok = true; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j] = '*';}
else if(k==2) {ok = true; for(int i=1;i<=n;++i) a[i][1] = '*';}
else if(k==3) {ok = true; for(int i=1;i<=n;++i) a[i][2] = '*';}
else if(k==4) ok = true, a[1][1] = '*';
else if(k==5)
{
int G = __gcd(n,m);
if(G==1) ok = false;
else ok = true;
for(int i=1;i<=n;i++)
for(int j=(i-1)%G+1;j<=m;j+=G)
a[i][j] = '*';
}
else if(k==6) ok = true, a[2][2] = '*';
else if(k==7) {ok = true, a[2][1] = '*'; for(int i=2;i<=m;++i) a[1][i] = '*';}
else if(k==8) ok = false;
//注意当n==2，k==9时只填(2,2)是不行的
else if(k==9) ok = true, a[1][1] = '*', a[2][3] = '*';
else if(k==10) ok = false;
//注意n==2,k==11时是可行的
else if(k==11)
{
if(m>=4) ok = true, a[1][2] = '*', a[2][1] = '*', a[1][m] = '*';
else ok = false;
}
else ok = false;
}
}
else
{
if(k==1) {ok = true; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j] = '*';}
else if(k==2) {ok = true; for(int i=1;i<n;++i) for(int j=1;j<=m;++j) a[i][j] = '*';}
else if(k==3) {ok = true; for(int i=1;i<=n;++i) a[i][2] = '*';}
else if(k==4) ok = true, a[1][1] = '*';
else if(k==5)
{
int G = __gcd(n,m);
if(G==1) ok = false;
else ok = true;
for(int i=1;i<=n;i++)
for(int j=(i-1)%G+1;j<=m;j+=G)
a[i][j] = '*';
}
else if(k==6) ok = true, a[2][1] = '*';
else if(k==7) {ok = true, a[2][1] = '*'; for(int i=2;i<=m;++i) a[1][i] = '*';}
else if(k==8) ok = false;
else if(k==9) ok = true, a[2][2] = '*';
else if(k==10) ok = false;
//注意一下这个
else if(k==11)
{
if(n==3&&m==3)
{
a[1][1]=a[2][3]=a[3][1]=a[3][2]=a[3][3]='*';
}
else if(m>=4) ok = true, a[1][2] = '*', a[2][1] = '*', a[1][m] = '*';
else ok = false;
}
else if(k==12) ok = false;
else ok = true, a[1][1] = '*', a[n][m] = '*';
}
if(!ok) cout<<"No\n";
else
{
cout<<"Yes\n";
if(!change) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {cout<<a[i][j]; if(j==m) cout<<'\n';}
else
{
for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) {cout<<a[j][i]; if(j==n) cout<<'\n';}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}
C(种树)
如果根节点已经完成了，那么这个子树对根节点父亲的贡献就有两种情况：用最少次数做完子树时，是否存在多余的、且对子树根节点的父亲有贡献的操作
如果根节点没有完成，则直接将 size 向上传递。直到遇到一个已经完成的祖先，在那个祖先中对size 进行统计即可。
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e5+10;
vector<int> e[N];
void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<=n;++i) e[i].clear();
vector<int> a(m),st(n+1),sz(n+1),f(n+1);
for(int i=0;i<m;++i) cin>>a[i],st[a[i]] = 1;
for(int i=0;i<n-1;++i)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
int ans = 0;
//dfs(u)返回的是u子树对其父节点的贡献
auto dfs = [&](auto && dfs,int u,int f)->int
{
//res表示的是u的子树内需要完成染色的点的个数
int res = 0;
int ok = 0;
for(auto v:e[u])
{
if(v==f) continue;
int t = dfs(dfs,v,u);
//若有儿子将u染色将ok = true
if(t<0) ok = 1;
else res += t;
}
//若即不是已经染色点也没被儿子更新res++
res += (!st[u]&&!ok);
//若该点已经被染色就结算，否则向上传递需要更新的点
if(st[u]||ok) {ans += max((res+1)/2,0); return (res&1)?-1:0;}
else return res;
};
dfs(dfs,a[0],0);
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}
E(随机过程)
注意在计算最大节点数时需要保留\(26^i\)以免出现模p以后的值小于n统计入res中的情况，同时记住最后对res取模
考虑第i层单个节点出现的概率，因为期望满足加法运算，直接用概率乘以点数即可
对于单个长度为i的字符串出现某个特点节点的概率是\(\frac{1}{26}^i\)
n次字符串都没出现该节点的概率是\((1-\frac{1}{26^i})^n\)
则该节点的出现概率为\((1-(1-\frac{1}{26^i})^n)\)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int p = 998244353;
const int N = 1e5+10;
ll P26[N],IP26[N];
ll quick_pow(ll a,int b)
{
a%=p;
ll ans=1;
for(;b;b>>=1)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
}
return ans;
}
ll inv(ll x)
{
return quick_pow(x,p-2);
}
void solve()
{
P26[0] = 1;
IP26[0] = 1;
ll INV26 = inv(26);
for(int i=1;i<=100000;++i)
{
P26[i] = P26[i-1]*26%p;
IP26[i] = IP26[i-1]*INV26%p;
}
//第i层的最大节点数：min(26^i,n)
ll n,m;
cin>>n>>m;
ll res = 1,tmp = 1;
for(int i=1;i<=m;++i)
{
if(tmp*26 >= n) res += n;
else
{
tmp *= 26;
res += tmp;
}
}
cout<<res%p<<" ";
//考虑第i层单个节点出现的概率，因为期望满足加法运算，直接用概率乘以点数即可
//对于单个长度为i的字符串出现某个特点节点的概率是(1/26)^i
//n次字符串都没出现该节点的概率是(1-(1/26)^i)^n
//则该节点的出现概率为(1-(1-(1/26)^i)^n)
ll ans = 0;
for(int i=0;i<=m;++i)
{
ans += P26[i]*(1-quick_pow((1-IP26[i]+p),n)+p), ans %= p;
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
}
G(疯狂星期六)
网络流，建图：源点向菜品容量为菜价，菜向人流容量为\(a[i]-V[i]\)，人向汇点容量为min(c,a[i])-V[i]，若最大流为菜价即合法
注意：若菜只有一个人直接计入V[i]即可，同时注意不要有负权边，若人向汇点的容量为负值直接return
#include<bits/stdc++.h>
using namespace std;
template<typename T> struct Flow_ {
const int n;
const T inf = numeric_limits<T>::max();
struct Edge {
int to;
T w;
Edge(int to, T w) : to(to), w(w) {}
};
vector<Edge> ver;
vector<vector<int>> h;
vector<int> cur, d;
Flow_(int n) : n(n + 1), h(n + 1) {}
void add(int u, int v, T c) {
h[u].push_back(ver.size());
ver.emplace_back(v, c);
h[v].push_back(ver.size());
ver.emplace_back(u, 0);
}
bool bfs(int s, int t) {
d.assign(n, -1);
d[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto x = q.front();
q.pop();
for (auto it : h[x]) {
auto [y, w] = ver[it];
if (w && d[y] == -1) {
d[y] = d[x] + 1;
if (y == t) return true;
q.push(y);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) return f;
auto r = f;
for (int &i = cur[u]; i < h[u].size(); i++) {
auto j = h[u][i];
auto &[v, c] = ver[j];
auto &[u, rc] = ver[j ^ 1];
if (c && d[v] == d[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
c -= a;
rc += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
T work(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, inf);
}
return ans;
}
};
using Flow = Flow_<int>;
int main()
{
int n,m;
cin>>n>>m;
//完成流的初始化
Flow G(n+m+2);
vector<int> a(n+1),V(n+1);
int c = 0;
for(int i=1;i<=n;++i) cin>>a[i]>>V[i];
int s = 0, t = n+m+1;
int sum = 0;
for(int i=1;i<=m;++i)
{
int u,v,w;
cin>>u>>v>>w;
if(u==v) {V[u]+=w; continue;}
sum += w;
if(u==1||v==1) c += w;
//从源点向菜品的流量为w
G.add(s,i+n,w);
G.add(i+n,u,a[u]);
G.add(i+n,v,a[v]);
}
//1号点的花费,注意应该在V修改后再加
c += V[1];
c = min(c, a[1]);
//对于1号点向汇点的流量为c-V[1],表示由点菜花去的钱最大限制
G.add(1,t,c-V[1]);
for(int i=2;i<=n;++i)
{
//对于其他点来说,由点菜花去的钱不能超过c-1-V[i]和a[i]-V[i]
//注意需要防止出现负权边
int w = min(c-1,a[i])-V[i];
if(w < 0) {cout<<"NO\n"; return 0;}
G.add(i,t,w);
}
//如果能完成点单
if(G.work(s,t) == sum) cout<<"YES\n";
else cout<<"NO\n";
}
J(找最小)
首先计算a,b数组的异或值ans1,ans2，每次交换相当于ans1,ans2都异或了\((a[i]\oplus b[i])\)
先实现线性基，对于ans1,ans2的值从高位向低位考虑，对于第i位若都为0不处理，都为1则都异或d[i]
若一个为0一个为1，最终的结果一定在该位为1，则分别考虑该位为1的是ans1还是ans2各自处理一下即可
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int a[N],b[N],c[N],d[32];
void solve()
{
memset(d,0,sizeof d);
int n;
cin>>n;
int ans1 = 0,ans2 = 0;
for(int i=0;i<n;++i) cin>>a[i], ans1^=a[i];
for(int i=0;i<n;++i) cin>>b[i], ans2^=b[i];
//cout<<ans1<<' '<<ans2<<'\n';
for(int i=0;i<n;++i) c[i] = a[i]^b[i];
for(int i=0;i<n;++i)
{
int x = c[i];
for(int j=30;j>=0;--j)
{
if((x>>j)&1)
{
if(!d[j]) {d[j]=x;break;}//注意：如果此处d[j]等于x需要break掉,不能继续循环
else x^=d[j];
}
}
}
//cout<<d[2]<<' '<<d[1]<<' '<<d[0]<<'\n';
for(int j=30;j>=0;--j)
{
if(!(ans1>>j&1)&&!(ans2>>j&1)) continue;
else if((ans1>>j&1)&&(ans2>>j&1)) ans1^=d[j], ans2^=d[j];
else
{
//当出现第一位不同时最终答案一定是该位为1的数的最小值
//若d[j]存在则两个ans各枚举一遍
//若d[j]不存在直接尽可能减小该位为1的数
if(!d[j])
{
int t = max(ans1,ans2);
for(int k=j-1;k>=0;--k)
{
if(t>>k&1) t^=d[k];
}
cout<<t<<'\n';
return ;
}
else
{
int minn = 2147483647;
int t = max(ans1,ans2);
//先选j位为1的数枚举
for(int k=j-1;k>=0;--k)
{
if(t>>k&1) t^=d[k];
}
minn = min(minn,t);
t = min(ans1,ans2);
//选j位为0的数异或线性基后枚举
t ^=d[j];
for(int k=j-1;k>=0;--k)
{
if(t>>k&1) t^=d[k];
}
minn = min(minn,t);
cout<<t<<'\n';
return ;
}
}
}
//若是全一致不应该输出0而是ans1
cout<<ans1<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}