ACL Contest 1

发表于 | 阅读数

ACL Contest 1

A

先按$x$排个序。则

  • ，如果$p_i>p_j,i>j$,则连边。

维护一个单调递减的单调栈，显然插入一个新元素，就会跟$<$自己的组成联通快，显然最后保留最小的那个元素，这样之后就有更多可能去合并其他元素。

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
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int fa[N], siz[N];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, siz[i] = 1;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    int xx = find(x);
    int yy = find(y);
    if (xx != yy)
    {
        fa[xx] = yy;
        siz[yy] += siz[xx];
    }
}

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
pii g[N];
int main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        int u = read(), v = read();
        g[u] = (mk(v, i));
    }
    init(n);
    stack<int> s;
    for (int i = 1; i <= n; i++)
    {
        int w = g[i].first;
        int tmp = i;
        while (!s.empty() && g[s.top()].first < w)
        {
            if (tmp == i)
                tmp = s.top();
            merge(s.top(), i);

            s.pop();
        }
        s.push(tmp);
    }
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; i++)
    {
        ans[g[i].second] = siz[find(i)];
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    printf("\n");
}

B

$n(n+1)\mod 2k=0$

将$2k\rightarrow ab=2k$因数分离。

设$n+1=ax,n=by,ax-by=1$,$exgcd$即可。

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
71
72
73
74
75

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll gd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gd;
}
int main()
{
    ll n;
    cin >> n;
    if (n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    if (n == 2)
    {
        cout << 3 << endl;
        return 0;
    }
    n <<= 1;
    ll z = sqrt(n);
    vector<ll> p;
    for (ll i = 2; i <= z; i++)
    {
        if (n % i == 0)
        {
            p.push_back(i);
            p.push_back(n / i);
        }
    }
    ll ans = n;
    for (ll o : p)
    {
        ll a = o;
        ll b = n / o;
        ll x, y;

        ll gd = exgcd(a, b, x, y);
        if (gd != 1)
            continue;

        x = (x + b) % b;

        ans = min(a * x - 1, ans);
    }
    cout << ans << endl;
}

C

设某个点$(x,y)$,终点为$(i,j)$,$ans=i+j-x-y$

最大化$\sum (i+j)$，限定可行点，流量为$1$,费用为$(i+j)$。以及连各种边，也可以预处理连边

跑最大费用流即可。

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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>

#define mk make_pair
#define INF 0x3f3f3f3f
const int N = 1e2 + 10;
const int mod = 1e9 + 7;

struct Edge
{
    int to, w, nxt, f;
    Edge() {}
    Edge(int v, int c, int t, int k) : to(v), w(c), nxt(t), f(k) {}
};
const int EN = 5e3 + 10;
const int EM = 5e4 + 10;
struct LeiDinic
{

    Edge e[EM << 1];
    int head[EN], scnt, dis[EN], vis[EN], cur[EN];
    int cost;
    LeiDinic() { scnt = 1, cost = 0; }
    void addEdge(int u, int v, int w, int k)
    {
        e[++scnt] = Edge(v, w, head[u], k);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v], -k); ///!!!!
        head[v] = scnt;
    }
    bool spfa(int s, int t)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, INF, sizeof(dis));
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;

        q.push(s);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;

                if (dis[to] > dis[x] + e[i].f && e[i].w)
                {
                    dis[to] = dis[x] + e[i].f;
                    if (!vis[to])
                    {
                        vis[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        return dis[t] != INF;
    }

    int dfs(int x, int t, int flow)
    {
        if (x == t)
            return flow;
        vis[x] = 1;
        int res = 0;
        for (int i = cur[x]; i && res < flow; i = e[i].nxt)
        {
            cur[x] = i;
            int to = e[i].to;
            if (!vis[to] && dis[to] == dis[x] + e[i].f && e[i].w)
            {
                int dis = dfs(to, t, min(flow - res, e[i].w));
                if (dis)
                {
                    e[i].w -= dis;
                    e[i ^ 1].w += dis;
                    cost += e[i].f * dis;
                    res += dis;
                }
            }
        }
        vis[x] = 0;
        return res;
    }
    pii Maxflow(int s, int t)
    {
        int ans = 0, tmp;
        while (spfa(s, t))
        {
            memcpy(cur, head, sizeof(head));
            while ((tmp = dfs(s, t, INF)))
                ans += tmp;
        }
        return mk(ans, cost);
    }
} mc;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
char mp[N][N];
int id[N][N];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", mp[i] + 1);
    }
    int cnt = 1;
    int s = ++cnt;
    int t = ++cnt;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            id[i][j] = ++cnt;
    int res = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == '#')
                continue;
            if (mp[i][j] == 'o')
            {

                res -= i + j;
                mc.addEdge(s, id[i][j], 1, 0);
            }
            mc.addEdge(id[i][j], t, 1, -(i + j));
            if (j + 1 <= m && mp[i][j + 1] != '#')
                mc.addEdge(id[i][j], id[i][j + 1], 1e9, 0);
            if (i + 1 <= n && mp[i + 1][j] != '#')
                mc.addEdge(id[i][j], id[i + 1][j], 1e9, 0);
        }
    // cout << 233 << endl;

    cout << res + -mc.Maxflow(s, t).second << endl;
}

D

先用双指针，处理出每个位置，可以跳到的位置$tmp$。

考虑$[l,r]$，如果找最长的长度，显然暴力跳不行，就倍增一下。

找到之后，可以发现$[last,r]$都可以放，那么这个时候倒过来跳的时候，$ans=\sum (r_i-l_i+1)$,画个图就可以$ok$。正反维护两个倍增的数组即可$\sum (r_i),\sum (l_i+1)$

D 
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;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

int a[N];
ll l[N][20], sl[N][20], r[N][20], sr[N][20];
int main()
{
    int n = read(), K = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    int tmp = 1;
    for (int i = 1; i <= n; i++)
    {
        while (tmp <= n && a[tmp] - a[i] < K)
        {
            tmp++;
        }

        r[i][0] = tmp;
        sr[i][0] = -tmp + 1;
    }
    r[n + 1][0] = n + 1;
    tmp = n;
    for (int i = n; i >= 1; i--)
    {
        while (tmp >= 1 && a[i] - a[tmp] < K)
        {
            tmp--;
        }

        l[i][0] = tmp;
        sl[i][0] = tmp;
    }

    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= n + 1; i++)
        {
            l[i][j] = l[l[i][j - 1]][j - 1];
            sl[i][j] = sl[l[i][j - 1]][j - 1] + sl[i][j - 1];

            r[i][j] = r[r[i][j - 1]][j - 1];
            sr[i][j] = sr[r[i][j - 1]][j - 1] + sr[i][j - 1];
        }

    int q = read();
    while (q--)
    {
        int ql = read(), qr = read();

        ll res = qr - ql + 1;
        int j = ql;
        for (int i = 18; i >= 0; i--)
        {
            if (r[j][i] <= qr)
            {
                res += sr[j][i];
                j = r[j][i];
            }
        }

        j = qr;
        for (int i = 18; i >= 0; i--)
        {
            if (l[j][i] >= ql)
            {
                res += sl[j][i];
                j = l[j][i];
            }
        }
        printf("%lld\n", res);
    }
}