# 整体评价

D题感觉像博弈论书的经常提到的一个场景题。

E题题意有点晦涩，赛后才看明白啥意思，F题是道经典题吧，但是感觉太追求最优解了。

ST预处理，查询为分治二分，时间复杂度为 +

## A. 小辰打比赛

import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(), s = sc.nextInt();

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);

int res = 0;
for (int i = 0; i < n; i++) {
if (s <= arr[i]) break;
res += arr[i];
}
System.out.println(res);
}

}


## B. 小辰的圣剑

import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
long m = sc.nextLong(), u = sc.nextLong();

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int[] brr = new int[n];
for (int i = 0; i < n; i++) {
brr[i] = sc.nextInt();
}

int ans = 0;
for (int i = 0; i < n; i++) {
long s1 = 0, s2 = 0;
for (int j = i; j < n; j++) {
s1 += arr[j];
s2 += brr[j];
if (s1 > m || s2 > u) break;
ans = Math.max(ans, j - i + 1);
}
}
System.out.println(ans);
}

}


## C. 陶陶学算术

import java.io.BufferedInputStream;
import java.util.*;

public class Main {

static List<int[]> split(int v) {
List<int[]> res = new ArrayList<>();
for (int i = 2; i <= v / i; i++) {
if (v % i == 0) {
int cnt = 0;
while (v % i == 0) {
v /= i;
cnt++;
}
}
}
if (v > 1) res.add(new int[] {v, 1});
return res;
}

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();

Map<Integer, Integer> hash1 = new HashMap<>();
int sign1 = 1;
for (int i = 0; i < n; i++) {
int op = sc.nextInt();
int x = sc.nextInt();
if (x < 0) {
x = -x;
sign1 = -sign1;
}
List<int[]> factors = split(x);
if (op == 1) {
for (int[] e: factors) {
hash1.merge(e[0], e[1], Integer::sum);
}
} else {
for (int[] e: factors) {
hash1.merge(e[0], -e[1], Integer::sum);
}
}
}

int m = sc.nextInt();
Map<Integer, Integer> hash2 = new HashMap<>();
int sign2 = 1;
for (int i = 0; i < m; i++) {
int op = sc.nextInt();
int x = sc.nextInt();
if (x < 0) {
x = -x;
sign2 = -sign2;
}
List<int[]> factors = split(x);
if (op == 1) {
for (int[] e: factors) {
hash2.merge(e[0], e[1], Integer::sum);
}
} else {
for (int[] e: factors) {
hash2.merge(e[0], -e[1], Integer::sum);
}
}
}

if (sign1 != sign2) {
System.out.println("NO");
} else {
boolean ok = true;
for (Map.Entry<Integer, Integer> kv: hash1.entrySet()) {
int v2 = hash2.getOrDefault(kv.getKey(), 0);
if (kv.getValue() != v2) {
ok = false;
break;
}
}
for (Map.Entry<Integer, Integer> kv: hash2.entrySet()) {
int v2 = hash1.getOrDefault(kv.getKey(), 0);
if (kv.getValue() != v2) {
ok = false;
break;
}
}
System.out.println(ok ? "YES" : "NO");
}
}

}


## D. 小辰的借钱计划

• E > a， 则交换
• E <= a, 则不交换

a的因子个数，可以在求解，倍数的话，可以快速搞定

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

// 求因子和，因子总数
public static int[] factors(int v) {
int res = 0;
int cnt = 0;
for (int i = 1; i <= v / i; i++) {
if (v % i == 0) {
if (v / i == i) {
res += i;
cnt++;
} else {
res += i;
res += v / i;
cnt += 2;
}
}
}
return new int[] {res, cnt};
}

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));

int t = sc.nextInt();
while (t-- > 0) {
int m = sc.nextInt(), a = sc.nextInt();

if (2 * a >= m) {
System.out.println("NO");
} else {
// 倍数的个数(包含a)
int n1 = ((m - a) / a);
int e1 = (n1 + 1) * n1 / 2 * a;

// 因子的个数(包含a)
int[] tmp = factors(a);
int n2 = tmp[1];
int e2 = tmp[0];

// 不会int溢出
if (e1 + e2 > a * (n1 + n2)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}

}


## E. 小辰的智慧树

import java.io.*;
import java.util.*;
import java.util.function.Function;

public class Main {

public static void main(String[] args) {
int n = sc.nextInt();
long m = sc.nextLong();

int mz = 0;
int[][] ps = new int[n][2];
for (int i = 0; i < n; i++) {
ps[i][0] = sc.nextInt();
ps[i][1] = sc.nextInt();
mz = Math.max(ps[i][0] + 1, mz);
}

// 定义评估函数
Function<Integer, long[]> evaluator = (h) -> {
long y = 0;
long acc = 0;
for (int i = 0; i < n; i++) {
if (ps[i][0] >= h) {
long x = ps[i][0] - Math.max(h, ps[i][1]);
y += x;
acc += x * (ps[i][0] * 2 - x);
}
}
return new long[] {acc, y};
};

// 二分
int l = 0, r = mz;
while (l <= r) {
int mid = l + (r - l) / 2;

long[] cur = evaluator.apply(mid);
long y = cur[1];
if (y > m) {
l = mid + 1;
} else {
r = mid - 1;
}
}

long[] cur = evaluator.apply(l);
long res = cur[0];
long y = cur[1];
// 补上剩余的
if (l > 0 && m > y) {
res += (m - y) * (l * 2 - 1);
}

System.out.println(res);
}

static
private StringTokenizer tokenizer = new StringTokenizer("");
private String innerNextLine() {
try {
} catch (IOException ex) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String nextLine = innerNextLine();
if (nextLine == null) {
return false;
}
tokenizer = new StringTokenizer(nextLine);
}
return true;
}
public String nextLine() {
tokenizer = new StringTokenizer("");
return innerNextLine();
}
public String next() {
hasNext();
}
public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
// 若需要nextDouble等方法，请自行调用Double.parseDouble包装
}

}



## F. 小辰刚学 gcd

Java卡在56%， 等价C++（常数优化后）卡90%。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}

int main() {

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int n, q;
cin >> n >> q;
vector<long> arr(n);
vector<vector<pair<long, int>>> g(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
long v = arr[i];
g[i].push_back({v, i});
if (i > 0) {
auto& prev = g[i - 1];
for (auto& pair : prev) {
long tv = gcd(v, pair.first);
if (tv != v) {
g[i].push_back({tv, pair.second});
}
v = tv;
if (v == 1) break;
}
}
}
vector<int> res;
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
l--;  // adjust for zero-based indexing
r--;  // adjust for zero-based indexing
auto& rightList = g[r];
int left = 0, right = rightList.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (rightList[mid].second >= l) {
left = mid + 1;
} else {
right = mid - 1;
}
}
res.push_back(left);
}
for (auto& val : res) cout << val << "\n";
return 0;
}


3 3 评论