ZROI 2019 暑期游记

ZROI 游记

在自闭中度过了17天

挖了无数坑,填了一点坑

所以还是有好多坑啊zblzbl

挖坑总集:

  • 时间分治
  • 差分约束
  • Prufer序列
  • 容斥
  • 树上数据结构 例题C (和后面的例题)
  • 点分
  • 最大流、费用流、上下界
  • Hero meet devil(dp套dp)
  • Pollards’ Rho
  • CRT & exCRT
  • BSGS & exBSGS
  • NTT & FFT 以及 分治NTT & FFT (& 原根)
  • Cipolla 算法(二次剩余)
  • Min25

ZROI D1

T1 小K与集合

题目传送门

首先知道,如果有多于k个1,显然直接把k个1分别放到不同的组,然后剩下的随便放,第一回合就没法拿了。

那么如果只有k-1个1呢,稍微想一下知道剩下那个组至少必须放k个2。因为就算拿到了2的组,会得到k个1。

然后感性想一想,k个i可以当一个i-1。没错,这题这么贪心是对的。

证明咕咕咕了。


这个玩意实现起来有点麻烦,我写的是递归。用ned(x,w)表示需要拿1个x到w组,如果没有x了递归到进行k次ned(x-1,w)。记忆化一下是不是这个数字已经凑不出来了。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100006
int n , k;
int A[MAXN] , cnt[MAXN];
int ksm( int a , int x ) {
long long ans = 1 , cur = a;
while( x ) {
if( x & 1 ) ans *= cur;
cur *= cur , x >>= 1;
if( ans > n || cur > n ) return 0x3f3f3f3f;
}
return ans;
}
vector<int> group[MAXN];
int ok[MAXN] , vis[MAXN];
bool ned( int x , int w ) {
if( x == n + 1 ) return ok[x] = false;
if( ~ok[x] ) return ok[x];
if( cnt[x] ) { group[w].push_back( x ) , --cnt[x]; return true; }
int r = k; while( r-- ) if( !ned( x + 1 , w ) ) return ok[x] = false;
return true;
}
vector<int> pos[MAXN];int t[MAXN];
int main() {
int T;cin >> T;
while( T-- ) {
cin >> n >> k;
memset( ok , -1 , sizeof ok );
memset( vis , 0 , sizeof vis );
memset( cnt , 0 , sizeof cnt );
memset( t , 0 , sizeof t );
for( int i = 1 ; i <= n ; ++ i ) pos[i].clear();
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , ++cnt[A[i]] , pos[A[i]].push_back( i );
for( int i = 0 ; i < k ; ++ i ) group[i].clear();
int flg = 0;
int r = k; while( r-- ) {
if( !ned( 1 , r ) )
{ puts( "0" ); flg = 1 ; break; }
}
if( flg ) continue;
int poi = 0;
printf("1");
for( int i = 0 ; i < k ; ++ i ) {
puts("");
printf("%d ",i != k - 1 ? group[i].size() : n - poi);
poi += group[i].size();
for( int j = 0 ; j < group[i].size() ; ++ j )
printf("%d ",pos[group[i][j]][t[group[i][j]]]) , vis[pos[group[i][j]][t[group[i][j]]]] = 1 , ++ t[group[i][j]];
}
for( int i = 1 ; i <= n ; ++ i ) if( !vis[i] )
printf("%d ",i);
puts("");
}
}

T2 小K的数据

直接暴力往前跳,没了。

考虑(l2,r2) 作为儿子节点 (l1,r1)作为父亲节点建树,然后每次从一个点往上跳就没了(当然跳要用模运算优化成O1)。

(这里的区间指(l2,r2))

