总结：本次训练赛考到的算法较少，大多为模拟题和思维题。但是也是有些地方值得去反思与总结。
题目描述
Professor Boolando can only think in binary, or more specifically, in powers of 2. He converts any number you give him to the smallest power of 2 that is equal to or greater than your number. For example, if you give him 5, he converts it to 8; if you give him 100, he converts it to 128; if you give him 512, he converts it to 512.
The Problem:
Given an integer, your program should binarize it.
输入描述:
The first input line contains a positive integer,n, indicating the numberof values to binarize. The values are on the followingninput lines, one per line. Each input will contain an integer between2 and 100,000 (inclusive).
输出描述:
At thebeginning of each testcase, output “Inputvalue:v”wherevis the input value. Then,on the next output line, print the binarized version. Leave a blank line after the output for each test case.
示例1
输入
3
900
16
4000
输出
Input value: 900
1024
Input value: 16
16
Input value: 4000
4096
水题，签到题，直接上代码。
#include<iostream>
using namespace std;
int a[100000];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
int t = 1;
while (t<a[i])
{
t *= 2;
}
cout << "Input value: " << a[i] << endl;
cout << t << endl;
cout << endl;
}
return 0;
}
题目描述
According to the national statistics, a teenager sends/receives 100+ text messages a day. Dr. Orooji’s teenage children are no exception but the problem is Dr. O (an old-fashioned, face-to- face communicator) has difficulty reading text messages full of abbreviations (short-hands) sent to him by his children. Dr. O needs your help reading these text messages.
The Problem:
Given the list of abbreviations and a paragraph, you are to expand the text (paragraph) so that Dr. O can read it easily.
输入描述:
The first input linecontains an integer,n (1 ≤ n ≤ 20),indicating the number of abbreviations. Theseabbreviations are on the followingninputlines, one per line. Each input linestarts in column 1 and containsan abbreviation (1-5 characters, consisting of only lowercaseletters and/or digits). The abbreviation is followed by exactly one space, and this isfollowed by the expanded version ofthe abbreviation (1-50 characters, consisting of only lowercase letters and spaces; assume the expandedversion does not start or end with aspace and contains no multiple consecutive spaces between words).Assume that all abbreviations are distinct, i.e., no duplicates.
The list of abbreviations isfollowed by a positive integer,p,indicating the number of input lines containingthe paragraph to be expanded. Theparagraph is on the followingpinputlines. Assume these input linesdo not exceed column 50, donot start or end with a space, and each line contains at least one word. The paragraph will contain only lowercaseletters, digits, and spaces. Assume that there will not be multipleconsecutive spaces in theinput paragraph.
A word is defined as aconsecutive sequence of letters/digits. Assume that a word will be entirely on oneinput line, i.e., a word isnot broken over two or more lines.
输出描述:
Each line of the inputparagraph must be on one line of output. Theinput line must be printed in theoutput exactly the same (spacing). Theonly exception is that each abbreviation must be replaced by its expanded version, i.e., when an abbreviation isfound in the input, its expanded version must beoutput.
Note that an abbreviationmust match a word completely and not just part of a word. For example,if u is an abbreviation for “you”, then u must appear as a word by itself in the paragraph
in order to be replaced,i.e., if the abbreviation is part of a word in the paragraph (e.g.,the paragraph containsthe word buy or ugly or you),the u in these words should not be replaced.
示例1
输入
8
g2g got to go
g good
c see
l8 late
l8r later
d i am done
u you
r are
6
hi
how r u
you tell me
you are l8
d
c u l8r
输出
hi
how are you
you tell me
you are late
i am done
see you later
不难的模拟题，但是需要注意带空格的字符串的输入方式和处理方式
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>
using namespace std;
struct A
{
string s,v;
bool operator<(A &b)
{
return s<b.s;
}
};
vector<A> a;
int main()
{
string x,y;
int T;
cin>>T;
while(T--)
{
cin>>x;
getchar();
getline(cin,y);
a.push_back({x,y});
}
sort(a.begin(),a.end());
cin>>T;
while(cin>>x)
{
for(int i = 0 ; i<a.size();i++)
{
if(x==a[i].s)
{
cout<<a[i].v;
break;
}
else if(i==a.size()-1)cout<<x;
}
cout<<(char)getchar();
}
}
题目描述
One of the cool UCF CS alumni is Dr. Greg, The Palindrome Tipper. A palindrome is a string
that reads the same forward and backward, e.g., madam, abba, 3, 44, 525.
One cool thing about Dr. Greg is that he leaves at least 20% tip when he eats out, e.g., if the meal is 30, Dr. Greg leaves 30, Dr. Greg leaves 6 (30*.20) for tip. If the tip (20%) is not a whole dollar amount, he rounds up the tip to make it a whole number. For example, if the meal is 12, a 20% tip would be12,a202.40 (12*0.20) but Dr. Greg would leave $3 for tip.
Another cool thing about Dr. Greg is that he is a palindrome guru. If his total bill (meal plus tip) is not a palindrome, he will increase the total (by adding to the tip) to make the total a palindrome. He will, of course, add the minimum needed to make the total a palindrome.
The Problem:
Given Dr. Greg’s meal cost, your program should determine the tip amount for him (according to his rules) and the total bill.
输入描述:
The first input line contains a positive integer, n, indicating the number of times Dr. Greg ate out. The meal costs are on the following n input lines, one per line. Each input will contain an integer between 5 and 10000 (inclusive).
输出描述:
At the beginning of each test case, output “Input cost: c” where c is the input cost. Then, on the next output line, print the tip amount and the total bill, separated by one space. Leave a blank line after the output for each test case.
示例1
输入
2
12
84
输出
Input cost: 12
10 22
Input cost: 84
17 101
模拟题，依然没有太多的难度
#include<iostream>
using namespace std;
bool tool(int n)
{
int i = n;
int m = 0;
while (i > 0)
{
m = m * 10 + i % 10;
i /= 10;
}
return m == n;
}
int main()
{
int m;
int a[100000];
cin >> m;
for (int i = 0; i < m; i++)
cin >> a[i];
for(int i=0;i<m;i++)
{
double j = a[i] * 0.2;
int k = a[i] / 5;
if (j > k)
k = k + 1;
while (!tool(k + a[i]))
{
k++;
}
cout << "Input cost: " << a[i] << endl;
cout << k << ' ' << a[i] + k << endl;
cout << endl;
}
return 0;
}
题目描述
Soccer fever has gripped the world once again, and millions of people from dozens of countries
will be glued to their TV sets for the World Cup. Being an enterprising sort, you’ve started up your own internet World Cup Soccer Channel for streaming matches online. Recently you came up with the idea of filling up the time between matches by having a couple of ‘experts’ offer critical analysis of games. For this purpose, you have devised a unique ranking system for soccer teams, which you must now implement.
The Problem:
Given a list of teams and a list of match scores, you must compute several quantities for each team. These are: the total number of goals scored over all their games, the total number of goals scored against them (goals allowed, for short), the number of wins, draws and losses, and the number of points scored so far. Points are to be computed as follows: winning a match nets a team 3 points, losing gets them nothing. In the event of a tie, both teams get 1 point.
In addition to this, you must order the teams correctly according to your new system. Teams are ordered according to points, from highest to lowest. In the event of a tie in points, the team that has a higher goal difference comes first. The goal difference is defined as the total number of goals scored by the team minus the total number of goals scored against them.
If there is still a tie (i.e., two or more teams have the same points and the same goal differences), the team with higher total goals scored comes first. If even this is tied, the team whose name comes first in alphabetical order goes first.
输入描述:
The first input line contains a positive integer, n, indicating the number of data sets to be processed. The first line of each data set consists of two positive integers T (T ≤ 30) and G (G ≤
400) – the number of teams in this group and the total number of games played by them. The next line contains T unique names separated by single spaces. Each name is a single uppercase word with no more than 15 characters.
Each of the next G input lines will contain the results of a match. Each line is of the form
<country_1> <score_1> <country_2> <score_2>. For example, “Greece 2 Nigeria 1” indicates that Greece and Nigeria played a game with score 2-1. All four terms will be separated by single spaces.
输出描述:
At the beginning of output for each data set, output “Group g:” where g is the data set number, starting from 1. Next you should print a single line for each team, ordering teams as mentioned above. For each team, the line you print should be of the form “<name> <points> <wins> <losses> <draws> <goals scored> <goals allowed>”. These items should be separated by single spaces. Leave a blank line after the output for each data set.
示例1
输入
2
2 1
KASNIA LATVERIA
KASNIA 0 LATVERIA 1
4 6
ENGLAND USA ALGERIA SLOVENIA
ENGLAND 1 USA 1
ALGERIA 0 SLOVENIA 1
SLOVENIA 2 USA 2
ENGLAND 0 ALGERIA 0
SLOVENIA 0 ENGLAND 1
USA 1 ALGERIA 0
输出
Group 1:
LATVERIA 3 1 0 0 1 0
KASNIA 0 0 1 0 0 1
Group 2:
USA 5 1 0 2 4 3
ENGLAND 5 1 0 2 2 1
SLOVENIA 4 1 1 1 3 3
ALGERIA 1 0 2 1 0 2
需要一点小技巧的模拟题，如果能够掌握结构体的使用以及sort函数的排序函数的重写的话，这题的解决也就是时间问题。是一道比较考验基本功的模拟题。
#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<utility>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
int a;
struct team
{
string name;
int p=0, w=0, l=0, d=0, gs=0, ga=0;
};
/*<<' '*/
void show(team t)
{
cout << t.name << ' ' << t.p << ' ' << t.w << ' ' << t.l << ' ' << t.d << ' ' << t.gs << ' ' << t.ga << endl;
}
bool cmp(team a, team b)
{
if (a.p != b.p)//比分
{
return a.p > b.p;
}
else
{
if ((a.gs - a.ga) != (b.gs - b.ga))//比差
{
return (a.gs - a.ga) > (b.gs - b.ga);
}
else
{
if (a.gs != b.gs)//比进球
{
return a.gs > b.gs;
}
else
{
int cnt = 0;
while (a.name[cnt] == b.name[cnt])
{
cnt++;
}
return a.name[cnt] < b.name[cnt];
}
}
}
}
void solve()
{
cin >> a;
for(int k=1;k<=a;k++)
{
int t, n;
cin >> t >> n;
team te[35];
for (int i = 1; i <= t; i++)
cin >> te[i].name;
for (int i = 1; i <= n; i++)
{
int s1,s2;
string n1, n2;
cin >> n1 >> s1 >> n2 >> s2;
for (int j = 1; j <= t; j++)
{
if (n1 == te[j].name)
{
te[j].gs += s1;
te[j].ga += s2;
int r = s1 - s2;
if (r > 0)
{
te[j].p += 3;
te[j].w += 1;
}
if (r == 0)
{
te[j].p += 1;
te[j].d += 1;
}
if (r < 0)
{
te[j].l += 1;
}
}
if (n2 == te[j].name)
{
te[j].gs += s2;
te[j].ga += s1;
int r = s2 - s1;
if (r > 0)
{
te[j].p += 3;
te[j].w += 1;
}
if (r == 0)
{
te[j].p += 1;
te[j].d += 1;
}
if (r < 0)
{
te[j].l += 1;
}
}
}
}
sort(te+1, te+t+1, cmp);
cout << "Group " << k << ":" << endl;
for (int i = 1; i <= t; i++)
{
show(te[i]);
}
cout << endl;
}
}
int main()
{
solve();
return 0;
}
Recently, a job for an algorithms specialist opened up at NIH. You never thought you’d be using your expertise in algorithms to save lives, but now, here is your chance! While the doctors are very good in carrying out medical research and coming up with better cures for diseases, they are not so good with numbers. This is where you come in.
You have been tasked to allocate money for all disease research at NIH. The interesting thing about disease research is that the number of lives saved doesn’t linearly increase with the amount of money spent, in most cases. Instead, there are “break-points”. For example, it might be the case that for disease A, we have the following break-points:
Research Funding
Lives Saved
10 million
5
50 million
100
100 million
1000
250 million
1100
If you spend more money than one breakpoint and less than another, the number of lives saved is equal to the amount saved for the previous breakpoint. (In the above example, if you spent 150 million, you’d still only save 1000 lives, and if you spent any amount more than150million,you’dstillonlysave1000lives,andifyouspentanyamountmorethan250 million, you’d still save 1100 lives.)
The doctors have figured out charts just like this one for all the diseases for which they do research. Given these charts, your job will be to maximize the number of lives saved spending no more than a particular budget.
The Problem:
Given several charts with information about how much has to be spent to save a certain number of lives for several diseases and a maximum amount of money you can spend, determine the maximum number of lives that can be saved.
输入描述:
The first input line contains a positive integer, n (n ≤ 100), indicating the number of budgets to consider. The first line of each budget contains two positive integers, d (d ≤ 10), representing the number of diseases for which there is data and B (B ≤ 100000), the total budget, in millions of dollars. The following d lines contain information about each of the d diseases. Each of these lines will contain exactly four ordered pairs of positive integers separated by spaces. Each pair will represent a dollar level (in millions) followed by the number of lives saved for that dollar
level of funding. Each of the pairs will be separated by spaces as well. Each of these values will be less than or equal to 100,000. Assume that the dollar levels on an input line are distinct and in increasing order, and that the number of lives saved on an input line are also distinct and in increasing order.
输出描述:
For each test case, just output a line with the following format:
Budget #k: Maximum of x lives saved.
where k is the number of the budget, starting at 1, and x is the maximum number of lives saved in that budget.
Leave a blank line after the output for each test case.
示例1
输入
3
2 2000
10 5 50 100 100 1000 250 1100
100 1 200 2 300 3 1900 1000
3 100
10 100 40 200 70 300 100 500
5 1 25 2 35 3 50 4
200 10000 300 20000 400 30000 500 40000
1 10
100 2 200 3 300 5 400 6
输出
Budget #1: Maximum of 2000 lives saved.
Budget #2: Maximum of 500 lives saved.
Budget #3: Maximum of 0 lives saved.
不难看出，这是一道01背包问题的变种题目，因此我们可以用动态规划的算法去完成此题。
#include<iostream>
#include<cstring>
using namespace std;
int dp[1000010][13];//在前i个基础上，花费j元的max
int v[13][5];
int s[13][5];
int n, m;
int main()
{
int T;
cin >> T;
for(int ii = 1; ii <= T; ii++)
{
memset(dp, 0, sizeof dp);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 4; j++)
{
scanf("%d%d", &s[i][j], &v[i][j]);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= 0; j--)
{
dp[j][i] = dp[j][i - 1];
for (int k = 1; k <= 4; k++)
if (j + s[i][k] <= m)
dp[j][i] = max(dp[j][i], dp[j + s[i][k]][i - 1] + v[i][k]);
else break;
}
}
printf("Budget #%d: Maximum of %d lives saved.\n",ii,dp[0][n]);
if(ii!=T)printf("\n");
}
}
题目描述
After two years of sharing a bedroom with you in a college dorm, Jeff finally has his own room. Excited about inviting girls over to his room, he ponders over what decorations the fairer sex will enjoy.1 He decides upon setting up a “fake” planetarium with a black ceiling and glow in the dark stars that form constellations. Unfortunately, in his haste, he has made several “errors” in setting up his constellations. See, everyone knows that constellations don’t have cycles in them. Instead, whenever we visually connect the stars together with lines, a tree is always formed. (A cycle is formed when you can start at a star and, using connections, go to one or more other stars and then end up at the original star.)
Since you were Jeff’s roommate for two years, you figure you’ll help him fix his constellations. Your job will be twofold: to count the number of constellations Jeff has, and to report how many of them have cycles and need to be fixed. A constellation consists of multiple stars that are all connected to one another (directly or indirectly). A constellation that needs fixing is simply one that has a cycle.
The Problem:
Given several configurations of stars and connections between stars, determine how many constellations are defined in each configuration and how many need fixing.
输入描述:
The first input line contains a positive integer, n (n ≤ 100), indicating the number of night skies to consider. The first line of each night sky contains two positive integers, s (s ≤ 1000), representing the number of stars for this night sky, and c (c ≤ 10000), representing the total number of connections between pairs of stars for this night sky. Each of the following c input lines contains two distinct positive integers representing a single connection between two stars. The stars in each test case will be numbered 1 through s, inclusive. A connection is considered bidirectional, thus, if a is connected to b, b is connected to a. Assume that all connections in a data set are distinct, i.e., no duplicates. Also assume that there will never be a connection from a star to itself.
1 This is based on a true story. The person who is the inspiration for this story did, in fact, major in Planetary Science and make his room’s ceiling a relatively accurate depiction of the night sky, as seen in Boston circa 1995.
输出描述:
For each test case, just output a line with the following format:
Night sky #k: X constellations, of which Y need to be fixed.
where k is the number of the night sky, starting at 1, X is the total number of constellations described in that night sky, and Y is how many of those constellations contain a cycle.
Leave a blank line after the output for each test case.
示例1
输入
3
5 4
1 2
1 3
2 3
4 5
8 5
1 2
3 4
6 7
6 8
8 7
3 2
1 2
1 3
输出
Night sky #1: 2 constellations, of which 1 need to be fixed.
Night sky #2: 3 constellations, of which 1 need to be fixed.
Night sky #3: 1 constellations, of which 0 need to be fixed.
说明
Note:In the second example, star number 5 is not connected to any other stars. This staron its own is NOT counted as a constellation, leaving only {1,2}, {3,4}and {6,7,8} as constellations, of which only the last one needs tobe fixed.
本题所涉及的知识点为并查集，考察并查集的基本用法以及检查重边。如果对并查集的理解足够深刻的话那么这道题也不会很难。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1010];
int ans[1010];
int n, m;
int find(int s)
{
if (f[s] == s)return s;
return f[s] = find(f[s]);
}
int main()
{
int T;
cin >> T;
int x, y;
int a1, a2;
for (int ii = 1; ii <= T; ii++)
{
scanf("%d%d", &n, &m);
a1 = a2 = 0;
for (int i = 1; i <= n; i++)
{
f[i] = i;
}
memset(ans, 0, sizeof ans);
while (m--)
{
scanf("%d%d", &x, &y);
x = find(x);
y = find(y);
if (x == y)
ans[x] = -1;
else f[x] = y;
}
for (int i = 1; i <= n; i++)
{
int t = find(i);
if (ans[i] == -1)
{
ans[i] = 0;
ans[t] = -1;
}
else if (ans[t] != -1)ans[t]++;
}
for (int i = 1; i <= n; i++)
{
if (ans[i] == -1)a2++;
if (ans[i]&&ans[i]!=1)a1++;
}
printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n"
, ii, a1, a2);
if (ii != T)printf("\n");
}
}
题目描述
Plate spinning is a circus act where a person spins various objects(usually plates and bowls) on poles without them falling off. It involves spinning an object and then returning back to the object in order to add additional speed to prevent it from falling off the pole.
In this problem you will simulate plate spinning where the plates are placed in a circular arrangement (much like the picture to the right). You must determine whether Chester the Clown will be able to maintain the plates spinning or whether one or more plates will end up falling off poles.
The Problem:
Given the number of poles/plates in a circular arrangement and the speed up to which Chester the Clown spins the plates (in degrees per second), determine if he can maintain the act or if plates will fall. For this problem, we will assume that plates degrade (slow down) at a constant rate of 5-degrees-per-second per second and that Chester can move from one pole to any other pole in 0.5 seconds. In addition, assume that Chester can spin up a plate with zero time cost.
A plate falls off when its rate is zero. However, if Chester arrives at a plate exactly at the same time the rate reaches zero, Chester will spin the plate and prevents it from falling, i.e., the rate must reach zero before Chester arrives for the plate to fall.
输入描述:
The first line of the input will be a single positive integer, a, representing the number of acts to evaluate. Each of the following a lines will represent a single act and will contain two positive integers, n and p, separated by a single space, where n represents the number of poles (1 ≤ n ≤ 15) and p represents the speed up to which Chester spins a plate (0 < p ≤ 100) in degrees per second. At the very beginning of each act, all plates are initially spinning at this speed, and he is currently at a plate in the circle (he can choose which plate to start at in order to maximize his chance of success).
输出描述:
For each circus act, output a header “Circus Act i:” on a line by itself where i is the number of the act (starting with 1). Then, on the next line, output “Chester can do it!” if Chester can maintain the act, or output “Chester will fail!” if one or more plates will fall. Leave a blank line after the output for each test case.
示例1
输入
3
2 10
5 7
2 12
输出
Circus Act 1:
Chester can do it!
Circus Act 2:
Chester will fail!
Circus Act 3:
Chester can do it!
一道很简单的思维模拟题，但是也为大家挖下了一个坑，那就是当盘子数量为1时的特判，如果忽略了这一点就会导致结果出错。
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int T;
cin>>T;
int n,p;
for(int ii = 1;ii<=T;ii++)
{
scanf("%d%d",&n,&p);
printf("Circus Act %d:\n",ii);
if(n==1||n*5<=p*2)printf("Chester can do it!\n");
else printf("Chester will fail!\n");
if(ii!=T)printf("\n");
}
}
H题-The Eternal Quest for Caffeine
题目描述
Like most engineering students, Jason relies on caffeine, soda in particular, to get him through long nights in the lab. He’s not too picky about the brand; as long as it’s fizzy, loaded with caffeine, and not the “diet” version, he’s happy. When the new Harris Engineering Center opened on the UCF Campus, he was pleased to see a soda machine on every floor. Not just any soda machine, either. These machines are the fancy kind that display all of the soda stock arranged in rows stacked on top of each other (like most snack machines). When a soda is purchased, a conveyor belt rises to the correct row, where the soda is surgically picked up by a robotic clasp that can travel left and right on the conveyor. The conveyor then descends to the vending slot, where the clasp gently deposits the soda. Finally, the slot unlocks and tilts forward, allowing the buyer to retrieve his or her soda. Engineering perfection! And as a bonus, the soda isn’t subjected to all the usual mechanical clatter that causes it to fizz over when it’s opened.
Unfortunately, these elaborate machines seem to have a propensity for component failure. On one soda mission from his lab, Jason discovered that the vending slot was broken on the machine on his floor, which prevented it from working altogether. He went to the next floor down and saw that that machine’s vending slot was fine, but the conveyor was broken. He went down to the ground floor and saw that that machine was in perfect order, but only had caffeine free diet soda! At this point, Jason devised a plan. It’s a simple matter for him to open up the working machine and harvest the parts he needs for the machine upstairs, then to hike back upstairs and repair the machine that houses the soda he needs. Sure, hecouldjust take the soda he wants while the machine is open, but what fun would that be?
The one issue with this plan is that while Jason does enjoy the engineering challenge, he hates the walking between various broken machines each time he goes to get a coke, so he’s asked you, a computer science student and fellow resident of the Harris Engineering Center to help. He can devise a way to monitor each machine in the building and ascertain what parts are working. He needs you to write a program that will allow him to get all the parts he needs from the various machines in the building, traveling up and down as few flights of stairs as possible (he doesn’t trust the elevators because he’s never been allowed to see how they work). Assume he can carry an unlimited number of parts. He also wants this algorithm to work for various kinds of coke machines and various buildings, in case the vendors decide to change out their machines one day, or the administration decides to relocate the EECS department again (you still can assume that there will always be exactly one coke machine on each floor).
The Problem:
Given the number of floors in the building, the number of parts required for a working machine, a description of the working parts in each machine in the building, and whether or not each machine has the desired kind of soda, determine the smallest number of floor changes required to
assemble a working machine that is already stocked with the desired soda. Jason will always start from his lab and return there after getting his soda.
输入描述:
There will be multiple sodamachine arrangements to process. Inputwill begin with three integers,N,F, andP(1 ≤N,F,P≤ 10), each separated by a singlespace with no leading or trailingspaces.Ndescribes the number of floors in the building,Findicates which floor Jason’s lab is on, andPindicates the number of different partsin each of the building’s soda machines.
On the nextNlines will be a set of integersfollowed by a single letter. Eachline describes the soda machine onone floor (starting with the ground floor, and proceeding upward in order). The characterson a line are separated by a single space, with no leading or trailing spaces.The first integers on each line will beS(0 ≤S≤P), indicating the number of workingparts in the machine.Sintegerswill follow, each indicating a working part in the machine (each of these integers will be unique and will bebetween 1 andP). Finally, there willbe a single character “Y” or “N”, where “Y” indicates that themachine has a kind of soda that Jason likes, and “N” indicates that it does not.
End of input will beindicated by a value of 0forN,F, andP. This case should not be processed.
输出描述:
For each soda machinearrangement, print the case number (starting with 1) and a single integer indicating the minimum number of timesJason will have to travel up or down a staircase to collect the parts he needs to repair a soda machine, get a sodathat he wants, and return to his lab. Ifthere is no way for Jason to get a soda, print “Impossible” instead of the integer. Leavea blank line after the outputfor each test case.
示例1
输入
4 2 5
5 1 2 3 4 5 N
4 1 2 3 5 Y
4 1 2 4 5 Y
5 1 2 3 4 5 Y
4 2 6
1 1 Y
2 2 3 Y
3 1 4 5 Y
0 Y
0 0 0
输出
Test case #1: 2
Test case #2: Impossible
一道思维模拟题，由于数据量小，所以暴力搜索是可行的，那么通过暴力搜索答案就可以解决这个问题了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n, a, m;
int s[12];
int cnt;
int ans;
void qes(int nl, int L, int f)
{
for (int i = 1; i <= n; i++)
{
if ((s[i] | f) == m)
{
if (ans == -1)ans = abs(nl - i) + L + abs(i - a);
else ans = min(ans, abs(nl - i) + L+ abs(i - a));
//cout<<i<<' '<<ans<<endl;
}
}
}
int main()
{
int t, t1;
char t2;
bool fff = true;
while (cin >> n >> a >> m, n || a || m)
{
if (fff)fff = false;
else printf("\n");
memset(s, 0, sizeof s);
ans = -1;
m = (1 << (m + 1)) - 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &t1);
s[i] |= 1 << t1;
}
cin >> t2;
if (t2 == 'Y')s[i]++;
}
t = 0;
for (int i = a; i <= n; i++)
{
t |= s[i];
if (t & 1)t--;
qes(i, abs(i - a), t);
}
t = s[a];
for (int i = a - 1; i > 0; i--)
{
t |= s[i];
if (t & 1)t--;
qes(i, abs(i - a), t);
}
printf("Test case #%d: ", ++cnt);
if (ans == -1)printf("Impossible\n");
else printf("%d\n", ans);
}
}
题目描述
For the UCF High School Programming Tournament, the judges were located in the Engineering building, and most of the teams were in the Classroom building, which is on the other side of Pegasus Circle.
Chris was walking to the Classroom building for the first time, and was joined by Jeremy, who had made the hike a couple of times already.
“Jeremy, is it faster to stay on the circle, or to cut through the middle using the boardwalks that go to the Student Union?” asked Chris.
“I don’t know.” Jeremy answered. “I think it’s about the same, but it might be slightly faster to use the walkways.”
“Well, if it’s about the same, let’s stick to the circle. I don’t want to be attacked by squirrels.”
The Problem:
Given two points on a circle, and two paths to get from one to the other—one following the perimeter of the circle, and the other by a sequence of connected straight line segments through the interior of the circle—determine the shorter of the two paths.
输入描述:
The input will contain multiple test cases, each consisting of two lines. The first line of each testcase contains six floating-point numbers:xc,yc,xs,ys,xf, andyf, where (xc,yc) is the center point of the circle, (xs,ys) is the start point for both paths (e.g., the Engineering building), and (xf,yf) is the finish point for both paths (e.g., the Classroom building).The circle will always have a radius greater than 1, and the start and finish points are both guaranteed to be at distinct pointson its perimeter, with an accuracy of at least 3 placesafter the decimal.The path along the perimeter is always in the directioncounter-clockwise around the circle.
The second line of each test case will start with an integer,n(1≤n≤ 10), followed by n pairs of floating-point numbers,x1,y1,x2,y2, …xn, and yn, where each pair (xi,yi) is a point inside the circle. The interior path traveled will be from point (xs,ys) to point (x1,y1), then from (x1,y1) to (x2,y2), then from (x2,y2) to (x3,y3), …, then from (xn,yn) to (xf,yf).
The last test case will be followed by a line containing six zeros. All numbers on an input line will beseparated from each other by one space, with no extra spaces at the beginning or end of lines. Assumethat all the input floating point numbers will be less than 1000.0 and greater than
-1000.0, with at most 6 places after the decimal.
输出描述:
For each test case in the input, output a line in either the format
Case #n:Stick to the Circle.
if the perimeter path is shorter,or
Case #n:Watch out for squirrels!
if the interior pathis shorter, where n is the num berof the input test case, starting at 1.
Assume that the two paths will not be equal, i.e., it is guaranteed that the two distances will not be equal. In particular, assume that the two paths will differ in length by 0.001 or more.
Leave a blank line after the output for each test case.
示例1
输入
5.0 5.0 10.0 5.0 5.0 10.0
6 8.5 4.7 6.9 5.0 3.6 6.5 4.2 7.1 4.2 8.3 4.7 8.8
2.0 8.0 0.5 16.87412 7.5 0.8761
2 3.25 9.25 7.0 7.0
0 0 0 0 0 0
输出
Case #1: Stick to the Circle.
Case #2: Watch out for squirrels!
本题是一道有一定难度的数学几何题目，问题的理解非常简单，但是本题的难点在于如何求出在圆上保证以逆时针求出圆弧，这道题的这个部分是值得赛后仔细推敲的地方。
#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<utility>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
const double PI = acos(-1);
double g(double& x, double& y)
{
return sqrt(x * x + y * y);
}
double get(double x1, double y1, double x2, double y2, double x3, double y3)
{
x2 -= x1;
y2 -= y1;
x3 -= x1;
y3 -= y1;
bool f;
if (x2 == 0)f = x3 > 0;
else if (x3 == 0)f = x2 < 0;
else f = atan(y3 / x3) < atan(y2 / x2);
if (x2 * x3 < 0)f = !f;
double st = x2 * x3 + y2 * y3;
st /= g(x2, y2) * g(x3, y3);
st = acos(st);
if (f)st = 2 * PI - st;
return g(x2, y2) * st;
}
double dis(double x1, double y1, double x2, double y2)//求两点距离
{
double res = sqrt((abs(x1 - x2) * abs(x1 - x2)) + (abs(y1 - y2) * abs(y1 - y2)));
return res;
}
void solve()
{
int cnt = 1;
double rx, ry, x1, y1, x2, y2;
cin >> rx >> ry >> x1 >> y1 >> x2 >> y2;
while (rx || ry || x1 || y1 || x2 || y2)
{
int n;
double ce = 0, le = 0;
cin >> n;
double fx = x1, fy = y1;
while (n--)
{
double px, py;
cin >> px >> py;
le += dis(fx, fy, px, py);
fx = px;
fy = py;
}
le += dis(fx, fy, x2, y2);
ce = get(rx, ry, x1, y1, x2, y2);
if (le < ce)
{
cout << "Case #" << cnt++ << ": ";
cout << "Watch out for squirrels!" << endl;
cout << endl;
}
else
{
cout << "Case #" << cnt++ << ": ";
cout << "Stick to the Circle." << endl;
cout << endl;
}
cin >> rx >> ry >> x1 >> y1 >> x2 >> y2;
}
}
int main()
{
solve();
return 0;
}
题目描述
Perfect binary trees are one of the coolest structures that computer scientists study. They have a lot of properties that make them very nice to work with. One of the nicest properties is that they can just be described by a single integerngiving the depth of the tree. For instance, the perfect binary tree forn= 3 looks like:
In general, a perfect binary tree with depthnwill have exactly 2n+1 – 1 nodes, and can be numbered by following the pattern seen above (there are of course other ways to number the nodes of the tree, but this is the scheme we will use in this problem).
A common question that arises when dealing with trees is the query of the lowest common ancestor (commonly called LCA) of two nodes in the tree. Formally, the LCA ofxandyis the nodezof greatest depth in the tree such thatzis an ancestor ofxandy. Nodeais an ancestor of nodecifcexists in the sub-tree rooted at nodea. Notice that 1 is trivially a common ancestor of any two nodes in the tree, but is not always thelowestcommon ancestor. For instance, the common ancestors of nodes 7 and 12 are 1 and 3, and 3 is the LCA since it is the node of greatest depth. The LCA of 2 and 13 is node 1, and the LCA of 5 and 11 is node 5. The definition of LCA guarantees that the LCA of any two nodes will always be unique.
The Problem:
Given two nodes in the tree using the numbering scheme shown above, determine the LCA of the two nodes.
输入描述:
Input will begin with apositive integer,T≤ 2?106,indicating the number of test cases. Thiswill be followed byTtest cases, each on a separate inputline. Each test case will contain twospace separated integers,XandY, represented in hexadecimal.XandYwill each contain at most 1000characters from the set {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}, where a-frepresent 10-15, respectively. You are todetermine the LCA ofXandY.
Note: The hexadecimal (base 16) numberdndn-1···d1d0 is converted to a decimal number (base 10) by the followingformula:d0·160 +d1·161 + ··· +dn-1·16n-1 +dn·16n.
输出描述:
For each case, output a singleline:
Case#x:y
wherexis the case number beginning with 1, andyis the LCA in hexadecimal with no leading 0’s. Leave a blankline after the output for each testcase.
示例1
输入
7
7 c
2 d
b 5
10 11
a020fac a030ccf
12afcdb 12afcdc
100000000 fffffffff
输出
Case #1: 3
Case #2: 1
Case #3: 5
Case #4: 8
Case #5: 501
Case #6: 255f9b
Case #7: 1
题意为建一个如图的完全二叉树，然后每次询问两个16进制数，然后把他们的公共父节点以16进制输出。本题我们可以知道，公共父节点为转化为2进制数后从前看的相同部分。那么我们只需要把16进制转化为2进制后求出父节点的值，然后再转化为16进制进行输出。而进制的转换写个函数是一个笨但是好用的方法。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
string get(char& s)
{
switch (s)
{
case '0':
return "0000";
case '1':
return "0001";
case '2':
return "0010";
case '3':
return "0011";
case '4':
return "0100";
case '5':
return "0101";
case '6':
return "0110";
case '7':
return "0111";
case '8':
return "1000";
case '9':
return "1001";
case 'a':
return "1010";
case 'b':
return "1011";
case 'c':
return "1100";
case 'd':
return "1101";
case 'e':
return "1110";
case 'f':
return "1111";
}
return "";
}
string get(char& s,int)
{
switch (s)
{
case '0':
return "0";
case '1':
return "1";
case '2':
return "10";
case '3':
return "11";
case '4':
return "100";
case '5':
return "101";
case '6':
return "110";
case '7':
return "111";
case '8':
return "1000";
case '9':
return "1001";
case 'a':
return "1010";
case 'b':
return "1011";
case 'c':
return "1100";
case 'd':
return "1101";
case 'e':
return "1110";
case 'f':
return "1111";
}
return "";
}
char g(string a)
{
int t = 0;
for (int i = 0; i < 4; i++)
t = t * 2 + a[i] - '0';
if (t < 10)return '0' + t;
return t - 10 + 'a';
}
string f(string& a)
{
while (a.length() % 4 != 0)a = '0' + a;
string res = "";
for (int i = 0; i < a.length(); i += 4)
{
res += g(a.substr(i,4));
}
return res;
}
char x[4040], y[4040];
string tx, ty, ans;
int main()
{
int T;
cin >> T;
for (int i = 1; i <= T; i++)
{
scanf("%s%s", x, y);
printf("Case #%d: ", i);
tx = get(x[0],1);
for (int i = 1; i < strlen(x); i++)
{
tx += get(x[i]);
}
ty = get(y[0],1);
for (int i = 1; i < strlen(y); i++)
{
ty += get(y[i]);
}
ans = "";
int n = max(tx.length(), ty.length());
for (int i = 0; i < n; i++)
{
if (tx[i] == ty[i])
ans += tx[i];
else break;
}
cout << f(ans) << endl;
if (i != T)cout << endl;
}
}
作者：TheSeven