代码堆

ACM

以后写的代码都扔到这里面吧，方便索引

loj三道有上下界的模板题

可以直接到loj上面去看

bzoj 1997

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
const int maxm = 1e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int u[maxn], v[maxn];
int low[maxn], dfn[maxn], cnt;
int tot, head[maxn];
int cur[maxn];
int pos[maxn];
int scc, belong[maxn];
int uu[maxn], vv[maxn];
bool instack[maxn];
int sta[maxn], top;
void init(){
    tot=0, cls(head, -1);
    cnt=0, cls(low, 0), cls(dfn, 0);
    scc=0;
    cls(instack, 0);
    top=0;
}
struct Node{
    int v, next;
}node[maxm<<2];
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next=head[u],head[u]=tot++;
}
bool in(int x1, int y1, int x2, int y2){
    if(x2>x1&&x2<y1&&y2>y1) return true;
    if(x2<x1&&y2>x1&&y2<y1) return true;
    return false;
}
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    instack[x] = true;
    sta[top++]=x;
    for(int i=head[x]; ~i; i=node[i].next){
        int y=node[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=  min(low[x], low[y]);
        }
        else if(instack[y]) low[x]=  min(low[x], dfn[y]);
    }
    if(low[x] == dfn[x]){
        int id;
        scc++;
        do{
            id=sta[--top];
            instack[id] = false;
            belong[id] = scc;
        }while(id!=x);
    }
}
bool judge(){
    inc(i, 1, n){
        if(belong[i] == belong[i+n]) return false;
    }
    return true;
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        init();
        inc(i, 1, m) scanf("%d%d", &u[i], &v[i]);
        inc(i ,1, n) scanf("%d", &cur[i]);
        inc(i, 1, n) pos[cur[i]] = i;
        if(m>3*n+6) {puts("NO"); continue;}
        int tot_edge=0;
        inc(i, 1, m){
            int x=pos[u[i]], y=pos[v[i]];
            if(x>y) swap(x, y);
            if(y-x==1||(x==1&&y==n)) continue;
            uu[++tot_edge]=x, vv[tot_edge] = y;
        }
//        for(int i=1; i<=tot_edge; i++){
//            cout<<uu[i]<<" "<<vv[i]<<endl;
//        }
        //i表示在内部，i+n表示在外部
        for(int i=1; i<=tot_edge; i++){
            for(int j=i+1; j<=tot_edge; j++){
                if(in(uu[i], vv[i], uu[j], vv[j])){
                    add_edge(i, j+n);
                    add_edge(i+n, j);
                    add_edge(j, i+n);
                    add_edge(j+n, i);
                }
            }
        }
        for(int i=1; i<=n*2; i++){
            if(!dfn[i]) tarjan(i);
        }
        if(judge())puts("YES");
        else puts("NO");
    }
    return 0;
}
/*
2
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5
*/

poj 3417

