好题挑选

ACM

整理模板

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

图的染色问题

将一个图染色，使得相邻的节点的颜色都不相同，问最少用几种颜色
输入：
n个点m条边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int maxm = 2e6+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
struct Node{
    int v, w, next;
}node[maxm];
int tot, head[maxn];
void add_edge(int u, int v){
    node[tot].v=v, node[tot].next=head[u], head[u]=tot++;
}
int flag[maxn];
//指向下一个势最大的点
int pt[maxn];
int size[maxn];
int color[maxn];
int main()
{
    tot = 0, cls(head, -1);
    scanf("%d%d", &n, &m);
    int u, v;
    for(int i=1; i<=m; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v), add_edge(v, u);
    }
    for (int i=n;i>=1;--i){
        int cur=0;
        for (int j=1;j<=n;++j)
            if (!flag[j]&&size[j]>=size[cur])
                cur=j;
        flag[cur]=1; pt[i]=cur;
        for (int j=head[cur];~j;j=node[j].next) size[node[j].v]++;
    }
    memset(flag,0,sizeof(flag));
    int ans = 0;
    for (int i=n;i>=1;--i){
        for (int j=head[pt[i]];~j;j=node[j].next)
            flag[color[node[j].v]]=i;
        color[pt[i]]=1;
        while (flag[color[pt[i]]]==i)
            color[pt[i]]++;
        ans=max(ans,color[pt[i]]);
    }
    printf("%d\n",ans);
    return 0;
}

BM模板

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(; b; b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
int t;
ll n;
namespace linear_seq
{
    const int N=10010;
    ll res[N],base[N],_c[N],_md[N];
    vector<int> Md;
    void mul(ll *a,ll *b,int k)
    {
        rep(i,0,k+k) _c[i]=0;
        rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for (int i=k+k-1; i>=k; i--) if (_c[i])
                rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    ll solve(ll n,VI a,VI b)   // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
    {
    //        printf("%d\n",SZ(b));
        ll ans=0,pnt=0;
        int k=SZ(a);
        assert(SZ(a)==SZ(b));
        rep(i,0,k) _md[k-1-i]=-a[i];
        _md[k]=1;
        Md.clear();
        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while ((1ll<<pnt)<=n) pnt++;
        for (int p=pnt; p>=0; p--)
        {
            mul(res,res,k);
            if ((n>>p)&1)
            {
                for(int i=k-1; i>=0; i--) res[i+1]=res[i];
                res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        rep(n,0,SZ(s))
        {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if (d==0) ++m;
            else if (2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L;
                B=T;
                b=d;
                m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        //rep(i,0,SZ(C))printf("%dx[%d]%s",C[i],i,i+1==SZ(C)?"=0\n":"+");
        return C;
    }
    ll gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};
int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%lld",&n);
        printf("%lld\n", linear_seq::gao(VI{31, 197, 1255, 7997, 50959, 324725, 2069239, 13185773, 84023455, 535421093, 411853810},n-2));
    }
}

敌对搜索

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+10;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, k, l;
int a[maxn], b[maxn], c[maxn];
int dp[1005][200+10];
const int TH = 100;
/*
4: good
2: normal
1: bad
*/
int dfs(int p, int now){
    if(p == n){
        if(now>=k) return 4;
        if(now<=l) return 1;
        return 2;
    }
    if(dp[p][now+TH]) return dp[p][now+TH];
    int &ans = dp[p][now+TH];
    int want, hate;
    if(p&1){
        want = 1, hate = 4;
    }
    else want = 4, hate = 1;
    bool flag = false;
    if(a[p]) {
		int ret= dfs(p+1, min(now+a[p], TH));
		if(ret==want) return ans = want;
		if(ret!=hate) flag = true;
	}
	if(b[p]) {
		int ret = dfs(p+1, max(now-b[p], -TH));
		if(ret==want) return ans = want;
		if(ret!=hate) flag = true;
	}
	if(c[p]) {
		int ret= dfs(p+1, -now);
		if(ret==want) return ans = want;
		if(ret!=hate) flag = true;
	}
	if(flag) return ans = 2;
	else return ans = hate;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &l);
    for(int i=0; i<n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
    int res = dfs(0, m);
    if(res == 4){
        printf("Good Ending\n");
    }
    else if(res == 1) printf("Bad Ending\n");
    else printf("Normal Ending\n");
    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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;
}

最长链的变形

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

公共的点的数量最大
在满足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
#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;
}

浮点数版本的最小费用流

注意用了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
#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;
}

线段树维护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
#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;
}

注意事项

__builtin_popcount不能统计long long 类型的1的个数

那种bfs搜索的时候一定要注意是否有无限的状态，否则要用优先队列来维护

unordered_map来代替map或者set

二分的第二种形式 <=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;
}

整数与浮点数

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

multiset 查找删除

1
2
3
multiset<int>::iterator it = s.find(*s.begin());
s.erase(it);
s.insert(a[i]);

切比雪夫距离与欧拉距离的相互转化

将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离

将一个点(x,y)的坐标变为(x+y2,x−y2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离

例题

找一个点，使得所有点到该点的切比雪夫距离综合最小

切比雪夫距离转化为欧式距离。欧式距离进行排序进行前缀优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 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;
}

dfs搜索的时候记性记忆化优化

统计砝码能称多种的东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}

未解决的问题

本文标题:好题挑选

文章作者:Babydragon

发布时间:2018-11-21, 21:32:03

最后更新:2018-11-22, 17:38:41

原始链接:http://baolintian.github.io/2018/11/21/好题挑选/

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

文章目录
  1. 1. 带权lca+最短路
  2. 2. 图的染色问题
  3. 3. BM模板
  4. 4. 敌对搜索
  5. 5. 保存最长链上面的所有的节点
  6. 6. 最长链的变形
  7. 7. 浮点数版本的最小费用流
  8. 8. 线段树维护lca
  9. 9. 注意事项
    1. 9.1. 二分的第二种形式 <=x中最大的一个数
    2. 9.2. 整数与浮点数
    3. 9.3. multiset 查找删除
  10. 10. 切比雪夫距离与欧拉距离的相互转化
    1. 10.1. 例题
  11. 11. dfs搜索的时候记性记忆化优化
  12. 12. 未解决的问题
{{ live2d() }}