做题记录

感觉一直把一些做的其他题放在复健里也不太对,所以新开了一篇。

[CF1368 F]

solution

题面:这是一道交互题

Alice 和 Bob 正在玩游戏,有 $n$ 盏灯排成一圈,顺时针标号为 $1\backsim n$。起初所有的灯都处于关闭状态。

游戏由 Alice 先手,她每次可以选定任意一个正整数 $k\in [1,n]$ 并指定任意 $k$ 盏灯,并将其打开 ( 如果原来就是开着的那么仍然是开着的 ),然后 Bob 可以选定任意连续 $k$ 盏灯,并将其关闭 ( 如果原来就是关闭的那么仍然是关闭的 ),他需要保证他选择的 $k$ 值和 Alice 的相同。

每一轮 Alice 操作后 Bob 再操作,被称为一个回合。Alice 想要在若干回合后让开着的灯的数量尽可能多,而 Bob 希望这个数尽可能少。

你需要写一个程序模拟 Alice,以帮助她完成最优策略,Bob 则由交互库来模拟。

设在最优策略下,若干个回合后开着的灯的数量的最大可能值为 $R(n)$,你需要在不超过 $10^4$ 回合内将开着的灯的数量达到这个值。

做法:发现 Alice 为了尽可能多,肯定要打开一些不连续的灯。打开到一定程度,使得灯被迫有 $k$ 个相连时,接下来的操作就都是无效的了。

假设间隔是 $k$,可以算得答案最多是 $n-k-\lceil\frac{n}{k}\rceil+1$,这可以通过鸽巢原理证明。而取到这个的方法就像我前面所说的,以 $k$ 个为一组了。

对答案式子进行上取整和根号的分类讨论,可得 $k=\lfloor\sqrt{n}\rfloor$ 时取到最大值 $n-2\lceil\sqrt{n}\rceil+1$。

时间复杂度 $O(n^2)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//2021.10.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
int a[N],swt[N];
inline void MAIN(){
res n=read();
res k=int(sqrt(n));
for(res i=k;i<=n;i+=k)a[i]=1;
for(res T=1;T<=10000;T++){
res ax=0;
for(res i=1;i<=n;i++)ax+=((swt[i]==0)&&(a[i]==0));
if(ax<k){puts("0");fflush(stdout);return;}
ax=0,printf("%d ",k);
for(res i=1;i<=n&&ax<k;i++)if(!a[i]&&!swt[i])swt[i]=1,printf("%d ",i),ax++;
puts(""),fflush(stdout),ax=read();
for(res i=1;i<=k;i++)swt[ax]=0,ax=ax%n+1;
}
puts("0");fflush(stdout);
}
}

[CEOI 2016] kangaroo

solution

题面:固定第一个数和最后一个数的长度为 $n$ 的排列,满足每个数要么是波谷,要么是波峰,问排列个数。

做法:考虑从每一个合法排列往前构造。假设现在有一个合法排列了,我们删去它的最大值,发现整个排列被分成两段,且端点要么是起点或终点,要么是波谷。不断进行这个操作,发现删去的顺序一定是唯一的,同时每一段的端点要么是起点或终点,要么是波谷,要么就是自己一个数。我们拿这个做 $\mathrm{dp}$,考虑从最小的数开始塞入排列,设 $f_{i,j}$ 表示已经塞到了 $i$,同时有 $j$ 个连续段的方案数。注意到这里的连续段是类似上述删除时那样构造的,即我们不管连续段之间的空格数。转移就是考虑删除的过程中,我们将 $i+1$ 删除时怎么才会变到 $(i,j)$ 这个状态。要么 $i+1$ 是单独的一个连续段,即从 $(i+1,j+1)$ 转移而来,那么要求 $i+1$ 塞在了任意两段连续段之间,即 $f_{i+1,j+1}\leftarrow^+ f_{i,j}$。要么它是两个连续段之间夹的波谷,即 $f_{i+1,j-1}\leftarrow^+ f_{i,j}$。$i+1$ 是起点和终点特殊讨论,最终一定被塞成一段,即 $f_{n,1}$。而这个 $\mathrm{dp}$ 的正确性已经在删除的过程中被证明了。

时间复杂度 $O(n^2)$。

听说这被称作水淹笛卡尔树?不太懂。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//2021.10.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
int n,s,t;
int f[N][N];
inline void MAIN(){
f[0][0]=1,n=read(),s=read(),t=read();
for(res i=1;i<=n;i++){
for(res j=0;j<i;j++){
if(i==s||i==t)add(f[i][j],f[i-1][j]),add(f[i][j+1],f[i-1][j]);
else {
res c=(i>s)+(i>t);
add(f[i][j+1],mul(f[i-1][j],j+1-c));
if(j)add(f[i][j-1],mul(f[i-1][j],j-1));
}
}
}
printf("%d\n",f[n][1]);
}
}

[SNOI 2020] 区间和

solution

题面:有一个长度为 $n$ 的整数数列 $a_1, a_2, \dots, a_n$(可能含有负数)。现在对其进行 $q$ 次操作,每次操作是以下二者之一:

  • 0 l r x 表示对于 $i = l, l+1, \dots, r$,将 $a_i$ 赋值为 $\max(a_i, x)$;
  • 1 l r 求区间 $[l, r]$ 的最大子段和。即:$\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$。

做法:显然的 $\mathrm{segment\ beats}$,不过没那么容易直接上手。

分析一下,按照那套逻辑,我们还要维护前缀最大值中有几个最小值,后缀的,全局最大的,发现这也不够维护所有信息,于是还得维护个能改变区间结构的最小取 $\max$ 值,这样就差不多了。然后手推一下这一些信息倒还是容易的,于是就给我写麻了,好难写捏。

时间复杂度你冷静分析一下,大概是要 $O(n\log^2 n)$?

code
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
//2021.11.9 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
int n,q;
struct TR{
LL lm,rm,mx,sum;
int lc,rc,mc,c,mn,laz,tg;
inline void init(const res &x){
sum=mn=x,c=1;
if(x<=0)lm=rm=mx=lc=rc=mc=tg=0;
else lm=rm=mx=x,lc=rc=mc=1,tg=inf;
}
inline void change(res val){
laz=val,swap(mn,val),val=mn-val;
sum+=(LL)val*c,lm+=(LL)val*lc,rm+=(LL)val*rc,mx+=(LL)val*mc;
}
}tr[N<<2];
inline void pushup(const res &rt){
tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
tr[rt].mn=min(tr[rt<<1].mn,tr[rt<<1|1].mn);
res fl=(tr[rt<<1].mn==tr[rt].mn),fr=(tr[rt<<1|1].mn==tr[rt].mn);
tr[rt].c=fl*tr[rt<<1].c+fr*tr[rt<<1|1].c;
tr[rt].tg=min({tr[rt<<1].tg,tr[rt<<1|1].tg,fl?tr[rt<<1].tg:tr[rt<<1].mn-1,fr?tr[rt<<1|1].tg:tr[rt<<1|1].mn-1});
res c1=fl*tr[rt<<1].lc,c2=fl*tr[rt<<1].c+fr*tr[rt<<1|1].lc;
RG LL s1=tr[rt<<1].lm,s2=tr[rt<<1].sum+tr[rt<<1|1].lm;
if(s2>s1)tr[rt].lm=s2,tr[rt].lc=c2;
else {
tr[rt].lm=s1,tr[rt].lc=c1;
if(c2>c1)tr[rt].tg=(int)min((LL)tr[rt].tg,tr[rt].mn+(s1-s2)/(c2-c1));
}
c1=fr*tr[rt<<1|1].rc,c2=fr*tr[rt<<1|1].c+fl*tr[rt<<1].rc;
s1=tr[rt<<1|1].rm,s2=tr[rt<<1|1].sum+tr[rt<<1].rm;
if(s2>s1)tr[rt].rm=s2,tr[rt].rc=c2;
else {
tr[rt].rm=s1,tr[rt].rc=c1;
if(c2>c1)tr[rt].tg=(int)min((LL)tr[rt].tg,tr[rt].mn+(s1-s2)/(c2-c1));
}
if(tr[rt<<1].rm+tr[rt<<1|1].lm>max(tr[rt<<1].mx,tr[rt<<1|1].mx))tr[rt].mx=tr[rt<<1].rm+tr[rt<<1|1].lm,tr[rt].mc=fl*tr[rt<<1].rc+fr*tr[rt<<1|1].lc;
else if(tr[rt<<1].mx>tr[rt<<1|1].mx)tr[rt].mx=tr[rt<<1].mx,tr[rt].mc=fl*tr[rt<<1].mc;
else tr[rt].mx=tr[rt<<1|1].mx,tr[rt].mc=fr*tr[rt<<1|1].mc;
}
void build(res rt,res l,res r){
tr[rt].laz=inf;
if(l==r){tr[rt].init(read());return;}
res mid=(l+r)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
}
inline void pushdown(const res &rt){
if(tr[rt].laz!=inf){
if(tr[rt].laz>tr[rt<<1].mn)tr[rt<<1].change(tr[rt].laz);
if(tr[rt].laz>tr[rt<<1|1].mn)tr[rt<<1|1].change(tr[rt].laz);
tr[rt].laz=inf;
}
}
void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
if(val<=tr[rt].mn)return;
if(L<=l&&r<=R&&val<=tr[rt].tg){tr[rt].change(val);return;}
if(l==r){tr[rt].init(val);return;}
res mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)modify(rt<<1,l,mid,L,R,val);
if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
pushup(rt);
}
LL qmx,qrm;
void query(res rt,res l,res r,const res &L,const res &R){
if(L<=l&&r<=R){
qmx=max({qmx,tr[rt].mx,qrm+tr[rt].lm}),qrm=max(qrm+tr[rt].sum,tr[rt].rm);
return;
}
res mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)query(rt<<1,l,mid,L,R);
if(R>mid)query(rt<<1|1,mid+1,r,L,R);
}
inline void MAIN(){
n=read(),q=read(),build(1,1,n);
while(q--){
res opt=read(),l=read(),r=read();
if(opt==0)modify(1,1,n,l,r,read());
else qmx=qrm=0,query(1,1,n,l,r),printf("%lld\n",qmx);
}
}
}

[JOI Open 2016] 摩天大楼

solution

题面:将互不相同的 $N$ 个整数 $A_1, A_2, \dots, A_N$ 按照一定顺序排列。 假设排列为 $f_1, f_2, \dots, f_N$,要求:$ | f_1 − f_2| + | f_2 − f_3| + \dots + | f_{N−1} − f_N| ≤ L$。 求满足题意的排列的方案数 $\bmod (10^9+7)$。

做法:直接考虑从小到大插入似乎不太行,因为和不是单调的,所以 $L$ 这一维那开到 $nA$ ,过不了。

但如果考虑将 $|f_{i}-f_{i-1}|$ 看成 $\sum A_i-A_{i-1}$ ,那考虑算 $A_i-A_{i-1}$ 的贡献就有搞头了。这个东西的系数显然是满足一个大于等于 $A_i$,一个小于等于 $A_{i-1}$ 的相邻数对个数。那仍旧考虑从小到大插入,$f_{i,j,k,p}$ 分别表示当前插到了第 $i$ 个数,形成了 $j$ 个连续段,贡献和为 $k$,头尾用了 $p$ 个的方案数。这里的贡献和我们考虑上面那个贡献,意思就是考虑 $A_i-A_{i-1}$ 的贡献。这个利用连续段是可以直接算的,因为接下来插入的都会比 $A_i$ 大,而之前的都小于等于 $A_{i-1}$,于是只要插在一个段的两边就可以了。转移都是类似的,时间复杂度 $O(n^2l)$。

