arc套刷计划

发现自己经常打比赛挂机……
正好在noip前练习一下思维题

arc101

2 E - Ribbons on Tree

9.20 难度2
题意:
给定一棵点数为偶数的树
求有多少种将点两两配对的方案使得
每一条边至少被一对匹配点之间的路径覆盖

请先思考后再展开

非常神仙的容斥:
设边集T为必定不经过的边,则答案即 $\sum (-1)^{|T|} F(T)$
显然大小为t的联通块,任意选择的方案数 $g(t)=(t-1)(t-3)(t-5)… \times 1$
具体的奇偶性等细节自行处理
如果T把树分成了多个联通块,则答案即每个块的g(t)的乘积

然而指数级枚举T显然是不现实的
利用图是一棵树的特性,考虑树形dp
设 $f(x,k)$ 表示在x的子树中,有k个是最顶上的联通块
这个联通块是可拓展的,所以不统计内部的方案数,直到被其父亲统计

dp转移时,常规地枚举两次siz,然后复杂度也同样是套路:
把siz看做子树的每个节点,则每个点对只会在lca处被遍历到,所以复杂度 $O(n^2)$

转移方程的话,因为边集大小增加,
如果不断开,相当于合并上面那个块, $f(x,sz1+sz2)+=f(x,sz1) \times f(y,sz2)$
如果断开(x,y), $f(x,sz1)+=(-1) \times f(x,sz1) \times f(y,sz2) \times g(sz2)$

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int MAX_N=5100;
typedef long long ll;
int hou[MAX_N],siz[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
const ll MOD=1e9+7;
void addup(ll &x,ll y) {x=(x+y)%MOD;}
ll g[MAX_N],f[MAX_N][MAX_N],tmp[MAX_N];
void dfs(int x,int fa)
{
siz[x]=1;f[x][1]=1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs(y,x);
for(int i=0;i<=siz[x]+siz[y];i++) tmp[i]=0;
for(int sz1=0;sz1<=siz[x];sz1++)
for(int sz2=0;sz2<=siz[y];sz2++)
{
addup(tmp[sz1+sz2],f[x][sz1]*f[y][sz2]%MOD);
if(sz2%2==0) addup(tmp[sz1],-f[x][sz1]*f[y][sz2]%MOD*g[sz2]%MOD);
}
siz[x]+=siz[y];
for(int i=0;i<=siz[x];i++) f[x][i]=tmp[i];
}
}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
g[0]=1;for(int i=2;i<=n;i+=2) g[i]=g[i-2]*(i-1)%MOD;
dfs(1,0);
ll ans=0;
for(int sz=2;sz<=n;sz+=2) addup(ans,f[1][sz]*g[sz]%MOD);
addup(ans,MOD);
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

arc100

3 E Or Plus Max

9.20 难度2
题意:
又看错题了……细思极恐
给定一个正整数 n(n≤18)
然后给定一行共 $2^n$ 个正整数 a0,a1,⋯,a2n−1
对于每一个 k( $1≤k<2^n$ ),输出满足 i OR j≤k 的最大 ai+aj 值。

请先思考后再展开

我能想到的最好的做法:
如果能得出 $i|j=k$ 的情况,那么前缀max就是答案
然而很难算出来
但如果能得出 $i|j \in k$ 的答案,那么前缀max也是可以的
而这个显然好算很多,i和j基本没关系了

