喜欢每个包绑一个hack是吧。
暴力操作（opt）
容易发现答案具有单调性，考虑二分答案。还发现只需要处理\(1\sim \left\lceil\frac{n}{2}\right\rceil\)即可。
发现如果\(c_{i}>c_{j}且i<j\)，那么选\(j\)肯定更优。
有\(\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\)，所以用个类似埃筛的东西预处理一下，注意要多处理一点。
考虑\(\left\lfloor\frac{a}{b}\right\rfloor=c\)时，有\(\frac{a}{b}<c+1\Leftrightarrow b\ge\frac{a}{c+1}+1\)。用这个东西直接check即可，时间复杂度\(O(n\log m)\)
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
// FILE *ErrFile = freopen("err.err","w",stderr);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("opt.in","r",stdin),*OutFile = freopen("opt.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
#define pii pair<int,int>
#define mk make_pair
const int N = 1e6 + 10;
int n,m,k,c[N],a[N],f[N];
inline bool check(int mid){
int res = 0;
rep(i,1,n/2+1,1) if(a[i] > mid) res += c[a[i]/(mid+1)+1];
return res <= k;
}
inline void solve(){
cin>>n>>m>>k;
memset(c,0x3f,sizeof c);
rep(i,1,n,1) cin>>a[i];
sort(a+1,a+1+n);
rep(i,1,m,1) cin>>c[i];
drep(i,m,1,1) c[i] = min(c[i],c[i+1]);
rep(i,2,m,1) rep(j,2,(m+1)/i+1,1) c[min(i*j,m+1)] = min(c[min(i*j,m+1)],c[i]+c[j]);
drep(i,m,1,1) c[i] = min(c[i],c[i+1]);
int l = 0,r = m,ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
cout<<ans<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
异或连通（xor）
模板：线段树分治。
发现每条边的出现位置是几个区间且区间个数不超过\(\log k\)，证明转化为二进制即可，用一个trie维护，求出区间即可。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("xor.in","r",stdin),*OutFile = freopen("xor.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define eb emplace_back
const int N = 1e5 + 10;
int n,m,q,k,u[N],v[N],c[N],qpos[N],ans[N];
pair<int,int> Q[N];
struct DSU{
vector<int> fa,siz,sta;ll ans;
inline void init(int n){
fa.resize(n+1),siz.resize(n+1);
rep(i,1,n,1) fa[i] = i,siz[i] = 1;ans = 0;
}
inline int get_fa(int x){while(x ^ fa[x]) x = fa[x];return x;}
inline ll get(int x){return 1ll*x*(x-1)/2;}
inline void Merge(int x,int y){
x = get_fa(x),y = get_fa(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x,y);
ans += 1ll*siz[x]*siz[y];
fa[x] = y;siz[y] += siz[x];sta.eb(x);
}
inline void undo(){
int x = sta.back();sta.pop_back();
siz[fa[x]] -= siz[x];fa[x] = x;
}
inline void undo(int res){while(sta.size() > res) undo();}
}D;
struct SegmentTreeDivide{
vector<int> t[N<<2];
void upd(int k,int l,int r,int ql,int qr,int p){
if(ql <= l && r <= qr) return t[k].eb(p);
int mid = (l + r) >> 1;
if(ql <= mid) upd(k<<1,l,mid,ql,qr,p);
if(qr > mid) upd(k<<1|1,mid+1,r,ql,qr,p);
}
void qry(int k,int l,int r){
int res = D.sta.size(),rans = D.ans;
for(auto i:t[k]) D.Merge(u[i],v[i]);
if(l == r) ans[l] = D.ans;
else{
int mid = (l + r) >> 1;
qry(k<<1,l,mid);qry(k<<1|1,mid+1,r);
}
D.undo(res);D.ans = rans;
}
}seg;
struct TRIE{
int tree[N*29][2],l[N*29],r[N*29],tot = 0;
inline int insert(int x,int id){
int p = 0;
drep(i,29,0,1){
int k = (x>>i)&1;
if(!tree[p][k]) tree[p][k] = ++tot,l[tot] = id;
p = tree[p][k];r[p] = id;
}
return p;
}
inline void work(int x,int id){
int p = 0;
drep(i,29,0,1){
int k1 = (x>>i)&1,k2 = (k>>i)&1;
if(k2){
if(tree[p][k1]) seg.upd(1,1,q,l[tree[p][k1]],r[tree[p][k1]],id);
p = tree[p][k1^1];
}
else p = tree[p][k1];
if(!p) break;
}
}
}trie;
int mp[N];
inline void solve(){
cin>>n>>m>>q>>k;D.init(n);
rep(i,1,m,1) cin>>u[i]>>v[i]>>c[i];
rep(i,1,q,1) cin>>Q[i].first,Q[i].second = i;
sort(Q+1,Q+1+q);
rep(i,1,q,1) mp[Q[i].second] = i;
rep(i,1,q,1) trie.insert(Q[i].first,i);
rep(i,1,m,1) trie.work(c[i],i);
seg.qry(1,1,q);
rep(i,1,q,1) cout<<ans[mp[i]]<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
诡异键盘（keyboard）
不会。
民主投票（election）
发现如果一个人得到\(a\)票时可以，那么他得到\(b(b>a)\)票时也可以。
考虑二分。设\(f_{x,s}\)表示以\(x\)为根的子树，每个点最多有\(s\)票，需要往上传的票数。
那么对于一个点\(x\)，设其子树大小（不包含自己）为\(s\)，那么\(x\)最多有\(s\)票，二分求出
其他点能否满足每个点最多\(s − 1\)票的条件。
考虑求一个全局的\(s\)使得\(f_{1,s}=0\)（即每个点都不会超），那么 \(size >s\) 和 \(size < s\)的点的答
案均确定了，只需考虑 \(size = s\)的点。此时用 \(s − 1\) 求出一个答案，容易发现由于 \(size_x = s\)，\(f_{x,s−1} \le 1\)，若\(f_{x,s−1}= 0\) 那么 \(f_{1,s−1}\)不会改变，因此 \(x\)点不能获胜，否则若 \(f_{1,s−1}\)和根到 \(x\) 链上所有点均为 \(1\)，\(f_{1,s−1}\) 会改成 \(0\)，故 \(x\)可以获胜。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("election.in","r",stdin),*OutFile = freopen("election.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10;
int n,siz[N],now,f[N];
char s[N];
vector<int> e[N];
void dfs(int x){
siz[x] = 0;
for(int y:e[x]) dfs(y),siz[x] += siz[y] + 1;
}
bool check(int mid){
auto dp = [&](auto &&dp,int x)->void{
f[x] = 0;
for(int y:e[x]) dp(dp,y),f[x] += f[y];
f[x] = max(0,f[x] - mid) + 1;
};
dp(dp,1);
return f[1] == 1;
}
void getans(int mid){
auto get = [&](auto &&get,int x)->void{
if(siz[x] == mid+1) return s[x] = '1',void();
for(int y:e[x]) if(f[y] > 1) get(get,y);
};
get(get,1);
}
inline void solve(){
cin>>n; rep(i,1,n,1) vector<int> ().swap(e[i]);
rep(i,1,n,1) siz[i] = 0;
rep(i,2,n,1){int f;cin>>f;e[f].emplace_back(i);}
dfs(1);
int l = 1,r = n,ans;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
rep(i,1,n,1) s[i] = siz[i] > ans?'1':'0';
check(ans-1);
if(f[1] == 2) getans(ans-1);
s[n+1] = '\0';
cout<<s+1<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int T;cin>>T;while(T--) solve();
}
p
