代码堆2

ACM

之前记录了一下，敲了有意义的题大概70~80道，很多题看了题解，希望以后减少看题解的次数吧

codeforces 1064

link
注意贡献，无用的贡献会排掉后面有用的贡献，所以用优先队列优先维护有贡献的点。

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<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 r, c;
int x, y;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int dx[5] = {1, -1, 0, 0};
int dy[5] = {0, 0, 1, -1};
struct Node{
    int x, y;
    int left, right;
    Node(int _x, int _y, int _left, int _right):x(_x), y(_y), left(_left), right(_right){}
    bool operator < (const Node& b) const{
        return (left+right)>b.left+b.right;
    }
};
bool check(int x, int y){
    if(x<=0||x>n||y<=0||y>m) return false;
    if(vis[x][y]) return false;
    if(mp[x][y] == '*') return false;
    return true;
}
void bfs(){
    cls(vis, 0);
    priority_queue<Node> q;
    while(!q.empty()) q.pop();
    q.push(Node(r, c, 0, 0));
    while(!q.empty()){
        Node temp = q.top();
        q.pop();
        int sx = temp.x, sy = temp.y, l=temp.left, r=temp.right;
        if(vis[sx][sy]) continue;
        vis[sx][sy] = true;
        int nl, nr;
        for(int i=0; i<4; i++){
            int nx = sx+dx[i];
            int ny = sy+dy[i];
            if(i == 0) nl=l, nr=r;
            else if(i == 1) nl=l, nr=r;
            else if(i == 2) nl=l, nr=r+1;
            else nl=nl+1, nr=r;
            if(check(nx, ny)&&nl<=x&&nr<=y){
                q.push(Node(nx, ny, nl, nr));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>r>>c>>x>>y;
    for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++) cin>>mp[i][j];
    bfs();
    int ans = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) if(vis[i][j]) ans++;
    cout<<ans<<endl;
    return 0;
}
/*
10 10
10 4
10 9
...*******
.*.*******
.*.*******
.*.*******
.*.*******
.*.*......
.*.*.*****
.*........
.********.
..........
*/

Yet another 2D Walking

按照顺序经过坐标系上面的一些点，使得欧拉距离和最小

分层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
#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 x, y;
    bool operator < (const Node & b) const{
        if(max(x,y) == max(b.x,b.y)){
            if(x == b.x) return y>b.y;
            return x<b.x;
        }
        return max(x, y)<max(b.x, b.y);
    }
}node[maxn];
int l[maxn], r[maxn];
ll dis(int x, int y){
    return abs(node[x].x-node[y].x)+abs(node[x].y-node[y].y);
}
ll dpl[maxn], dpr[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>node[i].x>>node[i].y;
    sort(node+1, node+1+n);
//    for(int i=1; i<=n; i++){
//        cout<<i<<" "<<node[i].x<<" "<<node[i].y<<endl;
//    }
    int tot = 1;
    for(int i=1; i<=n; i++){
        if(max(node[i-1].x,node[i-1].y) != max(node[i].x,node[i].y)){
            r[tot] = i-1;
            l[++tot] = i;
        }
    }
    r[tot] = n;
    for(int i=1; i<=tot; i++){
        //上一次转移到本次的代价+本层转移的代价
        dpl[i] = min(dpl[i-1]+dis(l[i-1], r[i]), dpr[i-1]+dis(r[i-1], r[i]))+dis(l[i], r[i]);
        dpr[i] = min(dpl[i-1]+dis(l[i-1], l[i]), dpr[i-1]+dis(r[i-1], l[i]))+dis(l[i], r[i]);
    }
    cout<<min(dpl[tot], dpr[tot])<<endl;
    return 0;
}

codeforces 1066 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
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int n, r;
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>r;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    int ans = 0;
    for(int i=1; i<=n; i++){
        int now = i;
        ans++;
        bool flag = false;
        for(int j = r-1; j>=-r+1; j--){
            if(j+i<=n&&j+i>=1&&a[j+i]) {
                i=min(j+i+r-1, n);
                flag = true;
                break;
            }
        }
        if(!flag) {
            cout<<-1<<endl;
            return 0;
        }
        //cout<<i<<endl;
    }
    cout<<ans<<endl;
    return 0;
}
/*
10 9
1 1 0 0 0 0 0 0 0 0
*/

zoj 3278

二分莫名其妙的飞了很多次。。。
注意重复元素的统计，重复元素的第K大
突然想到的是XDOJ上面的区间第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
#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;
ll k;
ll t1[maxn], t2[maxn];
ll ans;
bool judge(ll mid){
    ll tot = 0;
    for(int i=1; i<=n; i++){
        ll you = ll(mid / t1[i] + (mid % t1[i] > 0));
        if(you*t1[i] <=mid) you++;
        int index = lower_bound(t2+1, t2+1+m, you)-t2;
        tot += (m-index+1);
        //cout<<tot<<endl;
    }
    tot++;
    if(tot>k) return true;
    else return false;
}
int main()
{
    while(cin>>n>>m>>k){
        for(int i=1; i<=n; i++) cin>>t1[i];
        for(int i=1; i<=m; i++) cin>>t2[i];
        sort(t2+1, t2+1+m);
        ll l=0, r=1e10+10;
        ll mid;
        //judge(3);
        while(l<r){
            mid = (l+r)>>1;
            //cout<<l<<" "<<r<<" "<<mid<<endl;
            if(judge(mid))l=mid+1;
            else{
                r=mid;
                ans = mid;
            }
        }
        cout<<ll(ans)<<endl;
    }
    return 0;
}

codeforces 1066 C

操作L就是最左边方一本书，R就是最右边方一本书，？就是询问离最左边或者最右边的书的数量
一开始用deque进行相应的模拟，然后就炸了。
后来看到了不断的用左右两个指针进行相应的拓展，自己还是太弱了emmm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn];
int l, r;
int main(){
    ios::sync_with_stdio(false);
    int q, index;
    char op;
    cin>>q;
    for(int i=1; i<=q; i++){
        cin>>op>>index;
        if(op == 'L') a[index] = (--l);
        else if(op == 'R') a[index] = r++;
        else {
            cout<<min(a[index]-l, r-a[index]-1)<<endl;
        }
    }
    return 0;
}

contest1066

按位计算贡献

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
#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;
string a, b;
ll powmod(int b){
    ll ans = 1;
    ll a = 2;
    while(b){
        if(b&1){
            ans = ans*a%mod;
        }
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    cin>>a>>b;
    string zero="";
    for(int i=1; i<=n-1; i++) zero += '0';
    b = zero+b;
    ll tot = 0;
    ll ans = 0;
    int index = b.length()-1;
    int pow = 0;
    for(int i=a.length()-1; i>=0; i--, index--, pow++){
        if(a[i] == '1') {tot += (powmod(pow)); tot%=mod;}
        if(b[index] == '1') {
            ans = (ans+tot)%mod;
        }
    }
    for(; index>=0; index--){
        if(b[index] == '1'){
            ans = (ans+tot)%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

IEEE dog walking

有n条狗，k个遛狗的人，每一条狗有一个时间。你要将狗划分成k个团，使得他们排序好之后的插值最小

贪心，先对原来的数组进行排序，然后两两做差
最后，取前面n-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
#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, k;
int a[maxn];
int diff[maxn];
void solve(){
    for(int i=2; i<=n; i++){
        diff[i-1] = a[i] - a[i-1];
    }
    sort(diff+1, diff+1+n-1);
    ll cost = 0;
    for(int i=1; i<=n-k; i++) cost+=1ll*diff[i];
    printf("%lld\n", cost);
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++){
            scanf("%d", &a[i]);
        }
        sort(a+1, a+1+n);
        solve();
    }
    return 0;
}

BerOS File Suggestion

题目链接
就是做字符串的匹配，不过这道题由于母串比较的短，所以可以乱搞

这道题进一步的证明了unordered_map的优越性！！！

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>
#include<unordered_map>
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, q;
string file[maxn];
string query[maxn];
int ans[maxn];
unordered_map<string, bool> temp;
unordered_map<string, int> s;
unordered_map<string, string > ump;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>file[i];
        temp.clear();
        for(int j=0; j<file[i].length(); j++){
            for(int k=j; k<file[i].length(); k++){
                temp[file[i].substr(j, k-j+1)] = true;
                ump[file[i].substr(j, k-j+1)] = file[i];
            }
        }
        for(auto&it:temp) s[it.fi]++;
    }
    cin>>q;
    for(int i=1; i<=q; i++) cin>>query[i], ans[i]=s[query[i]];
    for(int i=1; i<=q; i++){
        if(ans[i] == 0){
            cout<<0<<" -"<<"\n";
        }
        else{
            cout<<ans[i]<<" "<<ump[query[i]]<<"\n";
        }
    }
    return 0;
}

A find a number

我以前的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
#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 = 505;
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;
bool vis[5020][maxn];
int d, s;
struct Node{
    int d, s;
    string ans;
    Node(int _d, int _s, string _ans):d(_d), s(_s), ans(_ans){}
};
void solve(){
    queue<Node> q;
    while(!q.empty()) q.pop();
    q.push(Node(0, 0, ""));
    vis[0][0] = true;
    while(!q.empty()){
        Node temp = q.front();
        q.pop();
        if(temp.d == 0&&temp.s == s){
            cout<<temp.ans<<endl;
            return ;
        }
        if(temp.s>s) continue;
        int dd;
        for(int i=0; i<10; i++){
            dd =  (temp.d*10+i)%d;
            if(!vis[temp.s+i][dd]&&temp.s+i<=s){
                q.push(Node(dd, temp.s+i, temp.ans+char(i+'0')));
                vis[temp.s+i][dd] = true;
            }
        }
    }
    cout<<-1<<endl;
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>d>>s;
    solve();
    return 0;
}

E getting deals down

感觉是一道比较好的二分的题目。
需要二分的条件有两个，需要一定的转换的技巧

题目的大意：
找一个d，使得任务的难度超过d，就会跳过，问最多能执行多少个任务，且总时限不能超过t.
我们发现d在p数组中。
然后排序统计就行了

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int n, m;
ll t;
ll p[maxn];
ll b[maxn];
bool check(ll mid, int num){
    int cnt =0;
    ll tt = 0;
    ll sum = 0;
    for(int i=1; i<=n&&cnt<num&&tt<=t; i++){
        if(p[i] <= mid){
            cnt++;
            sum += p[i];
            tt += p[i];
            if(cnt%m == 0&&cnt!=num){
                tt += sum;
                sum = 0;
            }
        }
    }
    return (tt<=t);
}
int main(){
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m>>t;
        int l=1, r=n;
        for(int i=1; i<=n; i++){
            cin>>p[i];
            b[i] = p[i];
        }
        sort(b+1, b+1+n);
        int mid, ans=0;
        while(l<=r){
            mid = (l+r)>>1;
            //cout<<l<<" "<<r<<" "<<mid<<" "<<ans<<endl;
            if(check(b[mid], mid)){
                l=mid+1;
                ans = mid;
            }
            else r=mid-1;
        }
        if(ans == 0) b[ans] = 1;
        cout<<ans<<" "<<b[ans]<<endl;
    }
    return 0;
}

codeforces contest 1054 D