然而每次二分在哪个区间,然后跳出去,最少跳出一个区间,最多一询问跳m2次,复杂度是对的。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN 1006
int n , m1 , m2 , q;
int pos[MAXN] , c[MAXN];
struct que{
int l1 , r1 , l2 , r2;
que( int a = 0 , int b = 0 , int c = 0 , int d = 0 ) :l1(a),r1(b),l2(c),r2(d) {}
bool operator < ( const que a ) const {
return l2 < a.l2;
}
}Q[MAXN];
map<int,int> col;
int main() {
cin >> n >> m1 >> m2 >> q;
char ch[4];
for( int i = 1 ; i <= m1 ; ++ i ) scanf("%d%s",&pos[i] , ch ) , c[i] = ch[0];
for( int i = 1 ; i <= m2 ; ++ i ) scanf("%d%d%d%d",&Q[i].l1 , &Q[i].r1 , &Q[i].l2 , &Q[i].r2);
sort( Q + 1 , Q + m2 + 1 );
for( int i = 1 ; i <= m1 ; ++ i ) {
int poi = pos[i] , p;
while( true ) {
p = upper_bound( Q + 1 , Q + m2 + 1 , que( 0 , 0 , poi , 0 ) ) - Q ;
if( p == 1 ) break;
-- p;
int l = Q[p].l1 , r = Q[p].r1 , L = Q[p].l2 , R = Q[p].r2;
if( poi < L || poi > R ) break;
poi = ( poi - l ) % ( L - l ) + l;
}
col[poi] = c[i];
}
int x;
while( q --> 0 ) {
scanf("%d",&x);
int p;
while( true ) {
p = upper_bound( Q + 1 , Q + m2 + 1 , que( 0 , 0 , x , 0 ) ) - Q ;
if( p == 1 ) break;
-- p;
int l = Q[p].l1 , r = Q[p].r1 , L = Q[p].l2 , R = Q[p].r2;
if( x < L || x > R ) break;
x = ( x - l ) % ( L - l ) + l;
}
printf("%c\n" , col[x] ? col[x] : '?');
}
}

T3 小K与奇数

首先判断无解,如果有度数不是奇数 或 边数不是偶数 是 无解 的充要条件。(证明可以看神仙duyi的博客


考虑没有限制长度是偶数的情况

考虑建立一个虚拟节点 n+1 连向全部的点,由于所有点度数是奇数并且题目保证了点数是偶数,一定存在一条欧拉回路(所有点度数都是偶数了)

把欧拉回路跑出来,然后通过n+1分割出的很多序列就是答案。


那么如果长度是偶数呢

考虑求一个这个图的长度为2的链的覆盖。

假设我们求出了,就直接把长度为2的链的两端连边,新图虽然不连通,但是满足每个点的度数都是偶数。比如u->v v->w 那么可以连 u->w这条边。

作出了这个东西,直接在这上面快乐地跑前面没有限制的算法就可以了。

具体怎么做这个东西呢,考虑这个图的dfs树。每次只考虑一个点子树上的点向这个点的边,暴力匹配连边就好了。如果这个点子树上向这个边个数为奇数再把这个点到父亲的边算上,然后标记一下就好了。

代码鸽掉了,有时间写,睡觉了💨

ZROI D2

小K与赞助

题目链接

考虑每个点向自己的父亲连一条容量为这个点限制,权值为0的边(在两棵树里面)

然后从源点到一个虚拟节点连边,容量为1,权值为这个点的点权(显然,一个点只能被选择一次)

然后两个树的根节点向汇点连边

跑最大费用流即可

(码的时候addedge写错调了好久。。)

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
120
121
122
123
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
#define MAXN 10100
int n , m , s , t , q1 , q2;
struct edge{
int to , w , dis , nxt;
}e[MAXN<<3]; int cnt = -1;
int maxf = 0 , minc = 0 , fl[MAXN] , dis[MAXN] , pre[MAXN] ;
int head[MAXN] , lst[MAXN];
void ade( int u , int v , int w , int d ) {
e[++cnt].nxt = head[u] , e[cnt].w = w;
e[cnt].to = v , e[cnt].dis = d;
head[u] = cnt;
e[++cnt].nxt = head[v] , e[cnt].w = 0;
e[cnt].to = u , e[cnt].dis = -d;
head[v] = cnt;
}
void sfpa( );
int hd1[MAXN<<1] , nex1[MAXN<<1] , to1[MAXN<<1] , rt1 , cnt1 = 0;
int hd2[MAXN<<1] , nex2[MAXN<<1] , to2[MAXN<<1] , rt2 , cnt2 = 0;
int lim1[MAXN] , lim2[MAXN];
void ade1( int u , int v ) {
to1[++cnt1] = v , nex1[cnt1] = hd1[u] , hd1[u] = cnt1;
}
void ade2( int u , int v ) {
to2[++cnt2] = v , nex2[cnt2] = hd2[u] , hd2[u] = cnt2;
}
int fa1[MAXN] , fa2[MAXN];
void dfs1( int u , int fa ) {
for( int i = hd1[u] ; i ; i = nex1[i] ) {
int v = to1[i];
if( v == fa ) continue;
fa1[v] = u;
dfs1( v , u );
}
}
void dfs2( int u , int fa ) {
for( int i = hd2[u] ; i ; i = nex2[i] ) {
int v = to2[i];
if( v == fa ) continue;
fa2[v] = u;
dfs2( v , u );
}
}
int c[MAXN];
int main() {
memset( head , -1 , sizeof head );
cin >> n; s = 3 * n + 1 , t = 3 * n + 2;
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&c[i]);
cin >> rt1;
for( int i = 1 , u , v ; i < n ; ++ i ) {
scanf("%d%d",&u,&v);
ade1( u , v ) , ade1( v , u );
}
cin >> rt2;
for( int i = 1 , u , v ; i < n ; ++ i ) {
scanf("%d%d",&u,&v);
ade2( u , v ) , ade2( v , u );
}
memset( lim1 , 0x7f , sizeof lim1 ) , memset( lim2 , 0x7f , sizeof lim2 );
cin >> q1;
for( int i = 1 , u , x ; i <= q1 ; ++ i ) {
scanf("%d%d",&u,&x);
lim1[u] = x;
}
cin >> q2;
for( int i = 1 , u , x ; i <= q2 ; ++ i ) {
scanf("%d%d",&u,&x);
lim2[u] = x;
}
dfs1( rt1 , rt1 ) , dfs2( rt2 , rt2 );
fa1[rt1] = t , fa2[rt2] = t - n;
for( int i = 1 ; i <= n ; ++ i ) {
ade( i , fa1[i] , lim1[i] , 0 );
ade( i + n , fa2[i] + n , lim2[i] , 0 );
ade( i + 2 * n , i , 1 , 0 ) , ade( i + 2 * n , i + n , 1 , 0 );
ade( s , i + 2 * n , 1 , -c[i] );
}
sfpa( );
cout << - minc << endl;
}
bool spfa( int s , int t );
void sfpa( ) {
while( spfa( s , t ) ) {
int u = t;
maxf += fl[t] , minc += fl[t] * dis[t];
while( u != s ) {
e[lst[u]].w -= fl[t] , e[lst[u] ^ 1].w += fl[t];
u = pre[u];
}
}
}
bool vis[MAXN];
queue<int> Q;
bool spfa( int s , int t ) {
memset( dis , 0x7f , sizeof dis );
memset( fl , 0x7f , sizeof fl );
memset( vis , 0 , sizeof vis );
memset( pre , -1 , sizeof pre );
Q.push( s ) , vis[s] = 1 , dis[s] = 0;
while( !Q.empty() ) {
int u = Q.front(); Q.pop();
vis[u] = 0;
for( int i = head[u] ; ~i ; i = e[i].nxt ) {
if( e[i].w > 0 && dis[e[i].to] > dis[u] + e[i].dis ) {
dis[e[i].to] = dis[u] + e[i].dis;
pre[e[i].to] = u;
lst[e[i].to] = i;
fl[e[i].to] = min( fl[u] , e[i].w );
if( !vis[e[i].to] )
vis[e[i].to] = true , Q.push( e[i].to );
}
}
}
return pre[t] != -1;
}

