时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho很喜欢在课间去小卖部买零食。然而不幸的是，这个学期他又有在一教的课，而一教的小卖部姐姐以冷若冰霜著称。第一次去一教小卖部买零食的时候，小Ho由于不懂事买了好一大堆东西，被小卖部姐姐给了一个冷若冰霜的眼神，食欲都下降了很多。
从那以后，小Ho就学乖了，去小卖部买东西只敢同时买3包以内的零食，并且价格加起来必须是5的整数倍，方便小卖部姐姐算价格。
但是小Ho不擅长计算，所以他把小卖部里所有零食的价格以及他对这个零食的渴望度都告诉了你，希望你能够帮他计算出在不惹恼小卖部姐姐的前提下，能够买到零食的渴望度之和最高是多少？
输入
每个输入文件包含多组测试数据，在每个输入文件的第一行为一个整数Q，表示测试数据的组数。
每组测试数据的第一行为一个正整数N，表示小卖部中零食的数量。
接下来的N行，每行为一个正实数A和一个正整数B，表示这种零食的价格和小Ho对其的渴望度。
一种零食仅有一包。
对于100%的数据，满足1 <= Q <= 10，1<=N<=50，0<A<=10，1<=B<=100。
对于100%的数据，满足A的小数部分仅可能为0.5或0。
输出
对于每组测试数据，输出一个整数Ans，表示小Ho可以获得最大的渴望度之和。
样例输入
1
4
0.5 6
4.5 7
5.0 4
2.0 9
样例输出
17
使用最简单的枚举就可以解决该问题。在有些情况下，只买两包零食甚至一包零食可能要比买三包零食的情况更优，所以三种情况都要考虑。
AC代码：
#include<iostream>题目2 : 清理海报
using namespace std;
float price[100];
int wanted[100];
int main()
{
int Q;
scanf("%d",&Q);
while(Q--)
{
int N;
int ans=0;
scanf("%d",&N);
for(int i=0;i<N;i++)
{
cin>>price[i]>>wanted[i];
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
for(int k=0;k<N;k++)
{
if(i!=j&&j!=k&&i!=k)
{
int m=price[i]+price[j]+price[k];
if((!(m%5))&&(!(price[i]+price[j]+price[k]-m)))
{
if(wanted[i]+wanted[j]+wanted[k]>ans)
ans=wanted[i]+wanted[j]+wanted[k];
}
}
}
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(i!=j)
{
int m=price[i]+price[j];
if((!(m%5))&&(!(price[i]+price[j]-m)))
{
if(wanted[i]+wanted[j]>ans)
ans=wanted[i]+wanted[j];
}
}
}
}
for(int i=0;i<N;i++)
{
int m=price[i];
if((!(m%5))&&(!(price[i]-m)))
{
if(wanted[i]>ans)
ans=wanted[i];
}
}
printf("%d\n",ans);
}
}
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi实验室所在的建筑一楼有一个用于贴海报的黑板，不停的有新的海报往上贴，也会安排人员不断的对海报进行清理，而最近，轮到了小Hi去对海报进行清理。
黑板是一块W*H大小的区域，如果以左下角为直角坐标系的话，在上次清理后第i张贴上去的海报可以视作左下角为(X1i, Y1i)，右上角为(X2i, Y2i)的一个矩形。
撕去一张海报会导致所有覆盖在其上的海报都被同时撕掉(这样被称为连带，这个过程是具有传递性的，即如果A覆盖B，B覆盖C，那么撕掉C会导致A和B均被撕掉)，但是一张海报想要被手动撕掉的话需要至少存在一个角没有被其他海报覆盖(海报A被海报B覆盖当且仅当他们存在面积大于0的交集并且A在B之前贴出，海报A的一个角被海报B覆盖当且仅当这个顶点处于海报B的内部)。
于是现在问题来了，为了节约时间，小Hi决定一次性撕掉尽可能多的海报，那么他应该选择哪张海报呢？在效果相同的情况下，小Hi倾向于选择更早贴出的海报。
输入
每个输入文件仅包含单组测试数据。
每组测试数据的第一行为三个正整数W，H和N，分别表示黑板的宽、高以及目前张贴出的海报数量。
接下来的N行，每行为四个正整数X1i、Y1i、X2i和Y2i，描述第i张贴出的海报。
对于20%的数据，满足1<=N<=5，1<=W,H<=10。
对于100%的数据，满足1<=N<=1000，0<=X1i, X2i <= W, 0<=Y1i, Y2i<=H, 1<=W,H<=108。
输出
对于每组测试数据，输出两个正整数Ans和K，表示小Hi一次最多能撕掉多少张海报，和他选择的海报是第几张贴出的。
样例输入
6 7 4
0 0 4 4
1 0 3 4
1 4 4 6
0 0 3 5
样例输出
3 1
撕去一张海报会导致所有覆盖在其上的海报都被同时撕掉，想到了什么呢？对了，图！每张海报看成一个点，如果A海报撕去后B海报也会被撕去，那么就从A到B连一条边，然后搜索进行遍历。这里要判断海报的两种状态，一种是是否被覆盖；一种是是否至少存在一个角没有被覆盖。这里我写了5个checkin函数，前4个函数判断海报i的四个角是否被海报j覆盖，最后1个函数判断一种特殊的情况，即两张海报之间存在覆盖，但是任何一个海报的四个角都没有被覆盖，类似于十字架。
AC代码：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int x1[1010],x2[1010],y1[1010],y2[1010];
int map[1010][1010];
int flag[1010],vis[1010];
int W,H,N,num;
bool checkin1(int i,int j)
{
if((x1[j]<x2[i])&&(x2[i]<x2[j])&&(y1[j]<y2[i])&&(y2[i]<y2[j])) return 1;
return 0;
}
bool checkin2(int i,int j)
{
if((x1[j]<x2[i])&&(x2[i]<x2[j])&&(y1[j]<y1[i])&&(y1[i]<y2[j])) return 1;
return 0;
}
bool checkin3(int i,int j)
{
if((x1[j]<x1[i])&&(x1[i]<x2[j])&&(y1[j]<y1[i])&&(y1[i]<y2[j])) return 1;
return 0;
}
bool checkin4(int i,int j)
{
if((x1[j]<x1[i])&&(x1[i]<x2[j])&&(y1[j]<y2[i])&&(y2[i]<y2[j])) return 1;
return 0;
}
bool checkin5(int i,int j)
{
if((x1[i]>=x1[j])&&(x1[i]<=x2[j])&&(x2[i]>=x1[j])&&(x2[i]<=x2[j])
&&(y1[j]>=y1[i])&&(y1[j]<=y2[i])&&(y2[j]>=y1[i])&&(y2[j]<=y2[i]))
{
return 1;
}
return 0;
}
int find(int i)
{
num=1;
queue<int> q;
q.push(i);
vis[i]=1;
while(!q.empty())
{
int k=q.front();
q.pop();
for(int j=1;j<=N;j++)
{
if((map[k][j])&&(!vis[j])&&(k!=j))
{
vis[j]=1;
num++;
q.push(j);
}
}
}
return num;
}
int main()
{
scanf("%d %d %d",&W,&H,&N);
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
for(int i=1;i<=N;i++)
{
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(j>i)
{
if(checkin1(j,i)||checkin2(j,i)||checkin3(j,i)
||checkin4(j,i)||checkin1(i,j)||checkin2(i,j)
||checkin3(i,j)||checkin4(i,j)||checkin5(i,j)||checkin5(j,i))
{
map[i][j]=1;
}
}
}
}
int flag1,flag2,flag3,flag4;
for(int i=1;i<=N;i++)
{
flag1=0,flag2=0,flag3=0,flag4=0;
for(int j=1;j<=N;j++)
{
if(j>i)
{
if(checkin1(i,j)) flag1=1;
if(checkin2(i,j)) flag2=1;
if(checkin3(i,j)) flag3=1;
if(checkin4(i,j)) flag4=1;
}
}
if(flag1&&flag2&&flag3&&flag4)
{
flag[i]=1;
}
}
int answer1=0,answer2=0;
for(int i=1;i<=N;i++)
{
if(!flag[i])
{
memset(vis,0,sizeof(vis));
int temp=find(i);
if(answer1<temp)
{
answer1=temp;
answer2=i;
}
}
}
printf("%d %d\n",answer1,answer2);
}
题目3 : 自行车架
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的宿舍楼下有一块用于停自行车的区域。平时自行车都停得非常杂乱，于是楼长打算去买一排自行车架用来停车。自行车架一般有P个槽，每个槽的两侧都可以停入自行车；但是一个槽位同时只能有一侧停入自行车。此外，停入一辆自行车会导致无法在这一侧的附近若干个槽位中停入自行车。
经过调查，这栋宿舍楼的学生共拥有N辆A型自行车、M辆B型自行车和K辆C型自行车。其中A型自行车会导致这一侧的左右各1个槽位不能使用，B型自行车会导致这一侧的左右2个槽位不能使用，C型自行车会导致这一侧的左右3个槽位不能使用。
现给定N、M和K，楼长希望知道P至少要是多少，才能将所有自行车都停入。![hihoCoder[Offer收割]编程练习赛2题目解析](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0RvdkwyMWxaR2xoTG1ocGFHOWpiMlJsY2k1amIyMHZMM0J5YjJKc1pXMWZhVzFoWjJWekx6SXdNVFl3TXpFekx6RTBOVGM0TURJMU9UTTJOVEF6TG5CdVp3PT0%3D.jpg?w=700&webp=1 "hihoCoder[Offer收割]编程练习赛2题目解析")
如图中所示，P最少为7就可以存放下2辆A型，1辆B型和2辆C型。
输入
每个输入文件包含多组测试数据，在每个输入文件的第一行为一个整数Q，表示测试数据的组数。
每组测试数据为3个整数N、M和K，意义如前文所述。
对于20%的数据，满足0<=N、M、K<=2，Q=100。
对于40%的数据，满足0<=N、M、K<=50，Q=100。
对于100%的数据，满足0<=N、M、K<=50，1<=Q<=100000。
输出
对于每组测试数据，输出一个整数P，表示自行车架至少需要的槽位。
样例输入
4
2 1 2
1 0 0
2 0 2
1 2 2
样例输出
7
1
5
7
这道题感觉就很难了，当时没有做出来。看了别人的思路和代码，按照我的理解来说一下。首先，我们要知道大方向肯定是DP，在DP的过程中不断加入自行车和槽位。首先要明确几个概念：
| A1 | |
| A2 |
比如说这种情况，我们称第一排是有空槽位的，也就是右上角那个位置；称第二排是没有空槽位的，因为A2已经占用了第二排最右边的位置。
用一个六维数组做dp，dp[i][j][k][p][q][r]，其中i，j，k分别是ABC三种车的数量。p是没有空槽位的那一排最右边的那辆自行车的类型，q是有空槽位的那一排最右边的那辆自行车的类型，r是有空槽位的那一排最右边的那辆自行车留有多少个空位。首先设置好初始值，一辆车的时候，相当于留了3个空位。(4个或者以上空位等同于3个)，对应的P为1。dp[1][0][0][0][0][3]=1；dp[0][1][0][1][0][3]=1；dp[0][0][1][2][0][3]=1。然后就是遍历整个六维数组，每次碰到值不为INF的情况时，就尝试加一辆新的车在最右边。由于一共有3种车，而且每种车可以分别加在两侧，所以一共六种情况。已经有两辆A车的情况下，dp[2][0][0][0][0][1]=2，加一辆新的B车，如果加在没有空槽位的那一排，则dp[2][1][0][1][0][3]=5；如果加在有空槽位的那一排，则dp[2][1][0][1][0][2]=4。最后给定任意的n,m,k,求dp[n][m][k][x][y][z]的最小值，即可。
| A | |
| A |
| A | ||||
| A | B |
| A | B | ||
| A |
dp[2][1][0][1][0][2]=4
AC代码：
#include<cstdio>题目4 : 扫地机器人
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf=1e8+1;
int dp[52][52][52][4][4][4],ans;
int solve()
{
memset(dp,inf,sizeof(dp));
dp[1][0][0][0][0][3]=1;
dp[0][1][0][1][0][3]=1;
dp[0][0][1][2][0][3]=1;
for(int i=0;i<=50;i++)
{
for(int j=0;j<=50;j++)
{
for(int k=0;k<=50;k++)
{
for(int li=0;li<3;li++)
{
for(int lj=0;lj<3;lj++)
{
for(int lk=1;lk<=3;lk++)
{
if(dp[i][j][k][li][lj][lk]!=inf)
{
for(int ad=0;ad<3;ad++)
{
//遍历每种新加入的自行车类型
int fi=i,fj=j,fk=k;
if(ad==0) fi++;
if(ad==1) fj++;
if(ad==2) fk++;
//用临时变量存放每种自行车的数量
int flk=lk+max(li,ad)+2;
//如果放在没有空槽位那一列
if(flk>3) flk=3;
dp[fi][fj][fk][ad][lj][flk]=min(dp[fi][fj][fk][ad][lj][flk],dp[i][j][k][li][lj][lk]+max(li,ad)+2);
flk=max(max(lj,ad)+2-lk,1);
//如果放在有空槽位那一列
if(flk>3) flk=3;
dp[fi][fj][fk][ad][li][flk]=min(dp[fi][fj][fk][ad][li][flk],dp[i][j][k][li][lj][lk]+flk);
}
}
}
}
}
}
}
}
}
int main()
{
int Q,N,M,K;
scanf("%d",&Q);
solve();
dp[0][0][0][0][0][1]=0;
while(Q--)
{
scanf("%d%d%d",&N,&M,&K);
ans=inf;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
for(int k=1;k<=3;k++)
{
ans=min(ans,dp[N][M][K][i][j][k]);
}
}
}
printf("%d\n",ans);
}
}
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho最近买了一台扫地机器人用来代替他清扫实验室的卫生，扫地机器人有不同的尺寸，但是通常来说可以被视作一个M*M的正方形，扫地机器人仅能清扫被自己覆盖过的区域。
小Ho所在的实验室是一个多边形，任意两条边之间要么为垂直关系要么为平行关系。扫地机器人也仅能沿着这两个方向平移，不能旋转。实验室中的一些区域过于狭窄，所以对扫地机器人的大小就有了限制。
于是小Ho找到了你，给出实验室的地形和扫地机器人的大小，希望你能够判断给定的扫地机器人能否成功清扫实验室的每一块区域。
输入
每个输入文件包含多组测试数据，在每个输入文件的第一行为一个整数Q，表示测试数据的组数。
每组测试数据的第一行为两个正整数N和M，分别表示多边形的点数和机器人的大小。
接下来的N行，每行为两个整数X、Y，表示多边形的一个顶点。
多边形的顶点按照顺时针顺序给出，即从当前点前往下一个点时，多边形的内部在右侧方向，多边形的边均平行于坐标轴。
对于20%的数据，满足0<=N<=200，1<=X、Y、M<=100。
对于100%的数据，满足0<=N<=1000，1<=X、Y、M<=108。
对于100%的数据，满足实验室可以由一个1*1的扫地机器人完成清扫。
对于100%的数据，满足Q<=5。
输出
对于每组测试数据，如果机器人能够顺利完成任务，输出Yes，否则输出No。
样例提示
样例1(x轴正方向为向下，y轴正方向为向右):
![hihoCoder[Offer收割]编程练习赛2题目解析](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0RvdkwyMWxaR2xoTG1ocGFHOWpiMlJsY2k1amIyMHZMM0J5YjJKc1pXMWZhVzFoWjJWekx6SXdNVFl3TXpFekx6RTBOVGM0TURNeU9UazRNalkxTG5CdVp3PT0%3D.jpg?w=700&webp=1 "hihoCoder[Offer收割]编程练习赛2题目解析")
样例3(x轴正方向为向下，y轴正方向为向右):
![hihoCoder[Offer收割]编程练习赛2题目解析](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0RvdkwyMWxaR2xoTG1ocGFHOWpiMlJsY2k1amIyMHZMM0J5YjJKc1pXMWZhVzFoWjJWekx6SXdNVFl3TXpFekx6RTBOVGM0TURNek1EZzROREV4TG5CdVp3PT0%3D.jpg?w=700&webp=1 "hihoCoder[Offer收割]编程练习赛2题目解析")
样例输入
3
6 2
0 0
0 2
2 2
2 3
3 3
3 0
6 2
0 0
0 3
3 3
3 5
5 5
5 0
8 2
0 0
0 2
1 2
1 3
3 3
3 1
2 1
2 0
样例输出
No
Yes
No
这道题的思路是模拟，过程很繁琐。从起点开始按输入顺序(顺时针)让机器人沿着多边形的内边走，每走一条边判断一下，根据向量的叉积可以判断往哪个方向转。由于回到起点时起点也要判断，因此把第二个点作为最后一个点。每次到一个角时，如果是向右转则必定在内角，否则在外角，对于每个角，判断是否有线穿过机器人，有则无解。
AC代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
int const MAX=1e3+5;
int n, m;
int dir[MAX];
//0左1右
struct POINT
{
int x,y;
}p[MAX];
struct LINE
{
POINT s,e;
}l[MAX];
struct ROBOT
{
int x1,y1,x2,y2;
};
//用一条对角线上的两个点来表示机器人,x2y2的坐总是大于等于x1y1
int Dir(POINT p1, POINT p2, POINT p3)
{
if((ll)(p1.x-p3.x)*(p2.y-p3.y)<(ll)(p2.x-p3.x)*(p1.y-p3.y)) return 1;
return 0;
}
bool OK(ROBOT r,LINE a)
{
if(a.s.x<0||a.s.y<0||a.e.x<0||a.e.y<0) return true;
int min_x=min(a.s.x,a.e.x);
int max_x=max(a.s.x,a.e.x);
int min_y=min(a.s.y,a.e.y);
int max_y=max(a.s.y,a.e.y);
if(a.s.x==a.e.x)
if((a.s.x<=r.x1&&a.s.x<=r.x2)||(a.s.x>=r.x1&&a.s.x>=r.x2)||max_y<=r.y1||min_y>=r.y2)
return false;
if(a.s.y==a.e.y)
if((a.s.y<=r.y1&&a.s.y<=r.y2)||(a.s.y>=r.y1&&a.s.y>=r.y2)||max_x<=r.x1||min_x>=r.x2)
return false;
return true;
}
int main()
{
int T;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
bool flag=true;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y);
p[n+1]=p[1];
p[n+2]=p[2];
for(int i=1;i<=n;i++)
{
l[i].s=p[i];
l[i].e=p[i+1];
}
for(int i=1;i<=n;i++) dir[i]=Dir(l[i].s,l[i].e,p[i+2]);
for(int i=1;i<=n&&flag;i++)
{
ROBOT a;
a.x1=a.x2=l[i].e.x;
a.y1=a.y2=l[i].e.y;
int dx=l[i].e.x-l[i].s.x;
int dy=l[i].e.y-l[i].s.y;
if(dir[i]==1)
//内角向右
{
if(dx>0)
{
a.x1-=m;
a.y1-=m;
}
if(dx<0)
{
a.x2+=m;
a.y2+=m;
}
if(dy>0)
{
a.x2+=m;
a.y1-=m;
}
if(dy<0)
{
a.x1-=m;
a.y2+=m;
}
}
else
//外角向左
{
if(dx>0)
{
a.x2+=m;
a.y1-=m;
}
if(dx<0)
{
a.x1-=m;
a.y2+=m;
}
if(dy>0)
{
a.x2+=m;
a.y2+=m;
}
if(dy<0)
{
a.x1-=m;
a.y1-=m;
}
}
for(int i=1;i<=n&&flag;i++)
{
if(OK(a,l[i]))
{
flag=false;
}
}
}
printf("%s\n",flag?"Yes":"No");
}
}
}