T1
不会，再见。/fn
T2
题意
有 \(n\) 个奶牛排成一列，每次队头的牛都会插到第倒数 \(c_i\) 个位置上，问有多少个牛无法到达第一位。
思路
是道很厉害的二分。可惜赛时没打出来。
不难发现它是具有单调性的，如果有 \(i\) 头牛可以拿到那么 \(i-1\) 条牛一定可以拿到（废话）。
这启发我们想到二分答案。
check 是好写的，判断一下前 \(mid\) 个是否可以全取到即可。
时间复杂度 \(O(n \log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=1e5+10;
ll ans;
int n,m,T,a[N],q[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline bool check(int mid){
memset(q,0,sizeof(q));
for(register int i=1;i<=mid;++i) q[a[i]]++;
for(register int i=1;i<=n;++i) q[i]+=q[i-1];
for(register int i=1;i<=n;++i) if(q[i-1]<i&&q[i]>=i) return 0;
return 1;
}
int main(){
n=read();
for(register int i=1;i<=n;++i) a[i]=n-read();
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d",n-l);
return 0;
}
T3
不会，看上去是大模拟，爬。
T4
不会 \(\text{dp}\)。
T5
唯一赛时做出来的一道。/ll
题意
给定一棵 \(n\) 个节点的无根树，每个叶子节点都视为一个出入口，有一只奶牛想要从出入口逃走，但农夫们不想要这样，他们可以派人守在出入口。
每一个时间内，奶牛和农夫都可以移动到相邻的节点上，并且农夫知道奶牛会如何移动，问对于每一个起始 \(i\)，农夫们最少需要多少人才能不让奶牛逃脱？
思路
听说正解是点分治啊。很厉害。但暴力草过去了是怎么回事呢。/yiw
首先发现答案可以由两部分构成，一个是直接从子树中的叶子结点润掉，另一个就是先润到父亲节点再走。
直接在子树中的答案是简单的，我们考虑对于一个叶子节点，怎样才能不放人就守住该节点。
我们只需要保证存在另一个存在农夫的叶子结点 \(x\)，它与该节点的距离小于根节点到该点的距离即可。可以用一种类似于分治的怪方法写完。
然后考虑要走到父亲的答案。
我们希望的是让农民数越少越好，所以在离当前节点最近的叶子节点上面放一定是优的。
然后用一个类似前缀 \(\max\) 的东西记录下从 \(1\) 到当前节点的链上面离当前节点最近的叶子即可。
复杂度不太好算，极限数据可以卡到 \(3s\) 左右，但是可以通过本题。
代码
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=1e5+10;
struct node{
int to,nxt,sz,us;
}a[N<<1];
int n,m,T,head[N],cnt;
int nxt[N],d[N],p[N],ans[N],f[N],rd[N],pre[N],pd[N],pp[N],maxn[N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void add(int from,int to){
a[++cnt]=(node){to,head[from],0,1};
head[from]=cnt;
}
void dfs(int x,int fa){
d[x]=d[fa]+1;
f[x]=fa;
p[x]=1e9;
int tot=0,id;
for(register int i=head[x];i;i=a[i].nxt){
int to=a[i].to;
if(to==fa) continue;
dfs(to,x);
++tot;
id=to;
a[i].sz=nxt[to];
if(p[to]+1<p[x]){
pp[x]=p[x];
p[x]=p[to]+1;
maxn[x]=to;
}else if(p[to]+1<pp[x]) pp[x]=p[to]+1;
}
if(tot==1) nxt[x]=nxt[id];
else nxt[x]=x,pd[x]=1;
if(p[x]==1e9){
p[x]=0;
}
}
int calc(int x,int de){
if(p[x]<=de) return 1;
int res=0;
for(register int i=head[x];i;i=a[i].nxt){
int to=a[i].to;
if(!a[i].us||f[x]==to) continue;
res+=calc(nxt[to],de+d[nxt[to]]-d[x]);
}
return res;
}
void calcson(int x,int fa){
if(pd[fa]) pre[x]=fa;
else pre[x]=pre[fa];
for(register int i=head[x];i;i=a[i].nxt){
int to=a[i].to;
if(to==fa) continue;
int q=a[i].sz;
ans[x]+=calc(q,d[q]-d[x]);
calcson(to,x);
}
}
int sv[N],sid[N];
void calcfa(int x,int fa){
if(fa!=0){
if(p[fa]==1){
ans[x]++;
}else{
int now=pre[x];
while(now!=0){
if(sv[now]+d[sid[now]]+d[now]-d[sid[now]]<=d[x]-d[now]){
ans[x]++;
break;
}
ans[x]+=calc(now,d[x]-d[now]);
now=pre[now];
}
}
}
sv[x]=1e9,sid[x]=-1;
for(register int i=head[x];i;i=a[i].nxt){
int to=a[i].to;
if(to==fa) continue;
a[i].us=0;
if(to==maxn[x]){
if(pp[x]-d[x]<sv[fa]){
sv[x]=pp[x]-d[x];
sid[x]=x;
}else{
sv[x]=sv[fa];
}
}else{
if(p[x]-d[x]<sv[fa]){
sv[x]=p[x]-d[x];
sid[x]=x;
}else{
sv[x]=sv[fa];
}
}
calcfa(to,x);
sv[x]=1e9,sid[x]=-1;
a[i].us=1;
}
}
int main(){
n=read();
int root=1;
for(register int i=1;i<n;++i){
int u=read(),v=read();
add(u,v),add(v,u);
++rd[u],++rd[v];
if(rd[u]>=2) root=u;
if(rd[v]>=2) root=v;
}
d[0]=-1;
dfs(root,0);
sv[0]=1e9;
calcson(root,0);
calcfa(root,0);
for(register int i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}