题解篇-C5

A-毛毛虫

题目描述

草丛中有两只毛毛虫。他们想穿过草丛里的杀虫剂到达对方的身边。而草丛里的杀虫剂形成了nn个两两无公共点的圆。注意这些杀虫剂只存在于圆的边界上，且杀虫剂宽度非常非常细。毛毛虫一开始不在任何圆的边界上。

毛毛虫穿过杀虫剂就要受到一次伤害。请问一只毛毛虫到达另一只的身边，最少需要受到几次伤害？

时间限制：1000ms 内存限制：65536KB

输入

第一个数为数据组数T，每组数据输入5行，T≤10。

第一行包含一个整数 n，n≤50。

第二行包含 n 个整数 x_i，表示 n 个圆的圆心的横坐标。

第三行包含 n 个整数 y_i ，表示 n 个圆的圆心的纵坐标。

第四行包含 n 个整数 r_i ，表示 n 个圆的半径。

最后一行包含四个整数 x1,y1,x2,y2，表示两只毛毛虫位置的横纵坐标。

所有坐标、半径的绝对值不超过10001000。

输出

对于每组数据，输出一行，毛毛虫受到伤害的次数。

输入样例

1
3
0 -6 6
0 1 6
2 2 2
-5 1 5 1

输出样例

1

---

分析

刚开始拿到这道题很容易被文字数量和一大堆的输入数据唬住(本人就是)，其实仔细分析会发现其实并不难(Moggin：这是学长出给初中生的题)。

言归正传，这道题就是一个点和圆的相对位置关系的题，很简单，两条毛毛虫都在某一圆内或者都不在某一圆内对毛毛虫的伤害为0，所以只用考虑包含一条毛毛虫同时不包含另一毛毛虫的圆的数量即可。

AC代码

#include<stdio.h>
int x[55]={},y[55]={},r[55]={};
int judge(int x1,int y1,int i){
	if(((x1-x[i])*(x1-x[i])+(y1-y[i])*(y1-y[i]))<=r[i]*r[i]){
		return 1;
	}
	return 0;
}
int main(){
	int T,n,i;
	int x1,y1,x2,y2;
	scanf("%d",&T);
	while(T--){
		int ans=0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&x[i]);
		}
		for(i=0;i<n;i++){
			scanf("%d",&y[i]);
		}
		for(i=0;i<n;i++){
			scanf("%d",&r[i]);
		}
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		for(i=0;i<n;i++){
			if(judge(x1,y1,i)&&!judge(x2,y2,i)){
				ans++;
			}
			else if(!judge(x1,y1,i)&&judge(x2,y2,i)){
				ans++;
			}
		}
		printf("%d\n",ans);	
	}
}

---

B-图1

题面

一个无向图，N个点编号1~N。M条边，每条边有一个权值c。

对于一个点集A，这个点集的权值S定义为S_A=max(c_ij)，其中i∈A∧j∈A∧i≠j。

现在将N个点分割为两个点集A、B，请问max(S_A,S_B)的最小值

时间限制：1000ms 内存限制：65536KB

输入

第一行两个正整数N、M。(2≤N≤20000,1≤M≤100000)

接下来M行，每行三个整数a,b,c，表示ab之间有一条权值为c的边（1≤a,b≤N,1≤c≤10⁹）

输出

一行一个数

输入样例

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出样例

3512

---

分析

首先分析题目，白话重新描述一下就是，给图顶点染色，只染两种颜色，然后将同色中权值最大的边最小化，求最小值。这样看来显然就是二分图了(对本人可能不那么显然)，对需要求出来的边进行枚举，将比其权值小的边删去后，剩余的边能否构成二分图，能构成，说明该边满足条件，然后再枚举比该边小的，再判断，直到最后不能构成二分图，则找到了答案。那通过什么方法枚举呢，当然可以挨着挨着枚举，时间复杂度也上去了，由于需要枚举的边是可以从大到小枚举过来的，所以我们可以直接采用二分来求就好了，这样时间复杂度就很低了。然后的问题就是判断能否构成二分图的问题了。我们直接采用比较简单的DFS染色即可。这样就能求出答案了。