树上差分，在节点处记录差分的值，然后dfs递归上去。
这个思想还是很神奇的。
若x，y有一条附加边，则dif[x]++，dif[y]++，dif[lca(x,y)]-=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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int head[maxn], tot;
struct Node{
    int v, next;
}node[maxn<<1];
int diff[maxn];
int cover[maxn];
int f[maxn][20];
int d[maxn];
bool vis[maxn];
void init(){
    tot=0, cls(head, -1);
    cls(diff, 0), cls(cover, 0);
    cls(d, 0);
    cls(vis, 0);
}
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next=head[u],head[u]=tot++;
}
void bfs(int s){
    d[s]=1;
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=head[u]; ~i; i=node[i].next){
            int v=node[i].v;
            if(vis[v]) continue;
            d[v] = d[u]+1;
            f[v][0] = u;
            for(int j=1; j<=19; j++){
                f[v][j] = f[f[v][j-1]][j-1];
            }
            q.push(v);
        }
    }
}
int lca(int u, int v){
    if(d[u]<d[v]) swap(u, v);
    for(int i=18; i>=0; i--){
        if(d[f[u][i]]>=d[v]) u=f[u][i];
    }
    if(u == v)return u;
    for(int i=18; i>=0; i--){
        if(f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    }
    return f[u][0];
}
int dfs(int s, int fa){
    cover[s] = diff[s];
    for(int i=head[s]; ~i;i=node[i].next){
        int v=node[i].v;
        if(v == fa) continue;
        cover[s] += dfs(v, s);
    }
    return cover[s];
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int u, v;
        init();
        inc(i ,1, n-1){
            scanf("%d%d", &u, &v);
            add_edge(u ,v);
            add_edge(v, u);
        }
        bfs(1);
        inc(i ,1, m){
            scanf("%d%d", &u, &v);
            diff[u]++, diff[v]++, diff[lca(u, v)]-=2;
        }
        dfs(1, -1);
        int ans = 0;
        //for(int i=1; i<=n; i++) cout<<i<<" "<<cover[i]<<endl;
        
        for(int i=1; i<=n; i++){
            if(cover[i] == 0&&i!=1) ans+=m;
            if(cover[i] == 1) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
4 2
1 2
1 4
2 3
3 4
2 4
*/

bzoj 2791

注意dfs预处理lca的d[]时枚举的顺序，
应该先枚举深度，然后枚举节点！！！

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 5e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, q;
int nex[maxn];
int pos[maxn];
int vis[maxn];
int scc;
int root[maxn];
int on_ring[maxn];
int sz[maxn];
int d[maxn];
int f[maxn][21];
void dfs(int u){
    vis[u] = scc;
    int v=nex[u];
    if(vis[v] == scc){
        int idx=1;
        for(int i=u; idx==1||i!=u; i=nex[i]){
            pos[i] = idx++;
            on_ring[i] = scc;
            root[i] = i;
            d[i] = 1;
        }
        sz[scc] = idx-1;
        return ;
    }
    else if(!vis[v])dfs(v);
    if(!on_ring[u]){
        d[u] = d[v]+1;
        f[u][0] = v;
        root[u] = root[v];
    }
}
void init_lca(){
    for(int j=1; j<=19; j++){
        for(int i=1; i<=n; i++){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}
int lca(int u, int v){
    if(d[u]<d[v]) swap(u, v);
    for(int i=19; i>=0; i--){
        if(d[f[u][i]]>=d[v]) u=f[u][i];
    }
    if(u == v) return u;
    for(int i=19; i>=0; i--){
        if(f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    }
    return f[u][0];
}
int dis(int x, int y, int z){
    return (y-x+z)%z;
}
void query(int u, int v){
    int fx=root[u], fy=root[v];
    if(on_ring[fx]!=on_ring[fy]){
        printf("-1 -1\n");
        return ;
    }
    if(fx == fy){
        int fa = lca(u, v);
        //cout<<"father "<<fa<<endl;
        printf("%d %d\n", d[u]-d[fa], d[v]-d[fa]);
        return ;
    }
    int x1= d[u]-1+dis(pos[fx], pos[fy], sz[on_ring[fx]]), y1=d[v]-1;
    int x2=d[u]-1, y2 = d[v]-1+dis(pos[fy], pos[fx], sz[on_ring[fy]]);
    if(max(x1, y1)!=max(x2, y2)){
        if(max(x1, y1)<max(x2, y2)){
            printf("%d %d\n", x1, y1);
        }
        else printf("%d %d\n", x2, y2);
        return ;
    }
    if(min(x1, y1)!=min(x2, y2)){
        if(min(x1, y1)<min(x2, y2)){
            printf("%d %d\n", x1, y1);
        }
        else printf("%d %d\n", x2, y2);
        return ;
    }
    printf("%d %d\n", max(x1, y1), min(x1, y1));
}
int main()
{
    scanf("%d%d", &n, &q);
    inc(i, 1, n) scanf("%d", &nex[i]);
    inc(i, 1, n) if(!vis[i]) ++scc, dfs(i);
    init_lca();
//    for(int i=1; i<=n; i++){
//        cout<<i<<" "<<root[i]<<" "<<f[i][0]<<" "<<sz[i]<<endl;
//    }
    int u, v;
    inc(i, 1, q){
        scanf("%d%d", &u, &v);
        query(u, v);
    }
    return 0;
}
/*
12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5
*/

最基础的并查集

写什么错什么，范围开小了。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1000000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int x[maxn], y[maxn];
int xx[maxn], yy[maxn];
int dx[maxn], dy[maxn];
int fa[maxn];
int rela[maxn];
int temp[maxn<<1];
int get(int x) {return x==fa[x]?x:fa[x]=get(fa[x]);}
int main()
{
    int _;
    _=readint();
    while(_--){
        n=readint();
        inc(i, 1, n) x[i]=readint(), y[i]=readint(),rela[i]=readint(), temp[i*2-1]=x[i], temp[i*2]=y[i];
        sort(temp+1, temp+2*n+1);
        //int sz = unique(temp+1, temp+1+2*n)-(temp+1);
        inc(i ,1, n){
            dx[i] = lower_bound(temp+1, temp+1+2*n, x[i])-temp;
            dy[i] = lower_bound(temp+1, temp+1+2*n, y[i])-temp;
        }
        for(int i=1; i<=n*2; i++) fa[i] = i;
        bool flag = true;
        for(int i=1; i<=n; i++){
            if(rela[i] == 1){
                int fau=get(dx[i]), fav=get(dy[i]);
                if(fau != fav)
                    fa[fau] = fav;
            }
        }
        for(int i=1; i<=n; i++){
            if(rela[i] == 0){
                if(get(dx[i]) == get(dy[i])) {flag = false; break;}
            }
        }
        if(!flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

xdoj1368

直接模拟就行了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll h[maxn];
int tot=0;
ll hh[maxn], preh[maxn];
int main()
{
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++) scanf("%lld", &h[i]);
        hh[1]=h[1], preh[1]=0;
        ll pre=h[1];
        tot=1;
        for(int i=2; i<=n; i++){
            if(h[i]>=pre) pre=h[i], hh[tot]=pre;
            else{
                int j=i+1;
                if(j>n) continue;
                for( ; j<=n; j++){
                    if(h[j]>h[j-1]) break;
                }
                preh[++tot]=h[j-1];
                pre = h[j];
                hh[tot]=h[j];
                i=j-1;
            }
        }
        ll ans =0 ;
        for(int i=1; i<=tot; i++){
            ans += (hh[i]-preh[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

bzoj 太鼓达人

因为一个节点入度和出度都是2,，所以第一个答案一定是(1<<k), 第二个答案要在第一个的基础上进行搜索，并不是字典序最小
最后的串只要输出M位就行了，实际上长度为(1<<k)+(k-1)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, k;
bool vis[1<<12];
int ans[1<<12];
bool dfs(int x, int t){
    //cout<<x<<" "<<t<<endl;
    if(vis[x]) return false;
    if(t==(1<<k)) return true;
    ans[t] = x&1;
    vis[x] = true;
    if(dfs(((x^(((x>>(k-1))&1)<<(k-1)))<<1), t+1)) return true;
    if(dfs(((x^(((x>>(k-1))&1)<<(k-1)))<<1)|1, t+1)) return true;
    vis[x] = false;
    return false;
}
int main()
{
    k=readint();
    int m=(1<<k);
    printf("%d ", (1<<k));
    dfs(0, 1);
    for(int i=1; i<k; i++)printf("0");
    for(int i=1; i<=(1<<k)-(k-1); i++) printf("%d", ans[i]);
    printf("\n");
    return 0;
}

bzoj杀人游戏

注意有个要特判，不能只统计入度为0的顶点
例如：
3 2
3 2
1 2
我们只要知道1或者3，就能确认全局了
注意check函数条件

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100000+10;
const int maxm = 300000;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int tot, head[maxn];
struct Node{
    int v, next;
}node[maxm<<1];
int tot1, head1[maxn];
struct Node1{
    int v, next;
}node1[maxm<<1];
int cnt, dfn[maxn], low[maxn];
int bl[maxn], scc;
bool instack[maxn];
int top, sta[maxn];
int in[maxn];
map < ll, int > mp2;
int ru[maxn];
int sz[maxn];
void init(){
    tot=0, cls(head, -1);
    tot1=0, cls(head1, -1);
    cnt=0, cls(dfn, 0), cls(low, 0);
    cls(bl, 0), scc=0;
    cls(instack, 0);
    top=0;
    cls(ru, 0);
    mp2.clear();
}
void add_edge(int u, int v){
    node[tot].v=v, node[tot].next=head[u],head[u]=tot++;
}
void add_(int u, int v){
    node1[tot1].v=v, node1[tot1].next=head1[u],head1[u]=tot1++;
}
void tarjan(int u, int fa){
    dfn[u] = low[u] = ++cnt;
    instack[u]=true;
    sta[top++]=u;
    for(int i=head[u];~i; i=node[i].next){
        int v=node[i].v;
        if(!dfn[v]){
            tarjan(v, u);
            low[u]=  min(low[u], low[v]);
        }
        else if (instack[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]){
        scc++;
        int id;
        do{
            id=sta[--top];
            instack[id]  =false;
            bl[id] = scc;
            sz[scc]++;
        }while(id!=u);
    }
}
bool check(int x)
{
    if (ru[x]!=0 || sz[x]!=1) return 0;
    for (int i=head1[x]; ~i; i=node1[i].next)
        if (ru[node1[i].v]==1) return 0;
    return 1;
}
bool chong2(int u, int v){
    if(mp2[u*maxn+v]) return false;
    mp2[u*maxn+v] =1;
    return true;
}
int main()
{
    n=readint(), m=readint();
    init();
    int u, v;
    for(int i=1; i<=m; i++){
        u=readint(), v=readint();
        add_edge(u, v);
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i, -1);
    int ans = 0;
    for(int i=1; i<=n; i++){
        u=bl[i];
        for(int j=head[i]; ~j; j=node[j].next){
            v=bl[node[j].v];
            if(u == v) continue;
            if(!chong2(u, v)) continue;
            add_(u, v);
            ru[v]++;
        }
    }
    //for(int i=1; i<=n; i++) cout<<i<<" "<<bl[i]<<" "<<ru[i]<<endl;
    for(int i=1; i<=scc; i++) if(ru[i] == 0) ans++;
    for(int i=1; i<=scc; i++){
        if(check(i)){ans--; break;}
    }
    printf("%.6f\n", 1.0*(n-ans)/n);
    return 0;
}

poj3468

2-sat

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
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000*2+100;
struct TwoSAT
{
    int n;
    vector<int> G[maxn*2];//存图
    int S[maxn*2],c;//dfs中的栈
    bool mark[maxn*2];
    bool dfs(int x)
    {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }
    void init(int n)
    {
        this->n=n;
        for(int i=0;i<2*n;i++) G[i].clear();
        memset(mark,0,sizeof(mark));
    }
    //xval表示的是偏移
    void add_clause(int x,int xval,int y,int yval)
    {
        x=x*2+xval;
        y=y*2+yval;
        G[x].push_back(y);
    }
    bool solve()
    {
        for(int i=0;i<2*n;i+=2)
        if(!mark[i] && !mark[i+1])
        {
            c=0;
            if(!dfs(i))
            {
                while(c>0) mark[S[--c]]=false;
                if(!dfs(i+1)) return false;
            }
        }
        return true;
    }
}TS;
int n, m;
int main(){
    while(~scanf("%d%d", &n, &m)&&n+m!=0){
        TS.init(2*n);
        int u, v;
        TS.add_clause(0, 1, 0, 0);
        TS.add_clause(1, 0, 1, 1);
        for(int i=1; i<n; i++){
            u=2*i, v=2*i+1;
            TS.add_clause(u, 0, v, 1);
            TS.add_clause(u, 1, v, 0);
            TS.add_clause(v, 0, u, 1);
            TS.add_clause(v, 1, u, 0);
        }
        char op1, op2;
        for(int i=1; i<=m; i++){
            scanf("%d%c %d%c", &u, &op1, &v, &op2);
            if(op1=='h') u=2*u+1;
            else u = u*2;
            if(op2 == 'h') v=2*v+1;
            else v=v*2;
            TS.add_clause(u, 1, v, 0);
            TS.add_clause(v, 1, u, 0);
        }
        if(!TS.solve()) {printf("bad luck\n");continue;}
        for(int i=2; i<2*n; i+=2){
            if(TS.mark[2*i]) printf("%dw ", i/2);
            if(TS.mark[(i+1)*2]) printf("%dh ", i/2);
        }
        printf("\n");
    }
}

xdoj 诺爷信号

注意一个节点的入度全部为0才能访问

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, k;
struct Node{
    int v, next;
}node[maxn];
int tot, head[maxn];
int ru[maxn];
bool can[maxn];
int score[11];
int ans;
bool has[1<<12];
void init(){
    tot=0, cls(head, -1);
    cls(ru, 0);
    ans= 0;
    cls(can, 0);
    cls(has, 0);
}
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next=head[u],head[u]=tot++;
}
struct Node1{
    int day;
    bool vis[11];
    short ru[11];
    int ans;
    Node1(){
        day=0, cls(vis, 0), ans=0;
    }
};
Node1 v;
int id;
void solve(){
    queue<Node1> q;
    while(!q.empty()) q.pop();
    //for(int i=1; i<=10; i++) cout<<i<<" "<<can[i]<<endl;
    for(int i=1; i<=10 ;i++) if(can[i]){
        cls(v.vis, 0);
        for(int j=1; j<=10; j++) v.ru[j]=ru[j];
        for(int j=head[i]; ~j; j=node[j].next) {
            v.ru[node[j].v]--;
            if(v.ru[node[j].v]==0) v.vis[node[j].v]=true;
        }
        for(int j=1; j<=10; j++) if(i!=j&&can[j]) v.vis[j] = true;
        v.day=1;
        v.ans=score[i];
        q.push(v);
    }
    while(!q.empty()){
        Node1 u=q.front();
        q.pop();
        if(u.day<=k) ans = max(ans, u.ans);
        if(u.day>=k) continue;
        id=0;
        for(int i=1; i<=10; i++) if(u.vis[i]) id+=(1<<i);
        if(has[id]) continue;
        has[id] = true;
        for(int i=1; i<=10; i++){
            if(u.vis[i]){
                cls(v.vis, 0);
                for(int j=1; j<=10; j++) v.ru[j] = u.ru[j];
                for(int j=head[i]; ~j; j=node[j].next){
                    v.ru[node[j].v]--;
                    if(v.ru[node[j].v]==0) v.vis[node[j].v]=true;
                }
                for(int j=1; j<=10; j++) if(i!=j&&u.vis[j]) v.vis[j] = true;
                v.ans = u.ans+score[i];
                v.day = u.day+1;
                q.push(v);
            }
        }
    }
}
int main()
{
    while(~scanf("%d", &m)){
        int u, v;
        init();
        for(int i=1; i<=m; i++) scanf("%d%d", &u,&v), add_edge(u, v), ru[v]++;
        for(int i=1; i<=10; i++) if(ru[i] == 0) can[i] = true;
        for(int i=1; i<=10; i++) scanf("%d", &score[i]);
        scanf("%d", &k);k/=3;
        solve();
        if(ans>=60) printf("%d\n", ans);
        else printf("I chose to die\n");
    }
    return 0;
}
/*
2
1 3
3 4
1 20 1 100 20 20 20 20 20 20
9
*/

ecl final sos

博弈论思维
必胜态为存在ss的状态，我一开始就是准备最朴素的寻找s_s, os, so,发现不能这样思考
n为偶数，且>=16后手胜，我一开始想的是>=14，结果错了
想这样的例子：
__os => __o_so,这样就破坏了后手必胜

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int main()
{
    int _;
    scanf("%d", &_);
    int kase = 1;
    while(_--){
        scanf("%d", &n);
        if(n&1&&n>=7) printf("Case #%d: Panda\n", kase++);
        else if(n%2==0&&n>=16) printf("Case #%d: Sheep\n", kase++);
        else printf("Case #%d: Draw\n", kase++);
    }
    return 0;
}

ecl final 替罪羊

按照题意贪心的进行取就行了，我个人感觉题目给的方差的式子没有什么卵用23333
这种先放一部分，然后贪心的放一个，使得贡献最大的思想挺重要的。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[maxn];
double sum;
struct Node{
    int num;
    double now;
    double nex;
    double fen;
    Node(int _fen, int number, double ave){
        fen = _fen;
        num = number;
        now = (ave-sum)*(ave-sum)*number;
        nex = now - (fen/(number+1)-sum)*(fen/(number+1)-sum)*(number+1);
    }
    bool operator < (const Node &b) const {
        return nex<b.nex;
    }
};
priority_queue<Node> pq;
int main()
{
    int _;
    scanf("%d", &_);
    int kase = 1;
    while(_--){
        sum = 0;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]), sum+=a[i];
        sum /= (1.0*m);
        while(!pq.empty()) pq.pop();
        for(int i=1; i<=n; i++) pq.push(Node(a[i], 1, a[i]));
        int left = m-n;
        while(left--){
            Node temp = pq.top();
            pq.pop();
            pq.push(Node(temp.fen, temp.num+1, temp.fen/(temp.num+1)));
        }
        double ans = 0;
        for(int i=0; i<n; i++){
            Node temp = pq.top();
            pq.pop();
            ans += temp.now;
        }
        ans /= m;
        printf("Case #%d: %.13lf\n", kase++, ans);
    }
    return 0;
}

master of sequence

遇到的坑点就是数组没有初始化。。。

给定一个长度为n的数组，要求每一次选择长度3~5的长度并且-1，最后使得整个数组变成0
问能否这样操作，使得能最后数组全部变成0

题解

首先[3, 5]可以变成>=3, 因为>=6的数组都可以拆成3， 4， 5的和，6=3+3， 7=3+4，，，
先要对原来的数组进行差分，然后就不断的取一个非减的差分数组，减去头

新的一道题目

给定一个数组，每次可以减去一个连续的长度>=3的数组，使得最后的数组变成0
若不存在，输出-1， 否则输出最小的步数：

ans: 在这个统计的时候加一个答案进行统计就行了

解答

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[maxn];
ll c[maxn];
int main()
{
    int _;
    int kase = 1;
    scanf("%d", &_);
    while(_--){
        scanf("%d", &n);
        a[0] = 0;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        a[n+1] = 0;
        for(int i=1; i<=n+1; i++) c[i] = a[i]-a[i-1];
        bool flag = true;
        int p=0;
        int ans = 0;
        for(int i=1; i<=n; i++){
            while(c[i]>0){
                //p=i+1;
                int pre=c[i];
                if(!p) p=i+1;
                while(p<=n+1&&c[p]>=0) p++;
                if(p>n+1) {flag=false; break;}
                if(p-i<3) {flag=false; break;}
                //p相当于是一个哨兵，不包含在-1的序列中
                c[p]+=c[i], c[i]=0;
                //cout<<"1--"<<i<<" "<<p<<" "<<c[i]<<" "<<c[p]<<endl;
                if(c[p]>0) c[i]=c[p], c[p]=0;
                ans += (pre-c[i]);
                //cout<<"2--"<<c[i]<<" "<<c[p]<<endl;
            }
            if(!flag) break;
        }
        if(flag) printf("Case #%d: Yes %d\n", kase++, ans);
        else printf("Case #%d: No\n", kase++);
    }
    return 0;
}
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[maxn];
ll c[maxn];
int main()
{
    int _;
    int kase = 1;
    scanf("%d", &_);
    while(_--){
        scanf("%d", &n);
        a[0] = 0;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        a[n+1] = 0;
        for(int i=1; i<=n+1; i++) c[i] = a[i]-a[i-1];
        bool flag = true;
        int p=0;
        for(int i=1; i<=n; i++){
            while(c[i]>0){
                //p=i+1;
                if(!p) p=i+1;
                while(p<=n+1&&c[p]>=0) p++;
                if(p>n+1) {flag=false; break;}
                if(p-i<3) {flag=false; break;}
                //p相当于是一个哨兵，不包含在-1的序列中
                c[p]+=c[i], c[i]=0;
                //cout<<"1--"<<i<<" "<<p<<" "<<c[i]<<" "<<c[p]<<endl;
                if(c[p]>0) c[i]=c[p], c[p]=0;
                //cout<<"2--"<<c[i]<<" "<<c[p]<<endl;
            }
            if(!flag) break;
        }
        if(flag) printf("Case #%d: Yes\n", kase++);
        else printf("Case #%d: No\n", kase++);
    }
    return 0;
}

uva

贪心的取两次就行了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 5e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[maxn];
int tot1, tot2;
int pos[maxn];
int neg[maxn];
bool cmp1(int a, int b) {return a<b;}
bool cmp2(int a, int b){return a>b;}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d", &n);
        tot1 = tot2 = 0;
        for(int i=1; i<=n; i++) {
            scanf("%d", &num[i]);
            if(num[i]>0) pos[tot1++] = num[i];
            else neg[tot2++] = -num[i];
        }
        sort(pos, pos+tot1, cmp1);
        sort(neg, neg+tot2, cmp1);
        int ans1 = 1;
        int pre = pos[0];
        for(int i=0; i<tot2; i++){
            i=lower_bound(neg, neg+tot2, pre)-neg;
            if(i==tot2) break;
            pre = neg[i];
            ans1++;
            int j=lower_bound(pos, pos+tot1, pre)-pos;
            if(j == tot1) break;
            ans1++;
            pre = pos[j];
        }
        int ans2=1;
        pre = neg[0];
        for(int i=0; i<tot1; i++){
            i=lower_bound(pos, pos+tot1, pre)-pos;
            if(i==tot1) break;
            pre = pos[i];
            ans2++;
            int j=lower_bound(neg, neg+tot2, pre)-neg;
            if(j == tot2) break;
            ans2++;
            pre = neg[j];
        }
        printf("%d\n", max(ans1, ans2));
    }
    return 0;
}

uva 10047

按照题意进行bfs就行了，记录的状态比较的多，注意转移

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 30;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
char mp[maxn][maxn];
bool vis[maxn][maxn][6][6];
int dis[maxn][maxn][6][6];
int sr, sc, tr, tc;
int ans = inf;
struct Node{
    int x, y, dir, cor, ans;
};
void init(){
    ans = inf;
    cls(vis, 0);
}
bool judge(int x, int y, int dir, int cor){
    if(x<=0||x>n||y<=0||y>m) return false;
    if(vis[x][y][dir][cor]) return false;
    if(mp[x][y] == '#') return false;
    return true;
}
void bfs(int x, int y){
    queue<Node> q;
    while(!q.empty()) q.pop();
    q.push(Node{x, y, 0, 0});
    //0朝北，1朝东，2朝南，3朝西
    //0 绿， 1 黑 ，2 red, 3 blue, 4 white
    while(!q.empty()){
        Node u = q.front();
        q.pop();
        int a=u.x, b=u.y, dir=u.dir, cor=u.cor;
        //cout<<a<<" "<<b<<" "<<dir<<" "<<cor<<" "<<u.ans<<endl;
        if(a==tr&&b==tc&&cor==0) {ans = min(ans, u.ans);break;}
        if(vis[a][b][dir][cor]) continue;
        vis[a][b][dir][cor] = true;
        if(dir == 0) {
            if(judge(a-1, b, dir, (cor+1)%5)) q.push(Node{a-1, b, dir, (cor+1)%5, u.ans+1});
            if(judge(a, b, 3, cor)) q.push(Node{a, b, 3, cor, u.ans+1});
            if(judge(a, b, 1, cor)) q.push(Node{a, b, 1, cor, u.ans+1});
        }
        else if(dir == 1){
            if(judge(a, b+1, dir, (cor+1)%5)) {q.push(Node{a, b+1, dir, (cor+1)%5, u.ans+1});}
            if(judge(a, b, 0, cor)) q.push(Node{a, b, 0, cor, u.ans+1});
            if(judge(a, b, 2, cor)) q.push(Node{a, b, 2, cor, u.ans+1});
        }
        else if(dir == 2){
            if(judge(a+1, b, dir, (cor+1)%5)) q.push(Node{a+1, b, dir, (cor+1)%5, u.ans+1});
            if(judge(a, b, 1, cor)) q.push(Node{a, b, 1, cor, u.ans+1});
            if(judge(a, b, 3, cor)) q.push(Node{a, b, 3, cor, u.ans+1});
        }
        else {
            if(judge(a, b-1, dir, (cor+1)%5)) q.push(Node{a, b-1, dir, (cor+1)%5, u.ans+1});
            if(judge(a, b, 2, cor)) q.push(Node{a, b, 2, cor, u.ans+1});
            if(judge(a, b, 0, cor)) q.push(Node{a, b, 0, cor, u.ans+1});
        }
    }
}
void pp(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) printf("%c", mp[i][j]);
        printf("\n");
    }
}
int main()
{
    int kase =1;
    while(~scanf("%d%d", &n, &m)&&n+m!=0){
        getchar();
        init();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                scanf("%c", &mp[i][j]);
                if(mp[i][j] == 'S') sr=i, sc=j;
                else if(mp[i][j] == 'T') tr=i, tc=j;
            }
            getchar();
        }
        //pp();
        bfs(sr, sc);
        if(kase>1) puts("");
        if(ans == inf) {
            printf("Case #%d\ndestination not reachable\n", kase++);
        }
        else printf("Case #%d\nminimum time = %d sec\n", kase++, ans);
    }
    return 0;
}

uva 10054

无向图的欧拉回路

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 60;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int G[maxn][maxn], d[maxn];
struct Node{
    int u, v;
};
vector<Node> ans;
void init(){
    cls(G, 0), cls(d, 0);
    ans.clear();
}
void euler(int u){
    for(int v=1; v<maxn; v++) if(G[u][v]){
        G[u][v]--, G[v][u]--;
        euler(v);
        ans.emplace_back(Node{u, v});
    }
}
int main()
{
    int _;
    int kase = 1;
    scanf("%d", &_);
    while(_--){
        init();
        scanf("%d", &n);
        int u, v;
        for(int i=0; i<n; i++) {
            scanf("%d%d", &u, &v);
            G[u][v]++, G[v][u]++, d[u]++, d[v]++;
        }
        bool flag = true;
        if(kase>1) puts("");
        for(int i=1; i<maxn; i++) if(d[i]&1) {flag = false; break;}
        if(!flag) {printf("Case #%d\nsome beads may be lost\n", kase++); continue;}
        euler(u);
        printf("Case #%d\n", kase++);
        for(int i=ans.size()-1; i>=0; i--){
            printf("%d %d\n", ans[i].u, ans[i].v);
        }
    }
    return 0;
}

uva 10905

这个排序的方式很骚啊

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
string s[55];
bool cmp(string a, string b){
    return a+b>b+a;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n){
        for(int i=0; i<n; i++) cin>>s[i];
        sort(s, s+n, cmp);
        for(int i=0; i<n; i++) cout<<s[i];
        cout<<"\n";
    }
    return 0;
}

uva 11100

要划分出最少的严格增的序列，并且要使每一个序列的个数尽量的平均
划分的过程中感觉用了分块的思想

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int num[maxn];
int mx = 0;
int vis[maxn];
int n;
void solve(){
    for(int i=0; i<mx; i++){
        for(int j=i; j<n; j+=mx){
            if(j!=i) printf(" ");
            printf("%d", num[j]);
        }
        printf("\n");
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(~scanf("%d", &n)&&n){
        cls(vis, 0);
        mx = 0;
        for(int i=0; i<n; i++){
            scanf("%d", &num[i]);
            vis[num[i]]++;
            mx = max(mx, vis[num[i]]);
        }
        sort(num, num+n);
        solve();
    }
    return 0;
}

poj 3802

我们小时候经常玩的东西
由两个视图，问最少需要多少这样的方格才能拼成？
我们尽量的使相等的方块抵消，然后不等的方格就要对答案进行累加

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[25], b[25];
int main()
{
    while(~scanf("%d%d", &n, &m)&&n+m!=0){
        int u;
        cls(a, 0), cls(b, 0);
        for(int i=1; i<=n; i++) scanf("%d", &u), a[u]++;
        for(int j=1; j<=m; j++) scanf("%d", &u), b[u]++;
        int ans = 0;
        for(int i=1; i<=20; i++){
            if(a[i]>=b[i]) ans += (i)*a[i];
            else ans += i*b[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

uva11134

行列拆开讨论
每一个点可以在一个区间内选择一个点，然后点不重叠
这里使用了贪心的思想
但是注意不能先按照左端点排序，再按右端点排序，然后尽量往左边放，比如，（1,1），（1,3），（2,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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int x, y, num;
}row[maxn], col[maxn];
bool cmp(Node a, Node b){
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
int ansx[maxn], ansy[maxn];
bool vis[maxn];
int main()
{
    while(~scanf("%d", &n)&&n){
        int x1, y1, x2, y2;
        for(int i=1; i<=n; i++) row[i].num = col[i].num = i;
        for(int i=1; i<=n; i++)
            {scanf("%d%d%d%d", &x1, &y1, &x2, &y2); row[i].x=x1, col[i].x=y1, row[i].y=x2, col[i].y=y2;}
        sort(row+1, row+n+1, cmp);
        sort(col+1, col+n+1, cmp);
        cls(vis, 0);
        bool flag = true;
        for(int i=1; i<=n; i++){
            int j;
            for(j=row[i].x; j<=row[i].y; j++){
                if(!vis[j]) {ansx[row[i].num]=j, vis[j] = true; break;}
            }
            if(j==(row[i].y+1)){flag = false;break;}
        }
        if(flag==false){printf("IMPOSSIBLE\n"); continue;}
        cls(vis, 0);
        for(int i=1; i<=n; i++){
            int j;
            for(j=col[i].x; j<=col[i].y; j++){
                if(!vis[j]) {ansy[col[i].num]=j, vis[j] = true; break;}
            }
            if(j==(col[i].y+1)){flag = false;break;}
        }
        if(flag==false){printf("IMPOSSIBLE\n"); continue;}
        for(int i=1; i<=n; i++) printf("%d %d\n", ansx[i], ansy[i]);
    }
    return 0;
}

codeforces round 510 div2 D

树状数组+前缀和
注意这道题有不在数组里面的数字的离散的映射， 这个我调了好久qaq
注意积累任意数在一个数组里面的映射的关系
BIT

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 100000000;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll t;
int a[maxn];
int id[maxn];
ll pre[maxn];
ll temp[maxn];
int c[maxn];
int sz;
int lowbit(int x){
    return x&(-x);
}
void add(int x, int val){
    while(x<sz) {
        c[x] += val;
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
unordered_set<ll> s;
unordered_map<ll, int> idd;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>t;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) pre[i] = pre[i-1]+a[i], temp[i] = pre[i];
    sort(temp+1, temp+1+n);
    sz = unique(temp+1, temp+1+n)-temp-1;
    //cout<<sz<<endl;
    for(int i=1; i<=n; i++){
        id[i] = lower_bound(temp+1, temp+sz+1, pre[i])-temp;
        idd[pre[i]] = id[i];
    }
//    for(int i=1; i<=n; i++){
//        cout<<id[i]<<" ";
//    }
//    cout<<endl;
//    for(int i=1; i<=n; i++){
//        add(id[i], 1);
//    }
    ll ans = 0;
    int tot = 0;
    for(int i=1; i<=n; i++){
        if(a[1]<t&&i==1) ans++;
        if(s.count(pre[i]-t)!=0&&i!=1){
            int index = idd[pre[i]-t];
            ans += (tot-query(index));
            if(pre[i]<t&&i!=1) ans++;
            //cout<<"in1 "<<ans<<endl;
        }
        else {
            int index = lower_bound(temp+1, temp+1+sz, pre[i]-t)-temp;
            if(index == 1) ans += tot;
            else if(index != sz+1)ans += (tot-query(index-1));
            if(pre[i]<t&&i!=1) ans++;
//            cout<<"haha"<<index<<endl;
//            cout<<tot<<" "<<query(index-1)<<endl;
//            cout<<"in2 "<<ans<<endl;
        }
        add(id[i], 1);
        s.insert(pre[i]);
        tot++;
    }
    cout<<ans<<endl;
}

虚树模板题 消耗战

建立有贡献的树形的结构进行dp就行了
教程

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 250000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int v, next;
    ll w;
}node[maxn<<1];
int tot, head[maxn];
int d[maxn];
int sz[maxn];
int topf[maxn];
int f[maxn][22];
int p[maxn];
ll mn[maxn];
int son[maxn];
int dfn[maxn], cnt;
vector<int> G[maxn];
int s[maxn], top;
int fa[maxn];
void init(){
    tot=0, cls(head, -1);
    cls(topf, 0);
}
void add_edge(int u, int v, int w){
    node[tot].v=v, node[tot].w=w, node[tot].next = head[u], head[u]=tot++;
}
void add_(int u, int v){
    G[u].push_back(v);
}
void dfs1(int u, int p){
    fa[u] = p;
    dfn[u] = ++cnt;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == p) continue;
        d[v] = d[u]+1;
        mn[v] = min(mn[u], node[i].w);
        f[v][0] = u;
        dfs1(v, u);
        //sz[u] += sz[v];
    }
}
int LCA(int u, int v){
    if(d[u]<d[v]) swap(u, v);
    for(int i=19; i>=0; i--){
        if(d[f[u][i]]>=d[v]) u=f[u][i];
    }
    if(u == v) return u;
    for(int i=19; i>=0; i--){
        if(f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    }
    return f[u][0];
}
void insert(int x) {
    if(top == 1) {s[++top] = x; return ;}
    int lca = LCA(x, s[top]);
    if(lca == s[top]) return ;
    while(top > 1 && dfn[s[top - 1]] >= dfn[lca]) add_(s[top - 1], s[top]), top--;
    if(lca != s[top]) add_(lca, s[top]), s[top] = lca;//
    s[++top] = x;
}
ll dp(int u){
    if(G[u].size() == 0) return mn[u];
    ll sum = 0;
    for(int i=0; i<G[u].size(); i++){
        int v=G[u][i];
        sum += dp(v);
    }
    G[u].clear();
    return min(sum, mn[u]);
}
bool cmp(int a, int b){
    return dfn[a]<dfn[b];
}
int id[maxn];
int main()
{
    while(~scanf("%d", &n)){
        int u, v, w, k;
        init();
        for(int i=0; i<n-1; i++){
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w), add_edge(v, u, w);
        }
        d[1]=1;
        mn[1] = (1ll<<60);
        //cout<<"in"<<endl;
        dfs1(1, 0);
        //dfs2(1, 1);
        for(int i=1; i<=19; i++){
            for(int j=1; j<=n; j++){
                f[j][i] = f[f[j][i-1]][i-1];
            }
        }
        //dfs2(1, 1);
       // cout<<"out"<<endl;
        scanf("%d", &m);
//        for(int i=1; i<=n; i++){
//            cout<<i<<" "<<mn[i]<<endl;
//        }
//        cout<<endl<<endl;
        while(m--){
            scanf("%d", &k);
            for(int i=0; i<k; i++) scanf("%d", &id[i]);
            sort(id, id+k, cmp);
            top=1;
            s[top] = 1;
            for(int i=0; i<k; i++) insert(id[i]);
            while(top>0){
                add_(s[top-1], s[top]);
                top--;
            }
            printf("%lld\n", dp(1));
        }
    }
    return 0;
}

bzoj 1001

最小割转化为对偶图之后求最短路
一类图的边有权，求边权的最小的和，使得目标的两点不连通的权值最小
这一类的问题都可以往最小割的方向想

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const int inf = 1e9;
struct Node{
    int v, next, w;
}node[maxn*3];
int minn = inf;
int N, M;
int tot, head[maxn];
int dist[maxn];
bool vis[maxn];
int cnt[maxn];
int end_pos;
void init(){
    memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w){
    node[tot].v=v,node[tot].w=w,node[tot].next=head[u],head[u]=tot++;
    node[tot].v=u,node[tot].w=w,node[tot].next=head[v],head[v]=tot++;
}
void build_graph(){
    scanf("%d%d",&N,&M); end_pos=2*(N-1)*(M-1)+1;
    int t;
    if(N==1){
        for(int i=1;i<M;++i){
            scanf("%d",&t);
            if(t<minn) minn=t;
        }
        return ;
    }
    else if(M==1){
        for(int i=1;i<N;++i){
            scanf("%d",&t);
            if(t<minn) minn=t;
        }
        return ;
    }
    for(int i=1;i<=end_pos;++i) dist[i]=inf;
    //横边
    for(int i=1;i<=2*(N-1)+1;i+=2)
        for(int j=1;j<M;++j){
            scanf("%d",&t);
            if(i==1) add_edge(j,0,t);
            else if(i==2*(N-1)+1) add_edge(end_pos-(M-j),end_pos,t);
            else add_edge((i-2)*(M-1)+j,(i-1)*(M-1)+j,t);
        }
    //纵边
    for(int i=1;i<2*(N-1)+1;i+=2)
        for(int j=1;j<=M;++j){
            scanf("%d",&t);
            if(j==1) add_edge(i*(M-1)+1,end_pos,t);
            else if(j==M) add_edge(i*(M-1),0,t);
            else add_edge(i*(M-1)+j,(i-1)*(M-1)+j-1,t);
        }
    //斜边
    for(int i=1;i<2*(N-1)+1;i+=2)
        for(int j=1;j<M;++j){
            scanf("%d",&t);
            add_edge((i-1)*(M-1)+j,i*(M-1)+j,t);
        }
}
bool spfa(int s){
    memset(cnt, 0, sizeof(cnt)), memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    cnt[s] = 0, vis[s] = true;
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=head[u]; ~i; i=node[i].next){
            int v=node[i].v;
            if(dist[v]>dist[u]+node[i].w){
                dist[v] = dist[u]+node[i].w;
                if(!vis[v]){
                    cnt[v]++;
                    vis[v] = true;
                    q.push(v);
                    if(cnt[v]>2*(N-1)*(M-1)+2) return false;
                }
            }
        }
    }
    return true;
}
int main(){
    init();
    build_graph();
    if(minn == inf){
        spfa(0);
//        for(int i=0; i<=2*(N-1)*(M-1)+1; i++){
//            cout<<i<<" "<<dist[i]<<endl;
//        }
        printf("%d\n", dist[end_pos]);
    }
    else printf("%d", minn);
    return 0;
}

hdu 6228

思维题
一开始题都读不懂，题意是若干个点染色，每种颜色会生成一棵树，问树最多会有多少个重叠的边
先用DFS求出每个点的子孙节点个数(包括自身)，假设为x，那么它的上面点的个数为n-x,只要x>=k&&(n-x)>=k即能满足上面的条件。

我是真没有想到这样就行了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, k;
struct Node{
    int v, next;
}node[maxn<<1];
int tot, head[maxn];
int d[maxn];
int sz[maxn];
int deg[maxn];
bool vis[maxn];
int level[maxn];
void init(){
    tot=0;cls(head, -1);
    cls(deg, 0);
    cls(vis, 0);
}
void add_edge(int u, int v){
    node[tot].v=v, node[tot].next=head[u], head[u]=tot++;
}
void dfs(int u, int p){
    d[u]=d[p]+1;
    sz[u] = 1;
    for(int i=head[u];~i;i=node[i].next){
        int v=node[i].v;
        if(p==v) continue;
        dfs(v, u);
       sz[u] += sz[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &k);
        init();
        int u, v;
        for(int i=0; i<n-1; i++){
            scanf("%d%d", &u, &v);
            add_edge(u ,v), add_edge(v, u);
            deg[u]++, deg[v]++;
        }
        if(k == 1) {printf("%d\n", n-1);continue;}
        dfs(1, 0);
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(sz[i]>=k&&n-sz[i]>=k) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
10
12 4
1 2
2 3
2 4
2 5
5 9
5 8
5 6
6 7
7 10
10 11
10 12
8 3
1 2
2 3 3 4 4 5 5 6 6 7 7 8
10
3 2
1 2 2 3
*/

bzoj 1997

保存最长链上面的所有的节点

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
 
 
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
const int maxm = 1e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
 
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
int n, m;
int u[maxn], v[maxn];
int low[maxn], dfn[maxn], cnt;
int tot, head[maxn];
int cur[maxn];
int pos[maxn];
int scc, belong[maxn];
int uu[maxn], vv[maxn];
bool instack[maxn];
int sta[maxn], top;
 
void init(){
    tot=0, cls(head, -1);
    cnt=0, cls(low, 0), cls(dfn, 0);
    scc=0;
    cls(instack, 0);
    top=0;
}
struct Node{
    int v, next;
}node[maxm<<2];
 
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next=head[u],head[u]=tot++;
}
 
bool in(int x1, int y1, int x2, int y2){
    if(x2>x1&&x2<y1&&y2>y1) return true;
    if(x2<x1&&y2>x1&&y2<y1) return true;
    return false;
}
 
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    instack[x] = true;
    sta[top++]=x;
    for(int i=head[x]; ~i; i=node[i].next){
        int y=node[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=  min(low[x], low[y]);
 
        }
        else if(instack[y]) low[x]=  min(low[x], dfn[y]);
    }
    if(low[x] == dfn[x]){
        int id;
        scc++;
        do{
            id=sta[--top];
            instack[id] = false;
            belong[id] = scc;
        }while(id!=x);
    }
}
 
bool judge(){
    inc(i, 1, n){
        if(belong[i] == belong[i+n]) return false;
    }
    return true;
}
 
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        init();
        inc(i, 1, m) scanf("%d%d", &u[i], &v[i]);
        inc(i ,1, n) scanf("%d", &cur[i]);
        inc(i, 1, n) pos[cur[i]] = i;
        if(m>3*n+6) {puts("NO"); continue;}
        int tot_edge=0;
        inc(i, 1, m){
            int x=pos[u[i]], y=pos[v[i]];
            if(x>y) swap(x, y);
            if(y-x==1||(x==1&&y==n)) continue;
            uu[++tot_edge]=x, vv[tot_edge] = y;
        }
//        for(int i=1; i<=tot_edge; i++){
//            cout<<uu[i]<<" "<<vv[i]<<endl;
//        }
        //i表示在内部，i+n表示在外部
        for(int i=1; i<=tot_edge; i++){
            for(int j=i+1; j<=tot_edge; j++){
                if(in(uu[i], vv[i], uu[j], vv[j])){
                    add_edge(i, j+n);
                    add_edge(i+n, j);
                    add_edge(j, i+n);
                    add_edge(j+n, i);
                }
            }
        }
 
        for(int i=1; i<=n*2; i++){
            if(!dfn[i]) tarjan(i);
        }
        if(judge())puts("YES");
        else puts("NO");
    }
    return 0;
}

洛谷2764

有向图的最小路径覆盖，转化为二分图的最大匹配。题目要求输出方案

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
#include <bits/stdc++.h>
const int N=160;
int n,m;
struct edge
{
    int v,next;
}node[N*N];
int head[N],cnt=0;
void add(int u,int v)
{
    node[cnt].v=v; node[cnt].next=head[u]; head[u]=cnt++;
}
int used[N],match[N];
bool m_find(int u)
{
    for(int i=head[u];~i;i=node[i].next)
    {
        int v=node[i].v;
        if(!used[v])
        {
            used[v]=1;
            if(!match[v]||m_find(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
void dfs(int now)
{
    if(!match[now]) {printf("%d ",now);return;}
    dfs(match[now]); printf("%d ",now);
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    memset(head, -1, sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof(used));
        if(m_find(i)) ans++;
    }
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++)
        used[match[i]]=1;
    for(int i=1;i<=n;i++)
        if(!used[i])//链的尾节点
        {dfs(i);printf("\n");}
    printf("%d\n",n-ans);
    return 0;
}

hdu 1565 方格取数

最大权独立集
注意建图的技巧
hdu 1569和它是一样的，我就只贴1569的代码了
都跑的是0ms

最大点权独立集=总权值-最小点权覆盖集。
最小点权覆盖集=图的最小割值=最大流。
这道题很明显就是求最大点权独立集，所以直接套用公式即可。
建图：如果S与(i+j)%2==0的点相连，(i+j)%2==1的点与T相连，容量为该点的权值。(i+j)%==0与(i+j)%2==1的点相连，容量为无限大。

建图很关键

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505;
const int INF = 1e9+10;
struct Edge{
    int to, cap, rev;
};
vector<Edge> G[maxn];
int cnt[maxn];
int level[maxn];
int s, t;
int n, m;
void add_edge(int u, int v, int cap){
    G[u].push_back(Edge{v, cap, G[v].size()});
    G[v].push_back(Edge{u, 0, G[u].size()-1});
}
void bfs(int s){
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++){
            Edge& e = G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to] = level[v]+1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int t, int flow){
    if(v == t) return flow;
    for(int& i=cnt[v]; i<G[v].size(); i++){
        Edge& e = G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d = dfs(e.to, t, min(flow, e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;//一旦有一条路径满足就立即返回！
            }
        }
    }
    return 0;
}
int max_flow(int s, int t){
    int flow = 0;
    for(;;){
        //构造层次图
        bfs(s);
        //无法连通终点，结束访问
        if(level[t]<0) return flow;
        int f;
        //cnt数组记录在递归的过程中的边的顺序。
        memset(cnt, 0, sizeof(cnt));
        //当存在增广路的时候不断的进行增广
        while((f = dfs(s, t, INF))>0){
            flow+=f;
        }
    }
}
int num[53][53];
int dx[5] = {1, -1, 0, 0};
int dy[5] = {0, 0, 1, -1};
int getid(int x, int y){
    if(x<=0||x>n||y<=0||y>m) return -1;
    //cout<<"haha "<<x<<" "<<y<<endl;
    return (x-1)*m+y;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int sum = 0;
        for(int i=0; i<=n*m+1; i++) G[i].clear();
        int u, v, cap;
        s=0, t=n*m+1;
        int w;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                scanf("%d", &num[i][j]);
                sum += num[i][j];
                if((i+j)%2==0){
                    int now = (i-1)*m+j;
                    add_edge(s, now, num[i][j]);
                    for(int k=0; k<4; k++){
                        int nx = i+dx[k];
                        int ny = j+dy[k];
                        int id = getid(nx, ny);
                        if(id!=-1) add_edge(now, id, INF);
                    }
                }
                else {
                    int now = (i-1)*m+j;
                    add_edge(now, t, num[i][j]);
                }
            }
        }
        printf("%d\n",sum-max_flow(s, t));
    }
    return 0;
}

