ABC277大失败

2022-11-132023-03-02做题记录13 分钟读完 (大约1949个字)0次访问

ABC277大失败😭😭😭

ABC277

A.- ^{-1}

Difficulty : $\color{cray} 11$

输出第 $x$ 个数的位置。

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;

int a[N];

int main()
{
    cin >> n >> m;
    for(int i = 1, x; i <= n; i++)
        cin >> x, a[x] = i;
    cout << a[m];
    return 0;
}

B.Playing Cards Validation

Difficulty : $\color{cray} 60$

条件判断。

#include <bits/stdc++.h>

using namespace std;

const int N = 60;

int n;

string S[N];

int main()
{
    cin >> n;
    int m = 0;
    for(int i = 1; i <= n; i++)
    {
        string s;
        cin >> s; S[i] = s;
        if(s[0] != 'H' && s[0] != 'D' && s[0] != 'C' && s[0] != 'S')
            continue;
        if(s[1] != 'A' && s[1] != '2' && s[1] != '3' && s[1] != '4' && s[1] != '5' && s[1] != '6' && s[1] != '7' && s[1] != '8' && s[1] != '9' && s[1] != 'T' && s[1] != 'J' && s[1] != 'Q' && s[1] != 'K')
            continue;
        m++;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)continue;
            if(S[i] == S[j])m--;
        }
    }
    if(m != n)
    {
        cout << "No";
    }
    else
    {
        cout << "Yes";
    }
    return 0;
}

C. Ladder Takahashi

Difficulty : $\color{brown} 540$

一个DAG上的DP。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n;

int a[N], b[N];

int h[N], tot;

struct node
{
    int x, y;
    node(int x = 0, int y = 0) : x(x), y(y) {}
    friend bool operator < (node a, node b)
    {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
};

node d[N];

int dx[N], dy[N];

int f[N];

int dfs(int x)
{
    if(f[x])return f[x];
    f[x] = max(f[x], x);
    int pos = lower_bound(dx + 1, dx + n + 1, x) - dx;
    for(int i = pos; i <= n; i++)
    {
        if(d[i].x > x)break;
        f[d[i].x] = max(f[d[i].x], dfs(d[i].y));
    }
    return f[x];
}

int main()
{
    cin >> n;
    h[++tot] = 1;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        h[++tot] = a[i];
        h[++tot] = b[i];
    }
    sort(h + 1, h + tot + 1);
    tot = unique(h + 1, h + tot + 1) - h - 1;
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(h + 1, h + tot + 1, a[i]) - h;
        b[i] = lower_bound(h + 1, h + tot + 1, b[i]) - h;
        d[2 * i - 1] = node(a[i], b[i]);
        d[2 * i] = node(b[i], a[i]);
        dx[2 * i - 1] = a[i]; dy[2 * i - 1] = b[i];
        dx[2 * i] = b[i]; dy[2 * i] = a[i];
    }
    n = 2 * n;
    sort(d + 1, d + n + 1);
    sort(dx + 1, dx + n + 1);
    sort(dy + 1, dy + n + 1);
    f[1] = 1;
    for(int i = 1; i <= n; i++)
        f[d[i].x] = max(f[d[i].x], dfs(d[i].y));
    cout << h[f[1]] << endl;
    return 0;
}

D.Takahashi’s Solitaire

Difficulty : $\color{green} 873$

可以先排序，然后找以每个数开头的环所做的贡献，就好了。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 2e5 + 10;

#define fir first
#define sec second
typedef pair<ll, ll> Pair;

int n, m, k;

int a[N];

map <int, int> t;

vector <Pair> vec;

ll f[N];

bool vis[N];

int nxt(int x)
{
    x++; if(x > k)x = 0; return x;
}

int pre(int x)
{
    x--; if(x < 0)x = k; return x;
}

ll find(int x)
{
    if(vec[x].fir != (vec[pre(x)].fir + 1) % m)
        return 0;
    if(f[x])return f[x];
    if(vis[x])return 0;
    vis[x] = true;
    return f[x] = find(nxt(x)) + vec[x].fir * vec[x].sec;
}

int main()
{
    scanf("%d%d", &n, &m);
    ll sum = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        t[a[i]]++; sum += a[i];
    }
    for(auto x : t)vec.push_back(x);
    k = vec.size() - 1;
    if(k + 1 == m) return printf("0"), 0;
    ll ans = sum;
    for(int i = 0; i <= k; i++)
    {
        vis[i] = true;
        f[i] = find(nxt(i)) + vec[i].fir * vec[i].sec;
        ans = min(ans, sum - f[i]);
    }
    printf("%lld", ans);
    return 0;
}