注意：一些需要注意的细节在这里说明一下。首先是二分最开始的值的设置，由于给的权值范围都是10⁹了，所以我们的初始值应该达到long long才行(测试了一下，需要10¹¹才能AC)。其次呢就是存图的问题，10000的顶点数，邻接矩阵存肯定爆内存了。所以采用链式前向星来存比较好。还有就是不是一开始就存图，是把边先枚举，比该边大的边才放进图里(连边)，所以最开始存顶点和边的信息需要一个结构体。最后就是染色的问题了，大家可以看了代码再看我马上要说的，就是vis[]数组的作用，因为判断了一个顶点后，和它相连的所有点都已经被染色了，如果再次访问这些点的话，就会出现错误，所以需要判断一下，让已经被染色的不再需要判断，因为无论这个点其所连的边有没有构成二分图，与其相连的所有点就相当于也已经全部判断了一遍了，所以不需要再判断一遍，也能节省一些时间。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define max 300005
using namespace std;
typedef long long ll;
struct node {
	int a,b,c;
} ver[max];
struct Edge {
	int v;
	int c;
	int next;
} e[max];
int head[max],e_num=0;
int n,m,S,T;
ll mid;
int color[max],vis[max];
void add(int u,int v,int c) {
	e[e_num].v=v;
	e[e_num].c=c;
	e[e_num].next=head[u];
	head[u]=e_num;
	e_num++;
}
void insert(int u,int v,int c) {
	add(u,v,c);
	add(v,u,c);
}
bool dfs(int u, int c)
{
	vis[u]=1;
    color[u]=c;
    for(int i=head[u];~i;i=e[i].next)
    {
        int j=e[i].v;
        if(!color[j])
        {
            if(!dfs(j, 3-c)) return false;
        }
        else if(color[j]==c) return false;
    }
    return true;
}
bool check() {
	memset(vis,0,sizeof(vis));
	memset(head,-1,sizeof(head));
	memset(color,0,sizeof(color));
	for(int i=1; i<=m; i++) {
		if(ver[i].c>mid) insert(ver[i].a,ver[i].b,ver[i].c);//如果大则连边
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			if(!dfs(i,1)) return false;
		}
	}
	return true;
}
int main() {
	int a,b,c;
	ll ans;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&ver[i].a,&ver[i].b,&ver[i].c);
	}
	ll l=0,r=1e14;
	while(l<=r){
		mid=((l+r)>>1);
		if(check()) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
}

需要看类似题目可以看看这道： https://www.nowcoder.com/questionTerminal/e5e5e74a65c34d588421944029306e2e (CodeForces 85E)

---

C-图2

题面

一个有向图，N个点编号1~N。M条边，每条边有一个权值c。

点i、j之间的最短路长度定义为 S_ij。如果i、j不连通，则S_ij=−1

输出所有使得S_ij最大的i和j

时间限制：1000ms 内存限制：65536KB

输入

第一行一个整数t表示数据组数(t≤50)

对于每组数据：

第一行两个正整数N、M。(2≤N≤200,1≤M≤1000)

接下来M行，每行三个整数a,b,c，表示ab之间有一条权值为c的边（1≤a,b≤N,1≤c≤10³）

输出

输出所有使得S_ij最大的i、j，每一对i、j输出一行，用空格隔开，按i的大小由小到大输出，i相同时按j的大小由小到大输出，

输入样例

2
2 1
1 2 3
3 3
1 2 2
2 3 3
3 1 5

输出样例

1 2
2 1

---

分析

首先看题目可以确定是最短路径题目，接下来就是选算法的问题了(Dijkstra、spfa、Floyd)，显然这里要求所有顶点之间的最短路径，如果选择spfa和Dijkstra则需要求n次再来遍历判断，显然太麻烦了，所以我们显然选择Floyd即可(后文我也会附上Dijkstra的代码)。

本题需要注意的一些地方：首先是排序，读清楚题，怎么排序，再写cmp函数。其次就是每组数据的最大S_ij不唯一，本人是采用循环找到前n个相同的最大值，再来输出，当然会有更好的方法。然后就是因为图权值最初设置为inf，因为又是要计算最大边，所以再Floyd算完之后，需要把仍然是inf的边置为-1，不影响后面的排序。最后呢就是注意Floyd算完之后需要存到另一个结构体数组里再进行排序会比较方便。