poj 3155 最大密集子图

先用分数规划，然后求最大闭合子图，从而能判断是否是最大密集子图
其中的公式推导不是很明白，就当是一个模板的积累了

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
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn = 205;
const int INF = 1e9+10;
const double eps = 1e-8;
struct Edge{
    int to, rev;
    double cap;
    Edge(int _to, double _cap, int _rev):to(_to), cap(_cap), rev(_rev){}
};
vector<Edge> G[maxn];
int cnt[maxn];
int level[maxn];
int s, t;
int n, m;
int d[maxn];
void add_edge(int u, int v, double cap){
    G[u].push_back(Edge(v, cap, G[v].size()));
    G[v].push_back(Edge(u, 0, G[u].size()-1));
}
void bfs(int s){
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++){
            Edge& e = G[v][i];
            if(e.cap>eps&&level[e.to]<0){
                level[e.to] = level[v]+1;
                q.push(e.to);
            }
        }
    }
}
double dfs(int v, int t, double flow){
    if(v == t) return flow;
    for(int& i=cnt[v]; i<G[v].size(); i++){
        Edge& e = G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            double d = dfs(e.to, t, min(flow, e.cap));
            if(d>eps){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;//一旦有一条路径满足就立即返回！
            }
        }
    }
    return 0;
}
double max_flow(int s, int t){
    double flow = 0;
    for(;;){
        //构造层次图
        bfs(s);
        //无法连通终点，结束访问
        if(level[t]<0) return flow;
        double f;
        //cnt数组记录在递归的过程中的边的顺序。
        memset(cnt, 0, sizeof(cnt));
        //当存在增广路的时候不断的进行增广
        while((f = dfs(s, t, INF))>eps){
            //cout<<"qiu "<<f<<endl;
            flow+=f;
        }
    }
}
int x[1024], y[1024];
void graph(double g){
    for(int i=0; i<=n+1; i++){
        G[i].clear();
    }
    for(int i=0; i<m; i++){
        add_edge(x[i], y[i], 1.0), add_edge(y[i], x[i], 1.0);
    }
    for (int i = 1; i <= n; i++)
	{
		add_edge(s, i, m);
		add_edge(i, t, m + 2 * g - d[i]);
	}
}
int sum = 0;
bool vis[maxn];
void dfs_ans(int u){
    sum++;
    vis[u] = true;
    for(int i=0; i<G[u].size(); i++){
        Edge v = G[u][i];
        if(v.cap>eps&&!vis[v.to]){
            dfs_ans(v.to);
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        if(m == 0){
            printf("1\n1\n");
            continue;
        }
        for(int i=0; i<maxn; i++) d[i] = 0;
        int u, v;
        for(int i=0; i<m; i++){
            scanf("%d%d", &x[i], &y[i]);
            d[x[i]]++, d[y[i]]++;
        }
        s = 0;
        t = n+1;
        double l=0, r=m;
        double mid;
        const double presion = 1.0/n/n;
        while(r-l>=presion){
            mid = ((l+r)/2.0);
            //cout<<l<<" "<<r<<" "<<mid<<endl;
            graph(mid);
            //未满流
            //cout<<"out"<<endl;
            if((n*m-max_flow(s, t))/2.0>eps) l=mid;
            else r=mid;
        }
        graph(l);
        max_flow(s, t);
        sum = 0, memset(vis, 0, sizeof(vis));
        dfs_ans(0);
        printf("%d\n", sum-1);
        for(int i=1; i<=n; i++) {
            if(vis[i]) printf("%d\n", i);
        }
    }
    return 0;
}

luogu 1719

二维最大子矩阵权值最大

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 120+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[maxn][maxn];
int pre[maxn][maxn];
int main()
{
    n=readint();
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) num[i][j] = readint();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            pre[i][j] = pre[i][j-1]+num[i][j];
        }
    }
    int ans = -inf;
    int temp = 0;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            temp = 0;
            //这里当成的是一维的贪心的取法的，只要权值大于0，这个连续的段就要取
            for(int k=1; k<=n; k++){
                temp += pre[k][j]-pre[k][i-1];
                if(temp>ans) ans = temp;
                if(temp<0) temp = 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

uva 10827 球面的矩阵的权值最大和

类似于二维的处理，因为是环形的，所以进行复制的处理

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 150+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[maxn][maxn];
int pre[maxn][maxn];
int main()
{
    int _;
    _ = readint();
    while(_--){
        n=readint();
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) num[i][j] = readint();
        for(int i=n+1; i<=2*n; i++){
            for(int j=1; j<=n; j++) num[i][j] = num[i-n][j];
        }
        for(int i=1; i<=n; i++) for(int j=n+1; j<=2*n; j++) num[i][j] = num[i][j-n];
        for(int i=n+1; i<=2*n; i++) for(int j=n+1; j<=2*n; j++) num[i][j] = num[i-n][j-n];
        for(int i=1; i<=n*2; i++){
            for(int j=1; j<=n*2; j++){
                pre[i][j] = pre[i][j-1]+num[i][j];
            }
        }
        int ans = -inf;
        int temp = 0;
        for(int i=1; i<=2*n; i++){
            for(int j=i; j<=2*n&&j-i+1<=n; j++){
                //temp = 0;
                //这里当成的是一维的贪心的取法的，只要权值大于0，这个连续的段就要取
                for(int l=1; l<=n; l++){
                    temp = 0;
                    for(int k=l; k-l+1<=n; k++){
                        temp += pre[k][j]-pre[k][i-1];
                        if(temp>ans) ans = temp;
                        if(temp<0) temp = 0;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

bzoj2791

有向图的基环树两个点到祖先节点的最短路
可以对环内的节点进行相应的编号

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
 
 
const int inf = 0x3f3f3f3f;
const int maxn = 5e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
 
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
int n, q;
int nex[maxn];
int pos[maxn];
int vis[maxn];
int scc;
int root[maxn];
 
int on_ring[maxn];
int sz[maxn];
int d[maxn];
int f[maxn][21];
 
void dfs(int u){
    vis[u] = scc;
    int v=nex[u];
    if(vis[v] == scc){
        int idx=1;
        for(int i=u; idx==1||i!=u; i=nex[i]){
            pos[i] = idx++;
            on_ring[i] = scc;
            root[i] = i;
            d[i] = 1;
        }
        sz[scc] = idx-1;
        return ;
    }
    else if(!vis[v])dfs(v);
    if(!on_ring[u]){
        d[u] = d[v]+1;
        f[u][0] = v;
        root[u] = root[v];
    }
}
 
void init_lca(){
    for(int j=1; j<=19; j++){
        for(int i=1; i<=n; i++){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}
 
int lca(int u, int v){
    if(d[u]<d[v]) swap(u, v);
    for(int i=19; i>=0; i--){
        if(d[f[u][i]]>=d[v]) u=f[u][i];
    }
    if(u == v) return u;
    for(int i=19; i>=0; i--){
        if(f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    }
    return f[u][0];
}
 
int dis(int x, int y, int z){
    return (y-x+z)%z;
}
 
void query(int u, int v){
    int fx=root[u], fy=root[v];
    if(on_ring[fx]!=on_ring[fy]){
        printf("-1 -1\n");
        return ;
    }
    if(fx == fy){
        int fa = lca(u, v);
        //cout<<"father "<<fa<<endl;
        printf("%d %d\n", d[u]-d[fa], d[v]-d[fa]);
        return ;
    }
    int x1= d[u]-1+dis(pos[fx], pos[fy], sz[on_ring[fx]]), y1=d[v]-1;
    int x2=d[u]-1, y2 = d[v]-1+dis(pos[fy], pos[fx], sz[on_ring[fy]]);
    if(max(x1, y1)!=max(x2, y2)){
        if(max(x1, y1)<max(x2, y2)){
            printf("%d %d\n", x1, y1);
        }
        else printf("%d %d\n", x2, y2);
        return ;
    }
    if(min(x1, y1)!=min(x2, y2)){
        if(min(x1, y1)<min(x2, y2)){
            printf("%d %d\n", x1, y1);
        }
        else printf("%d %d\n", x2, y2);
        return ;
    }
    printf("%d %d\n", max(x1, y1), min(x1, y1));
 
 
}
 
int main()
{
    scanf("%d%d", &n, &q);
    inc(i, 1, n) scanf("%d", &nex[i]);
    inc(i, 1, n) if(!vis[i]) ++scc, dfs(i);
    init_lca();
//    for(int i=1; i<=n; i++){
//        cout<<i<<" "<<root[i]<<" "<<f[i][0]<<" "<<sz[i]<<endl;
//    }
    int u, v;
    inc(i, 1, q){
        scanf("%d%d", &u, &v);
        query(u, v);
    }
    return 0;
}
/*
12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5
*/

ecf 51 F

link
一开始想缩21个环，但是早上问聚聚们说得用仙人掌？果断放弃
后来看了别人的代码
主要就是先瞎几把建一棵树，求没有被访问过的边的所在点的最短路，
假设求u, v间的最短路，要么在原来的树上面跑lca，要么经过那40个点的最短路
思路还是相当的强的

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int readll()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Node{
    int v, next;
    ll w;
}node[maxn<<1];
int tot, head[maxn];
bool vis[maxn];
bool bian[maxn<<1];
bool res[maxn];
ll dis[maxn];
ll diss[50][maxn];
int index;
ll g[maxn][20];
int f[maxn][20];
void init(){
    tot = 0, cls(head, -1);
}
int n, m;
void add_edge(int u, int v, ll w){
    node[tot].v=v, node[tot].w=w, node[tot].next = head[u], head[u] = tot++;
}
void dfs1(int u){
    vis[u] = true;
    for(int i=head[u]; ~i;i=node[i].next){
        int v = node[i].v;
        if(vis[v]) continue;
        bian[i] = bian[i^1] = true;
        dfs1(v);
    }
}
struct Qnode{
    int u;
    ll w;
    Qnode(int _u, ll _w):u(_u), w(_w){}
    bool operator < (const Qnode & b) const {
        return w>b.w;
    }
};
void dij(int s, int index){
    priority_queue<Qnode> pq;
    while(!pq.empty()) pq.pop();
    for(int i=0; i<=n; i++) dis[i] = inf;
    dis[s] = 0;
    cls(vis, 0);
    pq.push(Qnode(s, 0));
    while(!pq.empty()){
        Qnode temp = pq.top();
        pq.pop();
        int u = temp.u;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=head[u]; ~i; i=node[i].next){
            int v = node[i].v;
            ll w = node[i].w;
            if(dis[v]>dis[u]+w){
                dis[v] = dis[u]+w;
                if(!vis[v]) pq.push(Qnode(v, dis[v]));
            }
        }
    }
    for(int i=1; i<=n; i++) {
        diss[index][i] = dis[i];
    }
}
int d[maxn];
void dfs2(int x){
	for(int i=1; i<=17; i++) g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1],f[x][i]=f[f[x][i-1]][i-1];
	int v;
	for(int i=head[x]; ~i; i=node[i].next)
        if (bian[i] && (v=node[i].v)!=f[x][0]) f[v][0]=x,g[v][0]=node[i].w,d[v]=d[x]+1,dfs2(v);
}
ll lca(int u, int v){
    ll res = 0;
    if(d[u]<d[v]) swap(u, v);
    for(int i=17; i>=0; i--){
        if(d[f[u][i]]>=d[v]){
            res += g[u][i];
            u=f[u][i];
        }
    }
    if(u == v) return res;
    for(int i=17; i>=0; i--){
        if(f[u][i]!=f[v][i]){
            res += (g[u][i]+g[v][i]);
            u=f[u][i], v=f[v][i];
        }
    }
    return res+g[u][0]+g[v][0];
}
int main()
{
    init();
    //cout<<(inf<<1)<<endl;
    n=readint(), m=readint();
    int u, v;
    ll w;
    for(int i=1; i<=m; i++){
        u=readint(), v=readint(), w=readll();
        add_edge(u, v, w), add_edge(v, u, w);
    }
    dfs1(1);
    for(int i=0; i<tot; i++){
        if(!bian[i]&&!res[node[i].v]){
            res[node[i].v] = true;
            dij(node[i].v, index++);
        }
    }
//    for(int i=0; i<index; i++){
//        cout<<"keke ";
//        for(int j=1; j<=n; j++){
//            cout<<diss[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    d[1] = 1;
    dfs2(1);
    int q;
    scanf("%d", &q);
    while(q--){
        u=readint(), v=readint();
        ll res=lca(u,v);
        for(int i=0; i<index; i++)
            res=min(res,diss[i][u]+diss[i][v]);
        printf("%lld\n", res);
    }
    return 0;
}

bzoj 1002

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
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#define MAX_L 2005 //最大长度，可以修改
using namespace std;
class bign
{
public:
    int len, s[MAX_L];//数的长度，记录数组
//构造函数
    bign();
    bign(const char*);
    bign(int);
    bool sign;//符号 1正数 0负数
    string toStr() const;//转化为字符串，主要是便于输出
    friend istream& operator>>(istream &,bign &);//重载输入流
    friend ostream& operator<<(ostream &,bign &);//重载输出流
//重载复制
    bign operator=(const char*);
    bign operator=(int);
    bign operator=(const string);
//重载各种比较
    bool operator>(const bign &) const;
    bool operator>=(const bign &) const;
    bool operator<(const bign &) const;
    bool operator<=(const bign &) const;
    bool operator==(const bign &) const;
    bool operator!=(const bign &) const;
//重载四则运算
    bign operator+(const bign &) const;
    bign operator++();
    bign operator++(int);
    bign operator+=(const bign&);
    bign operator-(const bign &) const;
    bign operator--();
    bign operator--(int);
    bign operator-=(const bign&);
    bign operator*(const bign &)const;
    bign operator*(const int num)const;
    bign operator*=(const bign&);
    bign operator/(const bign&)const;
    bign operator/=(const bign&);
//四则运算的衍生运算
    bign operator%(const bign&)const;//取模（余数）
    bign factorial()const;//阶乘
    bign Sqrt()const;//整数开根（向下取整）
    bign pow(const bign&)const;//次方
//一些乱乱的函数
    void clean();
    ~bign();
};
#define max(a,b) a>b ? a : b
#define min(a,b) a<b ? a : b
bign::bign()
{
    memset(s, 0, sizeof(s));
    len = 1;
    sign = 1;
}
bign::bign(const char *num)
{
    *this = num;
}
bign::bign(int num)
{
    *this = num;
}
string bign::toStr() const
{
    string res;
    res = "";
    for (int i = 0; i < len; i++)
        res = (char)(s[i] + '0') + res;
    if (res == "")
        res = "0";
    if (!sign&&res != "0")
        res = "-" + res;
    return res;
}
istream &operator>>(istream &in, bign &num)
{
    string str;
    in>>str;
    num=str;
    return in;
}
ostream &operator<<(ostream &out, bign &num)
{
    out<<num.toStr();
    return out;
}
bign bign::operator=(const char *num)
{
    memset(s, 0, sizeof(s));
    char a[MAX_L] = "";
    if (num[0] != '-')
        strcpy(a, num);
    else
        for (int i = 1; i < strlen(num); i++)
            a[i - 1] = num[i];
    sign = !(num[0] == '-');
    len = strlen(a);
    for (int i = 0; i < strlen(a); i++)
        s[i] = a[len - i - 1] - 48;
    return *this;
}
bign bign::operator=(int num)
{
    char temp[MAX_L];
    sprintf(temp, "%d", num);
    *this = temp;
    return *this;
}
bign bign::operator=(const string num)
{
    const char *tmp;
    tmp = num.c_str();
    *this = tmp;
    return *this;
}
bool bign::operator<(const bign &num) const
{
    if (sign^num.sign)
        return num.sign;
    if (len != num.len)
        return len < num.len;
    for (int i = len - 1; i >= 0; i--)
        if (s[i] != num.s[i])
            return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i]));
    return !sign;
}
bool bign::operator>(const bign&num)const
{
    return num < *this;
}
bool bign::operator<=(const bign&num)const
{
    return !(*this>num);
}
bool bign::operator>=(const bign&num)const
{
    return !(*this<num);
}
bool bign::operator!=(const bign&num)const
{
    return *this > num || *this < num;
}
bool bign::operator==(const bign&num)const
{
    return !(num != *this);
}
bign bign::operator+(const bign &num) const
{
    if (sign^num.sign)
    {
        bign tmp = sign ? num : *this;
        tmp.sign = 1;
        return sign ? *this - tmp : num - tmp;
    }
    bign result;
    result.len = 0;
    int temp = 0;
    for (int i = 0; temp || i < (max(len, num.len)); i++)
    {
        int t = s[i] + num.s[i] + temp;
        result.s[result.len++] = t % 10;
        temp = t / 10;
    }
    result.sign = sign;
    return result;
}
bign bign::operator++()
{
    *this = *this + 1;
    return *this;
}
bign bign::operator++(int)
{
    bign old = *this;
    ++(*this);
    return old;
}
bign bign::operator+=(const bign &num)
{
    *this = *this + num;
    return *this;
}
bign bign::operator-(const bign &num) const
{
    bign b=num,a=*this;
    if (!num.sign && !sign)
    {
        b.sign=1;
        a.sign=1;
        return b-a;
    }
    if (!b.sign)
    {
        b.sign=1;
        return a+b;
    }
    if (!a.sign)
    {
        a.sign=1;
        b=bign(0)-(a+b);
        return b;
    }
    if (a<b)
    {
        bign c=(b-a);
        c.sign=false;
        return c;
    }
    bign result;
    result.len = 0;
    for (int i = 0, g = 0; i < a.len; i++)
    {
        int x = a.s[i] - g;
        if (i < b.len) x -= b.s[i];
        if (x >= 0) g = 0;
        else
        {
            g = 1;
            x += 10;
        }
        result.s[result.len++] = x;
    }
    result.clean();
    return result;
}
bign bign::operator * (const bign &num)const
{
    bign result;
    result.len = len + num.len;
    for (int i = 0; i < len; i++)
        for (int j = 0; j < num.len; j++)
            result.s[i + j] += s[i] * num.s[j];
    for (int i = 0; i < result.len; i++)
    {
        result.s[i + 1] += result.s[i] / 10;
        result.s[i] %= 10;
    }
    result.clean();
    result.sign = !(sign^num.sign);
    return result;
}
bign bign::operator*(const int num)const
{
    bign x = num;
    bign z = *this;
    return x*z;
}
bign bign::operator*=(const bign&num)
{
    *this = *this * num;
    return *this;
}
bign bign::operator /(const bign&num)const
{
    bign ans;
    ans.len = len - num.len + 1;
    if (ans.len < 0)
    {
        ans.len = 1;
        return ans;
    }
    bign divisor = *this, divid = num;
    divisor.sign = divid.sign = 1;
    int k = ans.len - 1;
    int j = len - 1;
    while (k >= 0)
    {
        while (divisor.s[j] == 0) j--;
        if (k > j) k = j;
        char z[MAX_L];
        memset(z, 0, sizeof(z));
        for (int i = j; i >= k; i--)
            z[j - i] = divisor.s[i] + '0';
        bign dividend = z;
        if (dividend < divid) { k--; continue; }
        int key = 0;
        while (divid*key <= dividend) key++;
        key--;
        ans.s[k] = key;
        bign temp = divid*key;
        for (int i = 0; i < k; i++)
            temp = temp * 10;
        divisor = divisor - temp;
        k--;
    }
    ans.clean();
    ans.sign = !(sign^num.sign);
    return ans;
}
bign bign::operator/=(const bign&num)
{
    *this = *this / num;
    return *this;
}
bign bign::operator%(const bign& num)const
{
    bign a = *this, b = num;
    a.sign = b.sign = 1;
    bign result, temp = a / b*b;
    result = a - temp;
    result.sign = sign;
    return result;
}
bign bign::pow(const bign& num)const
{
    bign result = 1;
    for (bign i = 0; i < num; i++)
        result = result*(*this);
    return result;
}
bign bign::factorial()const
{
    bign result = 1;
    for (bign i = 1; i <= *this; i++)
        result *= i;
    return result;
}
void bign::clean()
{
    if (len == 0) len++;
    while (len > 1 && s[len - 1] == '\0')
        len--;
}
bign bign::Sqrt()const
{
    if(*this<0)return -1;
    if(*this<=1)return *this;
    bign l=0,r=*this,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(mid*mid>*this)
            r=mid;
        else
            l=mid;
    }
    return l;
}
bign::~bign()
{
}
bign num[105];
/*
公式：
f[i] = 3*f[i-1]-f[i-2]+2;
*/
int main() {
    num[1] = 1, num[2] = 5;
    int n;
    cin>>n;
    for(int i=3; i<=n; i++){
        num[i] = num[i-1]*3-num[i-2]+2;
    }
    cout << num[n] << endl;
    return 0;
}

bzoj 1430猴子打架

它们间的打架的关系是一棵树形的结构，无根树的方案有$n^(n-2)$, 然后是有序的，所以乘$(n-1)!$
n-1次之后连通就应该联想到树形的结构？

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int mod = 9999991;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    ll ans = 1;
    for(ll i=1; i<=n-2; i++) ans = ans*n%mod;
    for(ll i=1; i<=n-1; i++) ans = ans*i%mod;
    cout<<ans<<endl;
    return 0;
}

bzoj 1003

先预处理出来1->m， [i, j] 天的固定航线的花费
$dp[i] = min(dp[j], dp[j]+cost[j+1][i]+k), j \lt i $
dp[i]表示的是前i天的花费

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x7f7f7f7f;
const int maxn = 105;
const int maxm = 30;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Node{
    int v, next, w;
}node[maxm*maxm*2];
int tot, head[maxn];
int dp[maxn], cost[maxn][maxn];
int dis[maxn];
bool vis[maxn];
bool broken[maxn][maxn];
bool can[maxn];
int n, m, k, e;
void add_edge(int u, int v, int w){
    node[tot].v=v, node[tot].w=w, node[tot].next=head[u], head[u] = tot++;
}
int spfa(){
    cls(vis, 0);
    cls(dis, 0x7f);
    dis[1] = 0;
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(1);
    vis[1] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=head[u]; ~i; i=node[i].next){
            int v = node[i].v;
            int w = node[i].w;
            if(!can[v]&&dis[v]>dis[u]+w){
                dis[v] = dis[u]+w;
                if(!vis[v]){
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dis[m];
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &e);
    tot=0, cls(head, -1);
    int u, v, w;
    for(int i=1; i<=e; i++) {
        //u=readint(), v=readint(), w=readint();
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u ,v, w), add_edge(v, u, w);
    }
    int d;
    //d=readint();
    scanf("%d", &d);
    for(int  i=1; i<=d; i++){
        //readint(), v=readint(), w=readint();
        scanf("%d%d%d", &u, &v, &w);
        for(int j=v; j<=w; j++) broken[u][j] = true;
    }
    cls(cost, 0x7f);
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            cls(can, 0);
            //这里m>n原来的写法就gg
            for(int k=1; k<=m; k++){
                for(int s=i; s<=j; s++) can[k] |= broken[k][s];
            }
            cost[i][j] = spfa();
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++) if(cost[i][j]<inf)cost[i][j] = cost[i][j]*(j-i+1);
    }
    cls(dp, 0x7f);
    for(int i=1; i<=n; i++) dp[i] = cost[1][i];
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            dp[i] = min(dp[i], dp[j]+cost[j+1][i]+k);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}
/*
5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
*/

