暑期模拟赛十 解题报告

T1:播放列表

　　乐乐非常喜欢听流行歌曲，他拥有n首歌曲。其中第i首歌曲持续时间为ti分钟。乐乐依次听了每一首歌，有些歌听了很多次，其中第i首歌连续听了ci次。
　　乐乐全部的播放列表如下：第一首歌编号为1共播放c1次，第二首歌编号为2共播放c2次，第三首歌...,第n首歌编号为n共播放cn次。
　　乐乐拿出一张纸，写下了他喜欢的音乐时刻。对于每一个记录的时刻，他想知道那一刻播放歌曲的编号是什么。也就是说乐乐想知道在第x分钟时播放的是哪一首歌（只要告诉这首歌的编号就行）。
　　你的任务是帮助乐乐计算记录的每个时刻的歌曲编号

测试数据：

　　第一行输入两个整数n，m（1≤n，m≤10^ 5）。
　　下面n行，每行输入两个整数，第i行输入整数ci，ti（1≤ci，ti≤10^ 9），描述整个播放列表。数据保证播放列表的总持续播放时间不超过10^9
　　下一行输入m个正整数v1，v2，...，vm，表示乐乐记录的时刻

　　输出m个整数，输出的第i个整数表示在vi时刻乐乐听到的歌曲编号。

【算法分析】：

直观的看是个模拟题如果我们用数组模拟时间那极限数据能够达到$10^9 *10^9*10^5==10^23$ 当然会超空间。
于是我，就将每首歌的开始时间记录，这样对于每个查找，只需用二分查到每个时间的前驱即可。

【AC代码】

#include<bits/stdc++.h>
using namespace std;
int be[100010];
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    int t1,t2,p=0;
    for(int i=1; i<=n; i++) {
        scanf("%d %d",&t1,&t2);
        be[i]=p+1;
        p+=t1*t2;
    }
    for(int i=1; i<=m; i++) {
        scanf("%d",&t1);
        int l=1,r=n;
        while(l<r) {
            int mid =(l+r)/2+1;
            if(be[mid]<=t1)l=mid;
            else r=mid-1;
        }
        printf("%d\n",l);
    }
    return 0;
}

T2:递归查询

【算法分析】:

简单的思路对于每一个l-r之间的数字都进行一次dg当然可以有记忆化。 超时 10分 QWQ
正解“打表”，预处理把每个数字的对应值都计算出，二维前缀和把每种数字计数，在查询时花费$O_{(1)}$的时间查询；

【AC代码】

#include<bits/stdc++.h>
using namespace std;
int l,r,o,ans;
int m[1000010];
int k[1000010];
int qz[1000010][10];
int g(int x) {
    int ret=1;
    while(x) {
        int t=x%10;
        if(t) ret=ret*t;
        x/=10;
    }
    return ret;
}
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=1000000; i++) m[i]=g(i);//计算数字数位乘积
    for(int i=1; i<=9; i++) k[i]=i；
    for(int i=1; i<=1000000; i++) k[i]=k[m[i]];//计算递归结果
    for(int i=1; i<=1000000; i++) {
        for(int j=1; j<=9; j++)  qz[i][j]=qz[i-1][j];
        qz[i][k[i]]++;
    }
    while(n--) {
        scanf("%d %d %d",&l,&r,&o);
        ans=qz[r][o]-qz[l-1][o];
        printf("%d\n",ans);
    }
    return 0;
}

T3：餐厅

　　乐乐想要去餐厅庆祝他的第一笔工资。
　　乐乐住在一个不寻常的地方，他的家到其他方就像是一棵有根的树，他的家就是根。这棵树共有n个节点所组成，根节点就是顶点1（顶点1就是乐乐的家）。其余的n-1个节点，如果是叶子节点就是餐厅（叶子节点就是指只有一个节点和他相连），如果不是叶子节点就是中转站。已知在n个节点中，有些节点是有小狗的（可能乐乐家也有），现在乐乐想选择某家餐馆去吃饭，但不幸的是他非常害怕狗，如果从他家到餐馆的路径中有存在超过连续的m个节点都有小狗，那么这条路是不能走的，这个餐厅是不能到达的，你的任务是求出有多少家餐馆乐乐可以去。

　　第一行输入整数n和m（2≤n≤10^5,1≤m≤n），分别表示树的总节点数和连续都具有小狗的节点最大的数量（如果超过m就不能走这条路）。
　　第二行输入n个整数a1，a2，...，an，如果ai等于0，说明第i个节点没有小狗，如果ai等于1，说明第i个节点有小狗。
　　接下来n-1行，每行输入一条树的边，用来连接某两个节点，格式用xi yi表示，（1≤xi，yi≤n，xi≠yi），xi和yi表示树的两个顶点，表示一条边,无向边。
　　数据保证所有的边接起来就是一棵根树。

　　输出一个整数，表示乐乐可以到达的餐厅的总数（必须满足问题描述的要求）。

【算法分析】：

这是一个有图的题目，存图也就用到邻接矩阵 or 邻接表。

