比赛链接

校内正式赛：https://ac.nowcoder.com/acm/contest/130719

校外同步赛：https://ac.nowcoder.com/acm/contest/130859

点评

在此，我谨向各方致以诚挚的感谢：首先，衷心感谢北华大学教务处的精心筹备，是你们的专业与用心为活动奠定了优质基础；同时，感谢各位老师的悉心指导与鼎力支持，为我们提供了宝贵的方向与保障；也感谢牛客平台提供的优质展示与实践空间，让想法得以落地、交流得以实现；最后，特别感谢给予我验题的机会，这份信任与认可让我倍感荣幸。

出题情况以及验题报告

出题人

木木三 https://ac.nowcoder.com/acm/contest/profile/934662562 ：C F G H I J

多多 https://www.nowcoder.com/users/619886673 ：A B D E K L

验题人

在此再次感谢各位验题人，感谢各位指正相关问题，感谢沟通

预估难度

  • A 寻找北华之光：800
  • I 键盘又坏了：800–1000
  • L Hi 老铁，欢迎加入快手！：800–1000
  • F 怎么这么多快递：1000–1200
  • B 多多的分形世界树：1100–1200
  • K 子路，冉有，公西华侍坐：1200–1300
  • D 我心灵的窗口，只滑动你的名字：1300–1600
  • C Dog and cat：1400–1500
  • E 蓝桥霸王：1400–1600
  • H 地球 OL 金手指：1400–1600
  • J 木木三肚子不舒服：1600–1800
  • G 一桃杀三猴：1700–1800（全场最难）

赛前预估通过量排序（从多到少）

A、I、L、F、B、K、C、G、D、E、H、J

正式赛实际通过排序（从多到少）

A、I、L、H、F、K、E、D、G、C、B、J

同步赛实际通过排序（从多到少）

A、K、F、L、I、H、D、E、C、G、J、B

答题情况

北华大学第十三届程序设计竞赛 单题真实通过率

（按「通过人数 / 总提交数」计算，题号横向展示）

一、校内正式赛数据

指标

A

B

C

D

E

F

G

H

I

J

K

L

通过人数

45

5

6

15

16

21

13

22

31

0

19

26

总提交数

51

26

12

43

71

57

137

183

55

16

51

95

真实通过率

88.24%

19.23%

50.00%

34.88%

22.54%

36.84%

9.49%

12.02%

56.36%

0.00%

37.25%

27.37%

二、校外同步赛数据

指标

A

B

C

D

E

F

G

H

I

J

K

L

通过人数

132

12

22

62

49

79

31

63

70

16

84

72

总提交数

160

14

93

154

102

115

204

216

143

78

160

207

真实通过率

82.50%

85.71%

23.66%

40.26%

48.04%

68.70%

15.20%

29.17%

48.95%

20.51%

52.50%

34.78%

三、补充说明

  • 真实通过率 = 通过人数 ÷ 总提交数 × 100%，更能反映每一次提交成功的概率，避免了“报名人数分母”带来的偏差。
  • 正式赛中，A题通过率最高（88.24%），说明提交的选手几乎都能一次或少量提交AC；G题通过率最低（9.49%），是提交后最容易翻车的题目。
  • 同步赛中，B题反超成为通过率最高（85.71%），而G题依旧是低通过率（15.20%），两场比赛的难题/易题分布基本一致。

A [2026 BHU ACM CPC] 寻找北华之光

签到题

输入一个字符串，在这个字符串后面追加输出 " is the Light of Beihua!" 即可。

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        String str = sc.next();
        System.out.println(str+" is the Light of Beihua!");
    }
}

B [Minecraft] 多多的分形世界树

简单树论 搜索算法

我只要找这个树从根节点到离根节点距离最长的那个点就行，如果有一系列距离最长的点，就取编号最小的那一个

两种搜索算法都行

解法 1：BFS 广度优先搜索

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {

        int n = sc.nextInt();

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        boolean[] visited = new boolean[n + 1];
        int[] deepth = new int[n + 1];
        int maxDeepth = 0;
        int result = Integer.MAX_VALUE;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        deepth[1] = 0;
        visited[1] = true;

        while (!queue.isEmpty()) {
            int f = queue.poll();
            for (Integer i : adj.get(f)) {
                if (!visited[i]) {
                    visited[i] = true;
                    deepth[i] = deepth[f] + 1;
                    queue.add(i);
                }
                if (deepth[i] > maxDeepth) {
                    maxDeepth = deepth[i];
                    result = i;
                }
                if (deepth[i] == maxDeepth) {
                    result = Math.min(result, i);
                }
            }
        }
        System.out.println(result + " " + maxDeepth);
    }
}