bz0j1006

cdq讲稿
题目求的是一般图的最小的染色方案数，使得相邻的节点的颜色不同
用了一个最大势算法，具体可以看看blog的演示的过程

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int maxm = 2e6+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int v, w, next;
}node[maxm];
int tot, head[maxn];
void add_edge(int u, int v){
    node[tot].v=v, node[tot].next=head[u], head[u]=tot++;
}
int flag[maxn];
//指向下一个势最大的点
int pt[maxn];
int size[maxn];
int color[maxn];
int main()
{
    tot = 0, cls(head, -1);
    scanf("%d%d", &n, &m);
    int u, v;
    for(int i=1; i<=m; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v), add_edge(v, u);
    }
    for (int i=n;i>=1;--i){
        int cur=0;
        for (int j=1;j<=n;++j)
            if (!flag[j]&&size[j]>=size[cur])
                cur=j;
        flag[cur]=1; pt[i]=cur;
        for (int j=head[cur];~j;j=node[j].next) size[node[j].v]++;
    }
    memset(flag,0,sizeof(flag));
    int ans = 0;
    for (int i=n;i>=1;--i){
        for (int j=head[pt[i]];~j;j=node[j].next)
            flag[color[node[j].v]]=i;
        color[pt[i]]=1;
        while (flag[color[pt[i]]]==i)
            color[pt[i]]++;
        ans=max(ans,color[pt[i]]);
    }
    printf("%d\n",ans);
    return 0;
}