枚举每个k,然后枚举其子集,维护最大和次大
时间复杂度: $O(3^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[MAX_N],mx[MAX_N];
int ans[MAX_N];
void main()
{
int n;scanf("%d",&n);
int m=1<<n;
for(int i=0;i<m;i++) scanf("%d",&a[i]);
for(int k=1;k<m;k++)
{
ans[k]=mymax(a[0],ans[k-1]);
mx[k]=a[0];
for(int u=k;u>0;u=(u-1)&k)
ans[k]=mymax(ans[k],a[u]+mx[k]),mx[k]=mymax(mx[k],a[u]);
printf("%d\n",ans[k]);
}
}

然而4亿在atcoder上面居然只需要760ms

正解:
既然我们的答案和具体子集没有关系,只关心其最大值和次大值
可以不用枚举子集,而是用子集来更新父亲
对于一个集T,不一定所有的子集都直接更新到T,也可能先经过T的子集,但这样一定不会漏
时间复杂度降低到了 $O(n2^n)$
据说这个技巧有个更深入的应用:Fast Zeta Transform

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
int a[MAX_N];
int f[MAX_N],g[MAX_N];//最大和次大值的位置
void update(int x,int pos)
{
if(pos<0 or pos==f[x] or pos==g[x]) return;
if(a[pos]>=a[f[x]]) g[x]=f[x],f[x]=pos;
else if(a[pos]>=a[g[x]]) g[x]=pos;
}
int bin[30];
void main()
{
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
for(int i=0;i<bin[n];i++) scanf("%d",&a[i]),f[i]=i,g[i]=-1;
int ans=0;
for(int k=0;k<bin[n];k++)
{
for(int i=0;i<n;i++)
{
if(k&bin[i]) continue;
update(k+bin[i],f[k]);
update(k+bin[i],g[k]);
}
ans=mymax(ans,a[f[k]]+a[g[k]]);
if(k>0) printf("%d\n",ans);
}
}
};

4 F - Colorful Sequences

9.26 难度3
题意:
定义一个长度为n,字符集大小为k的序列是好的,
当且仅当其中存在一个长度为k的子串满足1到k每个数在这里面恰好出现一次。
现在给一个长度为m的序列a,问在所有好的序列里面,a作为子串的出现次数的和。

请先思考后再展开

感觉这道题好神仙啊,还好有我p老大教我这个菜逼

先思考简化的问题
一、问题一
只考虑出现的次数,不考虑序列的好坏
因为互相之间没有影响,直接搞
枚举左边的数量,乱填, $(n-m+1) k^{n-m}$

二、问题二
考虑all-不好的
那么问题转化为染色,最近在noiac做的一道比赛题(题解自行搜索)
$f(n,ln)=f(n-1,ln-1) \times (k-(ln-1)) + \sum f(n-1,ln<t \leq k)$
此处复杂度为nk

三、问题一 + 问题二

A. 串a中包含k个不相同的
直接按照问题一计算即可

B. 串a中包含最长不相同,长度小于k,前后延伸最长不重叠
同样是计算不合法的数量,左右两边以刚才得到的延伸作为强制起点,按照问题二一样向左右分别dp
然后和问题一一样,枚举左边,只不过此时左右两边填写的数量不是乱填,而是要保证非法性

C. 串a整体都是互不重复,但长度小于k
我们既要求非法,有要统计贡献
因为串a本身是互不相同的,不能像B那样左右搞,因为互相影响

这里用到一个非常巧妙的转化
先忽略串a的具体字母,统计所有非法串中,长度为m的互不相同字符串的贡献
这样以后我们就不再关心串a的具体值了,反正互不相同且唯一就是了
最后把贡献还原回去,可以通过除以 排列数P(m,k) 实现