解法 2：DFS 深度优先搜索

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);

    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static int[] depth;
    static int maxDepth;
    static int result;

    public static void main(String[] args) {

        int n = sc.nextInt();
        adj = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        visited = new boolean[n + 1];
        depth = new int[n + 1];
        maxDepth = 0;
        result = Integer.MAX_VALUE;

        depth[1] = 0;
        dfs(1);

        System.out.println(result + " " + maxDepth);
    }

    static void dfs(int f) {
        visited[f] = true;
        for (int v : adj.get(f)) {
            if (!visited[v]) {
                depth[v] = depth[f] + 1;
                if (depth[v] > maxDepth) {
                    maxDepth = depth[next];
                    result = v;
                }
                if (depth[v] == maxDepth) {
                    result = Math.min(result, v);
                }
                dfs(v);
            }
        }
    }
}

C Dog and cat

枚举暴力 图论

题意简述

狗从起点走"日"字到达终点，每根骨头周围曼哈顿距离 ≤10 的格子为禁区。可以最多移除一根骨头，求最少步数。

解题思路

核心思想：枚举 + BFS

由于只能移除至多一根骨头，直接枚举

n+1 种情况：

不移除任何骨头

移除第 1,2,…,n根骨头

每种情况做一次 BFS 求骑士最短路，取最小值。

禁区处理技巧

用 cnt[x][y] 记录格子

(x,y)被几根骨头覆盖：

cnt > 0 → 禁区，不可走

cnt = 0 → 可走

移除骨头时将其覆盖格子 cnt--，恢复时 cnt++，避免重建整个禁区。

#include <bits/stdc++.h>
using namespace std;

const int LN = 1005;
const int INF = 1e9;

int dx[] = {1, 2, -1, -2, 1, 2, -1, -2};  // 修复了逗号 bug
int dy[] = {2, 1,  2,  1,-2,-1, -2, -1};

int n;
int boneX[105], boneY[105];
int cnt[LN][LN];      // 全局：每格被几根骨头覆盖
int dist[LN][LN];     // 全局：BFS 距离
bool vis[LN][LN];     // 全局：BFS 访问标记

int bfs(int sx, int sy, int ex, int ey) {
    if (cnt[sx][sy] > 0) return INF;  // 起点在禁区
    if (sx == ex && sy == ey) return 0;
    if (cnt[ex][ey] > 0) return INF;  // 终点在禁区

    memset(vis, 0, sizeof(vis));  // 只需清 vis，非常快

    queue<pair<int,int>> q;
    vis[sx][sy] = 1;
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < LN && ny >= 0 && ny < LN 
                && !cnt[nx][ny] && !vis[nx][ny]) {
                dist[nx][ny] = dist[x][y] + 1;
                vis[nx][ny] = 1;
                if (nx == ex && ny == ey) return dist[nx][ny];  // 提前终止
                q.push({nx, ny});
            }
        }
    }
    return INF;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    int ex, ey, sx, sy;
    cin >> ex >> ey >> sx >> sy;

    for (int i = 0; i < n; i++)
        cin >> boneX[i] >> boneY[i];

    // 建立禁区计数
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
        for (int j = -10; j <= 10; j++) {
            for (int k = -10; k <= 10; k++) {
                if (abs(j) + abs(k) > 10) continue;
                int x = boneX[i] + j, y = boneY[i] + k;
                if (x >= 0 && x < LN && y >= 0 && y < LN)
                    cnt[x][y]++;
            }
        }
    }

    // 不移除任何骨头
    int ans = bfs(sx, sy, ex, ey);

    // 枚举移除第 i 根骨头
    for (int i = 0; i < n; i++) {
        // 移除
        for (int j = -10; j <= 10; j++)
            for (int k = -10; k <= 10; k++) {
                if (abs(j) + abs(k) > 10) continue;
                int x = boneX[i] + j, y = boneY[i] + k;
                if (x >= 0 && x < LN && y >= 0 && y < LN)
                    cnt[x][y]--;
            }

        ans = min(ans, bfs(sx, sy, ex, ey));

        // 恢复
        for (int j = -10; j <= 10; j++)
            for (int k = -10; k <= 10; k++) {
                if (abs(j) + abs(k) > 10) continue;
                int x = boneX[i] + j, y = boneY[i] + k;
                if (x >= 0 && x < LN && y >= 0 && y < LN)
                    cnt[x][y]++;
            }
    }

    cout << (ans >= INF ? -1 : ans) << "\n";
    return 0;
}