uva1330 Game City

求一个有障碍的方格的最大的矩形的面积

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int mat[maxn][maxn], up[maxn][maxn], righ[maxn][maxn], lef[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m;
        char ch;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                cin>>ch;
                mat[i][j] = ch == 'F'?0:1;
            }
        }
//        for(int i=1; i<=n; i++){
//            for(int j=1; j<=m; j++){
//                cout<<mat[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            int l=0, r=m+1;
            for(int j=1; j<=m; j++){
                if(mat[i][j]){
                    up[i][j] = lef[i][j] = 0;
                    l = j;
                }
                else{
                    up[i][j] = i==1?1:up[i-1][j]+1;
                    //上一行的最左边和目前行的最左边
                    lef[i][j] = i==1?l+1:max(lef[i-1][j], l+1);
                }
            }
            for(int j=m; j>=1; j--){
                if(mat[i][j]){
                    righ[i][j] = n;
                    r=j;
                }
                else{
                    righ[i][j] = i==1?r-1:min(righ[i-1][j], r-1);
                    ans = max(ans, up[i][j]*(righ[i][j]-lef[i][j]+1));
                }
            }
        }
        printf("%d\n", ans*3);
    }
    return 0;
}

uva10891

记忆化博弈论
d[i][j]表示在(i, j)段能获得的最大的得分

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[maxn], sum[maxn], d[maxn][maxn];
int dp(int i, int j){
    if(d[i][j] !=-inf) return d[i][j];
    int m = 0;
    for(int s=i+1; s<=j; s++) m = min(m, dp(s, j));
    for(int s=i; s<j; s++) m = min(m, dp(i, s));
    return d[i][j] = sum[j]-sum[i-1]-m;
}
int main()
{
    while(~scanf("%d", &n)&&n){
        for(int i=0; i<maxn; i++) for(int j=0; j<maxn; j++) d[i][j] = -inf;
        for(int i=1; i<=n; i++) scanf("%d", &num[i]);
        for(int i=1; i<=n; i++) sum[i] = sum[i-1]+num[i];
        printf("%d\n", 2*dp(1, n)-sum[n]);
    }
    return 0;
}

la 3902 Network

从最深的叶子节点，向上k级的父亲，然后从这个父亲向两边覆盖即可

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, s, k;
vector<int> G[maxn];
vector<int> node[maxn];
bool cover[maxn];
int fa[maxn];
void dfs1(int u, int p, int d){
    fa[u] = p;
    if(G[u].size()==1 && d>=k) node[d].push_back(u);
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(v == p) continue;
        dfs1(v, u, d+1);
    }
}
void dfs2(int u, int p, int d){
    if(d<=k) cover[u] = true;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(v == p) continue;
        dfs2(v, u, d+1);
    }
}
void solve(){
    int ans = 0;
    for(int d=n-1; d>k; d--){
        for(int i=0; i<node[d].size(); i++){
            int u = node[d][i];
            if(cover[u]) continue;
            int v = u;
            for(int j=0; j<k; j++) v=fa[v];
            dfs2(v, 0, 0);
            ans++;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d%d", &n, &s, &k);
        int u, v;
        for(int i=0; i<maxn; i++) G[i].clear(), node[i].clear();
        cls(cover, 0);
        for(int i=0; i<n-1; i++){
            scanf("%d%d", &u, &v);
            G[u].push_back(v), G[v].push_back(u);
        }
        dfs1(s, -1, 0);
        solve();
    }
    return 0;
}

hiho 北京网络赛

建立一个队列，满足条件的话就不断的入队，不满足条件的话就不断的出队

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll a[maxn], b[maxn];
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        for(int i=0; i<n ;i++) scanf("%lld", &a[i]);
        for(int i=0; i<n; i++) scanf("%lld", &b[i]);
        ll ans = 0;
        ans = m+a[0]-b[0];
        queue<int> q;
        while(!q.empty()) q.pop();
        q.push(0);
        bool flag = false;
        for(int i=1; i<2*n; i++){
            if(q.size()==n&&ans>=0){
                flag = true;
                break;
            }
            while(!q.empty()&&ans<0){
                int v=q.front();
                q.pop();
                ans += b[v], ans -= a[v];
            }
            q.push(i%n);
            ans += a[i%n]-b[i%n];
        }
        if(flag) printf("%d\n", q.front()+1);
        else printf("-1\n");
    }
    return 0;
}

rich game hduoj

写挂了
注意读题，得分与赢一局的关系
列一个多元的等式，然后进行分情况讨论就可以了

1
2

knight 学会用python进行拟合函数

感觉这道题目找规律是很显然的，但是怎样求出公式还是比较的困难的，我想到的现场赛的策略就是进行多项式的拟合，应该改有求出来的概率的

la 5052 基因组进化

