比赛链接：传送门

Process

这场打得还可以，简单题做得比较快，但是后面两个小时连一道题都没做出来，有点可惜

Problems

C Matrix Walk

我们发现向左或向右走只会加减1，向上或向下只会加减m 于是第一遍for求出m，第二遍for判断是否出左右界，n直接输出10^9即可

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int N;
    int A[200000 + 100];
    
    int main()
    {
    #ifdef hk_cnyali
        freopen("C.in", "r", stdin);
        freopen("C.out", "w", stdout);
    #endif
        scanf("%d", &N);
        int sum = 0;
        for (int i = 1; i <= N; ++i)
        {
            scanf("%d", &A[i]);
            if (i == 1) continue;
            if (abs(A[i] - A[i - 1]) == 1) continue;
            if (A[i] == A[i - 1])
            {
                cout<<"NO"<<endl;
                return 0;
            }
            if (sum && abs(A[i] - A[i - 1]) != sum) 
            {
                cout<<"NO"<<endl;
                return 0;
            }
            sum = abs(A[i] - A[i - 1]);
        }
        for (int i = 2; i <= N; ++i)
        {
            if (A[i] == A[i - 1] + 1 && sum && !(A[i - 1] % sum))
            {
                cout<<"NO"<<endl;
                return 0;
            }
            if (A[i - 1] == A[i] + 1 && sum && !(A[i] % sum))
            {
                cout<<"NO"<<endl;
                return 0;
            }
        }
        if (!sum) sum = 1;
        cout<<"YES"<<endl;
        cout<<1000000000<<" "<<sum<<endl;
        return 0;
    }
``` 

### D Fight Against Traffic

分别以s和t为起点各跑一遍最短路，然后n^2枚举任意两个城市计算答案即可

#### Code
``cpp
    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int Maxn = 10000 + 10, Maxm = 20000 + 10, inf = 0x3f3f3f3f;
    
    int N, M, S, T;
    int A[1010][1010];
    
    int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];
    int Vis[Maxn];
    inline void add_edge(int x, int y)
    {
        To[++e] = y;
        Next[e] = Begin[x];
        Begin[x] = e;
        W[e] = 1;
    }
    struct node
    {
        int a, b;
        bool operator < (const node &x) const
        {
            return x.b < b;
        }
    };
    priority_queue <node> Q;
    inline void Dijkstra(int *Dis)
    {
        for (int i = 1; i <= N; ++i) Dis[i] = inf, Vis[i] = 0;
        Dis[S] = 0;
        while (!Q.empty()) Q.pop();
        Q.push((node){S, 0});
        while (!Q.empty())
        {
            node tmp = Q.top(); Q.pop();
            int x = tmp.a;
            if (Vis[x]) continue;
            Vis[x] = 1;
            for (int i = Begin[x]; i; i = Next[i])
            {
                int y = To[i];
                if (Dis[y] > Dis[x] + W[i])
                {
                    Dis[y] = Dis[x] + W[i];
                    Q.push((node){y, Dis[y]});
                }
            }
        }
    }
    int Dis1[Maxn], Dis2[Maxn];
    
    int main()
    {
    #ifdef hk_cnyali
        freopen("D.in", "r", stdin);
        freopen("D.out", "w", stdout);
    #endif
        scanf("%d%d%d%d", &N, &M, &S, &T);
        for (int i = 1; i <= M; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            A[x][y] = 1;
            A[y][x] = 1;
            add_edge (x, y);
            add_edge (y, x);
        }
        Dijkstra(Dis1);
        swap(S, T);
        Dijkstra(Dis2);
        swap(S, T);
        int sum = Dis1[T], ans = 0;
        for (int i = 1; i <= N; ++i)
        {
            for (int j = i + 1; j <= N; ++j)
            {
                if (A[i][j]) continue;
                //cout<<i<<" "<<j<<" "<<Dis1[i] + Dis2[j]<<" "<<sum<<endl;
                if (Dis1[i] + Dis2[j] + 1 >= sum && Dis1[j] + Dis2[i] + 1 >= sum)
                    ++ans;
            }
        }
        //cout<<Dis1[2] + Dis2[5] <<endl;
        cout<<ans<<endl;
        return 0;
    }