贡献的计算可以仿照前面的dp方式
设f表示串总数,当后缀不可延伸长度满足长度条件的时候就统计进g,然后g自己也转移

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int INF=0x3f3f3f3f;
typedef long long ll;
const ll MOD=1e9+7;
ll qpower(ll x,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
const int MAX_N=25100;
ll fac[410];//<=k
ll P(int n,int m) {return fac[n]*inv(fac[n-m])%MOD;}
int a[MAX_N];
bool b[410];
ll f[MAX_N][410],g[MAX_N][410];
void main()
{
fac[0]=1;for(int i=1;i<410;i++) fac[i]=fac[i-1]*i%MOD;
int n,k,m;scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
int mxlen=1;
for(int l=1,r=0;l<=m;b[a[l++]]=0)
{
if(l>r) b[a[++r]]=1;
while(r+1<=m and !b[a[r+1]]) b[a[++r]]=1;
mxlen=max(mxlen,r-l+1);
}
ll ans=ll(n-m+1)*qpower(k,n-m)%MOD;
if(mxlen==k) ;
else if(mxlen<m)
{
memset(b,0,sizeof b);int ls=0;while(ls+1<=m and !b[a[ls+1]]) b[a[++ls]]=1;
f[0][ls]=1;
memset(b,0,sizeof b);int rs=m+1;while(rs-1>=1 and !b[a[rs-1]]) b[a[--rs]]=1;
g[0][m-rs+1]=1;//debug 要的是长度
for(int i=1;i<=n-m;i++)
{
ll fsum=0,gsum=0;
for(int ln=k-1;ln>=1;ln--)
{
(fsum+=f[i-1][ln])%=MOD;(gsum+=g[i-1][ln])%=MOD;
f[i][ln]=(f[i-1][ln-1]*(k-(ln-1))%MOD+fsum)%MOD;
g[i][ln]=(g[i-1][ln-1]*(k-(ln-1))%MOD+gsum)%MOD;
}
}
for(int left=0;left<=n-m;left++)
{
ll fsum=0,gsum=0;
for(int ln=k-1;ln>=1;ln--)
(fsum+=f[left][ln])%=MOD,(gsum+=g[n-m-left][ln])%=MOD;
(ans-=fsum*gsum%MOD)%=MOD;
}
}
else
{
f[0][0]=1;
for(int i=1;i<=n;i++)
{
ll fsum=0,gsum=0;
for(int ln=k-1;ln>=1;ln--)
{
(fsum+=f[i-1][ln])%=MOD;(gsum+=g[i-1][ln])%=MOD;
f[i][ln]=(f[i-1][ln-1]*(k-(ln-1))%MOD+fsum)%MOD;
g[i][ln]=(g[i-1][ln-1]*(k-(ln-1))%MOD+gsum)%MOD;
if(ln>=m) (g[i][ln]+=f[i][ln])%=MOD;
}
}
ll tot=0;
for(int i=1;i<=k-1;i++) (tot+=g[n][i])%=MOD;
(ans-=tot*inv(P(k,m))%MOD)%=MOD;
}
printf("%lld",(ans+MOD)%MOD);
}
}
int main()
{
mine::main();
}

arc099

5 E - Independence

9.21 难度1
题意:
给定一个有 n 个节点, m条边的无向图,保证没有自环和重边。
请你把所有的 n 个节点分成两组,同组中的任意两个节点之间都有边直接连接。
问连接同组节点的总边数最小为多少?如果不存在合法的划分方案,则输出 −1

请先思考后再展开

我能想到的最好做法:
题目要求分成两个团,取补图后就是分成两个独立集
那么这个可以二分图染色,因为边意味着排斥关系
然后我们需要最小化 $min{ \frac{a(a-1)+b(b-1)}{2} }$
因为染色的时候我们会先入为主,那其实是可以整体取反的,也就是交换a和b
为了求最小值,我想到二维背包,但时间为 $O(n^3)$
感觉3亿在atcoder上应该是能跑过去的……有了上一道题的经验

我tm在想些什么???
a+b=n,做个屁的二维背包……
气到不想打

arc098

6 D - Xor Sum 2

9.21 难度2
题意:
给你一个长度为n的整数序列,让你求出满足以下条件的(l, r)的对数:
其异或和=其和

请先思考后再展开

能想到的最好做法:
维护一个前缀异或和a,前缀和b
$a[r]^a[l-1]=b[r]-b[l-1]$
然而异或没法和四则运算一起化柿子,复杂度只能是 $O(n^2)$

正解:
刚问出来就被秒掉了
$0 xor 0=0,0+0=0$
$0 xor 1=1,0+1=1$
$1 xor 1=0,1+1=2$
唯一的差异就是进位
而这个差异是没有办法消除的,只能避免
所以该区间一定不会在同一个位置上存在超过一个1
所以具有单调性

7 E - Range Minimum Queries

9.21 难度2
题意:
给定一个n个数的数列和两个整数数K,Q,执行Q次操作:选择一段长度为K的区间,删除其中的最小值。
问:执行Q次操作后,被删除的数的最小值和最大值之差 的最小值是多少?

请先思考后再展开