AC代码(Floyd)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 1000000000
#define max 205
struct node {
	int i,j,c;
}ans[40005];
int cmp(void const *a,void const *b) {
	struct node c,d;
	c=*(struct node*)a;
	d=*(struct node*)b;
	if(c.c!=d.c) return d.c-c.c;
	else {
		if(c.i!=d.i) return c.i-d.i;
		return c.j-d.j;
	}
}
int main() {
	int e[max][max];
	int t,n,m,M,cnt;
	int a,b,c;
	scanf("%d",&t);
	while(t--){
		M=-2147483647;
		memset(ans,0,sizeof(ans));
		cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) e[i][j]=0;
				else e[i][j]=inf;
			}
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&a,&b,&c);
			e[a][b]=c;
		}	
		for(int k=1; k<=n; k++)
			for(int i=1; i<=n; i++)
				for(int j=1; j<=n; j++)
					if(e[i][j]>e[i][k]+e[k][j])
						e[i][j]=e[i][k]+e[k][j];// Floyd
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(e[i][j]==inf) e[i][j]=-1;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				ans[cnt].c=e[i][j];
				ans[cnt].i=i;
				ans[cnt].j=j;
				cnt++;			
			}
		}
		qsort(ans,cnt,sizeof(struct node),cmp);
		int tmp=ans[0].c,eid=0;
		for(int i=1;;i++){
			if(ans[i].c==tmp) eid++;
			else break;
		}
		for(int i=0;i<=eid;i++){
			printf("%d %d\n",ans[i].i,ans[i].j);
		}
	}
}

AC代码(Dijkstra)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 2000
int INFINITY=1000000000;
int MAX=-2147483647;
struct node{
	int i,j,c;
};
struct node ans[40005];
int cnt=0,n,m;
int sweight[max]={},map[max][max],spath[max],e[max][max];
void init() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j) map[i][j]=e[i][j]=0;
			else map[i][j]=e[i][j]=INFINITY;
		}
	}
}
int cmp(void const *a,void const *b) {
	struct node c,d;
	c=*(struct node*)a;
	d=*(struct node*)b;
	if(c.c!=d.c) return d.c-c.c;
	else {
		if(c.i!=d.i) return c.i-d.i;
		return c.j-d.j;
	}
}
void Dijkstra(int v0){
	MAX=-2147483647;
	int i,j,v,minweight;
	char wfound[max]={0};
	for (i=1;i<=n;i++){
		sweight[i]=map[v0][i];
		spath[i]=v0;
	}
	sweight[v0]=0;
	wfound[v0]=1;
	for (i=1;i<=n-1;i++){
		minweight=INFINITY;
		for (j=1;j<=n;j++)
			if (!wfound[j]&&(sweight[j]<minweight)){
				v=j;
				minweight=sweight[j];
			}
		wfound[v]=1;
		for (j=1;j<=n;j++){
			if (!wfound[j]&&(minweight+map[v][j]<sweight[j])){
				sweight[j]=minweight+map[v][j];
				spath[j]=v;
			}	
		}			
	}
	for(i=1; i<=n; i++) {
		e[v0][i]=sweight[i];
	}
}
int main(){
	int a,b,c;
	int T;
	int tmp,eid;
	scanf("%d",&T);
	while(T--) {
		int cnt=0;
		memset(ans,0,sizeof(ans));
		scanf("%d%d",&n,&m);
		init();
		for(int i=1; i<=m; i++) {
			scanf("%d%d%d",&a,&b,&c);
			map[a][b]=c;
		}
		for(int i=1; i<=n; i++) {
			Dijkstra(i);
		}
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				if(e[i][j]==INFINITY) e[i][j]=-1;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				ans[cnt].c=e[i][j];
				ans[cnt].i=i;
				ans[cnt].j=j;
				cnt++;			
			}
		}
		qsort(ans,cnt,sizeof(struct node),cmp);
		tmp=ans[0].c,eid=0;
		for(int i=1;; i++) {
			if(ans[i].c==tmp) eid++;
			else break;
		}
		for(int i=0; i<=eid; i++){
			printf("%d %d\n",ans[i].i,ans[i].j);
		}
	}
}

Dijkstra即多了几步，总体思想是不变的。

---

D-图3

题面

一个无向图，N个点编号1~N。M条边，每条边有一个权值c。

问对于每条边，最少删除多少条边后，可以使得存在一个最小生成树包含这条边。

时间限制：1000ms 内存限制：65536KB

输入

第一行两个正整数N、M。(2≤N,M≤100)

接下来M行，每行三个整数a、b、c，表示ab之间存在一条权值为c的边。（1≤a,b≤N，1≤c≤500）

