Znzryb's Blog
0%

Posted on Edited on

思路讲解

无向图判环模版题，做cf之前来练练手

// 如果union函数发现根本不需要合并，那么a本来就在b的这个集合内

// 说明b有两条到达a的通路即形成了环

比较重要的两句话

AC代码

union是保留字，建议改为add（意思反正是这个意思）；

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
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> fa(1010);
        int n=edges.size();
        for(int i=1;i<=n;++i){  // 并查集初始化
            fa[i]=i;
        }
        for(int i=0;i<n;++i){
            int a=edges[i][0],b=edges[i][1];
            // 如果union函数发现根本不需要合并，本来就在这个集合内
            // 说明b有两条到达a的通路即形成了环
            if(!unionn(a,b,fa)){
                return {a,b};
            }
        }
        return {0,0};
    }
    int find(int x , vector<int> &fa){
        if(fa[x]!=x)
            fa[x]=find(fa[x],fa);
        return fa[x];
    }
    bool unionn(int a, int b, vector<int>& fa){
        if(find(a,fa)==find(b,fa)){
            return false;
        }else{
            fa[find(a,fa)]=find(b,fa);
            return true;
        }
    }
};

心路历程（WA，TLE，MLE……）

哈哈，第一次写力扣嘛，总归会遇到点问题，比如啥全角字符，什么union保留字，什么·······，不多赘述。

Posted on Edited on

思路讲解

主要思路与洛谷题解类似

主要思路就是先把所有点给打散，再连起来

打散比较简单，发现这个点入度≥2就持续删边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;++i) {
            if(g[i].size()>=2) {    // 入度>=2
                vector<int> temp;
                for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
                    temp.push_back(*it);
                }
                while (temp.size()>1) {
                    int a=temp.back();
                    temp.pop_back();
                    int b=temp.back();
                    del(i,a,b);
                }
            }
        }

重新连起来需要root1和root2，否则连不起来

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// root,root2就是根，所有的操作都是他衍生出来的
if(!isCool) {
    for(int i=1;i<=n;++i) {
        if(vis[i])
            continue;
        vis[i]=true;
        add(root,root2,i);
        root2=i;
        if(g[i].size()==0) {
            continue;
        }
        vis[*g[i].begin()]=true;
    }
}

AC代码

https://codeforces.com/contest/2029/submission/292760535

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(1e5)+10;
int n,T,m;
set<int> g[N];
bitset<N> vis;
struct op {
    int a,b,c;
};
vector<op> ans;

inline void del(int a,int b, int c) {
    op temp;
    temp.a=a,temp.b=b,temp.c=c;
    ans.push_back(temp);
    // 删除
    g[a].erase(b);g[a].erase(c);
    g[b].erase(a);g[c].erase(a);
    // a与b，c关系明晰，但是b，c关系不明，故需要检验判断
    if(g[b].count(c)==1)
        g[b].erase(c),g[c].erase(b);
    else
        g[b].insert(c),g[c].insert(b);
}

inline void add(int a,int b,int c) {
    op temp;
    temp.a=a,temp.b=b,temp.c=c;
    ans.push_back(temp);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>T;
    while (T--) {
        cin>>n>>m;
        vis.reset();    // 初始化
        for(int i=1;i<=n;++i) {
            g[i].clear();
        }
        ans.clear();
        if(m==0) {
            cout<<0<<endl;
            continue;
        }
        for(int _=1;_<=m;++_) {
            int a,b;
            cin>>a>>b;
            g[a].insert(b);     // g里面其实是个set
            g[b].insert(a);
        }
        for(int i=1;i<=n;++i) {
            if(g[i].size()>=2) {    // 入度>=2
                vector<int> temp;
                for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
                    temp.push_back(*it);
                }
                while (temp.size()>1) {
                    int a=temp.back();
                    temp.pop_back();
                    int b=temp.back();
                    temp.pop_back();
                    del(i,a,b);
                }
            }
        }
        bool isCool=true;
        int root,root2;
        for(int i=1;i<=n;++i) {     // 检验是否删完以后成为空图了
            if(g[i].size()==1) {
                isCool=false;
                root=i;
                root2=*g[i].begin();
                vis[i]=true,vis[*g[i].begin()]=true;
                break;
            }
        }
        // root,root2就是根，所有的操作都是他衍生出来的
        if(!isCool) {
            for(int i=1;i<=n;++i) {
                if(vis[i])
                    continue;
                vis[i]=true;
                add(root,root2,i);
                root2=i;
                if(g[i].size()==0) {
                    continue;
                }
                vis[*g[i].begin()]=true;
            }
        }
        cout<<ans.size()<<"\n";
        for(int i=0;i<ans.size();++i) {
            cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<"\n";
        }
    }
    return 0;
}
// AC https://codeforces.com/contest/2029/submission/292760535

