Butteruni Blog
0%

2023牛客暑期多校3（A D E H J）

发表于 更新于 分类于

题目链接

由易到难为：AH，JD，E

A. World Fragments 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string a,b;
ll string_to_long(string s)
{
    ll res = 0;
    for(int i = 0;i < s.size();++i)
    {
        res *= 2;
        if(s[i] == '1')
            res += 1;
    }
    return res;
}
int main()
{
    cin >> a >> b;
    if(a == b)
    {
        cout << 0 << '\n';
    }else 
    {
        if(a == "0")
        {
            cout << -1 << '\n';
        }else     
        {
            ll pa = string_to_long(a);
            ll pb = string_to_long(b);
            cout << abs(pa - pb) << '\n';
        }
    }
}

H. Until the Blue Moon Rises

哥德巴赫猜想，特判 和 的两种情况， 时 即可。

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
ll ans;
bool check(ll x)
{
    if(x==1) return false;
    for(ll i=2;i<=sqrt(x)+1;i++)
    {
        if(x%i==0)return false;
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        ans+=t;
    }
    if(n==1)
    {
        if(check(ans))
        {
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
    else if(n==2)
    {
        if(ans<2*n)
        {
            cout<<"No\n";
        }
        else
        {
            if(ans%2==0)
            {
                cout<<"Yes\n";
            }
            else
            {
                if(check(ans-2))
                {
                    cout << "Yes\n";
                }
                else
                {
                    cout << "No\n";
                }
            }
        }
    }
    else
    {
        if(ans<2*n)
        {
            cout<<"No\n";
        }
        else

        {
            cout<<"Yes\n";
        }
    }
    return 0;
}

J. Fine Logic

只有 和 两种情况，前者图中无环，按拓扑序输出即可，后者随意输出一个序列然后将其逆序输出第二个即可

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
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
const int M=2e6+10;
map<PII,bool> Pvis;
struct Edge
{
    int u,v,next;
}e1[M],e2[M];
int head1[N],head2[N],cnt1,cnt2;
int d1[N],d2[N];
int n,m;
void add1(int u,int v)
{
    ++cnt1;
    e1[cnt1].u=u;
    e1[cnt1].v=v;
    e1[cnt1].next=head1[u];
    head1[u]=cnt1;
    return;
}
void add2(int u,int v)
{
    ++cnt2;
    e2[cnt2].u=u;
    e2[cnt2].v=v;
    e2[cnt2].next=head2[u];
    head2[u]=cnt2;
    return;
}
int q[N];
int q2[N];
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(Pvis[{u,v}])continue;
        Pvis[{u,v}]=true;
        add1(u,v);
        add2(v,u);
        d1[v]++;
        d2[u]++;
    }

    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(!d1[i])q[++tt]=i;
    }
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=head1[u];~i;i=e1[i].next)
        {
            int v=e1[i].v;
            if(--d1[v]==0)q[++tt]=v;
        }
    }
    if(tt==n-1)
    {
        cout<<1<<"\n";
        for(int i=0;i<=tt;i++)
        {
            cout<<q[i]<<" \n"[i==tt];
        }
    }
    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;
}

D. Ama no Jaku