给定一个长度为n的数组，每一个数字长度为k位。
你可以操作任意多个数，使得这个数变成这个数的反。
为做多有多少个这样的子串。

求出来最少有多少个这样的子串，使得它的亦或和为0，那么就可以用总方案数减去了
亦或和为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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int num[maxn];
int n, k;
map<int, int> mp;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    k = (1<<k)-1;
    for(int i=1; i<=n; i++) cin>>num[i];
    int x = 0;
    ll ans = 0;
    //初始化。。。写错了。。。
    mp[0]++;
    //前缀亦或和
    for(int i=1; i<=n; i++){
        x^=num[i];
        if(mp[x]<mp[x^k]) ans+=mp[x], mp[x]++;
        else ans+=mp[x^k], mp[x^k]++;
    }
    cout<<(1ll*n*(n+1)/2-ans)<<endl;
    return 0;
}

contest 1068 E. Multihedgehog

题目就是定义了半径恰好为k的一个树形的结构
我们从叶子节点不断的向上面删除节点，问最后是否能够是满足条件的结构

注意定义，cnt[]要及时的清除

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 <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n, m;
set<int> G[maxn];
int cnt[maxn];
void solve(){
    set<int> leave;
    leave.clear();
    for(int i=1; i<=n; i++){
        if(G[i].size() == 1) leave.insert(i);
    }
//    for(auto&it:leave){
//        cout<<it<<" ";
//    }
//    cout<<endl<<endl;
    bool flag = true;
    while(n>1){
        set<int> pre;
        for(auto&it:leave){
            int p = *G[it].begin();
            G[p].erase(it), cnt[p]++, n--;
            pre.insert(p);
        }
//        for(auto&it:pre){
//            cout<<it<<" ";
//        }
//        cout<<endl;
        leave.clear();
        for(auto&it:pre){
            if(cnt[it]<3){
                flag = false;
                break;
            }
            cnt[it] = 0;
        }
        swap(leave, pre), m--;
    }
    if(!flag) cout<<"No"<<endl;
    else {
        if(m!=0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int u, v;
    cin>>n>>m;
    for(int i=1; i<=n-1; i++){
        cin>>u>>v;
        G[u].insert(v), G[v].insert(u);
    }
    solve();
    return 0;
}
/*
25 2
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
4 14
14 15
14 16
14 17
4 18
18 19
18 20
18 21
1 22
22 23
22 24
22 25
*/

contest1073 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int n;
string s;
ll hori[maxn], vert[maxn];
ll x, y;
bool check(int len){
    for(int i=1; i<=n-len+1; i++){
        int j = i+len-1;
        int heng = hori[i-1]+(hori[n]-hori[j]), zong = vert[i-1]+(vert[n]-vert[j]);
        int xx = x-heng, yy = y-zong;
        if(abs(xx)+abs(yy)<=len&&(len-xx-yy)%2==0) return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    cin>>x>>y;
    for(int i=1; i<=n; i++){
        if(s[i-1] == 'L') hori[i] = hori[i-1]-1, vert[i] = vert[i-1];
        else if(s[i-1] == 'R') hori[i] = hori[i-1]+1, vert[i] = vert[i-1];
        else if(s[i-1] == 'U') vert[i] = vert[i-1]+1, hori[i] = hori[i-1];
        else vert[i] = vert[i-1]-1, hori[i] = hori[i-1];
    }
    int l=0, r=n;
    int mid, ans = -1;
    while(l<=r){
        mid = (l+r)>>1;
        if(check(mid)){
            ans = mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

bzoj 3124

记录最长链上面的节点，从而来解决关于次长链上面的问题

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
#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 = 2e5+10;
const int maxm = 2e5+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;
struct Node{
    int v, next;
    ll w;
}node[maxm<<1];
 
int tot, head[maxn];
ll dis[maxn];
int fa[maxn];
bool vis[maxn];
int d[maxn];
int rt;
 
void init(){
    tot=0,cls(head, -1);
    cls(vis, 0);
    cls(dis, 0);
    rt=0;
}
 
 
 
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 dfs(int u, int p){
    fa[u]=p;
    d[u]=d[p]+1;
    for(int i=head[u];~i;i=node[i].next){
        int v=node[i].v;
        int w=node[i].w;
        if(p==v) continue;
        dis[v]=dis[u]+w;
        dfs(v, u);
    }
    if(dis[u]>dis[rt]) rt=u;
 
}
int top=0;
int chain[maxn];
ll len2;
int rt1, rt2;
 
 
void getchain(){
    int x=rt2;
    cls(vis, 0);
    while(x!=fa[rt1]){
        chain[top++]=x;
        vis[x]=true;
        x=fa[x];
    }
}
 
ll dis1[maxn];
 
int dfs1(int u, int fa){
    vis[u]=true;
    for(int i=head[u];~i;i=node[i].next){
        int v=node[i].v;
        ll w=node[i].w;
        if(vis[v]||v==fa) continue;
        dis1[v]=dis1[u]+w;
        dfs1(v, u);
    }
    if(dis1[u]>len2) len2=dis1[u];
}
 
 
 
int main()
{
    n=readint();
    int u, v, w;
    init();
    inc(i, 1, n-1){
        u=readint(), v=readint(), w=readll();
        add_edge(u, v, w), add_edge(v, u, w);
    }
    dfs(1, 0), rt1=rt;
    cls(dis, 0), cls(d, 0);
    dfs(rt, 0); rt2=rt;
    ll len=dis[rt];
    getchain();
    ll ans = 0;
    len2=0;
 
    int chang = d[rt2]-1;
    int l=rt2, r=rt1;
    for(int i=0; i<top; i++){
        int id=chain[i];
        len2=0, dis1[id]=0;
        dfs1(id, 0);
        if(len2 == dis[rt2]-dis[id]) l=id;
        if(len2 == dis[id]){r=id;break;}
    }
    printf("%lld\n%d\n",dis[rt2], d[l]-d[r]);
    return 0;
}

contest1073 F

题目大意：
给一个树形的结构，然后选择两条链， 使得一条链的两端不能在另外一条链上，并且满足下列的条件：

  1. 公共的点的数量最大
  2. 在满足1的条件下，使得两个链的长度最长。

实质上就是求满足条件的点的最长链，
满足条件的链就是子树的度数>=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
#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;
pii fir[maxn], sec[maxn];
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 id, depth, tot;
    Node(int _id, int _depth, int _tot):id(_id), depth(_depth), tot(_tot){}
    Node(){}
    bool operator < (const Node &b) const{
        if(depth == b.depth) return tot<b.tot;
        else return depth<b.depth;
    }
};
vector<int> G[maxn];
Node best;
void dfs(int u, int fa, int dep){
    int deg = 0;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(G[u][i] == fa) continue;
        deg++;
        //cout<<"haha"<<u<<" "<<v<<endl;
        dfs(v, u, dep+1);
        if(fir[v].fi>fir[u].fi){
            swap(fir[u], sec[u]);
            fir[u] = fir[v];
        }
        else if(fir[v].fi>sec[u].fi){
            sec[u] = fir[v];
        }
    }
    if(deg>=2) best = max(best, Node(u, dep, fir[u].fi+sec[u].fi));
    if(deg == 0){
        fir[u] = make_pair(dep, u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int u, v;
    for(int i=1; i<=n-1; i++){
        cin>>u>>v;
        G[u].push_back(v), G[v].push_back(u);
    }
    best = Node(0, 0, 0);
    dfs(1, 0, 1);
//    for(int i=1; i<=n; i++){
//        cout<<i<<" "<<fir[i].fi<<" "<<fir[i].se<<" "<<sec[i].fi<<" "<<sec[i].se<<endl;
//    }
//    cout<<best.id<<" "<<best.depth<<" "<<best.tot<<endl;
    int p = best.id;
    //cout<<p<<endl;
    int u1, v1, u2, v2;
    u1 = fir[p].se, v2 = sec[p].se;
    cls(fir, 0), cls(sec, 0);
    best = Node(0, 0, 0);
    dfs(p, 0, 1);
    p = best.id;
    cout<<u1<<" "<<fir[p].se<<endl;
    cout<<sec[p].se<<" "<<v2<<endl;
    return 0;
}

contest 1043 E

有n个人，有m个相互讨厌的人，他们会和不讨厌的人之间两两组合，最后获得一个总的分值，要使这个分值最小
分成两个部分计算：
$x_i+y_j \le x_j+y_i$, 转换一下$x_i-y_i \le x_j-y_j$,于是就按照这个属性进行排序。
一开始假设是相互不讨厌的，然后得到总的最小的边权。然后将那些相互讨厌的边权减去。
因为一开始采取的就是最优的策略，因此，减去的时候取min.
最后就能得到答案了。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
typedef long long ll;
struct Node{
    ll x, y;
    int id;
    bool operator < (const Node& b)const{
        return x-y<b.x-b.y;
    }
}node[maxn];
int n, m;
vector<int> G[maxn];
ll pre[maxn];
ll suf[maxn];
ll ans[maxn];
int pos[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int x, y;
    for(int i=1; i<=n; i++){
        cin>>x>>y;
        node[i].id = i, node[i].x = x, node[i].y = y;
    }
    sort(node+1, node+1+n);
    for(int i=1; i<=n; i++){
        pos[node[i].id] = i;
    }
    int id;
    for(int i=1; i<=n; i++){
        pre[i] = pre[i-1]+node[i].x;
    }
    for(int i=n; i>=1; i--){
        id = node[i].id;
        suf[i] = suf[i+1]+node[i].y;
    }
    int u, v;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        G[u].push_back(v), G[v].push_back(u);
    }
    for(int i=1; i<=n; i++){
        int u = node[i].id;
        ll tot = pre[i]+suf[i+1]+node[i].x*(n-i-1)+(i-1)*node[i].y;
        for(int j = 0; j<G[u].size(); j++){
            int v = G[u][j];
            v = pos[v];
            tot -= min(node[i].x+node[v].y, node[i].y+node[v].x);
        }
        ans[u] = tot;
    }
    for(int i=1; i<=n; i++){
        cout<<ll(ans[i]);
        if(i!=n) cout<<" ";
    }
    cout<<"\n";
    return 0;
}

bzoj 1315 (T了待更) 双割

问有多少种方法，使得去掉两条边之后，使得原来的连通变得不连通
用传统的方法写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
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
#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;
const int maxm = 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[maxm];
int tot, head[maxn];
int lowset[maxn][maxn];
int s[maxn], t[maxn];
int dep[maxn];
int bridge, nobridge;
bool vis[maxn];
void init(){
    tot = 0,
    bridge = nobridge = 0;
    for(int i=0; i<=n; i++){
        head[i] = -1, dep[i] = s[i] = t[i] = 0;
    }
}
void add_edge(int u, int v){
    node[tot].v = v, node[tot].next = head[u], head[u] = tot++;
}
bool check(int u, int fa){
    int cnt = 0;
    for(int i=head[fa]; ~i; i=node[i].next){
        if(node[i].v == u) cnt++;
    }
    return (cnt == 1);
}
void dfs(int u, int su, int du){
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(dep[v]!=dep[u]+1) continue;
        //不能有横跨边
        if(vis[v]) continue;
        vis[u] = true;
        if(check(u, v) &&su == s[v] &&t[v]<du) nobridge++;
        dfs(v, su, du);
    }
}
//最后一个参数必须有，来判断重边
void tarjan(int u, int fa, int d, int e){
    memset(lowset[u], 0, sizeof(lowset[u]));
    if(u == 1) s[u] = 0;
    else s[u] = 1;
    t[u] = 1;
    dep[u] = d;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if((e^1) == i) continue;
        //if(v == fa) continue;
        if(!dep[v]){
            tarjan(v, u, d+1, i);
            for(int j=1; j<d; j++){
                if(lowset[v][j]) lowset[u][j]+=lowset[v][j];
            }
        }
        else if(dep[v]<dep[u]){
            lowset[u][dep[v]]++;
        }
    }
    for(int i=1; i<d; i++){
        if(lowset[u][i])s[u] += lowset[u][i], t[u] = i;
    }
    if(s[u] == 1) bridge++;
    else if(s[u] == 2) nobridge++;
    if(s[u]!=0&&s[u]!=1&&check(u, fa)){
        cls(vis, 0);
        dfs(u, s[u], dep[u]);
    }
}
void read_int(int&x)
{
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    x = ch - '0';
    ch=getchar();
    while('0'<=ch&&ch<='9')
    {
        x = 10*x + ch-'0';
        ch = getchar();
    }
}
int ans, u, v;
int main()
{
    while(~scanf("%d%d", &n, &m)){
        init();
        for(int i=1; i<=m; i++){
            read_int(u), read_int(v);
            add_edge(u, v), add_edge(v, u);
        }
        tarjan(1, 0, 1, -1);
        //cout<<bridge<<" "<<nobridge<<endl;
        ans = bridge*(m-bridge) + bridge*(bridge-1)/2;
        printf("%d\n", ans+nobridge);
    }
    return 0;
}
/*
5 7
1 2
2 3
3 4
3 4
3 4
4 5
5 1
*/

claris 跑的飞快的代码

emmm是用数学方法的
link

codeforces 19e

一个图是二分图当且仅当没有奇环。

概念区分
区分树边，前向边，横跨边，以及反向边

题解：
我们统计每一条边经过了多少个奇环就行了，其中统计的方式用了差分的思想

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<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 n, m;
struct Node{
    int v, next;
}node[maxn<<1];
int tot, head[maxn];
int pre[maxn], cnt;
int d[maxn];
int tag1[maxn<<1];
int tag[maxn];
bool vis[maxn];
int odd;
vector<int> ans;
void init(){
    tot = 0, cls(head, -1);
    odd = 0;
    ans.clear();
}
void add_edge(int u, int v){
    node[tot].v = v, node[tot].next=head[u], head[u] = tot++;
}
void dfs(int u, int fa, int col){
    pre[u] = ++cnt;
    d[u] = col;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == fa) continue;
        if(pre[v]&&pre[v]<pre[u]){
            if(d[u]^d[v]){
                tag[u]--, tag[v]++;
                tag1[i>>1]--;
            }
            else tag[u]++, tag[v]--, tag1[i>>1]++, odd++;
        }
        else if(!pre[v]){
            dfs(v, u, col^1);
        }
    }
}
int dfs1(int u, int fa){
    int t=tag[u], t1;
    vis[u] = true;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == fa)continue;
        if(pre[v]<pre[u]){
            if(tag1[i>>1] == odd) ans.push_back(i>>1);
        }
        //相当于做一个圈的奇偶差分
        else if(!vis[v]){
            t1 = dfs1(v, u);
            t += t1;
            if(t1 == odd) ans.push_back(i>>1);
        }
    }
    return t;
}
int main(){
    init();
    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=1; i<=n; i++) if(!pre[i]){
        dfs(i, 0, 0);
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]) dfs1(i, 0);
    }