小K与重建计划

题目链接

前两个subtask:

暴力 乱搞

第三个:

当它是树,有答案当且仅当点权和大于等于边权和

证明:首先,充分性很显然,点权和小于边权和最后预算肯定超支啊。。

必要性:每次必定可以选择一个边两端大于边权的边,把它缩成一个点,然后归纳证明即可

然后,如果这个树有解,那么必定存在一条边使得它的权值大于它连接的点权和。假如没有,那么可以推出最后的点权和小于了边权和,与有解矛盾。

那么可以直接暴力缩,这个点就做完了。

第四个

直接在图上跑最小生成树,然后用第三个的方法套一下。

最小生成树上的边权和最小,显然是最优秀的。

正解

考虑一个以u为根的树形结构

因为整个树肯定是点权和大于边权和的,那么u的子树中必定有一个与u连着点权和大于边权和(证明类似)。因为根节点的点权相当于是个常数,可以直接考虑用子树点权和-边权和 再减去到父亲边的权从大到小排序,然后一个一个缩就可以了。

因为整个树点权和大于边权和,那么必定存在一个u的儿子v,使得v这个子树和u连着组成的这个树点权和大于边权和(证明类似于必定存在一条边的权值大于点权和)

考虑设v的子树上的点权和-边权和为A , v到u的边权为 B , u的权值为 C

那么 必定存在 v 使得 A - B + C > 0

那么我们干脆用 A - B + C 为关键字,从大到小处理每个儿子,又因为 C 永远是个常数,尽管 C 在变化也不需要在比较大小的时候用到,直接按照 A - B 排序处理即可。

每次进入这个点,如果它到它的父亲这条边拿了是增加权值就拿上,否则处理完了子树再拿。而且这么做因为sort常数有点大,跑得很慢,分两拨处理要快一些(是线性的)但是kruskal本身就带log了,懒得优化了

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
#define MAXN 200006
#define int long long
int n , m;
long long A[MAXN];

unordered_map<long long , int> bac;

struct edge{
int u , v , w , id;
} E[MAXN] ;
bool cmp( edge a , edge b ) {
return a.w < b.w;
}