坑:$n=1$ 时头就是尾,需要特判。

code
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
//2021.11.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
int n,l;
int a[N];
int f[N][N][1000+1][3];
inline void MAIN(){
n=read(),l=read();
if(n==1){puts("1");return;}
for(res i=1;i<=n;i++)a[i]=read();
sort(a+1,a+n+1),f[0][0][0][0]=1;
for(res i=0;i<n;i++){
for(res j=0;j<=i;j++)
for(res k=0;k<=l;k++)
for(res p=0;p<=2;p++){
if(!f[i][j][k][p])continue;
res val=k+(2*j-p)*(a[i+1]-a[i]);
if(val>l)continue;
add(f[i+1][j+1][val][p],mul(j+1-p,f[i][j][k][p]));
add(f[i+1][j][val][p],mul(2*j-p,f[i][j][k][p]));
if(p<2)add(f[i+1][j+1][val][p+1],mul(2-p,f[i][j][k][p]));
if(j)add(f[i+1][j-1][val][p],mul(j-1,f[i][j][k][p]));
if(p<2&&j)add(f[i+1][j][val][p+1],mul(2-p,f[i][j][k][p]));
}
}
res ans=0;
for(res i=0;i<=l;i++)add(ans,f[n][1][i][2]);
printf("%d\n",ans);
}
}

[TC12336]

solution

题面:给你一张图,要求删去若干条边,让残余图无论以什么形态都不能有边相交。求可以得到的残余图数量。

做法:观察一下就只有三角形或者菊花是可以的。于是枚举哪个点作为菊花的中心点以及有几个三角线即可。注意只剩一条边的情况会被端点算重,减掉即可。时间复杂度 $O(m\sqrt{m})$ 或者暴力点来个 $O(n^3)$ 之类的。

[CF674 F]

solution

题面:酒店中有 $n$ 只熊和 $p$ 张床,这些熊正在开晚会。

熊喜欢喝果汁,它们不喜欢喝葡萄酒。但是它们无法仅通过颜色和气味辨别果汁和葡萄酒。

一只熊可以一直在晚会上活动而不睡觉,除非它喝了葡萄酒。当一只熊喝完葡萄酒后,它立即会去睡觉,且在晚会期间不再醒来。

现在有若干个酒桶,每个酒桶中装填了果汁或葡萄酒,其中恰有一个桶中装了葡萄酒。酒桶的主人为了测试熊的智力,给它们一个如下挑战:

晚会会进行许多天。每天,会依次发生如下三件事情:

  1. 每只熊需要选择一个桶的子集 (可以为空集),多个熊可以同时选择一个桶。

  2. 每只熊需要把它选择的桶中的所有饮料都喝一小杯 (假设桶足够大,够所有的熊喝)。

  3. 对于所有喝到过酒的熊 (喝完饮料后它们自己能发现是否喝到过酒),马上会上床睡觉,并在整个晚会期间不再醒来 (i.e. 即它们不能参与剩下几天的活动了)。

    每张床恰能容纳一只熊,如果有熊无床睡觉,则挑战失败。

如果晚会结束后,这些熊中至少有一只没睡觉,且没有无床睡觉,并且它们能推理出哪个桶中装了葡萄酒 (假设熊足够聪明),则挑战成功。

容易证明,对于一个确定的 $i$,如果晚会开了 $i$ 天,则存在非负整数 $R_i$,满足:这些熊可以在 $R_i$ 个酒桶中确保挑战成功,但在 $R_i+1$ 个酒桶中无法保证挑战成功

给定正整数 $n,p,q$,你需要求出 $\displaystyle \bigoplus_{i=1}^q \left( \left( i \cdot R_i \right) \bmod 2^{32} \right)$,其中 $\bigoplus$ 表示按位异或运算。

做法:通过手玩样例 $3$,容易意识到我们总想每一桶饮料喝的熊的集合不相同。

于是枚举每一桶饮料喝的熊的数量 $i$,那么共有 $\binom{n}{i} q^i$ 种熊去喝的情况。同时一桶饮料若没有熊去喝,那么也可以判断。

再加上熊不能全喝醉,所以答案就是

注意到 $p$ 很小,所以暴力预处理组合数即可。组合数考虑将分子分母的 $2$ 都先拿出来,最后再放回去。那分母就是奇数,利用欧拉定理就可以直接求逆元了。时间复杂度 $O(pq)$。

code
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
//2021.11.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
uint inv[140];
inline uint Qpow(uint x,uint y){
uint ret=1;
while(y){
if(y&1)ret*=x;
x*=x,y>>=1;
}
return ret;
}
uint C[140];
int even[140];
inline void MAIN(){
for(res i=1;i<=130;i++)inv[i]=Qpow(i,(((uint)1)<<31)-1);
res n=read(),p=read(),q=read();
C[0]=1;
for(res i=1;i<=min(p,n-1);i++){
uint x=i,z=n-i+1;
even[i]=even[i-1]+ctz(n-i+1)-ctz(i);
x>>=ctz(i),z>>=ctz(n-i+1);
C[i]=C[i-1]*z*inv[x];
}
for(res i=1;i<=min(p,n-1);i++)C[i]<<=even[i];
uint ans=0;
for(res i=1;i<=q;i++){
uint X=0,r=1;
for(res j=0;j<=min(p,n-1);j++)X+=C[j]*r,r*=i;
ans^=X*i;
}
printf("%u\n",ans);
}
}

[CF674 G]

solution

题面:给定一个长度为 $n$ 的序列和一个整数 $p$。有 $m$ 个操作,操作要么是区间赋值,要么是询问区间内出现次数至少占 $p\%$ 的数。输出询问的答案时,可以包含错的数,也可以重复输出,但对的数一定要在答案中,且输出的数的个数不超过 $\lfloor\frac{100}{p}\rfloor$。

做法:考虑摩根( 忘记名字了 )投票法,就那个加一个就删一个的。注意到 $p\geq 20$,所以最多维护五个数。所以线段树每个节点维护个五元组就好了,时间复杂度 $O(5^2n\log n)$。

