ECJTUACM16 Winter vacation training #1 题解&源码

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

//寒假训练赛，第一次拿第一，感觉很爽哦，AC3题！

A--------------------------------------------------------------------------------------------

题目链接：http://codeforces.com/problemset/problem/723/A

题目大意：三个人想在某个地点相遇，给出三个人在数轴上的坐标，求要走的最小值

解析：先排下序，然后另外两个人到中间人的位置为最小值（水题，自己证明），也可以最大的减最小的

代码如下:

#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,s;
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
if(a>=b&&b>=c)d=b;
else if(b>=a&&a>=c)d=a;
else if(a>=c&&c>=b)d=c;
else if(b>=c&&c>=a)d=c;
else if(c>=a&&a>=b)d=a;
else if(c>=b&&b>=a)d=b;
s=fabs(d-a)+fabs(d-b)+fabs(d-c);
printf("%d\n",s);
}
return ;
}

B---------------------------------------------------------------

题目链接：http://codeforces.com/problemset/problem/723/B

正解：模拟

解题报告：

直接模拟，注意处理字符串的计数器的诸多情况，有一点细节。

下面给出AC代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
char s[];
int n,len=,s1 = ,s2 = ;
bool flag = ;
while(scanf("%d%s",&n,&s)!=EOF)
{
//for(int i=0;i<n;i++)
//scanf("%c",&s[i]);
for(int j = ; j < n; j++)
{
if(s[j] == '(') flag=;
if(s[j] == ')') flag=;
if((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= 'A' && s[j] <= 'Z')) {
len++;
}
else len = ;
if(!flag) s1=max(s1, len);
else if(len==)s2++;
}
printf("%d %d\n", s1,s2);
}
return ;
}

C---------------------------------------------------------------

题目链接：http://codeforces.com/problemset/problem/725/B

思路：注意第一个乘务员是从1开始，第二个从三开始，然后模拟下即可

下面给出AC代码：

#include<bits/stdc++.h>
using namespace std;
__int64 judge(char c)
{
if(c=='f')
return ;
if(c=='e')
return ;
if(c=='d')
return ;
if(c=='a')
return ;
if(c=='b')
return ;
if(c=='c')
return ;
}
int main()
{
__int64 n,m,k,l,sum;
char str[];
while(scanf("%I64d%s",&n,str)!=EOF)
{
k=n/;
l=n%;
if(l==||l==)
{
sum=(k*+l)*+(n-);
}
else if(l==)
{
sum=(k*+)*+(n-)-;
}
else if(l==)
{
k=k-;
sum=(k*+)*+(n-)-;
}
sum+=judge(str[])-;
printf("%I64d\n",sum);
}
return ;
}

D---------------------------------------------------------------

题目链接：http://poj.org/problem?id=1017

问题的理解：

①、这道题目的题意理解比较明显，意思就是提供一些底面积为6*6的箱子，各种规格的物品，底面积不一致。要想使得使用的箱子数目最少，那么就是使得每个箱子底面积都装满，显然要从大的物品开始装。问题的关键在于如何计算一个完整的箱子装完一中规格的物品之后，如何去装剩下的其他的物品，空间如何分配。

②、对于6*6的物品的而言，装一个就满了；对于5*5的物品而言，装一个以后还剩下11个1*1的空间，这些空间只能放1*1规格的物品；对于4*4的物品而言，装一个以后还剩下5个2*2的空间，或者是完全换算成20个1*1的空间，当然这里面的空间也可以拆分成部分2*2的空间以及部分1*1的空间；

③、比较难处理的是装3*3规格的物品，一个6*6的箱子最终可以完全装4个3*3的物品，并且需要的箱子数目是3*3的物品的数目除以4向上取整，因为3*3的物品不能和4*4以及5*5的物品放在一起。（向上取整编码时有一个技巧在于不要直接使用向上取整的函数，比如对于除以4向上取整可以编码为 (a+3)/4 。

④、问题的关键在于如何处理最后一个装3*3的箱子其剩下的空间怎么才处理：第一种情况，当装3个3*3物品时，那么还剩下1个2*2和5个1*1的空间；第二种情况，当装2个3*3的物品时，那么还剩下3个2*2和6个1*1的物品空间；第三种情况，当装1个3*3的物品时，那么还剩下5个2*2和7个1*1的物品空间（这个剩余空间的计算方法是按照优先2*2的物品，是的2*2的物品能放的数目最大，然后再考虑1*1的物品）