a[]在b[]中的位置要恰好卡住，那么就一定能够满足题意

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
int pos[maxn];
int n;
int main(){
    while(~scanf("%d", &n)&&n){
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<n; i++) scanf("%d", &b[i]), pos[b[i]] = i;
        int ans = 0;
        for(int i=1; i<n; i++){
            //a[]在b[]中的位置要恰好卡住，那么就一定能够满足题意
            int l=pos[a[i]], r=pos[a[i]];
            for(int j=i-1; j>=0; j--){
                l=min(l,pos[a[j]]);
                r=max(r,pos[a[j]]);
                if(r-l+1==i-j+1) ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

xdoj 1275

枚举矩形的右下角，然后判断就行了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
const int maxn = 105;
bool vis[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        int u ,v;
        cin>>n;
        cls(vis, 0);
        for(int i=1; i<=n; i++) {
            cin>>u>>v;
            vis[u][v] = true;
        }
        int ans = 0;
        for(int i=0; i<=100; i++){
            for(int j=0; j<=100; j++){
                if(!vis[i][j]) continue;
                int len = min(100-i, 100-j);
                for(int k=1; k<=len; k++){
                    if(vis[i+k][j]&&vis[i][j+k]&&vis[i+k][j+k]) ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

poj 2559 histgram 最大矩形的面积

在数组的最后设置一个哨兵，使之最后全部弹栈

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 <cstdio>
#include <stack>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
ll num[maxn];
struct Node{
    int index;
    ll h;
}node[maxn];
stack<Node> sta;
int n;
int main(){
    while(~scanf("%d", &n)&&n){
        for(int i=1; i<=n; i++) scanf("%lld", &num[i]);
        ll ans = 0;
        //最后使之全部弹栈
        num[n+1] = 0;
        for(int i=1; i<=n+1; i++){
            Node temp;
            temp.h = num[i];
            temp.index = i;
            if(sta.empty()) sta.push(temp);
            else{
                if(sta.top().h<temp.h) sta.push(temp);
                else if(sta.top().h>temp.h){
                    int target = i;
                    while(!sta.empty()&&sta.top().h>=temp.h){
                        Node pre = sta.top(); sta.pop();
                        ll area = pre.h*(i-pre.index);
                        ans = max(ans, area);
                        target = pre.index;
                    }
                    temp.index = target;
                    sta.push(temp);
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

joyoi 小猫爬山

因为容量高达1e8,所以不能进行背包
进行dfs即可

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 25;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[maxn];
int cab[maxn];
int w;
int ans = 0;
void dfs(int now, int cnt){
    //这个剪枝还是相当的重要的
    if(cnt>=ans) return ;
    if(now == n+1){
        ans = min(ans, cnt);
        return ;
    }
    for(int i=1; i<=cnt; i++){
        if(num[now]+cab[i]<=w){
            cab[i]+=num[now];
            dfs(now+1, cnt);
            cab[i] -= num[now];
        }
    }
    cab[cnt+1] = num[now];
    dfs(now+1, cnt+1);
    cab[cnt+1] = 0;
}
int main()
{
    ios::sync_with_stdio(false);
    while(~scanf("%d%d", &n, &w)){
        for(int i=1; i<=n; i++) scanf("%d", &num[i]);
        ans = inf;
        dfs(1, 1);
        printf("%d\n", ans);
    }
    return 0;
}

luogu 2243维修电路

01最短路复杂度可以到达O(n)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1100;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
char mp[maxn][maxn];
bool vis[maxn][maxn];
struct Node{
    int x, y;
    int step;
    Node(int _x, int _y, int _step):x(_x), y(_y), step(_step){}
};
int dx[4] = {-1, -1, 1, 1};
int dy[4] = {-1, 1, -1, 1};
bool judge(int x, int y){
    if(x<=0||x>n+1||y<=0||y>m+1) return false;
    return  true;
}
int bfs(){
    deque<Node> q;
    cls(vis, 0);
    while(!q.empty()) q.pop_back();
    q.push_back(Node(1, 1, 0));
    while(!q.empty()){
        Node u = q.front();
        q.pop_front();
        if(u.x == n+1 &&u.y == m+1){
            return u.step;
        }
        int x = u.x, y=u.y;
        int step = u.step;
        if(vis[x][y]) continue;
        vis[x][y] = true;
        for(int i=0; i<4; i++){
            int nx = dx[i]+x, ny=dy[i]+y;
            if(judge(nx, ny)){
                if(i == 0&&mp[nx][ny] == '\\' ){
                    q.push_front(Node(nx, ny, step));
                }
                else if(i == 0){
                    q.push_back(Node(nx, ny, step+1));
                }
                if(i == 1&&mp[nx][ny-1] == '\/'){
                    q.push_front(Node(nx, ny, step));
                }
                else if(i == 1){
                    q.push_back(Node(nx, ny, step+1));
                }
                if(i == 2&&mp[nx-1][ny] == '\/'){
                    q.push_front(Node(nx, ny, step));
                }
                else if(i == 2) {
                    q.push_back(Node(nx, ny, step+1));
                }
                if(i == 3&&mp[nx-1][ny-1] == '\\'){
                    q.push_front(Node(nx, ny, step));
                }
                else if(i == 3){
                    q.push_back(Node(nx, ny, step+1));
                }
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++) {
                cin>>mp[i][j];
            }
        }
        int ans = bfs();
        if(ans == -1) cout<<"NO SOLUTION"<<"\n";
        else cout<<ans<<endl;
    }
    return 0;
}

la 3716 基因突变

列出式子：
$ (i-j)*p \gt (sum[i]-sum[j])$，sum[i]表示的是前i个字符不同的字符的个数
注意设置一个哨兵就行了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 150000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, p;
char s1[maxn], s2[maxn];
struct Node{
    int num;
    int i;
}node[maxn];
bool cmp(Node a, Node b){
    if(a.num != b.num) return a.num<b.num;
    else return a.i<b.i;
}
int main()
{
    while(~scanf("%d%d", &n, &p)&&n+p){
        scanf("%s%s", s1+1, s2+1);
        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(s1[i]!=s2[i]) cnt++;
            node[i].i = i;
            node[i].num = i*p-100*cnt;
        }
        node[0].i=0, node[0].num=0;
        sort(node, node+1+n, cmp);
        int j = node[0].i;
        int ans = 0;
        if(n == 1){
            if(s1[1] == s2[1]) printf("1\n");
            else printf("No solution.\n");
            continue;
        }
//        for(int i=1; i<=n; i++){
//            cout<<node[i].i<<" "<<node[i].num<<endl;
//        }
        for(int i=1; i<=n; i++){
            if(node[i].i>j)
                ans = max(ans, node[i].i-j);
            if(node[i].i<j){
                j = node[i].i;
            }
        }
        if(ans == 0)printf("No solution.\n");
        else printf("%d\n", ans);
    }
    return 0;
}
/*
3 33
abc
abd
*/

xdoj 1269 炸弹人

注意bfs状态的记忆化

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
 
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
 
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
int n, m;
char mp[15][15];
int sx, sy, tx, ty;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
struct Node{
    int x, y;
    bool have;
    int step;
    Node(int _x, int _y, bool _have, int _step):x(_x), y(_y), have(_have), step(_step){}
};
 
bool vis[15][15][2];
bool judge(int x, int y){
    if(x<=0||x>10||y<=0||y>10) return false;
    //if(mp[x][y] == 'r') return false;
    return true;
 
}
 
int bfs(){
    queue<Node> q;
    cls(vis, 0);
    while(!q.empty()) q.pop();
    q.push(Node(sx, sy, 0, 0));
    while(!q.empty()){
        Node u = q.front();
        q.pop();
        int x = u.x, y = u.y, step = u.step;
        //cout<<x<<" "<<y<<" "<<step<<" "<<u.have<<endl;
        bool flag = u.have;
        if(x == tx&&y == ty){
            return step;
        }
        if(vis[x][y][flag]) continue;
        vis[x][y][flag] = true;
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(judge(nx, ny)){
                if(!flag&&mp[nx][ny] == 'B'){
                    //flag = true;
                    q.push(Node(nx, ny, 1, step+1));
                }
                else if(flag&&mp[nx][ny] == 'r'){
                    //flag = false;
                    q.push(Node(nx, ny, 0, step+1));
                }
                else if(!flag&& mp[nx][ny] == 'r') continue;
                else if(mp[nx][ny]!='r'){
                    q.push(Node(nx, ny, flag, step+1));
                }
 
            }
        }
    }
    return -1;
}
 
int main()
{
    for(int i=1; i<=10; i++){
        for(int j=1; j<=10; j++){
            scanf("%c", &mp[i][j]);
            if(mp[i][j] == 'S') sx = i, sy=j;
            if(mp[i][j] == 'E') tx = i, ty=j;
        }
        getchar();
    }
//    for(int i=1; i<=10; i++){
//        for(int j=1; j<=10; j++){
//            printf("%c", mp[i][j]);
//        }
//        printf("\n");
//    }
    int ans = bfs();
    if(ans == -1) printf("-1\n");
    else printf("%d\n" ,ans);
 
 
    return 0;
}

xdoj 1104

统计有多少的路径经过一条路径
直接一遍dfs就可以了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int v, next;
}node[maxn];
int tot, head[maxn];
int sz[maxn];
int fa[maxn];
void init(){
    tot = 0, cls(head, -1);
    cls(sz, 0);
}
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next = head[u], head[u] = tot++;
}
void dfs(int u, int p){
    sz[u] = 1;
    fa[u] = p;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        init();
        scanf("%d%d", &n, &m);
        int u, v;
        for(int i=1; i<=n-1; i++){
            scanf("%d%d", &u, &v);
            add_edge(u, v), add_edge(v, u);
        }
        int id;
        dfs(1, 0);
//        cout<<endl<<endl;
//        for(int i=1; i<=n; i++){
//            cout<<i<<" "<<sz[i]<<" "<<fa[i]<<endl;
//        }
        for(int i=1; i<=m; i++){
            scanf("%d", &id);
            u = node[(id<<1)-1].v;
            v = node[(id<<1)-2].v;
            if(fa[u] == v){
                printf("%lld\n", 1ll*(sz[u])*(n-sz[u]));
            }
            else{
                printf("%lld\n", 1ll*(sz[v]*(n-sz[v])));
            }
        }
    }
    return 0;
}

la 4094 思维

梦之队的最小的排名
智商不够啊，大力才结论
网上的构造真的是神奇

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int main()
{
    while(~scanf("%d", &n)&&n){
        if(n<=3) printf("1\n");
        else if(n ==4) printf("2\n");
        else printf("%d\n", n);
    }
    return 0;
}

uva 11389

有n条路线，然后下午的时间和夜间的时间不超过d，司机就没有加班费
若超过了，那么超过的时间就有加班费。问最小的加班总费用
贪心的进行相应的匹配就可以了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, d, r;
int a[maxn];
int b[maxn];
bool cmp(int a, int b){
    return a>b;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>d>>r){
        if(n+d+r == 0) break;
        for(int i=1; i<=n; i++)cin>>a[i];
        for(int i=1; i<=n; i++) cin>>b[i];
        sort(a+1, a+1+n), sort(b+1, b+1+n, cmp);
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(a[i]+b[i]<=d) continue;
            else ans += (a[i]+b[i]-d)*r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

bzoj 4152

优化建图+最短路
我原来写的dij原来一直是错的。。。
真是惊了
后来没有用引用莫名其妙的错误了，我猜可能和重边有关，明天再调吧
update:
比较函数没有return …

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define pa pair<long long,int>
const ll inf = 1e18;
const int maxn = 200000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int readll()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int x, y, id;
}node[maxn];
int tot, head[maxn];
struct Edge{
    int v, next;
    int w;
}edge[maxn<<2];
bool cmp1(Node a, Node b){
    return a.x<b.x;
}
bool cmp2(Node a, Node b){
    return a.y<b.y;
}
void add_edge(int u, int v, int w){
    edge[tot].v=v, edge[tot].next=head[u], edge[tot].w = w, head[u] = tot++;
}
ll dis[maxn];
struct Ans{
    int u;
    ll w;
    bool operator < (const Ans  b) const {
        return w>b.w;
    }
    Ans(int _u, ll _w):u(_u), w(_w){}
};
bool vis[maxn];
//void dij(int s){
//    for(int i=1; i<=n; i++) dis[i] = inf;
//    priority_queue<Ans> pq;
//    cls(vis, 0);
//    while(!pq.empty()) pq.pop();
//    dis[s] = 0;
//    pq.push(Ans(s, 0));
//    while(!pq.empty()){
//        Ans temp = pq.top();
//        pq.pop();
//        int u = temp.u;
//        //cout<<u<<" "<<temp.dis<<endl;
//        if(vis[u]) continue;
//        vis[u] = true;
//        for(int i=head[u]; ~i; i=edge[i].next){
//            int v = edge[i].v;
//            if(!vis[v]&&dis[v]>1ll*edge[i].w+dis[u]){
//                dis[v] = 1ll*edge[i].w+dis[u];
//                pq.push(Ans(v, dis[v]));
//            }
//        }
//    }
//}
priority_queue<pa,vector<pa>,greater<pa> > q;
void spfa()
{
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++) dis[i]=inf;
	dis[1]=0;
	q.push(make_pair(0,1));
	while (!q.empty())
	{
		int x=q.top().second;q.pop();
		if (vis[x]) continue;vis[x]=1;
		for (int p=head[x];~p;p=edge[p].next){
           int v = edge[p].v;
		  if (!vis[v]&&dis[v]>dis[x]+1ll*edge[p].w)
		  {
		  	dis[v]=dis[x]+1ll*edge[p].w;
		  	q.push(make_pair(dis[v],v));
		  }
		}
	}
}
int main()
{
    n=readint();
    for(int i=1; i<=n; i++){
        node[i].x=readint(), node[i].y=readint(), node[i].id = i;
    }
    tot = 0,cls(head, -1);
    sort(node+1, node+1+n, cmp1);
    int u, v;
    int w;
    for(int i=2; i<=n; i++){
        u=node[i].id, v=node[i-1].id;
        w = node[i].x-node[i-1].x;
        //cout<<u<<" "<<v<<" "<<w<<endl;
        add_edge(u, v, w), add_edge(v, u, w);
    }
    sort(node+1, node+1+n, cmp2);
    for(int i=2; i<=n; i++){
        u=node[i].id, v=node[i-1].id;
        w = node[i].y-node[i-1].y;
        //cout<<u<<" "<<v<<" "<<w<<endl;
        add_edge(u, v, w), add_edge(v, u, w);
    }
//    for(int i=1; i<=n;i++){
//        for(int j=head[i]; ~j; j=edge[j].next){
//            v = edge[j].v;
//            cout<<i<<" "<<v<<" "<<edge[j].w<<endl;
//        }
//        cout<<endl<<endl;
//    }
    spfa();
    printf("%lld\n", dis[n]);
    return 0;
}

hdu 6346 更新km模板

原来蓝书上面的km算法太慢了，可能和增广路的局限有关
本题只能使用该方法
不论是zkw还是spfa版本的最小费用流都T了

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int N = 210;
int val[N][N];
LL lx[N],ly[N];
int linky[N];
LL pre[N];
bool vis[N];
bool visx[N],visy[N];
LL slack[N];
int n;
void bfs(int k) {
    LL px, py = 0,yy = 0, d;
    memset(pre, 0, sizeof(LL) * (n+2));
    memset(slack, inf, sizeof(LL) * (n+2));
    linky[py]=k;
    do {
        px = linky[py],d = INF, vis[py] = 1;
        for(int i = 1; i <= n; i++)
            if(!vis[i]) {
                if(slack[i] > lx[px] + ly[i] - val[px][i])
                    slack[i] = lx[px] + ly[i] - val[px][i], pre[i] = py;
                if(slack[i] < d)
                    d = slack[i], yy = i;
                }
        for(int i = 0; i <= n; i++)
            if(vis[i])
                lx[linky[i]] -= d, ly[i] += d;
            else
                slack[i] -= d;
        py = yy;
        }
    while(linky[py]);
    while(py)
        linky[py] = linky[pre[py]], py=pre[py];
    }
void KM() {
    memset(lx, 0, sizeof(int)*(n+2));
    memset(ly, 0, sizeof(int)*(n+2));
    memset(linky, 0, sizeof(int)*(n+2));
    for(int i = 1; i <= n; i++)
        memset(vis, 0, sizeof(bool)*(n+2)), bfs(i);
    }
int main() {
    int T;
    scanf("%d", &T);
    for(int _i = 1; _i <= T; _i++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &val[i][j]);
                val[i][j] = -val[i][j];
                }
            }
        KM();
        LL ans = 0;
        for(int i = 1; i <= n; ++i)
            ans += lx[i] + ly[i];
        printf("Case #%d: %I64d\n", _i, -ans);
        }
    return 0;
}

hdu 6172

bm线性递推模板测试
放入的项一般>=8项
这道题目a[i]开放之后满足线性特征，所以可以这样的写
大力猜开根号的式子满足线性递推的关系
update: 事实上网上的题解找规律退推出来的公式确实满足线性递推的关系
模板说明：
只要给出前面的几项，算法就能自动的调整需要的项数，然后进行快速幂运算
模数必须是质数

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(; b; b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
int t;
ll n;
namespace linear_seq
{
    const int N=10010;
    ll res[N],base[N],_c[N],_md[N];
    vector<int> Md;
    void mul(ll *a,ll *b,int k)
    {
        rep(i,0,k+k) _c[i]=0;
        rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for (int i=k+k-1; i>=k; i--) if (_c[i])
                rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    ll solve(ll n,VI a,VI b)   // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
    {
    //        printf("%d\n",SZ(b));
        ll ans=0,pnt=0;
        int k=SZ(a);
        assert(SZ(a)==SZ(b));
        rep(i,0,k) _md[k-1-i]=-a[i];
        _md[k]=1;
        Md.clear();
        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while ((1ll<<pnt)<=n) pnt++;
        for (int p=pnt; p>=0; p--)
        {
            mul(res,res,k);
            if ((n>>p)&1)
            {
                for(int i=k-1; i>=0; i--) res[i+1]=res[i];
                res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        rep(n,0,SZ(s))
        {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if (d==0) ++m;
            else if (2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L;
                B=T;
                b=d;
                m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        //rep(i,0,SZ(C))printf("%dx[%d]%s",C[i],i,i+1==SZ(C)?"=0\n":"+");
        return C;
    }
    ll gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};
int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%lld",&n);
        printf("%lld\n", linear_seq::gao(VI{31, 197, 1255, 7997, 50959, 324725, 2069239, 13185773, 84023455, 535421093, 411853810},n-2));
    }
}

牛客多校第八场那道环计数的问题也可以用这个算法来搞，但是好像很复杂的样子qaq.

bzoj 3262 陌上花开

又一次的把排序的return少了。。。
主要的过程就是第一维进行排序，第二维有贡献的加入树状数组，然后进行答案的统计
每增加一维偏序，时间复杂度就会增加一个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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
 
const int inf = 0x3f3f3f3f;
const int maxn = 100000+10;
const int K = 200100+10;
 
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
int n, m, k;
int c[K];
int lowbit(int x){return x&(-x);}
void add(int x,int val){
    while(x<=k){
        c[x] += val;
        x += lowbit(x);
    }
}
 
int query(int x){
    int ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
 
struct Node{
    int a, b, c, num, ans;
    bool operator < (const Node & x) const{
        if(a!=x.a) return a<x.a;
        else if(b!=x.b) return b < x.b;
        else return c<x.c;
    }
}node[maxn];
 
bool operator == (const Node& a, const Node & b) {
    if(a.a == b.a&&a.b==b.b&&a.c==b.c) return true;
    else return false;
}
 
bool cmp(Node a, Node b){
    if(a.b!=b.b) return a.b<b.b;
    else a.c<b.c;
}
void CDQ(int l, int r){
    if(l == r) return ;
    int mid = (l+r)>>1;
    CDQ(l, mid); CDQ(mid+1, r);
    sort(node+l, node+mid+1, cmp);
    sort(node+mid+1, node+r+1, cmp);
    int i = l;
    for(int j=mid+1; j<=r; j++){
        while(i<=mid&&node[j].b>=node[i].b){
            add(node[i].c, node[i].num);
            i++;
        }
        node[j].ans += query(node[j].c);
    }
    for(int j=l; j<i; j++) add(node[j].c, -node[j].num);
}
 
int ans[maxn];
 
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d%d%d", &node[i].a, &node[i].b, &node[i].c);
    sort(node+1, node+1+n);
    int tot = 0;
    for(int i=1; i<=n; i++){
        if(node[i] == node[i-1]) node[tot].num++;
        else node[++tot] = node[i], node[tot].num++;
    }
    int temp = n;
    n = tot;
    CDQ(1, n);
//    printf("after the sort:\n");
//    for(int i=1; i<=n; i++){
//        cout<<node[i].a<<" "<<node[i].b<<" "<<node[i].c<<" "<<node[i].ans<<" "<<node[i].num<<endl;
//    }
    for(int i=1; i<=n; i++) ans[node[i].ans+node[i].num-1] += node[i].num;
    for(int i=0; i<temp; i++) printf("%d\n", ans[i]);
    return 0;
}

四维偏序

题目链接
还原的下标写错了， 疯狂的T

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 5e4+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll ans;
struct Node{
    int a, b, c;
    bool flag;
}node[maxn], temp1[maxn], temp2[maxn];
ll c[maxn];
int lowbit(int x){return x&(-x);}
void add(int x, int val){
    while(x<=n) {
        c[x] += val;
        x += lowbit(x);
    }
}
ll query(int x){
    ll ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void CDQ2(int l, int r){
    if(l == r) return ;
    int mid = (l+r)>>1;
    CDQ2(l, mid), CDQ2(mid+1, r);
    int zuo = l, you = mid+1;
    int index = l;
    while(zuo<=mid||you<=r){
        if(you>r||(zuo<=mid&&temp1[zuo].b<temp1[you].b)){
            if(temp1[zuo].flag)  add(temp1[zuo].c, 1);
            temp2[index++] = temp1[zuo++];
        }
        else {
            if(!temp1[you].flag) ans += query(temp1[you].c);
            temp2[index++] = temp1[you++];
        }
    }
    for(int i=l; i<=mid; i++) if(temp1[i].flag) add(temp1[i].c, -1);
    for(int i=l; i<=r; i++){
        temp1[i] = temp2[i];
    }
}
void CDQ(int l, int r){
    if(l == r) return ;
    int mid = (l+r)>>1;
    //cout<<l<<" "<<r<<endl;
    CDQ(l, mid) ,CDQ(mid+1, r);
    int zuo=l, you=mid+1;
    int index = l;
    while(zuo<=mid||you<=r){
        if(you>r||(zuo<=mid&&node[zuo].a<node[you].a)) {temp1[index++]=node[zuo++]; temp1[index-1].flag = true;}
        else {temp1[index++] = node[you++];temp1[index-1].flag = 0;}
    }
    for(int i=l; i<=r; i++) node[i] = temp1[i];
    CDQ2(l, r);
}
int main()
{
    freopen("partial_order.in", "r", stdin);
    freopen("partial_order.out", "w", stdout);
    n=readint();
    for(int i=1; i<=n; i++) node[i].a=readint();
    for(int i=1; i<=n; i++) node[i].b=readint();
    for(int i=1; i<=n; i++) node[i].c=readint();
    CDQ(1, n);
    printf("%lld\n", ans);
    return 0;
}

上面的模板要改

四维的写法

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
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50010;
struct data
{
    int id,a,b,c,d;
    bool p;
} num[4][maxn];
int cnt[4];
ll bit[maxn];
int n;
ll ans=0;
bool Comp1(data x,data y)
{
    return x.a<y.a;
}
bool Comp2(data x,data y)
{
    return x.b<y.b;
}
//bool Comp3(data x,data y)
//{
//    return x.c<y.c;
//}
void Add(int x, int v)
{
    while (x<=n)
    {
        bit[x]+=v;
        x += (x&(-x));
    }
}
ll Sum(int x)
{
    ll sum=0;
    while (x>0)
    {
        sum+=bit[x];
        x -= (x&(-x));
    }
    return sum;
}
void Work()
{
    for (int i=1; i<=cnt[2]; i++)
        if (!num[2][i].p) Add(num[2][i].c,1);
        else ans+=Sum(num[2][i].c);
    for (int i=1; i<=cnt[2]; i++)
        if (!num[2][i].p) Add(num[2][i].c,-1);
}
//void CDQ3(int L,int R)
//{
//    if (L==R) return;
//    int mid=(L+R)>>1;
//    cnt[3]=0;
//    for (int i=L; i<=mid; i++) if (!num[2][i].p) num[3][ ++cnt[3] ]=num[2][i];
//    for (int i=mid+1; i<=R; i++) if (num[2][i].p) num[3][ ++cnt[3] ]=num[2][i];
//    if (cnt[3])
//    {
//        sort(num[3]+1,num[3]+cnt[3]+1,Comp3);
//        Work();
//    }
//    CDQ3(L,mid);
//    CDQ3(mid+1,R);
//}
void CDQ2(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    cnt[2]=0;
    for (int i=L; i<=mid; i++) if (!num[1][i].p) num[2][ ++cnt[2] ]=num[1][i];
    for (int i=mid+1; i<=R; i++) if (num[1][i].p) num[2][ ++cnt[2] ]=num[1][i];
    if (cnt[2])
    {
        sort(num[2]+1,num[2]+cnt[2]+1,Comp2);
        Work();
        //CDQ3(1,cnt[2]);
    }
    CDQ2(L,mid);
    CDQ2(mid+1,R);
}
void CDQ1(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    cnt[1]=0;
    for (int i=L; i<=mid; i++) num[1][ ++cnt[1] ]=num[0][i],num[1][ cnt[1] ].p=false;
    for (int i=mid+1; i<=R; i++) num[1][ ++cnt[1] ]=num[0][i],num[1][ cnt[1] ].p=true;
    if (cnt[1])
    {
        sort(num[1]+1,num[1]+cnt[1]+1,Comp1);
        //Work();
        CDQ2(1,cnt[1]);
    }
    CDQ1(L,mid);
    CDQ1(mid+1,R);
}
int main()
{
    freopen("partial_order.in","r",stdin);
    freopen("partial_order.out","w",stdout);
    scanf("%d",&n);
    for (int i=1; i<=n; i++) num[0][i].id=i;
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].a);
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].b);
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].c);
    //system("pause");
    //for (int i=1; i<=n; i++) scanf("%d",&num[0][i].d);
    CDQ1(1,n);
    printf("%lld\n",ans);
    return 0;
}

五维偏序

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
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50010;
struct data
{
    int id,a,b,c,d;
    bool p;
} num[4][maxn];
int cnt[4];
ll bit[maxn];
int n;
ll ans=0;
bool Comp1(data x,data y)
{
    return x.a<y.a;
}
bool Comp2(data x,data y)
{
    return x.b<y.b;
}
bool Comp3(data x,data y)
{
    return x.c<y.c;
}
void Add(int x, int v)
{
    while (x<=n)
    {
        bit[x]+=v;
        x += (x&(-x));
    }
}
ll Sum(int x)
{
    ll sum=0;
    while (x>0)
    {
        sum+=bit[x];
        x -= (x&(-x));
    }
    return sum;
}
void Work()
{
    for (int i=1; i<=cnt[3]; i++)
        if (!num[3][i].p) Add(num[3][i].d,1);
        else ans+=Sum(num[3][i].d);
    for (int i=1; i<=cnt[3]; i++)
        if (!num[3][i].p) Add(num[3][i].d,-1);
}
void CDQ3(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    cnt[3]=0;
    for (int i=L; i<=mid; i++) if (!num[2][i].p) num[3][ ++cnt[3] ]=num[2][i];
    for (int i=mid+1; i<=R; i++) if (num[2][i].p) num[3][ ++cnt[3] ]=num[2][i];
    if (cnt[3])
    {
        sort(num[3]+1,num[3]+cnt[3]+1,Comp3);
        Work();
    }
    CDQ3(L,mid);
    CDQ3(mid+1,R);
}
void CDQ2(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    cnt[2]=0;
    for (int i=L; i<=mid; i++) if (!num[1][i].p) num[2][ ++cnt[2] ]=num[1][i];
    for (int i=mid+1; i<=R; i++) if (num[1][i].p) num[2][ ++cnt[2] ]=num[1][i];
    if (cnt[2])
    {
        sort(num[2]+1,num[2]+cnt[2]+1,Comp2);
        //Work();
        CDQ3(1,cnt[2]);
    }
    CDQ2(L,mid);
    CDQ2(mid+1,R);
}
void CDQ1(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    cnt[1]=0;
    for (int i=L; i<=mid; i++) num[1][ ++cnt[1] ]=num[0][i],num[1][ cnt[1] ].p=false;
    for (int i=mid+1; i<=R; i++) num[1][ ++cnt[1] ]=num[0][i],num[1][ cnt[1] ].p=true;
    if (cnt[1])
    {
        sort(num[1]+1,num[1]+cnt[1]+1,Comp1);
        //Work();
        CDQ2(1,cnt[1]);
    }
    CDQ1(L,mid);
    CDQ1(mid+1,R);
}
int main()
{
    freopen("partial_order_two.in","r",stdin);
    freopen("partial_order_two.out","w",stdout);
    scanf("%d",&n);
    for (int i=1; i<=n; i++) num[0][i].id=i;
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].a);
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].b);
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].c);
    //system("pause");
    for (int i=1; i<=n; i++) scanf("%d",&num[0][i].d);
    CDQ1(1,n);
    printf("%lld\n",ans);
    return 0;
}