code
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
//2021.11.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=150000+10;
namespace MAIN{
int n,m,p;
struct P{
int num,tag,a[5],b[5];
}tr[N<<2];
int len[N<<2];
inline P merge(const RG P &A,const RG P &B){
RG P ret=A;
ret.tag=0;
for(res i=0;i<B.num;i++){
RG bool fl=0;
for(res j=0;j<ret.num&&!fl;j++)if(B.a[i]==ret.a[j])ret.b[j]+=B.b[i],fl=1;
if(fl)continue;
if(ret.num<p){ret.a[ret.num]=B.a[i],ret.b[ret.num]=B.b[i],ret.num++;continue;}
res mnid=0;
for(res j=1;j<ret.num;j++)if(ret.b[j]<ret.b[mnid])mnid=j;
if(B.b[i]<ret.b[mnid]){
for(res j=0;j<ret.num;j++)ret.b[j]-=B.b[i];
}
else {
res tmp=ret.b[mnid];
ret.a[mnid]=B.a[i],ret.b[mnid]=B.b[i];
for(res j=0;j<ret.num;j++)ret.b[j]-=tmp;
}
}
return ret;
}
void build(res rt,res l,res r){
len[rt]=r-l+1;
if(l==r){
res x=read();
tr[rt].num=tr[rt].b[0]=1,tr[rt].a[0]=x;
return;
}
res mid=(l+r)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
inline void change(const res &rt,const res &val){
tr[rt].num=1,tr[rt].b[0]=len[rt],tr[rt].a[0]=val,tr[rt].tag=val;
}
inline void pushdown(const res &rt){
if(!tr[rt].tag)return;
change(rt<<1,tr[rt].tag),change(rt<<1|1,tr[rt].tag),tr[rt].tag=0;
}
void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
if(L<=l&&r<=R){change(rt,val);return;}
pushdown(rt);
res mid=(l+r)>>1;
if(L<=mid)modify(rt<<1,l,mid,L,R,val);
if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
P query(res rt,res l,res r,const res &L,const res &R){
if(L<=l&&r<=R)return tr[rt];
pushdown(rt);
res mid=(l+r)>>1;
if(L<=mid&&R>mid)return merge(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
if(L<=mid)return query(rt<<1,l,mid,L,R);
return query(rt<<1|1,mid+1,r,L,R);
}
inline void MAIN(){
n=read(),m=read(),p=100/read(),build(1,1,n);
while(m--){
res opt=read(),l=read(),r=read();
if(opt==1)modify(1,1,n,l,r,read());
else {
RG P ret=query(1,1,n,l,r);
printf("%d ",ret.num);
for(res i=0;i<ret.num;i++)printf("%d ",ret.a[i]);
puts("");
}
}
}
}

[Code Festival Final 17 C]

solution

题面:来自世界各地的 $n+1$ 名选手参加了比赛,A 调查并计算出第 $i$ 名选手所在城市与他自己所在城市的时差 $D_i$。时差如下定义:对于城市 A 和城市 B,当 A 为 $0$ 点时,B 为 $b$ 点,此时时差为 $\min(b,24-b)$(24小时制)。例如,当 A 所在城市为 $0$ 点时,第 $i$ 名选手所在城市的时间要么是 $D_i$,要么是 $24-D_i$。
记 $S$ 为 A 所在城市为 $0$ 点时,每两个城市间的时差的最小值。求出尽可能大的 $S$。

做法:首先注意到鸽巢原理,$n\geq 24$ 直接就是 $0$,因为必有两个城市重复了。剩下来的直接暴搜。时间复杂度 $O(2^{24})$。

code
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
//2021.11.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
int n;
int h[30];
int ans;
int fl[30];
void dfs(res dep){
if(dep==n+1){
res mn=30,las=0;
for(res i=1;i<24;i++)if(fl[i])mn=min(mn,i-las),las=i;
mn=min(mn,24-las),ans=max(ans,mn);
return;
}
if(!fl[h[dep]])fl[h[dep]]=1,dfs(dep+1),fl[h[dep]]=0;
if(!fl[(24-h[dep])%24])fl[(24-h[dep])%24]=1,dfs(dep+1),fl[(24-h[dep])%24]=0;
}
inline void MAIN(){
n=read()+1;
if(n>24){puts("0");return;}
for(res i=1;i<n;i++)h[i]=read();
dfs(1),printf("%d\n",ans);
}
}

[TC12118]

solution

题面:有两个由 $a,b,c$ 构成的字符串,将某个位置的 $a$ 变成 $b$ 的代价为 $c_0$,$b$ 变成 $c$ 为 $c_1$,$c$ 变成 $a$ 为 $c_2$,最大代价为 $mc$,问将第一个串变成第二个的方案数。

做法:注意到记录代价无意义,因为一个合法方案一定是有将第一个串变成第二个串,然后在每个位置循环变化,所以实际上记录代价可以被记录变化次数所代替。

令 $f_{i,j,k}$ 表示当前已经动了 $i$ 步,还有 $j$ 个位置差一步,$k$ 个位置差两步的方案数。转移就是 $f_{i,j,k}=(j+1)f_{i-1,j+1,k}+(k+1)f_{i-1,j-1,k+1}+(n-j-k+1)f_{i-1,j,k-1}$。观察一下就知道这个可以矩乘优化了,时间复杂度 $O(n^6\log m)$,其中 $n$ 为字符串长,$m$ 为步数。

[Code Festival Final 17 F]

solution

题面:有 $n$ 张纸,每张纸上要写 $k$ 个数,要求这 $k\cdot n$ 个数都在 $[1,n]$ 内,且 $[1,n]$ 中的每个数恰好出现 $k$ 次。还要求每张纸不能写相同的数,且任意两张纸的数字交集大小为 $1$,让你构造 $1000\leq n\leq 2000$ 和 $k$ 以及染色方案。

做法:首先根据每两个相同数字都要在不同的纸张,以及不同纸张之间都要有相同的数字,可以得到 $\frac{n(n-1)}{2}=\frac{nk(k-1)}{2}$,即 $n=k^2-k+1$。

然后接下来的我暂时还没想到。

code
1
2


[TC12161]

solution

题面:有 $n$ 个数 $a_i$,一个排列的价值为 $\sum_{i=1}^{n-1} \max(a_{p_i},a_{p_{i+1}})$,求价值最小且字典序最小的排列。

做法:肯定想要越大的越少出现,那么除了最小的,其他都是出现一次,即一个 V 字形。剩下来的直接贪心就可以了。时间复杂度 $O(n\log)$。

[LG6327]

solution

题面:中文不会自己看?

做法:考虑那个啥公式,就 $\sin(x+y)=\sin x\cos y+\sin y\cos x$,那么线段树上每个结点只用维护 $\sum \sin $ 和 $\sum \cos$ 了。时间复杂度 $O(n\log)$。

code
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
//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
#define ld long db
const int N=2e5+10;
namespace MAIN{
int n;
ld si[N<<2],cs[N<<2];
LL tag[N<<2];
void build(res rt,res l,res r){
if(l==r){
res x=read();
si[rt]=sin(x),cs[rt]=cos(x);
return;
}
res mid=(l+r)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
si[rt]=si[rt<<1]+si[rt<<1|1];
cs[rt]=cs[rt<<1]+cs[rt<<1|1];
}
inline void change(const res &rt,const RG LL &val){
RG ld vs=si[rt],vc=cs[rt];
si[rt]=vs*cos(val)+vc*sin(val);
cs[rt]=vc*cos(val)-vs*sin(val);
tag[rt]+=val;
}
inline void pushdown(const res &rt){
if(!tag[rt])return;
change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=0;
}
void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
if(L<=l&&r<=R){
change(rt,val);
return;
}
pushdown(rt);
res mid=(l+r)>>1;
if(L<=mid)modify(rt<<1,l,mid,L,R,val);
if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
si[rt=si[rt<<1]+si[rt<<1|1];
cs[rt]=cs[rt<<1]+cs[rt<<1|1];
}
ld query(res rt,res l,res r,const res &L,const res &R){
if(L<=l&&r<=R)return si[rt];
pushdown(rt);
res mid=(l+r)>>1;
RG ld ret=0;
if(L<=mid)ret=query(rt<<1,l,mid,L,R);
if(R>mid)ret+=query(rt<<1|1,mid+1,r,L,R);
return ret;
}
inline void MAIN(){
n=read(),build(1,1,n);
res q=read();
while(q--){
res opt=read(),l=read(),r=read();
if(opt==1){
res v=read();
modify(1,1,n,l,r,v);
}
else printf("%.1Lf\n",query(1,1,n,l,r));
}
}
}

[CSP-S 2021] 交通规划

solution

题面:中文不会自己看?

做法:$k=2$ 时,将异色的端点所处区域染色,同时将平面图转成其对偶图( 即一个区域看成一个点,相邻区域连边 ),那么题意从最小割就转化成了两个空阔区域间的最短路( 因为最优染色一定是两个区域,分别是黑白 )。

$k$ 更大时,考虑顺时针将每两个相邻且异色的射线间的空阔区域染与之前不同的颜色,把这些区域看成一个点,发现一个合法的割方案就等价于选择两个异色点连边,边权为这两个区域间的最小割,且要保证这里的边不交。于是做 $k$ 次 $\mathrm{Dijkstra}$,将每个区域到其他区域的最小割都算出来,剩下的就是个区间 $\mathrm{dp}$。时间复杂度 $O(knm\log nm+k^3)$。

code
1
2


[CF453 E]

solution

题面:你有 $n$ 只小马( 编号从 $1$ 到 $n$ )。每只小马有三种属性。

$s_i$:时间为 $0$ 时这只小马拥有的法力值。

$m_i$:这只小马可以拥有的最大法力值。

$r_i$:这只小马单位时间内回复的法力值。

提雷克会给出 $m$ 条指令,每一条都可以被描述为 $3$ 个整数:$t_i, l_i, r_i$。表示在时间为 $t_i$ 时,提雷克会从区间 $[l_i,r_i]$ 的小马中吸取魔力,指令保证 $t$ 升序,计算每一条指令之后提雷克可以吸取多少点魔力。

做法:考虑 $\mathrm{ODT}$ 那一套逻辑,把上次修改时间一致的连续点连成一个区间,发现这样的区间个数是 $O(n+m)$ 的。于是可以暴力处理这些区间,注意到一共就两类情况,即 $T-t\leq \frac{m}{r}$ 与否,可以容易注意到这东西是二维数点,离线下来可以一维数点,不过直接可持久化线段树挺好写的捏。时间复杂度 $O(n\log n)$。当然可以注意到这是分段函数,所以可以上闵科夫斯基凸包和

坑:这题实现上一车细节。比如就 $r=0$ 的这些点你要怎么安排的小细节,因为此时直接用乘法会遇到 $r=m=0$ 的情况导致无序而 RE。( 我不会说我写了一个半小时的 )

code
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
//2021.11.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
int n;
#define tup tuple<int,int,int>
set<tup> S;
int s[N],m[N],u[N];
set<int> T;
int ls[N*30],rs[N*30],tot;
pair<LL,LL> su[N*30];
inline pair<LL,LL> operator + (pair<LL,LL> a,pair<LL,LL> b){
return mp(a.fi+b.fi,a.se+b.se);
}
void build(res &rt,res l,res r){
rt=++tot;
if(l==r){su[rt]=mp(u[l],0ll);return;}
res mid=(l+r)>>1;
build(ls[rt],l,mid),build(rs[rt],mid+1,r),su[rt]=su[ls[rt]]+su[rs[rt]];
}
void insert(res &rt,res RT,res l,res r,const res &p){
rt=++tot;
ls[rt]=ls[RT],rs[rt]=rs[RT],su[rt]=su[RT];
if(l==r){if(u[l])su[rt]=mp(0ll,m[l]);return;}
res mid=(l+r)>>1;
if(p<=mid)insert(ls[rt],ls[RT],l,mid,p);
else insert(rs[rt],rs[RT],mid+1,r,p);
su[rt]=su[ls[rt]]+su[rs[rt]];
}
pair<LL,LL> query(res rt,res l,res r,const res &L,const res &R){
if(!rt)return su[rt];
if(L<=l&&r<=R)return su[rt];
res mid=(l+r)>>1;
RG pair<LL,LL> ret=mp(0ll,0ll);
if(L<=mid)ret=query(ls[rt],l,mid,L,R);
if(R>mid)ret=ret+query(rs[rt],mid+1,r,L,R);
return ret;
}
int rt[N];
int id[N];
inline bool cmp(const res &A,const res &B){
if(!u[A])return 0;
if(!u[B])return 1;
return (LL)m[A]*u[B]-(LL)m[B]*u[A]<0;
}
inline pair<LL,LL> calc(const res &L,const res &R,const res &t){
res l=0,r=n,ret=0;
while(l<=r){
res mid=(l+r)>>1;
if(m[id[mid]]<=(LL)t*u[id[mid]])l=mid+1,ret=mid;
else r=mid-1;
}
return query(rt[ret],1,n,L,R);
}
set<tup>::iterator L,R;
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)s[i]=read(),m[i]=read(),u[i]=read(),T.insert(i),id[i]=i;
S.insert(tup(0,0,0));
build(rt[0],1,n),sort(id+1,id+n+1,cmp);
for(res i=1;i<=n;i++)insert(rt[i],rt[i-1],1,n,id[i]);
res q=read();
while(q--){
res t=read(),l=read(),r=read();
LL ans=0;
auto IT=T.lower_bound(l);
while(IT!=T.end()&&(*IT)<=r){
res i=(*IT);
ans+=min((LL)m[i],(LL)u[i]*t+s[i]),T.erase(IT),IT=T.lower_bound(l);
}
if(S.empty())L=R=S.end();
else {
if(r==n)R=S.end();
else {
auto it=(--S.upper_bound(tup(r+1,0,0)));
tup tmp=(*it);
if(r>=get<1>(tmp))R=(++it);
else S.erase(it),S.insert(tup(get<0>(tmp),r,get<2>(tmp))),R=S.insert(tup(r+1,get<1>(tmp),get<2>(tmp))).fi;
}
auto it=(--S.upper_bound(tup(l+1,0,0)));
tup tmp=(*it);
if(l>get<1>(tmp))L=(++it);
else if(l>get<0>(tmp))S.erase(it),S.insert(tup(get<0>(tmp),l-1,get<2>(tmp))),L=S.insert(tup(l,get<1>(tmp),get<2>(tmp))).fi;
else {
if(l==get<0>(tmp))L=it;
}
}
auto nL=L;
for(;L!=R;L++){
pair<LL,LL> ret=calc(get<0>(*L),get<1>(*L),t-get<2>(*L));
ans+=ret.fi*(t-get<2>(*L))+ret.se;
}
S.erase(nL,R),S.insert(tup(l,r,t)),printf("%lld\n",ans);
}
}
}

[Wannafly 6 E]

solution

题面:中文题面不会自己看?

做法:所以说构造题千万不能看样例和数据范围啊。

$n\leq 3$ 时,显然不能找到两组使得右边的数大于左边,所以都无解。而其它的 $n$,$n=4$ 可以找到 $1144$,$n=5$ 可以找到 $16400$,然后你发现这样往后每次添加两个 $0$,只要第二位和第三位处划分就可以了。时间复杂度 $O(n)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//2021.12.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
inline void MAIN(){
res n=read();
if(n<=3)puts("-1");
else {
if(n&1){
printf("16400");
for(res i=n-5;i;i--)printf("0");
puts("");
}
else {
printf("1144");
for(res i=n-4;i;i--)printf("0");
puts("");
}
}
}
}

[Ynoi2007] rgxsxrs

solution

题面:中文题面不会自己看?

做法:整体或树上操作都类同于 $21$ 年暑假 $\mathrm{hdu}$ 多校第三场的那道 $C$,即考虑到以 $[0,x-1],[x,2x],[2x+1,\infty)$ 分段考虑,中间那一段暴力,后面那一段直接打标记。然后分块,之后再写好了。

code
1
2


[CF739 A]

solution

题面:长度为 $n$ 的序列,有 $m$ 个区间限制,要求构造这个序列,使得这 $m$ 个区间的最小 $\mathrm{mex}$ 最大。

做法:注意到最大值不能超过最短区间的长度,考虑构造这个下界。发现循环 $0,1,…,l$ 构造就行了,其中 $l$ 为最短区间长度。时间复杂度 $O(n)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//2021.12.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
inline void MAIN(){
res n=read(),m=read(),L=n;
for(res i=1;i<=m;i++){
res l=read(),r=read();
L=min(L,r-l+1);
}
res now=0;
printf("%d\n",L);
for(res i=1;i<=n;i++)printf("%d ",now),now=(now==L-1?0:now+1);
}
}

[CF733 C]

solution

题面:有 $n$ 个怪兽,第 $i$ 个的重量是 $a_i$。

一秒钟内,能让恰好一个怪兽吃掉相邻的比它重量小的怪兽。重量大的重量加上重量小的的重量;重量小的怪兽死掉。死后重新靠拢。

求一种顺序,变成:共 $k$ 个怪兽,第 $j$ 个的重量是 $b_j$。

做法:注意每次合并的一定是一个区间,那么就可以逐个确定是否能构造出 $b$。另一方面一个区间能能否构造,当且仅当和等于 $b$ 且不全部相等。因为如果全部相等则没得吃,若有一个不等,那么一定存在一个最大的数能吃相邻的一个。于是只要每次拿最大的那个来吃就好了。时间复杂度 $O(n)$。

