目录

• 北京化工大学2018年10月程序设计竞赛部分题解（a,c,e,h）
  • 竞赛事件相关

北京化工大学2018年10月程序设计竞赛部分题解（a,c,e,h）

竞赛事件相关

竞赛链接

虽然我发这个随笔的时候估计已经比完了，不过还是把链接放上来好了。

http://116.196.97.99/contest.php如果链接没设置好的话，可以在这里复制网址

竞赛题目

我做出来的

c.水题的zzh

题目描述

zzh是北化acm界新生代的大佬，每天会和无数来自全球各地的大佬进行交流。但是，zzh每天水群的时间有限。zzh想尽可能多的和更强的大佬进行交流。他把每个大佬的实力用一个数字ω表示出来，并且每天和ω总和最高的几位大佬进行交流。但是zzh正在忙着水群，于是把这个问题交给了你。事成之后，zzh会给你2147483647%1的金币作为奖励

输入

单组数据

第一行两个整数n，m，分别代表今天zzh水群的时间（以分计算）和今天想要与zzh交流的大佬的数量（<=2000）。

之后m行，分别有两个数字，代表和第i个大佬交流花费的时间（<n），以及大佬的ω（<1000）。

输出

今天与zzh交流的大佬的ω的值的总和。

样例输入

70 3
71 100
69 3
1 2

样例输出

5

这道题一看就是很常见的背包问题，然后我不会做了，我用了自己以前的代码，我检讨，我反思！

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int v,n;
    cin>>v>>n;
    int v[2100],p[2100],dp[2100];
    memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        cin>>v[i]>>p[i];
    for(int i=1;i<=n;i++)
        for(int j=v;j>=v[i];j--)
            dp[j]=max(dp[j-v[i]]+p[i],dp[j]);
    cout<<dp[v];
}

背包问题会就是会，不会也写不出来，大概。没什么好说的，下一道吧。

a.智力大奖赛

题目描述

输入

只有一行，有一个整数n，表示大三角形的层数（n<=45000）

输出

有两行，
第一行只有一个数，表示小三角形的个数；
第二行也只有一个数，表示能量棒的个数。

样例输入

8

样例输出

64
108

听坐我对面的说a很好做，但是数据太大了。

emmmmm,好的，没问题，biginteger走起！

大概思路就是第1行1个三角，第2行2+1个，第3行3+2个……

然后能量棒是第1行3根，第2行6根，第3行9根……

很简单的一道题，难点就在数据太大，不过，我biginteger怕过谁？？

import java.math.bigdecimal;
import java.util.scanner;
import java.math.biginteger;

public class main {

    public static void main(string[] args) {
        // todo auto-generated method stub
        scanner in = new scanner(system.in);
        int n=in.nextint();
        biginteger x1 = biginteger.zero;
        biginteger x2 = biginteger.zero;
        biginteger x3 = biginteger.zero;
        biginteger y1 = biginteger.zero;
        biginteger a1 = biginteger.one;
        biginteger b1 = biginteger.one;
        biginteger a2 = biginteger.zero;
        b1=b1.add(a1);
        b1=b1.add(a1);
        for(int i=0;i<n;i++) {
            x1=x1.add(a1);
            x2=x2.add(a2);
            a1=a1.add(biginteger.one);
            a2=a2.add(biginteger.one);
            y1=y1.add(b1);
            b1=b1.add(biginteger.one);
            b1=b1.add(biginteger.one);
            b1=b1.add(biginteger.one);
        }
        x3=x1.add(x2);
        system.out.println(x3); 
        system.out.println(y1); 
    }

}

能随意切换c++和java的我真棒233333

下一道，h吧，感觉挺简单的啊

h.数列

题目描述

故事不编了，m哥牛逼！

给出一个长度为n的数列a，现在有如下三种操作：
1、 1 p x: 将a[p]更改为x
2、 2 l r: 求a[l]到a[r]的最大值与最小值的差
3、 3 l r: 求a[l]到a[r]的和
现在给你一些操作，请你求出相应的数值。

输入

第一行输入一个数字t表示数据组数(1<=t<=10)
接下来t组数据，每组数据第一行为两个整数n、m(1<=n,m<=1e5)，分别代表a的长度和操作数，下一行n个整数表示a[1]到an，接下来m行，每行一个如题目给出的输入格式的操作
(1<=p,l,r<=n,0<=x<=1000)

