AtCoder Beginner Contest 280 A-F

https://atcoder.jp/contests/abc280
个人认为D >> E,F
被D搞心态了，导致EF都没看（）

A - Pawn on a Grid

统计#的个数

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, m, cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char ch;
            cin >> ch;
            if (ch == '#')  cnt ++;
        }
    }
    cout << cnt;
}

B - Inverse Prefix Sum

根据前缀和还原原数组

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 15;
int a[N], n;

signed main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], cout << a[i] - a[i-1] << ' ';
}

C - Extra Character

s中插入一个字符变成t，求插入位置
注意特判末尾

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main () {
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.size (); i++) {
        if (s[i] != t[i]) {
            cout << i + 1;
            return 0;
        }
    }
    cout << s.size () + 1;
}

D - Factorial and Multiple

先对k进行唯一分解，预处理出p和cnt数组，用来记录素因数及其个数
对于k, 大于\(\sqrt k\) 的因子只有一个，所以1e12的范围只需考虑到1e6即可。
因此如果k的最大素因子大于1e6,就直接取这个因子。
否则可以二分，范围从1到k，check当前mid是否能涵盖所有的因子。
（特别注意下tmp那里，我有点脑抽）

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e6 + 5;
int n, p[N], cnt[N], tt;

void test (int tt, int *p, int *cnt) {
    for (int i = 1; i <= tt; i++)   cout << p[i] << ' ' << cnt[i] << endl;
    cout << endl;
}

void pre () {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            p[++tt] = i;
            while (n % i == 0) {
                n /= i;
                cnt[tt] ++;
            }
        }
    }
    if (n > 1) {
        p[++tt] = n;
        cnt[tt] ++;
    }
}

bool check (int x) {
    //cout << x << ": ";
    for (int i = 1; i <= tt; i++) {
        int tot = 0, pr = p[i], tmp = x;
        while (tmp) {
            tot += (tmp / pr);
            tmp /= pr;
            //cout << tmp << ' ';
        }
        //cout << "tot: " << tot << ' ';
        if (tot < cnt[i])   return false;
    }
    return true;
}

signed main () {
    cin >> n;
    int m = n;
    pre ();
    //test (tt, p, cnt);

    if (p[tt] > 1e6) {
        cout << n;
        return 0;
    }

    int l = 1, r = m;
    while (l < r) {
        int mid = l + r >> 1;
        if (check (mid))    r = mid;
        else    l = mid + 1;
        //cout << "end: " << l << ' ' << r << endl;
    }
    cout << r << endl;
}

//预处理素数表
//二分n
//chceck x!是否能覆盖所有分解

E - Critical Hit

题意：现在是0，有 \(\frac{p}{100}\) 的概率打出2的攻击，\(1-\frac{p}{100}\) 的概率打出1的攻击。求打出n的攻击的期望值，模998244353
分析：就是裸的期望dp，式子：\(f_i = (f_{i-2} * \frac{p}{100} + f_{i-1} * (1-\frac{p}{100})) + 1\)，记得取模，分数求逆元。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int n, p, f[N];

int qmi(int a,int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1)//末位1取出
			ans = ans * a % p;
		k >>= 1;//次末位
		a = a * a % p;
	}
	return ans;
}

signed main () {
    cin >> n >> p;
    f[1] = 1;
    int p1 = p * qmi (100, mod - 2, mod) % mod, p2 = (1 - p1 + mod) % mod;
    //cout << p1 << ' ' << p2 << endl;
    for (int i = 2; i <= n; i++) {
        f[i] = (f[i-1] * p2 % mod + f[i-2] * p1 % mod + 1) % mod;
    }
    cout << f[n];
}

F - Pay or Receive

题意：给定一个n个点的有向图，输入m条边，边 \({a,b,c}\) 对应一条 \(a\) 到 \(b\) 的权为 \(c\) 的边以及一条 \(b\) 到 \(a\) 的权为 \(-c\) 的边。然后q次询问，问从a点走到b点的最大距离。若不可达输出nan，若距离无穷输出inf，其余情况输出最大值。
分析：把图建起来之后，先判可达性。用并查集判两点是否在一个集合中。对于inf的情况，模拟样例可知，若两点之间可以经过正环，则可以通过在上面一直绕圈圈的方式达到无穷。所以对于每点出发，跑bfs，若发现到达同一点距离却不同的情况就是出现了正环。若无正环且可达，输出 \(dis_b-dis_a\)。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5, M = N * 2, inf = -1e18;
int n, m, q;
int h[N], e[M], ne[M], w[M], idx;
int fa[N], cnt[N], dis[N];
bool vis[N], isINF[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int find (int x) {
    if (x != fa[x]) fa[x] = find (fa[x]);
    return fa[x];
}

void Merge (int a, int b) {
    a = find (a), b = find (b);
    if (a != b)     fa[a] = b;
}

void bfs (int st) {
    queue <int> q;
    q.push (st);
    vis[st] = true;
    dis[st] = 0;

    while (!q.empty ()) {
        auto t = q.front ();
        q.pop ();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis[j] == inf) {
                dis[j] = dis[t] + w[i];
                vis[j] = true;
                q.push (j);
            }
            else if (dis[j] != dis[t] + w[i]) {
                isINF[find (st)] = true;
                return ;
            }
        }
    }
}

signed main () {
    memset (h, -1, sizeof h);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)    fa[i] = i, dis[i] = inf;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, -c);
        if (find (a) != find (b))   Merge (a, b);
    }
    for (int i = 1; i <= n; i++) {
        int j = find (i);
        if (vis[j])     continue;
        vis[j] = true;
        bfs (j);
    }
    while (q --) {
        int a, b;
        cin >> a >> b;
        if (find (a) != find (b)) {
            cout << "nan\n";
            continue;
        }
        if (isINF[find (a)])    cout << "inf\n";
        else    cout << dis[b] - dis[a] << endl;
    }
}

//找正环

G - Do Use Hexagon Grid 2

似乎是一个很复杂的分类讨论，会看看的（）

Ex - Substring Sort

蹲蹲大佬的题姐。