code
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
//2021.12.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=500+10;
namespace MAIN{
int n;
int a[N];
int k,b[N];
vector<pair<int,char> > ans;
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i]=read();
k=read();
for(res i=1;i<=k;i++)b[i]=read();
res now=1,cur=1,ret=0,st=0,sum=0;
while(now<=n+1){
if(now>n&&ret!=b[cur]){puts("NO");return;}
if(!ret){st=now,ret=a[now++];continue;}
if(ret<b[cur]){ret+=a[now++];continue;}
if(ret>b[cur]){puts("NO");return;}
res fl=0,mx=0;
if(st+1==now){ret=0,cur++;continue;}
for(res i=st+1;i<now;i++)if(a[i]!=a[st]){fl=1;break;}
if(!fl){puts("NO");return;}
for(res i=st;i<now;i++)if(a[mx]<a[i])mx=i;
if(mx==st&&a[mx]==a[mx+1]){
for(res i=st;i<now-1;i++)if(a[mx]==a[i]&&a[i]>a[i+1]){mx=i;break;}
for(res i=mx+1;i<now;i++)ans.pb(mp(mx-sum,'R'));
for(res i=st;i<mx;i++)ans.pb(mp(mx-sum-(i-st),'L'));
sum+=now-st-1;
}
else {
for(res i=st;i<mx;i++)ans.pb(mp(mx-sum-(i-st),'L'));
sum+=mx-st;
for(res i=mx+1;i<now;i++)ans.pb(mp(mx-sum,'R'));
sum+=now-1-mx;
}
ret=0,cur++;
if(now>n&&cur<=k){puts("NO");return;}
if(now>n&&cur>k)break;
}
puts("YES");
for(auto x:ans)printf("%d %c\n",x.fi,x.se);
}
}

[CF429 E]

solution

题面:给定 $n$ 条线段 $[l_i,r_i]$,然后给这些线段红蓝染色,要求最后直线上任意一个点被蓝色及红色线段覆盖次数之差的绝对值之差小于等于 $1$。

做法:绝对值之差小于等于 $1$ 实际都是可以用欧拉回路解决的。差分后考虑区间端点处连边,然后把相邻的点度为奇数的点连边,这样保证了每个点的度数为偶数。接下来跑个欧拉回路,给无向图边定向,这样顺时针为红,逆时针为蓝,即可保证每个点的红蓝染色次数相等。时间复杂度 $O(n)$。

坑:因为相邻点连边了,所以空间要乘 $2$。

code
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
//2021.12.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
int n,m;
#define tup tuple<int,int,int>
tup a[N];
struct E{
int next,to;
E() {}
E(res next,res to):next(next),to(to) {}
}edge[N];
int head[N],cnt=-1;
inline void addedge(const res &u,const res &v){
edge[++cnt]=E(head[u],v),head[u]=cnt;
edge[++cnt]=E(head[v],u),head[v]=cnt;
}
int pos[N];
int vis[N],ans[N];
void dfs(res x){
vis[x]=1;
for(res &i=head[x];~i;i=edge[i].next)if(!ans[i])ans[i]=1,ans[i^1]=2,dfs(edge[i].to);
}
inline void MAIN(){
n=read(),memset(head,-1,sizeof(head));
for(res i=1;i<=n;i++){
res l=read(),r=read();
a[i]=tup(l,1,i),a[i+n]=tup(r+1,-1,i);
}
sort(a+1,a+2*n+1);
for(res i=1;i<=2*n;i++){
if(get<0>(a[i])>get<0>(a[i-1])){
m++;
if(!(i&1))addedge(m-1,m);
}
if(get<1>(a[i])==1)pos[get<2>(a[i])]=m;
else addedge(pos[get<2>(a[i])],m),pos[get<2>(a[i])]=cnt;
}
for(res i=1;i<=m;i++)if(!vis[i])dfs(i);
for(res i=1;i<=n;i++)printf("%d ",ans[pos[i]]&1);
}
}

[CF725 C]

solution

题面:给一个长度为 $27$ 的大写字母串,其中除了一个字符出现两次,其他都出现一次。要求构造出 $2\times 13$ 的字符网格,使得每个字符都出现一次,且原字符串中相邻的字母在网格中八连通。

做法:注意到若我们按原字符串直接塞入网格中( 即第二行处的末尾和第一行的末尾相连 ),我们不断向前旋转这个网格,相邻的字符仍然是相邻的。那么只用考虑那个出现两次的字符。出现两次的字符我们保留一个即可,设另一个相邻的字符是 $a,b$,那么不断旋转,这个字符一定会和 $a,b$ 相遇。这是小学二年级的相遇问题,而且因为删去这个字符后 $a,b$ 就在网格中相邻了,所以是对的。除非当这个出现两次的字符相邻了,那么显然无解。

时间复杂度 $O(26\ast 26)$,当然可以更优。

code
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
//2021.12.8 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
char str[30];
int vis[26];
int id1,id2;
char p[4],q[8],a[5][15],b[5][15];
int fl[4];
inline void MAIN(){
str[0]='!',str[28]='!';
scanf("%s",str+1);
res n=int(strlen(str+1));
for(res i=1;i<=n;i++){
if(!vis[str[i]-'A'])vis[str[i]-'A']=i;
else {
id1=i,id2=vis[str[i]-'A'];break;
}
}
for(res i=1;i<=n;i++){
if(i==id1)p[0]=str[i-1],p[1]=str[i+1];
if(i==id2)p[2]=str[i-1],p[3]=str[i+1];
}
if(abs(id1-id2)==1){puts("Impossible");return;}
res now=1,ni,nj;
for(res j=1;j<=13;j++){
if(now==id2)now++;
if(now==id1)ni=1,nj=j;
a[1][j]=str[now],now++;
}
for(res j=13;j;j--){
if(now==id2)now++;
if(now==id1)ni=2,nj=j;
a[2][j]=str[now],now++;
}
for(res T=1;T<=26;T++){
q[0]=a[ni][nj-1],q[1]=a[ni][nj+1],q[2]=a[ni-1][nj],q[3]=a[ni+1][nj];
q[4]=a[ni-1][nj-1],q[5]=a[ni-1][nj+1],q[6]=a[ni+1][nj-1],q[7]=a[ni+1][nj+1];
fl[0]=fl[1]=fl[2]=fl[3]=0;
for(res k=0;k<4;k++){
for(res i=0;i<8;i++){
if(q[i]==p[k]||p[k]=='!')fl[k]=1;
}
}
if(fl[0]==1&&fl[1]==1&&fl[2]==1&&fl[3]==1){
for(res i=1;i<=2;i++){
for(res j=1;j<=13;j++)putchar(a[i][j]);
puts("");
}
return;
}
if(nj<13&&ni==1)nj++;
else if(ni==1&&nj==13)ni=2;
else if(ni==2&&nj==1)ni=1;
else nj--;
for(res j=1;j<13;j++)b[1][j+1]=a[1][j];
b[2][13]=a[1][13];
for(res j=2;j<=13;j++)b[2][j-1]=a[2][j];
b[1][1]=a[2][1];
for(res i=1;i<=2;i++)for(res j=1;j<=13;j++)a[i][j]=b[i][j];
}
now=1;
for(res j=1;j<=13;j++){
if(now==id1)now++;
if(now==id2)ni=1,nj=j;
a[1][j]=str[now],now++;
}
for(res j=13;j;j--){
if(now==id1)now++;
if(now==id2)ni=2,nj=j;
a[2][j]=str[now],now++;
}
for(res T=1;T<=26;T++){
q[0]=a[ni][nj-1],q[1]=a[ni][nj+1],q[2]=a[ni-1][nj],q[3]=a[ni+1][nj];
q[4]=a[ni-1][nj-1],q[5]=a[ni-1][nj+1],q[6]=a[ni+1][nj-1],q[7]=a[ni+1][nj+1];
fl[0]=fl[1]=fl[2]=fl[3]=0;
for(res k=0;k<4;k++){
for(res i=0;i<8;i++){
if(q[i]==p[k]||p[k]=='!')fl[k]=1;
}
}
if(fl[0]==1&&fl[1]==1&&fl[2]==1&&fl[3]==1){
for(res i=1;i<=2;i++){
for(res j=1;j<=13;j++)putchar(a[i][j]);
puts("");
}
return;
}
if(nj<13&&ni==1)nj++;
else if(ni==1&&nj==13)ni=2;
else if(ni==2&&nj==1)ni=1;
else nj--;
for(res j=1;j<13;j++)b[1][j+1]=a[1][j];
b[2][13]=a[1][13];
for(res j=2;j<=13;j++)b[2][j-1]=a[2][j];
b[1][1]=a[2][1];
for(res i=1;i<=2;i++)for(res j=1;j<=13;j++)a[i][j]=b[i][j];
}
puts("Impossible");
}
}

[ARC093 D]

solution

题面:构造 $100\times 100$ 的网格染黑白色,使得白连通块个数为 $A$,黑为 $B$,$A,B\leq 500$。

做法:注意到 $A,B$ 不大,考虑将 $100\times 100$ 的网格分成上下两个部分,分别染全黑全白,然后在其中一些小空处染另一种颜色。比如一行行隔一个染一个这样子。具体可以看代码。

code
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
//2021.12.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
int a[N][N];
inline void MAIN(){
res A=read()-1,B=read()-1;
res x=1,y=1;
for(res i=1;i<=A;i++){
a[x][y]=1,y+=2;
if(y>100)x+=2,y=1;
}
for(res i=51;i<=100;i++)for(res j=1;j<=100;j++)a[i][j]=1;
x=100,y=1;
for(res i=1;i<=B;i++){
a[x][y]=0,y+=2;
if(y>100)x-=2,y=1;
}
puts("100 100");
for(res i=1;i<=100;i++){
for(res j=1;j<=100;j++){
if(a[i][j])putchar('.');
else putchar('#');
}
puts("");
}
}
}

[Code Festival Qual 17 A]

solution

题面:给定一个 $n\cdot m$ 的网格。一些人站在网格的边界上。一个人可以占据他面前的一行(列),过程是一直往前染色(每个人的颜色都不一样),直到下一个格子染上了颜色或者到达了边界。显然不同顺序会有不同的最终状态。求最终状态的方案数。

做法:

code
1
2


[POI 2011] IMP-Party

solution

题面:给定一张 $n$ 个点 $m$ 条边的图 $n\equiv 0(\mod\ 3)$,保证存在一个大小为 $\frac{2}{3}n$ 的团,要求输出一个大小为 $\frac{n}{3}$ 的团。

做法:高中时就知道的题了,结果现在才第一次做啊。

注意若两个点之间没有连边则一定不会在一个团里。考虑每次删掉两个不在一个团里的点,那么最多删 $\frac{n}{3}$ 次,因为存在一个大小为 $\frac{2}{3}n$ 的团。而剩下的 $\frac{1}{3}n$ 个点自然就是答案了。时间复杂度 $O(n^2+m)$。

code
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
//2021.12.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e3+10;
namespace MAIN{
int n,m;
int G[N][N];
int vis[N];
inline void MAIN(){
n=read(),m=read();
for(res i=1;i<=m;i++){
res u=read(),v=read();
G[u][v]=G[v][u]=1;
}
for(res i=1;i<=n;i++){
if(vis[i])continue;
for(res j=i+1;j<=n;j++){
if(G[i][j]||vis[j])continue;
vis[i]=vis[j]=1;break;
}
}
for(res i=1,t=1;i<=n&&t<=n/3;i++)if(!vis[i])printf("%d ",i),t++;
puts("");
}
}

