UCF (summer team competition II)

A . T9 Craziness( Selection structure )

Carelessness ：

Give the letter corresponding to each number , Give the existing dictionary string , Give multiple groups of decoding , If each decoding in a group has only one corresponding word , Then translate the sentence , If there is decoding that cannot be translated, it will not be translated , If there is decoding corresponding to multiple words, the total number of cases will be output ;

Ideas

First decode the dictionary string , Use one map Keep correspondence , With another map Write down the The number of words corresponding to each decoding , Then judge ;

#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;// The mapping relationship 
		mp2[ss]++;// Number 
   }
   	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())// There is no corresponding word for decoding 
			{
    
				flag=3;
				break;
			}
			else
			{
    
				if(mp2[s]!=1)// One decoding corresponds to multiple words 
				{
    
					ans*=mp2[s];
// cout<<mp2[s]<<endl;
					flag=2;
				}
			}
			ve.push_back(mp1[s]);
		}
		
		if(flag==1)// Case one 
		{
    
			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)// The second case 
		{
    
			printf("Message #%d: there are %lld possible messages\n\n",++cnt,ans);
		}
		else// Last case 
		{
    
			printf("Message #%d: not a valid text\n\n",++cnt);
		}
		
	}
   
}

C . Lawn Maintenance( Computational geometry )

Carelessness

It is the board problem of calculating the area of polygons in geometry , Review the board

The main idea is to calculate the area of the triangle formed by each edge and the origin according to triangulation , Then simply add ;

According to the geometric meaning of vector cross multiplication vector A And vector B Vector product of ( Cross product ) It's a vector , Its modulus is equal to A and B The area of the parallelogram made , Finding the cross product divided by two is the area of the triangle ; The sum of the directed areas of all triangles is the total area .

det  Find the cross product of determinant 

double area(int n)
{
    
	double ans1=0;
	for(int i=2;i<=n;i++) ans1+=(double)det(a[i],a[i-1])/2.0;// Determinant to find the difference product 
	ans1+=(double)det(a[1],a[n])/2.0;//
	if(ans1>0.0) return ans1;
	else return -ans1;// Take positive number 
}

#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);// Notice the conversion from floating point number to integer 
	   
	   if(anss%1000==0) cout<<ans/1000;
	   else cout<<anss/1000+1;
	   
	   cout<<" bag(s)\n\n";
   }
   
}

E . Waterford Wackiness( simulation )

The question ：

n A car passed the intersection , give n Direction of vehicle , Time from the previous car in the same direction , And number , Print out the sequence of all vehicles passing the intersection ;

Ideas ：

With 0 Time as reference , Calculate the relative time of all vehicles passing the intersection , Sorting can be

#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;
   }
}

Attached is a reference blog
Find the area of a polygon