A.World Fragments I

题意:

给定两个非负二进制数a和b，每次从a中选择某个数位x(0/1)，并令a = a + x或a = a - x,问将a变成b的最小操作数，无解输出-1。

分析：

①a = b时输出0
②a ≠ b时，若a = 0，b ≠ 0则无解，否则输出|a - b|

代码：

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

typedef long long LL;

LL get(string &s) {
    LL res = 0;
    
    reverse(s.begin(), s.end());
    for (int i = 0; i < s.size(); i ++) {
        if (s[i] == '1')
            res += (LL)1 << i;
    }
    
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    string s1, s2;
    cin >> s1 >> s2;
    
    LL a = get(s1), b = get(s2);
    
    if (a == 0 && b != 0)
        cout << -1;
    else
        cout << abs(a - b);
    
    return 0;
}

D.Ama no Jaku

题意:

给你一个01矩阵，你可以进行若干次操作，每次操作翻转某一行或者某一列，问能否使该矩阵行代表的二进制数\(r_i\)和列代表的二进制数\(c_i\)满足min(\(r_i\)) \(\geqslant\) max(\(c_i\))，如果可以输出最小操作数，否则输出-1。

分析:

①全为0或者1显然满足
②若非全0，min(\(r_i\)) \(\geqslant\) max(\(c_i\)) > 0
\(\Rightarrow\) 每行至少有一个1
\(\Rightarrow\) min(\(c_i\)) \(\geqslant\) \(2^n\),
\(\Rightarrow\) 要满足大小关系，则至少每行第一个元素都是1
\(\Rightarrow\) max(\(c_i\)) = \(2^{n + 1} - 1\)
\(\Rightarrow\) 要满足大小关系则矩阵必须全为1
综上，要满足要求最后矩阵必须全为0或者1
通过模拟可以发现，能通过翻转使其全为0或者1的矩阵应满足：每行要么和第一行相同要么和第一行取反相同，不妨这两类行数设为a和b。
因此若有解，答案就是min(第一行0的个数，第一行1的个数) + min(a, b)

代码:

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

const int N = 2010;
string s[N];

bool check(int n) {
    string s1 = s[0], s2;
    for (int i = 0; i < n; i ++) {
        s2 += !(s[0][i] - '0') + '0';
    }
    
    for (int i = 1; i < n; i ++) {
        bool flag1 = s[i] == s1, flag2 = s[i] == s2;
        
        if (!flag1 && !flag2)
            return false;
    }
    
    return true;
}

int cal(int n) {
    int cnt0 = 0, cnt1 = 0;
    
    for (int i = 0; i < n; i ++) {
        if (s[0][i] == '0')
            cnt0 ++;
        else
            cnt1 ++;
    }
    
    return min(cnt0, cnt1);
}

int cal1(int n) {
    int cnt = 0, cnt1 = 0;
    
    for (int i = 0; i < n; i ++) {
        if (s[i] == s[0])
            cnt ++;
        else
            cnt1 ++;
    }
    
    return min(cnt, cnt1);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++) {
        cin >> s[i];
    }
    
    if (n == 1)
        cout << 0;
    else {
        if (check(n)) {            
            cout << cal(n) + cal1(n);
        }
        else
            cout << -1;
    }
    
    return 0;
}

E.Koraidon, Miraidon and DFS Shortest Path

题意:

给定一张图，使用dfs求解从1到其他点的最短路，问给定的图能否在任意边的遍历顺序下都能正确求解最短路。

分析:

正解用到支配树(还没学会...)。附上赛时水过的代码。

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

const int N = 5e5 + 5;
int h[N], e[N], ne[N], idx;
int d[N];
bool success, st[N], st2[N];;

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