[CF765 F]

solution

题面:$n$ 个数,$m$ 次询问 $[l,r]$,问 $[l,r]$ 区间内两数之差的最小值。

做法:一眼莫队,然后想把添加改成删除也去不掉 set 这一个 $\log$,感受一下过不了,就不写了。

接下来先考虑一个大暴力,离线下来后,考虑每次添加一个 $r$ 对所有右端点是 $r$ 的询问的贡献。考虑在 $[1,r]$ 中找到最靠右的大于 $a_r$ 的数 $a_p$,那么 $[1,p]$ 的答案就会更新个 $a_p-a_r$。以此类推,暴力的话,我们只用一个升序数列就将其卡到 $O(n^2)$。再观察观察这个东西到底有什么性质,注意到有一部分贡献是一定无意义的。因为找到一个 $p’$ 时,一定要求 $a_{p’}-a_r<a_{p}-a_{p’}$,那么 $0<a_{p’}-a_r<\frac{a_{p}-a_r}{2}$。于是这样要不断递减下去,最多只会有 $O(\log V)$ 次,即合法的 $p’$ 只有 $O(\log V)$。那么用一棵线段树维护下值域,再用棵 $\mathrm{BIT}$ 维护答案更新就行了。总复杂度 $O(n\log n\log V)$。

code
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
//2021.12.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e5+10;
namespace MAIN{
int n,m;
int a[N];
vector<Pair> que[N];
int tr[N];
inline void modify(const res &x,const res &y){
for(res i=x;i;i-=lowbit(i))tr[i]=min(tr[i],y);
}
inline int query(const res &x){
res ret=1000000000;
for(res i=x;i<=n;i+=lowbit(i))ret=min(ret,tr[i]);
return ret;
}
int mx[N*30],tot,ls[N*30],rs[N*30];
void modify(res &rt,res l,res r,const res &p,const res &va){
if(!rt)rt=++tot;
mx[rt]=max(mx[rt],va);
if(l==r)return;
res mid=(l+r)>>1;
if(p<=mid)modify(ls[rt],l,mid,p,va);
else modify(rs[rt],mid+1,r,p,va);
}
int query(res rt,res l,res r,const res &L,const res &R){
if(!rt)return 0;
if(L<=l&&r<=R)return mx[rt];
res mid=(l+r)>>1,ret=0;
if(L<=mid)ret=query(ls[rt],l,mid,L,R);
if(R>mid)ret=max(ret,query(rs[rt],mid+1,r,L,R));
return ret;
}
int RT;
int ans[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i]=read(),tr[i]=1000000000;
m=read();
for(res i=1;i<=m;i++){
res l=read(),r=read();
que[r].pb(mp(l,i)),ans[i]=1000000000;
}
for(res i=1;i<=n;i++){
res p=query(RT,0,1000000000,a[i],1000000000);
while(p)modify(p,a[p]-a[i]),p=query(RT,0,1000000000,a[i],(a[i]+a[p])/2-(~(a[i]+a[p])&1));
modify(RT,0,1000000000,a[i],i);
for(auto [l,id]:que[i])ans[id]=min(ans[id],query(l));
}
for(res i=1;i<=n;i++)tr[i]=1000000000,a[i]=1000000000-a[i];
for(res i=1;i<=tot;i++)ls[i]=rs[i]=mx[i]=0;
tot=RT=0;
for(res i=1;i<=n;i++){
res p=query(RT,0,1000000000,a[i],1000000000);
while(p)modify(p,a[p]-a[i]),p=query(RT,0,1000000000,a[i],(a[i]+a[p])/2-(~(a[i]+a[p])&1));
modify(RT,0,1000000000,a[i],i);
for(auto [l,id]:que[i])ans[id]=min(ans[id],query(l));
}
for(res i=1;i<=m;i++)printf("%d\n",ans[i]);
}
}

[Gym102956 K]

solution

题面:有 $n$ 块木板,第 $i$ 块木板有稳定性 $a_i$,木板从高到低排列。在木板上放置果子,第 $i$ 块木板被放了大于等于 $a_i$ 个果子后会碎裂,有 $\lfloor\frac k 2\rfloor$ 会下坠到下一块木板上。求至少需要多少果子才可以砸碎前 $i$ 块木板。

做法:注意到可以先用一些少的果子让下面的木板被破掉,然后上面的果子就不会被除二。于是会考虑区间 $\mathrm{dp}$,$f_{l,r,x}$ 表示破掉了 $l$ 到 $r$ 还剩 $x$ 个果子的最小代价,转移就很显然了。注意到破掉一个区间最多只会剩 $\max a_i$ 个果子,因为剩更多还无意义。总复杂度 $O(n^3a^2)$,因为跑不满,所以可以过。

code
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
//2021.12.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=70+10;
namespace MAIN{
int n;
int a[N];
int f[N][N][150+10];
inline void MAIN(){
n=read(),memset(f,0x3f,sizeof(f));
for(res i=1;i<=n;i++)a[i]=read(),f[i][i][a[i]/2]=a[i];
for(res len=2;len<=n;len++){
for(res l=1,r=l+len-1;r<=n;l++,r++){
for(res x=a[r]>>1;x<=150;x++){
res &ret=f[l][r][x];
for(res k=l+1;k<r;k++){
for(res X=a[r-1]/2;X<=150;X++){
res c=max(a[r]-X,0);
if(x-(X+c)/2>=a[k-1]/2)ret=min(ret,f[l][k-1][x-(X+c)/2]+f[k][r-1][X]+c);
else break;
}
}
if(x==a[r]>>1){
for(res X=a[r-1]>>1;X<=a[r]+1;X++){
res c=max(a[r]-X,0);
if((c+X)/2!=a[r]/2)break;
ret=min(ret,f[l][r-1][X]+c);
}
}
for(res X=a[r-1]>>1;X<=150;X++){
if(X/2>x)break;
res c=max(x*2-X,0);
if(c+X>=a[r])ret=min(ret,f[l][r-1][X]+c);
}
ret=min(ret,f[l][r-1][x-a[r]/2]+a[r]);
}
}
}
for(res i=1;i<=n;i++){
res ans=inf;
for(res j=a[i]>>1;j<=150;j++)ans=min(ans,f[1][i][j]);
printf("%d ",ans);
}
}
}

[统一省选2021 A卷] 矩阵游戏

solution

题面:中文不会自己看?

做法:

code
1
2


[TC12304]

solution

题面:给出一棵 $n$ 个点的树和 $k$,问有多少个 $n$ 的排列,满足按排列重标号后,对于每一个 $i=1,…,n-k+1$,$[i,i+k-1]$ 总是个连通块。

做法:

code
1
2


[CF708 E]

solution

题面:有一个 $(n+2) \times m$ 的网格。

除了第一行和最后一行,其他每一行每一天最左边和最右边的格子都有 $p$ 的概率消失。

求 $k$ 天后,网格始终保持连通的概率。

做法:纯高中数列题。

考虑一个暴力 $\mathrm{dp}$,即设 $f(i,l,r)$ 表示当前算到第 $i$ 行,存在的是 $[l,r]$ 的概率。转移就是

其中 $p_x$ 为有 $x$ 次删除的概率,等于 $\binom{k}{x}p^x(1-p)^{k-x}$。

发现这个转移正着有点难讨论,不如算不交,即

写好看点,即设第一个 $\sum$ 为 $F(i-1)$,第二个为 $L(i-1,l)$,第三个为 $R(i-1,r)$,那么就得看看这三个咋求。

首先根据对称性,有 $L(i,x)=R(i,m-x+1)$。

可惜 $L,R$ 还是 $O(n^2)$,我们把它们拆解一下,即

注意到 $F_L$ 的形式很类似 $F$,所以我们类似地去推一下式子

于是就得到了一个递推过程,一共 $n$ 层,每一层处理出 $p_{l-1}L(i,l)$ 的前缀和,这样就可以 $O(1)$ 推出 $F_L$,再处理 $F_L$ 的前缀和,这样就可以得到 $L$ 和 $F$。总时间复杂度 $O(nm)$。

code
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
//2021.12.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
const int M=1500+10;
namespace MAIN{
int n,m,p,k;
int F[M][M],L[M][M],FL[M][M],P[N],q[N];
int fac[N],inv[N];
inline int C(const res &x,const res &y){
return mul(fac[x],mul(inv[y],inv[x-y]));
}
inline void MAIN(){
n=read(),m=read(),p=read(),p=mul(p,qpow(read())),k=read(),fac[0]=fac[1]=inv[0]=inv[1]=1;
for(res i=2;i<=k;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=2;i<=k;i++)inv[i]=mul(inv[i-1],inv[i]);
for(res i=0;i<=min(m,k);i++)P[i]=mul(C(k,i),mul(qpow(p,i),qpow(1+kcz-p,k-i)));
for(res i=1;i<=m;i++)q[i]=Add(q[i-1],P[i-1]);
F[0][m]=L[0][m]=1;
for(res i=1;i<=n;i++)for(res j=1;j<=m;j++){
F[i][j]=mul(P[m-j],Add(mul(Add(L[i-1][m],kcz-L[i-1][m-j]),q[j]),kcz-FL[i-1][j]));
L[i][j]=Add(L[i][j-1],F[i][j]);
FL[i][j]=Add(FL[i][j-1],mul(P[j-1],L[i][j-1]));
}
printf("%d\n",L[n][m]);
}
}

[loj6215]

solution

题面:中文题面建议自己看。如果读不懂可以手玩下样例。

做法:完全不会,直接偷学 EI 和 xy 的做法。

$k$ 次幂直接是不好算的,考虑用第二类斯特林数拆解,即最终要求的是

我们想把后面对应每个 $i$ 求出来,这里是个比较经典的做法,具体证明可以用范德蒙德卷积( 我好像以前写过,或许也有其它理解 )。

令二叉树数量的 $\mathrm{GF}$ 为 $F$,$\sum_{T_n}\sum_{u\in \mathrm{leaf}} \binom{\mathrm{len(u,rt)}}{i}y^ix^n$ 的 $\mathrm{GF}$ 为 $G$,$\sum_{T_n} \sum_{u,v\in \mathrm{leaf}}\binom{\mathrm{len(u,v)}}{i}y^ix^n$ 为 $H$。

为了方便起见,在 $\mathrm{GF}$ 暂时不考虑路径端点和 $\mathrm{LCA}$ 的存在,这只用在最后的地方乘上 $x^3(1+y)^3$ 进行修正。

利用固定根,枚举左右子树来得到 $\mathrm{GF}$ 的递推式,即

解释下最后一条式子,考虑到 $H$ 要么是根的两个子树合并起来,那么 $\mathrm{LCA}$ 就是根,这样路径总长就是相加( 因为不考虑路径端点和 $\mathrm{LCA}$ ),按范德蒙德卷积那样,这样的组合数上标刚好是路径之和、$H$ 还可以是某个子树算好了,那另外一边就是任意树,由于可以翻转,所以乘个 $2$。

最后算出 $H$,再乘上一个 $x^3(1+y)^3$,即答案为 ( 令 $\sqrt{1-4x}=t$ )

分子那个可以先不管,最后乘上组合数即可,那么求的就是

这样的话,我们只要求出 $[x^n] \frac{1}{t^i}$ 即可在 $O(m^2)$ 的时间内解决这道题了 。( EI 写的那个理论复杂度我看不懂。。。水平太低了,呜呜呜 )

这是比较容易的,用一个拉格朗日反演即可,即

这个二项式系数至少可以在 $O(n+m)$ 的时间复杂度内求出,于是总复杂度就是 $O(n+m^2)$ 了。