max-min的最小值显得很复杂
但因为取得都是原本就有的数,所以可以枚举min,然后找最小的max
因为min确定了,那么不能有任何区间包含小于min的数,这些数把整个区间分成很多段
对于每个长度为len的段,只能取出前面len-k小的数
把每个段能贡献的所有数排序,其中第q小的就是答案

arc097

8 D - Equals

9.21 难度2
题意:
给出可交换的两个位置,和一个排列,最大化pi=i的位置

请先思考后再展开

这都没想出来……
对于能间接互相交换的位置,假设有a要和b交换,则总是能够a到b,
此时b被挤开,跳到a,然后中间的部分不会发生改变

所以,可以用并查集维护间接到达关系,然后询问能够回到原本位置即可

9 E - Sorted and Sorted

9.21 难度1
题意:
排成一列的2N个球,有黑球和白球,黑球和白球上面都写了1-N的数字,给定一个操作:swap相邻两个球。问最少操作次数使得白球和黑球上的序号都分别递增。

请先思考后再展开

从简单问题入手,如果给出一个n的排列,要让a[i]=i,只能相邻交换
此时因为每次交换只能消除一个逆序对,所以答案是逆序对数
此时所谓逆序对即原位置p1,终位置p2, $p1[i]>p1[j]且p2[i]<p2[j]$

那么回到本题,求出一个最优秀的终止状态p2,就能得出答案了
那么,白球和黑球内部要有序,但交错的顺序不确定
即使暴力也不好枚举,但因为黑白内部的顺序已经确定,不难想到可以用类似字符串匹配的方式dp

设 $f(x \leq 2n,a,b)$ 表示填写到第x位,白色填了a个,黑色填了b个的逆序对最少个数
显然i=a+b,实现的时候需要去除一维
转移的话,关键就是要快速地计算新逆序对
设白色的id为x,则对应黑色的id为n+x
当放白色, $p1[t]>p1[a],t=1 \to a-1和n+1 \to n+b$
当放黑色, $p1[t]>p1[n+b],t=1 \to a和n+1 \to n+b-1$
这个东西可以预处理一下,然后就能达到 $O(n^2)$

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int MAX_N=2100;
const int INF=0x3f3f3f3f;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int p1[MAX_N*2];
int f[MAX_N*2][MAX_N];
int nw[MAX_N*2][MAX_N*2];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
char s[5];int id;scanf("%s%d",s,&id);
p1[id+n*(s[0]=='B')]=i;
}
for(int i=1;i<=2*n;i++)
for(int t=1;t<=2*n;t++)
nw[i][t]=nw[i][t-1]+(p1[t]>p1[i]);
memset(f,63,sizeof f);f[0][0]=0;
for(int x=1;x<=2*n;x++)
{
for(int a=0;a<=x and a<=n;a++)
{
int b=x-a;
if(a>0) f[x][a]=mymin(f[x][a],
f[x-1][a-1]+nw[a][a-1]+nw[a][n+b]-nw[a][n]
);
if(b>0) f[x][a]=mymin(f[x][a],
f[x-1][a]+nw[n+b][a]+nw[n+b][n+b-1]-nw[n+b][n]
);
}
}
printf("%d",f[2*n][n]);
}
};
int main()
{
mine::main();
}

10 F - Monochrome Cat

9.24 难度2
题意:
给定一棵有n个节点的树,每个点有黑白两个颜色。
现在有一只猫可以从任意节点开始,任意一个节点结束,要把所有节点染成黑色。
可以执行如下两种操作之一:

  1. 移动到相邻节点,并改变其颜色
  2. 改变当前节点颜色
    求:把所有节点染成黑色所需的最少操作次数
    数据范围:N<=2e5
请先思考后再展开

设白0黑1

不难想到:
如果叶子节点是黑色,可以删除,如此重复直到所有叶子节点都是白色位置

如果起点和终点一样,显然遍历所有叶子节点需要遍历每个节点和边(基于上面的操作)
如果对于一个点,其度是偶数,意味着会被抵消掉,如果此时是白色则要改变,
同理如果是奇数而且是黑色,也要改变自己一次,所以答案为 $\sum 度数+【(度数+颜色)\%2=0】$

