The 19th Zhejiang Provincial Collegiate Programming Contest
第一次體驗省賽，加油！
A.JB Loves Math
JB is good at Math, so he thinks all the math problems in the world are easy.
But one day, he meets a math problem which he can’t solve, so he asks you to help him.
JB will give you two numbers a and b, and you should then choose a positive odd number x and a positive even number y. You can let a add x or let a minus y in one operation. You should change a into b in the minimal number of operations. Note that you are not allowed to change the value of x and y.
Input
In the first line, there is one integer T
(1≤T≤105), denoting the number of test cases.
For each test case, there is one line containing two numbers a
and b (1≤a,b≤106), denotes the number given by JB.
Output
For each test case, print one number, denoting the minimal number of operations you need to change a into b.
Example
Input
2
3 6
5 3
Output
1
1
這道題目使用打表就可以完成
要把a變成b，可以增加奇數，或者減少偶數，求最少的操作次數。
分以下5種情況
- a與b相等，0次
- a小於b，並且(b-a)為奇數，那麼1次（增加b-a即可）
- a小於b，並且(b-a)為偶數，需要2次（增加兩次\(\frac{b-a}{2}\)）
錯誤！
因為\(\frac{b-a}{2}\)不一定是奇數！！。
如果不是奇數的話，就要增加兩個相同的奇數，然後減去一個偶數才可以達到。 - a大於b，並且(a-b)為偶數，那麼直接減(a-b)
- a大於b，並且(a-b)為奇數，那麼增加一，再減去(a-b+1)
證明：
增加一次不可以，增加兩次有構造方案，所以是增加兩次。
在寫程式碼的時候一定要注意可讀性，不然容易寄
#include <bits/stdc++.h>
using namespace std;
int T;
int main()
{
cin >> T;
while(T--)
{
int ans = 0;
int a, b;
scanf("%d%d", &a, &b);
if(a == b) ans = 0;
else if(a < b)
{
int d = b-a;
if(d&1) ans = 1;
else
{
if((d/2)&1) ans = 2;
else ans = 3;
}
}
else{
int d = a-b;
if(d&1) ans = 2;
else ans = 1;
}
printf("%d\n", ans);
}
return 0;
}
B.JB Loves Comma
JB is the most famous ICPC world finalist. His favorite problem in ICPC world final is a problem which asks him to add some commas in a string.
Now, JB wants to share happiness with adding comma with you, so he asks you to add a comma after each substring 「cjb」 in a string S he gives you.
Input
The only line contains a string S (1 ≤ |S| ≤ 105), contains only lowercase English letters.
Output
One string, denotes the result after adding commas.
Examples
input 1
pbpbppb
output 1
pbpbppb
input 2
cjbismyson
output 2
cjb,ismyson
這道題目也是一個水題，由於僅僅比較三個字元，所以並沒有必要採用KMP，直接比就行了。
#include <bits/stdc++.h>
using namespace std;
#define N 100020
char s[N];
int main()
{
scanf("%s", s+1);
int len = strlen(s+1);
for(int i = 1; i <= 2; i++) putchar(s[i]);
for(int i = 3; i <= len; i++)
{
putchar(s[i]);
if(s[i-2] == 'c' && s[i-1] == 'j' && s[i] == 'b')
putchar(',');
}
return 0;
}
C. JB Wants to Earn Big Money
JB has always wanted to make a lot of money, so recently he is addicted to stocks.
The trading rules of the stock market are as follows. Suppose there are n people who want to buy some shares while m people who want to sell some shares. Everyone will give a price.
The system will determine a final price x. For the people who want to buy some shares, if the price he gives is not lower than x, he will join the transaction. For the people who want to sell some shares, if the price he gives is not higher than x, he will join the transaction.
Now, JB gives you the price given by the people and the final price x. He wants you to tell him the number of people who can join the transaction.
Input
The first line contains three numbers n,m and x (1≤n,m,x≤105), denoting the number of two types of people and the final price determined by the system.
The second line contains n numbers a1,a2,…,an (1≤ai≤105), denoting the price given by the people who want to buy some shares.
The third line contains m numbers b1,b2,…,bm (1≤bi≤105), denoting the price given by the people who want to sell some shares.
Output
One number, denotes the number of people who can join the transaction.
Input
5 5 3
1 2 3 4 5
1 2 3 4 5
Output
6
這一道題目就是一個大水題！
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
int buf;
int ans = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &buf);
if(k <= buf) ans++;
}
for(int i = 1; i <= m; i++)
{
scanf("%d", &buf);
if(k >= buf) ans++;
}
cout << ans;
return 0;
}
G. Easy Glide
Grammy is playing a boring racing game named Easy Gliding. The game’s
main content is to reach the destination as fast as possible by walking
or gliding（滑行）. The fastest player wins.
Each player controls a character on a two-dimensional plane. A character can walk at any moment with a speed of V1.
Especially, when a character touches a gliding point, he/she can glide with a speed of \(V_2\) for the following 3 seconds. It is guaranteed that V1<V2.
Now Grammy locates at point S and she knows the coordinates(坐標) of all the gliding points p1,p2,…,pn. The goal is to reach point T as fast as possible. Could you tell her the minimum time she has to spend to reach point T?
Input
The first line contains one integer n (1≤n≤1000), denoting（表示） the number of gliding points.
The following n lines describe the gliding points. The i-th line contains two integers xi,yi (−1000000≤xi,yi≤1000000), representing the coordinates of the i-th gliding point pi.
The next line contains four integers，Sx,Sy,Tx,Ty(−1000000≤Sx,Sy,Tx,Ty≤1000000), representing the coordinates of S and T.
The next line contains two integers V1,V2 (1≤V1<V2≤1000000), representing the speed of walking and gliding.
Output
Output the minimum time Grammy has to spend to reach point T
in one line. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\)
Examples
InputCopy
2
2 1
0 3
0 0 4 0
10 11
OutputCopy
0.400000000000
InputCopy
2
2 1
-2 0
0 0 4 0
1 2
OutputCopy
3.354101966250
InputCopy
2
2 1
-2 0
0 0 4 0
1 10000
OutputCopy
2.000600000000
如果要是不看題解，感覺還是比較難，但是看了題解以後，就覺簡單了。
注意題目中的說法：小人可以從任意方向進行移動，所以從一點移動到另一點的時間就是\(\frac{兩點之間的歐幾里得距離}{速度}\)
現在進行分析：
從起點到重點，有以下幾種情況：
- 不經過加速點，直接到達重點
- 經過幾個特定的加速點，最終到達重點
如果不經過加速點，那麼肯定是兩點之間線段最短。
而如果是經過加速點的話，設經過的加速點的序列是\(a_1, a_2, a_{..}\)由貪心策略，從起點到加速點，從一個加速點到達另一個加速點，從加速點再到終點，肯定走的是直線距離（這樣的話，在局部使用了貪心，從而使得求解問題成為了一種可能）
#include <bits/stdc++.h>
using namespace std;
#define N 1020
int n;
struct {
double x, y;
}a[N];
/*
1 is s;
2-n+1 is point
n+2 is t
*/
int head[N], ver[N*N], nxt[N*N], tot;
double v1, v2;
double edge[N*N];
priority_queue< pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>> >q;
bool v[N];
double d[N];
double dist(int x, int y)
{
double dx = a[x].x - a[y].x;
double dy = a[x].y - a[y].y;
return sqrt(dx*dx+dy*dy);
}
inline void add(int x, int y, double z)
{
ver[++tot] = y;
edge[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
void djs()
{
fill(d, d+N, 1e10);
d[1] = 0;
q.push({d[1], 1});
while(!q.empty())
{
// cout << "djs";
int x = q.top().second;
q.pop();
if(v[x]) continue;
v[x] = true;
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if(d[y] > d[x] + edge[i])
{
d[y] = d[x] + edge[i];
q.push({d[y], y});
}
}
}
}
int main()
{
tot = 1;
scanf("%d", &n);
for(int i = 2; i <= n+1; i++){
scanf("%lf%lf", &a[i].x, &a[i].y);
}
cin >> a[1].x >> a[1].y >> a[n+2].x >> a[n+2].y;
n += 2;//修改一下，便於解決
cin >> v1 >> v2;
for(int i = 2; i <= n; i++)
{
add(1, i, dist(1, i) / v1);
}
for(int i = 2; i <= n; i++)
{
for(int j = 2; j <= n; j++)
{
if(i == j) continue;
double d = dist(i, j);
double len = 3 * v2;
if(len >= d){
add(i, j, d/v2);
}
else {
add(i, j, 3+(d-len)/v1);
}
}
}
djs();
printf("%.10lf", d[n]);
return 0;
}
I. Barbecue
Putata and Budada are playing a new game. In the beginning, Putata has a
note with a string consists of lowercase letters on it. In each round,the player who has the note must rip off a character from the beginning or the end of the note, then pass it to the other player. If at any moment, the string on the note is a palindrome, then the player who has the note loses. Notice that both before or after the player ripping off a character from the note, the player is considered to have the note. A string s1s2…sn of length n is considered to be a palindrome if for all integers i from 1 to n, si=sn−i+1.
However, when Putata found the note, he found that someone have played on this note before. Since both Putata and Budada are clever and will always
choose the best way to make themselves win, they wonder who will win the game, and they ask you for help. Formally, you are given a string of length n and you have to answer q queries, each query is described by two integers l and r, which means you have to determine who will win if Putata and Budada play the game described above on string slsl+1…sr .
Input
The first line contains two integers n,q (1≤n,q≤1000000), denoting the length of the string and the number of queries.
The second line contains a string s of length n, consisting of lowercase English letters.
Each of the following q lines contains two integers l and r (1≤l≤r≤n), describing a query.
Output
For each query, print a single line. If Putata wins the game in one query, output “Putata” (without quotes). Otherwise output “Budada“.
Example
InputCopy
7 3
potatop
1 3
3 5
1 6
OutputCopy
Putata
Budada
Budada
BUG出現在了字元串哈希中的p數組的p[0]項沒有初始化為1，從而導致在中秋佳節卡了半個小時！
思路：
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
unsigned long long order[N];
unsigned long long reorder[N], p[N];
char a[N];
int n, T;
int main()
{
scanf("%d%d", &n, &T);
scanf("%s", a+1);
p[0] = 1;
for(int i = 1; i <= n; i++)
p[i] = p[i-1]*131;
for(int i = 1; i <= n; i++)
{
order[i] = order[i-1] * 131 + a[i] - 'a' + 1;
}
for(int i = n; i >= 1; i--)
{
reorder[i] = reorder[i+1] * 131 + a[i] - 'a' + 1;
}
for(int _ = 1; _ <= T; _++)
{
int l, r;
scanf("%d%d", &l, &r);
if(order[r] - order[l-1] * p[r-l+1] == reorder[l] - reorder[r+1]*p[r-l+1])
{
puts("Budada");
}
// else if(order[r] - order[l] * p[r-l] == reorder[l+1] - reorder[r+1]*p[r-l] &&
// order[r-1] - order[l-1] * p[r-l] == reorder[l] - reorder[r]*p[r-l]
// )
// {
// puts("Budada");
// }
else{
if((r-l+1)&1 == 1)
{
puts("Putata");
}
else
{
puts("Budada");
}
}
}
return 0;
}
L. Candy Machine
JB loves candy very much.
One day, he finds a candy machine with N candies in it.
After reading the instructions of the machine, he knows that he can choose a subset(子集) of the N candies. Each candy has a sweet value. After JB chooses the subset, suppose the average sweet value of the chosen candies is X, all the candies with sweet value strictly larger than X will belong to JB. After JB makes the choice, the machine will disappear, so JB only has one opportunity to make a choice.
JB doesn’t care how sweet the candies are, so he just wants to make a
choice to maximize the number of candies he will get. JB has been fascinated by candy and can’t think, so he needs you to help him.
Input
The first line contains one integer N (1≤N≤106), denoting the number of candies in the machine.
The second line contains N integers a1,a2,…,aN (1≤ai≤109), denoting the sweet values of the candies.
Output
One integer, denoting the maximum number of candies JB can get.
Example
InputCopy
5
1 2 3 4 5
OutputCopy
2
題目大意：
給定一個集合，要求在這一個集合中選擇一個子集，設子集中元素的平均值是arv，要求求解子集中大於arv糖果的數目的最大值
這一道題目其實有一個很巧妙的思想：
因為隨著數據的增加，刪除，平均數是變著的，所以對於這一道題目就會顯得捉摸不定。
我考慮一種最壞情況，假設平均數不大於K，那麼小於K的所有值一定要選擇（貪心，選的越多，就可以容納大於K的數的個數越多）。對於大於K的數字，僅僅選擇比K大一點點的數字（貪心，為了選擇數目最多）。選擇的最多的數目就是：
選取儘可能多的比K大一點點的，使得整體的平均值小於K的數字。
按照這樣理解，那麼最優的答案一定是選擇的一個前綴。這樣的話，遍歷前綴，就可以得到答案。時間複雜度：\(O(nlogn)\)
最優的集合一定是原來的集合排好序之後的前綴（另一種證明）：
假設所選的集合不連續，那麼有：
程式碼一遍過，我還是那麼強大
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000020
ll a[N];
ll n;
ll sum[N];
int main()
{
ll ans = 0;
cin >> n;
for(int i = 1; i <= n; i++)
{
scanf("%lld", a+i);
}
sort(a+1, a+1+n);
for(int i = 1; i <= n; i++)
{
sum[i] = sum[i-1] + a[i];
}
for(ll i = 1; i <= n; i++)
{
ll l = 1, r = n;
while(l < r)
{
ll mid = (l+r)/2;
if(a[mid]*i > sum[i]) r = mid;//大於平均值
else l = mid + 1;
}
ans = max(ans, i - l + 1);
}
cout << ans;
return 0;
}
M. BpbBppbpBB
Grammy has learned how to engrave stamps recently. She engraved two types of special stamps, type C has a capital letter “B” on it, and type S has a small letter “b” or a small letter “p” on it. The shapes and sizes of the stamps are illustrated in the following picture.
Grammy stamped these letters (with rotations) on a grid paper without
overlapping, the letters can only be pressed at the piece of paper if it lies totally inside the piece of paper. However, Grammy forgot how many times she used each type of stamps. Please count the letters and helpher to remember them.
The black part of the stamps may be adjacent but may not overlap.
Note that the stamps can be rotated to a multiple of 90 degrees.
Input
The first line consists of two integers n,m (1≤n,m≤1000), representing the size of the paper.
In the following n lines, each line consists of m characters, representing the current state of the paper. “#” stands for a black square and “.” stands for a white square.
Output
Output two integers, denoting the number of type C stamps and the number of type S stamps, respectively.
Examples
InputCopy
10 17
#################
#################
#################
####..#####..####
###....###....###
###....###....###
####..#####..####
#################
#################
#################
OutputCopy
1 0
InputCopy
14 11
.##########
.##########
.##########
.####..####
.###....###
.###....###
.####..####
.##########
.##########
.##########
.###.......
.###.......
.###.......
.###.......
OutputCopy
0 1
InputCopy
20 14
.##########...
.##########...
.##########...
.####..####...
.###....###...
.###....###...
.####..####...
.##########...
.##########...
.##########...
.#############
.#############
.#############
.#######..####
....###....###
....###....###
....####..####
##############
##############
##############
OutputCopy
0 2
題目描述：
有兩種形式的貼紙（中間有孔）粘在一張紙上（不可以重疊，貼紙沒有超出紙的部分），求兩種類型的貼紙各有多少個？
思路：找到所有的貼紙的中間的空白位置（這樣形狀的空白位置只有可能是貼紙的中間，不可能是其他邊緣造成的），然後暴力枚舉，當發現有兩個空距離是C type的距離，就把這兩個孔判斷為C type的（兩個貼紙相鄰等其他情況中，兩個孔的距離一定比C type中的兩個孔的距離近）。
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n, m;
char a[N][N];
int dx[] = {0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3};
int dy[] = {0, 1, -1, 0, 1, 2, -1, 0, 1, 2, 0, 1};
vector<pair<int, int> > vec;
bool judge(int i, int j)
{
if(i-1 < 1 || i+4 > n || j-2 < 1 || j+3 > m) return false;
for(int _ = 0; _ < 12; _++)
{
int x = i+dx[_], y = j+dy[_];
if(a[x][y] != '.')
{
return false;
}
}
int cnt = 0;
for(int row = i-1; row <= i+4; row++)
{
for(int col = j-2; col <= j+3; col++)
{
if(a[row][col] == '.') cnt++;
}
}
if(cnt == 12) return true;
else return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '.')
{
if(judge(i, j)) {
vec.push_back(make_pair(i, j));
// printf("(%d, %d)\n", i, j);
// fflush(stdout);
}
}
}
}
int cnt = 0;
for(int i = 0; i < vec.size(); i++)
{
for(int j = i+1; j < vec.size(); j++)
{
int x1 = vec[i].first;
int x2 = vec[j].first;
int y1 = vec[i].second;
int y2 = vec[j].second;
if((abs(x1-x2)==7 && y1 == y2) || (abs(y1-y2) == 7 && x1 == x2))
cnt++;
}
}
printf("%d %d", cnt, vec.size() - cnt*2);
// for(int i = 0; i < vec.size(); i++)
// {
// printf("(%d, %d)\n", vec[i].first, vec[i].second);
// }
return 0;
}
