语法周赛round31

T1¶

题意

给定两个非零整数 $a, b$：

$a$ 表示南北方向的风速
当 $a > 0$ 时，表示刮北风
当 $a < 0$ 时，表示刮南风
$b$ 表示东西方向的风速
当 $b > 0$ 时，表示刮东风
当 $b < 0$ 时，表示刮西风

需要根据南北、东西两个方向的风向组合，判断季风的实际方向，并输出对应的字符串：

北风 + 东风 $\rightarrow$ NorthEast
北风 + 西风 $\rightarrow$ NorthWest
南风 + 东风 $\rightarrow$ SouthEast
南风 + 西风 $\rightarrow$ SouthWest

思路

这是一个简单的条件判断问题：

根据 $a$ 的正负判断南北方向：
$a > 0$：North
$a < 0$：South
根据 $b$ 的正负判断东西方向：
$b > 0$：East
$b < 0$：West
将两个方向组合后输出对应结果。

由于题目保证 $a \neq 0,\ b \neq 0$，因此不需要考虑等于 $0$ 的情况。

具体实现

读入两个整数 $a, b$
使用条件判断语句根据 $a$、$b$ 的符号分类
输出对应的方向字符串

逻辑判断如下（$\land$ 表示逻辑与）：

若 $a > 0 \land b > 0$，输出 NorthEast
若 $a > 0 \land b < 0$，输出 NorthWest
若 $a < 0 \land b > 0$，输出 SouthEast
若 $a < 0 \land b < 0$，输出 SouthWest

本题不涉及复杂算法，关键在于准确理解符号与方向之间的对应关系。

T2¶

题意

W 公园门票有两种：

单次票：每次入园买一次，价格 $a$ 元；
年票：价格 $b$ 元，买了以后今年无限次入园。

今年计划去 $n$ 次，求最少花费。

思路

只有两种方案：

全买单次票：花费 $n \times a$
买一张年票：花费 $b$

年票一旦购买就可无限次入园，所以不需要考虑“买年票 + 再买单次票”的组合（组合不会更优）。

因此答案为：

\[ \min(n \times a,; b) \]

难点在于：$n,a,b \le 10^{18}$，直接算 $n\times a$ 可能溢出 long long。

方法一：只用 long long

关键：我们不直接算 $n\times a$，而是用除法来判断谁更小。

当 $a>0$ 时：

\[ n\times a \le b \iff n \le \left\lfloor \frac{b}{a} \right\rfloor \]

这样就避免了乘法溢出。

还要处理两个边界：

$n=0$：不去，答案 $0$
$a=0$：单次票免费，去多少次都是 $0$

判定逻辑

若 $n=0$ 或 $a=0$，输出 $0$
否则若 n <= b / a，说明 $n\times a \le b$，输出 n * a
- 这里乘法是安全的，因为已经保证 n*a <= b <= 1e18
否则输出 b

方法二：使用 __int128

__int128 是一种更大的整数类型，可以表示范围更广的整数。其占用内存为 128 位。因此可以表示的最大值为 $2^{127}-1$。这个值是大于 $10^{36}$ 的数。缺陷就是该类型不支持 cin 和 cout。

因此输出一个 __int128 类型的值，需要把数字一位一位拆出来拼成字符串再输出。

输入可以先输入到字符串，然后将字符串遍历存储 __int128 类型的变量内。

__int128 cost1 = (__int128)n * a;
__int128 cost2   = (__int128)b;
__int128 ans = min(cost1, cost2);

// 输出 __int128：转成字符串
if (ans == 0) 
{
    cout << 0;
    return 0;
}
string s;
while (ans > 0) 
{
    int d = (int)(ans % 10);
    s += char('0' + d);
    ans /= 10;
}
reverse(s.begin(), s.end());
cout << s;

T3¶

题意

有 $n$ 台抽奖机按顺序编号为 $1\sim n$。小 G 初始有 $x$ 积分。

第 $i$ 台抽奖机游玩规则：