然后我们会发现自己忽略了 $u=v$ 的情况,这个情况也是可以用 $\mathrm{GF}$ 推的,可以推出这个的 $\mathrm{GF}$ 是 $P=1+2FP$,于是 $P=\frac{1}{\sqrt{1-4x}}$。所以这个情况的答案就是 $[x^n] \frac{x}{\sqrt{1-4x}}=\binom{2n-2}{n-1}$。

code
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
//2022.1.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+300+10;
const int M=300+10;
namespace MAIN{
int f[N],g[M],C[M][M],h[M];
inline void pre(const res &n,const res &m){
if(n<0)return;
res inv2=qpow(2),ret=mul(inv2,3),fac=1;
f[0]=1,f[1]=1;
for(res i=1;i<=n;i++)f[1]=mul(f[1],i+n),fac=mul(fac,i);
f[1]=mul(f[1],qpow(fac)),f[2]=qpow(4,n);
if(n==0)for(res i=3;i<=m;i++)f[i]=1;
else for(res i=3;i<=m;i++)f[i]=mul(f[i-2],qpow(ret-1)),f[i]=mul(f[i],Add(ret,n-1)),add(ret,inv2);
C[0][0]=1;
for(res i=1;i<=m;i++){
C[i][0]=1;
for(res j=1;j<=i;j++)C[i][j]=Add(C[i-1][j],C[i-1][j-1]);
}
}
int S[M][M];
int ans[M];
inline void MAIN(){
res n=read(),m=read();
pre(n-3,m+3);
for(res i=0;i<=m;i++){
for(res j=0;j<=i;j++){
if(j&1)add(g[i],kcz-mul(C[i][j],f[i-j+3]));
else add(g[i],mul(C[i][j],f[i-j+3]));
}
g[i]=mul(g[i],i+1);
}
for(res i=0;i<=m;i++)add(h[i],g[i]),add(h[i+1],mul(g[i],3)),add(h[i+2],mul(g[i],3)),add(h[i+3],g[i]);
//S=S_2(i,j)*j!
S[0][0]=1;
for(res i=1;i<=m;i++)for(res j=1;j<=i;j++)S[i][j]=mul(Add(S[i-1][j-1],S[i-1][j]),j);
for(res i=0;i<=m;i++)for(res j=0;j<=i;j++)add(ans[i],mul(S[i][j],h[j]));
res Fac=1;
if(n>=3){
Fac=f[1];
for(res i=2;i<=5;i++)Fac=mul(Fac,2*n-i);
for(res i=1;i<=2;i++)Fac=mul(Fac,qpow(mul(n-i,n-i)));
}
else {
for(res i=1;i<n;i++)Fac=mul(Fac,mul(qpow(i),i+n-1));
}
for(res i=0;i<=m;i++)add(ans[i],Fac),printf("%d ",ans[i]);
puts("");
}
}

[CF891 B]

solution

题面:有一个长度为 $n$ 且数互不相同的序列 $a$,现要求将 $a$ 排列成 $b$,满足任何一个非空下标真子集的 $a$ 和不等于 $b$ 和。

做法:一道降智题。

不要被构造题的数据范围迷惑了。平凡地,我们认为 $a$ 是递增的。那么将 $a$ 位移一位就是 $b$。证明也是容易的,若不包含 $n$,则下者一定大于上者;若包含,则考虑补集,于是下者一定小于上者。时间复杂度 $O(n)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//2022.1.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
int n;
int a[N];
Pair b[N];
int c[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i]=read(),b[i]=mp(a[i],i);
sort(b+1,b+n+1),b[n+1].fi=b[1].fi;
for(res i=1;i<=n;i++){
c[b[i].se]=b[i+1].fi;
}
for(res i=1;i<=n;i++)printf("%d ",c[i]);
puts("");
}
}

[CC NOV19A PBOXES/CF802 O]

solution

题面:不会有人不知道 codechef 有官方汉化吧,不会吧不会吧。

做法:典中典之模拟费用流,之前因为实在不想写代码所以一直没用这种做法。

首先建个费用流模型,方便起见,我们将以前习惯的四层图模型改成三层,因为这类题的边是单向的,CC 这题经过贪心后也是单向的,CF 那题本来就是要求单向的。即 $S$ 向每个点连个权值 $a_i$ 流量 $1$,每个点向 $T$ 连个权值 $b_i$ 流量 $1$,然后点与点之间的连边是单向的,所以只要 $i$ 向 $i+1$ 连个权值 $0$ 流量 $\inf$ 即可。

这种题的增广都有一个很好的贪心性质:不会退回已经增广过的有权值边。这个性质保证了我们的增广路径实际就两种,一种是从 $i$ 到 $j$,其中 $i\leq j$。一种是 $i$ 到 $j$,但 $i>j$,那么这里就满足 $[j,i]$ 之间的边的反边有流量了,即被增广过了。也可以发现流量改变是区间的,要么加一,要么减一,于是我们分别考虑如何维护这两种增广信息。

第一种增广是随意的,只要找到左边一个最小的 $a_i$,右边一个最小的 $b_i$,直接加起来就是答案。这东西完全可以用线段树在合并区间的时候维护下即可。第二种增广有要求,它要求 $[j,i]$ 之间的反边流量不为 $0$,那要咋维护呢?如果我们已经想要用线段树的话,那就是要考虑两个区间合并要用哪些信息。发现这个东西其实挺类似最大区间和的,一个区间要维护连着左端点的最长反边流量不为 $0$ 的位置以及这一段的最小 $a_i$,还有右端点类似的一段位置和最小 $b_i$。发现如果没有修改的话,我们已经维护了答案。如果是区间加一,那等于直接包揽了整段区间;如果是区间减一,我们还需要知道哪些反边流量为 $1$,然后缩短那一段。实际上维护为 $1$ 的这个信息是艰难的,不如维护从左边开始的最小反边流量的位置和值( 说得有点绕,不过手画一下是可以理解的 ),右边同理( 同时可以注意到最小值都是一样的 ),然后也要把之前维护的流量不为 $0$ 的信息改成不跨过这个最小值点。发现这样的话区间减某个数可以直接从哪个最小反边流量处断开即可( 因为每次能减就已经保证了反边流量减完后还大于等于 $0$ )。于是就可以做了,时间复杂度 $O(n+k\log n)$。

实现上,我们会发现两种情况的答案不能直接放一起比较大小,不然下传减到 $0$ 的标记时会无法更新。

坑:注意到边实际是区间,别当做点了。

code
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
109
110
111
112
113
114
115
116
117
118
119
//2022.1.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
int n;
Pair a[N];
struct Ans{
int ans,ansl,ansr;
Ans() {}
Ans(res ans,res ansl,res ansr):ans(ans),ansl(ansl),ansr(ansr) {}
inline bool operator < (const Ans &B) const {
if(ans<B.ans)return 1;
if(ans>B.ans)return 0;
if(ansl<=ansr)return 1;
return 0;
}
inline void print(){
printf("%d %d %d\n",ans,ansl,ansr);
}
};
struct TR{
int mn;//min flow
int lm,rm;//position of mn from left to right or otherwise
Pair lmv,rmv;//min value & position of before lm/rm
//l a r b
Pair ma,mb;
Ans ans[3];
int ls,rs;
}tr[N<<2];
int tag[N<<2];
inline Ans merge(const Pair &A,const Pair &B){
return Ans(A.fi+B.fi>inf?inf:A.fi+B.fi,A.se,B.se);
}
inline TR merge(const TR &A,const TR &B){
TR C;
C.ls=A.ls,C.rs=B.rs;
C.mn=min(A.mn,B.mn);
C.ans[0]=min(A.ans[0],B.ans[0]);
if(A.mn>B.mn){
C.ans[0]=min(C.ans[0],A.ans[1]);
C.ans[0]=min(C.ans[0],merge(B.lmv,A.mb));
}
else if(A.mn<B.mn){
C.ans[0]=min(C.ans[0],B.ans[1]);
C.ans[0]=min(C.ans[0],merge(B.ma,A.rmv));
}
else {
C.ans[0]=min(C.ans[0],merge(B.lmv,A.rmv));
}
C.ans[1]=min({A.ans[1],B.ans[1],merge(B.ma,A.mb)});
C.ans[2]=min({A.ans[2],B.ans[2],merge(A.ma,B.mb)});
C.ma=min(A.ma,B.ma),C.mb=min(A.mb,B.mb);
if(A.mn>B.mn)C.lm=B.lm,C.lmv=min(A.ma,B.lmv);
else C.lm=A.lm,C.lmv=A.lmv;
if(A.mn<B.mn)C.rm=A.rm,C.rmv=min(B.mb,A.rmv);
else C.rm=B.rm,C.rmv=B.rmv;
return C;
}
inline void change(const res &rt,const res &v){
tag[rt]+=v,tr[rt].mn+=v;
}
inline void pushdown(const res &rt){
if(!tag[rt])return;
change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=0;
}
void build(res rt,res l,res r){
if(l==r){
tr[rt].ls=tr[rt].rs=l;
tr[rt].ma=mp(-a[l].se,l),tr[rt].mb=mp(a[l].se,l);
tr[rt].ans[0]=Ans(inf,l,l),tr[rt].ans[1]=tr[rt].ans[2]=Ans(0,l,l);
tr[rt].lm=tr[rt].rm=l;
tr[rt].lmv=tr[rt].rmv=mp(inf,0);
return;
}
res mid=(l+r)>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
void modify(res rt,res l,res r,const res &L,const res &R,const res &v){
if(L<=l&&r<=R){
change(rt,v);
return;
}
pushdown(rt);
res mid=(l+r)>>1;
if(L<=mid)modify(rt<<1,l,mid,L,R,v);
if(R>mid)modify(rt<<1|1,mid+1,r,L,R,v);
tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
void erase(res rt,res l,res r,const res &p){
if(l==r){tr[rt].ma=tr[rt].mb=mp(inf,p),tr[rt].ans[0]=tr[rt].ans[1]=tr[rt].ans[2]=Ans(inf,l,l);return;}
pushdown(rt);
res mid=(l+r)>>1;
if(p<=mid)erase(rt<<1,l,mid,p);
else erase(rt<<1|1,mid+1,r,p);
tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++){
res x=read(),y=read();
a[i]=mp(x,y);
}
sort(a+1,a+n+1),reverse(a+1,a+n+1),build(1,1,n);
RG LL ans=0;
for(res i=1;i<<1<=n;i++){
Ans ret=min(tr[1].ans[0],tr[1].ans[2]);
if(tr[1].mn>0)ret=min(ret,tr[1].ans[1]);
ans+=ret.ans;
res l=ret.ansl,r=ret.ansr;
erase(1,1,n,l),erase(1,1,n,r);
if(l<=r)modify(1,1,n,l,r-1,1);
else modify(1,1,n,r,l-1,-1);
printf("%lld\n",-ans);
}
}
}

[CF901 D]

solution

题面:给你一个有 $n$ 个顶点与 $m$ 条边的无向图,那些顶点的编号依次为 $1$ 到 $n$。

再给你 $n$ 个整数 $C_1,C_2,…,C_n$ 每一个数都在区间 $[-n,n]$ 之间。保证 $C_v$ 的奇偶性与顶点 $v$ 的度的奇偶性相同。一个顶点的的度是指连接到它的边数。

你需要按照下列的要求为所有边写上一个在 $-2\cdot n^2$ 与 $2\cdot n^2$ 之间的一个重量:对于任何一个顶点 $v$,所有连接到这个顶点的边的重量和等于 $C_v$。或者,确定这是不可能达到的。

做法:属于是想当然了,导致代码调急了。

首先可以注意到度数为 $1$ 的点直接就确定了它所在的边的边权,类似地,我们直接搞出一棵生成树,然后从叶子到根跑一遍。如果此时根权值已经达到要求,就可行了。否则考虑非树边的影响。

