牛客国庆集训派对Day_4~6

Day_4

A.深度学习

题目描述

小 A 最近在研究深度学习，他自己搭建了一个很牛逼的神经网络，现在他手头一共有 n 组训练数据，一开始他会给自己的神经网络设置一个 batch size，假设为 B (1≤ B≤ n) ，每次训练他都会从手头的 n 组训练数据中抽取不同的 B 组数据，然后扔到神经网络去训练。
然而小 A 的服务器并不是特别支持并行，所以运行时间和 B 成正比，每一次训练都会花费 B 秒的时间。
现在小 A 发现这样每次随机选数据的话，从概率上讲要训练好多次才能使得每组训练数据都被选中过。小 A 是一个炼丹的新手，他觉得只要所有训练数据都被选中过，那么这个模型就会很牛逼，所以只要某次训练后，如果所有训练数据都被选中过，那么他就会停止进行训练。
现在他想合理地设置 B ，使得训练总时间的期望值尽可能地短，你只需要求出这个最小的期望值。

输入描述:

第一行一个正整数 n

输出描述:

输出一个实数，表示最小的期望值，本题有spj，只要和标准答案的标准误差在 10^-3 以内就算正确

示例1

输入

1

输出

1.000000

备注:

1≤ n ≤ 40
解题思路：要使得期望值最小，那么B应该设置成n并且一次训练后所有训练数据都被选中，即最小的期望值为n。
AC代码：

#include<bits/stdc++.h>
using namespace std;
double n;
int main(){
    while(cin>>n){
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<n<<endl;
    }
    return 0;
}

D.最小生成树

题目描述

小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 a_i，之后这张无向图是一张完全图，且边 (u,v) 的权值为 a_u+a_v
现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他

输入描述:

第一行一个正整数 n
第二行 n 个整数 a1,a2 … an

输出描述:

输出边权和最小的生成树的边权之和

示例1

输入

3
1 2 3

输出

7

备注:

1≤ n≤ 10^5

0≤ a_i ≤ 10^9
解题思路：找带权值最小的点分别和其他n-1个点进行连线，即可组成最小生成树。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;LL n,sum,a[maxn];
int main(){
    while(cin>>n){
        sum=0;
        for(LL i=0;i<n;++i)cin>>a[i],sum+=a[i];
        sort(a,a+n);sum-=a[0];sum+=a[0]*(n-1);
        cout<<sum<<endl;
    }
    return 0;
}

G.区间权值

题目描述

小 Bo 有 n 个正整数 a₁..a_n，以及一个权值序列 w₁…w_n，现在他定义$ f (l, r) = ( sum_{i=l}^r a_i ) × w_{r - l + 1} $ 
现在他想知道$ sum_{l = 1}^n sum_{r = l}^n f(l, r) $ 的值，需要你来帮帮他
你只需要输出答案对 10⁹+7 取模后的值

输入描述:

第一行一个正整数 n
第二行 n 个正整数 a1..an

第三行 n 个正整数 w1..wn

输出描述:

输出答案对 10^9+7 取模后的值

示例1

输入

3
1 1 1
1 1 1

输出

10

备注:

1≤ n≤ 3e5

1≤ a_i ≤ 10^7