输出

输出一行M个数，数之间用空格隔开

输入样例

3 3
1 2 1
3 1 2
3 2 3

输出样例

0 0 1

分析

首先分析题，要使最小生成树包含这条边。我们现在一直求最小生成树的方法也就两种，Kruskal和Prim算法。我们这道题显然就从Kruskal法来考虑比较方便(可能不是那么显然，先这样想)。Kruskal算法是通过先对边权值通过排序，从权值最小的边开始遍历每一条边，如果加入该边后，生成树仍然满足树的条件的话，则该边加入，如果构成了回路即不满足树的条件，则不增加该边，继续遍历。那对于本题呢，假设某边要存在一个最小生成树包含该边，按照Kruskal算法的过程，在枚举到该边之前，该边没有连通，即先枚举比该边权值小的所有边，然后再枚举该边，那要怎样保证该边一定在生成树里呢，即要保证该边加入后不形成回路，怎么保证呢，因为生成树的不唯一性，那就是要让该边的两个顶点(u,v)不连通，即u、v与其余所有比该边权值小的边的顶点组成一个图(容量为1，保证双向，因为仅求边的数量)，让u和v为源点和汇点，让u和v之间不连通即可，没有连通即割开，即求割，但是要保证删除的边最少，所以就是求最小割了，所以就是算最大流了，所以直接套板子就okk了。

需要注意的地方：首先，仍然一开始不建图，仅用一结构体存起来，等排完序后遍历时再存图，存图的时候也不要忘了把边的编号存起来，输出的时候需要用。然后是对每条边算了一遍最大流后，要把原图重新初始化一遍，以便存下一个图。之后是，有可能对某一条边来说，存在很多权值相等的边，权值相等的边是不能加入到图里的，但是排序对于权值相同的边并不敏感，所以需要自己判断一下，把权值相同的边先略去后，再建图。最后用数组存结果输出即可。

AC代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define INF 2147483647
#define max 10005
struct node{
	int a,b,c,num;
}p[105];
int min(int a,int b){
	if(a<b) return a;
	return b;
}
struct Edge{
	int v;
	int c;
	int next;
}e[max];
int head[max],e_num=-1;
int n,m,S,T;
int cmp(const void *a,const void *b){
	struct node c,d;
	c=*(struct node*)a;
	d=*(struct node*)b;
	return c.c-d.c;
}
void add(int u,int v,int c){
	e_num++;
	e[e_num].v=v;
	e[e_num].c=c;
	e[e_num].next=head[u];
	head[u]=e_num;
}
void insert(int u,int v,int c){
	add(u,v,c);
	add(v,u,c);
}
int depth[max];// 层次网络 
bool bfs()
{
    std::queue<int> q;//定义一个bfs寻找分层图时的队列
    while (!q.empty()) q.pop();
    memset(depth,-1,sizeof(depth));
    depth[S]=0;//源点深度为0
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(e[i].c>0&&depth[v]==-1){
                q.push(v);
                depth[v]=depth[u]+1;
            }
        }
    }
    return (depth[T]!=-1);
}
int dfs(int u,int flow){        //flow表示当前搜索分支的流量上限
    if(u==T){
        return flow;
    }
    int res=0;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(e[i].c>0&&depth[u]+1==depth[v]){
            int tmp=dfs(v,min(flow,e[i].c));    // 递归计算顶点 v，用 c(u, v) 来更新当前流量上限
            flow-=tmp;
            e[i].c-=tmp;
            res+=tmp;
            e[i^1].c+=tmp;      // 修改反向弧的容量
            if(flow==0){        // 流量达到上限，不必继续搜索了
                break;
            }
        }
    }
    if(res==0){     // 当前没有经过顶点 u 的可行流，不再搜索顶点 u
        depth[u]=-1;
    }
    return res;
}
int dinic(){        // 函数返回值就是最大流的结果
    int res=0;
    while(bfs()){
        res+=dfs(S,INF);    // 初始流量上限为 INF
    }
    return res;
}
int main(){
	int i,j;
	int ans[505]={};
    scanf("%d%d",&n,&m);//m为边
    for(i=0;i<m;i++){
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
        p[i].num=i;
    }
    qsort(p,m,sizeof(struct node),cmp);
    for(i=0;i<m;i++){
    	memset(head,-1,sizeof(head));
    	memset(e,0,sizeof(e));
    	e_num=-1;
    	S=p[i].a,T=p[i].b;
    	for(j=i;j>=0;j--){
    		if(p[j].c==p[i].c) continue;
    		insert(p[j].a,p[j].b,1);
		}	
		ans[p[i].num]=dinic();
	}
	for(i=0;i<m;i++){
		printf("%d ",ans[i]);
	}
    return 0;
}

