[VP] 2024 ICPC 西安邀请赛

题目(Luogu): [ICPC2024 Xi’an I] ICPC2024 邀请赛西安站重现赛

PDF(适于打印): The 2024 ICPC China Shaanxi National Invitational Programming Contest

注意：PDF 版题目由本人根据 Luogu 题面使用 $\LaTeX$ 制作，不是官方版本，如果你需要在此基础上更改，请下载 源Tex文件（本人经验有限，诸多部分是边学边做，故显凌乱）。

UPD: 当时的我还不知道 Polygon

以下就按照 A 题顺序来讲吧：

Problem J. Triangle

给你一个两个直角边分别在 $x, y$ 轴，直角顶点在原点的直角三角形，求它占了几个格子（一个格子如果有 $\geq\frac{1}{2}$ 的面积在三角形里面，则被称为所占的格子）$1\leq a, b \leq 10^6$

可以看到数据范围并不大，因此我们可以设斜边方程为 $y=-\frac{b}{a}x+b$，沿着 $x$ 轴（或 $y$ 轴）扫描，记录每一纵列占用多少格子，事实上，我们只需要知道 $y(x-0.5)$ 的值并上取整即可。

注意此题卡精度（照我的写法是要开 long double 的）。

long double a, b;
int main() {
    for(int i = 1; i <= a; i++)
        ans += (1 - (i - 0.5) / a) * b + 0.5;
}

Problem M. Chained Lights

void press(int x)
{
    light[x]^=1;
    for (int y=x+x;y<=n;y+=x) press(y);
}
for (int i=1;i<=n;i++) press(i);

优化上述代码。$1\leq T \leq 10^5, 1\leq k \leq n \leq 10^6$

纯纯的诈骗题。

首先 $T, n$ 都是没用的，其次 “After all the operations, lights 1, 2, 3 will be turned on and light 4 is still off.” 太有误导性了，我原以为这是所有操作都执行完的结果，实际上只是 $i=1$ 执行完了……然后玩几个样例就能看出来除了 $1$ 其余都是 No……

很明显能看出来这是和因数有关的，不妨分类讨论：素数(p)： 只会在 press(1) 和 press(p) 的时候操作两次，所以灯的状态不变；合数： 除开 $1$ 和它本身，剩余的因子都会使它被操作两次，灯的状态也不变。

puts(k == 1 ? "YES" : "NO");

Problem F. XOR Game

博弈论。

题面挺抽象的，读了好几遍才读懂（也有可能是英语差。

首先：对于一个数 Alice 先手，如果有奇数个，Alice 总可得到（以下简称达到目的为赢），有偶数个，则 Bob 赢，这还是比较显然的。