//    cout<<odd<<endl;
//    for(int i=0; i<m; i++){
//        cout<<tag1[i]<<" ";
//    }
//    cout<<endl;
    if(odd){
        sort(ans.begin(), ans.end());
        printf("%d\n", ans.size());
        for(int i=0; i<ans.size(); i++){
            printf("%d%c", ans[i]+1, (i == ans.size()-1)?'\n':' ');
        }
    }
    else{
        printf("%d\n", m);
        for(int i=1; i<=m; i++){
            printf("%d", i);
            if(i!=n) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

hdu5254 （代码被叉，有反例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
8 14
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
4 5 1
4 6 1
4 7 1
5 6 1
5 7 1
6 7 1
4 0 1
7 3 1

题意：
给定一个图，首先前n-1条边表示这个图的生成树，然后后面的m-n+1条边加在图中。
题目要求删掉最少的边，使得原来的图不连通。并且删掉的边，有且仅有一条属于生成树。
问最少删掉几条边。

题解：
首先因为只能删掉生成树上面的一条边，一次肯定选择树上节点度数为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
#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 = 2e4+10;
const int maxm = 4e5+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 td[maxn];
int vd[maxn];
int main()
{
    int _;
    scanf("%d", &_);
    int kase = 1;
    while(_--){
        scanf("%d%d", &n, &m);
        int u, v;
        cls(td, 0), cls(vd, 0);
        for(int i=1; i<=n-1; i++){
            scanf("%d%d", &u, &v);
            td[u]++, td[v]++;
        }
        for(int i=n; i<=m; i++){
            scanf("%d%d", &u, &v);
            vd[u]++, vd[v]++;
        }
        int res = inf;
        for(int i=1; i<=n; i++){
            if(td[i] == 1){
                res = min(res, vd[i]);
            }
        }
        printf("Case #%d: %d\n", kase++, res+1);
    }
    return 0;
}

hdu 4654(待更)

k连通分量的定义：这个图的最小割>=k, 那么就是k连通分量
最小割的算法
时间复杂度是$O(n^3)$
好像要是用新的算法，用了分治的思想去计算的，不会啊emmm

hdu 4115-2-sat

题意：
alice和bob玩剪刀布石头的游戏，alice已知bob的所有的操作，bob会对alice的第i个操作和第j个操作进行操作， 有下面的限制：

  1. 第i个操作和第j个操作要一样
  2. 第i个操作要和第j个操作不同

若alice输了其中的一局，那么alice就输了
问最后的输赢

题解：
alice要么和bob平局，要么赢bob.于是转化为了一个2-sat的问题
若要使操作使i,j相同时，那么可以有下面的连边：

  1. 若两局不能都平，那么第i局平必然可以推出第j局赢，若第j局赢那么第i局赢
  2. 若不能第i局平，j局赢，那么i局平那么，第j局必然是平， 若第j局平，那么第i局必然赢
  3. 若不能第i局赢， 第j局平。。。。
  4. 若不能两局都赢。。。

用tarjan求连通分量，第一次这样写2-sat,所以说2-sat也是一种思想2333

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
int tot, head[maxn];
struct Node{
    int v, next;
}node[maxn<<1];
int low[maxn], dfn[maxn], cnt;
int bl[maxn], scc;
int top, sta[maxn];
bool instack[maxn];
int n, m;
int beat[4] = {0, 2, 3, 1};
int bob[maxn];
void add_edge(int u, int v){
    node[tot].v = v, node[tot].next = head[u], head[u] = tot++;
}
void init(){
    tot = 0, memset(head, -1, sizeof(head));
    memset(low, 0, sizeof(low)), memset(dfn, 0, sizeof(dfn)), cnt=0;
    memset(instack, 0, sizeof(instack));
    top = 0, scc = 0;
}
void tarjan(int u, int fa){
    dfn[u] = low[u] = ++cnt;
    sta[top++] = u;
    instack[u] = true;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(v == fa) continue;
        if(!low[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(instack[v]&&dfn[v]<low[u]) low[u] = dfn[v];
    }
    if(low[u] == dfn[u]){
        scc++;
        int id;
        do{
            id = sta[--top];
            bl[id] = scc;
            instack[id] = false;
        }while(id!=u);
    }
}
bool solve(){
    memset(bl, 0, sizeof(bl));
    for(int i=1; i<=2*n; i++){
        if(!dfn[i]) tarjan(i, 0);
    }
    for(int i=1; i<=n; i++){
        if(bl[i] == bl[i+n]) return false;
    }
    return true;
}
int main(){
    int _;
    int kase = 1;
    scanf("%d", &_);
    while(_--){
        init();
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++){
            scanf("%d", &bob[i]);
            bob[i+n] = beat[bob[i]];
        }
        int a, b, c;
        for(int i=1; i<=m; i++){
            scanf("%d%d%d", &a, &b, &c);
            if(c == 0){
                if(bob[a]!=bob[b]) add_edge(a, b+n), add_edge(b, a+n);
                if(bob[a]!=bob[b+n]) add_edge(a, b), add_edge(b+n, a+n);
                if(bob[a+n]!=bob[b]) add_edge(a+n, b+n), add_edge(b, a);
                if(bob[a+n]!=bob[b+n]) add_edge(a+n, b), add_edge(b+n, a);
            }
            else{
                if(bob[a] == bob[b]) add_edge(a, b+n), add_edge(b, a+n);
                if(bob[a] == bob[b+n]) add_edge(a, b), add_edge(b+n, a+n);
                if(bob[a+n] == bob[b]) add_edge(a+n, b+n), add_edge(b, a);
                if(bob[a+n] == bob[b+n]) add_edge(a+n, b), add_edge(b+n, a);
            }
        }
        if(solve()) printf("Case #%d: yes\n", kase++);
        else printf("Case #%d: no\n", kase++);
    }
    return 0;
}

poj2914-无向图的最小割

需要一个新的算法
当板子积累了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=606;
using namespace std;
int mat[N][N];
int res;
void Mincut(int n)  //注意写的时候不要丢node
{
    int dist[N],node[N];
    bool vis[N];
    for(int i=0; i<n; ++i) node[i]=i;
    while(n>1)
    {
        int maxx=1,prev=0;
        for(int i=1; i<n; ++i)
        {
            dist[node[i]]=mat[node[0]][node[i]];
            if(dist[node[i]]>dist[node[maxx]]) maxx=i;
        }
        memset(vis,0,sizeof(vis));  //每次都要更新vis
        vis[node[0]]=1;
        for(int i=1; i<n; ++i)
        {
            if(i==n-1)
            {
                res=min(res,dist[node[maxx]]);
                for(int k=0; k<n; ++k)
                    mat[node[k]][node[prev]]=(mat[node[prev]][node[k]]+=mat[node[maxx]][node[k]]);  //看清楚這
                node[maxx]=node[--n];
            }
            vis[node[maxx]]=1;
            prev=maxx;
            maxx=-1;
            for(int j=1; j<n; ++j) if(!vis[node[j]])
            {
                dist[node[j]]+=mat[node[prev]][node[j]];  //更新的时候注意是prev,因为在更新的时候顺便把下一次循环的最大值搞了出来
                if(maxx==-1||dist[node[j]]>dist[node[maxx]])  
                    maxx=j;
            }
        }
    }
    return ;
}
int main(){
   int n,m;
   while(scanf("%d%d",&n,&m)!=EOF){
    res=100861199;
    int u,v,w;
    memset(mat,0,sizeof(mat));
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        mat[u][v]+=w;
        mat[v][u]+=w;
    }
    Mincut(n);
    printf("%d\n",res);
   }
}

gym 101964I

题目联链接
题意读错了，注意里面支配集的定义是：
首先选出来一个支配集的点集，然后其他不在集合里面的点至少有一条边与点集里面的点相连。不是我们平时理解的点支配集，它的定义是任意一条边至少有一个点在集合里面。
问有多少选点的方案。

题解：
dp[i]表示前面i个节点的方案的数量。
转移方程：$d[i] = \sum_{k=j+1}^{i-1}dp[j], g[i][j] = 0 ans j+1~i-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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
typedef long long ll;
int g[maxn][maxn];
ll dp[maxn];
int n, m;
int main(){
    scanf("%d%d", &n, &m);
    int u, v;
    for(int i=1; i<=m; i++){
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = 1;
    }
    dp[0] = 1;
    for(int i=1; i<=n+1; i++){
        for(int j=0; j<i; j++){
            if(g[i][j]) continue;
            bool flag = true;
            for(int k=j+1; k<i; k++){
                if(g[i][k]||g[j][k]) continue;
                else{
                    flag = false;
                    break;
                }
            }
            if(flag) dp[i] += dp[j];
        }
    }
    printf("%lld\n", dp[n+1]);
}

gym c

link
题意：
给一棵树形的结构，然后有若干个点为黑色。
选取若干个点，使得他们的点的最长链最短，并且点集的大小为m.问这个最短的最长链。

题解：
首先可以想到是二分。
但怎么二分确实很伤脑筋。
可以看到后面的代码先用bfs取小范围的点，然后用dfs进行统计判断，这种思路真的很巧妙emmm

如果按照一开始的想法将每一个点作为根进行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
#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;
vector<int> g[maxn];
int color[maxn];
queue<int> q;
bool vis[maxn];
int dfs(int u, int fa, int dst, int dis){
    int ans = color[u];
    if(dis == dst) return ans;
    for(int i=0; i<g[u].size(); i++){
        int v = g[u][i];
        if((!vis[v])||v == fa) continue;
        ans += dfs(v, u, dst, dis+1);
    }
    return ans;
}
bool check(int mid){
    while(!q.empty()) q.pop();
    q.push(1);
    cls(vis, 0);
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        vis[temp] = true;
        int ans = dfs(temp, 0, mid, 0);
        if(ans>=m) return true;
        for(int i=0; i<g[temp].size(); i++){
            int v = g[temp][i];
            if(vis[v]) continue;
            q.push(v);
        }
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    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);
        g[u].push_back(v), g[v].push_back(u);
    }
    int l=0, r=n;
    int mid;
    int ans = n;
    while(l<=r){
        mid = (l+r)/2;
        if(check(mid)) ans = mid, r=mid-1;
        else l=mid+1;
    }
    printf("%d\n", ans);
    return 0;
}
/*
9 4
1 0 1 0 1 0 0 1 1
1 2
2 4
2 3
4 5
1 6
6 7
6 8
7 9
*/

