前言
- E, F两题的代码参考来源均来自出题人的题解。
- 可以前去bilibili搜索牛客竞赛观看视频题解。
A-小红的字符串生成
思路：
- 枚举两种情况
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 100010;
using ll = long long;
void solve()
{
char a, b;
cin >> a >> b;
if(a != b)
{
cout << "4\n";
cout << a << endl;
cout << b << endl;
cout << a << b << endl;
cout << b << a << endl;
}
else
{
cout << "2\n";
cout << a << endl;
cout << a << b << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
B-小红的非排列构造
思路:
- 首先暴力判断是否为排列
- 如果是排列，修改一个数即可。
- 如果不是排列则输出0
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10;
using ll = long long;
int a[N];
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);
for(int i = 1; i < n; i ++)
if(a[i] == a[i + 1] || a[i] > n)
{
cout << "0\n";
return ;
}
if(a[n] > n)
{
cout << "0\n";
return ;
}
cout << "1\n1 99999999";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
C-小红的数字拆解
###思路：
- 贪心：遇到这一位数为偶数就拆解
- 注意排序方法即可
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10;
using ll = long long;
int a[N];
string s;
bool cmp(string x, string y)
{
if(x.size() != y.size())
return x.size() < y.size();
else
return x < y;
}
void solve()
{
vector<string> v;
cin >> s;
int len = (int)s.size();
string temp;
for(int i = 0; i < len; i ++)
{
temp += s[i];
if(((s[i] - '0') & 1) == 0)
{
v.push_back(temp);
temp.clear();
}
}
sort(v.begin(), v.end(), cmp);
for(string i : v)
cout << i << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
D-小红的陡峭值
思路:
- 恭喜获得分类讨论大师称号
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
int a[N];
void solve()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
//如果头和尾都不是0的特判
if(a[0] != 0 && a[n - 1] != 0)
if(abs(a[0] - a[n - 1]) != 1)
{
cout << "-1\n";
return ;
}
//记录最大值和最小值
int mi = INT_MAX, ma = 1;
for(int i = 0; i < n; i ++)
{
//记录最大值的位置和最小值的位置
if(a[i] == 0) continue;
ma = max(ma, a[i]);
mi = min(mi, a[i]);
}
vector<int> v1, v2;
//如果最大值和最小值的差值为1
if(ma - mi == 1)
{
for(int i = 0; i < n; i ++)
{
if(a[i] == 0) continue;
//如果值为最小值，则把坐标存入v1中
if(a[i] == mi) v1.push_back(i);
//如果值为最大值，则把坐标存入v2中
if(a[i] == ma) v2.push_back(i);
}
//如果最小值的最右边在最大值的最左边之前，则合法
if(v1.back() < v2[0])
{
//直接输出
int i;
for(i = 0; i <= v1.back(); i ++)
cout << mi << ' ';
for(; i < n; i ++)
cout << ma << ' ';
}
//如果最大值的最右边在最小值的最左边之前，则合法
else if(v2.back() < v1[0])
{
//直接输出
int i;
for(i = 0; i <= v2.back(); i ++)
cout << ma << ' ';
for(; i < n; i ++)
cout << mi << ' ';
}
else cout << -1;
}
//如果最大值等于最小值
else if(ma == mi)
{
//如果头为0
if(a[0] == 0)
{
cout << mi + 1 << ' ';
for(int i = 0; i < n - 1; i ++)
cout << mi << ' ';
}
//如果尾为0
else
{
for(int i = 0; i < n - 1; i ++)
cout << mi << ' ';
cout << mi + 1 << ' ';
}
}
//如果全是0
else if(mi > 1e9)
{
cout << "1 ";
for(int i = 0; i < n - 1; i ++)
cout << "2 ";
}
//都不是，输出-1
else cout << -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
E-小红的树形 dp
思路:
- 二分图
- d or p 各自只能在树的奇偶性相同的层级中：
- 比如d如果在奇数层， 为1 3 5 ……， 那么p只能在偶数层2 4 6……。反之亦然。
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10, M = 2 * N;
string s;
int dp[M];
vector<int> v[N];
//图的遍历
void dfs(int u, int fa, int p)
{
dp[u] = p;
for(int x : v[u])
{
if(x == fa) continue;
dfs(x, u, 1 - p);
}
}
void solve()
{
int n;
cin >> n >> s;
//建图
for(int i = 1; i < n; i ++)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
//使下标保持一致
s = ' ' + s;
dfs(1, 0, 1);
set<int> d, p;
//存入d or p 的节点的层数的奇偶
for(int i = 1; i <= n ; i++)
{
if(s[i] == 'd') d.insert(dp[i]);
if(s[i] == 'p') p.insert(dp[i]);
}
//当d or p 有一种的奇偶性都有，那代表不成立
if(d.size() > 1 || p.size() > 1)
{
cout << -1;
return ;
}
//在都只有一种奇偶性的情况下，避免d or p 处于同一种奇偶
else if((d.size() == 1 && p.size() == 1) && *d.begin() == *p.begin())
{
cout << -1;
return ;
}
//当d在奇数层的时候输出
if(*d.begin() == 1)
for(int i = 1; i <= n; i ++)
{
if(dp[i] == 1) cout << 'd';
else cout << 'p';
}
//当p在奇偶层的时候的输出
else
for(int i = 1; i <= n; i ++)
{
if(dp[i] == 1) cout << 'p';
else cout << 'd';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
京公网安备 11010502036488号