void bfs(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        d[i] = 0x3f3f3f3f;
    }
    d[1] = 0;
    q.push(1);
    
    while (q.size()) {
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            
            if (d[j] > d[t] + 1) {
                d[j] = d[t] + 1;
                
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

void dfs(int u) {
    st2[u] = true;
    
    if (!success)
        return;
    
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        
        if (st2[j])
            continue;
        
        if (d[j] != d[u] + 1) {
            success = false;
            return;
        } 
        
        dfs(j);
        st2[j] = false;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t --) {
        int n, m;
        cin >> n >> m;
        
        idx = 0;
        for (int i = 1; i <= n; i ++) {
            h[i] = -1;
            st[i] = st2[i] = false;
        }
        
        while (m --) {
            int a, b;
            cin >> a >> b;
            
            add(a, b);
        }
        
        bfs(n);
        success = true;
        dfs(1);
        
        if (success)
            cout << "Yes" << "\n";
        else
            cout << "No" << "\n";
        
    }
    
    return 0;
}

H.Until the Blue Moon Rises

题意:

给你n个数，你可以进行若干次操作，每次让一个数+1或者-1，问能否构造出n个质数

分析:

本题考“哥德巴赫猜想”。
哥德巴赫猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。
由此可以得到两种情况：
1.强哥德巴赫猜想（强哥猜）：任一大于2的偶数都可写成两个质数之和；（未被证明，但是同时也没有被推翻，即在本题的范围内强哥猜成立）
2.弱哥德巴赫猜想（弱哥猜）:任一个大于5的奇数都能被表示成三个奇质数的和。（一个质数可以被多次使用）;（已经被证明）
因此这题可以进行如下讨论：
设n个元素的和为s
①n = 1，直接判断s是否为质数
②n = 2，若s为偶数则用强哥猜（特判s是否大于等于4），否则判断s - 2是否为质数（奇数 + 偶数 = 奇数，偶质数只有2）。
③n > 2，则用哥猜。当n = 3时，由于任一大于5的整数都可写成三个质数之和，则s至少为6即最小的方案为“2，2，2”，以此类推，可知当s \(\geqslant\) 2n 时有解。

代码:

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

typedef long long LL;

bool check(LL a) {
    if (a < 2)
        return false;
    
    for (int i = 2; i * i <= a; i ++) {
        if (a % i == 0)
            return false;
    } 
    
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    LL s = 0;
    
    for (int i = 0; i < n; i ++) {
        int a;
        cin >> a;
        
        s += a;
    }
    
    if (n == 1) {
        if (check(s))
            cout << "Yes";
        else
            cout << "No";
    } else if (n == 2) {
        if (s % 2 == 0) {
            if (s >= 4)
                cout << "Yes";
            else
                cout << "No";
        } else if (check(s - 2)) {
            cout << "Yes";
        } else {
            cout << "No";
        }
    } else {
        if (s >= 2 * n) {
            cout << "Yes";
        } else {
            cout << "No";
        }
    }
    
    return 0;
}

J.Fine Logic

题意:

给定n个点和m个偏序关系，要求构造序列数最少的k个序列，使得m个偏序关系都能在这个k个序列中找到。

分析:

按偏序关系建图：
若不存在环则输出拓扑排序即可，此时k = 1
若存在环，输出1到n的正序序列和n到1的倒序序列即可，因为<u, v>可以在正序序列中找到，<v, u>可以在逆序序列中找到，因此包含了所有情况，此时k = 2

代码:

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

const int N = 1e6 + 5, M = 2e6 + 5;
int h[N], e[M], ne[M], idx;
int n, m, q[N], d[N];

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

bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++) {
        if (!d[i]) {
            q[++ tt] = i;
        }
    }
    
    while (hh <= tt) {
        int t = q[hh ++];
        
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            
            if (-- d[j] == 0) {
                q[++ tt] = j;
            }
        }
    }
    
    return tt == n - 1;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while (m --) {
        int a, b;
        cin >> a >> b;
        
        add(a, b);
        d[b] ++;
    }
    
    if (topsort()) {
        cout << 1 << "\n";
        for (int i = 0; i < n; i ++)
            cout << q[i] << " ";
    } else {
        cout << 2 << "\n";
        
        for (int i = 1; i <= n; i ++)
            cout << i << " ";
        
        cout << "\n";
        
        for (int i = n; i >= 1; i --)
            cout << i << " ";
    }
    
    return 0;
}