bzoj 纸箱生产

树状数组维护区间的最值+CDQ分治
注意维护重点的情况

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
//#include<cstdio>
//#include<cstring>
//#include<algorithm>
//#include<iostream>
//#include<queue>
//#include<cmath>
//#include<map>
//#include<stack>
//#include<set>
//#include<bitset>
//using namespace std;
//typedef long long ll;
//typedef unsigned long long ull;
//typedef pair<int, int> pii;
//#define pb(x) push_back(x)
//#define cls(x, val) memset(x, val, sizeof(x))
//#define fi first
//#define se second
//#define mp(x, y) make_pair(x, y)
//#define inc(i, l, r) for(int i=l; i<=r; i++)
//
//const int inf = 0x3f3f3f3f;
//const int maxn = 5e4+10;
//
//int readint()
//{
//    int x=0,f=1;char ch=getchar();
//    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
//    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
//    return x*f;
//}
//
//int a, p, n;
//ll ans;
//
//
//struct Node{
//    int a, b, c;
//    bool flag;
//}node[maxn], temp1[maxn], temp2[maxn];
//ll c[maxn];
//
//int lowbit(int x){return x&(-x);}
//void add(int x, int val){
//    while(x<=n) {
//        c[x] += val;
//        x += lowbit(x);
//    }
//}
//
//ll query(int x){
//    ll ans = 0;
//    while(x>0){
//        ans += c[x];
//        x -= lowbit(x);
//    }
//    return ans;
//}
//void CDQ2(int l, int r){
//    if(l == r) return ;
//    int mid = (l+r)>>1;
//    CDQ2(l, mid), CDQ2(mid+1, r);
//    int zuo = l, you = mid+1;
//    int index = l;
//    while(zuo<=mid||you<=r){
//        if(you>r||(zuo<=mid&&temp1[zuo].b<temp1[you].b)){
//            if(temp1[zuo].flag)  add(temp1[zuo].c, 1);
//            temp2[index++] = temp1[zuo++];
//        }
//        else {
//            if(!temp1[you].flag) ans = max(query(temp1[you].c)+1, ans);
//            temp2[index++] = temp1[you++];
//        }
//    }
//    for(int i=l; i<=mid; i++) if(temp1[i].flag) add(temp1[i].c, -1);
//    for(int i=l; i<=r; i++){
//        temp1[i] = temp2[i];
//    }
//}
//
//void CDQ(int l, int r){
//    if(l == r) return ;
//    int mid = (l+r)>>1;
//    //cout<<l<<" "<<r<<endl;
//    CDQ(l, mid) ,CDQ(mid+1, r);
//    int zuo=l, you=mid+1;
//    int index = l;
//    while(zuo<=mid||you<=r){
//        if(you>r||(zuo<=mid&&node[zuo].a<node[you].a)) {temp1[index++]=node[zuo++]; temp1[index-1].flag = true;}
//        else {temp1[index++] = node[you++];temp1[index-1].flag = 0;}
//    }
//    for(int i=l; i<=r; i++) node[i] = temp1[i];
//    CDQ2(l, r);
//}
//
//int main()
//{
//
//    a=readint(), p=readint(), n=readint();
//    int temp = a%p;
//    int num[4];
//    for(int i=1; i<=n; i++){
//        num[1] = node[i].a = temp;
//        temp = temp*a%p;
//        num[2] = node[i].b = temp;
//        temp = temp*a%p;
//        num[3] = node[i].c = temp;
//        temp = temp*a%p;
//        sort(num+1, num+4);
//        node[i].a=num[1], node[i].b=num[2], node[i].c=num[3];
//    }
//    for(int i=1; i<=n; i++){
//        cout<<node[i].a<<" "<<node[i].b<<" "<<node[i].c<<endl;
//    }
//    CDQ(1, n);
//    printf("%lld\n", ans);
//    return 0;
//}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 50000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
ll a, p;
int c[maxn*3];
int mx;
int lowbit(int x){return x&(-x);}
void add(int x,int val){
    while(x<=mx){
        c[x] = max(val, c[x]);
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans = max(c[x], ans);
        x -= lowbit(x);
    }
    return ans;
}
void erase(int x){
    while(x<=mx){
        c[x] = 0;
        x += lowbit(x);
    }
}
struct Node{
    ll a, b, c;
    int ans;
    bool operator < (const Node & x) const{
        if(c!=x.c) return c<x.c;
        else if(a!=x.a) return a<x.a;
        return b<x.b;
    }
}node[maxn];
bool cmp(Node a, Node b){
    if(a.a!=b.a) return a.a<b.a;
    else return   a.b<b.b;
}
bool operator == (Node a, Node b){
    return a.a == b.a && a.b==b.b&&a.c == b.c;
}
//bool cmp(Node a, Node b){
//    if(a.b!=b.b) return a.b<b.b;
//    else a.c<b.c;
//}
void CDQ(int l, int r){
    if(l == r)return;
    int mid=(l+r)>>1, i, j, x=1e9;
//    for(i=l;i<r;i++)if(node[i].c!=node[i+1].c && abs(i-mid)<abs(x-mid))x=i;
//    if(x == 1e9)return;
    //mid = x;
    CDQ(l,mid), sort(node+l,node+mid+1,cmp), sort(node+mid+1,node+r+1,cmp);
    for(i=l,j=mid+1;j<=r;j++)
    {
        for(;i<=mid && node[i].a<node[j].a;i++) add(node[i].b,node[i].ans);
        node[j].ans=max(node[j].ans,query(node[j].b-1)+1);
    }
    for(j=l;j<i;j++)erase(node[j].b);
    sort(node+mid+1,node+r+1), CDQ(mid+1,r);
}
ll raw[maxn*3];
int main()
{
    a=readint(), p=readint(), n=readint();
    ll temp = a%p;
    ll num[4];
    int tot = 1;
    for(int i=1; i<=n; i++){
        raw[tot++]=num[1] = node[i].a = temp;
        temp = temp*a%p;
        raw[tot++]=num[2] = node[i].b = temp;
        temp = temp*a%p;
        raw[tot++]=num[3] = node[i].c = temp;
        temp = temp*a%p;
        sort(num+1, num+4);
        node[i].a=num[1], node[i].b=num[2], node[i].c=num[3];
    }
    sort(raw+1, raw+tot);
    int sz = unique(raw+1, raw+tot)-raw-1;
    ll mxx = 0;
    for(int i=1; i<=n; i++){
        node[i].a = lower_bound(raw+1, raw+sz, node[i].a)-raw;
        mxx = max(node[i].a, mxx);
        node[i].b = lower_bound(raw+1, raw+sz, node[i].b)-raw;
        mxx = max(node[i].b, mxx);
        node[i].c = lower_bound(raw+1, raw+sz, node[i].c)-raw;
        mxx = max(mxx, node[i].c);
        node[i].ans = 1;
    }
//    for(int i=1; i<=n; i++){
//        cout<<node[i].a<<" "<<node[i].b<<" "<<node[i].c<<endl;
//    }
    sort(node+1, node+1+n);
    tot = 0;
    for(int i=1; i<=n; i++){
        if(node[i-1] == node[i]) continue;
        else {
            node[++tot] = node[i];
            node[tot].ans = 1;
        }
    }
    temp = tot;
    n = tot;
    mx = mxx;
    CDQ(1, n);
    int ans = 0;
    for(int i=1; i<=tot; i++) ans = max(ans, node[i].ans);
    printf("%d\n", ans);
    return 0;
}
/*
23123 13254354 2344
*/

牛客国庆练习–快速乘法

标准的题解
抖评测姬的代码1951ms，简直害怕

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
 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
ll readint()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll a0, a1, m0, m1, c, M, k, M4;
ll ans;
ll res;
inline ll fast_mult(ll a, ll b) {
    return a * b - (ll)((long double)a / M4 * b) * M4;
}
int main()
{
    int _;
    _=readint();
    while (_--) {
        scanf("%lld%lld%lld%lld%lld%lld%lld", &a0, &a1, &m0, &m1, &c, &M, &k);
        //a0=readint(), a1=readint(), m0=readint(), m1=readint();
        //c=readint(), M=readint(), k=readint();
        M4 = (ll)4e18 / M * M;
        ans = fast_mult(a0, a1);
        for (int i = 2; i <= k; ++i) {
            res = fast_mult(m0, a1) + fast_mult(m1, a0);
            if (res >= M4) res -= M4;
            res = res + c;
            ans = fast_mult(ans, res);
            a0 = a1, a1 = res;
        }
        printf("%lld\n", (ans % M + M) % M);
    }
    return 0;
}

牛客国庆练习day3 stone

题目大意：
有n堆石子，每个人可以轮流取a~b堆石子。
胜利的条件：

  1. 把一堆里面的石子取完

  2. 对手不能操作
    讨论一堆的sg[]
    x=x>=a, 直接输出结果，不能将其sg[]设为1！！！！

    注意b==1的特判

    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
     #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+10;
    int sg[maxn];
    bool vis[maxn];
    int x[maxn];
    int n, a, b;
    //void table(){
    //    for(int i=a; i<=b; i++){
    //        sg[i] = -1;
    //    }
    //    for(int i=1; i<=100; i++){
    //        memset(vis, 0, sizeof(vis));
    //        if(i>=a&&i<=b) continue;
    //        for(int j=i-b; j<=i-a; j++){
    //            if(j>=0&&sg[j]!=-1){
    //                vis[sg[j]] = true;
    //            }
    //        }
    //        for(int j=0; j<=i; j++){
    //            if(!vis[j]){
    //                sg[i] = j;
    //                break;
    //            }
    //        }
    //    }
    //    for(int i=1; i<=100; i++){
    //        if(i>b){
    //            cout<<i<<" "<<sg[i]<<" ";
    //            //偏移
    //            i -= b;
    //            cout<<(i%(a+b))/a<<endl;
    //            i+=b;
    //        }
    //    }
    //}
    int dfs(int num){
        if(num<a) return 0;
        if(a == 1){
            return num%(a+b);
        }
        else{
            num -= b;
            num = num%(a+b)/a;
            if(num == 0) return 1;
            else if(num == 1) return 0;
            return num;
        }
    }
    int main(){
        ios::sync_with_stdio(false);
    //    while(~scanf("%d%d", &a, &b)){
    //        table();
    //    }
        int _;
        scanf("%d", &_);
        while(_--){
            scanf("%d%d%d", &n, &a, &b);
            bool flag = false;
            for(int i=1; i<=n; i++){
                scanf("%d", &x[i]);
                if(x[i]>=a&&x[i]<=b){
                    flag = true;
                }
            }
            if(flag){
                printf("Yes\n");
                continue;
            }
            int ans = 0;
            for(int i=1; i<=n; i++){
                ans ^= dfs(x[i]);
            }
            if(ans) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }

牛客day2A

矩阵乘法，最暴力的乘法，正解要按位亦或

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
#include <bits/stdc++.h>
using namespace std;
int n, m, p;
int A[4100][70];
bool B[70][4100];
char s[70];
int ans[4096+10][4096+10];
int main()
{
    while(~scanf("%d%d%d", &n, &p, &m)){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=p; j++){
                scanf("%x", &A[i][j]);
            }
        }
        for(int i=1; i<=m; i++){
            scanf("%s", s+1);
            for(int j=1; j<=p; j++){
                B[j][i] = s[j]-'0';
            }
        }
        int ans=0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                int tep=0;
                for(int k=1; k<=p; k++)
                {
                    tep+=A[i][k]*B[k][j];
                }
                ans^=tep;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

update:运用矩阵乘法的小技巧419ms整整快了一倍

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
#include <bits/stdc++.h>
using namespace std;
int n, m, p;
int A[4100][70];
bool B[70][4100];
char s[70];
int ans[4096+10][4096+10];
int main()
{
    while(~scanf("%d%d%d", &n, &p, &m)){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=p; j++){
                scanf("%x", &A[i][j]);
            }
        }
        for(int i=1; i<=m; i++){
            scanf("%s", s+1);
            for(int j=1; j<=p; j++){
                B[j][i] = s[j]-'0';
            }
        }
        int aans=0;
        for(int i=1; i<=n; i++){
            for(int k=1; k<=p; k++){
                for(int j=1; j<=m; j++)
                {
                    ans[i][j] = ans[i][j]+A[i][k]*B[k][j];
                }
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++) aans^=ans[i][j];
        }
        printf("%d\n", aans);
    }
    return 0;
}

牛客国庆训练 day6

