4月做题记录

4月做题记录
最后一个4月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

「在家=摸鱼」系列

USACO18DEC The Cow Gathering

请先思考后再展开

提供一些hack数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
8 2
1 2
2 3
1 4
4 5
4 6
6 7
6 8
2 8
4 3
0...
4 2
1 3
1 2
3 4
3 2
2 4
0000
4 2
1 2
2 3
3 4
1 2
3 4
0001
9 2
9 1
1 3
3 4
4 2
3 5
4 6
6 8
6 7
5 3
6 7
000000100

树形结构显然只是结构,下文的建图建边都是指,若x要早于y,则x连向y,而与树边完全无关

首先点rt可以作为答案的条件,就是把rt看做根,不存在任何一个点能直接或间接到达子树内某点

因此对于任意x能到达y,因为这个条件导致失败的点集,就是以y为根x子树;换句话说,只要把所有失败的删掉,剩下的一定是合法的。然而因为间接到达的缘故不太好直接做,但我们观察到,如果对于节点x为根,能从x到达两棵及以上的子树,那所有点都会被ban掉,即无解。因此只要把无解判掉,x一定只能到达最多一棵子树,此时x无论能到达里面哪里,ban掉的范围都是除了那棵子树的部分,因此可以直接用给出的m个限制判而不需要考虑间接的情况了。

而是否有解其实很好判,写个类似拓扑的东西,将树边看做两条有向边,限制看做一条有向边,然后度数=1的时候把点加入队列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n,m,ind[N];vc<int> to[N],go[N];pii e[N];
bool check()
{
queue<int> q;fo(i,1,n) if(ind[i]==1) q.push(i);int cnt=0;
while(sz(q))
{
int x=q.front();q.pop();cnt++;
for(auto y:to[x]){ ind[y]--;if(ind[y]==1) q.push(y); }
for(auto y:go[x]){ ind[y]--;if(ind[y]==1) q.push(y); }
}return cnt==n;
}
int dep[N],siz[N],dfn[N],dfnid,ff[N][21];
void pre(int x,int fa=0)
{
dfn[x]=++dfnid,dep[x]=dep[fa]+1,siz[x]=1;
ff[x][0]=fa;fo(i,1,20) ff[x][i]=ff[ff[x][i-1]][i-1];
for(auto y:to[x]) if(y!=fa) pre(y,x),siz[x]+=siz[y];
}
int jump(int x,int len){fo(i,0,20)if(len&bin(i))x=ff[x][i];return x;}
int tg[N];
void main()
{
n=qread(),m=qread();fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x);ind[x]++,ind[y]++; }
fo(i,1,m) e[i].FR=qread(),e[i].SE=qread(),go[e[i].FR].PB(e[i].SE),ind[e[i].SE]++;
if(!check()){ fo(i,1,n) write2(0);return; } pre(1);
fo(i,1,m)
{
int x=e[i].FR,y=e[i].SE;
if(dfn[x]<=dfn[y] and dfn[y]<=dfn[x]+siz[x]-1){ int z=jump(y,dep[y]-dep[x]-1);tg[1]++,tg[dfn[z]]--,tg[dfn[z]+siz[z]]++; }
else tg[dfn[x]]++,tg[dfn[x]+siz[x]]--;
}
fo(i,1,n) tg[i]+=tg[i-1];fo(i,1,n) write2(tg[dfn[i]]==0);
}

「NOI Online 2 提高组」涂色游戏CF1260C Infinite Fence

请先思考后再展开

lcm两侧一定是同色,填异色即可,因此只需要求出两个蓝色间最多多少个红色(设红色比蓝色多)

code

upd:cf过了就没看了,然后没判k=1,喜提80

「NOI Online 2 提高组」游戏

请先思考后再展开

首先肯定是先求出$f_i=\sum_{j=i} C_j^i g_j$中的f,然后二项式反演得到g

有足足60min是不会做的,因为当时比较nc想着要记录下面选定了多少个,然后忽然意识到黑色不一定在下面,也可能在上面,所以要修修,啊那就从上面计数,诶那tm下面有多少个可以直接用siz-now求了啊,原来如此……

因此设$dp(x,now)=选了now对$,背包完讨论子树根x选不选即可,$O(n^2)$

CF1334F Strange Function

题意:$n \le 5e5$序列a,删除第i个需要花费$|p_i| \le 1e9$,用最小花费使序列前缀max去重后恰得到b

请先思考后再展开

看到luogu题解区神长只好写一发,虽然写的是bit,但因为拷板子懒得做任何优化并没有在cf榜中有什么优势,重在代码复杂度

无脑设$dp_{i,j}=匹配到a_i和b_j$,如果不选i,$b_j<a_i的 dp_{i-1,j}+p_i \rightarrow dp_{i,j}$而其他可以不动(但是在p是负数时,能移除就移除),选的时候只需要更新最多一处$b_z=a_i,dp_{i,z} \leftarrow dp_{i-1,z-1}$,总复杂度为$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N=1e6+10;
//树状数组
struct BIT
{
ll bit[N];void clear(ll val=0){ mem(bit,val); }
int lowbit(int x){return x&-x;}
void ad(int x,ll c){ while(x<N) bit[x]+=c,x+=lowbit(x); }
ll ask(int x){ ll ret=0;while(x>=1) ret+=bit[x],x-=lowbit(x);return ret; }
void ad(int l,int r,ll c){ ad(l,c),ad(r+1,-c);}
void chmin(int x,ll c){ll now=ask(x);if(c<now) ad(x,x,c-now);}
}dp;//下面的+1都是位移挪出0
//------------------FIXED------------------
int a[N],p[N],b[N],go[N];
void main()
{
int n=qread();fo(i,1,n) a[i]=qread();fo(i,1,n) p[i]=qread();
int m=qread();fo(i,1,m) go[b[i]=qread()]=i;dp.ad(1+1,bin(60));
fo(i,1,n)
if(p[i]<0)
{
dp.ad(0+1,m+1,p[i]);
if(go[a[i]]){ int z=go[a[i]];dp.chmin(z+1,dp.ask(z-1+1)-p[i]); }
}
else
{
if(go[a[i]]){ int z=go[a[i]];dp.chmin(z+1,dp.ask(z-1+1)); }
dp.ad(0+1, lower_bound(b+1,b+m+1,a[i])-b-1+1 ,p[i]);
}
ll ans=dp.ask(m+1);if(ans<=1e16) printf("YES\n%lld",ans); else puts("NO");
}

题意:给出26的排列p和两个小写字母字符串$s、t(|s| \le |t| \le 2e5)$,对t中每个子串$|t’|=|s|$判断是否满足每个位置,要么相等,要么$p_{t’-‘a’+1}=s-‘a’+1$

请先思考后再展开

$(a-b)^2(p_a-b)^2$,做9次NTT(据说需要双模数,不然会被hack)

收获:学会使用wolframalpha

看起来$O(n^2/w)$可过

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/96d3ad28.html
转载请注明出处,谢谢!