Blackops

初心易得，始终难守

0%

CF Educational #42 A B C D F

发表于 分类于 ，

A.Equator

坑点在在于int除2的时候是向下取整的所以还是乘以2好……

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200005;
LL arr[N];

int main(void)
{
    int n, i;
    scanf("%d", &n);
    LL sum = 0;
    for (i = 1; i <= n; ++i)
    {
        scanf("%I64d", arr + i);
        sum += arr[i];
    }
    LL t = 0;
    for (i = 1; i <= n; ++i)
    {
        t += arr[i];
        if (t * 2 >= sum)
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

B.Students in Railway Carriage

题意就是给你$n$个位置，在空位上放置$a$个学生和$b$个运动员使得放置的总人数最多。

记录一下前一个放的是谁，贪心地放和前面一个不冲突的就行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2e5 + 7;
char s[N];

int main(void)
{
    int n, a, b, i;
    scanf("%d%d%d", &n, &a, &b);
    scanf("%s", s + 1);
    int p = -1;
    int c = 0;
    for (i = 1; i <= n; ++i)
    {
        if (s[i] == '.')
        {
            if (p == -1)
            {
                if (a && (a >= b))
                {
                    --a;
                    ++c;
                    p = 1;
                }
                else if (b && b >= a)
                {
                    --b;
                    ++c;
                    p = 2;
                }
                else
                    p = -1;
            }
            else
            {
                if (p == 1 && b > 0)
                {
                    --b;
                    ++c;
                    p = 2;
                }
                else if (p == 2 && a > 0)
                {
                    --a;
                    ++c;
                    p = 1;
                }
                else
                    p = -1;
            }
        }
        else
            p = -1;
    }
    printf("%d\n", c);
    return 0;
}

C.Make a Square

题意就是给你一个数$n$删掉最少的位数变成平方数，结果不能带前导$0$

无脑BFS或者DFS都行，注意判断前导$0$就行。stoll真是好用

代码：

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>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);


inline int check(const string &x)
{
    if (x.size() >= 1 && x[0] == '0')
        return 0;
    LL d = stoll(x);
    LL q = sqrt(d);
    return q * q == d;
}
int bfs(const string &s)
{
    queue<pair<string, int> >Q;
    Q.push({s, 0});
    while (!Q.empty())
    {
        auto u = Q.front();
        Q.pop();
        if (check(u.first))
            return u.second;
        for (int i = 0; i < u.first.size(); ++i)
        {
            string tt = u.first;
            tt.erase(i, 1);
            if ((int)tt.size() >= 1)
                Q.push({tt, u.second + 1});
        }
    }
    return -1;
}
int main(void)
{
    string k;
    while (cin >> k)
    {
        cout << bfs(k) << endl;
    }
    return 0;
}

D.Merge Equals

题意就是给你$n$个数的序列，每次不停地找两个出现次数大于等于$2$的数，拿出其最靠左的两个位置$p1$和$p2$，然后把前面的数加到后面去，消掉前面的，直到不存在出现次数大于等于$2$的数为止。

实际上是个模拟题，鉴于数据范围稍大，因此用map维护每个数的出现次数，一个堆维护出现次数大于等于$2$的数中最小的数，再用一个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
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>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 150005;
LL arr[N];
map<LL, int>cnt;
map<LL, deque<int> >pos;
map<LL, int>vis;

struct info
{
    LL v;
    int cnt;
    bool operator<(const info &t)const {
        return v > t.v;
    }
};
priority_queue<info>Q;

int main(void)
{
    int n, i, c;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%I64d", arr + i);
        ++cnt[*(arr + i)];
        vis[*(arr + i)] = 1;
    }
    for (i = 0; i < n; ++i)
    {
        LL &v = *(arr + i);
        c = cnt[v];
        if (c >= 2)
        {
            if (vis[v])
            {
                vis[v] = 0;
                Q.push({v, c});
            }
        }
        pos[v].pb(i);
    }
    while (!Q.empty())
    {
        info u = Q.top();
        Q.pop();
        if (cnt[u.v] < 2)
            continue;
        int p1 = pos[u.v][0], p2 = pos[u.v][1];
        pos[u.v].pop_front();
        pos[u.v].pop_front();
        c = (cnt[u.v] -= 2);
        if (c >= 2)//消掉之后可能下一轮还是这个数，这里要入队一次
        {
            Q.push({u.v, c});
        }
        arr[p2] += arr[p1];
        auto it = lower_bound(all(pos[arr[p2]]), p2);
        pos[arr[p2]].insert(it, p2);
        c = ++cnt[*(arr + p2)];
        if (c >= 2)
        {
            Q.push({arr[p2], c});
        }
        arr[p1] = -1;
    }
    vector<LL>ans;
    for (i = 0; i < n; ++i)
    {
        if (arr[i] != -1)
            ans.pb(arr[i]);
    }
    printf("%d\n", ans.size());
    for (auto &x : ans)
        printf("%I64d ", x);
    puts("");
    return 0;
}

