2015 ACM-ICPC Asia Regional Contest Shanghai Site - Onsite Contest

F - Friendship of Frog

NN frogs from different countries are standing in a line. Each country is represented by a lowercase letter. The distance between adjacent frogs (e.g. the 1st1stand the 2nd2nd frog, the N−1thN−1th and the NthNth frog, etc) are exactly 11. Two frogs are friends if they come from the same country.
The closest friends are a pair of friends with the minimum distance. Help us find that distance.

Input

First line contains an integer TT, which indicates the number of test cases.
Every test case only contains a string with length NN, and the ithith character of the string indicates the country of ithith frogs.
⋅⋅ 1≤T≤501≤T≤50.
⋅⋅ for 80% data, 1≤N≤1001≤N≤100.
⋅⋅ for 100% data, 1≤N≤10001≤N≤1000.
⋅⋅ the string only contains lowercase letters.

Output

For every test case, you should output “ Case #x: y“, where xx indicates the case number and counts from 11 and yy is the result. If there are no frogs in same country, output −1−1 instead.

Sample Input

1
2
3
2
abcecba
abc

Sample Output

1
2
Case #1: 2
Case #2: -1

题解

超级水题,一次性遍历,顺便设置一个字母表,记录上一个字母位置,初始值为0,每遇到一个字母,对该字母表进行更新。如果上一个该字母表不为0,则先用当前位置减去表中上一个位置,然后记录下最小值,然后再更新。最终如果最小值为初始值,则输出-1,否则输出该最小值。

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx = 1e9+7;
char str[1007];
int a[26];
int main(){
int t;
scanf("%d",&t);
for(int cc = 1;cc<=t;cc++){
scanf("%s",&str);
int minD = maxx;
memset(a,0,sizeof(a));
int len = strlen(str);
for(int i = 0;i<len;i++){
int num = str[i]-'a';
if(a[num])
minD = min(minD,i - a[num] + 1);
a[num] = i + 1;
}
if(minD == maxx)
printf("Case #%d: -1\n",cc);
else
printf("Case #%d: %d\n",cc,minD);
}
return 0;
}

K - Kingdom of Black and White

In the Kingdom of Black and White (KBW), there are two kinds of frogs: black frog and white frog.
Now NN frogs are standing in a line, some of them are black, the others are white. The total strength of those frogs are calculated by dividing the line into minimum parts, each part should still be continuous, and can only contain one kind of frog. Then the strength is the sum of the squared length for each part.
However, an old, evil witch comes, and tells the frogs that she will change the color of at most one frog and thus the strength of those frogs might change.
The frogs wonder the maximum possible strength after the witch finishes her job.

Input

First line contains an integer TT, which indicates the number of test cases.
Every test case only contains a string with length NN, including only 00(representing
a black frog) and 11 (representing a white frog).
⋅⋅ 1≤T≤501≤T≤50.
⋅⋅ for 60% data, 1≤N≤10001≤N≤1000.
⋅⋅ for 100% data, 1≤N≤1051≤N≤105.
⋅⋅ the string only contains 0 and 1.

Output

For every test case, you should output “ Case #x: y“,where xx indicates the case number and counts from 11 and yy is the answer.

Sample Input

1
2
3
2
000011
0101

Sample Output

1
2
Case #1: 26
Case #2: 10

题解

解法有点偏暴力,首先将01分成m个联通块,一次性遍历,将m个联通块的长度储存起来,算出总值ans。然后对这m个联通块分别判断加1情况下是否变大,当然该值的计算要先用ans减去该联通块以及相邻左边或右边联通块的值,然后再加上更新的值。

