长沙理工新生赛
A
链接：
https://ac.nowcoder.com/acm/contest/3530/A
题目描述
众所周知，常守朱是一个优秀的执行官，她凭借自身的卓越能力解决了许多案件，当然她手中的支配者也为办案提供了很大的便利，支配者可以测量一个人的犯罪指数，当超过一定值时，则被认为是罪犯。
支配者的工作原理如下：将一个人的脑电波转化为01串（我瞎编的），01串中1的个数越多，则犯罪指数越高，下面给你一个01串，请你统计该串中1的个数
输入描述:
一个字符串s，字符串的长度小于1e5输出描述:
一个整数，字符串中1的个数示例1
输入
0101输出
2AC——遍历string
#include<string>
#include<iostream>
#include<cstdlib>
using namespace std;
int n;
int num;
string a;
int main()
{
cin>>a;
num = 0;
for(int i=0;i<a.length();++i)
{
if(a[i]=='1')
num++;
}
cout<<num<<endl;
return 0;
}E
链接：
https://ac.nowcoder.com/acm/contest/3530/E
来源：牛客网
题目描述
众所周知，佳爷是集训队最强，他经常喜欢鄙视集训队最菜的PC，这天他又来了，他丢给PC一道题目：
给你一个字符串，该字符串只包含符号 ‘(’ 和 ‘)’, ，我们称那些左右括号可以一一对应的括号字符串为完美字符串，
比如”()()()”, “((()))”, “((()))()()”, 都是完美字符串
而”((())”, “()(“, “((()))()(“ 不是完美字符串。
这么难的题目，PC当然是不会写的，但他又不想被佳爷鄙视，所以他找到了你，聪明的ACMer啊，请你帮PC解出这题把
输入描述:
第一行一个整数n，代表字符串的长度 n， 1 <= n <= 1e5
第二行一串字符串s，只包含字符 '(' , ')'。输出描述:
如果该字符串是完美字符串，就输出YES，。否则输出NO示例1
输入
4
(())输出
YESAC——栈的简单应用
#include<iostream>
#include<stack>
#include<cstdlib>
#include<string>
using namespace std;
string a;
int n;
int main()
{
cin>>n;
cin>>a;
stack<char> s1;
stack<char> s2;
for(int i=0;i<n;++i)
{
if(s1.empty())
s1.push(a[i]);
else if(a[i]==')'&&s1.top()=='('&&!s1.empty())
{
s1.pop();
}
else
{
s1.push(a[i]);
}
}
if(s1.empty())
cout<<"YES"<<endl;
else
{
cout<<"NO"<<endl;
}
system("pause");
return 0;
}F
链接：
https://ac.nowcoder.com/acm/contest/3530/F
来源：牛客网
题目描述
——你要是愿意，我就永远存在
某人的朋友圈实在是过于庞大且复杂，要判断两个人是不是朋友，那还真不容易。
现给出某个朋友圈关系图，求任意给出的两个人是否是朋友。
规定：如果x和y是朋友，y和z是朋友，那么x和z也是朋友。
如果x和y是朋友，那么x的朋友都是y的朋友，y的朋友也都是x的朋友。
输入描述:
第一行，三个整数n,m,p,(n ≤ 50000,m ≤ 50000,p≤50000)，分别表示有n个人，m个朋友关系，询问p对朋友关系。
以下m行：每行两个数Mi, Mj，1 ≤ Mi, Mj ≤ n，表示Mi和Mj具有朋友关系。
接下来p行：每行两个数Pi ,Pj,询问Pi，Pj是否具有盆友关系输出描述:
P行，每行一个“Yes”或“No”(不包含引号)。表示第i个询问的答案为“具有”或“不具有”朋友关系。示例1
输入
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6输出
Yes
Yes
NoAC ——赤果果的并查集
#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
int pre[500001];
int n,m,p;
int find(int x)
{
if(pre[x]==x)
{
return x;
}
else
{
return pre[x] = find(pre[x]);
}
}
void join(int x,int y)
{
int fx = find(x);
int fy = find(y);
if(x!=fy)
{
pre[fx] = fy;
}
}
int main()
{
cin>>n;
cin>>m;
cin>>p;
for(int i =1;i<=n;++i)
{
pre[i] = i;
}
for(int i =1;i<=m;++i)
{
int x,y;
cin>>x>>y;
join(x,y);
}
for(int i =1;i<=p;++i)
{
int x,y;
cin>>x>>y;
int dx = find(x);
int dy = find(y);
if(dy==dx)
cout<<"Yes"<<endl;
if(dy!=dx)
cout<<"No"<<endl;
}
system("pause");
return 0;
}C
链接：
https://ac.nowcoder.com/acm/contest/3530/C
来源：牛客网
题目描述
咚咚咚！在安静的7教417夜晚，车神带来了一堆神秘的数字。
而417的小伙伴都只钟爱于包含4和7的数字。
例如数字：747,4,7747,4,7是他们钟爱的数字，而476,5,27476,5,27不是。
车神灵机一动，突然问：对于给定的数字n，能否找出各个数位上数字和为n的最小钟爱数字。
如果找到则输出这个最小数, 如果找不到，则输出“YingYingYing”。
输入描述:
一行，一个整数n(1 ≤ n ≤ 1e6) 代表要求车牌号的各个数位上数字的和输出描述:
输出仅一行，为满足条件的最小车牌号，如果不存在这个车牌号就输出“YingYingYing”。示例1
输入
11输出
47示例2
输入
10输出
YingYingYingAC——思维
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a,b;
for(a=0;a*4<=n;++a)
{
for(b=0;a*4+b*7<=n;++b)
{
if(a*4+b*7==n)
break;
}
if(a*4+b*7==n)
break;
}
if(a*4+b*7!=n)
cout<<"YingYingYing"<<endl;
else
{
for(int i=0;i<a;++i)
{
cout<<4;
}
for(int i=0;i<b;++i)
{
cout<<7;
}
}
system("pause");
return 0;
}B
链接：
https://ac.nowcoder.com/acm/contest/3530/B
来源：牛客网
题目描述
给你n个人，每一个人最多可以选k张牌，这n个人都喜欢数s，一张牌有一个数，如果这个数是s，则这个牌称为happy card
每一个人拿到不同数量的happy card 可以获得不同数量的欢乐值。
假如一个人拿到了 i 张happy card ，则可以获得 hi 的欢乐值( hi 数组单调递增)， 没有happy card的人的欢乐值为0.
如果没有拿到happy card，则获得的欢乐值为0。
现在你需要把着n张牌分配给这n个人（每个人的牌数都可以为0），使这n个人的快乐值总和最大
输入描述:
第一行三个数字n,k,s, 1 <= n <= 500, 1<= k <= n , 1 <= s <= 1e9接下来n个数代表n张牌上的数ai， 1 <= ai <= 1e9接下来k个数代表hi的值,1 <= hi <= 1e9保证 hi-1 <= hi输出描述:
最大的快乐值和示例1
输入
5 3 2
2 2 2 2 2
2 6 7输出
14示例2
输入
4 3 9
9 9 9 9
1 2 3输出
4AC——DP/01背包？
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,s;
int h[1000];
ll f[1000];
int main() {
cin>>n>>k>>s;
int sum=0;
for(int i=1,x;i=<n;i++)
{
cin>>x
if(x==s)
sum++;
}
for(int i=1;i<=k;i++)
cin>>h[i];
for(int i=1;i<=k;i++)
{
for(int j=i;j<=sum;j++)
{
f[j]=max(f[j],f[j-i]+h[i]);
}
}
printf("%lld\n",f[sum]);
system("pause");
return 0;
}腾讯云开发者