D 我心灵的窗口，只滑动你的名字

滑动窗口，数据结构(单调队列)

https://oi-wiki.org/ds/monotonous-queue/

滑动窗口：

这个问题要求解满足特定条件的最长连续子数组，非常适合使用滑动窗口（双指针）来解决。我们可以维护一个窗口 [left, right]，并保证这个窗口内的子数组始终满足 “纯粹互补” 的条件。

滑动窗口定义指针和状态：

left, right：窗口的左右边界，初始都为 0。

currentSum：窗口 [left, right] 内所有元素的算术和。

currentXor：窗口 [left, right] 内所有元素的异或和。

maxLength：记录满足条件的最长子数组长度。

滑动窗口窗口移动：

我们用 right 指针不断向右扩展窗口，遍历整个数组。

在每一次循环中，将 a[right] 添加到窗口中，即更新 currentSum 和 currentXor。

检查窗口有效性：判断 currentSum 是否还等于 currentXor。

如果相等：说明窗口 [left, right] 仍然是 "纯粹互补" 的。这是一个有效的窗口，我们用它的长度 right - left + 1 来更新 maxLength。

如果不相等：说明新加入的 a[right] 与窗口内已有的元素产生了“冲突”（即发生了进位）。此时，我们需要从左边收缩窗口，直到窗口重新变得有效。我们不断地将 a[left] 从窗口中移除（更新 currentSum 和 currentXor），并递增 left 指针，直到 currentSum == currentXor 再次成立。

循环：

right 指针从 0 遍历到 n-1。在 right 每向右移动一步后，我们都通过收缩 left 来找到一个以 right 为右边界的最长有效窗口，并用其长度更新 maxLength。

随后问题的关键在于理解 “算术和 (Sum) == 按位异或和 (XOR Sum)” 这个条件的本质。

我们知道，加法 A + B 和异或 A ^ B 的关系是：

A + B = (A ^ B) + 2 * (A & B)

其中 A & B 表示 A 和 B 在二进制表示下，同时为 1 的那些位。2 * (A & B) 实质上就是加法运算中产生的进位。

因此，A + B == A ^ B 这个条件成立的充要条件是 2 * (A & B) == 0，也就是 A & B == 0。这意味着 A 和 B 的二进制表示中，没有任何一位同时为 1。

这个结论可以推广到多个数：

a[L] + ... + a[R] == a[L] ^ ... ^ a[R]

当且仅当，对于任意的二进制位 k，在子数组 a[L...R] 的所有数中，最多只有一个数的第 k 位是 1。

换句话说，这些数字在二进制位上是“互斥”的，相加时不会产生任何进位。这句话在题目补充中已经给出。

可以每次检查 64 位，有没有进位，进位了就出队列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    int l = 0, ans = 1;
    bool bit[64] = {0}; 
    
    for (int r = 0; r < n; ++r) {
        ll x = a[r];
        
        bool ok = true;
        for (int i = 0; i < 64; ++i) {
            if ((x >> i & 1) && bit[i]) {
                ok = false;
                break;
            }
        }
        
        while (!ok) {
            ll y = a[l];
            for (int i = 0; i < 64; ++i) {
                if (y >> i & 1) bit[i] = 0;
            }
            l++;
            
            ok = true;
            for (int i = 0; i < 64; ++i) {
                if ((x >> i & 1) && bit[i]) {
                    ok = false;
                    break;
                }
            }
        }
        
        for (int i = 0; i < 64; ++i) {
            if (x >> i & 1) bit[i] = 1;
        }
        
        ans = max(ans, r - l + 1);
    }
    
    cout << ans << endl;
    return 0;
}

或者说可以用异或前缀简写

每次出队列是不满足上述推导关系

n=int(input())
a=[0]+list(map(int,input().split()))
b=[0]*(n+1)
c=[0]*(n+1)
for i in range(1,n+1):
    b[i]=b[i-1]+a[i]
    c[i]=c[i-1]^a[i]
ans=1
l=0
for r in range(1,n+1):
    while(l<r and (b[r]-b[l])!=(c[r]^c[l])):
        l+=1
    ans=max(ans,r-l)
