前言

因为快要济南站了，所以最近都在复盘各种比赛。

和队友复盘了一把20上海，有点凉。

先是我刷榜这边，不知道为什么牛客的重现赛他要在排名那里才能看到别人AC了什么题。然后一直看榜看的比较自闭。最后赛后发现，我们队伍漏了一道签到题…

其次是读题，扫雷那题读错了，读成了要求修改次数最小的情况，后面发现只要构造一个修改次数$\leq \lfloor \frac{nm}{2} \rfloor$的情况就可以了（我就说怎么他们都AC了）。

最后，是实操写代码的情况。斐波那契签到题和$M$题简单模拟写起来都很容易，后面队长搞了那个二分题。不过中间因为更新答案那里出了$bug$所以卡住了。好在最后还是$AC$了。

后面我们队伍就在看那道扫雷，还有那道数位$DP$，不过都没能搞出来。也漏了另一题很好写的签到。

如果把那题好写的签到也写了，应该就有铁首了。再把扫雷搞过去，就稳$Cu$了。

距离济南站还有不到一周，希望有牌牌。

（打完济南站就要期末考了我绩点要凉了啊啊啊啊啊）

加油，加油，加加油ヾ(≧▽≦*)o

简单记录

Walker

这道题主要是分类讨论，能分成三个大类：

① 一个人走完全程

② 两个人都往对方方向走

③ 两个人的路径相接位置在两人中间某一位置（又分为两种小情况，是先往边界跑还是先往对方方向跑）

队友上机写的一把二分距离，是二分两人的路径相接的点在中间的哪一位置，再计算时间。

中途因为答案更新部分写炸了，$WA$了两次。

模拟赛Code：

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
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int t;
double n, p1, v1, p2, v2, ans;
bool check(double x)
{
    double t1 = (min(p1, x - p1) + x) / v1;
    double t2 = (min(p2-x, n-p2) + (n-x)) / v2;
    double time = max(t1, t2);
    ans = min(ans, time);
    if(t1 < t2)
    {
        return true;
    }
    else
        return false;
    
}
signed main(void)
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lf %lf %lf %lf %lf", &n, &p1, &v1, &p2, &v2);
        if(p1 > p2)
            swap(p1, p2), swap(v1, v2);
        ans = 1e9;
        double tt1 = 1e60, tt2 = 1e60, tt3 = 1e60, tt4 = 1e60;
        if(p1 > n - p1)
            tt1 = (n - p1 + n) / v1;
        else
            tt2 = (p1 + n) / v1;
        if(p2 > n - p2)
            tt3 = (n - p2 + n) / v2;
        else
            tt4 = (p2 + n) / v2;
        ans = min(min(tt1, tt2), min(tt3, tt4));
        double time2 = max((n - p1) / v1, p2 / v2);
        ans = min(ans, time2);
        double l = p1, r = p2;
        for(int i = 1; i <= 1000; i++)
        {
            double mid = (l + r) / 2;
            if(check(mid))
                l = mid;
            else
                r = mid;
        }
        printf("%.10lf\n", ans);
    }
}

Gitignore

一道简单的模拟题。

只要将文件路径转成图的关系，再dfs跑一下就可以了。

不过这题我敲得有点久，要能写的再快再准些就好了。

模拟赛时Code:

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
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int t, n, m, cnt;
int k, head[maxn];
struct Edge{
    int to;
    int nxt;
} E[maxn];
void Build(int u, int v){
    E[k].to = v;
    E[k].nxt = head[u];
    head[u] = k++;
}
map<string, int> mp;
map<int, int> isit;
void solve(string now, int isd){
    int len = now.size();
    string res = "", fa = "ROOT_INITS";
    for(int i = 0; i <= len - 1; i++)
    {
        res = res + now[i];
        if(now[i] == '/')
        {
            if(!mp.count(res))
            {
                mp[res] = ++cnt;
                isit[cnt] = isd;
                Build(mp[fa], mp[res]);
            }
            fa = res;
            continue;
        }
        if(i == len - 1)
        {
            if(!mp.count(res))
            {
                mp[res] = ++cnt;
                isit[cnt] = isd;
                Build(mp[fa], mp[res]);
            }
            continue;
        }
    }   
}
int ans, vis[maxn];
int dfs(int now){
    int flag = 1, nx = 0;
    for(int i = head[now]; ~i; i = E[i].nxt)
        flag &= dfs(E[i].to), nx = 1;
    return vis[now] = (nx == 0 ? (isit[now] == 1) : flag);
}
//int used[maxn];
void dfs2(int now){
    //printf("%d %d\n", now, vis[now]);
    //printf("de: %d\n", now);
    int b = 1, nx = 0;
    for(int i = head[now]; ~i; i = E[i].nxt)
    {
        nx = 1;
        if(vis[E[i].to] && now)    continue;
        b = 0;
    }
    if((nx && b) || (!nx && vis[now]))
    {
        //used[now] = 1;
        //printf("debug: %d\n", now);
        ans++;
    }
    else
    {
        /* code */
        for(int i = head[now]; ~i; i = E[i].nxt)
        {
            dfs2(E[i].to);
        }
    }
    
}
void inits(){
    memset(head, -1, sizeof(head));
    mp.clear();
    isit.clear();
    ans = 0;
    memset(vis, 0, sizeof(vis));
    k = 0;
    cnt = 0;
}
signed main(void)
{
    scanf("%d", &t);
    while(t--)
    {
        inits();
        mp["ROOT_INITS"] = 0;
        scanf("%d %d", &n, &m); getchar();
        for(int i = 1; i <= n; i++)
        {
            string now;
            getline(cin, now);
            solve(now, 1);
        }
        for(int i = 1; i <= m; i++)
        {
            string now;
            getline(cin, now);
            solve(now, 2);
        }
        /*
        for(int i = head[1]; ~i; i = E[i].nxt)
            printf("debug: %d\n", E[i].to);
        */
        dfs(0);
        dfs2(0);
        printf("%d\n", ans);
        
        /*
        printf("-----------------------\n");
        for(auto &iter : mp)
            cout << iter.first << " " << iter.second << endl;
        */
    }
}

Fibonacci

主要规律：奇，奇，偶，奇，奇，偶，…

然后，利用这个规律直接推符合条件的数目即可。

开题时队友推规律，我码一个打表程序（之前签到题被罚成弟弟了）。

队友很快给出式子$\frac{n(n-1)}{2}-\frac{x(x-1)}{2}$，$x$是$1 \to n$内奇数的个数。推完一拍，没什么问题，快速$1A$。

模拟赛Code：

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
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int fib[maxn];
signed main(void)
{
    /*
    fib[1] = fib[2] = 1;
    for(int i = 3; i <= 20; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    for(int n = 1; n <= 20; n++)
    {
        int ans = 0;
        for(int i = 1; i <= n; i++)
            for(int j = i + 1; j <= n; j++)
                if((fib[i] * fib[j]) % 2 == 0)
                    ans++;
        printf("%d %d\n", n, ans);
    }
    */
    int n;
    scanf("%lld", &n);
    int odd = (n / 3) * 2 + (n % 3);
    printf("%lld\n", n * (n - 1) / 2 - odd * (odd - 1) / 2);
}