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 << ' ';}
}