输出

对于每组数据
对每一个操作2或3，输出一个整数表示结果

样例输入

2
4 4
1 2 3 4
2 1 2
1 2 7
2 1 2
3 1 4
5 4
2 7 6 3 8
2 1 3
1 3 1
2 1 5
3 3 3

样例输出

1
6
15
5
7
1

这题真的很简单啊，不就是一些数组的操作吗？怎么做的人那么少。。。

唯一需要注意的就是题目中的数组是从1开始的。

#include <iostream>
using namespace std;
int suan(int a[],int l,int r){
    int m1,m2;
    m1=a[l];
    m2=a[l];
    for(int i=l+1;i<=r;i++){
        m1=m1>a[i]?m1:a[i];
        m2=m2<a[i]?m2:a[i];
    }
    return m1-m2;
}
int add(int a[],int l,int r){
    int s=0;
    for(int i=l;i<=r;i++){
        s+=a[i];
    }
    return s;
}
int main()
{
    int t,n,m,x,p,y,l,r;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int a[n+1];
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        while(m--){
            cin>>x;
            switch(x){
                case 1:cin>>p>>y;
                        a[p]=y;
                        break;
                case 2:cin>>l>>r;
                        cout<<suan(a,l,r)<<endl;
                        break;
                case 3:cin>>l>>r;
                        cout<<add(a,l,r)<<endl;
                        break;
            }
        }
    }
}

请不要在意我乱起的函数名！

然后这个时候我发现我排第12？？！从来没这么高过，信心大增！！！

继续加油！

看e好像做的人挺多的，我也来试试吧！

e.云计算

题目描述

北化acm社团有n台云服务器，每台服务器都有一个使用期限，第i台服务器还能使用ri天。现在有m个任务需要部署到云服务器上运行，第j个任务需要运行tj天。第j个任务能够部署在第i台服务器上时当且仅当 tj <=ri，并且每台服务器在其使用期限内总共只能运行一个任务。即使tk+tj <=ri，你也无法将第k个和第j个任务一起部署到第i 台服务器上，否则这题将失去其签到题的作用（看到签到题这几个字的时候我笑了）。为了能充分利用云服务器，现在需要计算最多能部署多少任务。而你作为北化acm的希望,这个问题需要由你 来解决。

输入

单组数据
第一行两个整数代表 n和m
第二行 n个整数代表 r1，r2，...，rn
第三行 m个整数代表t1，t2，...，tm
1<= n,m,tj ,ri <=100000

输出

输出一个整数代表最多有多少个任务能够部署到云服务器上

样例输入

5 5
6 1 3 4 2 
4 6 6 2 5 

样例输出

3

既然是签到题，哈哈，那就没什么好说的了，来吧，我不怕你！

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n,m,s=0;
    cin>>n>>m;
    int a[n],b[m];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    int j=0;
    for(int i=0;i<m;){
        if(b[i]<=a[j]){
            i++;
            j++;
            s++;
        }
        else{
            j++;
        }
        if(j==n){
            break;
        }
    }
    cout<<s;
}

嗯，很简单，就随便排排序，然后判断一下使用期限够不够就行了。

然后！！！第8了！！！

不过很可惜，我就止步4道了，之后再也没做出来了，名次也掉到了50多名，不过也很强了啊！好久不做题了竟然还能突破之前的最后成绩。

我没做出来的

b.求素数

题目描述

输入

共两行：
第一行为n何l，中间用空格隔开。 (1<=n<=100 , 1<=l<=7)
第二行为n个0~9的数字，中间用空格隔开。

输出

只有一行，含全部满足条件的素数，中间用逗号隔开,保证至少存在一个素数。

样例输入

10 3
8 9 1 0 2 3 5 4 7 6

样例输出

547

自己感觉代码没问题了，但就是过不了。。就不放了。

d.积木

题目描述

我懒得编故事了 m哥牛逼！
有n个积木，第i个积木的高度为a[i]，求每个积木前面有几个比它矮的积木

输入

多组输入，每组由两行组成，第一行输入n，第二行输入n个数，为n个积木的高度a[i]
//(1<=n<=100000)(1<=a[i]<=1000000000)

输出

每组数据输出n个数，第i个数为第i个积木前面比他矮的积木的个数

样例输入

5
1 2 3 4 5

样例输出

0 1 2 3 4

