AtCoder杂题选做.
abc404
F
概率DP.要求以下式子:
然后使用数的分解,暴力分拆出c,保证枚举的单调性,复杂度大概是 $O(m^3)$ .
G
写法建议:1
vector<array<i64,3> >edge;
建图,u,v,val,再也不用重写结构体,cmp直接对类型另起一个比较就行.
头一次碰到 差分约束 的题.
差分约束
想办法变成图论题跑最短路(或最长路)的算法(你需要一个额外的点对所有点跑单源最长路).
考虑下式:
从 $i$ 往 $j$ 连一条边权为 $c$ 的有向边.(最长路还是这么建边,但边权是 $-c$ )
求最小解:按上述方式建图跑最短路.
转化(按照你要求的最短路还是最长路去加边)
a_i==a_j :连两条边
要求的东西,,
最短路:求最大差值.
最长路:求最小差值(反着来).
是否存在解:是否存在负环(最长路是正环).
是否无穷:最短路后答案是不是 inf ,最长路同理检查是不是 -inf .
abc415
中间翘了两场abc,rating被扣成狗了…
F
赛时因为调的时间太长了没过掉…
回顾线段树:单点修改,查询区间内有多少个段(11223是3个段:11,22和3)
这个时候要用到:1
2
3
4l,r 线段树的参数
val,len 当前区间内最大值,当前区间的长度是多少
lc,ls 左端点字符,左端点起始的长度
rc,rs 右端点长度,右端点起始的长度
传参的时候记住, 如果左右段中间匹配上且左段整段一致,那么左段左长度要拼起右段左长度 ,右段同理.
因为这个调半天红温了…
G
换可乐问题:你有n瓶可乐,商店有好多种政策:用ai换bi瓶可乐,你想最大化喝到的可乐数量.( $a_i<b_i\le 300,n\le10^{15}$ )
换可乐问题其实是一个类似背包dp的东西:1
2
3
4
5
6
7
8for(int i=1;i<=300;++i){//枚举ai
for(int j=i;j<lim;++j){//当前多少可乐最后喝到的个数
dp[j]=max(dp[j],dp[j-i+b[i]]+b[i]);
}
}//范围内dp
for(int i=1;i<lim;++i){//最后再加原先有的可乐数量
dp[i]+=i;
}
然后对于n非常大的情况显然逮住一个最划算的往死里换是最划算的.直到进了某个范围内再使用dp的值.
这个范围在本题中是 $K(K+1)$ ,其中 $K$ 是值域.取1e5也是可以的.1
2
3
4
5
6
7if(n<lim)res=dp[n];
else{
i64 cnt=(n-91000-ip)/(ip-iq)+1;//换的次数
res+=(cnt*(ip-iq))+cnt*(iq);//前面是换一个减掉的 后面是换一个得到的
n-=cnt*(ip-iq);
res+=dp[n];
}
abc416
E
最短路问题,忘了怎么写了复习一下.
floyd的枚举是对该边更新的,也就是
所以更新是n方的.
同理,机场之间的航线可以新开一个点表示,所有机场到达新点的权重是t,新点到其他所有机场的权重是0.
为什么疯狂WA???
Floyd的枚举是kij,不是ijk!!!!!!!!!
F
树形dp,有点难写.
树上链形式的dp都有一个套路:dp[i][j][k] 节点i的子树中有j条链,其中i的情况是k(0不在任何一条路径上1作为端点2在链里面)
转移时首先链的条数要倒着枚举(背包).
然后枚举在链里面的情况:i作为端点和枚举的子v点也作为端点合并,以及i本身就在链里面,这个时候枚举子树v的杂链(0,1,2).
然后枚举端点情况:也是合并与合并杂链.
最后枚举i不在链上的情况:也是合并与杂链合并.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void dfs(int num,int ko){
dp[num][1][1]=dat[num];
for(auto i:edge[num]){
if(i==ko)continue;
dfs(i,num);
for(int j=k;j>=0;--j){
for(int l=0;l<=j;++l){
if(l)
dp[num][j][2]=max(dp[num][j][2],dp[num][j-l+1][1]+dp[i][l][1]);
dp[num][j][2]=max(dp[num][j][2],dp[num][j-l][2]+max({dp[i][l][0],dp[i][l][1],dp[i][l][2]}));
if(l&&j-l){
dp[num][j][1]=max(dp[num][j][1],dp[num][j-l][0]+dat[num]+dp[i][l][1]);
dp[num][j][1]=max(dp[num][j][1],dp[num][j-l][1]+max({dp[i][l][0],dp[i][l][1],dp[i][l][2]}));
}else if(l)
dp[num][j][1]=max(dp[num][j][1],dp[num][j-l][0]+dat[num]+dp[i][l][1]);
dp[num][j][0]=max(dp[num][j][0],dp[num][j-l][0]+max({dp[i][l][0],dp[i][l][1],dp[i][l][2]}));
}
}
}
}
G
给你1e5个最长10的字符串,你可以重复使用某一个字符串,但是一共要用k个,你要拼出来一个字典序最小的字符串输出.
首先,字符串相同长度一定会取最小的那个,所以实际上你只需要对10个字符串进行k次.
考虑贪心:我们发现对于字符串 $A<B$ 有 $C+A<C+B$ ,但是 $A+C\not<B+C$ ,所以我们要倒着枚举.答案的最后根据贪心应该是所有字符串中字典序最小的那个,我们尝试倒着枚举后面的C(长度小于10或者是完整的后部分),然后对其拼凑一个最小的前面的字符串A,以此类推,最后答案倒序输出.
AT_dp_contest
atcoder的dp场,一共26题.
J Sushi
你有n碟寿司,上面只可能放1或2或3个寿司.每次你会随机一个数,然后把那个盘子上的一个寿司吃掉(没有就不吃),问你吃完所有寿司的期望随机次数是多少.
首先发现盘子的排列和答案无关,因为概率都一样,所以答案只和寿司为1,2,3的个数有关.
设 dp[i][j][k] 表示剩1个寿司剩i,2个寿司剩j,3个寿司剩k三种情况时的期望次数.有
然后化一下式子,dfs一下算出来就可以了…
W
n条线段,每个线段覆盖lr区间,如果区间内存在一个数是1,那么答案就加上wi(可能是负的),问最大答案是多少?
人们说有一个典 :每个线段在区间可以右端点计算贡献能够不重不漏,所以按照区间右端点排序.
设dp[i][j]表示当前正在看第i个点,前面最近第j个位置是1的最大值.
首先转移dp[i][i]即在第i个点放1:
然后转移dp[i][j]即在第i个点放0:
观察发现i维似乎可以省略,所以空间变成O(n).
我们需要一个区间取max,区间加和的线段树,复杂度降成nlogn.
具体地:线段树开n的空间,代表dp[j]的值,i在枚举中体现.
转移ii的时候注意可以不选,那么就是0.
转移ij是直接在原位置对所有结尾是r的线段加上val.
最后答案和0取max,应对所有线段权值均为负的情况.
Y Grid 2
给一个HxW的网格,你只能往下走或者往右走,网格上有n个点不能走,问有多少种情况.
容斥dp:设 $dp[i][op]$ 表示从初始点走到第i个点,经过op个点(偶数或者奇数个点)的情况数,最后答案就是
ans=所有情况-sum(flag*从i点走到终点的情况*从起点走到i点的经过点情况)
AT_typical90
atcoder经典90题,据说非常劲爆,全是典.
015
对于给定的 $N$ ,求对于1-n的x,数列1-n里面任意选元素满足任意两个元素差值大于等于x的情况.
对于固定的 $x$ ,里面最多有 $\lceil\frac{n}{x}\rceil$ 个元素.
枚举元素,设为 $k$ ,有 $k-1$ 个空隙,也就有 $(k-1)(x-1)$ 个元素不能选.
所以对于 $x,k$ 答案是 $\binom{n-(k-1)(x-1)}{k}$ ,拓展即可得到
由于整除数列的收敛性,复杂度是nlogn.
025
设 给了一个函数返回数字各位的乘积,求 $\sum_{i=0}^n\left[i-f(i)=m\right]$ 这个式子,n,m范围都是1e11.
发现 $f(x)$ 的取值非常少,所以从f(x)下手:
dfs所有数字排列(显而易见的剪枝是强制数列单调),枚举所有f(x),这个时候由于f(x)已经确定了,x也就可以根据上面的式子算出来.
由于枚举的数字排列是可以随意组合的,所以判断是不是解只需要把x拆开和枚举的数字比较.
时间复杂度有点玄学,1e11跑了700ms.
Flu没做出来是因为只发现解很少,尝试从解入手,思路歪了.
030
计算 $\sum_{i=1}^n[\omega(i)=k]$ ,其中 $\omega$ 表示不同质因子数.
前置知识:
所以我们枚举每个质数,对其直接乘倍数,模拟埃氏筛在区间直接计算即可,复杂度 $O(n\log\log n)$ .
听说还可以做到 $O(n)$ ,但是看起来就很麻烦…