hdu 5988

最小费用流的最新的模板
double 改成 float就过了，真的是极限操作。。。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <iostream>
#define double float
using namespace std;
const int maxn = 200+10;
namespace mincostflow {
	const int INF=0x3f3f3f3f;
	struct node {
		int to; int cap;
		double cost; int rev;
		node(int t=0,int c=0,double _c=0,int n=0):
			to(t),cap(c),cost(_c),rev(n) {};
	}; vector<node> edge[maxn];
	void addedge(int from,int to,int cap,double cost) {
		edge[from].push_back(node(to,cap,cost,edge[to].size()));
		edge[to].push_back(node(from,0,-cost,edge[from].size()-1));
	}
	double dis[maxn];
	bool mark[maxn];
	void spfa(int s,int t,int n) {
        for(int i=0; i<=n+2; i++) dis[i] = double (INF);
		memset(mark+1,0,n*sizeof(bool));
		static int Q[maxn],ST,ED;
		dis[s]=0; ST=ED=0; Q[ED++]=s;
		while (ST!=ED) {
			int v=Q[ST]; mark[v]=0;
			if ((++ST)==maxn) ST=0;
			for (node &e:edge[v]) {
				if (e.cap>0&&dis[e.to]>dis[v]+e.cost) {
					dis[e.to]=dis[v]+e.cost;
					if (!mark[e.to]) {
						if (ST==ED||dis[Q[ST]]<=dis[e.to]) {
							Q[ED]=e.to,mark[e.to]=1;
							if ((++ED)==maxn) ED=0;
						} else {
							if ((--ST)<0) ST+=maxn;
							Q[ST]=e.to,mark[e.to]=1;
						}
					}
				}
			}
		}
	} int cur[maxn];
	int dfs(int x,int t,int flow) {
		if (x==t||!flow) return flow;
		int ret=0; mark[x]=1;
		for (int &i=cur[x];i<(int)edge[x].size();i++) {
			node &e=edge[x][i];
			if (!mark[e.to]&&e.cap) {
				if (dis[x]+e.cost==dis[e.to]) {
					int f=dfs(e.to,t,min(flow,e.cap));
					e.cap-=f; edge[e.to][e.rev].cap+=f;
					ret+=f; flow-=f;
					if (flow==0) break;
				}
			}
		} mark[x]=0;
		return ret;
	}
	pair<int,double> min_costflow(int s,int t,int n) {
		int ret=0;
		double ans=0;
		int flow = INF;
		while (flow) {
			spfa(s,t,n); if (dis[t]==double(INF)) break;
			memset(cur+1,0,n*sizeof(int));
			double len=dis[t];
			int f;
			while ((f=dfs(s,t,flow))>0)
				ret+=f,ans+=len*f,flow-=f;
		} return make_pair(ret,ans);//最大流，最小费用
	}
	void init(int n) {
		int i; for (int i = 1; i <= n; i++) edge[i].clear();
	}
}
int n, m;
using namespace mincostflow;
int ss, tt;
double e = 2.718281828459045;
int main(int argc, char const *argv[])
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d %d", &n, &m);//n个点，m条边
        init(n+2);//点的个数
        int x, y, z;
        double s;
        ss=1, tt = n+2;
        for(int i=1; i<=n; i++) {
            scanf("%d%d", &x, &y);
            if(x) addedge(ss, i + 1, x, 0);
            if(y) addedge(i + 1, tt, y, 0);
        }
        for (int i = 1; i <= m; i++) {//建边
            scanf("%d %d %d %f", &x, &y, &z, &s);
            if(z)addedge(x + 1, y + 1, z-1, -log(1.0 - s)), addedge(x + 1, y + 1, 1, 0.0);
        }
        pair<int,double > ans = min_costflow(ss, tt, n+2);//s,t,点的个数
        printf("%.2f\n", 1.0-pow(e, -ans.second));//最大流，最小费用
    }
	return 0;
}

hdu 5991

题意：
给一个图，现在让你增加或者减少一条边，这样的操作不超过十次。
问最少经过几次，使得这个图的各个分图变成团

题解：
根据floyd的覆盖的思想，进行不断的扩充

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
#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 = 1e2+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 mp[maxn][maxn];
int res;
void dfs(int d){
    if(d>=res) return ;
    int a, b, c;
    a = b = c = 0;
    for(int i=1; i<=n&&!a; i++){
        for(int j=i+1; j<=n&&!a; j++){
            if(mp[i][j]){
                for(int k=1; k<=n&&!a; k++){
                    if(i!=k&&j!=k&&(mp[i][k]^mp[k][j])){
                        a = i, b=j, c=k;
                    }
                }
            }
        }
    }
    if(!a) {
        res = d;
        return ;
    }
    mp[a][b] = mp[b][a] = (mp[a][b]^1);
    dfs(d+1);
    mp[a][b] = mp[b][a] = (mp[a][b]^1);
    mp[a][c] = mp[c][a] = (mp[a][c]^1);
    dfs(d+1);
    mp[a][c] = mp[c][a] = (mp[a][c]^1);
    mp[b][c] = mp[c][b] = (mp[b][c]^1);
    dfs(d+1);
    mp[b][c] = mp[c][b] = (mp[b][c]^1);
}
int main()
{
    int _;
    scanf("%d", &_);
    int kase = 1;
    while(_--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d", &mp[i][j]);
        res = 11;
        dfs(0);
        if(res == 11) printf("Case #%d: %d\n", kase++, -1);
        else printf("Case #%d: %d\n", kase++, res);
    }
    return 0;
}

2018icpc 沈阳G(数据结构转化为数学解)

题意：
给定平面的四种操作，然后进行相关的查询

题解：
$x^2+y^2 = r^2$, 先把(0~6000, 0~6000)， 共(6001*6001)个点压入vector中，然后解方程的时候从中取出相应的解，从而缩小搜索的范围。

注意数据清空的小技巧

代码

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
#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 = 1e7+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;
}
vector<pii> res[maxn], cl;
void init(){
    for(int i=0; i<=6000; i++){
        for(int j=0; j<=6000; j++){
            if(i*i+j*j<=10000000) res[i*i+j*j].push_back(mp(i, j));
            else break;
        }
    }
}
int n, m;
bool exist[6000+10][6000+10];
int weight[6000+10][6000+10];
ll ans, lastans;
void change(int &x, int &y){
    x = (x+lastans)%6000+1;
    y = (y+lastans)%6000+1;
}
int cx[4] = {1, 1, -1, -1};
int cy[4] = {1, -1, 1, -1};
bool check(int x, int y){
    if(x<0||x>6000||y<0||y>6000) return false;
    return true;
}
set<pii> s;
int main()
{
    init();
    int _;
    int kase = 1;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        cl.clear();
        ans = lastans = 0;
        printf("Case #%d:\n", kase++);
        int u, v, w, k, nx, ny;
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &u, &v, &w);
            exist[u][v] = true, weight[u][v] = w;
            cl.push_back(mp(u, v));
        }
        while(m--){
            int op;
            scanf("%d%d%d", &op, &u, &v);
            change(u, v);
            //printf("in: %d %d %d\n", op, u, v);
            if(op == 1){
                scanf("%d", &w);
                if(!check(u, v)) continue;
                exist[u][v] = true, weight[u][v] = w;
                cl.push_back(mp(u, v));
            }
            else if(op == 2){
                if(!check(u, v)) continue;
                exist[u][v] = false, weight[u][v] = 0;
            }
            else if(op == 3){
                scanf("%d%d", &k, &w);
                s.clear();
                for(auto&it:res[k]){
                    for(int i=0; i<4; i++){
                        nx = u-cx[i]*it.fi;
                        ny = v-cy[i]*it.se;
                        if(!check(nx, ny)) continue;
                        if(exist[nx][ny])s.insert(make_pair(nx, ny));
                    }
                }
                for(auto&it:s){
                    weight[it.fi][it.se] += w;
                }
            }
            else{
                scanf("%d", &k);
                s.clear();
                ans = 0;
                for(auto&it:res[k]){
                    for(int i=0; i<4; i++){
                        nx = u-cx[i]*it.fi;
                        ny = v-cy[i]*it.se;
                        if(!check(nx, ny)) continue;
                        if(exist[nx][ny]) s.insert(mp(nx, ny));
                    }
                    //cout<<nx<<" "<<ny<<endl;
                }
                for(auto&it:s) ans += weight[it.fi][it.se];
                printf("%lld\n", ans);
                lastans = ans;
            }
        }
        for(auto&it:cl) weight[it.fi][it.se] = 0, exist[it.fi][it.se] = false;
    }
    return 0;
}

