2011 Heilongjiang collegiate programming contest题解报告 Similar Word Lucky Boy Car race game
题目:
UESTC 924~933
A.水题
B.水题
C.模拟, 也没什么坑点.
D
Dart game
Problem:696
Time Limit:1000ms
Memory Limit:65536K
Description
Darts originated in Australia. Australia's aborigines initially for hunting and hit the enemy's weapon.
A game of darts in which the players attempt to score points by throwing the darts at a target.
2011 Heilongjiang collegiate programming contest题解报告 Similar Word Lucky Boy Car race game
Figure:DART BOARD
Darts movement rules of the game is very simple, the target is 1-20 points and the central circle is 50 small zoning, edge is 25 division, the rough circle line of fan-shaped covered area is 1-20 points and three times the corresponding division. This game is generally played by two people but can be played by teams. Each player starts with N points. The goal for each player is to reach zero by subtracting the amount they score from the amount they had left,but final throwing must be double division. And the first to reduce his/her score to zero wins.
So the task is :
Given a dart scores N that a player starts with, you are required to calculate how many different ways to reach zero. One is different way to another means at least one dart hits different division.Ways which have different orders and same divisions are the same way. For example,if N=4,there are 4 different ways reach to zero:the first is double 2,the second is 2 and double 1, the third is twice of double 1,the fourth is twice of 1 and double 1 .
The answer may be very large,you have to module it by 2011.
Input
The input contains several test cases.
Each test case contains an integer N ( 0 < N ≤ 1001 ) in a line.
N=0 means end of input and need not to process.
Output
For each test case, output how many different ways to reach zero.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Mod = 2011;
const int maxn = 2e3 + 5;
int dp1[maxn], dp2[maxn];
void init()
{
dp1[0] = dp2[0] = 1;
for(int i = 1; i <= 20; i++)
{
for(int j = i; j < maxn; j++)
{
dp1[j] = (dp1[j-i] + dp1[j])%Mod; //方案数求法
dp2[j] = (dp2[j-i] + dp2[j])%Mod;
}
}
for(int i = 25; i < maxn; i++)
dp1[i] = (dp1[i]+dp1[i-25])%Mod, dp2[i] = (dp2[i]+dp2[i-25])%Mod; //求25的
for(int i = 50; i < maxn; i++)
dp1[i] = (dp1[i]+dp1[i-50])%Mod; //求50的
for(int i = 1; i <= 20; i++) //求2的倍数作为分子的
for(int j = i*2; j < maxn; j++)
dp1[j] = (dp1[j]+dp1[j-i*2])%Mod;
for(int i = 1; i <= 20; i++) //求3的倍数
for(int j = i*3; j < maxn; j++)
dp1[j] = (dp1[j]+dp1[j-i*3])%Mod, dp2[j] = (dp2[j]+dp2[j-i*3])%Mod;
}
int main()
{
int n;
init();
while(~scanf("%d", &n), n)
{
printf("%d\n", (dp1[n]-dp2[n]+Mod)%Mod); //注意分别取模的相减,一定要+MOD再取模,一定!!!
}
return 0;
}
E
Similar Word
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
It was a crummy day for Lur. He failed to pass to the
CET-6
(College English Test Band- 6 6). Looking back on how it was in last year gone by, he gradually noticed he had fled too many English Lessons. But he determines to memorize words on his bed ,not in the classroom. You know, it is not that easy to pass the test mainly because the large amount of born words.
Lur is intelligent on games , never English. He cann't learn the similar words by heart. He always choose to select a word to learn from the similar words . For him, two words are similar if and only if one word can equal to the other by multiple cyclic shift(at least 1 1). For example,
car
and
arc
are similar words, while
car
and
rca
are also similar words . To save more time to play games.
Lur want to know wether two words are similar words faster, he asks you to write a program to tell him ,can you help him ?
Input
There are multiple test cases. Each case contains two lines. Each line contains a word, W W. You can assume that length (W)≤105 (W)≤105 . Ended by
EOF
.
Output
Output
yes
in a single line if two words are similar,otherwise you should output
no
in a single line.
Sample input and output
Sample Input
Sample Output
car
arc
car
cra
car
car
yes
no
no
Source
2011 Heilongjiang collegiate programming contest
算是水题,把字符串复制一次, 然后kmp匹配就好,注意长度不相同是no.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+5;
char s[maxn], t[maxn];
int Next[maxn], ans;
void makeNext(void)
{
int len = strlen(s);
Next[0] = Next[1] = 0;
for(int i = 1; i < len; i++)
{
int j = Next[i];
while(j && s[i] != s[j]) j = Next[j];
Next[i+1] = s[i]==s[j] ? j+1 : 0;
}
}
void kmp(void)
{
int len1 = strlen(s);
int len2 = strlen(t);
int i, j = 0;
for(int i = 0; i < len1; i++)
{
while(j && s[i] != t[j]) j = Next[j];
if(s[i] == t[j]) j++;
if(j == len2) ans++, j = Next[j];
}
}
int main(void)
{
while(~scanf(" %s %s", s, t))
{
ans = 0;
int len = strlen(s);
int len2 = strlen(t);
if(len != len2) { puts("no"); continue ; }
bool same = 1;
for(int i = 0; i < len; i++)
{
if(s[i] != t[i])
same = 0;
}
for(int i = 0; i < len; i++)
s[i+len] = s[i];
s[len*2] = 0;
makeNext();
kmp();
// cout << ans << ' ' << same << endl;
if(ans == 2 && same) puts("no");
else if(ans) puts("yes");
else puts("no");
}
return 0;
}
F 前缀和+贪心 跟这差不多 点击打开链接
G
Lucky Boy
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
Recently, Lur have a good luck. He is also the cleverest boy in his school as he create the most popular computer game – Lucky Boy. The game is played by two players, a a and b b, in 2 2d planar .In the game Lucky Boy, there are n n different points on plane, each time one can remove one or multiple co-line points from the plane. The one who can firstly remove more than two points from the plane wins. The one who removes the last point on the plane can also win the game. You may assume that two players are both clever enough that they can always make the best choice. The winner is called Lucky Boy.
Given the n points, can you tell me who will be the Lucky Boy ? Note that player a will always the first one to remove points from the plane.
Input
The first line of each case is an integer n(0<n≤103) n(0<n≤103), following n n lines each contains two integers x x and y(0≤x,y≤108) y(0≤x,y≤108), describing the coordinates of each point. Ended by
EOF
.
Output
Output
a is the lucky boy.
in a single line if a win the game, otherwise you should output
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e3 + 5;
struct node
{
int x, y;
}a[maxn];
int main()
{
int n;
while(~scanf("%d", &n))
{
for(int i = 1; i <= n; i++)
scanf("%d%d", &a[i].x, &a[i].y);
int flag = 0;
for(int i = 1; i <= n; i++)
{
if(flag) break;
map<double, int> mp;
for(int j = i+1; j <= n; j++)
{
if(a[j].y == a[i].y && !mp[-1])
mp[-1]++;
else if(a[j].y == a[i].y && mp[-1])
{
flag = 1;
break;
}
else
{
double tmp = (a[j].x-a[i].x)*1.0 / (a[j].y-a[i].y);
if(mp[tmp])
{
flag = 1;
break;
}
else mp[tmp]++;
}
}
}
if(flag)
puts("a is the lucky boy.");
else
{
if(n%3 == 0)
puts("b is the lucky boy.");
else
puts("a is the lucky boy.");
}
}
return 0;
}
H
Car race game
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
Bob is a game programming specialist. In his new car race game, there are some racers( n n means the amount of racers (1≤n≤100000) (1≤n≤100000)) racers star from someplace( xi ximeans Starting point coordinate),and they possible have different speed( V V means speed).so it possibly takes place to overtake(include staring the same point ). now he want to calculate the maximal amount of overtaking.
Input
The first line of the input contains an integer n n-determining the number of racers. Next n n lines follow, each line contains two integer Xi Xi and Vi Vi.( xi xi means the ith ith racer's Starting point coordinate, Vi Vi means the ith racer's speed. 0<Xi,Vi<1000000 0<Xi,Vi<1000000).
Output
For each data set in the input print on a separate line, on the standard output, the integer that represents the maximal amount of overtaking.