这道题是喜闻乐见的超时，最后也没找到好的算法。

看不懂，不想看的

f.罗dalao的密码

题目描述

众所周知，罗dalao十分的厉害。有一天，罗dalao发明了一种密码，用来给文档加密(可认为文档是一个长度为n的字符串s)。
罗dalao要对s[l]...s[r]加密，首先要反转区间s[l]...sr，然后使k=(r-l+1)/2(向下取整),再反转区间s[l]...s[l+k-1]和s[l+k]...s[r]，以此类推，一直到区间长度都为1为止。(加密整个文档相当于加密区间s[1]...s[n])
有一天你找到了一篇罗dalao加密过的文档，现在要你求出某个位置的字符加密前的位置。

输入

第一行输入整数t(0<t<=1000)，表示数据组数，接下来t行，每行两个整数n和p(1<=p<=n<=1e18),分别表示文档长度和询问的位置

输出

输出t行，每行一个整数，表示每组数据中加密后p位置的字符的原位置

样例输入

4
4 1
4 2
4 3
4 4

样例输出

3
4
1
2

g.罗dalao的小电影

题目描述

罗dalao非常的厉害，于是会有很多人向他请教一些问题，而他每天有l分钟专门用来解答问题。由于来请教的人很多，所以要找罗dalao请教问题，需要预定。
于是，罗dalao知道每天会有n个人来请教问题，第i个到来的人在第ai分钟到来，罗dalao解答问题要用ti分钟(罗dalao精明的安排保证ai+ti<=ti+1和an+tn<=l)，然而罗dalao想找空闲的时间看小电影，罗dalao看每一部小电影都要从头看到尾，期间不能有中断，每部小电影的时长为m，罗dalao想知道他每天最多可以看多少部小电影，现在请你帮他计算一下。

输入

单组
第一行3个整数：n，l和m(0<=n<=1e5,1<=l<=1e9,1<=m<=l)
接下来n行，每行两个整数ai和ti(0<=ai<=l-1,1<=ti<=l)

输出

输出一个整数，表示罗dalao最多能观看多少部小电影

样例输入

2 11 3
0 1
1 1

样例输出

3

i.leo的简单规律题

题目描述

leo喜欢吃烧烤，而且只吃三种，羊肉串，青菜，火腿肠，她吃烧烤之前喜欢把烧烤摆成一长串，而且还有特别的摆放规则，摆错了她这一顿就不吃了。
规则有：1.对于连续的三个烤串，不能三个烤串都是同一种。
2.对于连续的三个烤串，如果三种烤串都有，青菜不能放在中间（在吃肉中途吃菜是会令人自闭的）
3.依旧是对于连续的三个烤串，第一串和第三串都是青菜的话，中间不能是羊肉或者火腿肠（她的意思是吃素减肥）
现在有三种烤串都有无数根，她想摆出长度为n的烤串，请你求出方案数（由于结果可能会很大，所以只需给出答案模1000000007）

输入

第一行有一个数字t（t<100），表示有t组数据
接下来的t行，每行一个数字n (1≤n≤1010)

输出

对于每一组数据，输出摆出长度为n的烤串的方案数

样例输入

4
2
3
4
6

样例输出

9
20
46
244

问题 j.leo的简单数列

题目描述

leo有两个数列，它们的长度都是n
在最开始，a数列里都是0，b数列是leo随机填充的n个数（数字为1-n，保证b数列是1-n的一个排列）
现在leo可以进行两种操作
\1. add l r 表示她给a数列从a[l],a[l+1],...,a[r],都加一

1. query l r 表示她想知道当 l<= i <=r 时 a[i]/b[i]（向下取整）的所有项的总和
   当然leo在数学这一块还不是很熟练，上次月考数学才110分，所以想请你帮她完成这些操作

输入

多组数据
对于每组数据，第一行有2个数字n，q，表示a与b的长度 和操作数。1<= n,q < =100000
第二行有n个数字，表示数列b的初始状态
接下来的q行，每行一个操作，具体操作格式如题目所给
1<= l <= r <= n

输出

对于每一个query操作，输出一行表示求和的结果。

样例输入

6 10
6 1 4 3 2 5
query 1 4
add 2 2
query 3 6
add 1 6
add 3 4
query 2 5
query 1 6
add 2 4
query 1 4
query 3 5

样例输出

0
0
2
2
4
1

总结

我果然还是只能做简单题。。