vector<int> G[MAXN] , W[MAXN];
int fa[MAXN];
int find( int x ) {
return x == fa[x] ? x : fa[x] = find( fa[x] );
}

long long Sw[MAXN] , Sl[MAXN]; int siz[MAXN] , wtf[MAXN]; // 点权和 和 链权和
void dfs( int u , int fa ) {
Sw[u] = A[u] , siz[u] = 1;
for( int i = 0 ; i < G[u].size() ; ++ i ) {
int v = G[u][i] , w = W[u][i];
if( v == fa ) continue;
Sl[u] += w , wtf[v] = w;
dfs( v , u );
siz[u] += siz[v] , Sl[u] += Sl[v] , Sw[u] += Sw[v];
}
}
int w[MAXN];
bool cmpp( int a , int b ) {
return w[a] > w[b];
}
bool cmm( int a , int b ) {
return a > b;
}
void work( int u , int fa ) {
for( int i = 0 ; i < G[u].size() ; ++ i ) {
int v = G[u][i] , ww = W[u][i];
if( v == fa ) { w[fa] = 0 , W[u][i] = 0; continue; }
w[v] = Sw[v] - Sl[v] - ww , W[u][i] = Sw[v] - Sl[v] - ww;
}
sort( G[u].begin() , G[u].end() , cmpp ) , sort( W[u].begin() , W[u].end() , cmm );
int flg = 0;
if( - wtf[u] + A[fa] >= 0 && u != 1 ) printf("%lld ",bac[ 1ll * min( u , fa ) * MAXN + max( u , fa ) ]) , flg = 1 , A[u] += A[fa] - wtf[u];
for( int i = 0 ; i < G[u].size() ; ++ i ) {
int v = G[u][i];
if( v == fa ) continue;
work( v , u ) , A[u] = A[u] + W[u][i];
}
if( !flg && u != 1 ) printf("%lld ",bac[ 1ll * min( u , fa ) * MAXN + max( u , fa ) ]) , A[u] += A[fa] - wtf[u];
}

signed main( ) {
cin >> n >> m;
long long Re = 0;
for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&A[i]) , Re += A[i];
for( int i = 1 ; i <= m ; ++ i ) {
scanf("%lld%lld%lld",&E[i].u,&E[i].v,&E[i].w) , E[i].id = i;
if( E[i].u > E[i].v ) swap( E[i].u , E[i].v );
}
sort( E + 1 , E + 1 + m , cmp );
for( int i = 1 ; i <= n ; ++ i ) fa[i] = i;
long long re = 0;
for( int i = 1 ; i <= m ; ++ i ) {
int u = E[i].u , v = E[i].v;
if( find( u ) != find( v ) ) {
fa[find( u )] = find( v );
bac[ 1ll * u * MAXN + v ] = E[i].id;
G[u].push_back( v ) , G[v].push_back( u );
W[u].push_back( E[i].w ) , W[v].push_back( E[i].w );
re += E[i].w;
}
}
if( Re < re ) return puts("0") , 0;
puts("1");
dfs( 1 , 1 );
work( 1 , 1 );
}

小K与作品

题目链接

先放个别人的题解(鸽了)

考虑g(x)表示从x向前最短可以找到一个完全平方数

那么可以证明g(x) 与 f(x) 互为反函数(为什么?)

假设f(x) = y , 那么考虑从x到f(x)得到的那个完全平方数是a

考虑g(x) 得到的完全平方数是b

那么a b每个质因子质数异或起来也是0,

(剩下的证明先鸽了)

然后把l+1 , r-1 放进线性基,然后查一下 l ^ r 在里面有没有出现

然后得到了一个$n \frac{n^2}{w}$做法


ZROI D3

游戏

题目链接

考虑删除一个木板相当于交换两端的答案

对木板排序,从下往上做,没了

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 200006
int w , h , n;

int getpos( int ww , int hh ) { // 是哪一个求会落到 ww , hh
hh %= 2 * w;
int flg = 0;
if( hh >= w ) flg = 1;
hh %= w ;
++ hh;
int t = hh - ww + 1 , res = 0;
if( t <= 0 ) res = 1 , t = -t , t += 2;
if( t & 1 ) {
if( t == 1 ) res += 1;
else res += t - 1;
} else {
res = 0;
t = hh - ( w - ww );
if( t <= 0 ) res = -1 , t = -t , t += 2;
if( t & 1 ) {
if( t == 1 ) res += w;
else res += w + 2 - t;
}
}
if( flg ) res = w + 1 - res;
return res;
}
int ans[MAXN] , pre[MAXN];
struct opt{
int x , y;
} op[MAXN] ;
bool cmp( opt a , opt b ) {
return a.y > b.y;
}
int main() {
cin >> h >> w >> n;
for( int i = 1 ; i <= w ; ++ i ) pre[i] = getpos( i , h ) , ans[pre[i]] = i;
for( int i = 1 ; i <= n ; ++ i )
scanf("%d%d",&op[i].y,&op[i].x);
sort( op + 1 , op + 1 + n , cmp );
for( int i = 1 ; i <= n ; ++ i ) {
int l = op[i].x , r = op[i].x + 1 , ht = op[i].y;
swap( ans[getpos( l , ht )] , ans[getpos( r , ht )] );
}
for( int i = 1 ; i <= w ; ++ i ) printf("%d\n",ans[i]);
}

