题目传送门：第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海） D Strange_Fractions（解方程，数论） 解方程，设\(t = \frac{b}{a}\)，将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\)，通过小学二年级学的一元二次方程求根公式可知：当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的 […]

题目链接：The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn) 在PTA可以补题。 题意 / Problem 给定一个长度为N的01串，有Q次询问。 对于一个01串，每次可以代价为0的删除任意一个1以及和它相邻的两个数字，或者代价为1的将某个0翻转为1。 注意这个01串是环形的，也就是头尾相连，比如100也可以代价为0的进行一次删除 […]

题目链接：B-Bitwise Exclusive-OR Sequence_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com) 题意 / Problem 给定N个点，M条边，点权未知但是每条边上的边权就是其所连接的两个点的点权的异或和。问怎样规划点权可以使得所有点的点权加和最小，输出最小和。 注意：图不一定连通。（这个特别坑！！！） 思路 / Though […]

题目传送门：I-Mr. Main and Windmills_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） (nowcoder.com) 今天和学长进行了一场icpc昆明重现赛，被打爆了。这道题都没做出来，思路其实差不多了，但是考场上没想到可以用一个eps来解决斜率为无穷的情况，shit！ 题目大意 从点S，沿直线走到T点，问当点(x, y)恰好变化k次时，人所处的位置。 思路 […]

题目传送门：F-Sandpile on Clique_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com) 我去，模拟，卡了好久。 题目大意 有一个完全图，如果某个点的球数量大于入度（就是N - 1），那么这个点的值就给每一个出点一个球，自身就减少N - 1个球，问能否达到“每个点的球数量都小于N - 1”或者会出现无限循环。 思路 每次分散，给N - 1个点 + 1，其 […]

题目链接：C-Laser Trap_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com) 题目大意 T个测试用例，二维平面上N个点，形成的完全图。 问至少删除多少个点可以使得一个球在不碰到任何线的情况下从(0, 0)移动到(inf, inf)。 数据保证不存在任何一条线通过(0, 0)。 思路 哎，当时在赛场上想到了用斜率，用atan，也用了long double，但是没 […]

题目链接：A-So I'll Max Out My Constructive Algor..._第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com) 如果看不到题目请先报名比赛，就可以看到了。 题目大意 给定一个规模为N * N的矩阵，每个数字表示某个位置的高度h[i][j]，现在要使得每个位置都走且仅走一次(exactly once)，且上升的次数比下降的次数少。 并且 […]

题目传送门：K-Link-Cut Tree_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com) 题目大意 有T个测试样例。 给定n个点，m条边，第i条边的权值为2的i次方，求图中权值之和最小的环的边的编号（从小到大）。 思路 看到2的i次方，不难想到用贪心，从小到大（也就是按照输入顺序）遍历所有边，一旦出现环，就直接输出这个环的边的编号就行了，一定是权值和最小的。 这里 […]

只做出3道题，分别是AFK（三道签到题）。 大家可以看一下题单，这次比赛是在牛客网上进行的。 第46屆ICPC 東亞洲區域賽（澳門）(正式賽） 上午8点去比赛场地，跟我一起去的朋友说十分紧张，可因为我是打星队伍，所以没这么紧张。 C题思路对了，是利用叉乘对向量进行排序，然后枚举点二分，可是不知道哪里没搞好，总是WA。 其他的就无能为力了，寄咯~ 下面是我的一些题解（都是签到题呜呜呜）: ICPC澳 […]