3月做题记录

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

「在家=摸鱼」系列

ABC157F Yakiniku Optimization Problem

请先思考后再展开

很容易想到二分,问题转化为给出n个圆,是否存在一个区域被至少K个圆覆盖

被教育了,写了个乱搞只能过大部分数据,果断跑路打cf去了

结论:圆的交集的每段弧都是圆上的,只要不是只有一段弧(一个圆),就会有两弧的公共点,这一定是两圆交点的子集,可以用这个点代替圆的交集

因此这个区域可以由上面的点去考虑,所以总共要考虑的点集就是两圆交点、每个圆上取一点,枚举每个点再枚举每个圆判断,$O(log_{2}(ans/eps)* n^3)$,code

「NOI Online 提高组」序列

请先思考后再展开

首先显然操作2就是缩点,然后我们要用操作1,让所有点的和都是0

注意到一个奇环可以让环上某个点+=2而其他点不变,另一个经典套路是生成树可以让除了根外的所有点变成0

因此对每个联通块跑一次黑白染色来判断是否有奇环,如果有就给根当前值模2,然后判断当前值为0即可,code

CF1312G Autocompletion

题意:给一个Trie,取其中若干个点到根路径(因此称这个点为特殊点)得到集合S,对于集合S中每个字符串,求出得到这个字符串的最小花费。从根节点开始,每次向下到儿子花费1,也可以花费i到子树中字典序第i大的S中字符串去

请先思考后再展开

我的做法好像算是特别短的了,然而因为神志不清赛中没过,结束后手写板清屏写下三句话,翻译到c++,就过了……

注意到如果最后是从节点z到x,一定是先到z祖先中最近的特殊点lst走到z再跳。

因此记录$up=\min_{祖先t} dp_{lst \ of \ t}+dis(lst,t)+[递归到x时的tg_t]$,因为每次会对所有祖先做$tg+=tg_y$,所以很好维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
map<char,int> son[N];int dep[N],tg[N],dp[N];
void pre(int x,int fa,int up,int lst)
{
dep[x]=(x>0?dep[fa]+1:0);
dp[x]=min(up+1,dp[lst]+dep[x]-dep[lst]);
if(tg[x]) lst=x;chmin(up,dp[lst]+dep[x]-dep[lst]);
up+=tg[x];//就这三句,别问我为什么花了1.5h
for(auto t:son[x]) if(t.SE!=fa)
{
int y=t.SE;
pre(y,x,up,lst);
tg[x]+=tg[y];up+=tg[y];
}
}
int pos[N];
void main()
{
int n=qread();fo(i,1,n){ int fa=qread();char c[5];scanf("%s",c); son[fa][c[0]]=i; }
int k=qread();fo(i,1,k) pos[i]=qread(),tg[pos[i]]++;pre(0,-1,0,0);
fo(i,1,k) write1(dp[pos[i]]);
}

panasonic2020F Fractal Shortest Path

题意:在一个无限大的如图所示分形里,黑色为禁区,q次询问两点最短距离,移动方式为四连通

请先思考后再展开

找到一个最大的禁区块,使得其x完整覆盖x1x2,或y完整覆盖y1y2,那就必须要绕路走,而周围的一圈一定都是非禁区,容易发现只有这种情况,会在曼哈顿距离的基础上额外花费。$O(qlog_3a)$

1
2
3
4
5
6
7
8
ll solve(ll T,ll x1,ll y1,ll x2,ll y2)//x--,y--后
{
ll xx1=x1/T,yy1=y1/T,xx2=x2/T,yy2=y2/T;
if(xx1==xx2 and xx1%3==1 and abs(yy1-yy2)>=2) {x1%=(T*3),x2%=(T*3);return min(x1+x2-(T-1)*2,(T+T)*2-x1-x2)+abs(y1-y2);}
if(yy1==yy2 and yy1%3==1 and abs(xx1-xx2)>=2) {y1%=(T*3),y2%=(T*3);return min(y1+y2-(T-1)*2,(T+T)*2-y1-y2)+abs(x1-x2);}
if(T==1) return abs(x1-x2)+abs(y1-y2);
else return solve(T/3,x1,y1,x2,y2);
}

SRM735 MaxSquare

题意:给定长度为$n \le 1e5$的序列b,求$\max 2(s_i-s_j)(i-j)$

题解

loj2257「SNOI2017」遗失的答案

题意:给定$n,G,L \le 1e8$,q次询问x,求有多少个${1,2,..n}$的子集,满足gcd=G,lcm=L,且包含x

请先思考后再展开

相当于在${1,2,..n’=n/G}$中找个包含$x’=x/G$的子集,满足gcd=1且$lcm=L’=L/G$,最坏情况显然就是G=1,所以不用管G

因为选出的数一定都是lcm的约数,即$x’|L’$,即本质不同的询问只有几千个,且要考虑的数集合大小也是几千个,另外L’的不同质因子不超过8个。直接dp每个素因子是否有0和mx相当于,将约数个集合幂级数或卷积起来

容斥为不包含x肯定好搞

一开始想着,合并前后缀,这样时空都是$O(2^{2*8}*1e3)$,空间带上个常数2后超过500MB,似乎luogu那里没开这么大

那就是额外做个集合幂级数除法,但这样带多个log,时间爆炸

在想到集合幂级数之前想过对每组询问,两个循环搞容斥也是可以的,不确定对不对,但是肯定没有集合幂级数优美,不管了