题目给到的数据用邻接矩阵数组就需要有${(2*10^5)}^2=4*10^{10}$显然超出空间限制；

那么就需要用邻接表存图；
而用dfs遍历树即可

【AC代码】

/*
    Name: 餐厅 
    Author: hhz 
    Date: 22/08/19 16:08 
*/
#include<bits/stdc++.h>
const int N=200010;
using namespace std;
int tot,h[N],ver[N],nxt[N],c[N],n,m;
void add(int x,int y) {//邻接表，自行补脑。
    ver[++tot]=y;
    nxt[tot]=h[x];
    h[x]=tot;
}
int ans;
void dfs(int x,int r,int sum) {
//无向图的叶子节点无法通过度即出边判断，故以标记处理------------|
    bool f=true;                              //          |
    for(int i=h[x]; i!=0; i=nxt[i]) { //遍历出边           | 
        if(ver[i]==r) continue;//防止往回走                |
        f=false;//有向下遍历的操作则不是叶子节点--------------| 
        if(c[ver[i]]==1) {  //有狗 
            if(sum+1<=m) {   
                dfs(ver[i],x,sum+1);
            }   else continue ;
        } else dfs(ver[i],x,0);
    }
    if(f) ans++;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>c[i];
    for(int i=1; i<n; i++) {
        int x,y;
        cin>>x>>y;
        add(x,y);//无向图
        add(y,x);
    }
    dfs(1,0,c[1]);//(起点 原始点 狗数)
    cout<<ans;
}

T4：基因

　　一家跨国公司要求你帮助他们对苹果进行基因改造。为了让苹果长得更快，更大，更漂亮，更简单，苹果的DNA需要插入特定的猪的基因。
　　苹果的DNA由一系列来自集合{A, C, G, T}的字符表示。需要的猪基因也由这一组的字符组成。DNA应该被注射到某些地方，这样产生的序列就包含了一个猪基因(在连续的位置)。为了使事情变得更复杂，插入每个字符A, C, G, T有它自己的成本。
　　帮助这家跨国公司以最低的总成本达到他们的目标。作为奖励，你会得到很多苹果。
　
　　输入的第一行包含一个有N(1≤N≤10000)个字符组成的苹果DNA。
　　输入的第二行包含一个有M(1≤M≤5000)个字符组成的DNA,这代表了我们想要的插入苹果DNA中的猪基因。
　　这两个序列仅由集合{A, C, G, T}中的字符组成。
　　第三行输入包含了从区间[0,1000]的四个整数:插入一个字符A、C、G、T的成本.

【算法分析】:

贪心将模拟，将两个基因序列进行比对，记录每一次的成本。比较最小值即可；

【AC代码】

#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[200],minn,sum,l,r,i;
int main() {
    cin>>s;
    cin>>t;
    cin>>f['A']>>f['C']>>f['G']>>f['T'];
    minn=0x7fffffff;
    for(int i=1; i<=s.size(); i++) {
        l=i-1;
        r=0;
        sum=0;
        while(r<t.size()) {
            if(s[l]==t[r]) l++;
            else sum=sum+f[t[r]];
            r++;
        }
        if(minn>sum) minn=sum;
    }
    cout<<minn;
}

T5:分队

　　 在日本的一个寺院里，相扑比赛的负责人决定为他的N战士组织训练比赛。他确定了M场战斗的顺序和其参与者(两名战士在战斗中摔跤)。
　　就在比赛前的几分钟，他意识到他可以轻易地把事情搞得一团糟!那就是把战士分成两队，并且使同一队的战士在战斗中尽可能晚的面对对方。
　　帮助主管!对于给定的战斗计划，确定在最好的分队情况下，第一次同战队的人战斗的最大序号。在所有的测试数据中，这样的战斗肯定会发生。

【算法分析】：

题面好像有点不通顺，在这里解释一下，就是要将同时比赛的两人归为两队中，使同一队中的人最晚一起比赛。输出这场比赛的序号；
题意与noip-senior2010-3关押罪犯 类似，可参考；
用到并查集，细节看注释；

【AC代码】

/*
    Name:   分队 
    Author:  hhz
    Date: 22/08/19 15:16
    Description: 关押囚犯 
*/
#include<bits/stdc++.h>
using namespace std;
int f[200010];
int ff(int x) {
    if(f[x]==x) return x;
    else return f[x]=ff(f[x]);
}
int main() {
    int n,m;
    int a,b;
    int fa,fb;
    cin>>n>>m;
    for(int i=1; i<=2*n; i++) f[i]=i;
    for(int i=1; i<=m; i++) {
        cin>>a>>b;
        fa=ff(a);
        fb=ff(b);
//      祖先相同为同队,则输出
        if(fa==fb) {
            cout<<i;
            return 0;
        }
//      把祖先和朋友（敌人的敌人）的祖先并在一起 
        f[fa]=ff(b+n); 
        f[fb]=ff(a+n);
    }
    printf("0");
}

end;
为什么这次题目的主人公都喜欢把事情搞得复杂