赛时喜提 \textcolor{green}{100}+\textcolor{red}{0}+\textcolor{orange}{30}+\textcolor{red}{5}=\textcolor{orange}{135} ，但其实真的是信心赛，仅花 10min 就补成 \textcolor{green}{100}+\textcolor{green}{100}+\textcolor{orange}{30}+\textcolor{gold}{65}=\textcolor{yellowgreen}{295} 了。
T1 Divisors
水题，对每个数 O(\sqrt n) 求因子，开桶开 map 算贡献即可。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt",stdout)
#define cio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using ll=long long;
using ull=unsigned long long;
const int N=210;
int n,m;
int a[N];
map<int,int>t;
int ans[N];
int sum;
int main(){
//fio("div");
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
for(int j=1;j*j<=a[i];++j){
if(a[i]%j)continue;
if(j*j==a[i])++t[j];
else ++t[j],++t[a[i]/j];
}
}
for(pair<int,int>p:t){
if(p.first>m)break;
++ans[p.second];
++sum;
}
ans[0]=m-sum;
for(int i=0;i<=n;++i)printf("%d\n",ans[i]);
return 0;
}
T2 Market
仍然水题，思路想贼快，赛时没过装你吗呢。
先考虑只有一次购物的情况，显然要背包 \texttt{dp} ，但体积值域过大，价值过小，所以将价值设进状态中，即设 f_{i,j} 表示考虑前 i 个物品，当前价值为 j 的最小需要体积，方程 f_{i,j}=\min(f_{i-1,j},f_{i-1,j-v_i}+c_i)，然后考虑多次购物，先把物品和查询分别按时间从小到大排序，然后顺序枚举查询，同时保证这个查询前的前缀背包做完，查询时用二分。
赛时二分用了个贼唐的写法，把有用的值丢 vector 里取相反数再 lower_bound ...明明取个后缀最小值二分就好了。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
#define cio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using ll=long long;
using ull=unsigned long long;
const int N=310,M=1e5+10,V=1e9;
const ll inf=1e18;
int n,m;
int sum;
struct store{
int c,v,t;
}s[N];
struct query{
int t,id;
ll x;
}q[M];
int ans[M];
ll f[2][N*N];
ll tmp[N*N];
void ins(int x){
for(int i=0;i<=sum;++i){
f[x&1][i]=f[x-1&1][i];
if(i-s[x].v>=0)
f[x&1][i]=min(f[x&1][i],f[x-1&1][i-s[x].v]+s[x].c);
}
for(int i=sum;i>=0;--i)tmp[i]=min(tmp[i+1],f[x&1][i]);
}
int ask(ll x){
int l=0,r=sum,mid;
while(l+1<r){
mid=l+r>>1;
if(tmp[mid]<=x)l=mid;
else r=mid;
}
if(tmp[r]<=x)return r;
else return l;
}
int main(){
// tio();
// fio("market");
cio();
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>s[i].c>>s[i].v>>s[i].t;
sum+=s[i].v;
}
for(int i=1;i<=m;++i){
cin>>q[i].t>>q[i].x;
q[i].id=i;
}
for(int i=0;i<2;++i)
for(int j=0;j<=sum;++j)
f[i][j]=1e18;
for(int i=1;i<=sum+1;++i)tmp[i]=1e18;
tmp[0]=0;
f[0][0]=0;
sort(s+1,s+1+n,[](store a,store b)->bool{return a.t<b.t;});
sort(q+1,q+1+m,[](query a,query b)->bool{return a.t<b.t;});
for(int i=1,j=1;i<=m;++i){
while(j<=n&&q[i].t>=s[j].t)ins(j),++j;
ans[q[i].id]=ask(q[i].x);
}
for(int i=1;i<=m;++i)cout<<ans[i]<<"\n";
return 0;
}
/*
5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9
*/
T3 连通性
赛时没看这题，打了 \texttt{30pts} 跑了，感觉应该不难？
m=0 时就是任意图都行，每条边取或不取，2^{\frac{(n-1)n}{2}}
m=n 时就是若干互不连通的完全图，直接递推，设 f_{i,j} 为 i 个点，j 个图，f_{i,j}=jf_{i-1,j}+f_{i-1,j-1}
正解待补。
T4 树
区间和并鼠目寸光加树剖板子不熟 \texttt{65pts} -> \texttt{5pts} 。
（悲
发现一个事情，两路径有交时只要一条路经确定方向，另一条路径也确定了，所以一条路径等价于将这条路径所有边并为一个集合，初始一条边为一个集合。所以直接边下放到点树剖，用并查集给定路径上边集合个数， set 辅助用于区间合并 + 集合合并。
但这样做有个问题，那就是判不了无解，想要判无解还要上个线段树，那样代码就太巨了。其实我赛后写了线段树懒得调了
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
#define cio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using ll=long long;
using ull=unsigned long long;
const int N=3e5+10,mod=1e9+7;
int n,m;
vector<int>g[N];
int siz[N],hs[N],de[N],fa[N];
void dfs1(int u,int fath){
siz[u]=1;
fa[u]=fath;
de[u]=de[fath]+1;
for(int v:g[u]){
if(v==fath)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hs[u]])hs[u]=v;
}
}
int dfn[N],top[N];
int cnt;
void dfs2(int u,int topf){
dfn[u]=++cnt;
top[u]=topf;
if(hs[u])dfs2(hs[u],topf);
for(int v:g[u]){
if(v==fa[u])continue;
if(v==hs[u])continue;
dfs2(v,v);
}
}
struct djs{
int fa[N];
int tot;
void init(int m){
tot=m;
for(int i=1;i<=m;++i)fa[i]=i;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int mer(int x,int y){
x=find(x),y=find(y);
if(x==y)return x;
--tot;
fa[x]=y;
return y;
}
}ds;
struct node{
int l,r,v;
bool operator < (const node& b)const{
if(l!=b.l)return l<b.l;
return r<b.r;
}
};
set<node>s;
void ins(int l,int r,int v){
if(l>r)return ;
if(s.size()==0){
s.insert({l,r,v});
return ;
}
auto il=s.lower_bound({l,r,v});
if(il!=s.begin()&&prev(il)->r>=l)--il;
auto ir=il;
for(;ir!=s.end()&&ir->l<=r;++ir){
l=min(l,ir->l);
r=max(r,ir->r);
v=ds.mer(v,ir->v);
}
s.erase(il,ir);
s.insert({l,r,v});
}
void pm(int x,int y,int col){
while(top[x]!=top[y]){
if(de[top[x]]<de[top[y]])swap(x,y);
ins(dfn[top[x]],dfn[x],col);
x=fa[top[x]];
}
if(de[x]>de[y])swap(x,y);
ins(dfn[x]+1,dfn[y],col);
}
ll qpow(ll a,int x){
ll res=1;
while(x){
if(x&1)(res*=a)%=mod;
(a*=a)%=mod,x>>=1;
}return res;
}
ll ans;
int main(){
// tio();
// fio("usmjeri");
cio();
cin>>n>>m;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
ds.init(m);
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
pm(u,v,i);
}
int tmp=n-1;
for(node it:s){
tmp-=(it.r-it.l+1);
}
ans=(qpow(2,ds.tot+tmp));
cout<<ans;
return 0;
}
感觉正解应该是一个优美的 \texttt{dp} 啥的，毕竟我一开始也是往 \texttt{dp} 去想的。
正解待补。