注意到除了根的总和是不变的,于是每次选择一条非树边,影响总和的值总是偶数的,这意味着根权值的差若为奇数则已经无解了。而若有一个奇环,一旦确定了那条非树边,绕一圈加减,则等价于 $\mathrm{lca}$ 的权值加或减了两倍,再一路到根就已经构造出答案了。若只有偶环,可以证明偶环的变化对根的相对影响为 $0$,所以直接是不行的。时间复杂度 $O(n)$。

坑:注意正负符号的变化。

code
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
//2022.1.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
int n,m;
LL C[N];
Pair edge[N];
int fa[N];
inline int find(res x){
while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;
}
vector<Pair> G[N];
int dep[N],F[N][21],Fa[N];
LL a[N],val[N];
int fl[N];
void dfs(res x,res fax,res depx){
dep[x]=depx,F[x][0]=fax;
for(res i=1;i<=20;i++)F[x][i]=F[F[x][i-1]][i-1];
for(auto [tox,id]:G[x]){
if(tox==fax)continue;
Fa[tox]=id,dfs(tox,x,depx+1);
}
for(auto [tox,id]:G[x])if(tox==fax){val[id]=C[x]-a[x],a[fax]+=val[id],a[x]=C[x];break;}
}
inline int getlca(res x,res y){
if(dep[x]<dep[y])swap(x,y);
res d=dep[x]-dep[y];
for(res i=20;~i;i--)if(d&(1<<i))x=F[x][i];
if(x==y)return x;
for(res i=20;~i;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
return F[x][0];
}
inline void MAIN(){
n=read(),m=read();
for(res i=1;i<=n;i++)C[i]=read(),fa[i]=i;
for(res i=1;i<=m;i++){
res u=read(),v=read();
edge[i]=mp(u,v);
res fu=find(u),fv=find(v);
if(fu==fv)continue;
fl[i]=1,G[u].pb(mp(v,i)),G[v].pb(mp(u,i)),fa[fu]=fv;
}
dfs(1,0,1);
RG LL p=C[1]-a[1];
if(p&1){puts("NO");return;}
if(!p){
puts("YES");
for(res i=1;i<=m;i++)printf("%lld\n",val[i]);
return;
}
for(res i=1;i<=m;i++){
if(fl[i])continue;
auto [u,v]=edge[i];
res lca=getlca(u,v);
if(~(dep[u]+dep[v]-2*dep[lca])&1){
if(~(dep[u]-dep[lca])&1)p=-p;
puts("YES");
if(~(dep[lca]-dep[1])&1)p=-p;
val[i]+=p/2,p=-p;
res now=u;
while(now!=lca)val[Fa[now]]+=p/2,now=F[now][0],p=-p;
now=v;
p=C[1]-a[1];
if(~(dep[u]-dep[lca])&1)p=-p;
if(~(dep[lca]-dep[1])&1)p=-p;
p=-p;
while(now!=lca)val[Fa[now]]+=p/2,now=F[now][0],p=-p;
now=lca;
while(now!=1)val[Fa[now]]+=p,now=F[now][0],p=-p;
for(res _=1;_<=m;_++)printf("%lld\n",val[_]);
return;
}
}
puts("NO");
}
}

[Uva1467]

solution

题面:工程师要安装 $n$ 个服务, 其中第 $i$ 个服务 $J_i$ 需要 $s_i$ 单位的安装时间,截止时间为 $d_i$。如果在截止时间之前完成任务, 不会有任何惩罚;否则惩罚值为任务完成时间与截止时间之差。从 $t=0$ 时刻开始执行任务,同一时刻只能执行一个任务, 你的任务是让惩罚值最大的两个任务惩罚值之和最小。求出最小值。

做法:如果只是让最大的一个最小,那么我们直接按截止时间升序、安装时间升序排序即可,这个贪心的证明直接调整法即可,因为最后的时间是不变的,所以容易证出。另一方面,当排好序之后,我们考虑最大的两个分别是 $J_1,J_2$,设它们完成的时间是 $a_1,a_2$。首先容易说明交换任何数到 $J_1,J_2$ 之间都是会让答案变大,因为一定有一个惩罚不变,而交换之后 $a-d<a’-d’$,$a’,d’$ 为交换后的某个数。举个例子,比如从前交换到中间。本来是 $a’a_1$,那么 $a’-d’>a_1-d_1$,所以这样交换一定是亏的。所以有效的交换只有 $J_1$ 前交换到 $J_2$ 后。而我们可以证明交换两个一定是亏的,这和上面那个类似,会发现 $a’’-d’’+a’-d’>a_1-d_1+a_2-d_2$,于是不如不交换。于是有了这个贪心就容易了,想 $O(n^3),O(n^2),O(n\log n)$ 都可以,当然我个人比较懒,写个能过的就跑路了。

注意我这里的交换可能是和空气交换。

code
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
//2022.1.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
int n;
Pair a[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++){
res x=read(),y=read();
a[i]=mp(y,x);
}
sort(a+1,a+n+1);
for(res i=n;i;i--)a[2*i-1]=a[i],a[2*i]=mp(inf,0);
n<<=1;
res mx=0,smx=0,s=0,vmx=0,vsmx=0;
for(res i=1;i<=n;i++){
s+=a[i].se;
if(s-a[i].fi>vmx)smx=mx,vsmx=vmx,mx=i,vmx=s-a[i].fi;
else if(s-a[i].fi>vsmx)smx=i,vsmx=s-a[i].fi;
}
res ans=vmx+vsmx;
for(res _=1,t=min(smx,mx),p=max(smx,mx);_<=t;_++){
for(res j=p;j<=n;j++){
swap(a[_],a[j]);
s=0,vmx=0,vsmx=0;
for(res i=1;i<=n;i++){
s+=a[i].se;
if(s-a[i].fi>vmx)vsmx=vmx,vmx=s-a[i].fi;
else if(s-a[i].fi>vsmx)vsmx=s-a[i].fi;
}
ans=min(ans,vmx+vsmx);
swap(a[_],a[j]);
}
}
printf("%d\n",ans);
}
}

[uoj91]

solution

题面:中文题面不会自己看?

做法:带删除的线性基。

首先操作一二的区间操作可以利用差分变成单点操作以及区间清零( 线性代数小知识 ),然后只需思考修改一个向量为向量空间的基底的影响。

一共两种情况,要么这个向量是基底中的一个不能被其他向量线性表出,即删除后会让空间降维,要么可以被被表出,那么就需要找到另一个可以表出它的且与基底线性无关的向量加入基底之中。

发现这两种情况类似,只需要维护每个非基底向量可以被哪几位表出,删除全是暴力的。由于总向量个数是 $O(n+q)$ 的,所以暴力的复杂度也只是 $O(\frac{(n+m)mq}{\omega})$,其中 $\omega$ 是用 bitset 压位的。

坑:注意遇到零向量就直接跑路,小心复杂度错误。

code
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
//2022.1.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
int n,m,q;
int id[N];
bitset<N> val[N],a[N],ex[N];
inline void insert(const res &I){
for(res i=m-1;~i;i--){
if(val[I].test(i)){
if(id[i])val[I]^=val[id[i]],ex[I]^=ex[id[i]];
else {id[i]=I;return;}
}
}
}
inline void Xor(const res &p,const bitset<N> &v){
res g=0;
if(v.none())return;
for(res i=1;i<=n;i++)if(val[i].none()&&ex[i].test(p)){g=i;break;}
if(!g)for(res i=0;i<m;i++)if(id[i]&&ex[id[i]].test(p)){g=id[i],id[i]=0;break;}
for(res i=1;i<=n;i++)if(i!=g&&ex[i].test(p))val[i]^=val[g],ex[i]^=ex[g];
val[g]^=v,insert(g);
}
inline void MAIN(){
n=read(),m=read(),q=read();
for(res i=1;i<=n;i++)cin>>a[i],val[i]=a[i]^a[i-1],ex[i].set(i),insert(i);
while(q--){
res opt=read();
if(opt==1){
res l=read(),r=read();
bitset<N> v;
cin>>v;
for(res i=l;i<=r;i++)a[i]^=v;
Xor(l,v);
if(r!=n)Xor(r+1,v);
}
else if(opt==2){
res l=read(),r=read();
bitset<N> v;
cin>>v;
Xor(l,a[l]^v);
if(r!=n)Xor(r+1,a[r]^v);
for(res i=r;i>l;i--)Xor(i,a[i]^a[i-1]),a[i]=v;
a[l]=v;
}
else {
bitset<N> ans;
ans.reset();
for(res i=m-1;~i;i--)if(id[i]&&!ans.test(i))ans^=val[id[i]];
for(res i=m-1;~i;i--)printf("%0d",ans.test(i));
puts("");
}
}
}
}

[CF901 A]

solution

题面:给定一棵树的深度 $n$ 和每个深度的结点数,说明这样的树是否唯一。

做法:显然若有两层点数都是大于 $1$ 则不唯一,否则唯一。

code
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
//2022.1.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
int n;
int a[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n+1;i++)a[i]=read();
for(res i=2;i<=n;i++)
if(a[i]>1&&a[i+1]>1){
puts("ambiguous");
res now=0;
for(res j=0;j<=n+1;j++){
for(res k=1;k<=a[j];k++)printf("%d ",now);
now+=a[j];
}
puts("");
now=0;
for(res j=0;j<=i;j++){
for(res k=1;k<=a[j];k++)printf("%d ",now);
now+=a[j];
}
printf("%d ",now-1);
for(res k=1;k<a[i+1];k++)printf("%d ",now);
now+=a[i+1];
for(res j=i+2;j<=n+1;j++){
for(res k=1;k<=a[j];k++)printf("%d ",now);
now+=a[j];
}
return;
}
puts("perfect");
}
}

[Acmtimus1599]

solution

题面:有 $n$ 个点,A 从第一个点开始走,按序经过第二三 $\cdots$ 个点,最后从第 $n$ 个点回到第一个点。多次询问,每次询问 B 在一个给定的点 $(x,y)$,目光跟着 A 走路,你需要计算在这个过程中 B 逆时针转的圈数减去顺时针转的圈数的结果是多少。

做法:注意到完整的圈才算,不完整的不是。再思考怎么才会完整的转一圈,发现只有当一个多边形把 B 包含在里面才会,另一方面,这个圈数就等价于被有向包含了几次。考虑以 B 做一条水平射线,每碰一次边界看看是还在里面还是在外面,里面加一,外面减一,发现这就是答案。实现时,没必要算这个交点,而直接对边界的边做一些判断,具体判断画个图即可。时间复杂度 $O(nm)$。

code
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
//2022.1.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e3+10;
namespace MAIN{
int n;
Pair a[N];
inline LL cross(const Pair &p0,const Pair &p1,const Pair &p2){
return (p1.fi-p0.fi)*(p2.se-p0.se)-(p2.fi-p0.fi)*(p1.se-p0.se);
}
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++){
res x=read(),y=read();
a[i]=mp(x,y);
}
a[n+1]=a[1];
res q=read();
while(q--){
res x=read(),y=read();
Pair p=mp(x,y);
res wn=0;
for(res i=1;i<=n;i++){
if(cross(a[i],a[i+1],p)==0){puts("EDGE"),wn=n+1;break;}
if(a[i].se<=p.se){
if(a[i+1].se>p.se)if(cross(a[i],a[i+1],p)>0)wn++;
}
else {
if(a[i+1].se<=p.se)if(cross(a[i],a[i+1],p)<0)wn--;
}
}
if(wn<=n)printf("%d\n",wn);
}
}
}

[ICPC2020昆明 I]

solution

