专栏首页ACM算法日常Codeforces Round #549(div1)简析

Codeforces Round #549(div1)简析

限于篇幅,本文不再概述题意,仅简略讲述做法,供补题的同学作为参考。欢迎交流讨论~

A 1800 数论

正解貌似有分四种情况什么的,我做时是发现各个起点其实都等价的,所以随便选一个起点,再暴举终点以暴举答案,更新即可。

const int maxn = 1e5 + 5;
ll n, k, a, b, aa, minn = INF, maxx = -1;
set<ll> bb;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin >> n >> k >> a >> b;
    ll T = n * k;
    rep(i, 0, n - 1) {
        ll p = (ll)i * k + 1;
        bb.insert((p + b) % T);
        bb.insert((p - b + T) % T);
    }
    aa = (1 + a) % T;
    for(set<ll>::iterator it = bb.begin(); it != bb.end(); it++) {
        ll t = *it;
        ll ans = T / gcd(T, (t - aa + T) % T);
        minn = min(minn, ans);
        maxx = max(maxx, ans);
    }
    cout << minn << " " << maxx << endl;
    return 0;
}

B 2300 倍增

1.先预处理出在循环中某数前面的数是谁。

2.读入a数列时贪心选取最晚的父亲。

3.链上倍增预处理二进制祖先。

4.对于每个位置,预处理第n-1个祖先位置最早要从哪里开始,技巧上再顺手与前一位的最早位置取max,尽量缩小区间。

5.查询已经可做。

const int maxn = 2e5 + 5;
int n, m, q, permu[maxn], pre[maxn], a[maxn], f[maxn][25], late[maxn], L[maxn];

int Find(int pos, int n) {
    irep(i, 20, 0)
        if (n >= 1 << i) {
            n -= 1 << i;
            pos = f[pos][i];
        }
    return pos;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);

    rep(i, 0, n - 1)
        scanf("%d", &permu[i]);
    rep(i, 0, n - 1)
        pre[permu[i]] = permu[(i - 1 + n) % n];

    rep(i, 1, m) {
        scanf("%d", &a[i]);
        f[i][0] = late[pre[a[i]]];
        late[a[i]] = i;
    }
    rep(i, 1, 20)
        rep(j, 1, m)
            f[j][i] = f[f[j][i - 1]][i - 1];
    rep(i, 1, m)
        L[i] = max(Find(i, n - 1), L[i - 1]);

    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d", L[r] >= l);
    }

    return 0;
}

C 2800 凸包

难在技巧上。可以变换坐标:x' = x, y' = y - x ^ 2,如此之后可得线性函数x' * b + c = y',可以发现两点连边为抛物线,而其他点都在这条线下方才满足题意,故而求一个上凸壳即可。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
int n;
struct Point {
    ll x, y;

    Point(){}
    Point(ll x, ll y):x(x), y(y) {}

    friend ll operator * (const Point &a, const Point &b) {
        return a.y * b.x - b.y * a.x;
    }

    friend Point operator - (const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }

    bool operator < (const Point &rhs) const {
        if (x != rhs.x)    return x < rhs.x;
        return y < rhs.y;
    }
};

vector<Point> v, st;

void read() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        y = y - x * x;
        v.push_back({x, y});
    }
}

void convex() {
    sort(v.begin(), v.end());//按坐标排序

    for (int i = n - 1; ~i; --i)
        v[i] = v[i] - v[0];

    for (int i = 0; i < n; i++) {
        int tot = st.size();
        while (tot > 1 && (v[i] - st[tot - 2]) * (st[tot - 1] - st[tot - 2]) >= 0)    tot--, st.pop_back();
        st.push_back(v[i]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    read();
    convex();

    int ans = 0;
    for (int i = 1; i < st.size(); i++)
        if (st[i].x != st[i - 1].x)//x相同无法构成二次函数
            ans++;
    cout << ans << endl;

    return 0;
}

D 2700 dp

限于篇幅,解析部分有兴趣的同学还是看博客吧。

https://www.cnblogs.com/AlphaWA/p/10665100.html

#include <cstdio>
#include <cstring>

const int maxn = 1e5 + 5;
char S[maxn];
__int64_t ans, dp[maxn][15];//以第i个位置、以rankj的数拓展出去的方案数

int main() {
    scanf("%s", S + 1);
    int len = strlen(S + 1);

    for (int i = len; i; --i) {
        int d = S[i] - '0';

        for (int j = 0; j <= 10; ++j) {
            dp[i][j] = 1;//自己独立成一个方案
            if (i < len) {
                int t = S[i + 1] - '0';
                if (j > t) {//与后面联合,当前rank只会转移到更小的数字
                    dp[i][j] += dp[i + 1][(j * (j - 1) / 2 + t + 10) % 11];//事实上只有两位数的转移也可以直接打表
                }
            }
        }

        if (d)  ans += dp[i][d];//题目限制从1~9为起点
    }

    printf("%lld\n", ans);
    return 0;
}

E 3100 图论、交互

官解SCC缩点之后删点,AlphaWA没学过图论没太懂后半部分(哪位大佬给我讲一下也好),于是学习了神仙安德鲁何(%%%)不需要SCC的做法。其实看代码就能懂是在怎么操作了,看解析的链接: https://www.cnblogs.com/AlphaWA/p/10667859.html

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

const int maxn = 1e5 + 5;
int n, m, used[maxn], indeg[maxn];
vector<int> adj[maxn];
queue<int> Q;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }

    function<void(int)> dfs = [&](int cur) {
        if (used[cur])  return;
        used[cur] = 1;
        vector<int> tmp;
        for (int son : adj[cur]) {
            if (used[son] == 1) continue;
            dfs(son);
            tmp.push_back(son);
            indeg[son]++;
        }
        used[cur] = 2;
        adj[cur] = tmp;
    };

    for (int i = 1; i <= n; i++)    dfs(i);

    for (int i = 1; i <= n; i++) {
        if (!indeg[i]) {
            Q.push(i);
        }
    }

    while (Q.size() >= 2) {
        int a = Q.front(); Q.pop();
        int b = Q.front(); Q.pop();

        cout << "? " << a << ' ' << b << '\n' << flush;
        int answer; cin >> answer;

        if (!answer)    swap(a, b);
        for (int i : adj[b]) {//delete b
            if (!--indeg[i]) {
                Q.push(i);
            }
        }
        Q.push(a);
    }

    cout << "! " << Q.front() << endl;
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 力扣 526.优美的排序(next_permutation?)

    链接:https://leetcode-cn.com/problems/beautiful-arrangement

    ACM算法日常
  • leetcode 周赛155 | 项目管理之拓扑排序算法

    今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理...

    ACM算法日常
  • 程序员必须掌握的8大排序算法

    分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

    海天一树
  • 桶排序

    3. 桶排序        桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值(当然也可以装入若干个值),...

    attack
  • Codeforces Round #621 (Div. 1 + Div. 2)(无比自闭的一夜)

    菜到自闭自闭~~ 欲哭无泪~ 深夜一人伤悲~ 掉了~ rank– 明天要多刷水题,体验AC快感… 真几把自闭

    用户7727433
  • 计蒜客2018 蓝桥杯省赛 B 组模拟赛(一)

    Zoctopus
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack

扫码关注云+社区

领取腾讯云代金券