World Fragments I

题目大意

给定两个二进制数x,y，问是否可以进行任意次操作使x变成y，每次操作可以选择二进制数y中的一位使y加上或减去这个数。

解题思路

若x和y相等，不需要操作，答案为0.

若不相等，显然只有取的这个数为1才有意义，若y为0则取不到1，那么无论怎么操作都不能使x变成y，否则答案即为x，y的差的绝对值。

复杂度分析

时间复杂度：O（1）

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;

void solve(){
    bitset<63> sx,sy;
    cin>>sx>>sy;
    int x=sx.to_ullong(),y=sy.to_ullong();
    if(x==y){
        cout<<0<<endl;
    }else if(x==0){
        cout<<-1<<endl;
    }else{
        cout<<abs(x-y)<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Ama no Jaku

题目大意

给定一个大小的矩阵，每个位置的数只可能是0或1，你可以进行任意次操作：翻转一行或一列。记每一行或每一列组成一个二进制数，求进行多少次操作后可以使得行组成的最小二进制数大于等于列组成的最大二进制数。若不可能，输出-1.

解题思路

模拟样例可知，只有全0和全1的情况才符合题意。因此题目就转化为是否能转化为全0或全1的状态，如果能需要多少次操作。

按照第一列的第一个数和第一行的第一个数决定是否翻转这一列或这一行，使得第一行和第一列的数全部相等，接着判断矩阵是否都为0或都为1。

这里我们可以只考虑转化为0的情况，记录将第一行转化为0需要对列进行操作的次数cnt1，对第一列同理得到cnt2，最后答案取即可。

因为如果列操作将第一行变成0的操作最少，我们就选择变成0，即取变成0或1两种情况中操作少的。此时考虑完行的情况虽然可能与前面列操作使得第一行要变成的数可能与行操作情况不同，但由于这时第一行一定相同，行操作要变成的数与列操作要变成的数不同时不会发生冲突。

复杂度分析

时间复杂度:

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;
const int N=2010;
int n;
char s[N][N];

void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    int cnt1=0,cnt2=0;
    for(int i=0;i<n;i++){
        if(s[i][0]=='1'){
            cnt1++;
            for(int j=0;j<n;j++){
                s[i][j]='1'+'0'-s[i][j];
            }
        }
    }
    for(int i=0;i<n;i++){
        if(s[0][i]=='1'){
            cnt2++;
            for(int j=0;j<n;j++){
                s[j][i]='1'+'0'-s[j][i];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(s[i][j]!='0'){
                cout<<-1<<endl;
                return;
            }
        }
    }
    cout<<min(cnt1,n-cnt1)+min(cnt2,n-cnt2)<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Koraidon, Miraidon and DFS Shortest Path

题目大意

给定一个n个点的有向图，边权为1，问从点1开始以任意边权顺序进行dfs是否每个点都能得到正确的最短路。

解题思路

先用bfs求出每个点到1的距离dist[i]

再用dfs模拟题中所给的代码看是否会与原来所出来的结果矛盾。

注意这里dfs中遍历过的点标记vis后回溯时应该取消vis的标记，这样可以以任意边的顺序模拟。

时间复杂度看起来有点玄学与构图有关，但是还是过了

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;
int n,m;
vector<vector<int>> edge;
const int N=5e5+10;
int dist[N];
bool vis[N];
bool ans;

void bfs(int start){
    memset(dist,0x3f,(n+1)*sizeof(int));
    dist[start]=0;
    queue<int> q;
    q.push(start);
    while(q.size()){
        int u=q.front();q.pop();
        for(auto v:edge[u]){
            if(dist[v]>dist[u]+1){
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}

void dfs(int u){
    vis[u]=true;
    for(auto v:edge[u]){
        if(!vis[v]){
            if(dist[v]<dist[u]+1){
                ans=0;
                return;
            }
            dfs(v);
        }
    }
    vis[u]=false;
}

void solve(){
    ans=true;
    cin>>n>>m;
    edge.clear();
    edge.resize(n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
    }
    bfs(1);
    memset(vis,0,(n+1)*sizeof(bool));
    dfs(1);

    cout<<(ans?"Yes":"No")<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Until the Blue Moon Rises

题目大意

给定一个长度为n的数列，你可以做任意次数的操作：选择数列中两个数，使得，如果能使数列A中的每一个数变成，输出Yes，否则输出No

解题思路

令sum为数列的和。

当n=1时，直接判断这个数是不是质数。

当n=2时，若sum为偶数且sum大于等于4，根据哥德巴赫猜想(任意一个大于2的偶数一定可以由两个质数相加），该猜想尚未找到反例，故假设正确；当sum为奇数，由于奇数=奇数＋偶数，而是质数的偶数只有2，所以判断sum-2是否为质数即可。

当n=3时，同样根据哥德巴赫猜想成立。

复杂度分析

时间复杂度：O(sqrt(x))

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;
int sum,n;
const int N=1010;
int a[N];

bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum<n*2){
        cout<<"No"<<endl;
        return;
    }
    if(n==1){
        cout<<(is_prime(a[1])?"Yes":"No")<<endl;
    }else if(n==2){
        if(sum%2==0||sum%2==1&&is_prime(sum-2)){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }else if(n>=3){
        if(sum>=2*n){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Fine Logic

题目大意

给定n个人，m对输赢关系，让你输出最少数量的1~n全排列，使得每组输赢关系都能在输出的全排列中反应出来，即u在v的左边。

解题思路

拓扑排序+正反输出

若无环，则一遍拓扑排序即为结果。

若有环，则这m对关系不能通过1次全排列体现，至少需要2次，那么一次1,2,…,n和n,n-1,…,1的全排列则包含了所有可能的输赢情况。

复杂度分析

时间复杂度：O(n+m)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;
const int N=1e6+10;
int n,m;
vector<vector<int>> edge;
int ind[N];

void solve(){
    cin>>n>>m;
    edge.resize(n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        ind[v]++;
    }

    vector<int> res;
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            q.push(i);
        }
    }

    while(q.size()){
        int u=q.front();
        q.pop();
        res.push_back(u);
        for(auto v:edge[u]){
            ind[v]--;
            if(ind[v]==0){
                q.push(v);
            }
        }
    }

    if((int)res.size()==n){
        cout<<1<<endl;
        for(int i=0;i<res.size();i++){
            cout<<res[i]<<" \n"[i==(int)res.size()-1];
        }
    }else{
        cout<<2<<endl;
        for(int i=1;i<=n;i++){
            cout<<i<<" \n"[i==n];
        }
        for(int i=n;i>=1;i--){
            cout<<i<<" \n"[i==1];
        }
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}