但如果起点和终点不一样呢?
和起点终点相同的情况相比,从路径的形式上 就是少了【起点到终点的一条链】,
这个过程中,如果本来不需要操作就是黑色的节点,现在少经过一次,但需要操作,代价不变
而本来需要操作的节点,现在不经过,也不需要操作,少了2的代价

现在问题转化成,需要找出一条链,经过最多【本来需要操作的节点】,
不过每个节点最多经过一次,而且链的终点不能累加

这个终点有点烦人,但注意到终点总是能拓展的,即使是最极端的叶子节点,
因为度数=1,颜色一定是白色,所以权值为0,不是必须终点,即使终点为其父亲,形式上也可延伸到叶子节点
综上所述,只要在原答案的基础上,减去带权树的直径即可

arc096

11 E - Everything on It

9.21 难度2
题意:
拉面有 n 种配料 每种配料可以选择加入到拉面中,也可以不加入
一共 $2^n$ 种组合 有人来订购一些拉面
要求:
每种拉面配料不能相同。
每种配料在全部的面中至少出现过两次。

请先思考后再展开

这道题一眼容斥来搞【不能出现少于两次】的这个条件
$ANS=\sum_{k=0}^n (-1)^k C(n,k) f(k)$
其中f(k)表示有k个颜色只能不用或用一次,剩下n-k个颜色任意放,但不能出现两个完全相同的组合数
然后到这里我就不知道怎么处理不能完全相同这个问题了

f(k)应该分两部分去思考
① 不合法的k个颜色
那么相当于这k个元素,要么不放,要么放进一个集合中
假设有t个非空集合,那么这个是类似于第二类斯特林数的(刚学……)
递推式: $g(k,t)=g(k-1,t-1)+g(k-1,t) \times (t+1),0 \leq t \leq k$
解释:在原本第二类斯特林数的基础上,加上【可以丢掉】这个选项
可以是把第k个元素单独放进第t个位置,也可能第t个集合是混合的,再或者丢掉
②其他的n-k个颜色
这里非常巧妙,也是我一直不知道怎么解决的地方
方案数量为 $2^{n-k}$
那么对于那k个非法元素,本来觉得超级复杂,
其实因为每个最多出现一次,不同的碗一定不会重复
所以是 $2^{(n-k)t}$

而合法元素的话,不应该和碗的数量扯上关系,
而是考虑把每个方案看作一个碗,考虑这个碗是否出现
所以是 $2^{2^{n-k}}$

综上所述, $f(k)=\sum_{t=0}^k g(k,t) \times 2^{(n-k)t} \times 2^{2^{n-k}}$
套一个小费马定理即可

12 F - Sweet Alchemy

9.24 难度2
题意:
n≤50的树,每个点有权值,现要选点(可多次选一个点)使点数尽量多,如下限制:
选的总权值不超过C≤1e9;
ci表示i选的次数,pi表示i的父亲,那么cpi≤ci≤cpi+D,D≤1e9是给定常数。

请先思考后再展开

因为子节点选择的数量至少比父节点多
可以把操作看做是选择一整棵子树,那么问题转化成:

有n个物品,有体积和价值,要求在体积小于X的条件下让价值最大化,
每个物品也有选择次数的限制(根节点无限,其他节点为D)
观察值域,物品的数量很小,体积很大,单个价值很小,次数很大
直接用多重背包的模板,无法存下体积,用价值dp的话,总价值可能也会很大(因为次数大)

此时有一个很不好想到的姿势:用贪心代替大部分dp
结论:每个物品,只用前面n个去dp,其他的贪心
该贪心主要用微扰(应该是吧?)来证明:
当物品数量足够大的时候,如果不考虑小的误差,
是可以用贪心,选择性价比高的物品来得到大致结果的
为什么只能是大致呢?主要可能是部分细小的体积有优化空间