Qingdao Regional Contest D Magic Multiplication (爆搜)

先确定B数组，然后确定A数组
中间有一个优化很优秀！
当num<a[1]且num!=0时，num必然是两位数

代码

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
#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], b[maxn];
char str[maxn];
int len;
int pos = 0;
bool getA(){
    for(int i=1; i<=m; i++){
        int num = str[pos++]-'0';
        if(a[1]>num&&num){
            num = num*10+str[pos++]-'0';
        }
        if(num%a[1]) return false;
        b[i] = num/a[1];
        if(b[i]>=10) return false;
    }
//    for(int i=1; i<=m; i++){
//        cout<<b[i]<<" ";
//    }
//    cout<<endl;
    return true;
}
bool getB(){
    //cout<<"indicator "<<pos<<endl;
    for(int i=2; i<=n; i++){
        int num = str[pos++]-'0';
        if(b[1]>num&&num){
            num = num*10+str[pos++]-'0';
        }
        if(num%b[1]) return false;
        a[i] = num/b[1];
        if(a[i]>=10) return false;
        for(int j=2; j<=m; j++){
            num = str[pos++]-'0';
            if(a[i]*b[j]>num) {
                num = num*10+str[pos++]-'0';
                if(num!=a[i]*b[j]) return false;
            }
            else if(a[i]*b[j]<num) return false;
        }
    }
//    cout<<"inn"<<endl;
//    for(int i=1; i<=n; i++){
//        cout<<a[i]<<" ";
//    }
//    cout<<"haha  "<<pos<<" "<<len<<endl;
//    cout<<endl;
    return true;
}
bool solve(){
    int one = str[0]-'0';
    int two = (str[0]-'0')*10+str[1]-'0';
    //cout<<one<<" "<<two<<endl;
    for(int i=1; i<=9; i++){
        pos = 0;
        if(one%i == 0){
            a[1] = i;
            if(getA()&&getB()&&pos == len) return true;
        }
    }
    for(int i=1; i<=9; i++){
        pos = 0;
        if(two%i==0&&two/i<=9){
            a[1] = i;
            if(getA()&&getB()&&pos == len) return true;
        }
    }
    return false;
}
void print_ans(){
    for(int i=1; i<=n; i++) printf("%d", a[i]);
    printf(" ");
    for(int i=1; i<=m; i++) printf("%d", b[i]);
    puts("");
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        scanf("%s", str);
        len = strlen(str);
        if(solve()){
            print_ans();
        }
        else printf("Impossible\n");
    }
    return 0;
}

Plants vs. Zombies

题意：
从左向右走，每一次移动后，对这个格子施肥，问最后的最小权值最大是多少

题解：
二分，模拟贪心向右取就可以了

这里注意二分取上界的写法！因为每一个格子有一个权值，因此其实它的权值是阶跃的。

<=x中最大的一个数

1
2
3
4
5
while(l<r){
    int mid = (l+r+1)/2;
    if(a[mid] <= x) l=mid;
    else r=mid-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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll a[maxn];
int n;
ll m;
ll b[maxn];
bool check(ll mid){
    ll tot = 0;
    for(int i=1; i<=n; i++){
        b[i] = (mid+a[i]-1ll)/a[i];
    }
    b[n+1] = 0ll;
//    for(int i=1; i<=n; i++){
//        cout<<b[i]<<" ";
//    }
//    cout<<endl;
    for(int i=1; i<=n; i++){
        if(b[i] == 0&& i!=n )tot++;
        else {
            tot += (2ll*b[i]-1ll);
            b[i+1] -= (b[i]-1ll);
            if(b[i+1]<0) b[i+1] = 0;
        }
        if(tot>m) break;
    }
    //cout<<mid<<" "<<tot<<endl;
    if(tot<=m) return true;
    return false;
}
int main(){
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%lld", &n, &m);
        for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
        ll l=0, r=1ll*1e18;
        ll mid, ans;
        //check(8);
        while(l<r){
            mid = (l+r+1)>>1;
            if(check(mid)){
                l = mid;
                //ans = mid;
            }
            else r=mid-1ll;
        }
        printf("%lld\n", l);
    }
    return 0;
}

Color Squares(爆搜)

uva 4025
很有意思的一个搜索题，先预处理出来状态答案，然后直接进行查询就可以了

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
#define cls(a, b) memset(a, b, sizeof(a))
const int inf = 0x3f3f3f3f;
int dp[10][10][10][10];
bool vis[10][10][10][10][10][10][10][10][10];
struct Node{
    int w;
    int num[5], g[3][3];
    Node(int _w){
        w = _w;
        cls(num, 0), cls(g, 0);
    }
    Node(){}
};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool in(int x, int y){
    if(x<0||x>=3||y<0||y>=3) return false;
    return true;
}
bool check(Node p){
    if(vis[p.g[0][0]][p.g[0][1]][p.g[0][2]][p.g[1][0]][p.g[1][1]][p.g[1][2]][p.g[2][0]][p.g[2][1]][p.g[2][2]]) return false;
    vis[p.g[0][0]][p.g[0][1]][p.g[0][2]][p.g[1][0]][p.g[1][1]][p.g[1][2]][p.g[2][0]][p.g[2][1]][p.g[2][2]] = true;
    return true;
}
queue<Node> q;
void bfs(){
    while(!q.empty()) q.pop();
    Node p;
    q.push(Node(0));
    vis[0][0][0][0][0][0][0][0][0] = true;
    while(!q.empty()){
        Node t = q.front();
        q.pop();
        int &temp = dp[t.num[1]][t.num[2]][t.num[3]][t.num[4]];
        temp = min(temp, t.w);
        for(int i=0; i<3; i++) for(int j=0; j<3; j++){
            int b, r, g, y;
            b = r = g = y = 0;
            for(int c=0; c<4; c++){
                int nx = dx[c]+i;
                int ny = dy[c]+j;
                if(in(nx, ny)){
                    if(t.g[nx][ny] == 1) b++;
                    else if(t.g[nx][ny] == 2) r++;
                    else if(t.g[nx][ny] == 3) g++;
                }
            }
            int flag = t.g[i][j];
            p.w = t.w+1;
            if(flag!=1){
                for(int k=0; k<5; k++) p.num[k] = t.num[k];
                for(int k=0; k<3; k++) for(int l=0; l<3; l++){
                    p.g[k][l] = t.g[k][l];
                }
                p.g[i][j] = 1;
                p.num[flag] = t.num[flag]-1;
                p.num[1] = t.num[1]+1;
                if(check(p)) q.push(p);
            }
            if(flag!=2&&b){
                for(int k=0; k<5; k++) p.num[k] = t.num[k];
                for(int k=0; k<3; k++) for(int l=0; l<3; l++){
                    p.g[k][l] = t.g[k][l];
                }
                p.g[i][j] = 2;
                p.num[flag] = t.num[flag]-1;
                p.num[2] = t.num[2]+1;
                if(check(p)) q.push(p);
            }
            if(flag!=3&&b&&r){
                for(int k=0; k<5; k++) p.num[k] = t.num[k];
                for(int k=0; k<3; k++) for(int l=0; l<3; l++){
                    p.g[k][l] = t.g[k][l];
                }
                p.g[i][j] = 3;
                p.num[flag] = t.num[flag]-1;
                p.num[3] = t.num[3]+1;
                if(check(p)) q.push(p);
            }
            if(flag!=4&&b&&r&&g){
                for(int k=0; k<5; k++) p.num[k] = t.num[k];
                for(int k=0; k<3; k++) for(int l=0; l<3; l++){
                    p.g[k][l] = t.g[k][l];
                }
                p.g[i][j] = 4;
                p.num[flag] = t.num[flag]-1;
                p.num[4] = t.num[4]+1;
                if(check(p)) q.push(p);
            }
        }
    }
}
int b, r, g, y, w;
int main(){
    cls(dp, 0x3f);
    bfs();
    int kase = 1;
    while(~scanf("%d", &b)&&b){
        scanf("%d%d%d%d", &r, &g, &y, &w);
        int ans = inf;
        for(int i=0; i<10; i++) for(int j=0; j<10; j++)
        for(int k=0; k<10; k++) for(int l=0; l<10; l++){
            if(i*b+j*r+k*g+l*y>=w) ans = min(ans, dp[i][j][k][l]);
        }
        if(ans<inf) printf("Case %d: %d\n", kase++, ans);
        else printf("Case %d: Impossible\n", kase++);
    }
    return 0;
}

cf-1073 E(dfs+bit)

bit维护深度节点的信息，然后回归的时候将标记进行删除

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#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 = 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;
int tot, head[maxn];
struct Edge{
    int v, next;
}edge[maxn<<1];
void init(){
    tot = 0, cls(head, -1);
}
void addedge(int u, int v){
    edge[tot].v = v, edge[tot].next=head[u], head[u] = tot++;
}
ll ans[maxn];
int lowbit(int x){
    return x&(-x);
}
struct Node{
    int d, w;
    Node(int _d, int _w):d(_d), w(_w){}
};
int depth[maxn];
void bfs(){
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(1);
    depth[1] =1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(!depth[v]){
                depth[v] = depth[u]+1;
                q.push(v);
            }
        }
    }
}
ll c[maxn];
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;
}
vector<Node> node[maxn];
void dfs(int u, int fa){
    ll w;
    for(int i=0; i<node[u].size(); i++){
        w = node[u][i].w;
        add(depth[u], w), add(depth[u]+node[u][i].d+1, -w);
    }
    ans[u] += query(depth[u]);
    //cout<<"after "<<ans[u]<<endl;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    for(int i=0; i<node[u].size(); i++){
        w = node[u][i].w;
        add(depth[u], -w), add(depth[u]+node[u][i].d+1, w);
    }
}
int main()
{
    init();
    scanf("%d", &n);
    int u, v;
    for(int i=1; i<=n-1; i++){
        scanf("%d%d", &u, &v);
        addedge(u, v), addedge(v, u);
    }
    scanf("%d", &m);
    int d, x;
    while(m--){
        scanf("%d%d%d", &v, &d, &x);
        node[v].push_back(Node(d, x));
    }
    bfs();
    dfs(1, -1);
    for(int i=1; i<=n; i++) printf("%lld ", ans[i]);
    printf("\n");
    return 0;
}

cf contest 1073 F(无脑贪心)