具有现实意义
类似于ccpc网络赛的最后一题
先进行离散化，然后进行相应的状态转移就可以了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int x[maxn], y[maxn], z[maxn], dis[maxn<<1];
int u[maxn], v[maxn];
ll dp[maxn][maxn], sum[maxn][maxn];
int tot=1;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
        dis[tot++]=x[i];
        dis[tot++]=y[i];
    }
    //cout<<tot<<endl;
    sort(dis+1, dis+tot);
    int sz = unique(dis+1, dis+tot)-dis-1;
    for(int i=1; i<=n; i++){
        u[i] = lower_bound(dis+1, dis+1+sz, x[i])-dis;
        v[i] = lower_bound(dis+1, dis+1+sz, y[i])-dis;
        sum[u[i]][v[i]] += z[i];
    }
    //[i, j]整个矩形的权值
    for(int i=1; i<=sz; i++){
        for(int j=1; j<=sz; j++) sum[i][j] += sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    }
    ll ans = 0;
    for(int i=1; i<=sz; i++){
        for(int j=1; j<=sz; j++){
            dp[i][j]=max(dp[i-1][j]+sum[i-1][j]*(dis[i]-dis[i-1]-1),dp[i][j]);
            dp[i][j]=max(dp[i][j-1]+sum[i][j-1]*(dis[j]-dis[j-1]-1),dp[i][j]);
            dp[i][j]+=sum[i][j];
            if(dis[i]+dis[j]<=m)ans=max(ans,dp[i][j]+sum[i][j]*(m-dis[i]-dis[j]));
            else break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

国庆day4 树链统计

统计方案的划分在代码里面注释了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int mod = 998244353;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll a[maxn];
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    ll sum = 1;
    //以中心点为根的方案数
    for(int i=1; i<=n; i++){
        sum = sum*(a[i]+1)%mod;
    }
    for(int i=1; i<=n; i++){
        //每一条链单独成一棵树，或者是单独一个点
        sum = (sum+(a[i]-1)*a[i]/2+a[i])%mod;
    }
    printf("%lld\n", sum);
    return 0;
}

牛客国庆day4 树链博弈

统计每一层的黑色点的个数是否存在奇数；
若存在，那么先手必胜；否则后手必胜

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int color[maxn];
int tot_black[maxn];
int tot, head[maxn];
struct Node{
    int v, next;
}node[maxn];
void init(){
    tot = 0;
    cls(head, -1);
}
void add_edge(int u, int v){
    node[tot].v=v, node[tot].next=head[u], head[u] = tot++;
}
bool vis[maxn];
int d[maxn];
void bfs(int s){
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    d[s] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=head[u]; ~i; i=node[i].next){
            int v = node[i].v;
            if(!vis[v]){
                d[v] = d[u]+1;
                q.push(v);
            }
        }
    }
}
int main()
{
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &color[i]);
    int u, v;
    for(int i=1; i<=n-1; i++) {
        scanf("%d%d", &u, &v);
        add_edge(u, v),add_edge(v, u);
    }
    bfs(1);
    for(int i=1; i<=n; i++){
        if(color[i]){
            tot_black[d[i]]++;
        }
    }
    bool flag = false;
    for(int i=1; i<=n; i++){
        if(tot_black[i]%2){
            flag = true;
        }
    }
    if(!flag) printf("Second\n");
    else printf("First\n");
    return 0;
}

day1 Princess Principal

检测一段区间内的括号是否是匹配的
记录括号的位置

解题思路：预处理，通常判断是否是正确的括号序都用栈去判断，那么我们就先判断整个串出否是括号序，在栈的变化过程中，我们用一个数组记录某时刻栈顶是哪个元素即可。最后我们判断栈顶是否相等，即可判断这个区间是否是括号序。

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 <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n, m, q;
int num[maxn];
int pos[maxn];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &num[i]);
    }
    stack<int> s;
    while(!s.empty()) s.pop();
    for(int i=1; i<=n; i++){
        if(s.empty()) s.push(i);
        else if(num[i]/2 == num[s.top()]/2 && num[i] == num[s.top()]+1) s.pop();
        else s.push(i);
        if(!s.empty()) pos[i] = s.top();
    }
    int l, r;
    for(int i=1; i<=q; i++){
        scanf("%d%d", &l, &r);
        if(pos[l-1] == pos[r]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

day3 coloring

黑白染色+统计奇环， 感觉还是比较好写的

day3 shopping

注意去除multiset里面的元素的写法。。。
已经被坑两次了。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[maxn], b[maxn];
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        int chair = 0;
        double ans = 0;
        multiset<int> s;
        s.clear();
        for(int i=1; i<=n; i++){
            scanf("%d%d", &a[i], &b[i]);
            if(s.size()<m) s.insert(a[i]);
            else if(*s.begin()<a[i]) {
                    ans += *s.begin();
                    multiset<int>::iterator it = s.find(*s.begin());
                    s.erase(it);
                    s.insert(a[i]);
            }
            else ans += a[i];
            if(b[i] == 1) chair++;
        }
        multiset<int>::iterator it;
        if(chair>=s.size()){
            for(it=s.begin(); it!=s.end(); it++){
                ans += 1.0*(*it)/2;
            }
        }
        else{
            int res = s.size()-chair;
            for(it=s.begin(); it!=s.end(); it++){
                if(res>0) ans += 1.0*(*it), res--;
                else ans += 1.0*(*it)/2;
            }
        }
        printf("%.1lf\n", ans);
    }
    return 0;
}
/*
2
4 2
5 1
6 1
7 1
8 1
*/

day3 大都市

1ll<<60,注意后缀ll, 否则默认为int类型的位移

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, p;
struct Edge{
    int v, next, w;
}edge[maxn<<1];
int tot, head[maxn];
void init(){
    tot = 0, cls(head, -1);
}
void add_edge(int u, int v, ll w){
    edge[tot].v=v, edge[tot].w=w, edge[tot].next=head[u], head[u] = tot++;
}
int x[maxn];
struct Node{
    ll w;
    int u, v;
    bool operator < (const Node & b) const{
        return w>b.w;
    }
    Node(ll _w, int _u, int _v):w(_w), u(_u), v(_v){}
};
priority_queue<Node> pq;
ll dis[maxn];
ll ans[maxn];
int belong[maxn];
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    init();
    for(int i=1; i<=p; i++) scanf("%d", &x[i]), pq.push(Node(0, x[i], x[i]));
    int u, v;
    ll w;
    for(int i=1; i<=m; i++){
        scanf("%d%d%lld", &u, &v, &w);
        add_edge(u, v, w), add_edge(v, u, w);
    }
    while(!pq.empty()){
        Node temp = pq.top();
        pq.pop();
        u = temp.u, v=temp.v, w = temp.w;
        if(belong[v]) continue;
        belong[v] = u;
        dis[v] = temp.w;
        for(int i=head[v]; ~i; i=edge[i].next){
            pq.push(Node(temp.w+1ll*edge[i].w, u, edge[i].v));
        }
    }
    for(int i=1; i<=n; i++) ans[i] = (1ll<<60);
    for(int u=1; u<=n; u++){
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(belong[u] == belong[v]) continue;
            ans[belong[u]] = min(ans[belong[u]], dis[u]+dis[v]+1ll*edge[i].w);
            ans[belong[v]] = min(ans[belong[v]], dis[u]+dis[v]+1ll*edge[i].w);
        }
    }
    for(int i=1; i<=p; i++){
        printf("%lld%c", ans[x[i]], i==p?'\n': ' ');
    }
    return 0;
}

10.7cf练习

注意暴力的姿势，先统计满足一个条件的方案，然后再减去不满足的条件的方案数
__builtin_popcount不能统计long long 类型的1的个数

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int maxn = 3e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll a[maxn];
int cnt[maxn];
int pre[maxn];
int main()
{
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        int temp=0;
        while(a[i]){
            if(a[i]&1) temp++;
            a[i]>>=1;
        }
        cnt[i] = temp;
    }
    for(int i=1; i<=n; i++) pre[i] = pre[i-1]+cnt[i];
    ll ans = 0, odd=0, even=0;
    //统计有多少个偶数个1的区间，用了前缀和的思想
    for(int i=1; i<=n; i++){
        if(pre[i]%2==0){
            ans += (even+1);
            even++;
        }
        else {
            ans+=odd;
            odd++;
        }
        //减去一个数字的
        if(pre[i]%2 == pre[i-1]%2){
            ans--;
        }
    }
    //去除不满足条件的区间，因为一个数最多59个1，暴力扫描
    for(int i=1; i<=n; i++){
        ll sum = cnt[i], mx = cnt[i];
        for(int j=i-1; j>=1&&j>=i-61; j--){
            sum += cnt[j], mx=max(mx, 1ll*cnt[j]);
            if(mx>sum-mx&&sum%2==0) ans--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

带权中位数

数轴上面若干个权值，然后找到一个点，集中到一个点上面，然后使得代价最小$\abs(x-x_i) \* w_i$
这个问题就是带权中位数解决
题解
这道题要维护区间的点值在哪里、

现在每一个货仓i里有wi个货物。
排序后，找到第一个X，使∑Xi=1ai≥∑ni=X+1ai，X就是最优解。

感觉这种将区间的移动转变为带权中位数的移动的思想很巧妙啊，证明还不是太会emmm
代码参考
区间的带权中位数就是二分+BIT维护就可以了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
const ll mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, q;
int a[maxn], w[maxn];
ll c1[maxn], c2[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(ll &x, ll y){
    x += y;
    if(x>=mod) x-=mod;
}
void add1(int x, int val){
    while(x<=n){c1[x] += val; x += lowbit(x);}
}
void add2(int x, int val){
    while(x<=n){add(c2[x], val); x+=lowbit(x);}
}
ll query1(int x){
    ll ans = 0;
    while(x>0){
        ans += c1[x];
        x -= lowbit(x);
    }
    return ans;
}
ll query2(int x){
    ll ans = 0;
    while(x>0){
        ans += c2[x];
        ans %= mod;
        x -= lowbit(x);
    }
    return ans;
}
void op1(int x, int y){
    add1(x, -w[x]);
    add2(x, (-1ll*a[x]*w[x]%mod+mod)%mod);
    w[x] = y;
    add1(x, w[x]);
    add2(x, 1ll*a[x]*w[x]%mod);
}
void op2(int l, int r){
    ll sum = query1(r)-query1(l-1);
    int le = l, ri=r, mid;
    ll ans=r;
    while(le<=ri){
        mid = (le+ri)>>1;
        if(2*(query1(mid)-query1(l-1))>=sum) {
            ri=mid-1,ans=mid;
        }
        else le=mid+1;
    }
    ll big1 = ((query2(r)-query2(ans))%mod+mod)%mod, big2 = ((1ll*(((query1(r)-query1(ans))%mod+mod)%mod)*a[ans])%mod);
    ll small1 = (((1ll*((query1(ans)-query1(l-1))%mod+mod)%mod)*a[ans]+mod)%mod), small2 = ((query2(ans)-query2(l-1))%mod+mod)%mod;
    ans = 0;
    ans = big1-big2+small1-small2;
    ans = (ans%mod+mod)%mod;
    printf("%I64d\n", ans);
}
int main()
{
    ios::sync_with_stdio(false);
    scanf("%d%d", &n, &q);
    //这样可以映射到[1, n]选择一个集中的点
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), a[i] = a[i]-i+n;
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    for(int i=1; i<=n; i++){
        add1(i, w[i]);
        add2(i, 1ll*w[i]*a[i]%mod);
    }
    int x, y;
    for(; q>0; q--){
        scanf("%d%d", &x, &y);
        if(x<0) op1(-x, y);
        else op2(x, y);
    }
    return 0;
}
/*
4 10
1 333333333 666666666 1000000000
1000000000 1000000000 1000000000 1000000000
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
*/

分配椅子的方案

比赛的链接

智商完全不够啊

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll l[maxn], r[maxn];
int n;
int main()
{
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d%d", &l[i], &r[i]);
    }
    ll ans = n;
    sort(l+1, l+1+n), sort(r+1, r+1+n);
    for(int i=1; i<=n; i++){
        ans += max(r[i], l[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

C 最大规模的矩阵

最大规模的矩阵，使得它的权值和小于等于k

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3+10;
ll a[maxn], b[maxn];
int n, m;
ll k;
int main(){
    ios::sync_with_stdio(false);
    scanf("%d%d", &n ,&m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=m; i++) scanf("%d", &b[i]);
    scanf("%lld", &k);
    int ans = 0;
    for(int i=1; i<=n; i++) a[i] += a[i-1];
    ll s1, s2;
    int l, r;
    for(int i=1; i<=n; i++){
        s1 = 1e9;
        for(int j=1; j<=n-i+1; j++)s1 = min(s1, a[j+i-1]-a[j-1]);
        s2 = b[1];
        l = r = 1;
        while(r<=m){
            if(s1*s2<=k) ans = max(ans, i*(r-l+1)), s2+=b[++r];
            else s2 -= b[l++];
        }
    }
    printf("%d\n", ans);
    return 0;
}

round513

先维护每一个节点的深度和子树的大小
公式显示不出来，凑活着看吧emmmm
考虑新边的贡献：
$\sum_{i=1}^{n} sz[i] \times (n-sz[i])$
老边的贡献：
$ 奇深度节点的个数 \times 偶深度节点的个数$
最后答案除以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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int v, next;
}node[maxn<<1];
int tot, head[maxn];
void init(){
    tot =0, cls(head, -1);
}
void add_edge(int u, int v){
    node[tot].v=v,node[tot].next=head[u], head[u]=tot++;
}
int sz[maxn], d[maxn];
void dfs(int u, int fa){
    sz[u] = 1;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == fa) continue;
        d[v] = d[u]+1;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
int main()
{
    init();
    scanf("%d", &n);
    int u, v;
    for(int i=1; i<=n-1; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v), add_edge(v, u);
    }
    dfs(1, 0);
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans += 1ll*(n-sz[i])*sz[i];
    }
    int tot = 0;
    for(int i=1; i<=n; i++){
        if(d[i]%2) tot++;
    }
    ans += 1ll*tot*(n-tot);
    printf("%lld\n", ans/2);
    return 0;
}

round 514 div2

给定一棵树形的结构，每一个节点有一个点权，将树划分成若干条链，然后每条立链的点权的大小不超过S， 节点的个数不超过L
问最少要划分几条

贪心的从叶子节点不断的删点就可以了，一个节点可能会被覆盖多次，好像不会出现交差的情况

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, L;
ll S;
int w[maxn];
int fa[maxn];
bool vis[maxn];
int main()
{
    scanf("%d%d%lld", &n, &L, &S);
    int mx = -1;
    for(int i=1; i<=n; i++) scanf("%d", &w[i]), mx = max(mx, w[i]);
    fa[1] = 1;
    for(int i=2; i<=n; i++){
        scanf("%d", &fa[i]);
    }
    if(1ll*mx>S){
        printf("-1\n");
        return 0;
    }
    int ans = 0;
    int pre;
    for(int i=n; i>=1; i--){
        if(!vis[i]){
            int now=fa[i], nowl=1;
            ll nows=w[i];
            ans++;
            vis[i] = true;
            while(nowl<=L-1&&nows<=S-w[now]){
                vis[now] = true;
                nowl++, nows += w[now];
                pre = now;
                now = fa[now];
                if(pre == now) break;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

未解决的问题

本文标题:代码堆

文章作者:Babydragon

发布时间:2018-09-10, 00:13:17

最后更新:2018-10-09, 18:29:48

原始链接:http://baolintian.github.io/2018/09/10/代码堆/

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

文章目录
  1. 1. loj三道有上下界的模板题
  2. 2. bzoj 1997
  3. 3. poj 3417
  4. 4. bzoj 2791
  5. 5. 最基础的并查集
  6. 6. xdoj1368
  7. 7. bzoj 太鼓达人
  8. 8. bzoj杀人游戏
  9. 9. poj3468
  10. 10. xdoj 诺爷信号
  11. 11. ecl final sos
  12. 12. ecl final 替罪羊
  13. 13. master of sequence
    1. 13.1. 题解
    2. 13.2. 新的一道题目
      1. 13.2.1. 解答
  14. 14. uva
  15. 15. uva 10047
  16. 16. uva 10054
  17. 17. uva 10905
  18. 18. uva 11100
  19. 19. poj 3802
  20. 20. uva11134
  21. 21. codeforces round 510 div2 D
  22. 22. 虚树模板题 消耗战
  23. 23. bzoj 1001
  24. 24. hdu 6228
  25. 25. bzoj 1997
  26. 26. 洛谷2764
  27. 27. hdu 1565 方格取数
  28. 28. poj 3155 最大密集子图
  29. 29. luogu 1719
  30. 30. uva 10827 球面的矩阵的权值最大和
  31. 31. bzoj2791
  32. 32. ecf 51 F
  33. 33. bzoj 1002
  34. 34. bzoj 1430猴子打架
  35. 35. bzoj 1003
  36. 36. bz0j1006
  37. 37. uva1330 Game City
  38. 38. uva10891
  39. 39. la 3902 Network
  40. 40. hiho 北京网络赛
  41. 41. rich game hduoj
  42. 42. knight 学会用python进行拟合函数
  43. 43. la 5052 基因组进化
  44. 44. xdoj 1275
  45. 45. poj 2559 histgram 最大矩形的面积
  46. 46. joyoi 小猫爬山
  47. 47. luogu 2243维修电路
  48. 48. la 3716 基因突变
  49. 49. xdoj 1269 炸弹人
  50. 50. xdoj 1104
  51. 51. la 4094 思维
  52. 52. uva 11389
  53. 53. bzoj 4152
  54. 54. hdu 6346 更新km模板
  55. 55. hdu 6172
  56. 56. bzoj 3262 陌上花开
  57. 57. 四维偏序
  58. 58. 上面的模板要改
  59. 59. 五维偏序
  60. 60. bzoj 纸箱生产
  61. 61. 牛客国庆练习–快速乘法
  62. 62. 牛客国庆练习day3 stone
  63. 63. 牛客day2A
  64. 64. 牛客国庆训练 day6
  65. 65. 国庆day4 树链统计
  66. 66. 牛客国庆day4 树链博弈
  67. 67. day1 Princess Principal
  68. 68. day3 coloring
  69. 69. day3 shopping
  70. 70. day3 大都市
  71. 71. 10.7cf练习
  72. 72. 带权中位数
  73. 73. 分配椅子的方案
  74. 74. C 最大规模的矩阵
  75. 75. round513
  76. 76. round 514 div2
  77. 77. 未解决的问题
{{ live2d() }}