牛客周赛 Round 57题解(A - G 无D解)

A-小红喜欢1_牛客周赛 Round 57(重现赛) (nowcoder.com)

void solve()
{int ans = 0;for(int i  = 1;i <= 5;i++){cin >> n;ans = (n == 1 ? i : ans);}cout << ans << endl;
}

B-小红的树切割_牛客周赛 Round 57(重现赛) (nowcoder.com)

相邻的节点颜色相同就剪即可

void solve()
{int ans = 0;string s;cin >> n >> s;s = " " + s;for(int i = 1; i < n; i++){int u, v;cin >> u >> v;ans += (s[u] == s[v]);}cout << ans << endl;
}

C-小红的双好数（easy）_牛客周赛 Round 57(重现赛) (nowcoder.com)

1：首先所有数的2进制一定满足要求 

2：1的所有进制都满足

3：2是只有2进制满足

void solve()
{cin >> n;if(n == 1)cout << "YES" << endl << 2 << ' ' << 3 << endl;else if(n > 2){cout << "YES" << endl;cout << 2 << ' ' << n << endl;}elsecout << "NO" << endl;
}

 D-小红的线段_牛客周赛 Round 57(重现赛) (nowcoder.com)

E-小红的双好数（hard）_牛客周赛 Round 57(重现赛) (nowcoder.com)

暴力搜索即可

bool check(int x, int y)
{while(x){if(x % y > 1) return false;x /= y;}return true;
}void solve()
{int k1, k2;cin >> k1 >> k2;for(int i = k2; i < k2 + 1e6; i++){if(check(i , k1) && check(i, k2)){cout << "YES" << endl << i;return;}}cout << "NO" << endl;
}

F-小红的数组操作_牛客周赛 Round 57(重现赛) (nowcoder.com)

线段树模板

 

G-小红的双排列构造_牛客周赛 Round 57(重现赛) (nowcoder.com)

1：对于n == 1的情况而言区间数只能为2

如下： 1 1

2：对于n == 2的情况无论如何排序其区间数一定不为1

例如: 1 2 1 2 |  2 2 1 1 | 1 1 2 2 找不出为0的解

3：对于其他n而言区间数为[0 , n + 1]

4: 对于非1，2的n而言，k为0的通解就是将2个相同的数放在一起即可

如： 1 1 2 2 3 3

5: 最大的k解排序一定是

1 2 3 …… n 1 2 3 …… n的顺序排列

6：在2 至 n + 1区间数是有规律可言的，这边我直接给一个显著的样例，不必多言

n == 4的前提下

基础排序	k值
1 2 3 4 1 2 3 4	5
2 1 3 4 1 2 3 4	4
2 3 1 4 1 2 3 4	3
2 3 4 1 1 2 3 4	2

7：对于k == 1的样例(n > 2)解是可以直接构造的

通解为 将一个1至n的数组插入另外一个1至n数组的1 和 2之间即可

例 n == 4

1 1 2 3 4 2 3 4

剩下的就是将上述分类讨论得解即可非常简单的一题

void solve()
{cin >> n >> k;if(n == 1 && k < 2 || n == 2 && k < 1){cout << -1 << endl;return;}for(int i = 1;i <= n;i++)a[i] = i;vector<int> v(n + 1);for(int i = 1; i <= n; i++)cin >> v[i];if(k > n + 1){cout << -1 << endl;return;}if(k == 0){for(int i = 1; i <= n; i++)cout << i << ' ' << i << ' ';}else if(k == 1){cout << 1 << ' ';for(int i = 1;i <= n; i++)cout << i << ' ';for(int i = n;i >= 2; i--)cout << i << ' ';}else{int t = n + 1 - k;if(t)swap(a[1] , a[1 + t]);for(int i = 1; i <= n; i++)cout << a[i] << ' ';for(int i = 1; i <= n; i++)cout << i << ' ';}
}