无脑贪心

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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 = 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;
}
ll n, k;
ll x[maxn], y[maxn];
int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=1; i<=n; i ++) scanf("%lld", &x[i]);
    for(int i=1; i<=n; i++) scanf("%lld", &y[i]);
    long long a, b;
    a = b =0;
    for(int i=1; i<=n; i++){
        a = max(0ll, a+x[i]-y[i]*k);
        b = max(0ll, b+y[i]-x[i]*k);
        if(a>k||b>k){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

loj 正则表达式

主要积累一下正则表达式的匹配的执行的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
编译正则表达式 regcomp()
匹配正则表达式 regexec()
释放正则表达式 regfree()
*/
#include <bits/stdc++.h>
#include <regex.h>
using namespace std;
const int maxn = 1e2+10;
char a[maxn], b[maxn];
int main(){
    regex_t r;
    regmatch_t m;
    while(~scanf("%s%s", a, b)){
        regcomp(&r, a, 1);
        puts(regexec(&r,b,1,&m,0)||m.rm_eo-m.rm_so<strlen(b)?"No":"Yes");
        regfree(&r);
    }
}

loj 122

积累模板，强制在线

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int MaxL = 16, N = 5005;
char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline int _R() {
	int d = 0; bool ty = 1; char t;
	while (t = GC, (t < '0' || t > '9') && t != '-');
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}
inline int RD() {
	static int seed = 20010916;
	return seed =( (seed ^ 21323123)* 998244353 + 1234321237) & 0x7fffffff;
}
int n, m;
struct Graph {	//
	set<int> mt[N];
	void add(int x, int y) {
		mt[x].insert(y);
		mt[y].insert(x);
	}
	
	void del(int x, int y) {
		mt[x].erase(y);
		mt[y].erase(x);
	}
	bool find(int x, int y) {
		return mt[x].count(y);
	}
	bool empty(int x) { return mt[x].empty(); }
} G[MaxL];
struct Node {
	Node *Son[2], *fa;
	bool hav;
	int pid, tid, sz, w;
} pool[10000000], *bin[10000000], *null;
int tl;
void ninit() {
	null = pool;
	null -> Son[0] = null -> Son[1] = null -> fa = null;
	for (int i = 1; i < N * MaxL; i ++) bin[i] = pool + i;
}
struct ETT {
	Graph *G;
	set<int> e[N];
	map<int, int> mt[N];
	Node *End[2000005], *id[N]; int tote;
	Node* newnode(int id, int tid) {
		Node *x = bin[++ tl];
		x -> pid = id;
		x -> tid = tid;
		x -> w = RD();
		x -> hav = id && !G -> empty(id);
		x -> sz = 1;
		x -> Son[0] = x -> Son[1] = x -> fa = null;
		return x;
	}
	void delnode(Node *x) {
		bin[tl --] = x;
	}
	void pushup(Node *x) {
		x -> hav = (x -> pid && !G -> empty(x -> pid)) || x -> Son[0] -> hav || x -> Son[1] -> hav;
		x -> sz = x -> Son[0] -> sz + x -> Son[1] -> sz + 1;
	}
	void split_up(Node *x, Node *&l, Node *&r) {
		if (x -> fa == null) return;
		Node *y = x -> fa; x -> fa = null;
		if (y -> Son[0] == x) {
			y -> Son[0] = r;
			r -> fa = y;
			pushup(y);
			r = y;
		}
		else {
			y -> Son[1] = l;
			l -> fa = y;
			pushup(y);
			l = y;
		}
		split_up(y, l, r);
	}
	void split(Node *x, Node *&l, Node *&r) {
		l = x -> Son[0], r = x -> Son[1];
		x -> Son[0] = x -> Son[1] = l -> fa = r -> fa = null;
		pushup(x);
		split_up(x, l, r);
	}
	Node* merge(Node *l, Node *r) {
		if (l == null || r == null) return l == null ? r : l;
		if (RD()&16) {
			l -> Son[1] = merge(l -> Son[1], r);
			l -> Son[1] -> fa = l;
			pushup(l);
			return l;
		}
		else {
			r -> Son[0] = merge(l, r -> Son[0]);
			r -> Son[0] -> fa = r;
			pushup(r);
			return r;
		}
	}
	void makeroot(Node *&x) {
		if (x == null) return;
		Node *l, *r;
		split(x, l, r);
		x = merge(merge(x, r), l);
	}
	Node* findrt(Node *x) {
		while (x -> fa != null) x = x -> fa;
		while (x -> Son[0] != null) x = x -> Son[0];
		return x;
	}
	Node *findrt(int x) {
		return findrt(id[x]);
	}
	void add(int u, int v, bool lev) {
		Node *x = id[u], *y = id[v];
		if (x != null && y != null && findrt(x) == findrt(y)) {
			pushup(x), pushup(y);
			while (x -> fa != null) x = x -> fa, pushup(x);
			while (y -> fa != null) y = y -> fa, pushup(y);
			return;
		}
		makeroot(x), makeroot(y);
		End[++ tote] = newnode(x == null ? u : 0, u), mt[u][v] = tote;
		End[++ tote] = newnode(y == null ? v : 0, v), mt[v][u] = tote;
		if (lev) e[u].insert(v), e[v].insert(u);
		merge(merge(merge(End[tote - 1], y), End[tote]), x);
		if (x == null) id[u] = End[tote - 1];
		if (y == null) id[v] = End[tote];
	}
	void getid(int x) {
		if (mt[x].empty()) { id[x] = null; return; }
		id[x] = End[mt[x].begin() -> second];
		Node *l, *r;
		split(id[x], l, r);
		id[x] -> pid = x; pushup(id[x]);
		merge(merge(id[x], r), l);
	}
	int del(int u, int v) {
		int eid = mt[u][v];
		mt[u].erase(v), mt[v].erase(u);
		Node *x = End[eid], *y = End[eid ^ 1], *l, *r;
		split(x, l, r);
		merge(r, l);
		split(y, l, r);
		int t0 = l -> sz,
			t1 = r -> sz;
		if (x -> pid) getid(u);
		if (y -> pid) getid(v);
		delnode(x), delnode(y);
		return t1 < t0 ? u : v;
	}
	
	void init(int x) {
		tote = 1;
		fill(id, id + n + 1, null);
		G = :: G + x;
	}
	void _print(Node *p) {
		if (p -> Son[0] != null) _print(p -> Son[0]);
		printf("%d ", p -> tid);
		if (p -> Son[1] != null) _print(p -> Son[1]);
	}
	void print(int x) {
		Node *p = id[x];
		if (p == null) return;
		makeroot(p);
		_print(p);
		puts("");
	}
} T[MaxL];
namespace D_Graph {
	void addlevel(int level, Node *x) {
		if (x == null || !x -> hav) return;
		if (x -> pid) {
			int u = x -> pid;
			for (auto v : T[level].e[u]) if (u < v) {
				G[level].del(u, v);
				G[level + 1].add(u, v);
				T[level + 1].add(u, v, 1);
			}
			T[level].e[u].clear();
		}
		addlevel(level, x -> Son[0]);
		addlevel(level, x -> Son[1]);
		T[level].pushup(x);
	}
	Node *xrt;
	int X, Y;
	bool findin_G(int level, int x) {
		while (!G[level].empty(x)) {
			int u = *G[level].mt[x].begin();
			if (T[level].findrt(u) != xrt) {
				X = x, Y = u;
				return 1;
			}
			G[level].del(x, u);
			G[level + 1].add(x, u);
			T[level + 1].add(x, u, 0);
		}
		return 0;
	}
	bool findin_T(int level, Node *x) {
		if (x == null || !x -> hav) return 0;
		if (x -> pid) if (findin_G(level, x -> pid)) return 1;
		if (findin_T(level, x -> Son[0])) return 1;
		if (findin_T(level, x -> Son[1])) return 1;
		x -> hav = 0;
		return 0;
	}
	
	void find_replacement(int level, int x) {
		Node *p = T[level].id[x];
		xrt = p;
		if (p == null) findin_G(level, x);
		else T[level].makeroot(p), addlevel(level, p), findin_T(level, p);
	}
	void add(int x, int y) {
		G[0].add(x, y);
		T[0].add(x, y, 1);
	}
	void del(int x, int y) {
		for (int i = MaxL - 1; i >= 0; i --) if (G[i].find(x, y)) {
			G[i].del(x, y);
			if (!T[i].mt[x].count(y)) return;
			T[i].e[x].erase(y);
			T[i].e[y].erase(x);
			X = Y = 0;
			for (int j = i; j >= 0; j --) {
				//if (!T[j].mt[x].count(y)) {
					//printf("assertion failed : level %d\n", j);
					//exit(0);
				//}
				int t = T[j].del(x, y);
				if (!X) {
					find_replacement(j, t);
					if (X) T[j].add(X, Y, 1);
				}
				else T[j].add(X, Y, 0);
			}
			return;
		}
	}
	bool isconnected(int x, int y) {
		return T[0].id[x] != null && T[0].id[y] != null && T[0].findrt(x) == T[0].findrt(y);
	}
}
int main() {
	//freopen("dgraph2.in", "r", stdin);
	int i, opt, x, y, ans = 0;
	n = _R(), m = _R();
	ninit();
	for (i = 0; i < MaxL; i ++) T[i].init(i);
	for (i = 1; i <= m; i ++) {
		opt = _R(), x = _R() ^ ans, y = _R() ^ ans;
		assert(x && y);
		if (opt == 0) /*printf("Add %d %d\n", x, y), */D_Graph :: add(x, y);
		else if (opt == 1) /*printf("Del %d %d\n", x, y), */D_Graph :: del(x, y);
		else {
			ans = D_Graph :: isconnected(x, y);
			puts(ans ? "Y" : "N");
			ans = ans ? x : y;
		}
		//T[0].print(1);
		//T[0].print(2);
	}
}

codeforces contest 1062D

注意浮点数和整数运算的时候，注意规范。。。
被坑。。。没取floor就Wa了。。。
n/i不是向下取整的意思？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main(){
    scanf("%d", &n);
    ll ans = 0;
    for(int i=2; i<=n; i++){
        if(floor(1.0*n/i)>=2){
            ans += (floor(1.0*n/i)+2)*(floor(n/i)-1)/2;
        }
    }
    ans *= 4;
    cout<<ans<<endl;
    return 0;
}

codeforces contest 1062 一个连续区间的lca是什么

题意：
给定一个树形的结构，每一个询问都是一个区间，然后你可以删除区间里面的一个点，使得他们的lca最大

题解：
可以看tutorial,主要的思想就是线段树维护区间的lca和支配这个区间的两个点，这两个点的lca构成区间的lca.
然后找到这两个点之后，就能求两遍答案，之后取最优解就可以了。

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 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, q;
struct Node{
    int fa, fi, se;
    Node(int _fa, int _fi, int _se):fa(_fa), fi(_fi), se(_se){}
    Node(){}
}node[maxn<<2];
int dep[maxn];
int fa[maxn][20];
vector<int> p[maxn];
void dfs(int u, int ff){
    for(int i=0; i<p[u].size(); i++){
        int v = p[u][i];
        if(v == ff) continue;
        dep[v] = dep[u]+1;
        fa[v][0] = u;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if(dep[u]<dep[v])swap(u, v);
    for(int i=18; i>=0; i--){
        if(dep[fa[u][i]]>=dep[v]){
            u=fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i=18; i>=0; i--){
        if(fa[u][i] != fa[v][i]) u=fa[u][i], v=fa[v][i];
    }
    return fa[u][0];
}
Node merge(Node a, Node b){
    if(a.fa == -1) return b;
    if(b.fa == -1) return a;
    int ff = lca(a.fa, b.fa);
    if(a.fa == ff) return a;
    if(b.fa == ff) return b;
    return Node(ff, a.fi, b.fi);
}
void build(int rt, int l, int r){
    if(l == r) {
        node[rt] = Node(l, l, l);
        return ;
    }
    else{
        int mid = (l+r)>>1;
        build(rt<<1, l, mid);
        build(rt<<1|1, mid+1, r);
        node[rt] = merge(node[rt<<1], node[rt<<1|1]);
    }
}
Node query(int rt, int l, int r, int ql, int qr){
    if(qr<l||ql>r||l>r) {
        return Node(-1, -1, -1);
    }
    if(ql<=l && qr>=r) {
        //cout<<"in "<<l<<" "<<r<<" "<<rt<<endl;
        return node[rt];
    }
    int mid = (l+r)>>1;
    return merge(query(rt<<1, l, mid, ql, qr), query(rt<<1|1, mid+1, r, ql, qr));
}
int get(int l, int r, int i){
    return merge(query(1, 1, n, l, i-1), query(1, 1, n, i+1, r)).fa;
}
int main()
{
    scanf("%d%d", &n, &q);
    int u, v;
    for(int i=1; i<=n-1; i++){
        scanf("%d", &u);
        p[u].push_back(i+1);
    }
    dep[1] = 1, fa[1][0]=1;
    dfs(1, -1);
    for(int i=1; i<=18; i++){
        for(u=1; u<=n; u++){
            fa[u][i] = fa[fa[u][i-1]][i-1];
        }
    }
    build(1, 1, n);
//    for(int i=1; i<=25; i++){
//        cout<<i<<" "<<node[i].fa<<" "<<node[i].fi<<" "<<node[i].se<<endl;
//    }
    Node temp;
    int l, r;
    while(q--){
        scanf("%d%d", &l, &r);
        temp = query(1, 1, n, l, r);
        //cout<<temp.fi<<" "<<temp.se<<endl;
        u = get(l, r, temp.fi), v = get(l, r, temp.se);
        //cout<<dep[u]<<" "<<dep[v]<<endl;
        if(dep[u]>dep[v]){
            printf("%d %d\n", temp.fi, dep[u]-1);
        }
        else printf("%d %d\n", temp.se, dep[v]-1);
    }
    return 0;
}

带权lca的求法

luogu 3964

切比雪夫距离转化为曼哈顿距离
注意公式转换成前缀和
切比雪夫和曼哈顿距离的相互转化

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;
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{
    ll x, y;
}node[maxn];
ll prex[maxn], suffx[maxn];
ll prey[maxn], suffy[maxn];
ll xx[maxn], yy[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int x, y;
    ll u, v;
    for(int i=1; i<=n; i++) {
        //scanf("%llf%llf", &xx[i], &yy[i]);
        cin>>xx[i]>>yy[i];
        xx[i]*=10, yy[i] *= 10;
        u=(xx[i]+yy[i])/2, v=(xx[i]-yy[i])/2;
        //cout<<u<<" "<<v<<endl;
        xx[i] = u, yy[i] = v;
        node[i].x=u, node[i].y=v;
    }
    sort(xx+1, xx+1+n), sort(yy+1, yy+1+n);
//    for(int i=1; i<=n; i++) cout<<xx[i]<<" ";
//    cout<<endl;
//
//    for(int i=1; i<=n; i++) cout<<yy[i]<<" ";
//    cout<<endl;
    for(int i=1; i<=n; i++) prex[i] = prex[i-1]+xx[i], prey[i] = prey[i-1]+yy[i];
    for(int i=n; i>=1; i--) suffx[i] = suffx[i+1]+xx[i], suffy[i] = suffy[i+1]+yy[i];
    ll ans = 1e18;
    for(int i=1; i<=n; i++){
        int idx1 = lower_bound(yy+1, yy+1+n, node[i].y)-yy;
        //cout<<"ij "<<idx1<<" "<<node[i].y<<endl;
        ll part1 = idx1*node[i].y-prey[idx1]+suffy[idx1+1]-(n-idx1)*node[i].y;
        int idx2 = lower_bound(xx+1, xx+1+n, node[i].x)-xx;
        ll  part2 = idx2*node[i].x-prex[idx2]+suffx[idx2+1]-(n-idx2)*node[i].x;
        //cout<<part1<<" "<<part2<<endl;
        ans = min(ans, ll(part1+part2));
    }
   cout<<ans/10<<endl;
    return 0;
}

ICPC 2018 南京 最小球覆盖模板

link

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 <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int maxn = 1005;
inline double Sqrt(double a){
    return a<=0?0:sqrt(a);
}
inline double Sqr(double a){
    return a*a;
}
class Point_3{
    public:
        double x, y, z;
        Point_3(){}
        Point_3(double x, double y, double z):x(x),y(y),z(z){}
};
int npoint, nouter;
Point_3 pt[maxn], outer[4], res;
double radius, tmp;
double dist(Point_3 p1, Point_3 p2){
    double dx = p1.x-p2.x, dy=p1.y-p2.y, dz=p1.z-p2.z;
    return (dx*dx+dy*dy+dz*dz);
}
inline double dot(Point_3 p1, Point_3 p2){
    return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
}
void ball(){
    Point_3 q[3];
    double m[3][3], sol[3], L[3], det;
    int i, j;
    res.x = res.y = res.z = radius = 0;
    switch(nouter){
        case 1:res = outer[0];break;
        case 2:
            res.x = (outer[0].x+outer[1].x)/2;
            res.y = (outer[0].y+outer[1].y)/2;
            res.z = (outer[0].z+outer[1].z)/2;
            radius = dist(res, outer[0]);
            break;
        case 3:
            for(int i=0; i<2; i++){
                q[i].x = outer[i+1].x-outer[0].x;
                q[i].y = outer[i+1].y-outer[0].y;
                q[i].z = outer[i+1].z-outer[0].z;
            }
            for(int i=0; i<2; i++) for(int j=0; j<2; j++)
                m[i][j] = dot(q[i], q[j])*2;
            for(int i=0; i<2; i++) sol[i] = dot(q[i], q[i]);
            if(fabs(det = m[0][0]*m[1][1]-m[0][1]*m[1][0])<eps)
                return;
            L[0] = (sol[0]*m[1][1]-sol[1]*m[0][1])/det;
            L[1] = (sol[1]*m[0][0]-sol[0]*m[1][0])/det;
            res.x = outer[0].x+q[0].x*L[0]+q[1].x*L[1];
            res.y = outer[0].y+q[0].y*L[0]+q[1].y*L[1];
            res.z = outer[0].z+q[0].z*L[0]+q[1].z*L[1];
            radius = dist(res, outer[0]);
            break;
        case 4:
            for(int i=0; i<3; i++){
                q[i].x = outer[i+1].x-outer[0].x;
                q[i].y = outer[i+1].y-outer[0].y;
                q[i].z = outer[i+1].z-outer[0].z;
                sol[i] = dot(q[i], q[i]);
            }
            for(int i=0; i<3; i++) for(int j=0; j<3; j++){
                m[i][j] = dot(q[i], q[j])*2;
            }
            det = m[0][0]*m[1][1]*m[2][2]
                +m[0][1]*m[1][2]*m[2][0]
                +m[0][2]*m[2][1]*m[1][0]
                - m[0][2]*m[1][1]*m[2][0]
                - m[0][1]*m[1][0]*m[2][2]
                - m[0][0]*m[1][2]*m[2][1];
            if(fabs(det)<eps) return ;
            for(int j=0; j<3; j++){
                for(int i=0; i<3; i++) m[i][j] = sol[i];
                L[j] = (m[0][0]*m[1][1]*m[2][2]
                    +m[0][1]*m[1][2]*m[2][0]
                    +m[0][2]*m[2][1]*m[1][0]
                    - m[0][2]*m[1][1]*m[2][0]
                    - m[0][1]*m[1][0]*m[2][2]
                    - m[0][0]*m[1][2]*m[2][1])/det;
                for(int i=0; i<3; i++)
                    m[i][j] = dot(q[i], q[j])*2;
            }
            res = outer[0];
            for(int i=0; i<3; i++){
                res.x += q[i].x*L[i];
                res.y += q[i].y*L[i];
                res.z += q[i].z*L[i];
            }
            radius = dist(res, outer[0]);
    }
}
void minball(int n){
    ball();
    if(nouter<4)
        for(int i=0; i<n; i++)
            if(dist(res, pt[i])-radius > eps){
                outer[nouter] = pt[i];
                ++nouter;
                minball(i);
                --nouter;
                if(i>0){
                    Point_3 Tt = pt[i];
                    memmove(&pt[1], &pt[0], sizeof(Point_3)*i);
                    pt[0] = Tt;
                }
            }
}
double smallest_ball(){
    radius = -1;
    for(int i=0; i<npoint; i++){
        if(dist(res, pt[i])-radius > eps){
            nouter = 1;
            outer[0] = pt[i];
            minball(i);
        }
    }
    return sqrt(radius);
}
int main(){
    scanf("%d", &npoint);
    for(int i=0; i<npoint; i++){
        scanf("%lf%lf%lf", &pt[i].x, &pt[i].y, &pt[i].z);
    }
    double ans = smallest_ball();
    printf("%.15f\n", ans);
    return 0;
}

2018 南京 icpc k 搜索

图上有若干个点， 每一次都可以设置一个所有点的移动的方向，要求最后所有的点移动到一个点，移动的步骤不能超过50000，输出移动的方案。
这样的方案一定是存在的。

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
#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 mp[25][25];
struct Node{
    int x, y;
    Node(int _x = 0, int _y = 0):x(_x), y(_y){}
    bool operator < (const Node &b) const {
        if(x!=b.x) return x<b.x;
        else return y<b.y;
    }
}node[400+10];
int tx, ty;
bool test(){
    int tot = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(mp[i][j]!=-1&&mp[i][j]!=0) tot++;
        }
    }
    if(tot>=2) return true;
    return false;
}
void get_last(int &x, int &y){
    int tot = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) if(mp[i][j]!=-1&&mp[i][j]!=0) node[tot++] = Node(i, j);
    }
    sort(node, node+tot);
    x=node[0].x;
    y=node[0].y;
}
void get_far(int &x, int &y){
    int tot = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) if(mp[i][j]!=-1&&mp[i][j]!=0) node[tot++] = Node(i, j);
    }
    sort(node, node+tot);
    x=node[tot-1].x;
    y=node[tot-1].y;
}
struct Ans{
    string mov;
    int x, y;
    Ans(int _x, int _y, string _mov):x(_x), y(_y), mov(_mov){}
};
queue<Ans> q;
bool vis[25][25];
/* D U R L*/
char dir[4] = {'D', 'U', 'R', 'L'};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool check(int x, int y){
    if(vis[x][y]||mp[x][y]==-1) return false;
    if(x<=0||x>n||y<=0||y>m) return false;
    return true;
}
string bfs(int x, int y){
    while(!q.empty()) q.pop();
    cls(vis, 0);
    q.push(Ans(x, y, ""));
    vis[x][y] = true;
    while(!q.empty()){
        Ans temp = q.front();
        q.pop();
        if(temp.x == tx &&temp.y == ty){
            return temp.mov;
        }
        for(int i=0; i<4; i++){
            int nx = temp.x+dx[i];
            int ny = temp.y+dy[i];
            if(check(nx, ny)){
                vis[nx][ny] = true;
                q.push(Ans(nx, ny, temp.mov+dir[i]));
            }
        }
    }
}
string movement;
int tem[25][25];
void process(int x, int y){
    int len = movement.length();
    mp[x][y] = 0;
    //cout<<"pre "<<x<<" "<<y<<endl;
    for(int i=0; i<len; i++){
        for(int j=0; j<4; j++){
            if(movement[i] == dir[j]){
                int nx = x+dx[j];
                int ny = y+dy[j];
                if(nx<=0||nx>n||ny<=0||ny>m) break;
                if(mp[nx][ny] != -1){
                    x = nx, y = ny;
                }
                break;
            }
        }
    }
    //cout<<"after "<<x<<" "<<y<<endl;
    tem[x][y] = 1;
}
string ans;
void printans(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout<<mp[i][j];
        }
        cout<<endl;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    int x, y;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%1d", &mp[i][j]);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) if(!mp[i][j]) mp[i][j] = -1;
    }
    get_last(tx, ty);
    //cout<<tx<<" "<<ty<<endl;
    while(test()){
        get_last(tx, ty);
        get_far(x, y);
        //cout<<x<<" "<<y<<" "<<tx<<" "<<ty<<endl;
        movement = bfs(x, y);
        //cout<<movement<<endl;
        cls(tem, 0);
        for(int i=n; i>=1; i--){
            for(int j=m; j>=1; j--){
                if(mp[i][j]!=-1&&mp[i][j]!=0)
                    process(i, j);
            }
        }
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
            if(mp[i][j] != -1)mp[i][j] = tem[i][j];
        
        //printans();
        ans+=movement;
    }
    printf("%s\n", ans.c_str());
    return 0;
}

