前言
- 比赛链接。
被签到题爆踩了，主要就是签到题没打排名就炸了，T1 看一眼没思路就去看 T2 了，T2 一眼有思路结果少取了一个等挂了 \(25\)，本地没开 O2 跑的巨慢卡了半天长，交上去跑飞快？T4 题都读错了，以为 \(m\) 是边数，就寻思着图上怎么跑，干脆没打，赛后才发现是树。
总之打得非常唐。
T1 Fate
赛时被签到题爆踩，赛后又改了一下午？不是为啥我不会签到题啊？
请来 master 来帮忙，最后还是学了他的方法。
发先即 \(s\sim t\) 每条最短路径中必须且只能选择一个拐点使路径长度 \(+1\)。
定义 \(f_{x,0}\) 表示当前点为 \(x\)，从 \(t\sim x\) 路径上还没有使用长度 \(+1\) 的机会的方案书，\(f_{x,1}\) 就是使用了的。
对于边 \((x,y)\)，有：
\[\begin{cases} f_{x,0}=[dis_x=dis_y+1]\times f_{y,0}+[dis_x=dis_y]\times f_{y,1} \\ f_{x,1}=[dis_x=dis_y+1]\times f_{y,1} \\ \end{cases} \]从 \(t\) 开始从后往前记忆化深搜即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,s,t,dis[N],f[2][N];
bool vis[N];
vector<int>e[N];
int add(int x,int y)
{
x+=y;
return x>=P?x-P:x;
}
void bfs(int s)
{
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[s]=0; q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int y:e[x])
if(dis[y]>dis[x]+1)
{
dis[y]=dis[x]+1;
if(!vis[y]) q.push(y);
}
}
}
int dfs(bool flag,int x)
{
if(f[flag][x]!=-1) return f[flag][x];
if(x==s) return flag;
int ans=0;
if(flag)
{
for(int y:e[x])
if(dis[x]==dis[y]+1) ans=add(ans,dfs(1,y));
}
else
{
for(int y:e[x])
{
if(dis[x]==dis[y]+1) ans=add(ans,dfs(0,y));
if(dis[x]==dis[y]) ans=add(ans,dfs(1,y));
}
}
return f[flag][x]=ans;
}
signed main()
{
read(n),read(m),read(s),read(t);
for(int i=1,x,y;i<=m;i++)
{
read(x),read(y);
e[x].push_back(y);
e[y].push_back(x);
}
bfs(s);
memset(f,-1,sizeof(f));
write(dfs(0,t));
}
T2 EVA
-
还真不知道咋部分分。
发现 \(n\) 很小有很多操作空间。
显然对于一次捕捞，其左端点紧挨着一只鱼是最优的，这样还有可能在右面多捞几只。
所欲枚举左端点是那一条鱼，那么对于其他的鱼定义其在范围内的时刻为区间 \([l_i,r_i]\)，处理完之后将其按照左端点排序扫一遍即可。
可以使用堆，将其右端点为第一关键字扔进去，加入新决策时将右端点小于当前左端点的排除即可，同时更新答案。
处理其合法时刻区间 \([l_i,r_i]\) 的时候细节比较多，赛时因为少取了一个等挂分了，同时 double 不要直接进行大小比较，要用 eps。
复杂度 \(O(n^2\log n)\)，开 O2 和不开 O2 区别挺大的。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e3+10,M=4e6+10;
const double eps=1e-10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,tot,w[N],x[N],v[N],ans;
struct aa {double l,r; int w;}e[N];
bool cmp(aa a,aa b) {return a.l-b.l<eps;}
priority_queue<pair<double,int> >q;
signed main()
{
read(n),read(m);
for(int i=1;i<=n;i++)
read(w[i]),read(x[i]),read(v[i]);
for(int i=1;i<=n;i++)
{
tot=0;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(x[j]<x[i]&&v[j]<=v[i]) continue;
if(x[j]>x[i]+m&&v[j]>=v[i]) continue;
double vji=(double)(v[j]-v[i]);
double vij=-vji;
double xij=(double)(x[i]-x[j]);
double xji=-xij;
double ximj=(double)(x[i]+m-x[j]);
double xjim=-ximj;
double l,r;
if(x[j]<x[i]) l=xij/vji;
else
{
if(x[j]>x[i]+m)
l=xjim/vij;
else l=0;
}
if(v[i]==v[j]) r=1e11;
else if(v[j]>v[i]) r=ximj/vji;
else if(v[j]<v[i]) r=xji/vij;
if(r-l<eps&&abs(r-l)>eps) continue;
e[++tot]={l,r,w[j]};
}
sort(e+1,e+1+tot,cmp);
int sum=w[i];
ans=max(ans,sum);
for(int j=1;j<=tot;j++)
{
while(!q.empty())
{
auto a=q.top();
int x=a.second;
double y=-a.first;
if(y-e[j].l<eps&&abs(y-e[j].l)>eps)
{
q.pop();
sum-=x;
}
else break;
}
sum+=e[j].w;
q.push(make_pair(-e[j].r,e[j].w));
ans=max(ans,sum);
}
while(!q.empty()) q.pop();
}
write(ans);
}
T3 嘉然登场
-
原题：[ARC148E] ≥ K。
-
部分分 \(20pts\)：对于 \(n\le 10\) 的点爆搜即可。
-
部分分 \(20pts\)：对于只有 \(0,1\) 的序列不让 \(0\) 相邻即可，设 \(n=cnt_1,m=cnt_0\)，插空法有 \(ans=C_{n+1}^{m}\)。
-
正解：
将 \(a_i\) 排好序后分成两组，分别为 \(2a_i<k\) 和 \(2a_i\ge k\)，明明为 \(1\) 组和 \(2\) 组，考虑其相邻情况。
首先有任意两个 \(1\) 组数不能相邻，任意两个 \(2\) 组数可以相邻，考虑 \(1\) 组和 \(2\) 组相邻的情况。
对于一个 \(1\) 组的 \(a_i\)，找到能时期满足 \(a_i+a_j\ge k\) 的最小的 \(2\) 组里的 \(a_j\)，那么从 \(a_j\sim a_n\) 均能与其相邻，其余未填的数均不能与其相邻。
考虑每放入一个 \(1\) 组的 \(a_i\) 前，先把满足条件的 \(a_j\) 都放进去，最后另 \(a_i\) 放在鱼其中一个 \(a_j\) 相邻的位置即可。
每放入一个 \(2\) 组的 \(a_i\)，其自身会占领一个位置，因为排好序了，后面填的数均能与其相邻，其左右优扩展出两个位置，故此每放入一个位置数量 \(+1\)，设 \(a_i\) 的数量为 \(cnt_{a_i}\)，原来有 \(sum\) 个位置，隔板法有其贡献为 \(C_{cnt_{a_i}+sum-1}^{sum-1}\)。
每放入一个 \(1\) 组的 \(a_i\)，其自身会占领一个位置且后面填的数均不能与其相邻，不会扩展新的位置，故有贡献为 \(C_{sum}^{cnt_{a_i}}\)。
最后将没放完的 \(2\) 组的都放进去即可，因为题目保证有解，不可能 \(2\) 组先放完。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=2e5+10,P=998244353; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} ll n,m,k,a[N],l,r,mid,sum,b[N],cnt[N],inv[N],jc[N],ans; ll qpow(ll a,ll b) { ll ans=1; for(;b;b>>=1) { if(b&1) (ans*=a)%=P; (a*=a)%=P; } return ans; } void pre() { jc[0]=1; inv[0]=qpow(jc[0],P-2); for(int i=1;i<=n;i++) { jc[i]=jc[i-1]*i%P; inv[i]=qpow(jc[i],P-2); } } ll C(int n,int m) { if(n<m) return 0; return jc[n]*inv[n-m]%P*inv[m]%P; } signed main() { read(n),read(k); pre(); for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+1+n); a[n+1]=-1; sum=1; for(int i=2;i<=n+1;i++) { if(a[i]==a[i-1]) sum++; else { m++; b[m]=a[i-1]; cnt[m]=sum; sum=1; } } l=1,r=m,mid=0; while(b[mid]*2<k&&mid<=m) mid++; if(b[mid]*2>=k) mid--; ans=sum=1; for(;l<=mid;l++) { while(r>mid&&b[l]+b[r]>=k) { (ans*=C(cnt[r]+sum-1,cnt[r]))%=P; sum+=cnt[r]; r--; } (ans*=C(sum,cnt[l]))%=P; sum-=cnt[l]; } while(r>mid) { (ans*=C(cnt[r]+sum-1,cnt[r]))%=P; sum+=cnt[r]; r--; } write(ans); }
T4 Clannad
我用的是回滚莫队的做法。
首先题目没有强制在线且询问为一个区间，没有修改，很适合用莫队冲。
- 结论：一颗虚树经过的边的数量等于每组 \(dfs\) 序相邻的两个点的距离之和（头和尾也算一组相邻）除以 \(2\)，点的数量直接 \(+1\) 就行了。
对于这个结论，发现对于每个点直接动态维护其 \(dfs\) 序的前驱后继即可，于是有了 \(O(n\sqrt{n}\log n)\) 的套 set 做法，无法通过此题。
考虑使用不添加莫队。即只有删除，那么可以用回滚莫队套链表 \(O(1)\) 的删除，最后复杂度为 \(O(n\sqrt n)\)。
思路很好理解，但我不会链表也不会 \(O(1)\) 求 lca，赛后只好现学。
略带卡常，OJ 开 \(2s\) 过不去，改成 \(2.5s\) 再卡卡常能过，感谢学长带我卡常 >_<。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,q,t,tot,l,r,sum,a[N],b[N],dep[N],dfn[N],mi[N][20],cnt[N],to[N],ans[N],last[N],pos[N];
vector<int>e[N];
struct aa {int l,r,id;}g[N];
bool cmp(aa a,aa b) {return pos[a.l]==pos[b.l]?a.r>b.r:a.l<b.l;}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1; dfn[x]=++tot; mi[tot][0]=fa; to[tot]=x;
for(int y:e[x]) if(y!=fa) dfs(y,x);
}
int min_(int x,int y) {return dfn[x]<dfn[y]?x:y;}
void ST()
{
for(int j=1;j<=__lg(n);j++)
for(int i=1;i+(1<<j)-1<=n;i++)
mi[i][j]=min_(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
int lca(int x,int y)
{
if(x==y) return x;
x=dfn[x],y=dfn[y];
if(x>y) swap(x,y);
x++; int t=__lg(y-x+1);
return min_(mi[x][t],mi[y-(1<<t)+1][t]);
}
int dis(int x,int y) {return dep[x]+dep[y]-2*dep[lca(x,y)];}
struct bb
{
int nxt[N],pre[N],l,r;
void init()
{
for(int i=1,p=0;i<=n;i++)
if(cnt[i])
{
if(!l)
{
l=r=i;
p=i;
continue;
}
pre[i]=p,nxt[p]=i,r=i;
sum+=dis(to[p],to[i]);
p=i;
}
sum+=dis(to[l],to[r]);
}
void del(int x)
{
if(!pre[x]&&!nxt[x]) l=r=0,sum=0;
if(pre[x]&&nxt[x])
sum=sum-dis(to[pre[x]],to[x])-dis(to[x],to[nxt[x]])+dis(to[pre[x]],to[nxt[x]]);
if(!pre[x]&&nxt[x])
{
sum=sum-dis(to[x],to[nxt[x]])-dis(to[x],to[r])+dis(to[nxt[x]],to[r]);
l=nxt[x];
}
if(pre[x]&&!nxt[x])
{
sum=sum-dis(to[pre[x]],to[x])-dis(to[l],to[x])+dis(to[l],to[pre[x]]);
r=pre[x];
}
nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
}
void add(int x)
{
if(!l) l=r=x;
if(pre[x]==r) r=x;
if(nxt[x]==l) l=x;
nxt[pre[x]]=pre[nxt[x]]=x;
}
}lst;
signed main()
{
read(n),read(m),read(q);
for(int i=1,x,y;i<=n-1;i++)
{
read(x),read(y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=m;i++) read(a[i]);
for(int i=1,l,r;i<=q;i++)
{
read(l),read(r);
g[i]={l,r,i};
}
dfs(1,0); ST();
t=400;
for(int i=1;i<=m;i++) pos[i]=(i-1)/t+1;
sort(g+1,g+1+q,cmp);
for(int i=1;i<=m;i++) b[i]=dfn[a[i]];
for(int i=1;i<=m;i++) a[i]=b[i];
for(int i=1;i<=m;i++) cnt[a[i]]++;
lst.init();
l=1,r=m;
for(int i=1,j=1;j<=pos[m];j++)
{
int bl=t*(j-1)+1;
while(l<bl)
{
cnt[a[l]]--;
if(!cnt[a[l]]) lst.del(a[l]);
l++;
}
int last_s=sum; bb last_l=lst;
for(int k=1;k<=n;k++) last[k]=cnt[k];
for(;pos[g[i].l]==j;i++)
{
while(r>g[i].r)
{
cnt[a[r]]--;
if(!cnt[a[r]]) lst.del(a[r]);
r--;
}
int old=sum;
while(l<g[i].l)
{
cnt[a[l]]--;
if(!cnt[a[l]]) lst.del(a[l]);
l++;
}
ans[g[i].id]=sum;
while(l>bl)
{
l--;
if(!cnt[a[l]]) lst.add(a[l]);
cnt[a[l]]++;
}
sum=old;
}
sum=last_s,lst=last_l,r=m;
for(int k=1;k<=n;k++) cnt[k]=last[k];
}
for(int i=1;i<=q;i++) write(ans[i]/2+1),puts("");
}
总结
想 T1 这种题就属于不能死扣也不能放弃那种（不 swap 的），扔了分数就不可观，死扣就会影响下面的题，所以不要瞧不起签到题，还是很考验实力和心态的（所以是不是只要能看到 T1 就秒掉就没有这些破事儿了），所以还是要提升实力。
注意细节与读题。
附录
int_R 直接 AK 了膜拜，并获得了学长画的穗一张：
