SCOI

4/?

SCOI2018 树

题意:一棵树,修改点权,询问某点出发的最大权值简单路径,$n \le 1e5,|点权| \le 1e4$。时间3000ms空间64M

请先思考后再展开

树上距离以欧拉序表示就是在两点间任选一个点,然后$dis_x+dis_y-2dis_k$,线段树维护每个点到根距离

以向右边找为例,维护好区间内最大的$(i<j)的dis_j-2dis_i$,然后单点询问,边走边统计答案即可,$O(nlogn)$

具体实现应该类似CEOI2019 动态直径博客;忽然发现吊打三个标算了

SCOI2018 Numazu 的蜜柑

题意:一棵树上统计点对,y是x祖先,且$a_x^2+Aa_xa_y+Ba_y^2=0 \pmod{ 素数P}$,$n \le 1e5,P,a_x \le 1e16$

请先思考后再展开

特判B=0后,一元二次方程求根公式得到点x要找的ay,二次剩余+龟速乘/黑科技乘+map/unorderedmap

SCOI2018 星际迷航

题意:一切操作在$m \le 10$维向量模$素数P \le 1e8$意义下进行,初始A在原点,有n个向量,无限次取其中任意B,从而将坐标A变成2B-A,q次询问能否到达指定坐标,$n,q \le 1e5$

请先思考后再展开

对于m=1,以+和-数量相等为例(不等的话手动判),考虑每次选两个得到$a-b$,根据裴蜀定理,$gcd(各种差,P)|wt \pmod P$就是条件。根据gcd性质,只需要取出向量1与其他向量搞出来的差即可,向量个数为$O(n)$,为了判断倍数要开个1e8的bitset

然后就不太会了


赛后几个月才知道P是质数……虽然没法定义gcd,但线性空间本身就是满足上面说的,所以向量个数还是$O(n)$的

那对这个线性空间做高斯消元(类似线性代数-求矩阵行列式板子,辗转相除搞成倒三角,$O(nm^2logP)$),对于偶数步的情况就是丢上去分解(有逆元用就是爽得一匹),奇数步的情况,类似BSGS那样,先枚举每个原始向量丢进去跑,结果放set里,然后每个询问再丢进去,$O(q*(m^2+logn))$

SCOI2019 RGB

题意:$n \le 2e3$边带权树,每个点有颜色R、G、B,求点集对$(X,Y)$的数量,满足两个集合都是连通集合,且X内只有R和G,Y内只有G和B,并集中存在至少一个nb点到X和Y中任意点的距离都不超过M,模1e9+7,$边权 \le 1e6,M \le 1e7$

请先思考后再展开

并集显然都是G

如果没有距离限制,考虑并集做换根就线性了(dp出f、g分别表示这棵子树分配给X、Y的方案数,那么对于一个并集,在顶部rt统计的话,就是$(upf_{rt}+upg_{rt}+1) \prod_{rt子树孩子x} (f_x+g_x+1)$)

考虑到树的交是树,且两个nb点路径上都是nb点,所以对于一个方案而言,深度最小的nb点是唯一的,考虑从这里唯一计数。枚举这个nb点A,那么就是A子树中最深的点x要满足$d_x \in (M+d_{fa_x},M+d_{x}]$(去掉距离A超过M的,A子树里加一维01先做次dp,然后给其他人正常做dp,最后枚举是A祖先的rt作为并集的顶部),或者A是并集的根。$O(n^2)$