codeforce 1079 C 记忆化搜索

5倍常数就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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
bool vis[maxn][6];
int b[maxn];
int a[maxn];
int n;
bool dfs(int idx){
    if(idx == n)  return true;
    for(int i=1; i<=5; i++){
        if(vis[idx+1][i])continue;
        if((a[idx] == a[idx+1]&&i!=b[idx]) ||(a[idx]<a[idx+1]&&b[idx]<i)||
           (a[idx]>a[idx+1]&&b[idx]>i)){
               b[idx+1] = i;
               vis[idx+1][i] = true;
                if(dfs(idx+1)) return true;
           }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    bool flag = false;
    for(int i=1; i<=5; i++){
        b[1] = i;
        if(dfs(1)){
            flag = true;
            break;
        }
    }
    if(flag){
        for(int i=1; i<=n; i++) cout<<b[i]<<" ";
        cout<<endl;
    }
    else cout<<-1<<endl;
    return 0;
}

codeforces contest 1078 C–树形dp

想清楚每一种状态对用的计数的状态，不重不漏即可。
主要讨论清楚该节点与儿子节点的关系，该节点与父亲节点的关系即可

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
typedef long long ll;
const int mod = 998244353;
vector<int> G[maxn];
ll dp[maxn][3];
int n;
ll powmod(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a){
    return powmod(a, mod-2);
}
//dp[x][0]:与儿子连边形成的匹配最大
//dp[x][1]:与父亲连边匹配最大
//dp[x][2]:不连边最大
void dfs(int u, int fa){
    ll pre1=1, pre2=1;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v, u);
        pre1 = pre1*(2*dp[v][0]+dp[v][2])%mod;
        pre2 = pre2*(dp[v][0]+dp[v][2])%mod;
    }
    dp[u][2] = pre2;
    dp[u][1] = pre1;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        dp[u][0] += (dp[v][1]*pre1%mod)*inv(2*dp[v][0]+dp[v][2])%mod;
        dp[u][0] %= mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    int u, v;
    for(int i=0; i<n-1; i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, -1);
