牛客周赛 Round 34
A小红的字符串生成
题目描述：
小红拿到了两个字符，请你输出这两个字符可以生成的所有字符串。按任意顺序输出均可。
输入描述:
两个小写字母，用空格隔开。
输出描述:
第一行输出一个正整数n，代表可以生成的不同字符串数量。
接下来的n行，每行输出一个仅由小写字母组成的字符串。
签到题，只需要注意当两个字符相同时只有两种情况即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
char a,b;
cin >> a >> b;
if(a!=b){
cout << 4 << '\n';
cout << a << '\n';
cout << a << b << '\n';
cout << b << '\n';
cout << b << a << '\n';
}else{
cout << 2 << '\n';
cout << a << '\n';
cout << a << b << '\n';
}
return 0;
}B小红的非排列构造
题目描述:
小红拿到了一个数组,她修改尽可能少的元素使其变成非排列。你能帮帮她吗?
定义排列为一个长度为n的数组,其中1到n每个元素恰好出现一次。
输入描述:
第一行输入一个正整数n,代表数组的大小。
第二行输入n个正整数a,用空格隔开。代表数组的元素。
1≤n≤10
1≤a≤10
输出描述:
首先输出一个整数m,代表操作次数。
接下来的m行,每行输出两个正整数i,x,用空格隔开,代表将第i个元素修改为x。
有多种合法方案时,输出任意一种均可。
请注意,输入的i,x必须满足1≤i≤n且1≤x≤10
脑筋急转弯
如果合法，就是0，如果不合法，就把第1项改为n+1（排列外的数）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
ll a[maxn], v[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
bool f = false, b = false;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!v[a[i]]) {
v[a[i]]++;
} else {
f = true;
}
}
for (int i = 1; i <= n; i++) {
if (v[i] != 1) {
b = true;
break;
}
}
if (f || b) {
cout << 0;
} else {
cout << 1 << '\n' << 1 << ' ' << n+1;
}
return 0;
}C小红的数字拆解
越目描述:
小红拿到了一个偶数,她希望你将其切割成尽可能多的偶数。你能帮帮她吗?
输入描述:
一个偶数x。
1≤x<
输出描述:
输出若干行,从小到大输出每个偶数。(1个偶数可以重复出现)
贪心思想，从高位到低位贪心即可。
注意：测试数据的范围超过了__int128,所以要用字符串或者高精度表示。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
string sh[maxn];
bool cmp(const string& s, const string& c) {
if (s.length() != c.length()) {
return s.length() < c.length();
}
return s < c; // 长度相等时，按照字符串字典序排序
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string ch;
cin >> ch;
ll l = 0, r = 0, k = 0;
while (r < ch.length()) {
if ((ch[r] - '0') % 2 == 0) {
sh[k] = ch.substr(l, r - l + 1); // 复制字符串
k++;
l = r + 1;
}
r++;
}
sort(sh, sh + k, cmp);
for (int i = 0; i < k; i++) {
cout << sh[i] << '\n';
}
return 0;
}
D小红的陡峭值
题目描述:
小红定义一个数组的陡峭值为相邻两数差的绝对值之和。
现在小红拿到了一个长度为n的、仅由正整数组成的数组,但她有一些元素看不清了,只记得数组的陡峭值恰好等于1。
小红希望你能还原整个数组,你能帮帮她吗?
输入描述:
第一行输入一个正整数n,代表数组的大小。
第二行输入n个整数a,其中如果a;为0 代表小红看不清该元素,大于 0 代表能看清该元素。
2≤n≤10
0≤a≤10
输出描述:
如果无解,请输出 -1。
否则输出n个正整数,用空格隔开,代表小红还原的数组。
有多解时输出任意即可。
模拟：因为陡峭值要恰好为1，所以只能有一个分界线。
情况1：当a和a均不等于0时，那只有当,才有可能满足题目条件，否则直接输出-1；
如果满足前面情况，我们可以设ma和mi表示数组a中不等于0时的最大值和最小值。
当时，判断时mi在ma左边，还是ma在mi左边，并打印出相应的正确答案。如果ma的位置和mi的位置是交错的，那直接输出-1。
当ma==mi时，当a[1]==0,那么让a[1]=ma+1,其余的均为ma，否则a[n]=ma+1,其余的均为ma，
还有一种全是0的情况，那么mi就还是等于初始值，这种情况直接输出 2 1 1 1 …
其他情况直接输出-1。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
ll a[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
for(ll i=1;i<=n;i++) cin >> a[i];
if(a[1]!=0 && a[n]!=0){
if(abs(a[1]-a[n])!=1){
cout << -1;
return 0;
}
}
ll ma=1,mi=2e9;
for(int i=1;i<=n;i++){
if(a[i]==0) continue;
ma=max(ma,a[i]);
mi=min(mi,a[i]);
}
if(ma-mi==1){
vector<ll>v1,v2;//v1->ma,v2->mi;
for(int i=1;i<=n;i++){
if (a[i] == 0) continue;
if(a[i]==ma) v1.push_back(i);
if(a[i]==mi) v2.push_back(i);
}
if(v1.back()<v2[0]){
for(ll i=1;i<=v1.back();i++) cout << ma << ' ';
for(ll i=v1.back()+1;i<=n;i++) cout << mi << ' ';
}else if(v2.back()<v1[0]){
for(ll i=1;i<=v2.back();i++) cout << mi << ' ';
for(ll i=v2.back()+1;i<=n;i++) cout << ma << ' ';
}else{
cout << -1;
}
}else if(ma==mi){
if(a[1]==0){
cout << ma+1 << ' ';
for(ll i=2;i<=n;i++) cout<< ma << ' ';
}else{
for(ll i=1;i<n;i++) cout << ma << ' ';
cout << ma+1 ;
}
}else if(mi==2e9){
cout << 2 << ' ';
for(ll i=2;i<=n;i++ ) cout << 1 << ' ';
}else{
cout << -1;
}
return 0;
}E小红的树形 dp
题目描述：
小红拿到了一棵树,每个节点上有一个字符,每个节点上的字符为’d’、‘p’、‘?‘这三种。
现在请你将所有’?‘字符变成’d’或者’p’字符,需要满足任意两个相邻节点的字符不同。你能帮帮她吗?
输入描述:
第一行输入一个正整数n,代表节点的数量。
第二行输入一个长度为n的、仅包含’?’、'd’和’p’的字符串。第i个字符代表i号节点的初始字符。
接下来的n-1行,每行输入两个正整数u,v,代表节点u和节点v有一条边连接。
1≤n≤10
输出描述:
如果无解,请输出 -1。
否则输出一个由‘d’和’p’组成的字符串,第i个字符代表最终i号节点上的字符。
图论的基础知识，遍历字符串，找到第一个不是’?‘的作为树的根进行dfs遍历。如果都是’?',那么把第一个字符变成’d’或’p’作为树的根进行遍历。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
ll a[maxn];
vector<ll>e[maxn];
string ch;
bool f=true;
void dfs(ll u,ll fa){
if(!f){
return;
}
for(auto ed:e[u]){
if(ed==fa){
continue;
}
if(ch[ed]==ch[u]){
f=false;
return ;
}else if(ch[ed]=='?'){
if(ch[u]=='d'){
ch[ed]='p';
}else{
ch[ed]='d';
}
}
dfs(ed,u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,st=1e9;
cin >> n;
cin >> ch;
for(int i=1;i<n;i++){
ll u,v;
cin >> u >> v;
e[u-1].push_back(v-1);
e[v-1].push_back(u-1);
}
for(int i=0;i<ch.length();i++){
if(ch[i]!='?'){
st=i;
break;
}
}
if(st==1e9){
ch[0]='p';
dfs(0,0);
}else{
dfs(st,st);
}
if(f){
cout << ch;
}else{
cout << -1;
}
return 0;
}
F小红的矩阵构造
题目描述:
小红希望你构造一个n行m列的矩阵,满足所有元素之和恰好等于x,且每行、每列的异或和全部相等。你能
帮帮她吗?
输入描述:
三个正整数n,m,xc,用空格隔开。
4≤n,m≤ 1000
2≤x≤10
保证x是偶数。
输出描述:
如果无解,请输出 -1。
否则输出n行,每行输出m个非负整数,代表一个合法解。有多解时输出任意即可。
模拟，找出一种解决方案。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,x;
int a[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>x;
if(x%4==0){
a[1][1]=a[1][2]=a[2][1]=a[2][2]=x/4;
}
else if(x>2){
a[1][1]=a[1][2]=a[2][1]=a[2][2]=(x-6)/4;
a[2][3]=a[2][4]=a[3][2]=a[3][3]=a[4][2]=a[4][4]=1;
}
else{
cout<<-1<<'\n';
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<' ';
}
cout<<'\n';
}
}G小红的元素交换
题目描述:
小红拿到了一个排列,其中初始所有元素都是白色,但有一些元素被染成了红色。
小红每次操作可以选择交换任意一个红色元素和一个白色元素的位置。她希望操作尽可能少的次数使得数组
变成升序,你能帮帮她吗?
排列是指:一个长度为n的数组,其中1到n每个元素恰好出现了一次。
输入描述:
第一行输入一个正整数n,代表排列的长度。
第二行输入n个正整数a,代表排列的元素。
第三行输入一个长度为n的字符串,代表数组元素的染色情况。第i个字符为‘R’代表第i个元素被染成红
色,为’W’代表初始的白色。
1≤n≤10
1≤a≤n
输出描述:
如果无法完成排序,请输出 -1。
否则输出一个整数,代表操作的最小次数。
思路: 置换环 + 找规律
假如这题没有交换颜色的限制，那这题就是裸的置换环
但是实际上，这题的核心框架依旧是
置换环。
具体情况需要分类讨论
同一置换环(a个元素)中存在两种颜色, 则交换的次数一定为a-1
同一置换环(a个元素)中只存在1种颜色, 则需要借助外部的非同色形成一个混环，交换次数为1。
白环+红环=混环。
白环+混环=混环。
红环+混环=混环。
长度大于1的白/红环才需要变成混环。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1010;
int n , a[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
string s;
cin >> s;
s = ' ' + s;
int vis[N];
vector<int> r , w , h;
for(int i = 1; i <= n; i ++)
{
int st[26] = {};
int cnt = 0;
if(!vis[i])
{
for(int j = a[i]; !vis[j] ; j = a[j])
{
st[s[j] - 'A'] = 1;
vis[j] = 1;
cnt ++;
}
if(st['W' - 'A'] && st['R' - 'A'])
h.push_back(cnt);
else if(!st['W' - 'A'] && st['R' - 'A'])
r.push_back(cnt);
else if(!st['R' - 'A'] && st['W' - 'A'])
w.push_back(cnt);
}
}
sort(r.begin() , r.end());
sort(w.begin() , w.end());
int res = 0;
// 把长度大于1的白环和红环结合为混环
while(r.size() && w.size())
{
if(r.back() == 1 || w.back() == 1) break;
int v1 = r.back();
int v2 = w.back();
r.pop_back();
w.pop_back();
h.push_back(v1 + v2);
res ++;
}
//如果混环不存在，则要拿一个长度为1的白/红环与一个长度大于1的红/白环结合为一个混环
if(!h.size() && r.size() && w.size() && (r.back() > 1 || w.back() > 1))
{
int v1 = r.back();
int v2 = w.back();
r.pop_back();
w.pop_back();
h.push_back(v1 + v2);
res ++;
}
//混环不存在，却存在长度大于1的红/白环，则不满足
if(r.size() && r.back() > 1 && !h.size())
{
cout << -1;
return 0;
}
if(w.size() && w.back() > 1 && !h.size())
{
cout << -1;
return 0;
}
//将剩余的白/红环与混环再结合
while(r.size() && h.size())
{
if(r.back() == 1) break;
int v1 = r.back();
int v2 = h.back();
r.pop_back();
h.pop_back();
h.push_back(v1 + v2);
res ++;
}
while(w.size() && h.size())
{
if(w.back() == 1) break;
int v1 = w.back();
int v2 = h.back();
w.pop_back();
h.pop_back();
h.push_back(v1 + v2);
res ++;
}
//统计，每一个混环调整都是它的长度i的i-1次；
for(auto i : h) res += i - 1;
cout << res;
return 0;
}