游玩前需要至少 $a_i$ 积分，否则若当前积分 $< a_i$，小 G 立刻停止，不能再玩后面的机器。
若能游玩，则积分变化为：先花费 $a_i$，再获得 $b_i$，因此净变化为 $-a_i + b_i$。
每玩完一台后，如果当前积分 $\ge y$，小 G 立刻停止，不再继续。

要求输出小 G 停止时拥有的积分数。

思路

按照题意 从第 $1$ 台开始模拟 即可，因为：

抽奖机必须按顺序玩，且每台最多一次；
停止条件只依赖于“当前积分”和“当前机器的 $a_i$”。

模拟过程维护当前积分 sum：

对 $i=1\sim n$：

若 sum < a_i，无法支付，直接停止循环。
否则游玩该机器： $$\text{sum} \leftarrow \text{sum} - a_i + b_i$$
若游玩后 sum \ge y，达到目标，立即停止循环。

最终输出 sum。

复杂度：

只遍历一次，时间复杂度 $O(n)$；
只用常数额外空间，空间复杂度 $O(1)$。

具体实现

读入 $n,x,y$，令当前积分 sum = x
循环读入每台机器的 $a_i,b_i$ 并按顺序处理
每次先判断 sum < a_i 是否无法游玩
能游玩则执行更新 sum = sum - a_i + b_i
更新后若 sum >= y 立即停止
输出最终 sum
用 long long（或更大整型）存储积分，保证中间计算安全
按顺序模拟即可，不需要任何贪心或排序
读入 $n$ 可达 $10^5$，线性模拟足够通过

T4¶

题意分析

题目给出一副共有 $n$ 张的卡牌，从顶到底编号顺序已知。现在进行一次洗牌操作：

将前 $k$ 张卡牌分为牌堆 A；
将第 $k+1\sim n$ 张卡牌分为牌堆 B；
从牌堆 A 开始，轮流从 A、B 的顶部取一张牌，按顺序放入新牌堆；
当某一牌堆被取空后，将另一牌堆中剩余的卡牌按原顺序接到新牌堆后面。

最终要求输出洗牌后新牌堆中卡牌的顺序。

思路说明

我们可以直接使用数组模拟整个洗牌过程。

用数组 a[] 存储牌堆 A（原数组的前 $k$ 张）
用数组 b[] 存储牌堆 B（原数组的第 $k+1\sim n$ 张）
用数组 c[] 存储洗牌后的结果

具体实现

读入并拆分牌堆

先将所有卡牌读入数组 a，再把第 $k+1\sim n$ 张卡牌依次放入数组 b。

for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = k + 1; i <= n; i++) b[i - k] = a[i];
// 输入的第 k+1 张牌是牌堆 B 的第 1 张牌

此时：

牌堆 A 的大小为 $k$
牌堆 B 的大小为 $n-k$

模拟交替取牌过程

定义数组 c[] 存储最终结果，并用变量 pos 表示当前插入位置。

当两个牌堆都还有牌时，每一轮依次从 A、B 各取一张牌。

循环次数最多为：

\[ \min(k,\ n-k) \]

int pos = 1;
for (int i = 1; i <= n; i++) 
{
    if (i > k || i > n - k) break;
    // 若某一牌堆已取完，则停止交替取牌
    c[pos++] = a[i];
    c[pos++] = b[i];
}

处理剩余卡牌

交替取牌结束后，只会剩下 A 或 B 其中一个牌堆。

若牌堆 B 更长，则继续把 B 中剩余的牌按顺序加入；
否则把 A 中剩余的牌按顺序加入。

if (n - k > k)
    for (int i = k + 1; i <= n - k; i++) c[pos++] = b[i];
else
    for (int i = n - k + 1; i <= k; i++) c[pos++] = a[i];

// 全部读入存到牌堆 A
for (int i = 1; i <= n; i++) cin >> a[i];

// 将第 k+1 ~ n 张分到牌堆 B
for (int i = k + 1; i <= n; i++) b[i - k] = a[i];
// 输入的第 k+1 张牌是牌堆 B 的第 1 张牌