思考什么情况下,选择性价比高的物品一定是正确的
设有物品i和j, 并假设i的性价比更高即 $v_i / w_i > v_j / w_j$
选择vi个j物品,和选择vj个i物品,其价值都是 $v_i \times v_j$
但体积 $w_j \times v_i > w_i \times v_j$ 也就是说选择i的体积更小
这就是说,当达到此数量级,一定是性价比高的更优秀

那么,在这个数量级之外的次数可以用贪心计算,内部的情况因为比较复杂,不能贪心,只能dp
那么注意到w在单个的时候,和n是同阶的,也就是dp的权值是 $n^3$ 级别的,而体积依然非常大
所以应该用权值来dp,即 $f[权值]=min 体积$
考虑到用二进制拆分法处理多重dp,值域为 $n^3$ ,时间复杂度为 $O(n^4logn)$

dp完成后,剩余的空间就贪心地在剩余物品中选择即可

up:忘记了,用单调队列优化一下就到n四方了……

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int MAX_N=60;
const int INF=0x3f3f3f3f;
typedef long long ll;
struct LJB
{
int hou[MAX_N];
struct Edge{int y,g;}e[MAX_N];
int ln;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
LJB() {ln=0;memset(hou,0,sizeof hou);}
}E;
struct Nod
{
ll w,v;
ll num;
}p[MAX_N];
bool cmp(Nod a,Nod b) {return a.w*b.v>b.w*a.v;}
//规避除法,已知都是非负数
void dfs(int x,int fa)
{
p[x].w=1;
for(int k=E.hou[x];k>0;k=E.e[k].g)
{
int y=E.e[k].y;if(y==fa) continue;
dfs(y,x);
p[x].w+=p[y].w;p[x].v+=p[y].v;
}
}
ll f[MAX_N*MAX_N*MAX_N];
void main()
{
int n;ll mxV,D;scanf("%d%d%d",&n,&mxV,&D);
scanf("%lld",&p[1].v);
for(int i=2;i<=n;i++)
{
int fa;scanf("%lld%d",&p[i].v,&fa);
E.ins(fa,i);
}
dfs(1,0);
memset(f,63,sizeof f);f[0]=0;
for(int i=1;i<=n;i++)
{
ll num=mxV/p[i].v;//debug v可能退化成int再参与运算
if(i>1) num=min(num,(ll)D);
if(num>n) p[i].num=num-n,num=n;
else p[i].num=0;
ll now=1;
while(num>0)
{
ll w=now*p[i].w,v=now*p[i].v;
for(int ww=n*n*n;(ll)ww>=w;ww--) f[ww]=min(f[ww],f[ww-w]+v);
num-=now;
now=min(now<<1,num);
}
}
sort(p+1,p+n+1,cmp);
ll ans=0;
for(int ww=0;ww<=n*n*n;ww++)
{
if(f[ww]>mxV) continue;
ll ret=ww,left=mxV-f[ww];
for(int i=1;i<=n;i++)//debug 注意此时不是原编号
{
ll num=min(left/p[i].v,p[i].num);
left-=num*p[i].v;ret+=num*p[i].w;
}
ans=max(ans,ret);
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

arc103

13 E - Tr/ee

9.30 难度2
题意:
构造题
给出一个01串,位置i表示能否通过去除某条边得到大小为i的联通块

请先思考后再展开

rose秒了……
我的思路:
显然位置1一定是1,位置n一定是0
然后它还必须具有对称性

构造的话我想着可能应该从链开始考虑,然后像样例那样构造出一个大小合法的子树

但随后我就不知道如何保证一定不会出现某个大小了
正解:从大到小枚举,如果不可行就作为单个节点挂在根节点那里(反正大小为1一定会产生)
否则搞一个大小为i的子树,递归下去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char s[MAX_N];
int id=0;
void solve(int x,int siz)
{
for(int i=siz-1;i>=1;i--)
{
printf("%d %d\n",x,++id);
if(s[i]=='1')
{
solve(id,i);
break;
}
}
}
void main()
{
scanf("%s",s+1);int n=strlen(s+1);
for(int i=1;i<=n/2;i++) if(s[i]!=s[n-i]) {puts("-1");return;}
if(s[1]=='0' or s[n]=='1') {puts("-1");return;}
solve(++id,n);
}

D - Robot Arms

9.30 难度2
题意:
确定小于等于40步长,长度自己定,但要应对所有询问
满足n个询问(1000内),通过上下左右能到达不同的n个位置,并输出具体方案

请先思考后再展开

大致思路是二进制拆分,但本题的难点就在于只能上下左右,不能不走
比赛的时候想过,如果放大限制行不行?
例如把每个位置拆开成2个、3个乃至4个,但好像都不行
比赛就只打了个暴力部分分

正解看起来很暴力,晚上对着yww大爷的代码看半天全机房都不会证明……
就是从大到小,然后看x和y哪个绝对值大,然后就“gao”,最后再移动多几步
第二天早上过来,忽然就大致理解了
这道题的特殊性就在于1和-1的运用,也就是说虽然不能都不走,但是可以对二进制做差
而二进制有这许多非常奇妙的性质,比如说后面的t个二进制之和+1是等于t+1个二进制
所以如果我们直接把x搞定了,剩下的部分做和、差总是能得出y的(因为最大拼出int,而x+y小于int)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
int n,x[MAX_N],y[MAX_N];
vector<int> d;
vector<char> ans[MAX_N];
void gao(int k)
{
d.push_back(k);
for(int i=1;i<=n;i++)
if(abs(x[i])>abs(y[i]))
{
if(x[i]<0) x[i]+=k,ans[i].push_back('L');
else x[i]-=k,ans[i].push_back('R');//debug 倒着走!
}
else
{
if(y[i]<0) y[i]+=k,ans[i].push_back('D');
else y[i]-=k,ans[i].push_back('U');
}
}
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=30;i>=0;i--) gao(1<<i);
for(int i=1;i<=8;i++) gao(1);
if(x[1]!=0 or y[1]!=0) gao(1);//曼哈顿距离为奇数
for(int i=1;i<=n;i++) if(x[i]!=0 or y[i]!=0) {puts("-1");return;}
printf("%d\n",d.size());
for(int i=0;i<(int)d.size();i++) printf("%d ",d[i]);
puts("");
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)ans[i].size();j++) printf("%c",ans[i][j]);
puts("");
}
}
}
int main()
{
mine::main();
}

