muti-university contest2

ACM

多校第二场

1003 cover

问至少几笔覆盖图的路径。
答案是\(max(\frac{d}{2}, 1)\), d表示的是奇数度数的节点的个数
我们将奇数度数的节点之间连一条边，使之能变成一笔画问题，然后得到欧拉路径之后将增加的边删去。
注意图可能会不连通， 因此要用并查集维护一下

感觉比较的套路？
Q：有向无环图可以求最小路径覆盖。那么怎么求解方案呢？

ac 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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxm = 5e5+5;
int d[maxn];
bool vis[maxm];
int to[maxm], nex[maxm];
int tot, head[maxn];
int fa[maxn];
int n, m;
vector<int> group[maxn];
vector<int> ans[maxn];
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    for(int i=0; i<=n; i++){
        fa[i] = i;
        group[i].clear();
        ans[i].clear();
    }
    memset(d, 0, sizeof(d));
    memset(vis, 0, sizeof(vis));
}
void add_edge(int u, int v){
    to[tot] = v;
    nex[tot] = head[u];
    head[u] = tot++;
}
int find_fa(int x){
    int a = x;
    while(x!=fa[x]) x = fa[x];
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void uni(int u, int v){
    int fau = find_fa(u);
    int fav = find_fa(v);
    if(fau!=fav){
        fa[fau] = fav;
    }
}
int s[maxm], top;
void dfs(int u){
    //每条边只要访问一次
    for(int i=head[u]; ~i; i=nex[i]){
        head[u] = i;
        int id = abs((i/2)+1);
        if(vis[id]) continue;
        int v = to[i];
        vis[id] = true;
        dfs(v);
        s[top++] = ((i&1)==1)?-(i/2+1):(i/2+1);
    }
}
int pos[maxn];
/*
9928 49 1342
*/
int main()
{
    ios::sync_with_stdio(false);
    //clock_t ss, t;
    //ss = clock();
    //freopen("1003.in", "r", stdin);
    //freopen("10033.out", "w", stdout);
    while(cin>>n>>m){
        int u, v;
        init();
        for(int i=0; i<m; i++){
            cin>>u>>v;
            add_edge(u, v);
            add_edge(v, u);
            d[u]++, d[v]++;
            uni(u, v);
        }
        for(int i=1; i<=n; i++) find_fa(i);
        for(int i=1; i<=n; i++){
            if(d[i]&1){
                group[find_fa(i)].push_back(i);
            }
        }
        int tot2 = 1;
        for(int i=1; i<=n; i++){
            if(fa[i] == i){
                if(group[i].size() == 0){
                    top = 0;
                    dfs(i);
                    bool flag = false;
                    while(top--){
                        ans[tot2].push_back(s[top]);
                        flag = true;
                    }
                    if(flag)
                        tot2++;
                }
                else{
                    top = 0;
                    int sz = group[i].size();
                    for(int j=0; j<sz; j+=2){
                        add_edge(group[i][j], group[i][j+1]);
                        add_edge(group[i][j+1], group[i][j]);
                    }
                    dfs(i);
                    int tot1=0;
                    bool flag = false;
                    for(int j=top-1; j>=0; j--){
                        if(s[j]>m||s[j]<-m) {
                            pos[tot1++] = j;
                        }
                    }
                    for(int j=0; j<tot1-1; j++){
                        for(int k=pos[j]-1; k>pos[j+1]; k--){
                            ans[tot2].push_back(s[k]);
                            flag = true;
                        }
                        if(flag)
                            tot2++;
                        flag = false;
                    }
                    for(int j=pos[tot1-1]-1; j>=0; j--){
                        ans[tot2].push_back(s[j]);
                        flag = true;
                    }
                    for(int j=top-1; j>pos[0]; j--){
                        ans[tot2].push_back(s[j]);
                        flag = true;
                    }
                    if(flag)
                        tot2++;
                }
            }
        }
        cout<<tot2-1<<endl;
        int sz = 0;
        for(int i=1; i<tot2; i++){
            sz = ans[i].size();
            cout<<sz;
            for(int j=0; j<sz; j++){
                cout<<" "<<ans[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}
/*
4 6
1 2
2 4
4 3
3 1
2 3
4 1
4
2
1 2
3 4
4 2
1 2
3 2
1897 -16372
*/

1005 Hack it

构造题，涉及到数论的知识，感觉我和大佬之间的差距就那么大.jpg
听说是原题

ac code

1006 Matrix

感觉看题解的时候，推公式的时候好麻烦啊

1007 naive operation

因为区间更新的时候，每一个点的权值都不一样，因此不能使用第三类树状数组进行相应的更新。
线段树维护的是b[i]的属性
原code

ac 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
typedef long long ll;
typedef long long ll;
int n, q;
int a[maxn], b[maxn];
struct Node {
    int minx, valb, sum_zero, lazy;
}node[maxn*4];
void push_up(int rt, int l, int r){
    node[rt].minx =min(node[ls].minx, node[rs].minx);
    node[rt].sum_zero = node[ls].sum_zero+node[rs].sum_zero;
}
void push_down(int rt, int l, int r){
    node[ls].lazy += node[rt].lazy;
    node[rs].lazy += node[rt].lazy;
    node[ls].minx -= node[rt].lazy;
    node[rs].minx -= node[rt].lazy;
    node[rt].lazy = 0;
    return;
}
void build(int rt, int l ,int r){
    node[rt].lazy = node[rt].sum_zero = 0;
    if(l == r){
        node[rt].minx = node[rt].valb = b[l];
        return ;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    push_up(rt, l, r);
}
void update(int rt, int l, int r, int ql ,int qr){
    if(l>r) return;
    if(node[rt].minx>1&&l == ql&&r == qr){
        node[rt].lazy += 1;
        node[rt].minx -= 1;
        return ;
    }
    if(l == r&&node[rt].minx == 1){
        node[rt].sum_zero += 1;
        node[rt].minx = node[rt].valb;
        node[rt].lazy = 0;
        return;
    }
    if(node[rt].lazy>0) push_down(rt, l, r);
    if(mid>=qr) update(ls, l, mid, ql, qr);
    else if(ql>mid) update(rs, mid+1 ,r, ql, qr);
    else{
        update(ls, l, mid, ql, mid);
        update(rs, mid+1, r, mid+1, qr);
    }
    push_up(rt, l, r);
}
ll query(int rt, int l, int r, int ql, int qr){
    if(l>r) return 0;
    if(l == ql&&r == qr) return node[rt].sum_zero;
    if(node[rt].minx==0) update(rt, l, r, ql, qr);
    if(qr<=mid){
        return query(ls, l, mid, ql, qr);
    }
    else if(ql>mid){
        return query(rs, mid+1, r, ql, qr);
    }
    else{
        return query(ls, l, mid, ql, mid)+query(rs, mid+1, r, mid+1, qr);
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>q){
        for(int i=1; i<=n; i++) cin>>b[i];
        char op[10];
        //cout<<"haha"<<endl;
        build(1, 1, n);
        //cout<<"keke"<<endl;
        int l, r;
        for(int i=0; i<q; i++){
            cin>>op>>l>>r;
            if(op[0] == 'a'){
                update(1, 1, n, l, r);
            }
            else{
                cout<<query(1, 1, n, l, r)<<endl;
            }
        }
    }
    return 0;
}

Hack it

构造题，涉及到数论的题目

题解

ac 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e3+10;
bool ans[maxn][maxn];
int n, m;
const int p = 47;
int main()
{
    ios::sync_with_stdio(false);
    memset(ans, 0, sizeof(ans));
    //cout<<"haha"<<endl;
    for(int i=0; i<p; i++){
        for(int j=0; j<p; j++){
            for(int k=0; k<p; k++){
                ans[i*p+j][k*p+(j*k+i)%p] = true;
            }
        }
    }
    cout<<2000<<endl;
    for(int i=0; i<2000; i++){
        for(int j=0; j<2000; j++){
            if(ans[i][j])
                cout<<1;
            else cout<<0;
        }
        cout<<endl;
    }
    return 0;
}

Matrix

计数类dp,公式很难推啊

未解决的问题

本文标题:muti-university contest2

文章作者:Babydragon

发布时间:2018-07-25, 21:45:29

最后更新:2018-07-27, 13:58:45

原始链接:http://baolintian.github.io/2018/07/25/muti-university-contest2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 1003 cover
    1. 1.1. ac code
  2. 2. 1005 Hack it
    1. 2.1. ac code
  3. 3. 1006 Matrix
  4. 4. 1007 naive operation
    1. 4.1. ac code
  5. 5. Hack it
    1. 5.1. 题解
    2. 5.2. ac code
  6. 6. Matrix
  7. 7. 未解决的问题
{{ live2d() }}