12月做题记录

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

好题:「HNOI2015」亚瑟王

「JOISC 2016 Day 1」俄罗斯套娃

请先思考后再展开

肯定先考虑一次询问怎么回答。因为两维考虑放到平面上建点,那么每个点都向严格左下所有点连边,那么就是询问最小不可重路径覆盖,根据Dilworth定理等于最长反链。考虑具体本题中,两个点不可比当且仅当$i,j:a_i \le a_j,b_i \ge a_j$,于是又转化成了最长不增子序列了

多组询问的话,离线下来就是在左边加点,询问纵坐标$\le B$的答案,树状数组查询前缀和即可,$O(nlogn)$

code,短得超乎我想象

「WC2007」剪刀石头布

请先思考后再展开

统计一个竞赛图的三元环个数,于是就是最小化$\sum C_{deg_x}^2$,经典差分,$C_{a+1}^2-C_a^2=a$

起点连向每条边(x<y)流量1,每条边连向两个端点费用0,每个点后面建n个流量1费用为增量的结算边(肯定会把小的边跑满)

code

「THUSC2016」成绩单

请先思考后再展开

听说做完传统题就有一本了,而传统题是两白给题……强行题答大战,不过题答没心情玩了

自然的想法是dp或者搜索,本质上是一个东西qaq

考虑一个区间最后一次选,就是若干个连续段,然后这段区间去掉这些连续段后剩下的若干连续段是独立的,相当于0101010之类的,然后1是我的,0是独立的子问题,考虑怎么不需要一次选出所有连续段,设$f(l,r,mi,mx,0/1)$表示目前处理这个区间且第一个段是不是我自己的,然后我这个区间外左边其实还选了一些人,只需要记录其中的mi和mx即可,然后一个段的代价在最后那个1记录,$O(n^5)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int val(int mx,int mi){int t=max(0,mx-mi);return t*t*B+(mx>=mi)*A;}
int gmi(int x,int y){return w[x]<w[y]?x:y;}int gmx(int x,int y){return w[x]>w[y]?x:y;}
void main()
{
int n=qread();A=qread(),B=qread();fo(i,1,n) w[i]=qread();w[0]=1e3+1;
fo(l,1,n){MI[l][l]=MX[l][l]=l;fo(r,l+1,n) MI[l][r]=gmi(MI[l][r-1],r),MX[l][r]=gmx(MX[l][r-1],r);}
fd(l,n,1) fo(r,l,n) fo(mi,0,n) fo(mx,1,n+1) fd(op,1,0)
{
int now;
if(op) now=val( max(w[mx],w[MX[l][r]]),min(w[mi],w[MI[l][r]]) );
else now=val(w[mx],w[mi])+dp[l][r][0][n+1][1];
fo(k,l,r-1)
{
if(op) chmin(now,dp[k+1][r][gmi(MI[l][k],mi)][gmx(MX[l][k],mx)][0]);
else chmin(now,dp[l][k][0][n+1][1]+dp[k+1][r][mi][mx][1]);
}
dp[l][r][mi][mx][op]=now;
}
write(min(dp[1][n][0][n+1][0],dp[1][n][0][n+1][1]));
}

「ZJOI2008」泡泡堂

请先思考后再展开

枚举至少T个对手能给我们带来得分,易得

1
2
3
4
5
6
7
8
9
10
int check(int T,int a[],int b[])
{
int ret=0,lst=n;
fd(i,T,1)
{
if(a[lst]<b[i]) return 0;
ret+=1+(a[lst]>b[i]),lst--;
}
return ret;
}

gank一发二分发现gg了,那就试一发三分,打出表发现确实满足三分性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int solve(int a[],int b[])
{
int fl=0,fr=n;
while(fr-fl>10)
{
int ln=(fr-fl)/3,left=fl+ln,right=fr-ln;
if(check(left,a,b)<check(right,a,b)) fl=left; else fr=right;
}
int ans=0;fo(i,fl,fr) chmax(ans,check(i,a,b));return ans;
}
int a[N],b[N];
void main()
{
n=qread();fo(i,1,n) a[i]=qread();fo(i,1,n) b[i]=qread();
sort(a+1,a+n+1);sort(b+1,b+n+1);
write1(solve(a,b));write(n*2-solve(b,a));
}

证明是不可能证明的,正经的贪心做法也有些奇妙

bzoj3563 DZY Loves Chinese

请先思考后再展开

k加密了,但我们可以通过这行实际数字反解出前面有多少个连通的,暴力求最后一组询问的答案即可

bzoj3569 DZY Loves Chinese II「AHOI2013」连通图

一句话题意:n点m边q次询问,每次给出大小为k的边集问去掉后图是否连通

前者强制在线,$n \le 1e5,m \le 5e5,q \le 5e4,k \le 15$,不过数据不强;后者$n,q \le 1e5,m \le 2e5,k \le 4$

请先思考后再展开

对于可以离线的后者,闷声上个线段树分治+可回退并查集,$O(qk*logn*logq)$

其实很自然的想法是建个dfs生成树,这样没有横叉边,然后断开的树边形成若干个块看能否通过非树边将他们连通

这种树上增减路径的题目可以考虑随机化+异或,对于本题,给非树边随机一个权值

连通的充要结论:记录每条树边被非树边覆盖的异或和,则被删除的树边不能存在真子集满足异或和=0;证明

可以先树上差分预处理,然后线性基判断合法性,$O(qk(k+30))$,code