⑤、剩下的2*2的物品就比较好办了，把前面各物品堆放时的剩下的空间堆放，不够就继续使用新的箱子；

下面给出AC代码：

#include <stdlib.h>
#include <stdio.h>
int main()
{
int N, a, b, c, d, e, f, y, x;
//N表示使用的箱子的数目，a-f一次表示1*1--6*6规格物品的个数
//x y是编码时使用的一个技巧，x表示1*1的剩余空间数，y表示2*2
//int u[4] = {0,5,3,1}; while()
{
scanf("%d %d %d %d %d %d",&a, &b, &c, &d, &e, &f);
if(a== && b== && c== && d== && e== && f==)
break;
N = f+e+d+(c+)/; //先计算大块头的物品6*6和5*5和4*4以及3*3的物品所需要的箱子 //关键是计算剩余的 2*2的空间，以最大化2*2的空间为计算标准 y = d*; //6*6和5*5的物品均不剩下2*2的空间，一个箱子装一个4*4的物品剩下5个2*2的空间 if( c% == )
y += ;
else if( c% == )
y += ;
else if( c% == )
y += ; //这里是关键，把这一个3*3的物品摆放在中间的位置才有可能放入5个2*2的物品 if( y < b)
N += ((b-y)+)/; //如果2*2的剩余空间不够，那么就需要新开箱子 x = *N - *f - *e - *d - *c - *b; //计算剩余的1*1的空间用了一个比较好的方法 if( x <a)
N += ((a-x)+)/; //如果1*1的空间不够，那么就需要开新的箱子 printf("%d\n", N);
}
return ;
}

E---------------------------------------------------------------

题目链接：http://poj.org/problem?id=1018

题意：

某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和价格prices。

现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。

其中B为这n件设备的带宽的最小值，P为这n件设备的总价。

分析：此题目可用多种方法求解，DP 、搜索、贪心、三分法

这里讲dp的思路。

我们定义状态dp 【i】【j】表示选择了前 i 个宽带其容量为 j 的最小费用。

很容易得到转移方程：dp【i】【j】=min（dp【i】【j】，dp【i-1】【k】+p）；

注意选择 j 的时候的大小情况。

顺便提供一下贪心的思路。（正确性未知）

从初始的第一个要选的宽带的每一个开始，每次向下贪心选择一个总的 B/P 的最大值，找出其中最大的既为答案。有兴趣的可以验证一下正确性！

dp代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <iomanip>
using namespace std; const int maxn=;
const int inf=0x3f3f3f3f;
int dp[maxn]; struct node{
int flow,sum;
node(int flow0=,int sum0=){
flow=flow0,sum=sum0;
}
}; void solve(){
queue <node> q;
q.push(node(inf,));
int n,m,flow,price;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&m);
for(int i=;i<maxn;i++) dp[i]=inf;
while(m-- >){
scanf("%d%d",&flow,&price);
int qsize=q.size();
while(qsize-- >){
node s=q.front();
q.pop();
if(s.flow<flow){
if(s.sum+price<dp[s.flow]) dp[s.flow]=s.sum+price;
}else{
if(s.sum+price<dp[flow]) dp[flow]=s.sum+price;
}
q.push(s);
}
}
while(!q.empty()) q.pop();
for(int i=;i<maxn;i++){
if(dp[i]<inf) q.push(node(i,dp[i]));
}
}
double ans=;
while(!q.empty()){
node s=q.front();
q.pop();
if(double(s.flow)/double(s.sum) > ans) ans= double(s.flow)/double(s.sum) ;
}
cout<<setiosflags(ios::fixed)<<setprecision()<<ans<<endl;
} int main(){
int t;
scanf("%d",&t);
while(t-- >){
solve();
}
return ;
}

ECJTUACM16 Winter vacation training #1 题解&源码的更多相关文章

