Lut本科回忆录

更新至A,H,D,J…

题A

题意：给定二进制数 $x$ 和 $y$，每次操作选择 $x$ 中的一位 $b$, 使得 $x+=b$ 或 $x-=b$，问多少次操作使得 $x=y$。

解：当 $x=0$ 时怎么操作都不行，反之取 $1$ 操作 $|x-y|$ 次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int main(){
    string n, m; cin >> n >> m;
    ll a = 0, b = 0;
    for(int i = 0; i < n.size(); ++ i)
        a = a * 2 + (n[i] == '1');
    for(int i = 0; i < m.size(); ++ i)
        b = b * 2 + (m[i] == '1');
    if(a == 0 && b != 0){cout << -1 << '\n'; return 0;}
    cout << abs(a - b) << '\n';
}

题H

题意：对一个长度为 $n$ 的数组 $a$， 可以进行无数次操作，每次操作选择 $1<=i,j<=n$，使得 $a_i+=1,a_j-=1$。
问能否使得数组 $a$ 都为质数。

解：这里直接引用哥德巴赫猜想：$任一大于2的偶数都可写成两个质数之和（推至任一大于7的奇数可以写成三个质数之和）$。知道该定理后，我们可以先将 $n - 1$ 个数都变成 $2$，然后判断第 $n$ 个数是不是质数，反之是偶数的话就可以取一个 $2$ 合并后再分解， 是奇数的话看 $n$ 是否大于等于3，再之看 $a_n>=3?$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N];
bool ok(ll k){
    for(int i = 2; i * i <= k; ++ i)
        if(k % i == 0) return 0;
    return 1;
}
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    if(n == 1){
        if(ok(a[1]) && a[1] > 1) cout << "Yes";
        else cout << "No";
        return 0;
    }
    for(int i = 1; i < n; ++ i){
        if(a[i] == 1) a[n] --;
        else if(a[i] > 2) a[n] += a[i] - 2;
    }
    
    if(a[n] < 2) cout << "No";
    else if((2 + a[n]) % 2 == 0) cout << "Yes\n"; 
    else {
        if((n >= 3 && a[n] >= 3) || ok(a[n])) cout << "Yes";
        else cout << "No";
    }
}

题D

题意：给定一个大小为 $n*n$ 的 $01$ 矩阵，每次操作可以翻转某一具体行或列，最终使得 $min(r_i)>=max(c_j)$，表示每行每列组成的二进制数中，行中最小的二进制数比列中最大的二进制数大。求最少操作次数，不能实现则输出 $-1$。

解：当且仅当矩阵权威 $0/1$ 的时候满足题目条件。我们可以对全为 $0$ 或 $1$ 的矩阵反推，那么必然存在某一步骤时每行每列要么相等要么就是取一次反，这里我们枚举行。当且仅当 $s[1] == s[i](或s[i]的反， 1 <i<=n)$ 时答案存在。

#include<iostream>
using namespace std;
string s[2010];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> s[i];
    int a = 0, b = 0;
    for(int i = 2; i <= n; ++ i){
        if(s[i] == s[1]) continue;
        for(int j = 0; j < n; ++ j) s[i][j] = (s[i][j] == '1') ? '0': '1';
        if(s[1] == s[i]) a ++;
        else {cout << -1; return 0;}
    }
    for(int i = 0; i < n; ++ i) if(s[1][i] == '1') b ++;
    cout << min(min(b, n - b) + a, min(b, n - b) + n - a);
}

题J

题意：给定 $n$ 个点和 $m$ 对偏序关系 $<u,v>$，构造最少的排列数目 $k$ 使得其中对每个偏序而言至少有一个排列满足的 $u<v$ $(1<=n,m<=1e6)$

解：当 $k=2$ 时的两个排列为 $1, 2, 3...n-1, n$ 和 $n, n - 1... 3, 2, 1$ 时，对任意一堆偏序必然存在于这二者之一。可见 $k=2$ 是 $k$ 的上限。当 $k=1$ 时仅存在一个排列满足所有的偏序，显然我们可以把所有偏序跑一遍拓扑，如果拓扑存在则 $k=1$。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
vector<int> g[N];
int d[N], q[N];
int main(){
    int n, m, t = 0; cin >> n >> m;
    for(int i = 1; i <= m; ++ i){
        int u, v; cin >> u >> v;
        g[u].push_back(v); d[v] ++;
    }
    for(int i = 1; i <= n; ++ i) if(d[i] == 0) q[++ t] = i;
    for(int i = 1; i <= t; ++ i){
        for(auto &x: g[q[i]]){
            if(-- d[x] == 0) q[++ t] = x;
        }
    }
    if(t == n){
        cout << 1 << '\n';
        for(int i = 1; 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 << ' ';
    }
}