print(ans)

E 蓝桥霸王

数学模拟题

解决这个问题的关键是分析角色在任意一段轨道上滑行时能量的变化情况。

动能定理告诉我们，合外力对物体做的总功等于物体动能的改变量。

W_net = ΔE_k = E_k_final - E_k_initial

其中，E_k = 1/2 * m * v^2是物体的动能。

现在，我们来分析作用在角色上的力以及它们做的功。考虑角色从一段轨道的起点P1(x1, y1)滑到终点P2(x2, y2)。

  1. 重力 (Gravity Force)
  2. 摩擦力 (Friction Force)
  3. 支持力 (Normal Force)

现在我们来简化摩擦力做的功W_f。

  • 轨道段的长度L是P1和P2之间的直线距离:L = sqrt((x2 - x1)² + (y2 - y1)²).
  • cos(θ)可以通过轨道的几何关系得到。cos(θ) = (水平距离) / (斜边长度) = (x2 - x1) / L。 (因为题目保证x是严格递增的，所以x2 - x1 > 0)。

将cos(θ)的表达式代入W_f：

W_f = -(μ * mg * cos(θ)) * L = -(μ * mg * ( (x2-x1) / L )) * L

L被消掉了，得到一个非常简洁的表达式：

W_f = -μ * mg * (x2 - x1)

这个公式说明，在一段直轨道上，摩擦力做的功只与水平移动距离有关，而与斜坡的陡峭程度无关！这是一个非常重要的结论，大大简化了计算。

现在我们将所有力做的功加起来：

W_net = W_g + W_f + W_N

W_net = -mg(y2 - y1) - μ * mg * (x2 - x1) + 0

根据动能定理W_net = E_k_final - E_k_initial：

1/2 * m * v2² - 1/2 * m * v1² = -mg(y2 - y1) - μ * mg * (x2 - x1)

观察上式，每一项都包含质量m。我们可以将m约掉。这意味着角色的质量不影响最终结果。

1/2 * v2² - 1/2 * v1² = -g(y2 - y1) - μ * g * (x2 - x1)

为了方便计算，我们整理一下，求解v2²：

v2² - v1² = -2g(y2 - y1) - 2μg(x2 - x1)

v2² = v1² - 2g(y2 - y1) - 2μg(x2 - x1)

这就是我们需要的核心递推公式。它表明，只要我们知道角色在一段轨道起点的速度v1，我们就可以计算出它在终点的速度v2。

但是这个公式为已经推导给出，大家直接用推导公式即可

不断更新 v2

如果是 0 结束循环 输出 0.00

否则输出最后的速度 v

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    double R,Wa;
    int N;
    cin>>R>>Wa>>N;
    vector<double> x(N+1), y(N+1);
    for(int i = 0; i <= N; i++) {
        cin>>x[i]>>y[i];
    }
    double YR = R*R;       
    const double g = 9.8;
    for(int i = 0; i < N; i++) {
        double dx = x[i+1] - x[i];
        double dy = y[i+1] - y[i];
        double L = sqrt(dx*dx + dy*dy);   
        double WWWW = -dy / L;        
        double a = g*WWWW - Wa*g*(dx/L);
        double ds = L;
        double piggy= YR+2*a*ds;
        if(piggy < 0) {
            printf("0.00\n");
            return 0;
        }
        YR = piggy;
    }
    printf("%.2f\n", sqrt(YR));
    return 0;
}

F 怎么这么多快递

数据结构 模拟

给定 n个快递信息，每个信息包含一个取件码（格式：AA-B-CCCC）和收件人姓名。随后有 t次查询，每次输入一个姓名，需按字典序升序输出该收件人名下的所有取件码。若查无此人，则输出 -1。