E.Crystal Switches

Difficulty : $\color{green} 1183$

可以跑分层图最短路。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;
const int INF = 0x3f3f3f3f;

int cnt, head[N];

struct edge
{
    int to, nxt, cost;
    edge(int v = 0, int x = 0, int c = 0) :
        to(v), nxt(x), cost(c) {}
};

edge e[N << 1];

void add(int u, int v, int c)
{
    e[++cnt] = edge(v, head[u], c); head[u] = cnt;
    e[++cnt] = edge(u, head[v], c); head[v] = cnt;
}

int n, m, k;

int dis[N], vis[N];

struct node
{
    int x, c;
    node(int x = 0, int c = 0) :
     x(x), c(c) {}
};

void bfs()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; deque <int> q;
    q.push_back(1);
    while(!q.empty())
    {
        int x = q.front();
        q.pop_front();
        for(int i = head[x]; i; i = e[i].nxt)
        {
            int v = e[i].to, c = e[i].cost;
            if(dis[x] + c < dis[v])
            {
                dis[v] = dis[x] + c;
                if(c == 0)q.push_front(v);
                else q.push_back(v);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(z)add(x, y, 1);
        else add(x + n, y + n, 1);
    }
    for(int i = 1; i <= k; i++)
    {
        int x; scanf("%d", &x);
        add(x, x + n, 0);
    }
    bfs();
    if(dis[n] == INF && dis[2 * n] == INF)
        printf("-1");
    else printf("%d", min(dis[n], dis[2 * n]));
    return 0;
}

F.Sorting a Matrix

Difficulty : $\color{orange} 2400$

可以将题目中的要求转化为：

每一行的值域范围不相交， $Max_i \le Min_{i + 1}$
每一行的数字是单调不降的

可以发现这两个条件一个是由行的顺序确定的，一个是由列的顺序决定的可以看成两个相互独立的问题。

对于第一个问题，直接处理每一行的最小值和最大值，排序判断即可。

对于第二个问题，将每一列看成点，可以建边跑拓扑排序判断。

#include <bits/stdc++.h>
using namespace std;

#define fir first
#define sec second
#define mpr make_pair
typedef pair<int, int> Pair;

const int N = 2e6 + 10;
const int INF = 1e9;

int n, m;

int a[N];

vector<int> g[N];

bool used[N];

vector<int> topo;

int pos(int x, int y)
{
    return (x - 1) * m + y - 1;
}

void dfs(int v)
{
    used[v] = true;
    for (auto u : g[v])
        if (!used[u])
            dfs(u);
    topo.push_back(v);
}

bool checkR()
{
    vector<Pair> vec;
    for (int i = 1; i <= n; i++)
    {
        int Min = INF, Max = -INF;
        for (int j = 1; j <= m; j++)
        {
            int x = pos(i, j);
            if (a[x] == 0)
                continue;
            Min = min(Min, a[x]);
            Max = max(Max, a[x]);
        }
        if (Min <= Max)
            vec.push_back(mpr(Min, Max));
    }
    sort(vec.begin(), vec.end());
    for (int i = 1; i < vec.size(); i++)
        if (vec[i - 1].sec > vec[i].fir)
            return false;
    return true;
}

bool checkC()
{
    for (int y = 1; y <= n; y++)
    {
        vector<pair<int, int>> vec;
        for (int x = 1; x <= m; x++)
            if (a[(y - 1) * m + (x - 1)])
                vec.push_back({a[(y - 1) * m + (x - 1)], x});
        sort(vec.begin(), vec.end());

        for (int i = 1; i < (int)vec.size(); i++)
        {
            if (vec[i - 1].first != vec[i].first)
            {
                int v = m + vec[i - 1].first;
                for (int j = i - 1; j >= 0; j--)
                {
                    if (vec[j].first != vec[i - 1].first)
                        break;
                    g[vec[j].second].push_back(v);
                }
                for (int j = i; j < (int)vec.size(); j++)
                {
                    if (vec[j].first != vec[i].first)
                        break;
                    g[v].push_back(vec[j].second);
                }
            }
        }
    }

    n = m + n * m;
    for (int i = 1; i <= n; i++)
        if (!used[i])
            dfs(i);
    reverse(topo.begin(), topo.end());

    for (int i = 1; i <= n; i++)
        used[i] = false;
    for (auto v : topo)
    {
        used[v] = true;
        for (auto u : g[v])
        {
            if (used[u])
            {
                return false;
            }
        }
    }
    return true;
}

int main(void)
{
    cin >> n >> m;
    for (int y = 1; y <= n; y++)
        for (int x = 1; x <= m; x++)
            cin >> a[(y - 1) * m + (x - 1)];
    if (!checkR())
        return printf("No\n"), 0;
    if (!checkC())
        return printf("No\n"), 0;
    printf("Yes\n");
    return 0;
}

G.Random Walk to Millionaire

Difficulty : $\color{orange} 2491$

Editorial

Ex.Constrained Sums

Difficulty: $\color{red} 2917$

好像和CF1697F一样？条件大同小异。

由于值域的范围很小，有一种2-SAT的做法就是用每一个变量表示命题“ $a_i$ 是否 $\ge j$ ”，这样点数就是 $n \times (k + 1)$ ，然后说一下CF的题的做法，就是比Ex多了一个单调递增的限制。

列出以下命题，并且其逆否命题都要建边，

$a_i \le a_{i+ 1} \Longleftrightarrow \forall a_i \ge v, \Rightarrow a_{i + 1} \ge v$
$a_i \not = x \Longleftrightarrow \forall a_i \ge x \Rightarrow a_x \ge x+ 1$
$a_i + a_j \le x \Longleftrightarrow \forall a_i \ge v \Rightarrow \lnot(a_j \ge x - v + 1)$
$a_i + a_j \ge x \Longleftrightarrow \forall \lnot (a_i \ge v) \Rightarrow a_j \ge x - v + 1$

然后2-SAT解决即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e7 + 10;
const int M = 6e7 + 10;

int n, m, q;

int cnt, head[N];

struct edge
{
    int to, nxt;
    edge(int v = 0, int x = 0) :
        to(v), nxt(x) {}
};

edge e[M << 1];

void add(int u, int v)
{
    e[++cnt] = edge(v, head[u]); head[u] = cnt;
}

int dfn[N], low[N], tim;

int st[N], top;

bool vis[N];

int color, c[N];

void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;
    vis[x] = true;
    st[++top] = x;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vis[v])
        {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(dfn[x] == low[x])
    {
        color++;
        while(st[top + 1] != x)
        {
            vis[st[top]] = false;
            c[st[top]] = color;
            top--;
        }
    }
}