对于条件 当且仅当矩阵全为 或矩阵全为 时实现，于是只需要判断矩阵能否反转成上述矩阵即可。由于 值为 或 因此对于所有行 和所有列 最多反转一次，于是先遍历第一行和第一列判断反转情况，之后查看这种反转能否整个矩阵满足条件即可

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int n;
string ma[2020];
int d_col[2020],d_row[2020];
bool crush(int x,int y,char t)
{
    if(!(d_col[y] <= 1 && d_row[x] <= 1))
    {
        return 1;
    }
    if((d_col[y] + d_row[x]) % 2 == 0 && ma[x][y] == t)
    {
        return 0;
    }else if((d_col[y] + d_row[x] % 2 == 1 && ma[x][y] != t))
    {
        return 0;
    }
    return 1;
}
int into(char x)
{
    int cnt = 0;
    int ans = INF;
    memset(d_col,0,sizeof(d_col));
    memset(d_row,0,sizeof(d_row));
    for(int i = 1;i <= n;++i)
    {
        if(crush(1, i, x))
        {
            cnt++;
            d_col[i]++;
        }
        if(crush(i, 1, x))
        {
            cnt++;
            d_row[i]++;
        }
    }
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j)
        {
            if(crush(i, j, x) )
            {
                cnt = INF;
            }
        }
    }
    ans = min(ans,cnt);
    memset(d_col,0,sizeof(d_col));
    memset(d_row,0,sizeof(d_row));
    cnt = 0;
    for(int i = 1;i <= n;++i)
    {
        if(crush(i, 1, x))
        {
            cnt++;
            d_row[i]++;
        }
        if(crush(1, i, x))
        {
            cnt++;
            d_col[i]++;
        }
    }
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j)
        {
            if(crush(i, j, x))
            {
                cnt = INF;
            }
        }
    }
    ans = min(ans,cnt);
    memset(d_col,0,sizeof(d_col));
    memset(d_row,0,sizeof(d_row));
    cnt = 0;
    if(!crush(1, 1, x))
    {
        cnt += 2;
        d_col[1]++,d_row[1]++;
    }
    for(int i = 1;i <= n;++i)
    {
        if(crush(1, i, x))
        {
            cnt++;
            d_col[i]++;
        }
        if(crush(i, 1, x))
        {
            cnt++;
            d_row[i]++;
        }
    }
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j)
        {
            if(crush(i, j, x))
            {
                cnt = INF;
            }
        }
    }
    ans = min(ans,cnt);
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i)
    {
        cin >> ma[i];
        ma[i] = " " + ma[i];
    }
    int ans1,ans2,ans;
    ans1 = into('0');
    ans2 = into('1');
    ans = min(ans1,ans2);
//     cout << ans1 << ' ' << ans2 << ' ';
    if(ans == INF)
    {
        cout << -1 << '\n';
    }else 
    {
        cout << ans << '\n';
    }
}

E. Koraidon, Miradon and DFS Shortest Path

从 为出发跑一遍最短路形成bfs树（在这里将 作为第 层向下形成bfs树，显然除了构成bfs树的边之外只剩下三种边：连接bfs树上同一层两点的边，从bfs树下层出发连向bfs树上层的边，从bfs树上层出发连向下层的边。其中，第三种边不影响树的正确生成（由于走了一遍bfs，这种边只能跨一层），第一种边一定会导致树无法正确生成，而对于第二种边，由于在dfs中每个点只更新一次，所以只要目标上层点在这条边被走过之前更新就能保证树的正确生成，即该边属于以目标为根的子树即可。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
typedef pair<int,int> PII;
struct Edge
{
    int from, to, val, next;
}edge[MAXN];
int n, m, cnt, s = 1;
int head[MAXN], dist[MAXN];
bool vis[MAXN];
bool flag = true;
inline void addEdge(int from, int to)
{
    edge[++cnt].to = to;
    edge[cnt].from = from;
    edge[cnt].val = 1;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
void dfs(int cur)
{
    if(!flag) 
        return ;
    vis[cur] = 1;
    for(int i = head[cur];i != -1;i = edge[i].next)
    {
        int j = edge[i].to;
        if(dist[j] == dist[cur] + 1)
        {
            dfs(j);
        }else if(vis[j])
        {
            continue;
        }else
        {
            flag = 0;
            break;
        }
    }
    vis[cur] = 0;
}
void dijikstra()
{
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0, 1});
    for(int i = 1; i <= n; ++i)
        dist[i] = INF;
    dist[1]=0;
    while(!q.empty())
    {
        auto t=q.top();
//         cout << t.second << '\n';
        q.pop();
        int u=t.second;
        if(vis[u])continue;
        vis[u]=true;

        for(int i=head[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
//             cout << v << ' ';
            if(dist[v] > dist[u]+1)
            {
                dist[v]=dist[u]+1;
                q.push({dist[v],v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        cnt = 0, s = 1;
        for(int i = 0; i <= n; ++i)
            head[i] = -1, vis[i] = 0;
        for(int i = 1; i <= m; ++i)
        {
            int u, v;
            cin >> u >> v;
            addEdge(u, v);
        }
        dijikstra();
        for(int i = 1;i <= n;++i)
        {
            vis[i] = 0;
        }
        vis[1] = 1;
        flag = 1;
        dfs(1);
//         for(int i = 1; i <= n; ++i)
//             cout << dist[i] << " ";
        if(flag)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

可能还会补B