F - Distance Sums

9.30 难度2
题意:
构造一棵树
给出对于每个节点,其他节点到它的距离之和

请先思考后再展开

按照d排序,d最小的一定是树的重心
那么考虑d最大的节点,同理,它一定是叶子节点,否则存在比它更大的d
那么每次取出最大的d,它的子树确定,同时它的父亲也是能够确定的( $d[fa]=d[x]-n+2 \times siz[x]$ )
最后还必须要跑一次dfs验证,因为此时只能说相对大小是正确的

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int n;
const int MAX_N=110000;
struct Nod
{
ll d;int p,siz;
friend bool operator < (Nod a,Nod b) {return a.d<b.d;}
}p[MAX_N];
#define PR pair<int,int>
vector<PR> ans;
int hou[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;
void ins(int x,int y)
{
e[++ln]=(Edge){y,hou[x]};hou[x]=ln;
}
ll f[MAX_N];
void dfs(int x,int fa,int dis)
{
f[x]=dis;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs(y,x,dis+1);
}
}
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&p[i].d),p[i].p=i,p[i].siz=1;
sort(p+1,p+n+1);
for(int i=n;i>=2;i--)
{
ll want=p[i].d-n+2*p[i].siz;
int fa=lower_bound(p+1,p+n+1,(Nod){want,0,0})-p;//互不相同
if(p[fa].d!=want or fa==i) {puts("-1");return;}
ins(p[i].p,p[fa].p);ins(p[fa].p,p[i].p);
ans.push_back( make_pair(p[i].p,p[fa].p) );
p[fa].siz+=p[i].siz;
}
dfs(1,0,0);
ll rt=0,rt2=0;for(int i=1;i<=n;i++) {rt+=f[i];if(p[i].p==1) rt2=p[i].d;}
if(rt!=rt2) {puts("-1");return;}
for(int i=0;i<(int)ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second);
}
}
int main()
{
mine::main();
}

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