画画

题目链接

两个人在从左上往右下移动

(x1 , y1) ( x2 , y2 )

x1 < x2 时 则第一个人走的路径是确定好的

y1 < y2 时 第一个人走的路径确定好的

(鸽几天)

交易

题目链接

10pts

直接模拟

40pts q = 1

一条信息什么时候最晚传到终点

65pts 链

考虑左边的信息到右边的贡献 ( x -> x + 1 )

对于一条边,假设在l1,r1 和 l2,r2 是断开的,那么经过这条边时就是吧中间的一段给加到后面的区间 线段树

std1

类比链,点分治,求经过重心的点对的信息 直接合并

线段树合并

再从重心向下推一遍 类似点分治的去重

Onlog^2n

std2

假设一个点的信息数量是val 那么断开时记录一下 tmp = val

则重新联通时 就变成了X 和 Y当前信息的个数和再减去原来的

ZROI D4

题目链接

有决策单调性!可以直接分治 mplog

随便搞搞斜优就好了、、

$dp[i][j] = min( dp[k][j-1] - kdi + S{k} ) - S_i + id_i + d_i$

$dp[t][j-1] - tdi + S{t} < dp[p][j-1] - pdi + S{p} $

$\frac{dp[t][j-1] + S_t - dp[p][j-1] - S_p}{t-p} < d_i (t > p)$

只是很难写QAQ

然后全开longlong 100 -> 90 (常数)O mp

赛后卡了卡常终于跑过去了。。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define RE register
using namespace std;
#define MAXN 100006
typedef long long ll;
int n , m , p;
int d[MAXN] , poi[MAXN];
ll dp[50006][1006];
ll spoi[MAXN];
int que[MAXN] , head , tail;
int j;
int read( ) {
int res = 0; char ch = ' ';
while( ch > '9' || ch < '0' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) { res *= 10 , res += ch - '0' , ch = getchar(); }
return res;
}
signed main() {
cin >> n >> m >> p;
for( RE int i = 2 ; i <= n ; ++ i ) d[i] = read() , d[i] += d[i - 1];
for( RE int i = 1 , h , t ; i <= m ; ++ i ) {
h = read( ) , t = read();
poi[i] = t - d[h];
}
sort( poi + 1 , poi + 1 + m );
for( RE int i = 1 ; i <= m ; ++ i ) spoi[i] = spoi[ i - 1 ] + poi[i];
j = 1;
for( RE int i = 1 ; i <= m ; ++ i )
dp[i][1] = 1LL * i * poi[i] - spoi[i];
for( j = 2 ; j <= p ; ++ j ) {
head = 0 , tail = -1;
for( int i = 1 ; i <= m ; ++ i ) {
while( head < tail && poi[i] * ( que[head] - que[head + 1] ) < ( spoi[ que[head] ] + dp[que[head]][ j - 1 ] - spoi[que[head + 1]] - dp[que[head + 1]][j - 1] ) ) ++ head;
dp[i][j] = dp[que[head]][j - 1] + 1LL * poi[i] * ( i - que[head] ) - ( spoi[i] - spoi[que[head]] );
while( head < tail && ( spoi[ que[tail] ] + dp[que[tail]][ j - 1 ] - spoi[que[tail - 1]] - dp[que[tail - 1]][j - 1] ) * ( que[tail] - i ) < ( spoi[ que[tail] ] + dp[que[tail]][ j - 1 ] - spoi[i] - dp[i][j - 1] ) * ( que[tail] - que[tail - 1] ) ) -- tail;
que[++tail] = i;
}
}
printf("%lld",dp[m][p]);
}

设f(k) 表示恰好切k段

打表 发现 f是凸的

据说有mlogm的做法(鸽了)(但真的好强)

打地鼠

题目链接

奇怪的和

题目链接

ZROI D5

小D与子序列

题目链接

考虑dp,dp表示前i小得到j的最少个数,顺便维护一个len表示以这个作为最大值往前多少个取到最小值

