A. JB Loves Math

对于输入a,b，我们需要定义一个数对（x,y），其中x为奇数，y为偶数，且x,y在操作中不能变化

  • 可以执行a+x，a-y操作
  • 通过n次操作变成b
  • 输出n

分析：

  • 取a=b的情况

    • a=b=0，次数为0

  • 取a>b的情况

    • 若a-b为偶数，则a-y=b，次数为1
    • 若a-b为奇数，则a-y+x=b,次数为2

  • 取a<b的情况

    • 若b-a为偶数
      • 若(b-a)%4!=0，则a+x+x=b，如3+1+1=5，次数为2
      • 若(b-a)%4==0，则a+x+x-y=b，如3+5+5-2= 11 (3+4+4非法操作)，次数为3
    • 若b-a为奇数
      • 则a+x=b，次数为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())

for i in range(n):
    a, b = map(int, input().split())
    
    if a == b:
        print(0)
    if a > b:
        if (a - b) % 2 == 0:
            print(1)
        else:
            print(2)
    if a < b:
        if (b - a) % 2 != 0:
            print(1)
        elif (b - a) % 4 != 0:
            print(2)
        else:
            print(3)

B.JB Loves comma

在每个cjb后加，

1
2
3
4
5
6
7
8
9
10
s =input()

print(s[0],end='')
print(s[1],end='')
for i in range(2,len(s)):
    if s[i-2] == 'c' and s[i-1] == 'j' and s[i] ==  'b':
        print(s[i],end='')
        print(',',end='')
    else:
        print(s[i],end='')

C. JB Wants to Earn Big Money

求第二行大于等于x的数字和第三行小于等于x的数字总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a,b,c = map(int,input().split())
cnt = 0


s = list(map(int,input().split()))
for i in range(len(s)):
    if s[i] >= c:
        cnt += 1
        

s = list(map(int,input().split()))
for i in range(len(s)):
    if s[i] <= c:
        cnt += 1
            
print(cnt)

G. Easy Glide

题意：Grammy需要从起点S到终点T，可以选择步行（速度V1）或在接触滑行点后滑行3秒（速度V2，V2>V1），求到达终点的最短时间。

用Dijkstra求最短路问题：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
int n, m, a[N], b[N];
double g[N][N];
bool st[N];
double dis[N];
int x1, yy1, x2, y2;
int v1, v2;
double jl(int x1, int yy1, int x2, int y2)		
{
    double res = 0;
    res = sqrt((x1 - x2) * (x1 - x2)*1.0 + (yy1 - y2) * (yy1 - y2)*1.0);
    return res;
}
double disksal()
{
    for(int i=0;i<=n+2;i++) dis[i]=0x3f3f3f3f;
    dis[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dis[t]>dis[j])) t=j;
        }
        st[t]=true;
        for(int k=1;k<=n;k++)
        {
            dis[k]=min(dis[k],dis[t]+g[t][k]);
        }
    }
    return dis[n];
}
void solve() {
    cin >> n;       // 输入中间点数量
    n += 2;         // 加上起点和终点，总点数n
    
    // 输入中间点坐标
    for (int i = 2; i < n; i++)
        cin >> a[i] >> b[i];
    
    // 输入起点、终点坐标和速度
    cin >> x1 >> yy1 >> x2 >> y2;
    cin >> v1 >> v2;
    
    // 构建起点到终点的直接步行时间
    g[1][n] = jl(x1, yy1, x2, y2) / (v1 * 1.0);
    
    // 构建起点到各中间点的步行时间
    for (int i = 2; i < n; i++) {
        g[1][i] = jl(x1, yy1, a[i], b[i])/(v1 * 1.0);
    }
    
    // 构建各中间点到终点的交通时间
    for (int i = 2; i < n; i++) {
        double k = jl(a[i], b[i], x2, y2);  // 计算距离
        // 前3s滑翔后步行
        if (k / (v2 * 1.0) <= 3)
            g[i][n] = k / (v2 * 1.0);
        else
            g[i][n] = 3 + (k - v2 * 3.0) / (v1 * 1.0);
    }
    
    // 构建中间点之间的交通时间
    for (int i = 2; i < n; i++) {
        for (int j = 2; j < n; j++) {
            if (i == j) continue;  // 跳过自身
            double k = jl(a[i], b[i], a[j], b[j]);
            // 前3s滑翔后步行
            if (k / (v2 * 1.0) <= 3)
                g[i][j] = k / (v2 * 1);
            else
                g[i][j] = 3 + (k - v2 * 3.0) / (v1 * 1.0);
        }
    }
    printf("%.6lf\n",disksal());
}
signed main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
    int T = 1; 
    solve();
}

I. Barbecue

cpp

python

python版本无法快速输出，因此过不了第七个样例

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
import sys
input = lambda: sys.stdin.readline().strip()
n, q = map(int, input().split())
s = input().strip()
s = ' ' + s  # 使索引从1开始

P = 13331
mod = 10 ** 9 + 7
lh = [0] * (n + 2)
rh = [0] * (n + 2)
p = [1] * (n + 2)



# 构建哈希数组
for i in range(1, n + 1):
    lh[i] = (lh[i-1] * P + ord(s[i])) % mod     # 构建正向哈希
    rh[i] = (rh[i-1] * P + ord(s[n - i + 1])) % mod     # 构建反向哈希
    p[i] = (p[i-1] * P) % mod                    # 构建p数组,(P的幂次)

