AtCoder Beginner Contest 197

The competition link is here

Question A and B is too easy, so i won‘t write the editorial.

• ??: 代表完全不会 \(\rightarrow\) 看情况准备
• ??：代表缺少思路，但看题解能快速反映 \(\rightarrow\) 重点突破，弱点
• ??：代表能写出来，但是耗时过久 $\rightarrow $ 看别人的题解，进行优化
• ??：代表能快速反应，并能AC！

C - ORXOR

Problem Statement

给定一个长为\(N\)的数组\(A\)。将其分为一个或多个不为空的集合，对于每个集合都进行OR运算，对于每个集合得到的值进行XOR运算，要求最后的值最小。

Constraints

• \(1≤N≤20\)
• \(0≤A_i<2^{30}\)
• All values in input are integers.

Solution

这题写的时候想贪心的从高往低处理bit，但是发现区间操作比较困难。

之后考虑暴力法，但是将dfs的复杂度想成了全排列的复杂度。但实际上就对于每个位置进行一次选与不选的操作，因此时间复杂度为\(\mathcal{O(2^{n})}\)。

直接状压即可。

Code

为了提升阅读体验，将代码都统一放到最后。 点此跳转

D - Opposite

Problem Statement

有一个正\(n\)边形，\(n\)为偶数，给我们\(n\)边形的两个顶点\((x_0,y_0), (x_{n/2}, y_{n/2})\)。求出\((x_1, y_1)\)。

Constraints

• \(4≤N≤100\)
• \(N\) is even.
• \(0≤x_0,y_0≤100\)
• \(0≤x_{\frac{N}{2}},y_{\frac{N}{2}}≤100\)
• \((x_0,y_0)≠(x_{\frac{N}{2}},y_{\frac{N}{2}})\)
• All values in input are integers.

Solution

? 这题当时直接怀疑人生，看不懂题目。后面才发现是自己一个公式不熟悉：

绕点公式

在圆心为\((x_c,y_c)\)的圆上，从\((x_{0}, y_{0})\)旋转\(\theta\)度，得到的坐标\((x_1, y_1)\)

• \(x_1 = (x_0 - x_c) * \cos(\theta) - (y_0 -y_c) * \sin(\theta) + x_c\)
• \(y_1 = (x_0 - x_c) * \sin(\theta) + (y_0 - y_c) * \cos(\theta) + y_c\)

\(Proof\): Link

Code

点此跳转

E - Traveler

Problem Statement

在一个数轴上给定\(N\)个球，每个球在位置\(X_i\)上，且有自己的编号\(C_i\)，你从\(0\)点出发，每秒走\(1\)步，并以编号单调不降的次序收集所有的球，要求收集所有球的时间最短。

Constraints

• \(1\le N \le 2\times10^5\)
• \(|X_i| \le 10^9\)
• \(X_i \neq X_j\)
• \(X_i \neq 0\)
• \(1\le C_i\le N\)
• All values in input are intergers.

Solution

由于你必须顺序的收集球，对于每种编号\(C_i\)，你只有两种情况，停在最左或者停在最右。那么你只需要预处理出每类编号的最小值和最大值然后递推过去即可~

思路如下：

• 初始lcost = 0,rcost = 0,lpos = 0,rpos = 0
• 枚举到当前编号的最左，当前编号的最右两种情况，更新:

Code

点此跳转

F - Construct a Palindrome

Problem Statement

