牛客周赛 Round 34
感觉比以往难度有些大，但是大佬们该强的还是很强啊
小红的字符串生成
思路
就两个字符，如果字符相同只能组成两种，不同则可以组成四种
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
#define ct(x) cout<<x<<endl
void solve(){
char a,b;
cin>>a>>b;
if(a!=b){
cout<<4<<endl;
cout<<a<<endl;
cout<<b<<endl;
cout<<b<<a<<endl;
cout<<a<<b<<endl;
return ;
}
else{
cout<<2<<endl;
cout<<a<<endl;
cout<<a<<a<<endl;
return ;
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的非排列构造
思路
这个题我一开始做的比较蒙，原来是自己一开始没有读懂题意，罪过罪过
我们可以用map存储一下每个数字出现的个数，如果没有出现n个，或者1-n中有的数字一次也没出现则一开始就是一个非排列，因此不需要进行操作，否则我们只需要操作一个数字就可以
Code
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define all(x) x.begin(),x.end()
void solve(){
int n;
cin>>n;
std::vector<int> a(n+1);
std::map<int, int> mp;
set<int> s;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
// s.insert(a[i]);
}
if(mp.size()!=n){
cout<<0<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(mp[i]==0){
cout<<0<<endl;
return ;
}
}
cout<<1<<endl;
if(a[1]>=n){
cout<<1<<" "<<a[1]-1<<endl;
return ;
}
else{
cout<<1<<" "<<a[1]+1<<endl;
return ;
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的数字拆解
思路
我们如果想得到尽可能多的整数，那我们就需要对所有为偶数的位置上进行切断就可以，由于数字很大，所以我们考虑用字符串进行操作和读取，其次题目要求要从小到大输出每个偶数，所以我们做一个字符串的排序就可以了，我就在自定义字符串排序中犯了一个天大的错误
Code
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define all(x) x.begin(),x.end()
bool cmp(string a,string b){
if(a.size()==b.size()){
for(int i=0;i<a.size();i++){
int x=a[i]-'0';
int y=b[i]-'0';
if(x==y){
continue;
}
else{
return x<y;
}
}
}
return a.size()<b.size();
}
void solve(){
string s;
cin>>s;
std::vector<string> a;
string s1="";
for(int i=0;i<s.size();i++){
s1+=s[i];
if((s[i]-'0')%2==0){
a.emplace_back(s1);
s1="";
}
else{
// s1+=s[i];
continue;
}
}
sort(all(a),cmp);
for(auto x:a){
cout<<x<<endl;
}
return ;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的陡峭值
思路
构造序列的问题，很遗憾我这题只拿了188.89，应该是有地方写混乱了，这个题只要分类讨论再根据情况进行构造就行,最后我才发现原来我写的代码会让出现1的时候0的位置还是0，这样是不对的，我们只能让其他等于0的位置变成2
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
void solve(){
int n;
cin>>n;
std::vector<int> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
std::set<int> s;
std::map<int, int> mp;
for(int i=1;i<n;i++){
if(a[i]!=0&&a[i+1]!=0){
res+=abs(a[i+1]-a[i]);
}
s.insert(a[i]);
mp[a[i]]++;
}
s.insert(a[n]);
mp[a[n]]++;
// cout<<(*s.end())<<endl;
// return ;
// for(auto x:s){
// cout<<x<<" ";
// }
// returnn ;
if(res==1&&mp[0]==0){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
return ;
}
if(res>1||s.size()>3){
cout<<-1<<endl;
return ;
}
else{
if(s.size()==1){
if(a[1]!=0){
cout<<-1<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(i!=n){
cout<<1<<" ";
}
else{
cout<<2<<endl;
}
}
}
else if(s.size()==2){
bool f=false;
for(auto it:s){
if(it==0){
f=true;
}
}
if(!f){
if(res==1){//不存在0且陡峭值不等于1
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
return ;
}
else{
cout<<-1<<endl;
return ;
}
}
// int x= *s.end();
int x=-1;
for(auto it:s){
if(it!=0){
x=it;
}
}
// cout<<x<<endl;
int idx=-1;
// cout<<x<<endl;
if(mp[x]==1){
for(int i=1;i<=n;i++){
if(a[i]==x){
idx=i;
break;
}
}
if(idx==1){
if(x>1){
for(int i=1;i<=n;i++){
if(i!=1){
cout<<x-1<<" ";
}
else{
cout<<x<<" ";
}
}
return ;
}
else{
for(int i=1;i<=n;i++){
if(i!=1){
cout<<x+1<<" ";
}
else{
cout<<x<<" ";
}
}
return ;
}
}
if(x!=1){
for(int i=1;i<=n;i++){
if(i<idx){
cout<<x-1<<" ";
}
else{
cout<<x<<" ";
}
}
}
else{
for(int i=1;i<=n;i++){
if(i<idx){
cout<<x+1<<" ";
}
else{
cout<<x<<" ";
}
}
}
}
else{
std::vector<int> b;
for(int i=1;i<=n;i++){
if(a[i]==x){
b.push_back(i);
}
}
if(b[0]!=1||b[b.size()-1]!=n){
if(b[0]!=1){
for(int i=1;i<=n;i++){
if(i<b[0]){
cout<<x+1<<" ";
}
else{
cout<<x<<" ";
}
}
return ;
}
else{
for(int i=1;i<=n;i++){
if(i>b[b.size()-1]){
cout<<x+1<<" ";
}
else{
cout<<x<< " ";
}
}
return ;
}
}
else{
cout<<-1<<endl;
return ;
}
}
}
else if(s.size()==3){
bool f=false;
for(auto it:s){
if(it==0){
f=true;
}
}
if(!f){
cout<<-1<<endl;
return ;
}
int x=-1,y=-1;
// for(auto it:s){
// if(it!=0){
// if(x==-1){
// x=it;
// }
// else{
// y=it;
// }
// }
// }
// cout<<x<<" "<<y<<endl;
// return ;
for(int i=1;i<=n;i++){
if(a[i]!=0){
if(x==-1){
x=a[i];
}
else{
if(a[i]!=x){
y=a[i];
}
}
}
}
// cout<<x<<" "<<y<<endl;
// return ;
if(abs(x-y)!=1){
cout<<-1<<endl;
return ;
}
std::vector<int> c,d;
for(int i=1;i<=n;i++){
if(a[i]==x){
c.push_back(i);
}
if(a[i]==y){
d.push_back(i);
}
}
if(c[c.size()-1]>d[0]){
cout<<-1<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(i<d[0]){
cout<<x<<" ";
}
else{
cout<<y<<" ";
}
}
return ;
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的树形 dp
思路
dfs一下，让根节点是'd'或'p'都变一下，如果能出现合法字符串即为可以，否则不行
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
vector<int> g[N];
string s1;
bool dfs(int x,int y,char a){
if(s1[x]!='?'&&s1[x]!=a){
return false;
}
s1[x]=a;
if(a=='d'){
a='p';
}
else{
a='d';
}
for(int i=0;i<g[x].size();i++){
if(g[x][i]==y){
continue;
}
if(s1[g[x][i]]=='?'||s1[g[x][i]]==a){
bool f=dfs(g[x][i],x,a);
if(!f){
return false;
}
}
else{
return false;
}
}
return true;
}
void solve(){
int n;
cin>>n;
string s;
cin>>s;
s=" "+s;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
s1=s;
bool f=false;
if(s1[1]=='d'||s1[1]=='?'){
f=dfs(1,-1,'d');
if(f){
for(int i=1;i<=n;i++){
cout<<s1[i];
}
return ;
}
}
s1=s;
if(s1[1]=='p'||s1[1]=='?'){
f=dfs(1,-1,'p');
if(f){
for(int i=1;i<=n;i++)
cout<<s1[i];
return ;
}
}
cout<<-1<<endl;
return ;
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}