---

E-棋盘

题面

一个N行，M列的棋盘。棋盘每个格子都是边长为1的正方形。

现在要在棋盘上放一些1×2大小的骨牌。骨牌的边线与格子重合（必须占2个格子），任意两个骨牌不能重叠。

但是棋盘上的一些格子已经被占用，请问最多可以放多少个骨牌。

时间限制：1000ms 内存限制：65536KB

输入

第一行三个正整数N、M、q。(2≤N,M≤100,0≤q≤1000)

接下来q行，每行两个整数a,b,表示第a行第b列的格子被占用（1≤a,b≤N）

输出

输出一行

输入样例

8 8 0

输出样例

32

---

分析

首先我们看题，格子里放骨牌，1*2的骨牌，有些格子被占用，问最多的放法。可能刚看到这道题没什么思路，但我们可以从这个1*2看出一些东西，可以想到就是两个相邻的格子可以放一个骨牌，我们就可以看作一个格子和其所有相邻的格子之间存在一条边，容量为inf，并且该格子连接源点，容量为1，与其相邻的格子连接汇点，容量也为1，这样从源点到汇点的最大流即可以放的骨牌的方法数了。我们举一个例子：一个十字格子(5个格子)，把中间的格子连接源点，则其四周的格子都要连接汇点，那么此时的最大流显然就是1了，也就是方法数为1，同理就可以扩张为整个棋盘了。将所有i+j为奇数(i为行j为列)的点连源点，偶数连汇点相邻的连边，容量就不再赘述，然后求最大流即可。

需要注意的地方：首先就是存边，单纯的邻接矩阵肯定不行。然后就是那些被占用的点，用一个二维数组存行和列然后作为标记数组，标记的不存入图内即可。最后就是其实该题和练习赛A题几乎一样，并且更简单(想到方法的前提下)

AC代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define INF 2147483647
#define max 1000000
int num[1005][1005]={};
int min(int a,int b){
	if(a<b) return a;
	return b;
}
struct Edge{
	int v;
	int c;
	int next;
}e[max];
int head[max],e_num=-1;
int n,m,S,T;

void add(int u,int v,int c){
	e_num++;
	e[e_num].v=v;
	e[e_num].c=c;
	e[e_num].next=head[u];
	head[u]=e_num;
}
void insert(int u,int v,int c){
	add(u,v,c);
	add(v,u,0);
}
int depth[max];// 层次网络 
bool bfs()
{
    std::queue<int> q;//定义一个bfs寻找分层图时的队列
    while (!q.empty()) q.pop();
    memset(depth,-1,sizeof(depth));
    depth[S]=0;//源点深度为0
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(e[i].c>0&&depth[v]==-1){
                q.push(v);
                depth[v]=depth[u]+1;
            }
        }
    }
    return (depth[T]!=-1);
}
int dfs(int u,int flow){        //flow表示当前搜索分支的流量上限
    if(u==T){
        return flow;
    }
    int res=0;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(e[i].c>0&&depth[u]+1==depth[v]){
            int tmp=dfs(v,min(flow,e[i].c));    // 递归计算顶点 v，用 c(u, v) 来更新当前流量上限
            flow-=tmp;
            e[i].c-=tmp;
            res+=tmp;
            e[i^1].c+=tmp;      // 修改反向弧的容量
            if(flow==0){        // 流量达到上限，不必继续搜索了
                break;
            }
        }
    }
    if(res==0){     // 当前没有经过顶点 u 的可行流，不再搜索顶点 u
        depth[u]=-1;
    }
    return res;
}
int dinic(){        // 函数返回值就是最大流的结果
    int res=0;
    while(bfs()){
        res+=dfs(S,INF);    // 初始流量上限为 INF
    }
    return res;
}
int main(){
	int a,b,sum=0,eid=0;
	int i,q;
	memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&q);
    S=0,T=n*m+1;
    for(i=1;i<=q;i++){
		scanf("%d%d",&a,&b);
		num[a][b]=1;
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
        	eid++;
        	if(!num[i][j]){
        		if((i+j)%2){
					insert(S,eid,1);
					if(j<m) insert(eid,eid+1,INF);
					if(j>1) insert(eid,eid-1,INF);
					if(i<n) insert(eid,eid+m,INF);
					if(i>1) insert(eid,eid-m,INF);
				}
				else{
					insert(eid,T,1);
				}
			}
			
	    }
	}
    printf("%d",dinic());
    return 0;
}