题面:A 坐火车从 $s$ 到 $t$,经过了许多风车。火车在一条线段上行驶。随着火车的行驶,风车在 A 的视野里会发生位置相对变化。现在给出风车们的坐标,多次询问 $(h,k)$,请你找到当第 $h$ 个风车与其他风车的相对位置变化 $k$ 次时火车的位置。

做法:直接把 $O(n^2)$ 条直线与火车路径交一下,按 $x$ 排个序即可。时间复杂度 $O(n^2+m)$。

code
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
//2022.1.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
int n,m;
inline int sgn(const RG ld &x){
if(x<-eps)return -1;
if(x>eps)return 1;
return 0;
}
struct vec{
ld x,y;
vec() {x=y=0;}
vec(ld A,ld B){x=A,y=B;}
inline vec operator + (const RG vec &v) const {return {x+v.x,y+v.y};}
inline vec operator - (const RG vec &v) const {return {x-v.x,y-v.y};}
inline vec operator * (const RG ld &v) const {return {x*v,y*v};}
inline vec operator / (const RG ld &v) const {return {x/v,y/v};}
inline ld operator * (const RG vec &v) const {return x*v.x+y*v.y;}
inline ld len() const {return hypotl(x,y);}
inline ld len_sqr() const {return x*x+y*y;}
inline vec rotate(const RG ld &c) const {return {x*cosl(c)-y*sinl(c),x*sinl(c)+y*cosl(c)};}
inline vec trunc(const RG ld &l) const {return (*this)*l/len();}
inline vec rot90() const {return {-y,x};}
inline void init(){
x=read(),y=read();
}
inline bool operator < (const RG vec &A) const {
return x<A.x;
}
};
inline ld cross(const RG vec &A,const RG vec &B){
return A.x*B.y-A.y*B.x;
}
inline int line_intersection(const RG vec &a,const RG vec &b,const RG vec &p,const RG vec &q,vec &o,ld *t=0){
RG ld U=cross(p-a,q-p);
RG ld D=cross(b-a,q-p);
if(sgn(D)==0)return sgn(U)==0?2:0;
o=a+(b-a)*(U/D);
if(t)*t=U/D;
return 1;
}
inline bool ck_in(const vec &a,const vec &b,const RG vec &c){
return a.x<=c.x&&c.x<=b.x;
}
vec a[N];
vector<vec> b[N];
inline void MAIN(){
n=read(),m=read();
vec st,ed;
res fl=0;
st.init(),ed.init();
if(ed<st)swap(st,ed),fl=1;
for(res i=1;i<=n;i++)a[i].init();
for(res i=1;i<=n;i++){
for(res j=1;j<=n;j++){
if(i==j)continue;
vec p;
line_intersection(st,ed,a[i],a[j],p);
if(ck_in(st,ed,p))b[i].pb(p);
}
sort(b[i].begin(),b[i].end());
if(fl)reverse(b[i].begin(),b[i].end());
}
while(m--){
res h=read(),k=read();
if(b[h].size()<k)puts("-1");
else printf("%.10Lf %.10Lf\n",b[h][k-1].x,b[h][k-1].y);
}
}
}

[2017WF A]

solution

题面:逆时针方向给出一个简单多边形,问内部可放置的线段的最长长度,保证无两边共线。

做法:注意到答案的线段一定是多边形某两个端点连线所在的直线( 可以通过旋转反证 ),然后考虑一条直线被切割成若干段,会是一段在里面,一段在外面反复的,所有合起来取个 $\max$ 就好了。时间复杂度 $O(n^3)$。

code
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
//2022.1.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
int n,m;
inline int sgn(const RG ld &x){
if(x<-eps)return -1;
if(x>eps)return 1;
return 0;
}
struct vec{
ld x,y;
vec() {x=y=0;}
vec(ld A,ld B){x=A,y=B;}
inline vec operator + (const RG vec &v) const {return {x+v.x,y+v.y};}
inline vec operator - (const RG vec &v) const {return {x-v.x,y-v.y};}
inline vec operator * (const RG ld &v) const {return {x*v,y*v};}
inline vec operator / (const RG ld &v) const {return {x/v,y/v};}
inline ld operator * (const RG vec &v) const {return x*v.x+y*v.y;}
inline ld operator ^ (const RG vec &v) const {return x*v.y-y*v.x;}
inline ld len() const {return hypotl(x,y);}
inline ld len_sqr() const {return x*x+y*y;}
inline vec rotate(const RG ld &c) const {return {x*cosl(c)-y*sinl(c),x*sinl(c)+y*cosl(c)};}
inline vec trunc(const RG ld &l) const {return (*this)*l/len();}
inline vec rot90() const {return {-y,x};}
inline void init(){
x=read(),y=read();
}
inline bool operator < (const RG vec &A) const {
return x<A.x;
}
};
inline ld len(const vec &a,const vec &b,const vec &A,const vec &B){
return B^(a-A)/(b^B)*b.len();
}
vec a[N];
ld ans;
pair<ld,int> b[N];
inline void solve(const vec &v,const vec &p){
res cnt=0;
for(res i=1;i<=n;i++){
res c0=sgn(p^(a[i]-v)),c1=sgn(p^(a[i+1]-v));
if(c0!=c1)b[++cnt]=mp(len(v,p,a[i],a[i+1]-a[i]),c0-c1);
}
sort(b+1,b+cnt+1);
res fl=0;
ld ret=0;
for(res i=1;i<=cnt;i++){
if(fl)ret+=b[i].fi-b[i-1].fi;
else ans=max(ans,ret),ret=0;
fl+=b[i].se;
}
ans=max(ans,ret);
}
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i].init();
a[n+1]=a[1];
for(res i=1;i<=n;i++)for(res j=i+1;j<=n;j++)solve(a[i],a[j]-a[i]);
printf("%.10Lf\n",ans);
}
}

[集训队作业2018] 围绕着我们的圆环

solution

题面:uoj 的题面当然是中文的啊。

做法:其实看到这样的式子容易想到线性方程组,于是就猜到了基本和 $C$ 细节无关,只和秩有关。这也是容易证明的,考虑两个秩相同的 $C$,分别等于两组 $A,B$ 的乘积。注意到秩相同代表可以被初等变换成一致,又等价于分别左乘右乘一堆初等矩阵,于是发现每一组 $(A,B)$ 一定对应一组 $(A’,B’)$,所以证明了秩相同的 $C$ 答案是一致的。

设 $C$ 的秩为 $r$,不妨枚举 $A$ 的秩为 $t$,我们考虑 $A$ 能组出的秩为 $r$ 的矩阵有多少个。( 因为我们会发现用 $C$ 算 $A$ 似乎无比艰难 )$A$ 的秩为 $t$ 意味着它的列向量所组成的空间维度为 $t$,也即极大线性无关组的大小为 $t$。那么其他都被线性表出。而 $C$ 的列向量的线性极大无关组大小为 $r$,它的行只有 $t$ 行是线性无关的,其他都可被表出。于是这就说明 $A$ 能表出的 $C$ 只有 $t$ 行是有效的,也即能表出的 $C$ 只有 $f_{t,s,r}$,其中 $f_{a,b,c}$ 表示大小为 $a\cdot b$ 秩为 $c$ 的矩阵数量。( 上面证明不太严谨,建议自己严谨证明一下 )再考虑 $B$ 有几个,这就容易了,拿着 $A$ 的列向量去乘 $B$,考虑这个线性方程组的解数,容易得出 $B$ 的数量为 $2^{(q-t)s}$。而我们知道相同秩的 $C$ 答案是一样的,于是整体除以相同秩的 $C$ 的数量。即答案为

现在考虑如何算 $f$,显然想到 $\mathrm{q-binomial}$,具体证明可以看这里,于是

然后改写下答案形式,即

剩下来就是要动态算 $C$ 的秩,带删除的线性基即可。时间复杂度 $O(n^2+\frac{n^2(n+m)}{\omega})$。

代码实现上我直接比较暴力,显然取模次数可以更少,不过我懒得优化了。

code
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
//2022.1.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+1;
namespace MAIN{
int A,B,C;
int rnk,id[N];
bitset<N> val[N],ex[N];
bitset<N> re(){
bitset<N> ret;
for(res i=0;i<C;i++){
res x=read();
ret.set(i,x);
}
return ret;
}
inline void insert(const res &p){
for(res i=C-1;~i;i--){
if(val[p].test(i)){
if(id[i])val[p]^=val[id[i]],ex[p]^=ex[id[i]];
else {id[i]=p,rnk++;return;}
}
}
}
inline void change(const res &p,const bitset<N> &v){
res g=0;
for(res i=1;i<=A;i++)if(val[i].none()&&ex[i].test(p)){g=i;break;}
if(!g){
rnk--;
for(res i=0;i<C;i++)if(id[i]&&ex[id[i]].test(p)){g=id[i],id[i]=0;break;}
}
for(res i=1;i<=A;i++)if(i!=g&&ex[i].test(p))val[i]^=val[g],ex[i]^=ex[g];
val[g]=v,ex[g].reset().set(p),insert(g);
}
int pw2[N*N*2];
int fac2[N],ifac2[N];
int lastans;
inline int get(){
res ret=0;
for(res t=rnk;t<=A&&t<=B;t++){
res r=pw2[t*(t-1)/2+(B-t)*C];
r=mul(mul(ifac2[A-t],ifac2[B-t]),mul(ifac2[t-rnk],r));
add(ret,r);
}
return mul(mul(fac2[A-rnk],fac2[B]),ret);
}
inline void MAIN(){
A=read(),B=A,C=A,pw2[0]=1;
for(res i=1;i<N*N*2;i++)pw2[i]=Add(pw2[i-1],pw2[i-1]);
fac2[0]=1;
res lim=max({A,B,C});
for(res i=1;i<=lim;i++)fac2[i]=mul(fac2[i-1],pw2[i]-1);
ifac2[lim]=qpow(fac2[lim]);
for(res i=lim;i;i--)ifac2[i-1]=mul(ifac2[i],pw2[i]-1);
res q=0,k=0;
for(res i=1;i<=A;i++)val[i]=re(),ex[i].set(i),insert(i);
printf("%d\n",lastans=get());
while(q--){
res x=read()^(k*lastans);
change(x,re());
printf("%d\n",lastans=get());
}
}
}

[CF960 G]

solution

题面:给你三个正整数 $n,a,b$,定义 $A$ 为一个排列中是前缀最大值的数的个数,定义 $B$ 为一个排列中是后缀最大值的数的个数,求长度为 $n$ 的排列中满足 $A=a$ 且 $B=b$ 的排列个数。

做法:

code
1
2


[Cometoj#2 F]

solution

题面:是中文题面捏。

做法:

code
1
2


[CF468 C]

solution

题面:$f(x)$ 表示 $x$ 的每一位数的和,给出 $a$,构造 $l,r$,使得 $\sum_{i=l}^r f(i)$ 是 $a$ 的倍数。

做法:注意到在某个数的最前面添加个 $1$ 是会让答案加一,我们为了让 $\sum_{i=l}^r f(i)$ 至少要大于 $a$,所以先算了下 $\sum_{i=1}^{10^{18}-1} f(i)$ 的值,可以组合意义得出这个是 $9\times9\times10^{18}$。另一方面,根据位移的性质,我们只用位移 $a-(9\times9\times10^{18}\mod a)$ 位即可让缺少的部分被补上了,所以就做完了。时间复杂度 $O(1)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//2022.1.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
inline void MAIN(){
LL a=Read();
RG LL t=1000000000000000000%a;
t=t*9%a*9%a;
t=a-t;
t%=a;
printf("%lld %lld\n",max(t,1ll),t+1000000000000000000-1);
}
}