day1
Q1 难度⭐⭐
题目：
kotori最近喜欢上了lovelive这个游戏，因为她发现自己居然也是里面的一个人物。
lovelive有个抽卡系统。共有R、SR、SSR、UR四个稀有度，每次单抽对应稀有度的概率分别是80%，15%，4%，1%。
然而，kotori抽了很多次卡还没出一张UR，反而出了一大堆R，气得她想删游戏了。她想知道n次单抽正好出m张R卡的概率是多少？
输入描述：两个正整数n和m（1<=m<=n<=50）
输出描述：n次单抽正好出m张R的概率。保留四位小数。
思路：
#include <iostream>
using namespace std;
int main()
{
double ans=1;
int n, m, i;
cin >> n >> m;
for(i=0; i<n-m; i++)
ans*=0.2;
for(i=n; i>=n-m+1; i--)
ans*=i;
for(i=m; i>1; i--)
ans/=i;
for(i=0; i<m; i++)
ans*=0.8;
printf("%.4lf\n", ans);
return 0;
}Q2 难度⭐⭐⭐
题目：
ruby很喜欢吃薯条。
有一天，她拿出了n根薯条。第i根薯条的长度为ai。
ruby认为，若两根薯条的长度之差在l和r之间，则认为这两根薯条有“最萌身高差”。
用数学语言描述，即若l≤|ai-aj|≤r，则第i根薯条和第j根薯条有“最萌身高差”。
ruby想知道，这n根薯条中，存在多少对薯条有“最萌身高差”？
注：次序不影响统计，即认为(ai,aj)和(aj,ai)为同一对。
输入描述：第一行三个正整数n,l,r，含义见题目描述。 （1≤n≤200000,1≤l≤r≤1e9）
第二行n个正整数ai，分别代表每根薯条的长度。 （1≤ai≤1e9）
输出描述：一个正整数，代表，代表“最萌身高差”的薯条对数。
思路：
遍历一遍数组，判断并统计每位有多少个最萌身高差对象
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
long long n, l, r;
cin >> n >> l >> r;
vector<long long> arr(n);
for (int i = 0; i < n; i ++)
cin >> arr[i];
sort(arr.begin(), arr.end());
int i, il, ir;
long long sum = 0;
for (i = il = ir = 0; i < n; i ++)
{
while (arr[ir] <= r + arr[i] && ir < n)
ir++;
while (arr[il] < l + arr[i] && il < n)
il++;
sum += ir - il;
}
cout << sum << endl;
return 0;
}Q3 难度⭐⭐⭐⭐
题目：
Eli最近迷上了汉诺塔。她玩了传统汉诺塔后突发奇想，发明了一种新的汉诺塔玩法。
有A、B、C三个柱子顺时针放置，移动的次序为A仅可以到B，B仅可以到C、C仅可以到A。即只可顺时针移动，不可逆时针移动。当然，汉诺塔的普适规则是适用的：每次移动后，大金片必须在小金片的下面。
现在A柱子上有𝑛 n 个金片。Eli想知道，她把这些全部移动到B或C，分别要多少次操作？
输入描述：一个正整数𝑛。(𝑛<107) (n<107)
输出描述：两个整数，分别代表A移到B和A移到C的最少操作数。由于该数可能过大，你需要对1000000007取模。
思路：
动态转移方程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[10000004][2];
int n;
int main()
{
cin>>n;
dp[1][0] = 1;dp[1][1] = 2;
dp[2][0] = 5;dp[2][1] = 7;
for(int i = 3; i <= n; ++i)
{
dp[i][0] = (1 + dp[i-1][1] * 2) % mod;
dp[i][1] = (2 + dp[i-1][1] * 2 + dp[i-1][0]) % mod;
}
cout<<dp[n][0]<<' '<<dp[n][1]<<endl;
return 0;
}
day2
Q1 难度⭐⭐
题目：
给你一个数组𝑎，请你求出数组a中任意两个元素间差的绝对值的最小值。
思路：
先排序，再判断最小差值（注意会爆INT）
class Solution
{
public:
int minDifference(vector<int>& a)
{
sort(a.begin(), a.end());
long long ans = 1e10;
for(int i = 1; i < a.size(); i ++)
ans = min(ans, (long long)a[i] - a[i-1]);
return ans;
}
};Q2 难度⭐⭐⭐⭐
E-kotori和素因子_北京信息科技大学第十一届程序设计竞赛（重现赛） (nowcoder.com)kotori和素因子_牛客题霸_牛客网 (nowcoder.com)E-kotori和素因子_北京信息科技大学第十一届程序设计竞赛（重现赛） (nowcoder.com)
题目：
kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。
她想知道，最终所有取出的数的和的最小值是多少？
注：若 a mod k==0，则称 k 是 a 的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数。
输入描述：第一行一个正整数 𝑛 ，代表kotori拿到正整数的个数。 第二行共有 𝑛 个数 𝑎𝑖，表示每个正整数的值。 保证不存在两个相等的正整数。 1≤𝑛≤10，2≤𝑎𝑖≤1000
输出描述：一个正整数，代表取出的素因子之和的最小值。若不存在合法的取法，则输出-1。
思路：
判断质数：质数、约数-CSDN博客
DFS：DFS与BFS-CSDN博客
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1010];
int ans=0x3f3f3f;
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
void dfs(int x,set<int> s,int temp)
{
if(x == n)
{
ans = min(ans, temp);
return;
}
for(int i = 2; i <= a[x]; i ++)
{
if(a[x] % i == 0 && is_prime(i) && !s.count(i))
{
s.insert(i);
dfs(x + 1, s, temp + i);
s.erase(i);
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
set<int> s;
dfs(0,s,0);
if(ans == 0x3f3f3f)
cout << -1;
else
cout << ans;
return 0;
}Q3 难度⭐⭐⭐⭐
题目：
大科学家dd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，dd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的dd开始着手修改白菜的基因序列，dd每次修改基因序列的任意位需要的代价是1，dd想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价的是多少。
输入描述：第一行一个正整数n(1≤n≤1000000)
第二行一个长度为n的字符串，表示所给白菜的基因序列
保证给出字符串中有且仅有大写英文字母
输出描述：输出一行，表示最小代价
思路：
创建新数组，根据s[i]是否非递减判断在新数组末尾或中间插入字符
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int f[N];
int main()
{
int n;
cin >> n;
string s;
cin >> s;
f[1] = s[0];
int len = 1;
for(int i = 1; i < n; i ++)
{
if(f[len] <= s[i])
f[++len] = s[i];
else
{
int l = 1, r = len;
while(l < r)
{
int mid = l + r >> 1;
if(s[i] < f[mid]) r = mid;
else l = mid + 1;
}
f[l] = s[i];
}
}
cout << n - len;
return 0;
}
day3
Q1 难度⭐
题目：
kanan唱歌经常高音上不去，为此她非常苦恼。
后来她发现了一个规律，一段连续的音符，只要后一个音比前一个音的高度差不大于8那么她就能唱上去。
但如果一个音过高，比前一个音高9以上，kanan就无法发出这个音了。
而低音则没有这个限制。如“1 5 10 1 2”她就能完整唱完，但“1 10 5 1 2”她就不能完整唱完。
现在有一段音符。她想截取其中一个连续的片段把它唱完。她想知道，这个片段长度的最大值是多少？
输入描述：第一行一个正整数n，代表音符的数量。 （1≤n≤200000）
第二行有n个正整数ai，代表每个音符的音高。（1≤ai≤100）
输出描述：一个正整数，代表连续片段长度的最大值。
思路：
遍历数组
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200004;
int a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
int ans = 1;
int len = 1;
for(int i = 1; i <n; i++)
{
if(a[i] - a[i-1] <= 8)
len++;
else
len = 1;
ans = max(len,ans);
}
cout << ans << endl;
return 0;
}Q2 难度⭐⭐⭐⭐
题目：
现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。
给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
注意：需保证所有方案的距离都是最短的方案
数据范围：2≤𝑛,𝑚≤10
思路：
动态转移方程：
class Solution
{
public:
int countPath(vector<vector<int> >& CityMap, int n, int m)
{
int x1, x2 ,y1, y2;
vector<vector<int>> dp(n, vector<int>(m, 0));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(CityMap[i][j] == 1)
{
x1 = i;
y1 = j;
}
if(CityMap[i][j] == 2)
{
x2 = i;
y2 = j;
}
}
}
int dx = x1 < x2 ? 1 : -1;
int dy = y1 < y2 ? 1 : -1;
dp[x1][y1] = 1;
for(int x = x1 + dx; x != x2 + dx; x += dx)
{
dp[x][y1] = CityMap[x][y1] != -1 ? dp[x-dx][y1] : 0;
if(dp[x-dx][y1] == 0)
dp[x][y1] = 1;
}
for(int y = y1 + dy; y != y2 + dy; y += dy)
{
dp[x1][y] = CityMap[x1][y] != -1 ? dp[x1][y-dy] : 0;
if(dp[x1][y-dy] == 0)
dp[x1][y] = 1;
}
for(int x = x1 + dx; x != x2 + dx; x += dx)
{
for(int y = y1 + dy; y != y2 + dy; y += dy)
{
dp[x][y] = CityMap[x][y] != -1 ? dp[x-dx][y] + dp[x][y-dy] : 0;
}
}
return dp[x2][y2];
}
};
Q3 难度⭐⭐⭐⭐
买卖股票的最好时机(四)_牛客题霸_牛客网 (nowcoder.com)
题目：
假设你有一个数组𝑝𝑟𝑖𝑐𝑒𝑠，长度为𝑛，其中𝑝𝑟𝑖𝑐𝑒𝑠[𝑖]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你最多可以对该股票有𝑘k笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费
数据范围:
1≤𝑝𝑟𝑖𝑐𝑒𝑠.𝑙𝑒𝑛𝑔𝑡ℎ≤1000
0≤𝑝𝑟𝑖𝑐𝑒𝑠[𝑖]≤1000
1≤𝑘≤100
输入描述：第一行输入一个正整数 n 和一个正整数 k。表示数组 prices 的长度和 交易笔数
第二行输入 n 个正整数表示数组的所有元素值。
输出描述：输出最大收益
思路：
状态转移方程：
dp[j][0] = max(dp[j-1][1] - v, dp[j][0])
dp[j][1] = max(dp[j][1], dp[j][0] + v)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<vector<int>> dp(k,vector<int>(2));
int v;
scanf("%d", &v);
for(int i = 0; i < k; ++i)
{
dp[i][0] = -v;
dp[i][1] = 0;
}
for(int i = 1; i < n; ++i)
{
scanf("%d", &v);
dp[0][0] = max(dp[0][0], -v);
dp[0][1] = max(dp[0][1], dp[0][0] + v);
for(int j = 1; j < k; ++j)
{
dp[j][0] = max(dp[j-1][1] - v, dp[j][0]);
dp[j][1] = max(dp[j][1], dp[j][0] + v);
}
}
cout << dp[k-1][1] << endl;
return 0;
}
day4
Q1 难度⭐
A-AOE还是单体？_牛客小白月赛25 (nowcoder.com)
题目：
牛可乐准备和 n 个怪物厮杀。已知第 i 个怪物的血量为 ai。
牛可乐有两个技能：
第一个技能是蛮牛冲撞，消耗 1 mp，可以对任意单体怪物造成 1 点伤害。
第二个技能是蛮牛践踏，消耗 x mp，可以对全体怪物造成 1 点伤害。
牛可乐想知道，将这些怪物全部击杀，消耗 mp 的最小值的多少？
输入描述：第一行两个正整数 n 和 x ，分别代表怪物的数量、每次蛮牛践踏消耗的 mp 值。
第二行 n 个正整数 ai，分别代表每个怪物的血量。
输出描述：一个正整数，代表消耗 mp 的最小值。
思路：
遍历数组并计算最小值
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n, x;
long long a[200010];
cin >> n >> x;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
long long ans = 0;
if (x >= n)
{
for (int i = 0; i < n; i++)
{
ans += a[i];
}
}
if (x < n)
{
long long t, sum = 0;
t = (n - x) * x;
for (int i = n - x; i < n; i++)
{
sum += a[i] - (n - x);
}
ans = sum + t;
}
cout << ans << endl;
}Q2 难度⭐⭐
题目：
kotori最近在研究n皇后的问题。
所谓n皇后问题是这样的：一个n*n的地图，上面一共放n个皇后，保证任意两个皇后都不能互相攻击（每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后）。
kotori思考了很久都无法得出答案，整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟，按照次序一共放了k个皇后。
但是，皇后的站位太复杂了，kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你，在第i个皇后放置在棋盘上之后，是否存在两个皇后可以互相攻击？
输入描述：第一行输入一个正整数k，代表总共放置的皇后的个数。（1<=k<=1e5）
接下来的k行，每行两个正整数xi和yi，代表每个皇后的坐标。（1<=xi,yi<=1e9）
之后输入一个正整数t，代表t次询问。（1<=t<=1e5）
接下来的t行，每行一个正整数i，代表询问第i个皇后放置后，是否存在互相攻击的情
况。（1<=i<=k）
保证不存在两个皇后放置的位置相同。
输出描述：共t行。每行对应当前的询问是否存在两个皇后可以互相攻击，
若是则输出“Yes”，否则输出“No”
思路：
DFS：DFS与BFS-CSDN博客
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
map<int, bool> a, b, c, r;
int main(void)
{
int k, x, y, t, idx = INF, i;
scanf("%d", &k);
for (i = 1; i <= k; i++)
{
scanf("%d%d", &x, &y);
if (idx != INF)
continue;
if (!a[x - y] && !b[x + y] && !c[x] && ! r[y])
a[x - y] = b[x + y] = c[x] = r[y] = 1;
else
idx = i;
}
scanf("%d", &t);
while (t--)
{
scanf("%d", &i);
if (i >= idx)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}Q3 难度⭐⭐⭐⭐
题目：
给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。
取位置 𝑖 的金币时，假设左边一堆金币数量是𝐿L，右边一堆金币数量为𝑅，则获得𝐿∗𝑐𝑜𝑠𝑡[𝑖]∗𝑅的积分。如果左边或右边没有金币，则金币数量视为1。
请你计算最多能得到多少积分。
数据范围：数组长度满足 1≤𝑛≤100 ，数组中的元素满足 1≤𝑐𝑜𝑖𝑛𝑠𝑖≤100
思路：
状态转移方程：
dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
class Solution
{
int arr[110] = {0};
int dp[110][110] = {0};
public:
int getCoins(vector<int>& coins)
{
int n = coins.size();
arr[0] = arr[n + 1] = 1;
for(int i = 1; i <= n; i ++)
arr[i] = coins[i - 1];
for(int i = n; i >= 1; i --)
for(int j = i; j <= n; j ++)
for(int k = i; k <= j; k ++)
dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
return dp[1][n];
}
};day5
Q1 难度⭐
题目：
KiKi有一个矩阵，他想知道转置后的矩阵（将矩阵的行列互换得到的新矩阵称为转置矩阵），请编程帮他解答。
输入描述：第一行包含两个整数n和m，表示一个矩阵包含n行m列，用空格分隔(1≤n≤10,1≤m≤10)
从2到n+1行，每行输入m个整数（范围-231~231-1），用空格分隔，
共输入n*m个数，表示第一个矩阵中的元素。
输出描述：输出m行n列，为矩阵转置后的结果。每个数后面有一个空格。
思路：
翻转输入输出
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int matrix[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> matrix[i][j];
for (int j = 0; j < m; j++)
{
for (int i = 0; i < n; i++)
cout << matrix[i][j] << " ";
cout << endl;
}
return 0;
}
Q2 难度⭐⭐⭐⭐
题目：
众所周知，高考数学中有一个题目是给出12个单项选择，每一个选择的答案是 A，B，C，D 中的一个。网上盛传答案存在某种规律，使得蒙对的可能性大大增加。于是今年老师想让你安排这12个题的答案。但是他有一些条件，首先四个选项的数量必须分别为 na，nb，nc，nd。其次有 m 个额外条件，分别给出两个数字 x，y，代表第 x 个题和第 y 个题的答案相同。 现在你的老师想知道，有多少种可行的方案安排答案。
输入描述：第一行五个非负整数na，nb，nc，nd，m，保证na+nb+nc+nd=12，0≤m≤1000。
接下来m行每行两个整数x，y（1≤ x,y ≤12）代表第x个题和第y个题答案必须一样。
输出描述：仅一行一个整数，代表可行的方案数。
思路：
并查集：并查集-CSDN博客
DFS：DFS与BFS-CSDN博客
#include <iostream>
#include <vector>
using namespace std;
int p[4];
int fa[20];
int t[20];
int ans = 0;
int findParent(int x)
{
if (fa[x] != x)
fa[x] = findParent(fa[x]);
return fa[x];
}
void dfs(int x)
{
if (x == 13)
{
ans++;
return;
}
if (t[x] == 0)
dfs(x + 1);
else
{
for (int i = 0; i < 4; i++)
if (t[x] <= p[i])
{
p[i] -= t[x];
dfs(x + 1);
p[i] += t[x];
}
}
}
int main()
{
for (int i = 1; i <= 12; i++)
fa[i] = i;
int m, x, y;
cin >> p[0] >> p[1] >> p[2] >> p[3] >> m;
for (int i = 1; i <= m; i++)
{
cin >> x >> y;
int fx = findParent(x), fy = findParent(y);
if (fx != fy)
fa[fx] = fy;
}
for (int i = 1; i <= 12; i++)
t[findParent(i)]++;
dfs(1);
cout << ans << endl;
return 0;
}Q3 难度⭐⭐⭐
题目：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路：
双指针
class Solution {
public:
int trap(vector<int>& height)
{
int ans = 0;
int l = 0, r = height.size() - 1;
int lMax = 0, rMax = 0;
while (l < r)
{
lMax = max(lMax, height[l]);
rMax = max(rMax, height[r]);
if (height[l] < height[r])
{
ans += lMax - height[l];
l ++;
}
else
{
ans += rMax - height[r];
r --;
}
}
return ans;
}
};day6
Q1 难度⭐
疯狂的自我检索者_牛客小白月赛25 (nowcoder.com)
题目：
牛妹作为偶像乐队的主唱，对自己的知名度很关心。她平时最爱做的事就是去搜索引擎搜自己的名字，看看别人对自己的评价怎么样。
这天，她打开了一个“偶像评分系统”，上面有很多人给她打分。
“偶像评分系统”的分数有1分、2分、3分、4分和5分。给牛妹评分的人有 n 个。但其中有 m 个人把分数隐藏了，牛妹并不能看到这些人给她打的分数。
牛妹想知道，已知这些信息的情况下，自己得到的平均分数的最大可能和最小可能分别是多少？
输入描述：第一行输入两个正整数 n 和m (1<m<n< 200000)
第二行输入 n- m 个正整数 a;，代表没有隐藏的分数。 (1≤ ai<5)
若m 和n 相等，则第二行为空。
输出描述：两个数，用空格隔开，分别代表最小可能平均分数和最大可能平均分数。如果你的输出
和正确答案之间误差不超过10^5，则认为你的答案正确。
思路：
隐藏的分数最低为m*1，最高为m*5
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> A(n-m);
for (auto &x: A)
cin >> x;
sort(A.begin(), A.end());
int sum = accumulate(A.begin(), A.end(), 0);
cout << (sum+m)*1./n << " ";
cout << (sum+5*m)*1./n << " ";
}Q2 难度⭐⭐⭐⭐
题目：
给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列
排列：指 1 到 n 每个数字出现且仅出现一次
数据范围： 1≤𝑛≤5×10^4，排列中的值都满足 1≤𝑣𝑎𝑙≤𝑛
思路：
一直入栈直到遇到n，出栈并将n-1
class Solution
{
public:
vector<int> solve(vector<int>& a)
{
int n = a.size();
vector<bool> mp(n + 1, false);
vector<int> ans;
stack<int> st;
for(auto i : a)
{
mp[i] = true;
st.push(i);
while(mp[n]) n--;
while(!st.empty() && st.top() > n)
{
ans.push_back(st.top());
st.pop();
}
}
return ans;
}
};
Q3 难度⭐⭐⭐⭐⭐
题目：
小红拿到了一个长度为 n 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 k 次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？
输入描述：第一行两个正整数 n 和 k
第二行有 n 个正整数 ai
1≤n≤10^5
1≤k≤10^12
1≤ai≤10^9
输出描述:不超过 k 次操作之后，数组中可能出现最多次数元素的次数。
思路：
![[C++进阶]继承](https://i-blog.csdnimg.cn/direct/76d319057c694f7ba1cb55549b76804b.png)