---

F-垃圾粉碎机

题目描述

垃圾分类快来了，垃圾场主某楠希望赶在垃圾分类之前将厂里的垃圾全部粉碎填埋。为此场长专门去租了n台垃圾粉碎机，每种垃圾粉碎机都有一个最长使用时间ti，在这段时间里总共可以处理mi吨垃圾,可以在任意时间使用任意时长，但是用完就不能再用。由于场里太穷，同一时间只能运行一台垃圾粉碎机，现在想问在垃圾分类来临之前，最多能粉碎多少垃圾。为了简化计算，所有时间单位以小时计算。

时间限制：1000ms 内存限制：65536KB

输入

前两个数为垃圾粉碎机的个数N和距离垃圾分类来临时间T小时

接下来N行每行2个整数，对应的ti和mi

所有数字均不大于1e5

输出

输出一行，能处理的垃圾最大重量，保留2位小数，单位为吨

输入样例

1 2
2 3

输出样例

3.00

分析

读题就能看出这是一道非常明显的分数背包题，就直接贪心算法就可解决了，根据m_i/t_i的商进行排序即可，然后遍历输出搞定。

如果对其他背包问题还有问题的朋友可以查看本人的另一篇博文: https://dbettkk.github.io/2019/11/11/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-DP-%E2%80%94%E2%80%94%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/#more

AC代码

#include<stdio.h>
#include<stdlib.h>
#define max 100005
struct node{
	double t;
	double m;
	double a;
}dp[100005];
int cmp(void const *a,void const *b) {
	struct node c,d;
	c=*(struct node*)a;
	d=*(struct node*)b;
	return c.a<d.a;
}
int main(){
	int n,T,i;
	double ans=0;
	scanf("%d%d",&n,&T);
	for(i=0;i<n;i++){
		scanf("%lf%lf",&dp[i].t,&dp[i].m);
		dp[i].a=dp[i].m/dp[i].t;
	}
	qsort(dp,n,sizeof(struct node),cmp);
	for(i=0;i<n;i++){
		if(dp[i].t<=T){
			ans+=dp[i].m;
			T-=dp[i].t;
		}
		else{
			ans+=T*dp[i].a;
			T=0;
		}
	}
	printf("%.2lf",ans);
}

---

G-小面包

题目描述

又要发小面包了。这次我们有许多3*6的小面包和6*6的方糕，以及一个6*N的长方形盒子，强迫症的某楠一定要把它们整齐的装到盒子里，并且要尽量装满。请问有多少总不同装法？

时间限制：1000ms 内存限制：65536KB

输入

多组数据输入。 每组一个3的倍数N（0<=N<=750）

输出

对于每组数据，输出一行，为最终计算对1000007取模得到的结果。

输入样例

3
6

输出样例

1
3

样例解释

输入为3时，只能放入一块小面包。

输入为6时，有三种情况：

（1）竖着放两块小面包

（2）横着放两块小面包

（3）放一块方糕

分析

首先因为输入的n是3的倍数，所以我们可以将问题简化为2*n的盒子装1*2和2*2的方糕的问题。然后我们开始寻找递推关系。假设n对应有f(n)种装法，那么如果我们首先装1*2的空间，那就相当于只能装1*2的方糕，那么对应就是解决f(n-1)的问题，那如果我们先装2*2的空间，那么可以有两种装法，两个1*2的方糕横着摆放和一个2*2的方糕(有朋友可能会问为什么两个1*2的方糕竖着摆放的情况不算，因为这种情况实际上是属于我们前面提到的先装1*2的空间的情况，如果这里再算一遍就重复了)，所以就相当于解决2*f(n-2)的问题即可。然后如果是装3*2的空间，那么不就是等效于1*(2*2)的情况和2*(1*2)的情况吗，所以我们就找到递推关系了，如下：

• f(n)=f(n-1)+2*f(n-2)