poj3718 Facer’s Chocolate Dream

题意:定义长度为n且恰3个1的01串为一个dish,问有多少个大小为m的dish的集合,异或和为$A \oplus B$,$n,m \le 1e3$

请先思考后再展开

一开始以为m个可重,显然$dp_i(n_1)=选了i个数且n-n_1个列为0,n_1个列为1,每次用个组合数转移,O(nm),ans=dp_m(|A \oplus B|)*C_n^{|A \oplus B|}$

其实不可重而且是集合的话,最后除$m!$,这样只需要去掉重复的情况,考虑第i个和前面某个相同了,容斥掉即可

$dp_i(n_1)-=(i-1)dp_{i-2}(n_1)*C_n^3$

「BJWC2011」元素

请先思考后再展开

线性基+贪心?一如既往感性猜结论过拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pll bs[100];
void insert(ll val,ll num)
{
fd(i,60,0) if(num&bin(i))
{
if(!bs[i].FR) {bs[i]={num,val};break;}
else
{
if(val>bs[i].SE) swap(val,bs[i].SE),swap(num,bs[i].FR);
num^=bs[i].FR;
}
}
}
void main()
{
int n=qread();fo(i,1,n) insert(qread(),qread());
int ans=0;fo(i,0,60) ans+=bs[i].SE;write(ans);
}

「HNOI2015」亚瑟王

请先思考后再展开

$$
ans=E(sum)=\sum E_i=\sum i被选中的概率*d_i,只需考虑怎么算概率
\\
考虑一种方案(选的数的集合+被选时间,这里时间是排列而不是轮数)的概率怎么算,\prod (1-p_i)^{被跳过多少轮}p_i^{被选上}
\\
集合容易但排列难搞,对于不选那些只和集合有关随便算,关键是选了的怎么搞
\\
然后我就自闭了,其实只要形式化地写出来就很简单了,总是心里嫌麻烦错过机会qwq
\\
对于大小为m的选数集合S,
\sum_{时间排列t} \prod_{k=1}^m (1-p_{S_k})^{\sum [j>k,t_j<t_k]} p_{S_k}
\\
考虑从后往前插入,\prod_{k=1}^{m} (p_{S_k}\sum_{j=0}^{m-k} (1-p_{S_k})^j )
=\prod (1-(1-p_{S_k})^{m-k+1})
\\
于是直接带权dp这个集合就好了,例如dp_{i,j}=考虑前i个数,选了j个数,此时集合的概率
\\
dp_{i,j}=dp_{i-1,j-1}*(1-(1-p_i)^{r-j+1})+dp_{i-1,j}*(1-p)^{r-j},ans=\sum d_i*\sum_{j} dp_{i-1,j-1}*(1-(1-p_i)^{r-j+1})
$$
有的人是直接看出第一个的系数的,即考虑1-完全不选的概率,而不选的时候却特别好算;$O(Tnr)$,code

CF814E An unavoidable detour for home

题意:问有多少大小为$n \le 50$的无向图,给出每个点的度数$d_x \in [2,3]$,且要求1到每个点x的最短路为$L_x,路径唯一,L_x \le L_{x+1}$

请先思考后再展开

沙雕题,显然考虑bfs分层考虑,而且每层的组成相当于$1,2,3…n$画若干个分割,除了树边只有横叉边且这种边必须在同一层
$$
先处理出f(l,r,a,b)表示[l,r]这个区间为一层,留给以后(可能同层或下一层)有a个度1的点b个度2的点
\\
考虑f(l,r)从f(l,r-1)转移,f(l,r,aa,bb)+=f(l,r-1,a,b)*val在下文将用(aa,bb,val)表示
$$

1
2
if(d[r]==2) {ad(a+1,b,1);if(a)ad(a-1,b,a);if(b)ad(a+1,b-1,b);}
else {ad(a,b+1,1);ad(a,b,a);if(b)ad(a+2,b-1,b);if(a>1)ad(a-2,b,a*(a-1)/2);if(b)ad(a,b-1,a*b);if(b>1)ad(a+2,b-2,b*(b-1)/2);}

$O(n^4)$,完整code

其实$O(n^3)$的也很无趣,感兴趣的可以看liuchengao

uoj22「UR#1」外星人

题意:给出x和n个函数$f(x)=x\%a_i$,问任意排列能达到的最大x及其方案数

请先思考后再展开

有贡献的模数递减,且在两个模数$x>y间的无用函数区间(pre,\infty),在y的下一段能使用的无用函数区间(pre \%y,\infty)$,于是对于一个确定的有贡献模数集合,考虑从左往右每次把这次新解锁的$(pre\%y,pre]$(要剔除当前选择的y)放到剩下的$n-[>y]-1$个位置中(即$P_{n-[>j]-1}^{(pre\%y,pre]-1}$,且$>x$的那些先放好),而那些有贡献的模数不需要考虑放哪里,相当于从左往右找第一个空位放进去的

1
2
3
4
fd(i,N-2,0) sum[i]=sum[i+1]+s[i];
dp[x]=P(n,sum[x+1]);fd(num,x,1) if(s[num]) fo(i,num,x) if(dp[i])
add(dp[i%num],dp[i]*s[num]%MOD*P(n-sum[i+1]-1,sum[i%num+1]-sum[i+1]-1)%MOD);
fd(i,mi-1,0) if(dp[i]) {write2(i),write(dp[i]);break;}

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