目录

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

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

竞赛事件相关

竞赛链接

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

https://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

总结

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