心路历程（WA，TLE，MLE……）

原来的思路是找环，删点，但发现无向图找环很麻烦，也无法满足我的需求，于是还是决定变树。

无向图找环，用dfs加dsu（并查集）

如果不太会的话建议左转去做leetcode684冗余连接

初始化要彻底

1
2
3
4
5
vis.reset();    // 初始化
for(int i=1;i<=n;++i) {
    g[i].clear();
}
ans.clear();

Posted on Edited on

AC代码

dp0/1/2[0] i 之后的最高评分 ，代表其中 i 次比赛是在跳过的间隔之前/之中/之后。

其实没啥好多说的，就是题解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
#include <bits/stdc++.h>
#define  int long long

using namespace std;
const int N=static_cast<int>(3e5)+10;
int T,n;
int A[N],dp[N][5],ra[N];

struct record {
    int l,r,s;
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>T;
    while (T--) {
        cin>>n;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
        }
        int curS=0;
        for(int i=1;i<=n;++i) {
            if(A[i]>curS) {
                curS+=1;
            }else if (A[i]<curS) {
                curS-=1;
            }
            ra[i]=curS;
        }
        if(curS==n) {       // 搞个特判
            cout<<curS-1<<endl;
            continue;
        }
        dp[1][0]=1;     // 前
        dp[1][1]=0;     // 中
        dp[1][2]=1;     // 后
        for(int i=2;i<=n;++i) {
            if(A[i]>dp[i-1][0])
                dp[i][0]=dp[i-1][0]+1;
            else if(A[i]<dp[i-1][0])
                dp[i][0]=dp[i-1][0]-1;
            else
                dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]);    // 是继承空缺，还是继承连续，这是个问题
            int temp=0;
            if(A[i]>dp[i-1][1])
                temp=dp[i-1][1]+1;
            else if(A[i]<dp[i-1][1])
                temp=dp[i-1][1]-1;
            else
                temp=dp[i-1][1];
            int temp2;
            if(A[i]>dp[i-1][2])
                temp2=dp[i-1][2]+1;
            else if(A[i]<dp[i-1][2])
                temp2=dp[i-1][2]-1;
            else
                temp2=dp[i-1][2];
            dp[i][2]=max({dp[i][0],temp,temp2});
        }
        cout<<max(dp[n][1],dp[n][2])<<endl;
    }
    return 0;
}
// AC https://codeforces.com/contest/2029/submission/292353225

心路历程（WA，TLE，MLE……）

一次AC，dp是这样的

Posted on Edited on

事实证明人还是不要太固执，我之前就是一定想要写一个搜索算法，但怎么写都TLE，即便我看了hint知道是dp，还是想写搜索，但最后一发dp AC了。怎么说呢，搜索的时间复杂度还是有点玄学，也可能是我学艺不精（bushi）。其实我感觉如果你知道这题是dp的话也不是说非常难写，毕竟我这个非常抗拒dp的写出来了嘛

思路讲解

我们先想一个朴素dp，一个牌可以换到n牌当且仅当他可以换到 n牌 或 之前可以换到n牌的牌（为简化，我们称之为A牌），那就把所有这些牌都遍历一下就知道能不能换到了。

当然这个朴素dp的时间复杂度就比较随缘，最坏情况可能有O（n**2），而且其实也不是很好写。

然后我们小小的优化一下（这种优化我感觉挺常见的），其实能不能换到就是看能不能换到A牌当中优先度最低的牌。

当然三个人对牌的优先度不同，我们用pair<char,int> lowq,lowk,lowj; 分别存一下A牌中在qkj中优先度最小的。

这是对他们的初始化

