EOJ Monthly 2019.2

发表于 | 分类于 | Views

3676. 解题

官方题解：

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
#include <bits/stdc++.h>
#include <ext/rope>
#include <algorithm>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int M = 5e7 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

char s[N];
int a[N];
int pos[M];

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    scanf("%s", s + 1);

    int q;
    int len = strlen(s + 1);

    scanf("%d", &q);

    for (;q--;) {
        int m;
        int i;
        int sys = 1;
        int ans = -1;

        scanf("%d", &m);

        pos[0] = len + 1;

        for (i = len; i >= 1; i--, sys = (sys * 10) % m) {
            a[i] = (a[i + 1] + (s[i] - '0') * sys) % m;
            if (pos[a[i]]) {
                ans = pos[a[i]] - i - 1;
                break;
            }
            pos[a[i]] = i;
        }

        if (~ans)
            printf("%d %d\n", i, i + ans);
        else
            printf("%d\n", ans);

        for (; i <= len; i++) {
            pos[a[i]] = 0;
            a[i] = 0;
        }
    }

    return 0;
}

3681. 中位数

官方题解：

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
#include <bits/stdc++.h>
#include <ext/rope>
#include <algorithm>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

vector<int> G[N];
int w[N];
int wt[N];
int dp[N];
int n, m;

int getAns(int u) {
    if (u == n)
        return wt[n];
    int &res = dp[u];
    if (res != INF)
        return res;
    res = -INF;
    for (int v : G[u])
        res = max(res, wt[u] + getAns(v));
    return res;
}
bool check(int val) {
    for (int i = 1; i <= n; i++) {
        if (w[i] >= val)
            wt[i] = 1;
        else if (w[i] < val)
            wt[i] = -1;
    }
    mst(dp, 0x3f);
    return getAns(1) >= 0;
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);

    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].emplace_back(v);
    }

    int L = 0, R = 1000000001;
    int ans = -1;

    for (;L <= R;) {
        int mid = L + R >> 1;
        if (check(mid)) {
            ans = mid;
            L = mid + 1;
        } else
            R = mid - 1;
    }

    printf("%d\n", ans);

    return 0;
}

这两道都是巧妙的思维题，马住。