牛客网OJ题解--20210228
B-苦逼的单身狗
https://ac.nowcoder.com/acm/problem/14547
本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。
NC14547-苦逼的单身狗
题目链接
https://ac.nowcoder.com/acm/problem/14547
题目描述
双11又到了，小Z依然只是一只单身狗，对此他是如此的苦恼又无可奈何。 为了在这一天脱单小Z决定向女神表白，但性格腼腆的小Z决定隐晦一点，截取一段包含'L'、'O'、'V'、'E'的英文。（顺序不限）。小Z想起之前小D送给他一本英文书，决定在这里面截取一段话，小Z发现有好多种方案来截取这段话。 你能知道小Z能有多少种方案截取这段话么？ 为了简化问题，英文文本讲不会出现空格、换行、标点符号及只有大写的情况。
本题有T组数据。对于每组数据只有一行文本。1≤T≤20，1≤文本长度≤100000。
测试样例
输入
3 ILOVEACM LOVELOVE ALBECVOD
输出
8 15 4
解题思路
我们以LOVELOVE为例分析一下，每次我们都找到含有LOVE（顺序随意）的子串，然后记录这四个字符最早出现的位置，然后左边的字符数+1就包含这个子串的所有情况。比如现在从i=1开始向右查找。
- i=0(L),i=1(O),i=2(V),i=3(E),那么最早出现的位置是i=0,左边无字符，所以字符数是0，那么包含这个子串的情况就是有一种即子串自身LOVE
- i=1(O),i=2(V),i=3(E),i=4(L),那么最早出现的位置是i=1，左边有一个字符L，所以字符数是1，那么包含这个子串的情况就有2种即LOVEL和OVEL
- i=2(V),i=3(E),i=4(L),i=5(O),那么最早出现的位置是i=2，左边有两个字符L,O，所以字符数是2，那么包含这个子串的情况3种即LOVELO，OVELO和VELO
依次类推，所以我们就找到了规律，即每次获取刚好出现LOVE的子串，然后比较获得四个字符最先出现的位置，查看左边的字符数即可。
解题代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
//记录四个字符出现的坐标
int l = -1, o = -1, v = -1, e = -1;
long long ans = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == 'L')
l = i;
else if (s[i] == 'O')
o = i;
else if (s[i] == 'V')
v = i;
else if (s[i] == 'E')
e = i;
//取一个含有字符串的love的子串并且比较四个坐标取最小值
int cnt = min(min(l, o), min(v, e));
if (cnt != -1)
{
//包含本次子串的情况数量为左边的字符数+1
ans += cnt + 1;
}
}
cout << ans << endl;
}
system("pause");
return 0;
} NC14545-B-经商
题目链接
https://ac.nowcoder.com/acm/problem/14545
题目描述
小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。 小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。 小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。小d想知道，他在精力范围内，能够获得的利益值到底是多少。 设定小d自己的编号为1.并且对应一个人的交际次数限定为1。
本题包含多组输入，第一行输入一个数t，表示测试数据的组数
每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值
接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。
再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai，bi<=10
1<=C<=500
1<=x,y<=N
测试样例
输入
1 5 3 7 5 10 3 2 4 3 1 100 1 2 2 3 1 4
输出
10
解题思路
这是一道并查集+0/1背包dp题，可以参考学习笔记《浅谈用一维数组dp解决0/1背包问题》和《浅谈并查集解决分组问题》。这里就是纯板子题，但是一定要注意读懂题干，是要求只有两个人有直接关系或者间接关系才可以认识，例如样例1中的1和5是不能认识的，虽然给出了1认识5的精力消耗和收益，但是由于1和5没有直接关系并且1也不能通过该其他人认识5。所以这道题就是先试用并查集建立分组关系网，然后使用0/1背包dp解决。
解题代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define close_stdin ios::sync_with_stdio(false)
int n, m, c;
const int maxn = 10005;
int a[maxn], b[maxn];
int fa[maxn];
int dp[505];
int find(int x)
{
//寻找最深层祖先，同时压缩更新x的祖先为最深层祖先
return (fa[x] == x ? x : fa[x] = find(fa[x]));
}
void merge(int x, int y)
{
//x的最深层祖先的祖先更新为y，这样x和y就有关系了，同时y会成为更深层的根本祖先
if (find(x) != find(y))
fa[find(x)] = find(y);
}
void my_input()
{
cin >> n >> m >> c;
for (int i = 2; i <= n; i++)
{
cin >> a[i] >> b[i];
}
}
void solve()
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
//初始时默认是独立节点，无祖先，所以各节点无关系
fa[i] = i;
}
while (m--)
{
int x, y;
cin >> x >> y;
//x和y建立关系同时默认y是更深层的祖先
//所以此时fa[x]=y即x的最根本祖先是y
//同时fa[find(X)]=y即x的祖先的最根本祖先也会是y
merge(x, y);
}
//关系网建立完成后进行0/1dp
for (int i = 2; i <= n; i++)
{
//讨论每一个对于1~i每一个节点是否放入
//首先需要满足有关系才可以认识
//一定要注意例如样例1中1和5就不能认识，因为他们没有共同认识的人且两者也不认识
if (find(i) == find(1))
{
//能够认识，讨论是否认识
for (int j = c; j >= a[i]; j--)
{
//板子
dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
}
}
}
cout << dp[c] << endl;
}
int main()
{
close_stdin;
int t;
cin >> t;
while (t--)
{
my_input();
solve();
}
system("pause");
return 0;
} 