2017 五一 清北学堂 Day1模拟考试结题报告

2018-06-17 22:42:12来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

预计分数:100+50+50

实际分数:5+50+100

=.=

多重背包

(backpack.cpp/c/pas)

(1s/256M)

题目描述

提供一个背包,它最多能负载重量为W的物品。

现在给出N种物品:对于第i类物品,一共有Ci件物品;对于每一件物品,重量为Wi,价值为Vi。

找出一种装载方式使得背包中的物品总价值最大。

输入格式(backpack.in)

第一行两个整数N,W,代表物品的种类与背包的总负重。

第2~N+1行,每行三个整数Wi, Vi, Ci,代表第i种物品的重量、价值与数量。

输出格式(backpack.out)

仅一行,一个整数V,代表最大的总价值。

样例输入

3 9

5 8 2

3 6 2

2 1 5

样例输出

14

数据范围与限制

1<=N<=20, 0<=W<=1000

1<=Wi<=100, 0<=Vi<=100, 0<=Ci<=100

 一看见这道题的时候,我马上想到了动态规划完全背包问题,但无奈因为学习动归年代久远+没怎么学好,只能默默地打暴力;

数据范围也挺小,老师的意思应该就是让我们暴力。。

二十分钟打完暴力,然后我习惯性的做了几组极端数据改了改小错误就过了,

但是。。。。。。。。

因为我写的回溯比较特殊。。。、

所以。。。。。。。。

只能过极端数据。。。。

。。。。。。。

我竟然,,被这种水题淹死了,,,

AC 代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 #include<queue>
 7 #include<algorithm>
 8 using namespace std;
 9 struct node
10 {
11     int w;//重量
12     int v;//价值
13     int num;//数量 
14     int gdnum;
15 }a[40];
16 int n,m;
17 int ans=0;
18 void dfs(int nownum,int nowv,int noww)// 当前 背包编号 价值  重量 
19 {
20     if(nowv>ans&&noww<=m) {ans=nowv;}
21     if(noww>m||nownum>n)return;
22     
23     int p=a[nownum].gdnum;
24 
25     for(int i=0;i<=p;i++)
26     {
27         if(a[nownum].num>0)
28         {
29             a[nownum].num=a[nownum].num-i;
30             dfs(nownum+1,nowv+a[nownum].v*i,noww+a[nownum].w*i);
31             a[nownum].num=a[nownum].num+i;
32         }
33     }
34     
35     
36     //dfs(nownum+1,nowv,noww);
37 }
38 int main()
39 {
40     //freopen("backpack.in","r",stdin);
41     //freopen("backpack.out","w",stdout);
42     
43     scanf("%d%d",&n,&m);
44     
45     for(int i=1;i<=n;i++)
46     {
47         scanf("%d%d%d",&a[i].w,&a[i].v,&a[i].num);
48         a[i].gdnum=a[i].num;
49     }
50         
51     
52     dfs(1,0,0);
53     
54     printf("%d",ans);
55     
56     fclose(stdin);
57     fclose(stdout);
58     return 0;
59 }

循环序列

(circulate.cpp/c/pas)

(1s/256M)

 

题目描述

Alice与Bob在玩游戏:

Alice首先给出两个数X与Y(X<=Y);

Bob则按顺序将X,X+1,X+2,…,Y-1,Y写成一个大数S。

Alice最后将S首尾相连,让其围成一个圈。

这时,Bob想知道,从S的开头出发,往后的第L到第R数字之和是多少。

输入格式(circulate.in)

第一行四个整数X,Y,L,R,代表Alice的两个数字和Bob想要知道的第L位到第R位的数字之和。

输出格式(circulate.out)

仅一行,一个整数M,代表第L位到第R位的数字之和。

样例输入

10 11 4 12

样例输出

7

样例解释

Bob将数字写成一行大数S = 1011;围成一个圈后,从第4位到第12位分别是1,1,0,1,1,1,0,1,1,它们的和是7.

数据范围与限制

对于50%的数据,L=1, X,Y,L,R<=1000;

对于100%的数据,S的长度不大于10000,X,Y,L,R<=100000000.

 一开始读题有些懵逼,但想了一会儿才发现也不是很难,也就是数据处理比较繁琐。

于是二话不说就开始模拟。。。

但是敲完之后一看数据范围才发现撑死也就过百分之五十的数据

想了一会儿又没有想出什么好算法来。。。。

so硬着头皮交了份模拟暴力代码

果不其然->50分

正解:

因为从l-r很可能出现循环计算的情况,所以我们直接求出l和r对于生成字符串的倍数再加上余数即可

因为在循环计算生成字符串的每一位数字的时候非常繁琐,所以我们可以做一个前缀和,这样可以大大降低时间复杂度

超时代码:

TLE

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int x,y,l,r;
 5 int a[10001];
 6 int numa=1;
 7 int b[1001];
 8 int numb=1;
 9 int qiu(int o)
10 {
11     return o/numa*a[numa]+a[o%numa];
12 }
13 int main()
14 {
15     scanf("%d%d%d%d",&x,&y,&l,&r);
16     for(int i=x;i<=y;i++)
17     {
18         int p=i;
19         numb=1;
20         while(p!=0)
21         {
22             b[numb++]=p%10;
23             p=p/10;
24         }
25         for(int i=numb-1;i>=1;i--)
26         {
27             a[numa++]=b[i];
28         }
29     }
30     numa--;
31     for(int i=1;i<=numa;i++)
32     {
33         a[i]=a[i-1]+a[i];
34     }
35     cout<<qiu(r)-qiu(l-1);// -1是为了方式l号元素数两遍 
36     return 0;
37 }
AC

合并游戏

merge.cpp/c/pas

(1s/256M)

题目描述

       Cindy和Dan在玩一个游戏。

       一开始Cindy想出了N个数,接着她把这N个数全部给了Dan。

       Dan得到这组数后,它会挑出3个数(如果不足3个则全部挑出)。Dan会把这几个数加起来变成一个数,然后再把这个数与剩下的数再放到一起。Dan会一直这样做,直到最后只剩下一个数。

       Cindy则会在旁边记下每次Dan得到的数,她把这些数加起来,作为本次游戏的得分。她想知道,对于一组数,Dan能得到的最大的得分是多少?

输入格式

       第一行一个正整数N,代表这组数的个数;

       第二行N个正整数,代表这N个整数。

输出格式

       一行一个整数,代表可能的最大得分。

样例输入(merge.in)

       4

       3 1 5 6

样例输出(merge.out)

       29

样例解释

       Dan可以首先把(3,5,6)这三个数先合并起来,得到3 + 5 + 6 = 14; 接着他把剩下的两个数再合起来,得到1 + 14 = 15.这样,总得分是最大的 14 + 15 = 29.

数据范围与限制

       对于50%的数据,N<=10

       对于100%的数据,N<=1000,所有数不大于1000

当我读完题目的时候,我就想到了动态规划,想到了堆,想到了贪心,想到了优先队列。。。。

但是哪一个都不会,,,,。。,,。,。,。,。。

so还是跟着感觉模拟

没想到最后居然AC了=。=

好狗血。。。。。。

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 #include<queue>
 7 #include<algorithm>
 8 using namespace std;
 9 int n;
10 int a[10001];
11 int ans=0;
12 int flag=0;
13 int now=0;
14 int comp(const int &a ,const int & b)
15 {
16     return a>b;
17 }
18 void gett()
19 {
20     now=0;
21     if(a[1]!=-1&&a[2]==-1)
22     {
23         //ans=ans+a[1];
24         flag=1;
25         return ;
26     }
27     for(int i=1;i<=3;i++)
28     {
29         if(a[i]==-1)continue;
30         now=now+a[i];
31         a[i]=-1;
32     }
33     ans=ans+now;
34     a[1]=now;
35     sort(a+1,a+n+1,comp);
36 }
37 int main()
38 {
39     freopen("merge.in","r",stdin);
40     freopen("merge.out","w",stdout);
41     scanf("%d",&n);
42     
43     for(int i=1;i<=n;i++)
44     scanf("%d",&a[i]);
45     
46     sort(a+1,a+n+1,comp);
47     
48     while(flag==0)
49     {
50         gett();
51     }
52     
53     printf("%d",ans);
54     fclose(stdin);
55     fclose(stdout);
56     return 0;
57 }
AC

 

 

总结:

这次考试,不能说考的很好,因为我们学校有两位大神拿了满分,这个差距绝对不是一丁半点的,从思路到代码,从样例到极端数据,他们的能力远远在我之上

但又不能说考的很坏,起码没有犯跟前三次考试一样的超低级错误(其实第一个题也犯了次低级错误=.=),也算是一个转折点

第一题爆零(确实不值)

第二题超时(思维太窄)

第三题AC(有点运气)

至少没有出现那种一点思路都没有纯懵逼的题目,说明自己还有提升的空间

加油!

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1226 倒水问题

下一篇:关于C++构造函数