int pos = 1;

// 交替取牌，最多进行 min(k, n-k) 轮
for (int i = 1; i <= n; i++) 
{
    if (i > k || i > n - k) break;
    c[pos++] = a[i];
    c[pos++] = b[i];
}

// 将剩余牌堆按顺序接到末尾
if (n - k > k) 
{
    // B 更长，还剩下 b[k+1 .. n-k]
    for (int i = k + 1; i <= n - k; i++) c[pos++] = b[i];
} 
else 
{
    // A 更长（或相等），还剩下 a[n-k+1 .. k]
    for (int i = n - k + 1; i <= k; i++) c[pos++] = a[i];
}

// 输出结果
for (int i = 1; i <= n; i++) 
{
    if (i > 1) cout << ' ';
    cout << c[i];
}

T5¶

题意

地铁共有 $n$ 个站，被 $k$ 个收费区按分界点 $$1=p_0<p_1<\cdots<p_k=n+1$$ 划分。第 $i$ 个收费区为 $$[l_i,r_i]=[p_{i-1},\ p_i-1].$$

对每次询问 $(i,j)$（从站 $i$ 到站 $j$）票价规则按顺序判断：

若 $i=j$，收费 $1$。
若 $i\neq j$ 且在同一收费区，收费 $2$。
否则设 $a=\min(i,j),\ b=\max(i,j)$，若 $[a,b]$ 内包含 $m$ 个完整收费区（满足 $a\le l_x\le r_x\le b$），收费 $2+m$。

思路

先把每个收费区的左右端点预处理出来：

$L[i]=p_{i-1}$
$R[i]=p_i-1$

对每个询问：

令 $x=\min(i,j)$，$y=\max(i,j)$。
若 $x=y$，直接输出 $1$（规则 1）。
枚举所有收费区，找到 $x$ 所在收费区编号 $a$、$y$ 所在收费区编号 $b$（满足 $L[a]\le x\le R[a]$，$L[b]\le y\le R[b]$）。
若 $a=b$，输出 $2$（规则 2）。
否则进入规则 3：
中间被完整包含的收费区个数初值为 $$m=b-a-1$$
还需考虑边界两侧收费区是否被完整包含：
- 若 $x=L[a]$，说明左侧收费区 $a$ 从左端点开始被包含，$m$ 加 $1$；
- 若 $y=R[b]$，说明右侧收费区 $b$ 到右端点结束被包含，$m$ 加 $1$。
- 最终费用 $$\text{ans}=2+m.$$

由于 $k\le 1000$，每次询问枚举收费区 $O(k)$ 可以直接通过。

具体实现

读入 $n,k$ 和分界点 $p_0\sim p_k$
预处理 $L[i],R[i]$
每次询问：
若 $x=y$ 输出 $1$
枚举 $1\sim k$ 找到 $a,b$
若 $a=b$ 输出 $2$
否则按 $$m=b-a-1 + [x=L[a]] + [y=R[b]]$$ 输出 $\text{ans}=2+m$

for (int i = 1; i <= k; i++) 
{
    L[i] = p[i - 1];
    R[i] = p[i] - 1;
}
int q;
cin >> q;
while (q--) 
{
    long long x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    long long ans = 0;
    // 规则 1：同站进出
    if (x == y) {
        ans = 1;
        cout << ans << "\n";
        continue;
    }
    int a = -1, b = -1;
    // 找 x 和 y 所在的收费区编号
    for (int i = 1; i <= k; i++) 
    {
        if (a == -1 && L[i] <= x && x <= R[i]) a = i;
        if (b == -1 && L[i] <= y && y <= R[i]) b = i;
    }
    // 规则 2：同收费区不同站
    if (a == b) 
    {
        ans = 2;
        cout << ans << "\n";
        continue;
    }
    // 规则 3：计算完整收费区数量 m
    long long m = b - a - 1;
    if (x == L[a]) m++;
    if (y == R[b]) m++;
    ans = 2 + m;
    cout << ans << "\n";
}