1
2
3
lowq=make_pair('q',n);
lowk=make_pair('k',n);
lowj=make_pair('j',n);

我们以这段代码为例，这个牌成功换到了A牌中q优先度最小的，q不用更新，他的优先度肯定更高。

lowk以及lowj需要更新，这个 i 牌可能比他们的优先度更小。

1
2
3
4
5
6
7
8
if(pq[i]>pq[lowq.second]) {
      isReach[i]=true;
      dp[i]=lowq;
      if(pk[i]<pk[lowk.second])
          lowk=make_pair('k',i);
      if(pj[i]<pj[lowj.second])
          lowj=make_pair('j',i);
}

最后答案输出就很简单了，跳着存入ans，玩过邻接表的都不会陌生

1
2
3
for(int i=1;i<n;i=dp[i].second) {
    ans.push_back(dp[i]);
}

AC代码

提交记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(2e5)+17;
int pq[N],pk[N],pj[N];
int T,n;
vector<pair<char,int> > ans;
bitset<N> isReach;
pair<char,int> dp[N],lowq,lowk,lowj;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        // 初始化
       ans.clear(),isReach.reset();
        for(int i=1;i<=n;++i) cin>>pq[i];
        for(int i=1;i<=n;++i) cin>>pk[i];
        for(int i=1;i<=n;++i) cin>>pj[i];
        lowq=make_pair('q',n);
        lowk=make_pair('k',n);
        lowj=make_pair('j',n);
        for(int i=n-1;i>=1;--i) {
            if(pq[i]>pq[lowq.second]) {
                isReach[i]=true;
                dp[i]=lowq;
                if(pk[i]<pk[lowk.second])
                    lowk=make_pair('k',i);
                if(pj[i]<pj[lowj.second])
                    lowj=make_pair('j',i);
            }
            if(pk[i]>pk[lowk.second]) {
                isReach[i]=true;
                dp[i]=lowk;
                if(pq[i]<pq[lowq.second])
                    lowq=make_pair('q',i);
                if(pj[i]<pj[lowj.second])
                    lowj=make_pair('j',i);
            }
            if(pj[i]>pj[lowj.second]) {
                isReach[i]=true;
                dp[i]=lowj;
                if(pk[i]<pk[lowk.second])
                    lowk=make_pair('k',i);
                if(pq[i]<pq[lowq.second])
                    lowq=make_pair('q',i);
            }
        }
        if(!isReach[1]) {
            cout<<"NO"<<endl;
            continue;
        }
        cout<<"YES"<<endl;
        for(int i=1;i<n;i=dp[i].second) {
            ans.push_back(dp[i]);
        }
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();++i) {
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

一个暴搜dfs代码TLE

在第11个点TLE了，加了快读也不太行

19999个撑不住了

当然这个TLE之前肯定还出了点事，最重要的是把退出条件放在最前面，而且任何退出条件后进来的全部是多余的，ans需要pop一下。

1
2
3
4
if(isFind) {
        ans.pop_back();
        return;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(2e5)+17;
int pq[N],pk[N],pj[N];
int T,n;
bool isFind;
vector<pair<char,int> > ans;
bitset<N> vis;

void dfs(int x) {   // x即为当前持有的卡牌
    if(isFind) {
        ans.pop_back();
        return;
    }
    if(x==n) {
        isFind=true;
        return;
    }
    if(vis[x])
        return;
    vis[x]=true;
    for(int i=x+1;i<=n;++i) {
        if(isFind)
            return;
        // 可以看到，emplace_back支持直接传入构造函数的参数来构造创建元素，而push_back必须先构造元素，再通过复制构造函数传入。
        if(pq[i]<pq[x]) {
            ans.emplace_back('q',i);
            dfs(i);
            if(!isFind)
                ans.pop_back();
        }
        if(pk[i]<pk[x]) {
            ans.emplace_back('k',i);
            dfs(i);
            if(!isFind)
                ans.pop_back();
        }
        if(pj[i]<pj[x]) {
            ans.emplace_back('j',i);
            dfs(i);
            if(!isFind)
                ans.pop_back();
        }
    }
}

signed main()
{
    cin>>T;
    while (T--) {
        cin>>n;
        // 初始化
        isFind=false,ans.clear(),vis.reset();
        for(int i=1;i<=n;++i) {
            cin>>pq[i];
        }
        for(int i=1;i<=n;++i) {
            cin>>pk[i];
        }
        for(int i=1;i<=n;++i) {
            cin>>pj[i];
        }
        dfs(1);
        if(!isFind) {
            cout<<"NO"<<endl;
            continue;
        }
        cout<<"YES"<<endl;
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();++i) {
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }
    }
    return 0;
}

Posted on Edited on

思路排除

这题乍一看好像是二分答案，但仔细一看好像还不太对，毕竟1600，太板了也不太好。

如果这题考二分的话，题面可能是让你求这个v最大可以为多少，这个非常适合二分答案，但显然这题不是这么问的。

我看见以前qq群里有人问什么时候用二分答案（牛客最近一场小白月赛出了道这个），我个人的回答是，你看到一道觉得像的题，都可以想一想能不能用二分答案，然后想一想检查器好不好写？如果检查器复杂度太高（跑一遍就超时），或者检查器所需要的算法可以直接求出该题答案，那么就不太行。

有些时候你也不要对自己要求太高，什么看一眼就知道怎么做。一般来说出现这种情况要么这道题太板了，要么这道题相对于你来说太简单了，我个人认为遇到这种情况大概率这题都不太适合于你平时练习，反而是你要想一想才对于你有提升吧。

思路讲解

搞两个数组存一下，到该位置能有多少个蛋糕（一个从左到右，一个从右到左，以消除左向依赖以及右向依赖）

具体而言是这样的

image

那么，然后如果我们要知道Alice把 [l,r] 这块区域切给自己后，剩下的我怎么知道够不够分那？

L[],R[]现在就开始发挥作用了

剩下区间的蛋糕总数就是L[l-1]+R[r+1]

1
2
3
4
5
6
// 剩下区间的蛋糕总数就是L[l-1]+R[r+1]
inline bool check(int l,int r) {
    if(L[l-1]+R[r+1]<m)
        return false;
    return true;
}

写好 check( ) 剩下的事就简单了，就是用双指针去遍历每种可能的区间，不断更新答案就好了（用的事Acwing的模版）

1
2
3
4
5
6
for(int i=1,j=1;i<=n;++i) {
      while (check(i,j) && j<=n) {
          ans=max(ans,sumA[j]-sumA[i-1]);
          ++j;
      }
  }

AC代码

AC记录

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 <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(2e5)+15;
int T,n,m,v,A[N],sumA[N],L[N],R[N];

inline bool check(int l,int r) {
    if(L[l-1]+R[r+1]<m)
        return false;
    return true;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n>>m>>v;
        for(int i=0;i<=n+10;++i)    // 初始化，因为有可能用到超范围部分，所以多初始化一道
            A[i]=0,sumA[i]=0,L[i]=0,R[i]=0;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
            sumA[i]=A[i]+sumA[i-1];
        }
        int curT=0;
        for(int i=1;i<=n;++i) {
            curT+=A[i];
            if(curT>=v)
                curT=0,L[i]=L[i-1]+1;
            else
                L[i]=L[i-1];
        }
        curT=0;
        for(int i=n;i>=1;--i) {
            curT+=A[i];
            if(curT>=v)
                curT=0,R[i]=R[i+1]+1;
            else
                R[i]=R[i+1];
        }
        if(L[n]<m) {
            cout<<-1<<endl;
            continue;
        }
        int ans=0;
        for(int i=1,j=1;i<=n;++i) {
            while (check(i,j) && j<=n) {
                ans=max(ans,sumA[j]-sumA[i-1]);
                ++j;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
// https://codeforces.com/contest/2028/submission/291995395

心路历程（WA，TLE，MLE……）

最早我觉得是二分答案，但接着发现不对。

代码我就不放了，主要原因是这个分蛋糕的Alice不是这m个生物中的一个，如果这题考二分的话，题目可能让你求这个v最大可以为多少。

记得把数组开大点，前面提交out of bound 了

image

然后不要动不动return 0;

&& j≤n 是可以加的，虽然之后的i其实就进入不到这个while里了，但先前的i一定比之后的i更优秀在这种情况下（你想想看，r确定了，l越来越大，[l,r]越来越像，Alice份给自己的就越来越少）

image