UCF(暑期团队赛二)

A . T9 Craziness(选择结构)

大意：

给出每个数字对应的字母，给出已存在的字典字符串，给出多组译码，如果一组译码中的每个译码都只有一个对应单词，则译出句子，若存在译码无法翻译则不翻译，若有译码对应多个单词则输出总共的情况数量；

思路

先把字典字符串译码，用一个 map 存好对应关系 ，用另一个 map 记下 每个译码对应单词的数量，然后判断即可；

#include<bits/stdc++.h>
using namespace std;

int n,m;
string s;
int cnt;

typedef long long ll;

map<string,string>mp1;
map<string,int>mp2;
vector<string>ve;

int main()
{
   cin>>n;
   
   for(int i=1;i<=n;i++)
   {
   		cin>>s;
   		int len=s.size();
   		string ss="";
   		for(int i=0;i<len;i++)
   		{
   			if(s[i]=='a'||s[i]=='b'||s[i]=='c') ss+='2';
   			if(s[i]=='d'||s[i]=='e'||s[i]=='f') ss+='3';
   			if(s[i]=='g'||s[i]=='h'||s[i]=='i') ss+='4';
   			if(s[i]=='j'||s[i]=='k'||s[i]=='l') ss+='5';
   			if(s[i]=='m'||s[i]=='n'||s[i]=='o') ss+='6';
   			if(s[i]=='p'||s[i]=='q'||s[i]=='r'||s[i]=='s') ss+='7';
   			if(s[i]=='t'||s[i]=='u'||s[i]=='v') ss+='8';
   			if(s[i]=='w'||s[i]=='x'||s[i]=='y'||s[i]=='z') ss+='9';
		}
		mp1[ss]=s;//映射关系
		mp2[ss]++;//数量
   }
   	cin>>m;
	getchar();
	getchar();
//	getchar();
//	getchar();
	
	for(int i=1;i<=m;i++)
	{
		int flag=1;
		ll ans=1;
		ve.clear();
		getline(cin,s);
//		cout<<s<<endl;

		stringstream ss(s);
		while(ss>>s)
		{
			if(mp1.find(s)==mp1.end())//出现译码无对应单词
			{
				flag=3;
				break;
			}
			else
			{
				if(mp2[s]!=1)//一个译码对应多个单词
				{
					ans*=mp2[s];
//					cout<<mp2[s]<<endl;
					flag=2;
				}
			}
			ve.push_back(mp1[s]);
		}
		
		if(flag==1)//第一种情况
		{
			printf("Message #%d: ",++cnt);
			int len=ve.size();
			for(int i=0;i<len;i++)
			{
				if(i!=len-1) cout<<ve[i]<<" ";
				else cout<<ve[i]<<endl;
			}
			cout<<endl;
		}
		else
		if(flag==2)//第二种情况
		{
			printf("Message #%d: there are %lld possible messages\n\n",++cnt,ans);
		}
		else//最后一种情况
		{
			printf("Message #%d: not a valid text\n\n",++cnt);
		}
		
	}
   
}
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

C . Lawn Maintenance(计算几何)

大意

就是计算几何求多边形面积的板子题 ，复习一下板子

主要思路是根据三角剖分求出每一条边和原点构成的三角形的面积，然后简单相加；

根据矢量叉乘的几何意义 矢量A与矢量B的矢量积(叉积)是一个矢量，其模等于由A和B作成的平行四边形的面积，求出叉积除二就是三角形面积；所有三角形的有向面积相加就是总面积。

det 行列式求叉积
1

double area(int n)
{
	double ans1=0;
	for(int i=2;i<=n;i++) ans1+=(double)det(a[i],a[i-1])/2.0;//行列式求差积
	ans1+=(double)det(a[1],a[n])/2.0;//
	if(ans1>0.0) return ans1;
	else return -ans1;//取正数
}
1
2
3
4
5
6
7
8

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point{
	int x,y;
}a[11];

double ans;
int n,m,t;
int cnt;

double area(int n)
{
	double ans1=0;
	for(int i=2;i<=n;i++) ans1+=(double)(a[i].x*a[i-1].y-a[i].y*a[i-1].x)/2.0;
	ans1+=(double)(a[1].x*a[n].y-a[1].y*a[n].x)/2.0;
	if(ans1>0.0) return ans1;
	else return -ans1;
}

int main()
{
   while(cin>>t&&t)
   {
	   ans=0.0;
	   for(int i=1;i<=t;i++)
	   {
	   		cin>>a[i].x>>a[i].y;
	   }
	   ans+=area(t);
	   
	   cin>>m;
	   for(int i=1;i<=m;i++)
	   {
	   		cin>>a[i].x>>a[i].y;
	   }
	   ans-=area(m);
	   
	   cin>>n;
	   while(n--)
	   {
	   		cin>>m;
	   		for(int i=1;i<=m;i++)
	   		{
	   			cin>>a[i].x>>a[i].y;
	   		}
	   		ans-=area(m);
	   }
	   
	   printf("Lawn #%d: buy ",++cnt);
	   
	   int anss=ceil(ans);//注意浮点数到整数的转换
	   
	   if(anss%1000==0) cout<<ans/1000;
	   else cout<<anss/1000+1;
	   
	   cout<<" bag(s)\n\n";
   }
   
}
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

E . Waterford Wackiness(模拟)

题意：

n辆车过十字路口，给出 n 辆车的方向 ， 距同方向前辆车的时间，和编号，打印出所有车辆经过路口的顺序；

思路：

以 0 时刻为参照 ， 算出所有车经过路口的相对时间，排序即可

#include<bits/stdc++.h>
using namespace std;

struct node{
	int id;
	int sum;
}a[1001];

char c;
int sumn,sums,sume,sumw;
int n,t;
int cnt;

bool cmp(node a,node b)
{
	return a.sum<b.sum;
}

int main()
{
   cin>>t;
   
   while(t--)
   {
		sumn=sums=sume=sumw=0;
		cin>>n;
		
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].id>>c>>a[i].sum;
			if(c=='E') sume+=a[i].sum,a[i].sum=sume;
			if(c=='W') sumw+=a[i].sum,a[i].sum=sumw;
			if(c=='N') sumn+=a[i].sum,a[i].sum=sumn;
			if(c=='S') sums+=a[i].sum,a[i].sum=sums;
		}
		
		sort(a+1,a+1+n,cmp);
		
		cout<<"Data set #"<<++cnt<<":"<<endl;
		
		for(int i=1;i<=n;i++) 
		{
			cout<<"Car #"<<a[i].id<<endl;
		}
		cout<<endl;
   }
}
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

附上参考的博客
求多边形面积