F.Simple Cycles Edges

题意就是给你$n$个点，$m$条边的无自环，无重边的无向图，求所有简单环上的边。

看到图论题立马上去刚了，燃鹅退役前只写过边双连通，这题是点双连通（刚不动刚不动），然后去学了一下点双连通。

首先可以容易发现简单环总是边数等于点数的，但是不一定如此，比如：

NhSSq.md.png

这个图里显然有两个简单环，但是在同一个边双连通分量中，因此不能用边双连通去缩点，而要用点双连通，大体做法就是把每个点双连通分量求出来，看看分量中的边数是否等于点数即可。这样一来上图的两个分量刚好符合条件。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct edge
{
    int to, nxt, id;
    edge() {}
    edge(int _to, int _nxt, int _id): to(_to), nxt(_nxt), id(_id) {}
} E[N << 1];
int head[N], tot;
int dfn[N], low[N], st[N], top, ts, ins[N], pbc_cnt, road[N][2];
stack<int>est;
vector<int>pbc_edge[N];
set<int>p;

void init()
{
    CLR(head, -1);
    tot = 0;
}
inline void add(int s, int t, int id)
{
    E[tot] = edge(t, head[s], id);
    head[s] = tot++;
}
void tarjan(int u, int f)
{
    dfn[u] = low[u] = ++ts;
    ins[u] = 1;
    st[top++] = u;
    int v;
    for (int i = head[u]; ~i; i = E[i].nxt)
    {
        v = E[i].to;
        if (!dfn[v])
        {
            est.push(i);
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])//u为割点
            {
                ++pbc_cnt;
                int eid;
                do
                {
                    eid = est.top();
                    est.pop();
                    pbc_edge[pbc_cnt].pb(E[eid].id);
                }
                while (E[eid].id != E[i].id);
            }
        }
        else if (dfn[v] < dfn[u] && v != f)
        {
            est.push(i);
            low[u] = min(low[u], dfn[v]);
        }
    }
}
int main(void)
{
    int n, m, a, b, i;
    scanf("%d%d", &n, &m);
    init();
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &a, &b);
        add(a, b, i);
        add(b, a, i);
        road[i][0] = a, road[i][1] = b;
    }
    for (i = 1; i <= n; ++i)
        if (!dfn[i])
            tarjan(i, -1);
    vector<int>ans;
    for (i = 1; i <= pbc_cnt; ++i)
    {
        p.clear();
        for (auto &eid : pbc_edge[i])
        {
            p.insert(road[eid][0]);
            p.insert(road[eid][1]);
        }
        if (pbc_edge[i].size() == p.size())
            ans.insert(ans.end(), all(pbc_edge[i]));
    }
    sort(all(ans));
    int sz = ans.size();
    printf("%d\n", sz);
    for (i = 0; i < sz; ++i)
        printf("%d%c", ans[i], " \n"[i == sz - 1]);
    return 0;
}