1≤ w_i ≤ 10^7
解题思路：手推构造两个前缀和数组，即可得到答案。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int maxn=3e5+5;int n;
LL ans,a[maxn],w[maxn],sum[maxn],tot[maxn];
int main(){
    while(cin>>n){
        sum[0]=tot[0]=ans=0;
        for(int i=1;i<=n;++i)cin>>a[i],sum[i]=sum[i-1]+a[i],tot[i]=(tot[i-1]+sum[i])%mod;
        for(int i=1;i<=n;++i)cin>>w[i];
        for(int i=1;i<=n;++i)
            ans=(ans+(tot[n]-tot[n-i]-tot[i-1])*w[i]%mod+mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

 I.连通块计数

题目描述

小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i 条链有 a_i 个点，每一条链的一端都与根结点相连。
现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可

输入描述:

第一行一个正整数 n
第二行 n 个正整数 a1 … an

输出描述:

输出答案对 998244353 取模后的值

示例1

输入

2
1 1

输出

6

备注:

1≤ n≤ 10^5

1≤ a_i ≤ 10^7
解题思路：
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
LL n,ans,res,tp;
int main(){
    while(cin>>n){
        ans=0;res=1;
        while(n--){
            cin>>tp;
            res=(res*(tp+1))%mod;
            ans=(ans+tp*(tp+1)/2)%mod;
        }
        cout<<(ans+res)%mod<<endl;
    }
    return 0;
}

J.寻找复读机

题目描述

某个 QQ 群里一共有 n 个人，他们的编号是 1..n，其中有一些人本质上是复读机。
小 A 发现，如果一个人的本质是复读机，那么他每次发的消息一定跟群里的上一条消息一样，特别地第一个发消息的人一定不是复读机。
现在小 A 搞到了一份聊天记录，他想请你找出所有可能是复读机的群友

输入描述:

第一行两个正整数 n,m，表示群里的人数和聊天记录的总条数
接下来 m 行按时间顺序给出聊天记录，每行有一个正整数 x 和一个小写字母字符串 S，表示群友 x 发了消息 S

输出描述:

输出一行，将所有可能是复读机的群友的编号按照从小到大排序后输出，每两个编号之间隔一个空格

示例1

输入

3 5
1 gugugu
2 gugugu
1 gugu
3 tingzhifudu
2 tingzhifudu

输出

2

备注:

1≤ n≤ 10^3

1≤ m≤ 10^3

1≤ |S|≤ 100
解题思路：因为是不容易找哪个是复读机（可能没发言的也是复读机），所以我们找不是复读机的群友--->不和群里上一条消息一样的人一定不是复读机，因此标记一下这些人，最后再按顺序输出是复读机的编号即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,st,cnt,ans[1005];string str,tmp;bool flag[1005];
int main(){
    while(cin>>n>>m){
        cin>>x>>str;st=x,cnt=0;memset(flag,false,sizeof(flag));flag[x]=true;
        while(--m){
            cin>>y>>tmp;
            if(tmp!=str)flag[y]=true;
            x=y,str=tmp;
        }
        for(int i=1;i<=n;++i)
            if(!flag[i])ans[cnt++]=i;
        for(int i=0;i<cnt;++i)
            cout<<ans[i]<<(i==cnt-1?'
':' ');
    }
    return 0;
}

 Day_5

G.贵族用户

题目描述

终于活成了自己讨厌的样子。
充钱能让你变得更强。
在暖婊这个游戏里面，如果你充了x元钱，那么你能获得10x个钻石。同时暖婊也有m档VIP，如果你往暖婊里面充了a_i个钻石，那么你能成为第i档贵族用户。当你成为第i档贵族用户之后，那么你可以获得$ p_i $%的优惠。
你需要k件材料合成衣服，其中第i件材料原价为d_i个钻石，你一共需要c_i件这种材料。当你获得p的优惠时，这个材料的真实价格为。
请问栗子米最少需要氪多少钱，这里我们规定只能氪整数的钱。

输入描述:

第一行一个整数T(T≤ 1000)，表示数据组数。
每组数据第一行两个整数m,k(1≤ m,k≤ 15)。
接下来m行每行两个正整数1≤ a_i ≤ 10^5, 1≤ p_i ≤ 100，保证a_i ≤ a_(i+1)，p_i ≤ p_(i+1).

_{接下来k行每行两个正整数1≤ ci, di≤ 1000。}

输出描述:

对于每组数据，输出一个整数，表示至少要氪多少钱。

示例1

输入

1
1 1
100 100
100 100

输出

10
解题思路：遗忘补缺---精度处理！
AC代码：

#include<bits/stdc++.h>
using namespace std;
int input(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
struct node1{int a,p;}nod1[15];
struct node2{int c,d;}nod2[15];
int T,m,k,ans,tmp;
int _ceil(int x){return x%100==0?x/100:x/100+1;}
void solve(){
    ans=0;m=input();k=input();
    for(int i=0;i<m;++i)nod1[i].a=input(),nod1[i].p=input();
    for(int i=0;i<k;++i)nod2[i].c=input(),nod2[i].d=input(),ans+=nod2[i].c*nod2[i].d;
    for(int i=0;i<m;++i){
        tmp=0;
        for(int j=0;j<k;++j)
            tmp+=_ceil(nod2[j].d*(100-nod1[i].p))*nod2[j].c;
        ans=min(ans,max(tmp,nod1[i].a));
    }
    printf("%d
",ans%10==0?ans/10:ans/10+1);
}
int main(){
    T=input();
    for(int i=1;i<=T;i++)solve();
    return 0;
}

L.数论之神

题目描述

终于活成了自己讨厌的样子。

这是她们都还没长大的时候发生的故事。那个时候，栗子米也不需要为了所谓的爱情苦恼。
她们可以在夏日的午后，花大把的时间去研究生活中一些琐碎而有趣的事情，比如数论。
有一天西柚柚问了栗子米一个题，她想知道中有多少不同的数，这些不同的数字里面第k大的是多少。

输入描述:

第一行一个整数T(T≤ 10^5 )，表示数据组数。

每组数据第一行两个整数，表示n,k(1≤ n≤ 10^18)，保证k不会超过不同的数字个数。

输出描述:

对于每组数据输出，输出两个整数，表示有多少个不同的数字和这里面第k大的是多少。

示例1

输入

3
1 1
5 2
67 8

输出

1 1
3 2
15 8
解题思路：找规律发现一定是1,2,3,...,x,n/(x-1),n/(x-2),...，x是sqrt(n)附近，求出第k大即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;LL n,k,x,y,tot,tp;
int main(){
    while(cin>>t){
        while(t--){
            cin>>n>>k;
            x=sqrt(n);
            if(n/x!=x)tp=0;
            else tp=-1;//多了一个重复的元素，增量为-1
            tot=2*x+tp;
            k=tot-k+1;//第k大的位置
            if(k<=x)y=k;//y直接赋值为k
            else y=n/(tot-k+1);// n/(x-m)
            cout<<tot<<' '<<y<<endl;
        }
    }
    return 0;
}

 Day_6

B.board

题目描述

恬恬有一个nx n的数组。她在用这个数组玩游戏：
开始时，数组中每一个元素都是0。
恬恬会做某些操作。在一次操作中，她可以将某一行的所有元素同时加上一个值，也可以将某一列的所有元素同时加上一个值。
在几次操作后，一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗？

输入描述:

第一行一个整数n（1≤ n≤ 1000）。
接下来n行每行n个整数表示数组a。
第(i+1)行的第j个元素表示a_i_j（a_i_j=-1或 0 ≤ a_i_j ≤ 10000）。-1表示隐藏的元素。

输出描述:

仅一个整数表示答案。

示例1

输入

3
1 2 1
0 -1 0
0 1 0

输出

1
解题思路：由于数据较小，记录-1这个元素的坐标，并将其赋值为1w，然后暴力模拟减一下，最后肯定只剩下这个元素（其余全为0），其值记为m'，即被隐藏的值为1w-m'。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,ex,ey,cnt,minv,mp[1005][1005];
int main(){
    while(~scanf("%d",&n)){
        memset(mp,0,sizeof(mp));
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                scanf("%d",&mp[i][j]);
                if(mp[i][j]==-1)ex=i,ey=j,mp[i][j]=10000;
            }
        }
        for(int i=0;i<n;++i){
            cnt=0;minv=20000;
            for(int j=0;j<n;++j)
                if(mp[i][j]>0)cnt++,minv=min(minv,mp[i][j]);
            if(cnt==n&&minv!=20000){
                for(int j=0;j<n;++j)
                    mp[i][j]-=minv;
            }
        }
        for(int j=0;j<n;++j){
            cnt=0;minv=20000;
            for(int i=0;i<n;++i)
                if(mp[i][j]>0)cnt++,minv=min(minv,mp[i][j]);
            if(cnt==n&&minv!=20000){
                for(int i=0;i<n;++i)
                    mp[i][j]-=minv;
            }
        }
        printf("%d
",10000-mp[ex][ey]);
    }
    return 0;
}

C.Circle

题目描述

现在我们要把1...n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。

输入描述:

一行一个整数n(1≤ n≤ 1000)。

输出描述:

一行一个整数表示答案。

示例1

输入

4

输出

4

说明

样例的一种构造方法为1 4 3 2。
解题思路：把1放首位置，由于相邻的奇数和偶数肯定互质，所以把1...n这n个元素依次放入一个环就可以，即最大对数为n。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int main(){
    while(cin>>n){
        cout<<n<<endl;
    }
    return 0;
}

H.Mountain

题目描述

平面上有n座山，每座山都有左右两面，第i座山的高度为a_i，现在弱弱在第一座山的左边山脚下（高度为0），他想要依此爬过这些山，到达第n座山的右边山脚下。
除了简单的爬上爬下，还有一种特殊操作。
如果弱弱目前在第i座山右面的海拔x的位置，且第j ( i < j )座山的海拔大于等于x，且第i + 1，...，j - 1座山中没有一座山的海拔高于x，那么他可以使用绳索滑到第j座山左面海拔x的位置。
弱弱想找到一种方式，使得他在行程中海拔变化的幅度最小。请输出最小幅度。

输入描述:

第一行一个整数n（1≤ n ≤ 1000）。
接下来一行n个整数a_i（1 ≤ a_i ≤ 1000）表示每座山的高度。

输出描述:

一行一个整数表示答案。

示例1

输入

5
1 3 5 4 2

输出

10
解题思路：最小幅度一定是最高山的高度的两倍。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,ans,m;
int main(){
    while(cin>>n){
        ans=0;
        for(int i=0;i<n;++i)cin>>m,ans=max(ans,m);
        cout<<ans*2<<endl;
    }
    return 0;
}