Cidoai的平均数对
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, k;cin >> n >> k;int totalAns = 0;int rSum = 0;vector<int> ex, weights;for (int i = 0; i < n; ++i) {int a, b;std::cin >> a >> b;if (b <= k) {totalAns += a;rSum += k - b;} else {ex.push_back(b - k);weights.push_back(a);}}vector<int> f(rSum + 1, 0);for (int i = 0; i < ex.size(); ++i) {for (int j = rSum; j >= ex[i]; --j) {f[j] = std::max(f[j], f[j - ex[i]] + weights[i]);}}cout << f[rSum] + totalAns;return 0;
}
代码思路
一、整体思路
-
输入部分:通过
cin >> n >> k;
读取输入的整数n
和k
,分别表示对数的数量和参数k
的值。接着使用一个循环读取n
对数(a_i, b_i)
。 -
计算部分:遍历每一对数,如果
b_i
小于等于k
,则将a_i
累加到totalAns
中,并将k - b_i
累加到rSum
中。如果b_i
大于k
,则将b_i - k
存入ex
向量中,将a_i
存入weights
向量中。 -
动态规划部分:创建一个长度为
rSum + 1
的向量f
,并初始化为全零。使用两层循环进行动态规划,外层循环遍历ex
向量,内层循环从rSum
到当前的ex[i]
进行逆序遍历。在每次循环中,更新f[j]
为f[j]
和f[j - ex[i]] + weights[i]
的较大值。 -
输出部分:最后输出
f[rSum] + totalAns
,即满足条件的a_i
的最大和。
二、原理分析
-
问题理解:问题要求在给定的
n
对数中选出一些对,使得这些对中b_i
的平均值不超过k
,同时a_i
的和最大。 -
处理特殊情况:对于那些
b_i
已经小于等于k
的对数,直接将它们的a_i
累加到totalAns
中,因为这些对数已经满足条件,无需进一步处理。 -
动态规划求解:对于那些
b_i
大于k
的对数,使用动态规划来求解。将问题转化为一个背包问题,背包的容量为rSum
(即超出k
的部分的总和),物品的重量为ex[i]
(即每个超出k
的b_i
减去k
的值),物品的价值为weights[i]
(即对应的a_i
)。通过动态规划求解在不超过背包容量的情况下,能获得的最大价值,即这些对数中a_i
的最大和。 -
最终结果:最终的结果是已经满足条件的对数的
a_i
之和totalAns
加上通过动态规划求解得到的超出部分的最大a_i
之和f[rSum]
。
Cidoai的树上方案
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码
#include <iostream>
#include <vector>const int mod = 998244353;using namespace std;void dfs(int u, const vector<vector<int>>& adj, vector<vector<int>>& f) {f[u][0] = f[u][1] = 1;for (int v : adj[u]) {dfs(v, adj, f);f[u][0] = (1LL * f[u][0] * ((f[v][0] + f[v][1]) % mod)) % mod;f[u][1] = (1LL * f[u][1] * f[v][0]) % mod;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<vector<int>> adj(n + 1);vector<vector<int>> f(n + 1, vector<int>(2));for (int i = 2, p; i <= n; ++i) {cin >> p;adj[p].push_back(i);}dfs(1, adj, f);cout << (f[1][0] + f[1][1]) % mod;return 0;
}
代码思路
一、整体思路
该代码的目的是解决在给定的有根树中,从树外引入一个点向树内任意连边,使得构成的简单图不含三元环的方案数问题。通过深度优先搜索(DFS)遍历树,并使用动态规划的思想计算每个节点的两种状态的方案数,最终得到根节点的总方案数。
二、具体步骤
-
输入部分:通过
cin >> n;
读取树的节点数量n
。使用一个循环读取每个节点的父亲节点编号,构建树的邻接表adj
。 -
准备工作:创建两个二维向量
adj
和f
,adj
用于存储树的邻接关系,f
用于存储每个节点的两种状态的方案数(f[u][0]
表示不与子节点相连的方案数,f[u][1]
表示与子节点相连的方案数)。 -
深度优先搜索(DFS)
dfs
函数用于遍历树,计算每个节点的方案数。- 对于每个节点
u
,初始时f[u][0] = f[u][1] = 1
,表示当前节点自身的两种初始状态都有 1 种方案。 - 对于每个子节点
v
,递归调用dfs(v, adj, f)
计算子节点的方案数。 - 然后根据子节点的方案数更新当前节点的方案数。
f[u][0] = (1LL * f[u][0] * ((f[v][0] + f[v][1]) % mod)) % mod;
表示当前节点不与子节点相连时,方案数为自身不相连的方案数乘以子节点不相连和相连的方案数之和,再取模。f[u][1] = (1LL * f[u][1] * f[v][0]) % mod;
表示当前节点与子节点相连时,方案数为自身相连的方案数乘以子节点不相连的方案数,再取模。
-
输出结果:在
main
函数中,调用dfs(1, adj, f)
从根节点开始进行深度优先搜索,计算所有节点的方案数。最后,输出根节点的总方案数(f[1][0] + f[1][1]) % mod
。
三、原理分析
- 通过 DFS 遍历树,可以确保每个节点的方案数都能根据其子节点的方案数正确计算。
- 动态规划的状态定义和转移方程能够准确地计算出每个节点在不同状态下的方案数,从而最终得到根节点的总方案数。
- 取模操作
% mod
是为了保证结果在规定的模数范围内,避免数值过大。
Cidoai的字符集合
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码
#include<iostream>
#define int long long
#define endl '\n';
using namespace std;
const int N=1e6+10;
bool he[N];
void solve(){map<string,int>xx;int n;cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;for(int j=1;j<=k;j++){string p;cin>>p;if(xx[p]==0||xx[p]==i){xx[p]=i;}else {he[i]=1;he[xx[p]]=1;}}}int sum=1;for(int i=1;i<=n;i++){if(!he[i])sum++;}if(sum>n)sum=n;cout<<sum;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--){solve();}
}
代码思路
一、整体思路
- 首先读取输入的歌曲数量
n
。 - 对于每一首歌曲,读取其旋律长度
k
和各个旋律字符串。将旋律字符串作为键,歌曲编号作为值存入map<string, int> xx
中。如果当前旋律字符串已经在xx
中且值为当前歌曲编号或者为初始值0
,则更新其值为当前歌曲编号;如果当前旋律字符串在xx
中且值不为当前歌曲编号,说明找到了两首有相同旋律的歌曲,将这两首歌曲对应的标记位he[i]
和he[xx[p]]
置为1
。 - 遍历所有歌曲,统计标记位为
0
的歌曲数量,即没有与其他歌曲有相同旋律的歌曲数量,记为sum
。如果sum
大于歌曲总数n
,则sum
更新为n
。 - 最后输出
sum
,即最少可以划分成的集合数量。
二、关键步骤原理
-
使用
map<string, int> xx
:map
是一种关联容器,它以键值对的形式存储数据。在这里,键是旋律字符串,值是歌曲编号。通过这种方式,可以快速查找某个旋律是否已经出现过,以及是在哪一首歌曲中出现的。- 当遍历一首歌曲的旋律时,如果某个旋律字符串已经在
map
中,并且值与当前歌曲编号相同或者为初始值0
,说明这个旋律是首次在当前歌曲中出现或者之前也在当前歌曲中出现过,此时更新xx[p]
为当前歌曲编号。如果值不为当前歌曲编号,说明这个旋律在另一首歌曲中也出现过,找到了相似的两首歌曲,将它们的标记位置为1
。
-
标记位
he[i]
:- 定义了一个布尔型数组
he[N]
,用于标记每一首歌曲是否与其他歌曲有相同的旋律。当找到两首有相同旋律的歌曲时,将它们对应的标记位置为1
。 - 最后遍历这个标记数组,统计标记位为
0
的歌曲数量,这些歌曲是没有与其他歌曲有相同旋律的,可以单独作为一个集合。而有相同旋律的歌曲会被归为一个集合。
- 定义了一个布尔型数组
-
sum
的计算:sum
初始值为1
,表示至少有一个集合。在遍历歌曲过程中,每找到一首没有与其他歌曲有相同旋律的歌曲,就将sum
加一。- 最后,如果
sum
大于歌曲总数n
,说明所有歌曲都有相同旋律,此时将sum
更新为n
,即所有歌曲都在一个集合中。