def query_lh(l, r):
    return (lh[r] - lh[l-1] * p[r - l + 1]) % mod

def query_rh(l, r):
    return (rh[n - l + 1] - rh[n - r] * p[r - l + 1]) % mod

for _ in range(q):
    l, r = map(int, input().split())
    if query_lh(l, r) == query_rh(l, r):    # 如果
        print("Budada")
    else:
        length = r - l + 1
        if length % 2:
            print("Putata")
        else:
            print("Budada")

L . Candy Machine

题意简述：
JB发现了一个装有N颗糖果的糖果机。他可以选择一个糖果的子集（可以是任意数量的糖果）。选定子集后，计算这些被选糖果的平均甜度值X。所有甜度值严格大于X的糖果都将属于JB。JB希望最大化他能获得的糖果数量。注意，他只有一次选择机会。

cpp

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
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1000010;
//typedef pair<int, int> PII;
//vector<PII> p;
//int n, m, x;
int a[N];
double pre[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
 
	}
	sort(a + 1, a + n + 1);
	pre[1] = a[1];
	for (int i = 2; i <= n; i++)
	{
		pre[i] = pre[i - 1] + a[i];
	}
 
	//for (int i = 0; i < n; i++)
	//	cout << pre[i] << " ";
	int ans = 0;
	double p = 0,avg;
	for (int i = 1; i <= n; i++)
	{
	  avg = pre[i] / i;
		int l = 0, r = i;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (a[mid] <= avg * 1.0)
				l = mid;
			else
				r = mid - 1;
		}
		ans = max(ans, i - r);
	}
	cout << ans << endl;
}

python

python 版本还是会超时

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
import sys
import bisect
input = lambda: sys.stdin.readline().rstrip()

n = int(input())

l = [0] + list(map(int, input().split()))

l.sort()

brr = [0] * (n+10)

brr[1] = l[1]
for i in range(1,n+1):
    brr[i] = brr[i-1] + l[i]

res = 0
ans = 0
for i in range(1,n+1):
    avg = brr[i] / i
    lef = 0
    rig= i
    idx = bisect.bisect_right(l, avg)	#找到第一个大于avg的位置
    #print(avg,idx)
   # print(idx)
    # while(lef<=rig):      不是二分答案
    #     mid = lef + (rig-lef)// 2
    #     if avg < l[mid]:
    #         ans = mid
    #         rig = mid - 1
    #     else:
    #         lef = mid+1
    res = max(res,i-idx+1)
print(res)

M. BpbBppbpBB

题意：

​ 有C和S两种类型的图形，取一网格纸将多个cs放入其中，图形可以多次旋转90度。

  • 保证图形全位于网格纸内才能放入
  • 图形不相互重叠

思路：

  • 由于C类型有两个洞，S类型有一个洞，可以推出C*2+S*1=洞数
  • 那么关键在于洞的识别：我们要采用6*6的矩阵来确保这个洞属于CS（卡了我好久）
  • 可以通过先枚举行，再枚举列确保每次找到的端点都是洞的左上方，然后通过相对位置判断是否为洞
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <utility>
using namespace std;
typedef long long LL;
const int N = 1e3 +10; 
char arr[N][N];
int brr[N][N];

typedef pair<int, int> PA;
typedef pair<PA, int> PA2;
int n,m;


char s[10][19] = {
"######",
"##..##",
"#....#",
"#....#",
"##..##",
"######"
};

bool judge(int x, int y) {
    int xx = x -2;
    int yy = y -1;
    for(int i = 0; i<6; i++)
    {
        for(int j = 0; j<6; j++)
        {
            if(arr[xx+i][yy+j] != s[i][j])
                return false;
           
        }
    }
    return true;

}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> n >> m;
    int a  = 0, b = 0;
    for (int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=m; j++)
        {
            cin >> arr[i][j];
        }
    }
    //cout << n << m << endl;
    int cnt = 0;
    for (int i = 2; i<=n; i++)
    {
        for(int j = 2; j<=m;j++)
        {
        
            if(judge(i,j))
            {
            //    cout << i << " " << j << endl;
                 brr[i][j] = 1;
                
                 
                arr[i+1][j-1] = '#';
                arr[i+2][j-1] = '#';

                arr[i][j] = '#';
                arr[i+1][j] = '#';
                arr[i+2][j] = '#';
                arr[i+3][j] = '#';
                
                arr[i][j+1] = '#';
                arr[i+1][j+1] = '#';
                arr[i+2][j+1] = '#';
                arr[i+3][j+1] = '#';
               
                arr[i+1][j+2] = '#';
                arr[i+2][j+2] = '#';

               // cout << arr[i][j] << arr[i-1][j]  << arr[i][j-1]
                //arr[i][j] = 1;
                cnt++;
            }
        }
    }
    // for (int i = 1; i<=n; i++)
    // {
    //     for(int j = 1; j<=m;j++)
    //     {
    //         cout << brr[i][j] ;
    //     }
    //     cout << endl;
    // }

    
    for (int i = 2; i<=n; i++)
    {
        for(int j = 2; j<=m;j++)
        {
            if(brr[i][j] == 1)
            {
            
                    if(brr[i+7][j] == 1)
                        {
                            brr[i+7][j] = 0;
                            a++;
                        }
                
                    if(brr[i][j+7] == 1)
                    {
                        brr[i][j+7] = 0;
                        a++;
                    }
            }
        
        }
    }

  //  cout << cnt << endl;
    cout << a << " "<< cnt - 2*a<< endl;

}