标签归档:洛谷

洛谷 P3386 【模板】二分图匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<list>
#include<cmath>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, e;
vector<int> edges[2005];
bool visited[2005];
int match[2005];
bool biFind(int node) {
    if (visited[node])return false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {
            match[node] = edges[node][i];
            match[edges[node][i]] = node;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        if (u > n || v > m)continue;
        edges[u].push_back(v + n);
        edges[v + n].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, false, sizeof(visited));
        if (biFind(i))cnter++;
    }
    cout << cnter;
}

洛谷 P3379 【模板】最近公共祖先(LCA)重写

朴素算法:洛谷70分,O2 80分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<vector>
using namespace std;
int n, m, s;
vector<int> edges[500005];
int father[500005],depth[500005];
void dfs(int node, int fath) {
    father[node] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    while (a != b) {
        if (depth[a] >= depth[b])a = father[a];
        else b = father[b];
    }
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

倍增:洛谷80分,O2 100分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
#include<algorithm>
#define MAXLOG 20
using namespace std;
int n, m, s;
vector<int> edges[500005];
int depth[500005];
int ancestor[500005][MAXLOG+2];
void dfs(int node, int fath) {
    ancestor[node][0] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    if (depth[b] > depth[a])swap(a, b);
    for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i];
    if (a == b)return a;
    for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){
        a = ancestor[a][i];
        b = ancestor[b][i];
    }
    return ancestor[a][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

Tarjan:洛谷70分,O2 100分

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<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, s;
vector<int> edges[500005],askPair[500005];
bool visited[500005];
int father[500005];
inline int _find(int node) {
    if (father[node]==-1)return node;
    return father[node] = _find(father[node]);
}
inline void _union(int x, int y) {
    if(_find(x)!=_find(y))father[_find(x)] = y;
}
struct ask {
    int u, v;
    int ans;
}asks[500005];
inline int checkV(int id,int node) {
    if (asks[id].u != node)return asks[id].u;
    return asks[id].v;
}
void dfs(int node,int fath) {
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i],node);
        _union(edges[node][i], node);
    }
    visited[node] = true;
    for (int i = 0; i < askPair[node].size(); i++) {
        int v = checkV(askPair[node][i], node);
        if (visited[v])asks[askPair[node][i]].ans = _find(v);
    }
}
int main() {
    memset(father, -1, sizeof(father));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        cin >> asks[i].u >> asks[i].v;
        askPair[asks[i].u].push_back(i);
        askPair[asks[i].v].push_back(i);
    }
    dfs(s,s);
    for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n";
}

洛谷 P1022 计算器的改良

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int ratio = 0, constant = 0;
#define IfLetter if (ch <= 'Z'&&ch >= 'A' || ch <= 'z'&&ch >= 'a')
#define IfNumber if (ch >= '0'&&ch <= '9' || ch=='+' || ch=='-')
int main() {
    char letter;
    char ch;
    int num = 0;
    bool flag = true;
    while ((ch = getchar()) != '\n') {
        IfNumber{ // number(maybe with variable)
            ungetc(ch, stdin);
            int re = scanf("%d", &num); //specially prepared for the testcase form like "-a"
            if (re == 0) {
                getchar();
                ratio -= (flag ? 1 : -1);
            }
            ch = getchar();
            IfLetter{
                ratio += num * (flag ? 1 : -1);
                letter = ch;
            }
            else {
                constant += num * (flag ? 1 : -1);
                ungetc(ch, stdin);
            }
            num = 0;
        }
        else IfLetter{ //pure variable without ratio
            letter = ch;
            ratio+=(flag ? 1 : -1);
        }
        else if (ch == '=') {
            flag = false;
        }
    }
    printf("%c=%.3lf", letter, -1.0*constant / ratio);
}

洛谷 P2114 [NOI2014]起床困难综合症

