SummaryEducational Codeforces Round 40 Summary

Educational Codeforces Round 40 Summary

比赛链接:传送门

Process

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

Problems

C Matrix Walk

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

Code

#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

#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;
}

Categories: Summary Tags: ,

Comments

No Comments Yet. Be the first?

Post a comment