当然大家也可先推一推前面几种情况然后找规律也是可以解决的，只是这个找规律比较靠运气。

AC代码

#include<stdio.h>
int main() {
	int n,a[755];
	while(~scanf("%d",&n)) {
		a[1]=1,a[0]=1,a[2]=3,a[3]=5,a[4]=11;// 这是推出的前几种情况，实际不需要这么多
		for(int i=2; i<=n/3; i++) {
			a[i]=(a[i-1]+2*a[i-2])%1000007;
		}
		printf("%d\n",(a[n/3])%1000007);
	}
}

---

H-点线面

题面

二维平面上有n个点。现在用一根（毛）线将这些点围起来，问线的最小长度和围起来的面积。

时间限制：1000ms 内存限制：65536KB

输入

第一行一个正整数N。(2≤N≤100000)

接下来N行，每行两个整数a，b，表示一个点的坐标。（−10⁶≤a,b≤10⁶）

输出

输出一行一个数，保留两位小数。

输入样例

4
0 0
0 4
3 0
1 1

输出样例

12.00 6.00

分析

刚上了计算几何，应该都能看出这就一道凸包板子题。当然如果有和我一样没有很认真听的可以看下我下方的分析。

凸包怎么实现呢，首先确定平面中最下方的点，这个点肯定是在凸包内的，然后再以这个点为基点对其余所有点进行极角排序，即将其余点与该点进行连线后，对连线与x轴的夹角进行排序。排了序后，将夹角最小的点入栈，然后遍历所有其他点，若此点在栈顶的点的左边(实际是栈顶两个点连线的左边)，则压栈，若在右边(同理)，则将栈顶出栈然后把此点压栈，遍历结束后，栈中的点即为凸包上的点。还有就是如何判断在点的左边还是右边的问题了，用叉积即可。比如，a(x1,y1)和b(x2,y2)和c(x3,y3)，判断c相对于ab的位置，那就是相当于判断x1*y2+x2*y3+x3*y1和x1*y3+x2*y1+x3*y2 的大小即可。求出栈后，周长直接遍历算即可，面积则遍历求叉积相加即可(别忘除以2)。

参考： https://www.cnblogs.com/Gaxc/p/9610900.html

AC代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#define rint register int
using namespace std;

struct node {
	double x,y;
} a[100005];
int n,p,st[100005],top;
double ans,miny=2e9,minx=2e9;

int cmp(node b,node c) { //极角排序
	if (fabs((b.y-miny)*(c.x-minx)-(c.y-miny)*(b.x-minx))<=1e-8) return fabs(minx-b.x)<fabs(minx-c.x);
	return (b.y-miny)*(c.x-minx)<(c.y-miny)*(b.x-minx);
}

int check(int b,int c,int d) { //叉积判断
	return ((a[b].x*a[c].y)+(a[c].x*a[d].y)+(a[d].x*a[b].y)-(a[b].x*a[d].y)-(a[c].x*a[b].y)-(a[d].x*a[c].y))>0;
}

double dist(double x1,double y1,double x2,double y2) { //计算两点间的距离
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main() {
	rint i;
	scanf("%d",&n);
	for (i=1; i<=n; ++i) {
		scanf("%lf%lf",&a[i].x,&a[i].y);
		if (a[i].y<miny) { //寻找最下方的点
			miny=a[i].y;
			minx=a[i].x;
		}
	}
	sort(a+1,a+1+n,cmp); //极角排序
	st[1]=1;
	st[2]=2;
	top=2; //将两个点加入栈中
	for (i=3; i<=n; ++i) { //扫描
		while (!check(st[top-1],st[top],i)) top--;
		st[++top]=i;
	}
	for (i=2; i<=top; ++i) //计算答案
		ans+=dist(a[st[i-1]].x,a[st[i-1]].y,a[st[i]].x,a[st[i]].y);
	ans+=dist(a[st[top]].x,a[st[top]].y,a[1].x,a[st[1]].y);
	double area=0;
	for(i=1;i<top;i++){
		area+=(a[st[i]].x*a[st[i+1]].y-a[st[i+1]].x*a[st[i]].y);
	} 
	area+=(a[st[top]].x*a[st[1]].y-a[st[1]].x*a[st[top]].y);
	area/=2;
	printf("%.2lf %.2lf",ans,area);
	return 0;
}

---

题目来源

北航OJ

---

---