链接：https://www.nowcoder.com/acm/contest/204/A
来源：牛客网
深度学习
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
Special Judge, 64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
Special Judge, 64bit IO Format: %lld
题目描述
小 A 最近在研究深度学习，他自己搭建了一个很牛逼的神经网络，现在他手头一共有 n 组训练数据，一开始他会给自己的神经网络设置一个 batch size，假设为 B (1≤ B≤ n) ，每次训练他都会从手头的 n 组训练数据中抽取不同的 B 组数据，然后扔到神经网络去训练。
然而小 A 的服务器并不是特别支持并行，所以运行时间和 B 成正比，每一次训练都会花费 B 秒的时间。
现在小 A 发现这样每次随机选数据的话，从概率上讲要训练好多次才能使得每组训练数据都被选中过。小 A 是一个炼丹的新手，他觉得只要所有训练数据都被选中过，那么这个模型就会很牛逼，所以只要某次训练后，如果所有训练数据都被选中过，那么他就会停止进行训练。
现在他想合理地设置 B ，使得训练总时间的期望值尽可能地短，你只需要求出这个最小的期望值。
然而小 A 的服务器并不是特别支持并行，所以运行时间和 B 成正比，每一次训练都会花费 B 秒的时间。
现在小 A 发现这样每次随机选数据的话，从概率上讲要训练好多次才能使得每组训练数据都被选中过。小 A 是一个炼丹的新手，他觉得只要所有训练数据都被选中过，那么这个模型就会很牛逼，所以只要某次训练后，如果所有训练数据都被选中过，那么他就会停止进行训练。
现在他想合理地设置 B ，使得训练总时间的期望值尽可能地短，你只需要求出这个最小的期望值。
输入描述:
第一行一个正整数 n
输出描述:
输出一个实数，表示最小的期望值，本题有spj，只要和标准答案的标准误差在 10-3 以内就算正确
备注:
1≤ n ≤ 40 思路：浪费时间的总和是大于等于n的，所以求的最小的就是n。
#include<bits/stdc++.h>
using namespace std; int main()
{
double n;
scanf("%lf",&n);
printf("%.6f\n",n);
return ;
}
链接：https://www.nowcoder.com/acm/contest/204/D
来源：牛客网
最小生成树
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
思路：把n-1个点都和根结点相连，求出n-1条边的总和即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
ll a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+,a+n+);
ll sum=;
for(int i=;i<=n;i++)
{
sum+=a[]+a[i];
}
printf("%lld\n",sum);
return ;
}
链接：https://www.nowcoder.com/acm/contest/204/G
来源：牛客网
区间权值
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
小 Bo 有 n 个正整数 a1..an，以及一个权值序列 w1…wn，现在他定义 
现在他想知道
的值，需要你来帮帮他
你只需要输出答案对 109+7 取模后的值
现在他想知道
的值，需要你来帮帮他你只需要输出答案对 109+7 取模后的值
输入描述:
第一行一个正整数 n
第二行 n 个正整数 a
1
..a
n
第三行 n 个正整数 w
1
..w
n
输出描述:
输出答案对 10
9
+7 取模后的值
备注:
1≤ n≤ 3x 10
5
1≤ a
i
≤ 10
7
1≤ w
i
≤ 10
7
思路：前缀和。有对称性。把式子展开找出w1~wn的各个和ai的乘积和。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+;
const int mod=1e9+;
int n,pnt;
ll a[maxn],w[maxn],suma[maxn],sumb[maxn];
ll sumc[maxn];
int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%lld",&a[i]);
suma[i]=suma[i-]+a[i];
suma[i]%=mod;
}
for(int i=; i<=n; i++)
scanf("%lld",&w[i]);
sumb[]=suma[n];
for(int i=; i<=n; i++)
{
if(n-i+>i-)
{
sumb[i]=sumb[i-]+(suma[n-i+]-suma[i-]);
sumb[i]%=mod;
}
else
{
pnt=i-;
break;
}
}
sumb[n]=suma[n];
for(int i=n-; i>=pnt+; i--)
{
sumb[i]=sumb[n-i+];
}
ll ans=;
for(int i=; i<=n; i++)
{
ans+=(sumb[i]%mod*w[i]%mod)%mod;
ans%=mod;
}
ans%=mod;
printf("%lld\n",ans);
return ;
}
链接：https://www.nowcoder.com/acm/contest/204/I
来源：牛客网
连通块计数
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
思路：分为两部分：含有根结点+不含根结点的各个部分和。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
ll a[maxn];
ll b[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i]+;
}
sort(b+,b+n+);
ll he=;
for(int i=;i<=n;i++)
{
he=(he*b[i])%;
}
for(int i=;i<=n;i++)
{
he=(he+(a[i]*(a[i]+)/%()))%;
}
printf("%lld\n",he);
return ;
}
链接：https://www.nowcoder.com/acm/contest/204/J
来源：牛客网
寻找复读机
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
某个 QQ 群里一共有 n 个人，他们的编号是 1..n，其中有一些人本质上是复读机。
小 A 发现，如果一个人的本质是复读机，那么他每次发的消息一定跟群里的上一条消息一样，特别地第一个发消息的人一定不是复读机。
现在小 A 搞到了一份聊天记录，他想请你找出所有可能是复读机的群友
小 A 发现，如果一个人的本质是复读机，那么他每次发的消息一定跟群里的上一条消息一样，特别地第一个发消息的人一定不是复读机。
现在小 A 搞到了一份聊天记录，他想请你找出所有可能是复读机的群友
输入描述:
第一行两个正整数 n,m，表示群里的人数和聊天记录的总条数
接下来 m 行按时间顺序给出聊天记录，每行有一个正整数 x 和一个小写字母字符串 S，表示群友 x 发了消息 S
输出描述:
输出一行，将所有可能是复读机的群友的编号按照从小到大排序后输出，每两个编号之间隔一个空格
备注:
1≤ n≤ 10
3
1≤ m≤ 10
3
1≤ |S|≤ 100 思路：用map，strcpy,strcmp，然后找谁不是复读机，输出是复读机的即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
map <int ,int> a;
char s[],tmp[];
int x;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
scanf("%d %s",&x,&s);
a[x]=;
strcpy(tmp,s);
for(int i=;i<=m;i++)
{
scanf("%d %s",&x,&s);
if(strcmp(s,tmp)!=)
{
a[x]=;
}
strcpy(tmp,s);
}
for(int i=;i<=n;i++)
{
if(a[i]==)
{
printf("%d ",i);
}
}
return ;
}
链接：https://www.nowcoder.com/acm/contest/204/H
来源：牛客网
树链博弈
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
给定一棵 n 个点的树，其中 1 号结点是根，每个结点要么是黑色要么是白色
现在小 Bo 和小 Biao 要进行博弈，他们两轮流操作，每次选择一个黑色的结点将它变白，之后可以选择任意多个(可以不选)该点的祖先(不包含自己)，然后将这些点的颜色翻转，不能进行操作的人输
由于小 Bo 猜拳经常输给小 Biao，他想在这个游戏上扳回一城，现在他想问你给定了一个初始局面，是先手必胜还是后手必胜
现在小 Bo 和小 Biao 要进行博弈，他们两轮流操作，每次选择一个黑色的结点将它变白，之后可以选择任意多个(可以不选)该点的祖先(不包含自己)，然后将这些点的颜色翻转，不能进行操作的人输
由于小 Bo 猜拳经常输给小 Biao，他想在这个游戏上扳回一城，现在他想问你给定了一个初始局面，是先手必胜还是后手必胜
输入描述:
第一行一个正整数 n
第二行 n 个整数 w
1
..w
n
，w
i
∈ {0,1}，w
i
=1 表示第 i 个结点一开始是黑点，否则是白点
接下来 n-1 行，每行两个正整数 u,v 表示一条树边 (u,v)
输出描述:
如果先手必胜，输出First ，否则输出Second
备注:
1≤ n≤ 1000 思路：DFS找出每一个点所在的层数，若果每一层的黑色为偶数则输出“Second”。
代码：
#include <bits/stdc++.h>
using namespace std;
const int Max = 3e6+;
vector <int> ma[Max];
int du[Max],deep[Max];
bool visited[Max];
int color[Max];
int n;
#define rep(i,s,n) for(int i=s;i<=n;i++)
#define per(i,n,s) for(int i=n;i>=s;i--) void DFS(int u, int dp){
deep[u]=dp;
visited[u]=true;
int len=ma[u].size();
rep(i,,len-){
int to=ma[u][i];
if(!visited[to]){
DFS(to,++dp);
dp--;
}
}
} int main(){
scanf("%d",&n);
rep(i,,n){
scanf("%d",&color[i]);
}
int u,v;
rep(i,,n-){
scanf("%d %d",&u,&v);
ma[u].push_back(v);
ma[v].push_back(u);
}
DFS(,);
bool ok=;
rep(i,,n){
if(color[i]){
du[deep[i]]++;
}
}
rep(i,,n){
if(du[i]%==){
ok=;
break;
}
}
if(ok){
printf("Second\n");
}
else{
printf("First\n");
}
return ;
}