代码

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
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
int t;scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
cin>>s;
int flag = -1;
vector<long long> Q;
int len = 0;
for(int i=0;i<s.size();i++)
{
if(s[i]-'0'!=flag)
{
Q.push_back(len);
len = 1;
flag = s[i]-'0';
}
else
len++;
}
Q.push_back(len);
Q.push_back(0);
long long res = 0;
for(int i=1;i<Q.size()-1;i++)
res += Q[i]*Q[i];
long long ans = res;
for(int i=1;i<Q.size()-1;i++)
{
long long tmp = 0;
if(Q[i]==1)
ans = max(ans,res-Q[i-1]*Q[i-1]-Q[i]*Q[i]-Q[i+1]*Q[i+1]+(Q[i-1]+Q[i+1]+1)*(Q[i-1]+Q[i+1]+1));
else
{
ans = max(ans,res-Q[i-1]*Q[i-1]-Q[i]*Q[i]+(Q[i-1]+1)*(Q[i-1]+1)+(Q[i]-1)*(Q[i]-1));
ans = max(ans,res-Q[i+1]*Q[i+1]-Q[i]*Q[i]+(Q[i+1]+1)*(Q[i+1]+1)+(Q[i]-1)*(Q[i]-1));
}
}
printf("Case #%d: %lld\n",cas,ans);
}
}

L - LCM Walk

A frog has just learned some number theory, and can’t wait to show his ability to his girlfriend.
Now the frog is sitting on a grid map of infinite rows and columns. Rows are numbered 1,2,⋯1,2,⋯ from the bottom, so are the columns. At first the frog is sitting at grid (sx,sy)(sx,sy), and begins his journey.
To show his girlfriend his talents in math, he uses a special way of jump. If currently the frog is at the grid (x,y)(x,y), first of all, he will find the minimum zzthat can be divided by both xx and yy, and jump exactly zz steps to the up, or to the right. So the next possible grid will be (x+z,y)(x+z,y), or (x,y+z)(x,y+z).
After a finite number of steps (perhaps zero), he finally finishes at grid (ex,ey)(ex,ey). However, he is too tired and he forgets the position of his starting grid!
It will be too stupid to check each grid one by one, so please tell the frog the number of possible starting grids that can reach (ex,ey)(ex,ey)!

Input

First line contains an integer TT, which indicates the number of test cases.
Every test case contains two integers exex and eyey, which is the destination grid.
⋅⋅ 1≤T≤10001≤T≤1000.
⋅⋅ 1≤ex,ey≤1091≤ex,ey≤109.

Output

For every test case, you should output “ Case #x: y“, where xx indicates the case number and counts from 11 and yy is the number of possible starting grids.

Sample Input

1
2
3
4
3
6 10
6 8
2 8

Sample Output

1
2
3
Case #1: 1
Case #2: 2
Case #3: 3

题解

设当前位置为(x,y),gcd(x,y) = g。则可设x = m1g,y=m2g,LCM(x,y) = m1m2g,则目标值为(m1g+m1m2g,m2g)或(m1g,m2g+m1m2g)。已知目标值,求x,y。我们设目标值为x2,y2,则可推出m1 = x2/(g+y2)或m2 = y2/(g+x2)。递归过程,直到m1或m2不为0则返回值,否则次数加1,再继续递归。

最终得到结果。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){
return a%b==0?b:gcd(b,a%b);
}
ll dfs(ll g,ll x,ll y){
ll ans = 0;
if(!(x%(g+y))){
ans++;
ll tmp = x*g/(g+y);
ans+=dfs(gcd(max(tmp,y),min(tmp,y)),tmp,y);
}
if(!(y%(g+x))){
ans++;
ll tmp = y*g/(g+x);
ans+=dfs(gcd(max(tmp,x),min(tmp,x)),x,tmp);
}
return ans;
}
int main(){
ll t,x,y;
scanf("%lld",&t);
for(ll c = 1;c<=t;c++){
scanf("%lld%lld",&x,&y);
ll tmp = gcd(max(x,y),min(x,y));
ll ans = dfs(tmp,x,y);
printf("Case #%lld: %lld\n",c,++ans);
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!