//    for(int i=1; i<=n; i++){
//        cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
//    }
    printf("%lld\n", (dp[1][0]+dp[1][2])%mod);
    return 0;
}

codeforces contest 1078 B(背包dp)

题意：
要求你给定一个k和m,你能确定每一个物品的重量。

题解：
若值的种类小于等于2，那么就是n
否则就是找m个重量相同的物品，并且这m个重量相同的不能记录在背包的状态中。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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 = 105;
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];
bool have[maxn][maxn*maxn];
bool has[maxn][maxn*maxn];
int cnt[maxn];
set<int> s;
int main()
{
    scanf("%d", &n);
    int ans = 1;
    have[0][0] = true;
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]), cnt[a[i]]++;
        //if(a[i]!=50) tot += a[i];
        s.insert(a[i]);
        for(int j=i-1; j>=0; j--){
            for(int k=0; k<maxn*maxn; k++){
                if(have[j][k]){
                    //可以到达的背包的状态
                    have[j+1][a[i]+k] = true;
                    //可以拆成j+1分， k为a[i]的倍数，但不是j倍，
                    //防止记录相同的物体的重量
                    if((a[i]+k)%(j+1)==0&&j*a[i]!=k) has[j+1][a[i]+k] = true;
                }
            }
        }
    }
    if(s.size()<=2) printf("%d\n", n);
    else{
        for(int i=1; i<=100; i++){
            for(int j=1; j<=cnt[i]; j++){
                //一旦满足就要跳出来
                if(!has[j][i*j]) ans = max(ans, j);
                else break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

codeforces contest 1077 E (从后向前贪心)

题意：
给定若干个类型的种类的个数，要求选出来的一些种类，使得后一个种类的个数是前一个种类的个数的2倍。

题解：
从后向前贪心即可

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 id[maxn];
int cnt[maxn];
int a[maxn], temp[maxn];
int main()
{
    ios::sync_with_stdio(false);
    vector<int> num;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i], temp[i] = a[i];
    sort(temp+1, temp+1+n);
    int sz = unique(temp+1, temp+1+n)-temp-1;
    for(int i=1; i<=n; i++){
        int idx = lower_bound(temp+1, temp+1+sz, a[i])-temp;
        id[i] = idx;
        cnt[idx]++;
    }
    sort(cnt+1, cnt+1+sz);
    int last = cnt[sz];
    int ans = 1;
    int pos;
    int res = 0;
    for(int i=1; i<=last; i++){
        int cur = i;
        int pos = sz;
        res = cur;
        while(pos>0&&cur%2==0){
            cur /= 2;
            pos--;
            if(cnt[pos]<cur) break;
            res += cur;
        }
        ans = max(ans, res);
    }
    cout<<ans<<endl;
    return 0;
}

poj 3585(二次换根+树形dp)

第一次dfs的时候计算以1为根的答案。
第二次进行dp的时候不断的换根进行计算。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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 = 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 n, m;
bool vis[maxn];
int deg[maxn];
int first[maxn], second[maxn];
struct Edge{
    int v, w, next;
}edge[maxn<<1];
int tot, head[maxn];
void init(){
    tot = 0, cls(head, -1);
    cls(deg, 0), cls(first, 0), cls(second, 0);
}
void addedge(int u, int v, int w){
    edge[tot].v = v, edge[tot].w = w, edge[tot].next=head[u], head[u] = tot++;
}
void dp(int u, int fa){
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].v;
        if(fa == v) continue;
        dp(v, u);
        if(deg[v] == 1)  first[u] += edge[i].w;
        else first[u] += min(first[v], edge[i].w);
    }
}
void dfs(int u, int fa){
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].v;
        if(v == fa) continue;
        if(deg[u] == 1) second[v] = first[v]+edge[i].w;
        else second[v] = first[v] + min(second[u]-min(first[v], edge[i].w), edge[i].w);
        dfs(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    scanf("%d", &_);
    while(_--){
        init();
        scanf("%d", &n);
        int u, v, w;
        for(int i=1; i<n; i++){
            scanf("%d%d%d", &u, &v, &w);
            deg[u]++, deg[v]++;
            addedge(u, v, w), addedge(v, u, w);
        }
        dp(1, 1);
//        for(int i=1; i<=n; i++) {
//            cout<<i<<" "<<first[i]<<endl;
//        }
        second[1] = first[1];
        dfs(1, -1);
        int ans = -1;
        for(int i=1; i<=n; i++) ans = max(ans, second[i]);
        printf("%d\n", ans);
    }
    return 0;
}

P1441 砝码称重 (dfs+dp计数)

注意这道题目里面的记忆化的思想

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000+10;
bool vis[35];
int now = 1;
int n, m;
int a[35];
bool f[maxn];
int ans = 0;
void count(){
    memset(f, 0, sizeof(f));
    f[0] = true;
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            for(int j=2000; j>=a[i]; j--){
                if(f[j-a[i]]) f[j] = true;
            }
        }
    }
    int cnt = 0;
    for(int i=1; i<=2000; i++) if(f[i]) cnt++;
    ans = max(ans, cnt);
}
void dfs(int tot){
    if(tot == m){
        count();
        return;
    }
    for(int i=now; i<=n; i++){
        if(!vis[i]){
            vis[i] = true;
            //强大的优化！！
            now = i+1;
            dfs(tot+1);
            vis[i] = false;
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    sort(a+1, a+1+n);
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

本文标题:代码堆2

文章作者:Babydragon

发布时间:2018-10-15, 11:32:05

最后更新:2019-03-02, 13:54:03

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

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

文章目录
  1. 1. codeforces 1064
  2. 2. Yet another 2D Walking
  3. 3. codeforces 1066 B
  4. 4. zoj 3278
  5. 5. codeforces 1066 C
  6. 6. contest1066
  7. 7. IEEE dog walking
  8. 8. BerOS File Suggestion
  9. 9. A find a number
  10. 10. E getting deals down
  11. 11. codeforces contest 1054 D
  12. 12. contest 1068 E. Multihedgehog
  13. 13. contest1073 C
  14. 14. bzoj 3124
  15. 15. contest1073 F
  16. 16. contest 1043 E
  17. 17. bzoj 1315 (T了待更) 双割
    1. 17.1. claris 跑的飞快的代码
  18. 18. codeforces 19e
  19. 19. hdu5254 （代码被叉，有反例）
  20. 20. hdu 4654(待更)
  21. 21. hdu 4115-2-sat
  22. 22. poj2914-无向图的最小割
  23. 23. gym 101964I
  24. 24. gym c
  25. 25. hdu 5988
  26. 26. hdu 5991
  27. 27. 2018icpc 沈阳G(数据结构转化为数学解)
    1. 27.1. 代码
  28. 28. Qingdao Regional Contest D Magic Multiplication (爆搜)
    1. 28.1. 代码
  29. 29. Plants vs. Zombies
    1. 29.1. <=x中最大的一个数
    2. 29.2. 代码
  30. 30. Color Squares(爆搜)
    1. 30.1. code
  31. 31. cf-1073 E(dfs+bit)
    1. 31.1. code
  32. 32. cf contest 1073 F(无脑贪心)
    1. 32.1. code
  33. 33. loj 正则表达式
  34. 34. loj 122
    1. 34.1. code
  35. 35. codeforces contest 1062D
  36. 36. codeforces contest 1062 一个连续区间的lca是什么
  37. 37. 带权lca的求法
  38. 38. luogu 3964
  39. 39. ICPC 2018 南京 最小球覆盖模板
  40. 40. 2018 南京 icpc k 搜索
  41. 41. codeforce 1079 C 记忆化搜索
  42. 42. codeforces contest 1078 C–树形dp
    1. 42.1. code
  43. 43. codeforces contest 1078 B(背包dp)
    1. 43.1. code
  44. 44. codeforces contest 1077 E (从后向前贪心)
    1. 44.1. code
  45. 45. poj 3585(二次换根+树形dp)
    1. 45.1. code
  46. 46. P1441 砝码称重 (dfs+dp计数)
    1. 46.1. code
{{ live2d() }}