给你图和边(\(N\)个节点\(M\)条边），每个边上有对应的字符。要求你找到从\(1\)到\(N\)的最短路径，满足其构成的字符串为回文串。

Constraints

• \(2\le N \le1000; 2\le M \le 1000\)
• the char is a lowercase English letter.

Solution

当时模拟时有想到双端BFS，因为是回文串，我们两边同时走相同的就行了。但是因为没有怎么训练过双端BFS就没写出来。

考虑两种情况：

• 回文串长度为偶数，则最终他们走到相同的位置，即\(i=i\)
• 回文串长度为奇数，则最终他们之间的位置相差\(1\)，即\(i+1=j\)（枚举边即可）

由于是需要最短的，我们定义d(i,j):=代表从左端为i,右端为j的走了几步。因此，我们直接BFS，保证每次从i走的边的字符和从j走的字符的边相同，最后根据以上两种情况特判即可。

需要注意的是对于一条边\(u\rightarrow v\)，d(u,v) 不一定等于 d(v, u)，他们的定义不同。

Code

点此跳转

后记

这场ABC，C，D，F都不太熟，E虽然会但写的不快，总结以下问题：

• C对于暴搜的 敏感度一般。(暴搜)
• D数学公式，计算几何不行。（数学，几何）
• E对于动态规划和规律不够敏感。 (思维，dp)
• F 对于双端BFS不熟悉。（图论）

Code

Code —— C

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vt vector
#define all(x) x.begin(), x.end()
#define lb(x) lower_bound
#define mst(x, bit) memset(x, bit, sizeof(x))
#define rep(i, l, r) for (ll(i)=(l);(i)<(r);++i)
#define dbg() std::cerr << "\n ------ no bug ------- \n";
using ll = long long;
using db = double;
using pii = pair<int, int>;

// my solution is not well, may have more easy solution!
// dfs 暴力枚举的时间复杂度实际上为2^n 
// 注意最大值的设置 
// 对于dfs时间复杂度的计算不敏感
void solve(){
    int n; std::cin >> n;
    vt<int> f(n);
    rep (i, 0, n) std::cin >> f[i];
    ll ans = (1ll << 31); // note ! 
    rep (mask, 0, (1 << n)){
        ll cur = 0, ors = 0;;
        rep (i, 0, n){
            ors |= f[i];
            if ((mask >> i) & 1){
                cur ^= ors;
                ors = 0;
            }
        }
        cur ^= ors;
        ans = min(ans, cur);
    }
    std::cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

Code —— D

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vt vector
#define all(x) x.begin(), x.end()
#define lb(x) lower_bound
#define mst(x, bit) memset(x, bit, sizeof(x))
#define rep(i, l, r) for (ll(i)=(l);(i)<(r);++i)
#define dbg() std::cerr << "\n ------ no bug ------- \n";
using ll = long long;
using db = double;
using pii = pair<int, int>;
const db PI = acos(-1.0);

void solve(){
    int n; std::cin >> n;
    db x0, y0, xh, yh;
    std::cin >> x0 >> y0;
    std::cin >> xh >> yh;
    
    db theta = 2 * PI / n;  
    db xc = (x0 + xh) / 2;
    db yc = (y0 + yh) / 2;


    db x1 = (x0 - xc) * cos(theta) - (y0 - yc) * sin(theta) + xc;
    db y1 = (x0 - xc) * sin(theta) + (y0 - yc) * cos(theta) + yc;
    
    std::cout << fixed << setprecision(11) << x1 << " " << y1 << "\n";
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}	

Code —— E

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vt vector
#define all(x) x.begin(), x.end()
#define lb(x) lower_bound
#define mst(x, bit) memset(x, bit, sizeof(x))
#define rep(i, l, r) for (ll(i)=(l);(i)<(r);++i)
#define dbg() std::cerr << "\n ------ no bug ------- \n";
using ll = long long;
using db = double;
using pii = pair<int, int>;
inline int ri() { int x; std::cin >> x; return x; }
inline ll rl() { ll x; std::cin >> x; return x; }


const int maxn = 2e5 + 50;
ll mn[maxn], mx[maxn];
void solve(){

    int n; std::cin >> n;
    set<int> s;
    mst(mn, -1), mst(mx, -1);
    rep (i, 0, n){
        ll x, c; std::cin >> x >> c; 
        s.insert(c);
        if (mn[c] == -1) mn[c] = mx[c] = x;
        else {
            mn[c] = min(mn[c], x);
            mx[c] = max(mx[c], x);
        }
    }

    ll lc = 0, rc = 0, lp = 0, rp = 0;
    for (auto x: s){
        ll tlc, trc, tlp, trp;

        // 到左边
        tlc = min(lc + abs(mx[x] - lp) + mx[x] - mn[x], rc + abs(mx[x] - rp) + mx[x] - mn[x]);
        tlp = mn[x];

        trc = min(lc + abs(mn[x] - lp) + mx[x] - mn[x], rc + abs(mn[x] - rp) + mx[x] - mn[x]);
        trp = mx[x];

        lc = tlc, rc = trc;
        lp = tlp, rp = trp;
        // cout << lc << " " << lp << " || " << rc << " " << rp << "\n";
    }

    std::cout << min(lc + abs(lp), rc + abs(rp)) << "\n";
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

Code —— F

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vt vector
#define all(x) x.begin(), x.end()
#define lb(x) lower_bound
#define mst(x, bit) memset(x, bit, sizeof(x))
#define rep(i, l, r) for (ll(i)=(l);(i)<(r);++i)
#define dbg() std::cerr << "\n ------ no bug ------- \n";
using ll = long long;
using db = double;
using pii = pair<int, int>;
inline int ri() { int x; std::cin >> x; return x; }
inline ll rl() { ll x; std::cin >> x; return x; }
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 1e3 + 50;
using pis = pair<int, char>;
vt<pis> E[maxn];
void solve(){
    int n = ri(), m = ri();
    vt<int> f1(m), f2(m);
    rep (i, 0, m){
        char ch;
        std::cin >> f1[i] >> f2[i] >> ch;
        E[f2[i]].pb(make_pair(f1[i], ch));
        E[f1[i]].pb(make_pair(f2[i], ch));
    }

    vt<vt<int>> d(n + 1, vt<int>(n + 1, inf));
    queue<pii> que; que.push(make_pair(1, n)); d[1][n] = 0;
    while (!que.empty()){
        int pos1 = que.front().first;
        int pos2 = que.front().second;
        que.pop();
        for (auto go1: E[pos1]){
            for (auto go2: E[pos2]){
                if (go1.second != go2.second) continue;
                if (d[go1.first][go2.first] == inf){
                    d[go1.first][go2.first] = d[pos1][pos2] + 1;
                    que.push(make_pair(go1.first, go2.first));
                }
            }
        }
    }

    int ans = 0x3f3f3f3f;
    rep (i, 1, n + 1) ans = min(ans, 2 * d[i][i]);
    // so you need to store the input of edge ! 
    rep (i, 0, m){
        ans = min(ans, 2 * d[f1[i]][f2[i]] + 1);    
        ans = min(ans, 2 * d[f2[i]][f1[i]] + 1);    
    }

    if (ans == 0x3f3f3f3f) std::cout << -1 << "\n";
    else std::cout << ans << "\n";
}   

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

AtCoder Beginner Contest 197

原文：https://www.cnblogs.com/Last--Whisper/p/14655043.html