数据结构选择：由于一个收件人可能对应多个取件码，我们需要一种“键-值”映射关系。使用 std::map<string, vector<string>>。其中 Key 为姓名，Value 为取件码列表（vector）。std::map 会自动对姓名进行排序，但本题只要求对同一个人的取件码排序，因此我们在录入完成后，对每个 vector 进行排序即可。字典序规则：题目描述的取件码比较规则本质上就是标准的字符串字典序比较（从左到右逐位比较 ASCII 码）。因此，我们可以直接使用 C++ 默认的字符串比较运算符或 std::sort。查询处理：对于每次查询，先判断 map 中是否存在该姓名。若存在，遍历并输出对应的 vector；若不存在，输出 -1。

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    // 使用 map 存储：姓名 -> 取件码列表
    map<string, vector<string>> storage;

    for (int i = 0; i < n; ++i) {
        string code, name;
        cin >> code >> name;
        storage[name].push_back(code);
    }

    // 预先对每个人的取件码进行字典序排序
    for (auto &entry : storage) {
        sort(entry.second.begin(), entry.second.end());
    }

    int t;
    cin >> t;
    while (t--) {
        string queryName;
        cin >> queryName;

        // 查找是否存在该收件人
        if (storage.find(queryName) != storage.end()) {
            for (const string &code : storage[queryName]) {
                cout << code << "\n";
            }
        } else {
            cout << "-1\n";
        }
    }

    return 0;
}

G 一桃杀三猴

数学题 智力题 逻辑题 烧脑题 脑筋急转弯(?)

设第 i 次操作前有 个桃子，每次操作后变为 。

为避免分数，引入 zi=xi+n-1，可化为等比递推：。

要保证连续进行 (n) 次且始终为整数，最小取 (z1=n^n)，最终得到初始桃子数为 x1=n^n-n+1)。

详细数学推理请看此链接：https://www.cnblogs.com/tonz/p/4820767.html

//fly!
#include<bits/stdc++.h>
#define ll long  long
#define ull unsigned long long
#define fi first
#define all(x) x.begin(),x.end()
#define se second
#define be begin()
#define en end()
#define endl <<"\n"
#define double long double
#define endd <<" "
using namespace std;
//atuo lfy 琴弦断了，缘也尽了，你也走了
void solve() {   
  int n;cin>>n;
  if(n==2){
    cout<<7 endl;return ;
  }else{
    ll t=pow(n,n)-n+1;
    cout<<t endl;
  }
}
int main() {
    std::ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    int T = 1;
    // scanf("%d", &T);
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

H 地球OL金手指

数学题 智力题

本质是一个很经典的瓶子问题。只增加了一个抽奖百分百的机制，也就是说除开买第一瓶水的钱，剩下的钱全都可以1比1换成水（应该是茶，方便理解统称水好了）。

则理论上初始能买到的最多的水就是sum=n-t+1（初始资金减去一瓶水剩下的钱 ，加1）

之后只需要考虑空瓶（等价于初始买到的水数）即可 （sum-1)/(k-1)（算是一个公式，具体推导和原理可以去搜瓶子问题）

