Yijan's Blog HomeArchives
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] - kd_i + S_{k} ) - S_i + id_i + d_i$

$dp[t][j-1] - td_i + S_{t} < dp[p][j-1] - pd_i + 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与字符串

题目链接

首先，这个串肯定是长成这样的：

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

那么，假设前面循环出现的段每段有$a_i$个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/old91/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！
笔记