2019暑期牛客多校

ACM
,

WIP

第三场

B: Crazy Binary String

签到题
初步想法是$v_i$记录在$i$处出现过的0与1个数之差，当$v_j == v_i (j \gt i)$时计算$j-i$，记录其最大值
然而这就是个前缀和。。

1
2
3
4
5
6
7
8
for(int i=0;i<n;i++) {
    if(a[i])state++;
    else state--;
    if(first[state])
        maxx = max(maxx, i-first[state]);
    else first[state] = i;
}
cout<<maxx;

J: LRU management

大暴力，模拟
赛后补题

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 <iostream>
#include <list>
#include <unordered_map>
using namespace std;
list<pair<string, int>> cache;
unordered_map<string, list<pair<string, int>>::iterator> last;
int T, Q, M;
void access(const string &str, int v) {
    auto ite = last.find(str);
    if (ite != last.end()) {
        auto cur = ite->second;
        printf("%d\n", cur->second);
        cache.push_back(*cur);
        cache.erase(cur);
        last[cur->first] = prev(cache.end());
    } else {
        printf("%d\n", v);
        cache.emplace_back(str, v);
        last[str] = prev(cache.end());
        if (int(cache.size()) > M) {
            last.erase(cache.front().first);
            cache.erase(cache.begin());
        }
    }
    last[str] = prev(cache.end());
}

void query(const string &str, int v) {
    auto ite = last.find(str);
    if ((ite == last.end()) ||
        (v == 1 && next(ite->second) == cache.end()) ||
        (v == -1 && ite->second == cache.begin()))
        printf("Invalid\n");
    else{
        auto result = ite->second;
        if (v == -1)
            result--;
        if (v == 1)
            result++;
        printf("%d\n", result->second);
    }
}
char buffer[2048];
int opt, v;
int main() {
    scanf("%d", &T);
    while (T--) {
        cache.clear();
        last.clear();
        scanf("%d %d", &Q, &M);
        while (Q--) {
            scanf("%d %s %d", &opt, buffer, &v);
            if (opt)
                query(buffer, v);
            else
                access(buffer, v);
        }
    }
}

Magic Line

做几何的时候一定要注意代码的细节

过分别按照x与y取中位数得到的点画一条线，将坐标延伸至无限远，进行微小的调整，即可错开这个点。
此处有一细节问题：当调整极远处坐标时应考虑到线的旋转，从而会影响到一开始排序的方向。

第五场

generator1

题意

计算$2*2$矩阵的$n$次幂($n \leq 10^{10^6}$)

思路

首先$n$这么大，快速幂是肯定的。但是有个问题就是
这个整数转换为"整数"的复杂度不可忽略。
将n视为字符串$n_1,n_2,n_3,…,n_{|n|}$，其中$n_i$代表n的第i数位，对矩阵T有

\begin{align}
& T^{int(n)} \\
==& T^{n_1*10^{|n|}+n_2*10^{|n|-1}+…} \\
==& T^{n_1*10^{|n|}}*T^{n_2*10^{|n|-1}}*…*T^{n_{|n|} *10^0}
\end{align}

备注

考场上应当就问题考虑解决问题的办法，找到问题的特征，不应该抱着现成的板子不放。过不去肯定有别的问题。
但是我现在只想去世

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 <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef vector<vector<long long> /**/> mat;
mat unit = mat{vector<long long>{1, 0}, vector<long long>{0, 1}};
mat zero = mat{vector<long long>{0, 0}, vector<long long>{0, 0}};
int a, b, x1, x2, mod;
char n[1000000];
const mat operator*(const mat &a, const mat &b) {
    mat ret = zero;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                ret[i][j] += a[i][k] * b[k][j];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            ret[i][j] %= mod;
    return ret;
}
template <typename T>
const T operator^(T a, int n) {
    T ret = unit;
    while (n) {
        if (n & 1)
            ret = ret * a;
        n >>= 1;
        a = a * a;
    }
    return ret;
}
int main() {
    scanf("%d %d %d %d", &x1, &x2, &a, &b);
    scanf("%s %d", n, &mod);
    int length = strlen(n);
    mat res = unit;
    mat base = mat{vector<long long>{a, b}, vector<long long>{1, 0}};
    for (int i = length - 1; i >= 0; i--) {
        if (n[i] - '0')
            res = res * (base ^ (n[i] - '0'));
        base = base ^ 10;
    }
    res = res * mat{vector<long long>{x2, 0}, vector<long long>{x1, 0}};
    printf("%lld\n", res[1][0]);
}

three points 1

有思路有思路。。。。
十分钟能写完么
不能

第六场

B: Shorten IPv6 Address

比赛的时候我在干什么系列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T = int(input())
case = 0
while T > case:
    case += 1
    x = input()
    x = [
        int(x[i:i+16], 2)
        for i in range(
            0, len(x), 16
        )]
    s = [':'.join([hex(i)[2:] for i in x])]
    for i in range(8):
        for j in range(i+1, 8):
            flag = True
            for k in x[i:j+1]:
                if k != 0:
                    flag = False
            if flag:
                s.append(':'.join([hex(_)[2:] for _ in x[:i]])+'::'+
                         ':'.join([hex(_)[2:] for _ in x[j+1:]]))
    s.sort(key=lambda x: (len(x), x))
    print('Case #%d:' % (case), s[0])

但是python里头有个all，可以判断一个可遍历对象里头是否都为true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T = int(input())
case = 0
while T>case:
    case+=1
    x = input()
    x = [hex(int(x[i:i+16], 2))[2:] 
        for i in range(0, len(x), 16)
    ]
    s = [':'.join(x)]
    for i in range(8):
        for j in range(i+1,8):
            if all(map(lambda x:x=='0',x[i:j+1])):
                s.append(':'.join(x[:i])+'::'+':'.join(x[j+1:]) )
    s.sort(key=lambda x:(len(x),x))
    print('Case #%d:'%(case),s[0])

D: Move

数据毒瘤。。。有多少人的二分都过了。。
证明"$f(V)=需要的盒子数$"不单调：
首先取体积为V的流体（即$\lim\limits_{n \to \infty}v_1,v_2…v_n$）放满K个盒子，取$v_i, v_j$合并为一个物体，此时$\sum v_i$没变，而多了一个需要的盒子
貌似遍历check一遍就能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool check(int V) {
    memset(put, 0, sizeof(bool) * n);
    int cnt_obj = n, cnt = 0;
    while (sumV) {
        int cur = V;
        for (int i = 1; i <= n; i++)
            if (!put[i] && v[i] <= cur) {
                put[i] = true;
                cnt_obj--;
                cur -= v[i];
            }
        cnt++;
    }
    return cnt <= k;
}