哦不用记录len了,,其实直接记录最小值转移就可以了!

考试的时候脑子混了。。。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define MAXN 5006
int n , m;
int dp[MAXN][MAXN] , pre[MAXN][MAXN] , len[MAXN][MAXN];
int A[MAXN];
int main() {
cin >> n >> m;
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
sort( A + 1 , A + 1 + n );
memset( dp , 0x3f , sizeof dp );
int minm = 0x3f3f3f3f;
for( int i = 1 ; i <= n ; ++ i ) {
for( int j = 1 ; j <= m ; ++ j ) {
if( j < A[i] ) if( dp[i - 1][j] != 0x3f3f3f3f )
{ dp[i][j] = dp[i - 1][j] , pre[i][j] = j; continue; } else;
else if( A[i] == j ) { dp[i][A[i]] = 1; }
else {
if( dp[i - 1][j - A[i]] == 0x3f3f3f3f && dp[i - 1][j] == 0x3f3f3f3f ) continue;
if( dp[i - 1][ j - A[i] ] + 1 < dp[i - 1][j] )
dp[i][j] = dp[i - 1][j - A[i]] + 1 , pre[i][j] = j - A[i];
else
dp[i][j] = dp[i - 1][j] , pre[i][j] = j;
}
}
minm = min( minm , dp[i][m] );
}
if( minm == 0x3f3f3f3f ) return puts("-1") , 0;
int ans = 0x3f3f3f3f;
for( int i = 1 ; i <= n ; ++ i )
if( dp[i][m] == minm && pre[i][m] != m ) {
int cur = m , j = i;
while( pre[j][cur] ) cur = pre[j][cur] , -- j;
ans = min( ans , A[i] - A[j] );
}
cout << ans << endl;
}

小D与字符串

题目链接

首先,这个串肯定是长成这样的:

一段一段循环出现的和最后一小段循环节的前驱

那么,假设前面循环出现的段每段有$ai$个ith字符,最后小段有$b_i$个ith字符,那么可以发现每种字符贡献是独立的(把块内randomshuffle一下结果没变嘛)那么显然有$b{i} \leq a_{i}$。

并且,由于总共ith字符个数只有$c_i$个所以还有:

$a{i} \cdot k+b{i} \leq c_{i}$

也就是说,要在满足这两个条件的前提下,我们需要最大化

$a_i(k - 1) + b_i$

为啥要-1呢,因为第一块不在lcp里面。。(不然就完全重复的后缀了)

考虑什么时候答案最优,当$a_i$减少1 ,$b_i$增加k的时候,带入式子发现答案正好增加了1,也就是说对于每一个$k$我们希望$a_i$尽可能小,同时$b_i$尽可能大,但是也得满足前面所说的限制。


枚举k,分两种情况讨论:

1.$b_i = a_i$

如果可以做到$b_i = a_i$显然会让a,b相等。但是这个情况必须满足$k+1|c_i$,并且$a_i = c_i / (k + 1)$

2.$b_i < a_i$

首先有$b_i + k > a_i - 1$,否则完全可以再进行一次减少a增加b的操作。

并且,由于$b_i$不能增加(除非增加k都会让答案变得不优秀)

所以,一定有$b_i = a_i - k$

带入不等式可以推出

$a_i \leq \lceil \frac{c_i}{k+1}\rceil$

由于$b_i = a_i - k$, 要最大化$b_i$就要最大化$a_i$,又因为k+1不整除$c_i$有$a_i = \lceil \frac{c_i}{k+1}\rceil = \lfloor \frac{c_i}{k+1}\rfloor + 1$

由于对于每个$c_i$$c_i/(k+1)$有sqrt种取值,总复杂度$n^2\sqrt c$

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
#define MAXN 27
#define int long long
int n;
ll c[MAXN];
ll mx = 0;
int work( int a , int x , int c ) {
return c - a * ( x - 1 ) >= 0 ? ( x - 2 ) * a + min( a , c - ( x - 1 ) * a ) : 0;
}
signed main() {
cin >> n;
for( int i = 1 ; i <= n ; ++i ) scanf("%lld",&c[i]) , mx = max( mx , c[i] );
ll res = 0;
for( ll k = 2 , r , s ; k <= mx + 1 ; k = r + 1 ) { // 这里其实是 k + 1
r = 0x3f3f3f3f3f3f3f3f , s = 0;
for( int i = 1 ; i <= n ; ++ i ) {
int a = c[i] / ( k );
s += max( work( a , k , c[i] ) , work( a + 1 , k , c[i] ) );
if( c[i] / k ) r = min( r , c[i] / ( c[i] / k ) );
}
res = max( res , s );
}
cout << res << endl;
}

