Shen Huang's Blog
0%

Posted on Edited on

这题是作为Njust第二场新生赛A，比赛时先写了，写了一半就写不下去了，觉得太恶心，之后才好好写的，写完之后就是1Y

主要就是一个搜索，穷举答案，当有十一个人的时候判断一下就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/* a.cpp 2013.07.29 新生赛A 题
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define print() cout<<"------"<<endl
using namespace std;
int maps[30][30];//一开始不小心写成bool类型了了
struct node{
	int id,w;
}p[30];
map<string,int>m;
map<string,int>m2;
int num[30];
bool vis[30];
int ans;
void dfs(int src,int go,int de,int mid,int st)//go=1,de=4,mi=4,st=2
{
	int ret=0,cnt=0;
	if(go==1&&de==4&&mid==4&&st==2) {
		for(int i=0;i<23;i++){
			if(vis[i]){
				cnt++;
				ret+=p[i].w;
				for(int j=i+1;j<23;j++)
					if(vis[j]){
					ret+=maps[i][j];
				}
			}
		}
		ans=max(ans,ret);
		return ;
	}
	for(int i=src;i<23;i++)
	{
		if(!vis[i])
		{
			if(p[i].id==1&&go>=1) continue;
			if(p[i].id==2&&de>=4) continue;
			if(p[i].id==3&&mid>=4) continue;
			if(p[i].id==4&&st>=2) continue;
			vis[i]=1;
			if(p[i].id==1){
				dfs(i,go+1,de,mid,st);
			}
			if(p[i].id==2){
				dfs(i,go,de+1,mid,st);
			}
			if(p[i].id==3){
				dfs(i,go,de,mid+1,st);
			}
			if(p[i].id==4){
				dfs(i,go,de,mid,st+1);
			}
			vis[i]=0;
		}
	}
}

int main(){
	int t,n,va;
	string s2,s1;
	s2="goalkeeper";
	m[s2]=1;//1个
	s2="defender";
	m[s2]=2;//4
	s2="midfielder";
	m[s2]=3;//4
	s2="striker";
	m[s2]=4;//2
	while(cin>>s1)
	{
		ans=-0x7ffffff;
		memset(maps,0,sizeof(maps));
		m2.clear();
		m2[s1]=0;
		memset(num,0,sizeof(num));
		scanf("%d",&va);
		cin>>s2;
		p[0].w=va;
		p[0].id=m[s2];
		num[m[s2]]++;
		for(int i=1;i<23;i++)
		{
			cin>>s1;
			scanf("%d",&va);
			cin>>s2;
			m2[s1]=i;
			p[i].w=va;
			p[i].id=m[s2];
			num[m[s2]]++;
		}
		int M;
		scanf("%d",&M);
		for(int i=0;i<M;i++)
		{
			cin>>s1>>s2>>va;
			maps[m2[s2]][m2[s1]]=va;
			maps[m2[s1]][m2[s2]]=va;
		}
		if(num[1]<1) {
			printf("impossiblen");
			continue;
		}
		if(num[2]<4){
			printf("impossiblen");
			continue;
		}
		if(num[3]<4){
			printf("impossiblen");
			continue;
		}
		if(num[4]<2){
			printf("impossiblen");
			continue;
		}
			memset(vis,0,sizeof(vis));
			dfs(0,0,0,0,0);
		printf("%dn",ans);
	}

	return 0;
}

Posted on Edited on

学习了一下三维的计算几何的直线距离，注意平行是另外的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/* HDU 4617 多校第二场 三维几何题 G
 * 告诉你圆心以及圆上的两个点，圆柱是无限长的
 * 也就是说求圆柱中心的那个直线，枚举每个圆柱之间的距离
 * 如果小于
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define maxn 33
#define EPS 1e-8
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
struct point{	
	double x,y,z;
	point (){}
	point (double x,double y,double z):x(x),y(y),z(z){}
	point operator + (point a) {return point(x+a.x,y+a.y,z+a.z);}
	point operator - (point a) {return point(x-a.x,y-a.y,z-a.z);}
	point operator * (double a) {return point(x*a,y*a,z*a);}
	point operator / (double a) {return point(x/a,y/a,z/a);}
}pt[maxn][3],p[maxn],nor[maxn];
double r[maxn];
inline int dcmp(double x){ return (x>EPS)-(x<-EPS);}
inline double dot(point a,point b) {return a.x*b.x+a.y*b.y+a.z*b.z;}
inline point cross(point a,point b) {
	return point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
inline double veclen(point x) {return sqrt(dot(x,x));} 
inline double ptdis(point a,point b){return veclen(a-b);}
inline point vecunit(point x) {return x/veclen(x);}
bool lldis(point p1,point u,point p2,point v,double &s){//判断空间两条直线是否平行，平行则输出0，否则～
	double b=dot(u,u)*dot(v,v)-dot(u,v)*dot(u,v);
	if(dcmp(b)==0) return false;
	double a=dot(u,v)*dot(v,p1-p2)-dot(v,v)*dot(u,p1-p2);
	s=a/b;
	return true;
}
double p21(point p,point a,point b){//求平行直线距离
	point v1= b - a ,v2 =p -a;
	return veclen(cross(v1,v2))/veclen(v1);
}
int main(){
	int T,n;
	scanf("%d",&T);
	while(T--&&scanf("%d",&n))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<3;j++){
				scanf("%lf%lf%lf",&pt[i][j].x,&pt[i][j].y,&pt[i][j].z);
				p[i]=pt[i][0];
				r[i]=veclen(pt[i][0]-pt[i][1]);
				nor[i]=cross(pt[i][1]-pt[i][0],pt[i][2]-pt[i][0]);
			}
		double ans=1e10;
		bool touch=0;
		for(int i=0;i<n&&!touch;i++)
			for(int j=i+1;j<n&&!touch;j++)
			{
				double s,t,dis;
				if(lldis(p[i],nor[i],p[j],nor[j],s)){
					lldis(p[j],nor[j],p[i],nor[i],t);
					point a=p[i]+nor[i]*s;
					point b=p[j]+nor[j]*t;
					dis=ptdis(a,b);
				}else dis=p21(p[i],p[j],p[j]+nor[j]);
				if(dis<=r[i]+r[j]) touch=1;
				ans=min(ans,dis-r[i]-r[j]);

			}
		if(touch) cout<<"Lucky"<<endl;
		else printf("%.2fn",ans);
	}
	return 0;
}

Posted on Edited on

别人问为什么TLE了，然后就写了一个，发现几乎一模一样，也许是他名字起的不好听吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/* POJ 2362 简单DFS 加 简单减枝
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
#define maxn 100
int st[maxn];
int n,side;
bool vis[maxn];
bool cmp(int a,int b)
{
	return a>b;
}
bool dfs(int bian,int len,int id)//边数，目前长度，现在的线段编号
{
	if(bian==3) return 1;
	vis[id]=1;
	for(int i=id;i<n;i++)
		if(!vis[i]){
			if(len+st[i]>side) continue;
			vis[i]=1;
			if(len+st[i]==side&&dfs(bian+1,0,0))
					return 1;
			if(len+st[i]<side&&dfs(bian,len+st[i],i))
				return 1;
			vis[i]=0;
	}
	return 0;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		int total=0;
		for(int i=0;i<n;i++)
		{	
			scanf("%d",&st[i]);
			total+=st[i];
		}
		if(total%4!=0){
			printf("non");
			continue;
		}
		side=total/4;
		sort(st,st+n,cmp);
		if(st[0]>side){
			printf("non");
			continue;
		}
		if(dfs(0,0,0)){
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}

Posted on Edited on

终于有自己的博客了

相比于http://blog.163.com/chen3221@126/

之前这个更加自由了，之前那个竟然坑爹地有字数限制，以后代码之类就放这里了

还有今天又丢钥匙加校园卡了，又丢了，无奈~希望明天能找到