AtCoder Beginner Contest 284

https://atcoder.jp/contests/abc284
被D卡了，感觉十分的弱智。
GEx看不懂题解（

A - Sequence of Strings

#include <bits/stdc++.h>

using namespace std;

int main () {
    vector <string> v;
    int n;  cin >> n;
    while (n --) {
        string s;
        cin >> s;
        v.push_back (s);
    }
    reverse (v.begin (), v.end ());
    for (auto i : v)    cout << i << endl;
}

B - Multi Test Cases

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n, x, ans = 0;
    cin >> n;
    while (n --) {
        cin >> x;
        if (x & 1)  ans ++;
    }
    cout << ans << endl;
}

int main () {
    int t;  cin >> t;
    while (t --)    solve ();
}

C - Count Connected Components

dfs统计连通块个数

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 5;
int n, m, cnt;
bool vis[N];
int h[N], e[N], ne[N], idx;

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

void dfs (int x) {
    if (vis[x])     return ;
    vis[x] = true;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        dfs (j);
    }
}

void solve () {
    memset (h, -1, sizeof h);
    cin >> n >> m;
    while (m --) {
        int a, b;
        cin >> a >> b;
        add (a, b), add (b, a);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt ++;
            dfs (i);
        }
    }

    cout << cnt << endl;
}

int main () {
    solve ();
}

//连通块个数

D - Happy New Year 2023

直接枚举，不要预处理

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    for (int i = 2; i * i * i <= n; i++) {
        if (n % (i * i) == 0) {
            cout << i << ' ' << n / (i * i) << endl;
            break;
        }
        if (n % i == 0 && sqrt (n / i) == (int)sqrt (n / i)) {
            cout << (int)sqrt(n / i) << ' ' << i << endl;
            break;
        }
    }
}

signed main() {
    int t;
    cin >> t;
    while (t--)    solve();
    //cout << (int)sqrt(N);
}

//不要预处理！！！

E - Count Simple Paths

求从1出发的简单路径数目。
直接搜

#include <bits/stdc++.h>

using namespace std;
const int N = 4e5 + 5, inf = 1e6;
int h[N], e[N], ne[N], idx;
int n, m, ans;
bool vis[N];

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

void dfs (int x) {
    if (vis[x] || ans > inf)    return ;
    vis[x] = true;
    ans ++;
    for (int i= h[x]; ~i; i = ne[i])    dfs (e[i]);
    vis[x] = false; //回溯
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n >> m;
    while (m --) {
        int a, b;
        cin >> a >> b;
        add (a, b), add (b, a);
    }
    dfs (1);
    cout << min (ans, inf);
}

//因为有长度限制所以可以直接搜

F - ABCBAC

字符串哈希 什么是字符串Hash

每次 \(check\): \([0,i) + [i+n,2*n)\) 和 \([i,i+n)\) 这两段字符串是否对称
即转化为枚举 \(i\), 多次查询区间字符串是否为回文串的问题
可用字符串哈希(为减少冲突,这里采用双哈希):
前面的串是处在端点的两个前缀拼起来, 后面的串是一段在中间的连续后缀
答案: \([0, i)\) 和 \([i+n, 2*n)\)

举个栗子：

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

using namespace std;
const int N = 2e6 + 5; //两倍n
const int mod1 = 1e9 + 7, mod2 = 1e9 + 9;

struct pii {
    int p1, p2;
    pii () {}
    pii (int p1_, int p2_) : p1(p1_), p2(p2_) {}
    pii operator + (pii t) {
        t.p1 = (this->p1 + t.p1) % mod1;
        t.p2 = (this->p2 + t.p2) % mod2;
        return t;
    }

    pii operator - (pii t) {
        t.p1 = (this->p1 - t.p1 + mod1) % mod1;
        t.p2 = (this->p2 - t.p2 + mod2) % mod2;
        return t;
    }
    
    pii operator * (pii t) {
        t.p1 = (this->p1 * t.p1) % mod1;
        t.p2 = (this->p2 * t.p2) % mod2;
        return t;
    }

    bool operator == (pii t) {
        if (t.p1 == this->p1 && t.p2 == this->p2)   return true;
        return false;
    }
}p[N], pre[N], suf[N]; //pow值, 前缀哈希和, 后缀哈希和(左闭右开)

signed main() {
    int n;
    string t;
    cin >> n >> t;
    pii P = {131, 13331}; //进制
    p[0] = {1, 1};
    for (int i = 1; i <= 2 * n; i++) {
        p[i] = p[i-1] * P;
        pii tt = {t[i-1] - 'a', t[i-1] - 'a'};
        pre[i] = pre[i-1] * P + tt;
    }
    for (int i = n * 2; i; i--) {
        pii tt = {t[i-1] - 'a', t[i-1] - 'a'};
        suf[i] = suf[i+1] * P + tt;
    }

    for (int i = 0; i <= n; i++) { //左闭右开区间
        pii sum1 = (pre[i] * p[n - i]) + (pre[2*n] - pre[i+n] * p[n-i]);
        pii sum2 = suf[i+1] - suf[i+n+1] * p[n];
        if (sum1 == sum2) {
            cout << t.substr (0, i) + t.substr (i + n, 2 * n - i) << endl;
            cout << i << endl;
            return 0;
        }
    }
    cout << "-1\n";
}

//每次check: [0,i) + [i+n,2*n) 和 [i,i+n) 这两段是否对称
//及转化为枚举i, 多次查询区间字符串是否为回文串的问题
//可用字符串哈希(为减少冲突,这里采用双哈希):
//前面的串是处在端点的两个前缀拼起来, 后面的串是一段在中间的连续后缀
//答案: [0, i) 和 [i+n, 2*n)

G - Only Once

没懂

Ex - Count Unlabeled Graphs

没懂