小D与计算

题目链接

提答

Task1

取反,左移63位再右移63位没了

Task2

a + b = ( a ^ b ) + ( a & b ) << 1

相当于拆成进位和不进位

每一轮是三步,最后一共190多步

Task3

直接调用前面的加法函数,右移后暴力判最低位,注意每次进位数压一下

Task4

相当于 d = x ^ y 后看最高位,用 | d >>1 ,d >>2 ,d >>4 …来把最高位后面全部变1,然后 d ^ ( d >>1 ) 就得到了只有最高位的1.

Task5 & Task6

它们鸽了

ZROI D6

今天有点自闭了啊~

蔡老板与公司

题目链接

首先喷一下,这题被某带佬爆出原题了。。

由于是括号匹配,十有八九是和栈有关的。

考虑维护一个栈,每加入一个字符把它和栈顶尝试匹配,然后把整个栈的hash值算一算。如果已经出现过了,说明我们得到了合法的括号序列,然后累加进hash表。

为啥呢? 如果出现了一个合法的括号序列,这个括号序列在栈里面显然是会被消没的。消没后的这个东西如果以前也出现过,说明中间夹的就是一段合法的括号序列。当然,有可能夹着几段,所以是累加。

感性理解一下吧QWQ

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
typedef pair<long long,long long> py;
#define mp make_pair
#define MAXN 1000006
const long long bs1=233,mod1=1926008173;
const long long bs2=2333,mod2=1926008179;
map<py,int> M;
long long hs1[MAXN],hs2[MAXN];
py get(int i,int c){
if( i ) return mp( hs1[i] = ( hs1[i-1] * bs1 + c ) % mod1 , hs2[ i ] = ( hs2[ i-1 ] * bs2 + c ) % mod2 );
return mp(0ll,0ll);
}
char str[MAXN];
int st[MAXN],tp,n;
int main ()
{
scanf("%s",str+1);
n=strlen(str+1);
long long ans=0;
M[make_pair(0ll,0ll)]++;
for( int i = 1 ; i <= n ; i++ ) {
int c = str[i] - 'a' + 1;
if( tp && st[tp] == c ) -- tp;
else st[ ++tp ] = c;
py tmp = get( tp , st[tp] );
ans += M[tmp]++;
}
printf("%lld",ans);
return 0;
}

蔡老板与豪宅

由于不会FWT 不会 FMT 先鸽着,学了再来做

蔡老板与宝藏

一个可做但是很难写的题。。随缘看

ZROI D7

今天真自闭了。。推T1两小时推不出没想到真实个O(松)。。dls的题确实毒瘤。。

首先考虑类似fft一样,对读入进去的数据进行一次Rader排序。

那么每一次操作就等价于对于前一半和后一半进行一次位运算。

然后压位,每32位压进一个unsigned int里面,进行操作时直接把前面一半和后面一半进行暴力一次操作,并且放进一个新的数组递归进行。

对于前2^16进行预处理,真实复杂度就会减少五层大概是$3^{n-5}$, 4e7可以跑QWQ。

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
// 你好松啊~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 2100000
typedef unsigned int ui;
int n , A[MAXN]; ui a[MAXN];
int rad[MAXN] , pre[MAXN];
int dfs1( int dep , ui x ) {
if( ! dep ) return x & 1;
return dfs1( dep - 1 , x & ( x >> ( 1 << dep - 1 ) ) ) + dfs1( dep - 1 , x | ( x >> ( 1 << dep - 1 ) ) ) + dfs1( dep - 1 , x ^ ( x >> ( 1 << dep - 1 ) ) );
}
int dfs2( int dep , ui* c ) {
if( dep == 5 ) return pre[ (*c & ( *c >> 16 )) & 65535 ] + pre[ (*c | ( *c >> 16 )) & 65535 ] + pre[ (*c ^ ( *c >> 16 )) & 65535 ];
ui *t = c + ( 1 << dep - 5 );
int res = 0;
for( int i = 0 ; i < ( 1 << dep - 6 ) ; ++ i ) t[i] = c[i] & c[i + (1 << dep - 6)] ;
res += dfs2( dep - 1 , t );
for( int i = 0 ; i < ( 1 << dep - 6 ) ; ++ i ) t[i] = c[i] | c[i + (1 << dep - 6)] ;
res += dfs2( dep - 1 , t );
for( int i = 0 ; i < ( 1 << dep - 6 ) ; ++ i ) t[i] = c[i] ^ c[i + (1 << dep - 6)] ;
res += dfs2( dep - 1 , t );
return res;
}
int main() {
cin >> n;
for( int i = 0 ; i < ( 1 << n ) ; ++ i ) scanf("%1d",&A[i]);
rad[0] = 0;
for( int i = 1 ; i < ( 1 << n ) ; ++ i )
rad[i] = ( rad[i >> 1] >> 1 ) | ( ( i & 1 ) << n - 1 );
for( int i = 0 ; i < ( 1 << n ) ; ++ i ) if( i < rad[i] )
swap( A[i] , A[rad[i]] );
for( int i = 0 ; i < ( 1 << n ) ; ++ i )
a[i >> 5] |= A[i] << ( i & 31 );
if( n <= 5 ) return printf( "%d\n",dfs1( n , * a ) ) , 0;
for( int i = 0 ; i < ( 1 << 16 ) ; ++ i ) pre[i] = dfs1( 4 , i );
printf( "%d\n",dfs2( n , a ) );
}