过了暴力的拍,然而只获得了n在15内的30pt,懵逼了,有空再调试

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
int n,M;vc<pii> to[N];char col[N];
int dis[N][N],ff[N];
void pre(int x,int fa,int rt){ ff[x]=fa;
fo(t,0,sz(to[x])-1)
if(to[x][t].FR!=fa) dis[rt][to[x][t].FR]=dis[rt][x]+to[x][t].SE,pre(to[x][t].FR,x,rt); }
int RT;ll dp[3][N][2],ans;
void solve(int x,int fa,bool sub)
{
if(dis[RT][x]>M) return;
if(x==RT) sub=1;
if(sub)
{
fo(is,dis[ff[RT]][x]>M,dis[ff[RT]][x]>M) dp[0][x][is]=(col[x]!='B'),dp[1][x][is]=(col[x]!='R'),dp[2][x][is]=(col[x]=='G');
fo(t,0,sz(to[x])-1) if(to[x][t].FR!=fa)
{
int y=to[x][t].FR;solve(y,x,sub);
fo(op,0,3)
{
int L=op,R=op;if(op==2) L=0;
ll s0=0,s1=0;
fo(op2,L,R) add(s0,dp[op2][y][0]),add(s1,dp[op2][y][1]);
dp[op][x][1]=(dp[op][x][1]*(s0+s1+1)+dp[op][x][0]*s1)%MOD,
dp[op][x][0]=dp[op][x][0]*(s0+1)%MOD;
}
}
if(x==RT) fo(op,0,1) fo(op2,0,1) dp[op][x][op2]=0;
}
else
{
fo(is,1,1) dp[0][x][is]=(col[x]!='B'),dp[1][x][is]=(col[x]!='R'),dp[2][x][is]=(col[x]=='G');
fo(t,0,sz(to[x])-1) if(to[x][t].FR!=fa)
{
int y=to[x][t].FR;solve(y,x,sub);
fo(op,0,3)
{
int L=op,R=op;if(op==2) L=0;
ll s0=0;fo(op2,L,R) add(s0,dp[op2][y][1]);
dp[op][x][1]=dp[op][x][1]*(s0+( dis[RT][y]<dis[RT][x]?0:1 ))%MOD;
}
}
}
//debug("x=%d ",x);fo(op,0,2) debug("(%lld,%lld) ",dp[op][x][0],dp[op][x][1]);debug("\n");
}
void solve2(int x,int fa,ll upf,ll upg)
{
//debug("x=%d upf=%lld upg=%lld\n",x,upf,upg);
if(x==RT)
{
add(ans, (upf+upg+1)*(dp[2][x][1]+dp[2][x][0])%MOD );
return;
}
add(ans, (upf+upg+1)*dp[2][x][1]%MOD );
//debug("after %d ans=%lld\n",x,ans);
ll uf=(col[x]!='B'),ug=(col[x]!='R');uf=uf*(upf+1)%MOD,ug=ug*(upg+1)%MOD;
fo(t,0,sz(to[x])-1) if(to[x][t].FR!=fa) if(dis[RT][to[x][t].FR]>dis[RT][x]) uf=uf*(dp[0][to[x][t].FR][1]+1)%MOD,ug=ug*(dp[1][to[x][t].FR][1]+1)%MOD;
fo(t,0,sz(to[x])-1) if(dis[RT][to[x][t].FR]<dis[RT][x]) solve2(to[x][t].FR,x,uf,ug);
}
void main()
{
n=qread(),M=qread();scanf("%s",col+1);fo(i,2,n){ int x=qread(),y=qread(),c=qread();to[x].PB({y,c}),to[y].PB({x,c}); }
fd(rt,n,1) pre(rt,0,rt);
fo(rt,1,n) if(col[rt]=='G')
{
mem(dp,0);
RT=rt;int zz=rt;while(ff[zz] and dis[RT][ff[zz]]<=M) zz=ff[zz];
solve(zz,0,0);
solve2(zz,0,0,0);
//debug("rt=%d ans=%d\n",rt,ans);
}
write(ans);
}

SCOI2018 游泳池

题意:$n \le 500$的凸多边形,标记若干顶点为特殊点,严格内部有$m \le 50$个不重叠的圆,设选择移走了z个圆,常数$t \le 1e4、K \le 1e6$给定,最大化$\frac{t}{zK+t}*$[在边界上随机一点,去往直线距离最远的顶点的直线路径上没有圆,且那个顶点是特殊点],坐标绝对值不超过1e7,精度要求为1e-4

题解

SCOI2018 ABNS

题意:一种饮料的参数有$a,b,c$,每次询问时给定A和B,可以给当前存在的每种饮料各分配浮点系数ki,满足$\sum a_ik_i \le A,\sum b_ik_i \le B时最大化\sum c_ik_i$。参数都是正整数且满足$c \le 1e3,其他参数 \le 3e7$。有$n \le 1e5$个事件,可能是新饮料品种,可能是一对AB表示询问,或者回退到以前的某个时间点

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