//fly!
#include<bits/stdc++.h>
#define ll long  long
#define ull unsigned long long
#define fi first
#define all(x) x.begin(),x.end()
#define se second
#define be begin()
#define en end()
#define endl <<"\n"
#define double long double
#define endd <<" "
using namespace std;
//atuo lfy 琴弦断了，缘也尽了，你也走了
void solve() {   
  ll n,k,t;cin>>n>>k>>t;
  if(k==1){
        if(n>=t)cout<<-1 endl;
        else cout<<0 endl;
        return 0;
    }
    if(n<t){
      cout<<0 endl;return ;
    }
    ll sum=n-t+1;
    ll ans=0;
    if(sum>1){
      ans=(sum-1)/(k-1);
    }
    cout<<ans+sum endl;
}
int main() {
    std::ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    int T = 1;
    // scanf("%d", &T);
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

I 键盘又坏了

数据结构 模拟

仔细阅读题面就行将题目给出的坐标用map存下（当然也有其他的方法）之后对应输出就可以了

这道题目虽然给出了两种键盘布局，但实际上“原键盘（QWERTY）”是干扰信息，我们只需要关注新键盘（字母表顺序）布局。

题目大意

  1. 新键盘布局：字母 A-Z 按顺序排列在三行中，坐标规则已给出。
  2. 输入规则：
  3. 任务：给定字符串，输出总耗时（即字符串长度）及每一秒按下的坐标。

题目思路

  • 总时间：由于每秒输出一个字符，总时间 n直接等于字符串的长度 s.length()。
  • 坐标映射：

我们可以根据字符在字母表中的位置（0-25）来推算坐标：

  • 大小写判断：
# 构建新键盘字母到坐标的映射（仅大写，小写统一转大写匹配）
letter_coords = {
    'A': (0, 0), 'B': (0, 1), 'C': (0, 2), 'D': (0, 3), 'E': (0, 4),
    'F': (0, 5), 'G': (0, 6), 'H': (0, 7), 'I': (0, 8), 'J': (0, 9),
    'K': (1, 1), 'L': (1, 2), 'M': (1, 3), 'N': (1, 4), 'O': (1, 5),
    'P': (1, 6), 'Q': (1, 7), 'R': (1, 8), 'S': (1, 9),
    'T': (2, 1), 'U': (2, 2), 'V': (2, 3), 'W': (2, 4), 'X': (2, 5),
    'Y': (2, 6), 'Z': (2, 7)
}
SHIFT = (3, 0)  # Shift键固定坐标
# 读取输入字符串
s = input().strip()
n = len(s)
# 输出总时间
print(n)
# 处理每个字符，输出对应按键坐标
for char in s:
    # 统一转大写获取字母坐标
    upper_char = char.upper()
    y, x = letter_coords[upper_char]
    # 判断是否为大写字母，决定输出内容
    if char.isupper():
        # 大写：Shift + 字母坐标
        print(f"{SHIFT[0]} {SHIFT[1]} {y} {x}")
    else:
        # 小写：仅字母坐标
        print(f"{y} {x}")

J 木木三肚子不舒服

二分 贪心

题意：有 N 人需用一艘最多载两人的船过河，每次耗时取两人中较慢者。除木木三外其余人时间已知，木木三时间可调。要求在总耗时 ≤ T 内，使木木三过河时间尽可能大，并求此时总耗时；若无法满足则输出 -1。

思路：先不考虑木木三的时间，思考最优的过河方案。

对于河此岸人数n==2的情况，显然，耗费时间为二者中最长的一个，两人即可全部到达对岸；对于n==3的情况，先让最快的人带一人去对岸，最快的人回来，再接另一人去对岸，总共花费时间为a1+a2+a3

那么对于n>3的情况呢？我们可以先运送此岸上用时最长的两人，那么最优秀的运送方法有两种：

1.最快的1载最慢的n去对岸，1回此岸继续载次慢的n-1去对岸，a1最后再回到此岸，共用时2*a1+an+a(n-1)

2.最快的人1与次快的人2去对岸，最快的人1回到此岸，最慢的人n再与次慢的人n-1去对岸，次快的人2回到此岸，共用时a1+2*a2+an

那么此时我们在考虑木木三的时间，在一定的时间限制，要求最大，比较容易想到二分，于是我们只需要对木木三时间进行二分然后判断是否满足时间限制，求出最大的时间即可

//fly!
#include<bits/stdc++.h>
#define ll long  long
#define ull unsigned long long
#define fi first
#define all(x) x.begin(),x.end()
#define se second
#define be begin()
#define en end()
#define endl <<"\n"
#define double long double
#define endd <<" "
using namespace std;
//atuo lfy 琴弦断了，缘也尽了，你也走了
int n;
ll dp[100005];ll t[100005];
ll pd(ll w){
    ll t1[100005];
    for(int i=1;i<n;i++)t1[i]=t[i];
    t1[n]=w;
    sort(t1+1,t1+n+1); 
    dp[1]=t[1],dp[2]=t1[2];    
    for(int i=3;i<=n;i++)
    dp[i]=min(dp[i-1]+t1[1]+t1[i],dp[i-2]+t1[1]+2*t1[2]+t1[i]);
    return dp[n];
}
void solve() {  
    ll T; 
  cin>>n>>T;
  
    for(int i=1;i<n;i++)    
    cin>>t[i];
    sort(t+1,t+n);
    if(n==1){
        cout<<T endd<<T endl;;return ;
    }
    ll a=1,b=T+10;
    while(a<=b){
        ll w=(a+b)>>1;
        if(pd(w)<=T){
            a=w+1;
        }else{
            b=w-1;
        }
    }
    a-=1;
    cout<<a endd<<pd(a) endl;
}
int main() {
    std::ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    int T = 1;
    // scanf("%d", &T);
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

K 子路，冉有，公西华侍坐

前缀和&差分模版题

前缀和知识点

https://oi-wiki.org/basic/prefix-sum/

原题地址

https://codeforces.com/problemset/problem/816/B

#include <bits/stdc++.h>
using namespace std;
#define ll long long

constexpr int N = 200005;
ll a[N];
ll b[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    //cin >> t;
    while (t--) {
        ll n, k, q;
        cin >> n >> k >> q;
        ll maxx = 200000;
        for (int i = 1; i <= n; ++i) {
            ll l, r;
            cin >> l >> r;
            a[l]++;
            a[r + 1]--;
        }
        for (int i = 1; i <= maxx; ++i) {
            a[i] += a[i - 1];
            if (a[i] >= k) b[i]++;
        }
        for (int i = 1; i <= maxx; ++i) {
            b[i] += b[i - 1];
        }
        for (int i = 1; i <= q; ++i) {
            ll l, r;
            cin >> l >> r;
            cout << b[r] - b[l - 1] << endl;
        }
    }
    return 0;
}

L Hi老铁，欢迎加入快手！

简单博弈论

一、 核心概念：必胜态 (N-position) 与必败态 (P-position)

在公平组合游戏中（即两个玩家的可用操作只取决于当前局面，而与轮到谁无关），任何一个局面（状态）要么是必胜态，要么是必败态。

  • 必败态 (P-position, Previous player winning)：处在这个局面的玩家，无论他怎么操作，最终都会输掉比赛（前提是对手不犯错）。换句话说，从这个局面出发的所有合法操作，都会将游戏带入一个必胜态。
  • 必胜态 (N-position, Next player winning)：处在这个局面的玩家，至少存在一种操作，能将游戏带入一个必败态，从而确保自己最终获胜。

基本判定规则：

  1. 无法进行任何操作的最终局面是一个必败态。
  2. 如果一个局面可以转移到某个必败态，那么这个局面是必胜态。
  3. 如果一个局面的所有可转移局面都是必胜态，那么这个局面是必败态。

二、 分析游戏规则与局面

  1. 游戏局面：由库存(N, M)决定。
  2. 最终局面：(0, 0)。当轮到某人操作时，局面是(0, 0)，他无法进行任何操作，根据规则，他输了。因此，(0, 0)是一个必败态 (P-position)。
  3. 操作（状态转移）：从(N, M)可以转移到以下三种状态之一：

三、 从小局面开始推导

我们的目标是找出所有必败态的规律。我们已经知道(0, 0)是一个必败态。

  • 分析局面 (0, 1)：
  • 分析局面 (1, 1)：
  • 分析局面 (0, 2)：
  • 分析局面 (1, 2)（示例1）：
  • 分析局面 (2, 2)（示例2）：

四、 发现规律与证明

我们已经找到的必败态有：(0, 0),(0, 2),(2, 0),(2, 2)。

你可能会สังเกตเห็น一个规律：当 N 和 M 都是偶数时，该局面似乎是必败态。

我们来证明这个猜想。

猜想：一个局面(N, M)是必败态，当且仅当 N 和 M 都是偶数。

为了证明这个 "当且仅当" 的命题，我们需要证明两个方向：

  1. 证明：如果(N, M)中 N 和 M 都是偶数，那么它是一个必败态。
  2. 证明：如果(N, M)不是(偶数, 偶数)的形式，那么它是一个必胜态。

综上所述，对于任何非(偶数, 偶数)的局面，我们总能找到一种方法，一步将其变成(偶数, 偶数)的局面。

结论：我们的猜想被证明是正确的。

五、 最终结论与解题策略

  1. 必败态 (P-position)：N和M都是偶数。
  2. 必胜态 (N-position)：N和M中至少有一个是奇数。

作为先手，你面对的是初始局面(N, M)。

  • 如果初始局面是必胜态，你就可以通过一次精妙的操作，将其变为必败态，然后把这个“烂摊子”丢给对手。之后无论对手怎么走，他都会把局面变成必胜态，你再把它变回必败态，如此往复，直到最后你把(0,0)这个最终的必败态留给对手，你就赢了。
  • 如果初始局面是必败态，那么无论你怎么走，都会把局面变成一个必胜态。聪明的对手会抓住机会，把局面再变回必败态。这样你就落入了被动，最终会输掉。

所以，作为先手的你，获胜的条件是：初始局面(N, M)是一个必胜态。

解题算法：

判断输入的N和M是否不同时为偶数。

  • 如果N % 2 == 0并且M % 2 == 0，则初始局面是必败态，先手必败。输出NO。
  • 否则 (即(奇,奇),(奇,偶),(偶,奇)三种情况)，初始局面是必胜态，先手必胜。输出YES。 
#include<bits/stdc++.h>

using namespace std;

int main()
{
    long long a, b;
    cin >> a >> b;
    if (a % 2 == 0 && b % 2 == 0) {
        cout << "NO\n";
    }
    else
        cout << "YES\n";
}