2017 五一 清北学堂 Day1模拟考试结题报告
预计分数: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 代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int w;//重量
int v;//价值
int num;//数量
int gdnum;
}a[];
int n,m;
int ans=;
void dfs(int nownum,int nowv,int noww)// 当前 背包编号 价值 重量
{
if(nowv>ans&&noww<=m) {ans=nowv;}
if(noww>m||nownum>n)return; int p=a[nownum].gdnum; for(int i=;i<=p;i++)
{
if(a[nownum].num>)
{
a[nownum].num=a[nownum].num-i;
dfs(nownum+,nowv+a[nownum].v*i,noww+a[nownum].w*i);
a[nownum].num=a[nownum].num+i;
}
} //dfs(nownum+1,nowv,noww);
}
int main()
{
//freopen("backpack.in","r",stdin);
//freopen("backpack.out","w",stdout); scanf("%d%d",&n,&m); for(int i=;i<=n;i++)
{
scanf("%d%d%d",&a[i].w,&a[i].v,&a[i].num);
a[i].gdnum=a[i].num;
} dfs(,,); printf("%d",ans); fclose(stdin);
fclose(stdout);
return ;
}
循环序列
(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对于生成字符串的倍数再加上余数即可
因为在循环计算生成字符串的每一位数字的时候非常繁琐,所以我们可以做一个前缀和,这样可以大大降低时间复杂度
超时代码:
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
int x,y,l,r;
int a[];
int numa=;
int b[];
int numb=;
int qiu(int o)
{
return o/numa*a[numa]+a[o%numa];
}
int main()
{
scanf("%d%d%d%d",&x,&y,&l,&r);
for(int i=x;i<=y;i++)
{
int p=i;
numb=;
while(p!=)
{
b[numb++]=p%;
p=p/;
}
for(int i=numb-;i>=;i--)
{
a[numa++]=b[i];
}
}
numa--;
for(int i=;i<=numa;i++)
{
a[i]=a[i-]+a[i];
}
cout<<qiu(r)-qiu(l-);// -1是为了方式l号元素数两遍
return ;
}
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代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
int n;
int a[];
int ans=;
int flag=;
int now=;
int comp(const int &a ,const int & b)
{
return a>b;
}
void gett()
{
now=;
if(a[]!=-&&a[]==-)
{
//ans=ans+a[1];
flag=;
return ;
}
for(int i=;i<=;i++)
{
if(a[i]==-)continue;
now=now+a[i];
a[i]=-;
}
ans=ans+now;
a[]=now;
sort(a+,a+n+,comp);
}
int main()
{
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
scanf("%d",&n); for(int i=;i<=n;i++)
scanf("%d",&a[i]); sort(a+,a+n+,comp); while(flag==)
{
gett();
} printf("%d",ans);
fclose(stdin);
fclose(stdout);
return ;
}
AC
总结:
这次考试,不能说考的很好,因为我们学校有两位大神拿了满分,这个差距绝对不是一丁半点的,从思路到代码,从样例到极端数据,他们的能力远远在我之上
但又不能说考的很坏,起码没有犯跟前三次考试一样的超低级错误(其实第一个题也犯了次低级错误=.=),也算是一个转折点
第一题爆零(确实不值)
第二题超时(思维太窄)
第三题AC(有点运气)
至少没有出现那种一点思路都没有纯懵逼的题目,说明自己还有提升的空间
加油!
最新文章
- 对c++ public、protected、private关键字的理解
- 集合的概念 Stack和Queue Dictionary ArrayList和List<;T>;方法及用法
- 《CLR.via.C#第三版》第二部分第4,5章节读书笔记(二)
- Wince下sqlce数据库开发(一)
- 《Node.js+MongoDB+AngularJS Web开发》读书笔记及联想
- javascript动态添加form表单元素
- 【BZOJ】3196: Tyvj 1730 二逼平衡树(区间第k小+树套树)
- TDirectory.GetFileSystemEntries获取指定目录下的目录和文件
- Chapter 2 - How to Add a sprite
- 帝国cms 列表页分页样式修改美化【2】
- poj1220:高精度进制转换模板题
- Android TXT文件读写
- 企业邮件系统-Postfix安装使用
- Mysql之Windows初探
- Java编程规范(二)
- Nginx 403 forbidden多种原因及故障模拟重现
- Atcoder 水题选做
- SO\PR回写的数据如下
- 网络子系统46_ip协议数据帧的转发
- spring_150905_sqlmapclient