ECJTUACM16 Winter vacation training &num;4 题解&amp&semi;源码
A......................................................................................... 题目链接→Code ...
ECJTUACM16 Winter vacation training &num;5 题解&amp&semi;源码
A------------------------------------------------------------------------------------------- 题目链接:ht ...
&OpenCurlyDoubleQuote;玲珑杯”ACM比赛 Round &num;12题解&amp&semi;源码
我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,日后补上剩余题的题解&源码吧! A ...
2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&amp&semi;源码(A&period;高斯消元，D,模拟，E,前缀和，F,LCS，H,Prim算法，I,胡搞，J,树状数组)
A------------------------------------------------------------------------------------ 题目链接:http://20 ...
&OpenCurlyDoubleQuote;盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&amp&semi;&amp&semi;源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp,K,二分+排序,L,矩阵快速幂,M,线段树区间更新+Lazy思想,N,超级快速幂+扩展欧里几德,O,BFS】
黑白图像直方图发布时间: 2017年7月9日 18:30 最后更新: 2017年7月10日 21:08 时间限制: 1000ms 内存限制: 128M 描述在一个矩形的灰度图像上,每个 ...
2016广东工业大学新生杯决赛网络同步赛暨全国新生邀请赛题解&amp&semi;源码
Problem A: pigofzhou的巧克力棒 Description 众所周知,pigofzhou有许多妹子.有一天,pigofzhou得到了一根巧克力棒,他想把这根巧克力棒分给他的妹子们.具体 ...
2017年浙江理工大学程序设计竞赛校赛题解&amp&semi;源码(A&period;水, D&period; 简单贪心 ,E&period;数论,I 暴力)
Problem A: 回文 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1719 Solved: 528 Description 小王想知道一个字 ...
April Fools Contest 2017 题解&amp&semi;源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间,G,数学)
A. Numbers Joke time limit per test:2 seconds memory limit per test:64 megabytes input:standard inpu ...
2017广东工业大学程序设计竞赛决赛题解&amp&semi;源码(A,数学解方程，B,贪心博弈，C,递归，D,水，E,贪心，面试题，F,贪心，枚举，LCA，G,dp，记忆化搜索，H,思维题)
心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description 来,我们先来放松下,听听儿歌,一起“唱” ...

随机推荐

4&period;5你太黑了，不带这么玩TypeForwardedTo的
话说最近好不容易把framework 4.0的metadata信息都能全部抽出了,结果换4.5挂了...framework那帮人在4.5里面用了些什么诡异的玩意? 结果一看4.5的部分field用了t ...
onclick跳转
☆如果是本页显示可以直接用location,方法如下: ①onclick="javascript:window.location.href='URL'" ②onclick=&quo ...
POJ 2404 Jogging Trails
Jogging Trails Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2122 Accepted: 849 Des ...
Mac上写C++
用惯Windows的同学可能刚开始用Mac的时候并不知道如何写C++,我刚开始在Mac上写C++的时候也遇到过这个困扰,Mac上并没有Windows上自己用习惯的Visual C++,下面我分享一下个 ...
打印杨辉三角--for循环
要求打印7行直角杨辉三角杨辉三角特点: 第1行和第2行数字都为1: 从第三行开始,除去开头和结尾数字为1,中间数字为上一行斜对角两个数字的和. 如下图: 打印结果: 代码如下: package 杨辉 ...
关于session共享的解决方法
当网站业务规模和访问量的逐步增大,原本由单台服务器.单个域名组成的网站架构可能已经无法满足发展需要此时会购买更多的服务器,并且以频道化的方式启用多个二级子域名,然后根据业务功能将网站分别部署在独立的 ...
自学Python Day1
Day1: 强制转换,打印类型.Python2(row input)=Python3 input input(Python2)不接受强制转换,输入和输出是一致的.加双引号是字符串,不加 ...
shell脚本简介
什么是shell? shell是一个命令解释器,它在操作系统的最外层,负责直接与用户对话,把用户的输入解释给操作系统,并处理各种各样的操作系统的输出结果,输出到屏幕返回给用户.这种对话方式可以是交互的 ...
orcl创建表及管理表
常用的字段数据类型: .字符串(varchar2(n)) n表示保存最大长度,基本200作用..整数(number(n)) n位的整数,也可用int代替.小数(number(n,m)) m为小数位,n ...
HTTP Transaction Delays
w客户端.服务器超载 HTTP The Definitive Guide 与建立TCP连接以及传输请求和相应报文的时间相比,事务处理的时间是很短的.除非客户端或服务器超载或正在处理复杂的动态资源,否则 ...