穷途末路,向Itst学习了一下,呃……

就是咱别管啥或卷积了,答案的式子并不难写:$\sum_S (-1)^S 2^{\sum_{二进制状态j} [j \subseteq U \oplus S]}$,于是我们可以直接累计每种二进制的出现次数,并维护次数的子集和,回退直接超集–就完事了,而且这种做法不写fwt可能也能过

CF908H New Year and Boolean Bridges

题意:给出一个对角线无意义的对称方阵,元素$(i,j)=’A’/‘O’/‘X’$分别表示这两点间的关系是:强联通、可达、不强连通且可达。求一个合法的n个点有向图,最小化边数

请先思考后再展开

对于一个确定的强连通分组方案,每个联通块直接形成一条链就行了,而每个强连通内肯定是一个环最优(但要注意大小为1的),即最小化$n-联通块数+[大小>1的强连通数]$

因为这个方阵是满的,联通块数一定是1,所以先把必定强连通的缩成一个点,然后原本就一个点就直接删掉(合并不会更优),等价于一个无向图,将点染色,使得相邻不同色,最小化颜色数(注意!此时点数m不超过23)

试图搜索k染色结果找到了cqzhangyu写的这题题解……好像写得挺好的,link

不过其实几句就讲完了,就是随机一个模数当做计数去做,会发现特别好做,就是预处理可行独立集,然后用fwt或卷积,判断k可行的条件显然为$\sum_S (-1)^{|U \setminus S|} A_S^i$,$O(m2^m)$

CF1215D Ticket Game

请先思考后再展开

虽然这题dif只有1700,感觉也不是很水,而且是这套里最有趣的了

转化题意为,i次加,j次减,最后后手希望能恰好是wt

先考虑j=0,发现如果$wt<(i/2)*9$,先手可以直接超过,而如果$wt>(i/2)*9$,先手可以全0不走,因此要求$wt=(i/2)*9$

然后多提供k次加,k次减,先手只要每次往最坏方向跳9,后手就不得不选反方向跳9,因此公共的k无意义

code

CF1327F AND Segments

请先思考后再展开

dls又发视频了

明显拆位,问题转化成若干区间必须全是1,若干区间必须存在0,看起来很经典,但智商下线划水30min就跑去做G了

现在一看,全是1相当于ban掉了若干位置放0的可能,相当于在能放的地方放若干个dp,且在每个右端点时需要满足上个0放的范围是个后缀,因为处理i时只会修改$dp_{i,i}$,一个状态非法后以后也是非法,所以可以写成线性的dp,总复杂度$O(nloga)$

1
2
3
4
5
6
7
8
fo(i,1,m) if(B[i]&bin(z)) cnt[A[i].FR]++,cnt[A[i].SE+1]--; else chmax(up[A[i].SE],A[i].FR);
fo(i,1,n) cnt[i]+=cnt[i-1];
mem(dp,0);dp[0]=1;int sum=1,pos=0;
fo(i,1,n)
{
if(cnt[i]==0) dp[i]=sum,add(sum,dp[i]);
while(pos<up[i]) add(sum,MOD-dp[pos++]);
}ans=ans*sum%MOD;

CF1327G Letters and Question Marks

请先思考后再展开

看懂题开始码:不涉及?的用hash花$O(nk)$判,一个长度为len的串涉及?的左端点个数为$O(len)$级别,暴力$O(len^2)$判断能否匹配,能的话给每个?统计是字母c的话的贡献,然后跑个$O(2^{14}14)$的沙雕状压

求稳写了个双hash,结果赛后才过样例。手速慢是我的问题,但我完全搞不懂这出题人是怎么想的,闲着没事n开这么大卡人常数荣获tle,改单hash又wa,最后只好改成在cf从来没用过的kmp(因为太少用,并没有存kmp和ac机的板子),当然复杂度一样,code

其实如果我之前准备好便捷使用的hash和kmp板子说不定能在当时30min内搞出来

Codechef WEASELSC

题意:给出长度为n的序列a,求一个长度为n的非负整数序列b,最大化b的序列和,要求b最多一个非0连续段。

对于这个连续段中元素,$\forall i,b_i \le a_i$,且不增或不减,且不同数字个数不超过K+1个,$n,a_i \le 1e5,k \le 50$

请先思考后再展开

递减的不用管,翻转a再做一次就好了

核心观察1:看做不超过k段区间,每段区间值相同,那么一定满足区间的值就是区间的min,因为如果向上首先是被后面的人限制了,可以将这两段区间合并

设$lf_i和rf_i$分别表示向左、向右第一个更小的数,考虑对于一个方案在区间最小值计算贡献那么就是做K次下述dp

$$
g_i=\max_{i<j \le rf_i} f_j+a_i(lf_j-lf_i)
$$

核心观察2:做若干次$j=lf_j$后一定能到达i,因此设$fa_i=lf_i$得到的树上,转移集合就是子树中。子树没有祖先方便处理,因此考虑换成从小到大的形式
$$
g_x=\max_{y \in arc_x} dp_y+a_y(fa_x-y)+a_x(x-fa_x)
$$

很明显可以斜率优化了,而且进一步考虑性质可以避免使用树上cdq

首先编号是单调的,因此横坐标是单调递增的,我们在末尾弹栈的时候,不要修改栈中没必要修改的地方,记录原本的栈尾在哪里,就能快速还原了。口胡复杂度为$O(nlogn)$。

看起来是另一种做法

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