前言：
- 该比赛有牛客官方视频讲解——牛客周赛35视频讲解回放
A - 小红的字符串切割
思路：
- 分两半输出即可
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
void solve()
{
string s;
cin >> s;
s = '&' + s;
int i;
for(i = 1; i <= s.length() / 2; i ++)
cout << s[i];
cout << endl;
for(; i < s.length(); i ++)
cout << s[i];
cout << 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 - 小红的数组分配
思路：
- 从小到大排序，判断元素大小是否两两相等。
- 若是， 则输出数组
- 否则输-1
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 2e5 + 10;
int a[N];
void solve()
{
int n;
cin >> n;
//注意题目是2*n
n *= 2;
for(int i = 1; i <= n; i ++)
cin >> a[i];
//排序
sort(a + 1, a + n + 1);
//判断是否两两相等
for(int i = 1; i <= n; i += 2)
if(a[i] != a[i + 1])
{
cout << -1 << endl;
return ;
}
//分奇偶输出
for(int i = 1; i <= n; i++)
if(i & 1)
cout << a[i] << ' ';
cout << endl;
for(int i = 1; i <= n; i ++)
if((i & 1) == 0)
cout << a[i] << ' ';
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
C-小红关鸡
思路 1（渣渣的思路）：
- 从小到大排序， 找到比
小的最大数的位置， 算出区段中的数的个数，并用ans记录数量最多的值
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
ll a[N];
//判断
bool check(ll x, ll y)
{
if(x <= y) return true;
return false;
}
//二分查找
int finds(ll v, int n)
{
int l = 1, r = n, mid;
while(l < r)
{
mid = (r + l) >> 1;
//分两次判断，使其可以跳出循环
if(check(a[mid + 1], v))
l = mid + 1;
else if(check(a[mid], v))
{
if((r + l) / 2 == l) break;
l = mid;
}
else
r = mid - 1;
}
mid = (r + l) >> 1;
//返回下标
return mid;
}
void solve()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for(int i = 1; i <= n; i ++)
{
int temp = finds(a[i] + k, n);
//记录最大值
ans = max(ans, temp - i + 1);
}
//输出概率
cout << double(ans) / n << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
思路2（思路来源——LittleXi的题解）：
- 利用双指针从头到尾遍历1次即可
- 判断区段
内的合法数值的数量，并统计最大值即可
以下是代码部分，代码参考来源——GhostLX知乎题解
#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, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
//从小到大排序
sort(a + 1, a + n + 1);
int l = 1, r = 1;
int ans = 1;
//双指针遍历
while(l <= n)
{
while(a[r + 1] - a[l] <= k && r < n)
r ++;
ans = max(ans, r - l + 1);
l ++;
}
//输出
cout << double(ans) / n << 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];
//储存需要修改的数组， key为坐标， value为数值
map<int, int> mp;
//储存1-n有哪些数没用到
bool vis[N];
void solve()
{
int n;
cin >> n;
//存储需要修改的数的个数，初始化为n
int cnt = n;
//输入
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
mp[i] = a[i];
}
for(int i = 1; i <= n; i ++)
{
//大于n，则直接跳过
if(a[i] > n) continue;
//如果数值a[i]没用到过
if(!vis[a[i]])
//标记为用过， 删除该结点， 需要修改的数-1
vis[a[i]] = true, mp.erase(i), cnt --;
}
//输出需要修改的数的个数
cout << cnt << endl;
//迭代器， 初始化迭代器
auto it = mp.begin();
//暴力
for(int i = 1; i <= n; i ++)
//如果这个数值没有用到过
if(!vis[i])
//mp中，在这个坐标下的value修改为没用过的值，并使迭代器移到下一位
it->second = i, it ++;
//遍历输出
for(auto x : mp)
cout << x.first << ' ' << x.second << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
代码参考来源——长途
#include<iostream>
#include<vector>
using namespace std;
const int N=100005;
int a[N];
int n;
bool st[N];
int main()
{
scanf("%d",&n);
vector<int> ver;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
//如果范围在1~n范围内，则标记为true
if(a[i]>=1&&a[i]<=n&&!st[a[i]])
st[a[i]]=true;
else
//否则把坐标放入到ver数组中
ver.push_back(i);
}
vector<int> ver2;
for(int i=1;i<=n;i++)
//如果该数值未用过
if(!st[i])
//把需要修改后的值放入ver2数组中
ver2.push_back(i);
//输出需要修改的数值个数
printf("%d\n", (int)ver.size());
//输出即可
for(int i=0;i<ver.size();i++)
printf("%d %d\n",ver[i],ver2[i]);
}
E-小红的无向图构造
思路：
- 实际上就是建一个树。该树分层。结点
在第几层，则它离头结点
的距离为多少。
- 总而言之，按照距离分层建图。
- 后若最大的边数小于
则为
- 若
也输出
- 其他情况有解
以下是代码部分，代码参考来源——牛客周赛35视频讲解回放
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 2e5 + 10;
***[i]的i代表层数， g[i]的值代表结点的标号
vector<int> g[N];
int main()
{
int n, m, maxn = 0;
cin >> n >> m;
//建树，并标记最大值
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
maxn = max(maxn, a[i]);
g[a[i]].push_back(i);
}
//已知树的边数为n - 1, 当无法建树时
if(m < n - 1)
return cout << -1, 0;
//储存相连的坐标
vector<pair<int, int>> v;
//先建树
for(int i = 1; i <= maxn; i++)
{
//如果有一层为空，则无法建树
if(g[i].empty())
return cout << -1, 0;
//如果非空，则把层数和下标存入v中
for(auto j : g[i])
v.emplace_back(g[i - 1][0], j);
}
//如果建立出树之后，仍不满足条件， 求最多多少条边
if(v.size() < m)
{
//此循环用来同层节点相连
for(int i = 1; i <= maxn; i++)
{
for(int j = 0; j < g[i].size(); j ++)
{
for(int k = j + 1; k < g[i].size(); k ++)
{
v.emplace_back(g[i][j], g[i][k]);
if(v.size() == m) break;
}
if(v.size() == m) break;
}
if(v.size() == m) break;
}
//该循环用来相邻层的节点相连
for(int i = 1; i <= maxn; i ++)
{
//注意排除第一个结点，因为之前连过了。
for(int j = 1; j < g[i].size(); j ++)
{
for(auto k : g[i + 1])
{
v.emplace_back(g[i][j], k);
if(v.size() == m) break;
}
if(v.size() == m) break;
}
if(v.size() == m) break;
}
}
//判断边的数量是否满足条件
if(v.size() < m)
return cout << -1, 0;
//输出
for(auto i : v) cout << i.first << ' ' << i.second << endl;
return 0;
}
F & G - 小红的子序列权值和
思路1牛客官方视频题解：
……
- 结论（需记住）：
- 那么x的因子数为
……
- 那么x的因子数为
- 先把
- 先利用二项式公式求出取
，
个
的总共组合数。再乘以么个组合的因数个数 3.后是否选择
,
为
- 可得出公式——（
- 所以可以用乘法逆元快速求出组合数，再乘权值即可
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
// 该数值的个数
int tong[4];
int mod = 1e9 + 7;
//快速幂
ll power(ll base, ll pow)
{
ll res = 1;
while(pow)
{
if(pow&1) res = res * base % mod;
pow >>= 1;
base = base * base % mod;
}
return res;
}
//小费马求乘法逆元
ll inv(ll x)
{
return power(x, mod - 2);
}
ll fac[N] = {1};
//求组合数
ll C(int n, int m)
{
return fac[n] * inv(fac[n - m]) % mod * inv(fac[m]) % mod;
}
int main()
{
int n;
cin >> n;
//求阶乘
for(int i = 1; i <= n; i ++)
fac[i] = fac[i - 1] * i % mod;
ll temp = 1, c2 = 0, c3 = 0;
//统计每个数出现的次数
for(int i = 0; i < n; i ++)
{
int x; cin >> x;
tong[x] ++;
}
//temp储存数值1的贡献
for(int i = 1; i <= tong[1]; i++)
temp = temp * 2 % mod;
//每次求出
for(int i = 0; i <= tong[2]; i ++)
{
c2 += C(tong[2], i) * (i + 1) % mod;
c2 %= mod;
}
//每次求出
for(int i = 0; i <= tong[3]; i ++)
{
c3 += C(tong[3], i) * (i + 1) % mod;
c3 %= mod;
}
cout << (c2 * c3 % mod * temp % mod - 1 + mod) % mod << endl;
return 0;
}
优化方案
-
参考来源smilences的题解
-
-
用此公式，替换到思路1的代码中。
-
推导过程如下
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// 该数值的个数
ll tong[4];
int mod = 1e9 + 7;
//快速幂
ll power(ll base, ll pow)
{
ll res = 1;
while(pow)
{
if(pow&1) res = res * base % mod;
pow >>= 1;
base = base * base % mod;
}
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
tong[x] ++;
}
ll ans = 1;
//利用推导的公式求值为2的情况
if(tong[2])
ans *= tong[2] * power(2, tong[2] - 1) % mod + power(2, tong[2]);
ans %= mod;
//利用推导的公式求值为3的情况
if(tong[3])
ans *= tong[3] * power(2, tong[3] - 1) % mod + power(2, tong[3]);
ans %= mod;
//求值为1时的情况
ans *= power(2, tong[1]);
ans %= mod;
cout << (ans + mod - 1) % mod << '\n';
return 0;
}
京公网安备 11010502036488号