参看题解:
https://www.luogu.org/blog/user17941/solution-p2114
https://www.luogu.org/blog/user25845/solution-p2114

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n, m, t[100005];
string s[100005];
int zero = 0, one = 0x7fffffff;
int ans = 0;
void process(int & x) {
    for (int i = 1; i <= n; i++) {
        switch (s[i][0]) {
        case 'A':
            x &= t[i];
            break;
        case 'O':
            x |= t[i];
            break;
        case 'X':
            x ^= t[i];
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> s[i] >> t[i];
    process(zero);
    process(one);
    for (int i = 31; i >= 0; i--) {
        if (ans + (1 << i) > m)continue;
        if (!(zero&(1<<i))&&(one&(1 << i)))ans |= (1 << i);
    }
    process(ans);
    cout << ans;
}

洛谷 P1972 [SDOI2009]HH的项链

参考题解:https://www.luogu.org/blog/skylee/solution-p1972

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
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int arr[500005];
int c[500000];
int last[1000001];
int flag=0;
struct question{
    int id,l,r,ans;
    bool operator < (const question& q2) const{
        if(flag==0)return r<q2.r;
        else return id<q2.id;
    }
}qs[200005];
inline int lowbit(int i){
    return i&(-i);
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int i,int v){
    while(i<=n){
        c[i]+=v;
        i+=lowbit(i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>qs[i].l>>qs[i].r;
        qs[i].id=i;
    }
    sort(qs+1,qs+m+1);
    int ptr=1;
    for(int i=1;i<=m;i++){
        for(;ptr<=qs[i].r;ptr++){
            if(last[arr[ptr]]!=0)update(last[arr[ptr]],-1);
            update(last[arr[ptr]]=ptr,1);
        }
        qs[i].ans=query(qs[i].r)-query(qs[i].l-1);
    }
    flag=1;
    sort(qs+1,qs+m+1);
    for(int i=1;i<=m;i++){
        cout<<qs[i].ans<<endl;
    }
}

洛谷 P2023 [AHOI2009]维护序列

没啥说的,和上一道题一模一样。。只是把输入改掉就可以了。。

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<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3373 【模板】线段树 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
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3368 【模板】树状数组 2

看起来实际上也挺好做的,就是只要把树状数组维护的对象改成原序列的差分数组即可。这样每次树状数组所谓的query求1到n的前缀和也就变成了就单点n的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
using namespace std;
struct BTA{//Update Section,Query Single Point
    const static int MAX=500000;
    int C[MAX+5];
    BTA(){
        memset(C,0,sizeof(C));
    }
    int lowbit(int i){
        return i&(-i);
    }
    int query(int x){
        int sum=0;
        while(x>0){
            sum+=C[x];
            x-=lowbit(x);
        }
        return sum;
    }
    void update(int i,int v){
        while(i<=MAX){
            C[i]+=v;
            i+=lowbit(i);
        }
    }
    void updateSection(int l,int r,int v){
        update(l,v);
        update(r+1,-v);
    }
}TA;
int n,m;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        TA.updateSection(i,i,v);
    }
    for(int i=1;i<=m;i++){
        int op,v1,v2,v3;
        cin>>op;
        if(op==1){
            cin>>v1>>v2>>v3;
            TA.updateSection(v1,v2,v3);
        }
        else{
            cin>>v1;
                cout<<TA.query(v1)<<endl;
        }
    }
}

洛谷 P1197 [JSOI2008]星球大战

总算是没看题解自己A了一道题,呜呜呜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
int father[400005];
int _find(int node){
    if(father[node]==-1)return node;
    return father[node]=_find(father[node]);
}
bool _union(int x,int y){
    if(_find(x)==_find(y))return false;
    father[_find(x)]=_find(y);
    return true;
}
int n,m,k;
bool alive[400005];
vector<int> edges[400005];
stack<int> ans;
stack<int> q;
int cnt,cntn;
int main(){
    ios::sync_with_stdio(false);
    memset(father,-1,sizeof(father));
    memset(alive,true,sizeof(alive));
    cin>>n>>m;
    cnt=0;cntn=n;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int v;
        cin>>v;
        alive[v]=false;
        q.push(v);
        cntn--;
    }
    for(int i=0;i<n;i++){
        if(!alive[i])continue;
        for(int j=0;j<edges[i].size();j++){
            if(!alive[edges[i][j]])continue;
            if(_union(i,edges[i][j]))cnt++;
        }
    }
    ans.push(cntn-cnt);
    while(!q.empty()){
        int cur=q.top();q.pop();
        cntn++;
        alive[cur]=true;
        for(int i=0;i<edges[cur].size();i++){
            if(!alive[edges[cur][i]])continue;
            if(_union(cur,edges[cur][i]))cnt++;
        }
        ans.push(cntn-cnt);
    }
    while(!ans.empty()){
        cout<<ans.top()<<endl;
        ans.pop();
    }
}

洛谷 P1199 三国游戏

https://www.luogu.org/blog/user23248/solution-p1199

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int n,a[501][501],maxV;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>a[i][j];
            a[j][i]=a[i][j];   
        }
    }
    for(int i=1;i<=n;i++){
        sort(a[i]+1,a[i]+n+1);
        maxV=max(maxV,a[i][n-1]);
    }
    cout<<1<<endl<<maxV;
}