牛客周赛 Round 34
A 小红的字符串生成
简单的一道按序输出，判断两个字符是否相同，然后依次输出就行
#include<bits/stdc++.h>
using namespace std;
int main()
{
char a,b;
cin >>a >> b;
if(a == b)
{
cout<<2<<endl;
cout<<a<<endl<<a<<a<<endl;
}
else
cout<<4<<endl<<a<<endl<<b<<endl<<a<<b<<endl<<b<<a<<endl;
return 0;
}
B 小红的非排列构造
这题只要判断是否是排列数组就行了，如果是则将第一个改成n+1即范围外的数（我改成了100100是因为n最大就是1e5）。
#include<bits/stdc++.h>
using namespace std;
int a[100100];
int main()
{
int n , m;
cin >> n;
bool flag = true;
for(int i = 0 ; i <n ; i ++ )
{
cin >> m;
if(m > n) flag = false;
else{
a[m] ++ ;
if(a[m] >1 ) flag = false;
}
}
if(flag) cout<<1<<endl<<1<<" "<<100100<<endl;
else cout<<0<<endl;
return 0;
}
C 小红的数字拆解
这道题如果没仔细看的话很容易迷惑，注意“分割”这个字眼，所以直接贪心加排序（因为数字过长所以不能当作数字处理，排序不能用自带的库函数需要自己定义排序方法）就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
vector<string> V;
bool cmp(string &a,string &b)
{
if(a.size()==b.size())return a<b;
return a.size()<b.size();
}
int main()
{
cin >> s;
for(int i=0,j=0;i<s.size();i++)
if((s[i]-'0')%2==0)
{
V.push_back(s.substr(j,i-j+1));
j=i+1;
}
sort(V.begin(),V.end(),cmp);
for(auto c:V)cout<<c<<endl;
return 0;
}
D 小红的陡峭值
这题其实更倾向于分类讨论的类型，因为题目限制已经很强了，所以参考其中一个同学的做法，用了l、r、pos1、pos2四个变量来进行类举分别代表第一个非零量、第二个非零量、第一个非零量的位置、第二个非零量的位置。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int l=-1,r=-1;
int pos1=0,pos2=0;
bool flag=1;
for(int i=1;i<=n;i++)
{
if(a[i]!=0&&l==-1)
{
l=a[i];
}
if(l==a[i])
{
pos1=i;
}
if(a[i]!=0&&a[i]!=l&&pos2==0)
{
r=a[i];
pos2=i;
}
if(l!=-1&&r!=-1)
{
if(a[i]!=l&&a[i]!=r&&a[i]!=0)
{
flag=0;
}
}
}
if(pos2==0&&pos1==0)
{
for(int i=1;i<=n-1;i++) cout<<1<<' ';
cout<<2;
return 0;
}
if(pos2==0&&pos1!=0)
{
if(pos1!=n)
{
for(int i=1;i<=pos1;i++) cout<<l<<' ';
for(int i=pos1+1;i<=n;i++) cout<<l+1<<' ';
return 0;
}
if(pos1==n&&a[1]==0)
{
cout<<l+1<<' ';
for(int i=2;i<=n;i++) cout<<l<<' ';
return 0;
}
cout<<-1<<endl;
return 0;
}
if(abs(r-l)>1||pos1>pos2||flag==0)
{
cout<<-1<<endl;
return 0;
}
//如果有两个非零量且非零量差值合理
for(int i=1;i<=pos1;i++)
{
cout<<l<<' ';
}
for(int i=pos1+1;i<=n;i++)
{
cout<<r<<' ';
}
return 0;
}
E 小红的树形 dp
众所周知图论是我一生之敌（不是
据大佬所说，可以使用交叉染色的方法进行补齐然后再进行验证，所以可以就是bfs+验证
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N] , idx;
int w[N];
bool flag = 1;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u , int fa)
{
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
if(w[j] == w[u])
{
flag = 0;
}
else w[j] = (w[u] ^ 1);
dfs(j, u);
}
}
int main()
{
int n ;
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) h[i] = -1;
int root;
for(int i = 1 ; i <= n ; i ++ )
{
char s;
cin >> s;
if(s == 'p') w[i] = 0 ;
else if(s == 'd' ) w[i] = 1;
else w[i] = 2;
}
//双向图
for(int i = 1 ; i < n ; i ++ )
{
int a , b;
cin >> a >> b;
add(a , b);
add(b, a);
}
//找到一个函数入口
for(int i = 1 ; i <= n ; i ++ )
{
if(w[i] == 1)
{
root = i ;
break;
}
}
dfs(root , 0);
if(flag)
{
for(int i = 1 ; i <= n ; i ++ )
{
if(w[i] == 1) cout<<'d';
else cout<<'p';
}
}
else
cout<<-1<<endl;
return 0;
}
F 小红的矩阵构造
这题纯构造，写出来就写不来没写出来就没写出来
#include <iostream>
using namespace std;
const int N=1010;
int a[N][N];
int n,m,x;
int main(){
cin>>n>>m>>x;
if(x==2){
cout<<"-1"<<endl;
return 0;
}
if(x%4){
x-=6;
a[1][1]=a[1][4]=a[4][1]=a[4][4]=x/4;
a[1][2]=a[1][3]=a[2][1]=a[2][3]=a[3][1]=a[3][2]=1;
}
else a[1][1]=a[1][4]=a[4][1]=a[4][4]=x/4;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
G 小红的元素交换
双色环问题 ， 如果是双色环则是环数减一，单色环则是环数加一，如果是单色环则考虑先与其他单色环融合后当作双色环处理是最小次数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 100010;
void solve() {
int n;
string s;
cin >> n;
vector<int> a(n + 1);
vector<vector<int>> e(n + 1);
for(int i = 1; i <= n; i++) {
cin >> a[i];
e[i].push_back(a[i]);
}
cin >> s;
s = " " + s;
vector<int> vis(n + 1);
vector<vector<int>> sz(3); // r w rw
int tol = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
tol++;
int u = i, r = 0, w = 0, cnt = 0;
while(!vis[u]) {
vis[u] = 1;
cnt++;
r |= (s[u] == 'R');
w |= (s[u] == 'W');
u = e[u].front();
}
if(r && w) sz[2].push_back(cnt);
else if(r) sz[0].push_back(cnt);
else sz[1].push_back(cnt);
}
}
if(tol == n) {
cout << 0 << '\n';
return;
}
for(int i = 0; i < 2; i++) {
if(sz[i].size() && !sz[!i].size() && !sz[2].size()) {
cout << -1 << '\n';
return;
}
}
sort(sz[0].begin(), sz[0].end());
sort(sz[1].begin(), sz[1].end());
int ans = 0;
for(int i = 0; i < 2; i++) {
while(sz[i].size() && sz[i].back() > 1) {
if(sz[!i].size()) {
sz[2].push_back(sz[i].back() + sz[!i].back());
sz[!i].pop_back();
} else {
sz[2][sz[2].size() - 1] += sz[i].back();
}
sz[i].pop_back();
ans++;
}
}
for(int x : sz[2]) ans += x - 1;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while(t--) solve();
return 0;
}