int t;

int P(int x, int y, int f)
{
    return x + y * n + f * t;
}

void build()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            add(P(i, j, 0), P(i, j + 1, 0));
            add(P(i, j + 1, 1), P(i, j, 1));
        }
        add(P(i, m, 1), P(i, m, 0));
    }
}

bool inrange(int x)
{
    return x >= 0 && x <= m;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    t = (m + 1) * n;
    build();
    while(q--)
    {
        int i, j, l, r;
        scanf("%d%d%d%d", &i, &j, &l, &r);
        for(int x = r; x < m; x++)
        {
            add(P(i, x, 1), P(i, x, 0)),
            add(P(j, x, 1), P(j, x, 0));
        }
        for(int x = 0; x < r; x++)
        {
            if(inrange(x) && inrange(r - x - 1))
            {
                add(P(i, x, 1), P(j, r - x - 1, 0));
                add(P(j, x, 1), P(i, r - x - 1, 0));
            }
        }
        for(int x = 0; x < l; x++)
        {
            if(inrange(x) && inrange(l - x - 1))
            {
                add(P(i, x, 0), P(j, l - x - 1, 1));
                add(P(j, x, 0), P(i, l - x - 1, 1));
            }
        }
    }
    for(int i = 1; i <= 2 * t; i++)
        if(!dfn[i])tarjan(i);
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(c[P(i, j, 0)] == c[P(i, j, 1)])
                return printf("-1"), 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(c[P(i, j, 0)] < c[P(i, j, 1)])
                {printf("%d ", j); break;}
    return 0;
}

ABC277大失败

https://jekyll-y.github.io/2022/11/13/ABC277大失败/

作者

Jekyll_Y

发布于

2022-11-13

更新于

2023-03-02

许可协议

#AtCoder Beginner Contest Record

ABC277大失败

ABC277

A.- ^{-1}

B.Playing Cards Validation

C. Ladder Takahashi

D.Takahashi’s Solitaire

E.Crystal Switches

F.Sorting a Matrix

G.Random Walk to Millionaire

Ex.Constrained Sums

作者

发布于

更新于

许可协议

评论

目录