集合

如果考场上可以想到枚举个数就好了呢~

首先,考虑当最小差和最大差都枚举了的时候怎么做。

对选出的序列排序后差分一下,假设差分后是$x_{1…n}$,那么显然

$\sum x_i = mx , MIN x_i = mn$

然后发现这就是个方程啊!插板法一下就没了呢~

但是这样做瓶颈在于枚举个数。这样是$O(n^3)$的呢!

那么如果最开始就枚举最小差和个数呢?

由于枚举了最小差,个数不超过n/d

这是Onlog的!

假设最小差是$i$, 个数是$j$

此时我们要算的是$i \times \sum \Delta mx$

为了算最大差的和,只需要算所有的最大值和所有的最小值然后剪一下

枚举最小值是c,贡献值是

$\displaystyle\sum{c=1}^{n-(i-1)(j-1)} C{n-(i-1)(j-1)-c}^{j-1} \times c$

然而可以推出最大值贡献是(n+1)x - 最小值的和(我也不知道为啥)

剩下的再鸽会~


ZROI D8

自闭了。

随缘写。


ZROI D9

快乐链覆盖

zblzbl

一个比较裸的树形dp,但是有个问题是咋输出方案。。具体看题解吧。。码事不可能码的这辈子都不可能码的(🐦

考试直接30分暴力拆边直径走人

快乐线段树

结论题,具体看题解(

快乐KMP

 这题抽空一定写写(🐦

后缀树好题啊(


ZROI D10

这是最惨的一天。。

原本想连续十天rating单调递增。。结果最简单的一天翻车了。。。。。。

T1爆0太真实了(

普通LCP

题目链接

后缀间lcp。。裸height数组。。求出来后单调栈一下就没了

然而标算是后缀树(感觉没啥问题啊为啥我爆0了。。

1e6的话。。rmq能跑的吧。。

(🐦)

优秀的Tree

原题。。数组没开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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 400006
#define P 1000000007
typedef long long ll;

ll head[MAXN] , to[MAXN] , nex[MAXN] , cnt;
void ade( int u , int v ) {
to[++cnt] = v , nex[cnt] = head[u] , head[u] = cnt;
}
ll n,siz[MAXN],sum[MAXN];
ll c[MAXN];
ll res;
//siz 为 子树 大小 sum 为当前处理过 的 所有 颜色为 c 的 点的 子树 上 的点的个数
//res 为一个块里面的 选两个点 的个数
void dfs(ll u,ll fa){
siz[u] = 1;
ll last = sum[c[u]];
for( int i = head[u] ; i ; i = nex[i] ) {
ll v = to[i];
if( v == fa ) continue;
ll cur = sum[c[u]];
dfs(v,u);
siz[u] += siz[v];
ll sz = siz[v] - sum[c[u]] + cur; sz %= P;
res -= sz*(sz-1)/2 , res += P , res %= P;
}
sum[c[u]] = last + siz[u] , sum[c[u]] %= P;
}
ll J[MAXN];
int main() {
res = 0;
cin >> n;
J[0] = 1;for( int i = 1 ; i <= n ; ++ i ) J[i] = J[ i - 1 ] * i , J[i] %= P;
for (ll i = 1; i <= n; ++i) scanf("%lld", &c[i]);
for (ll i = 0; i < n - 1; ++i) {
static ll u, v;
scanf("%lld%lld", &u, &v);
ade( u , v ) , ade( v , u );
}
dfs(1, 1);
for (ll i = 1; i <= n; ++i)
if (sum[i]) res += n * (n - 1) / 2 , res -= (n - sum[i]) * (n - sum[i] - 1) / 2 , res %= P;
printf("%lld\n", res % P * 2 % P * J[n - 1] % P );
}

猛男splay

鸽~

文章作者: yijan
文章链接: https://yijan.co/2019/08/14/old91/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog