shicj's blog

这是本场比赛的签到题。 0x00 题目大意 共 nnn 个人，xxx 个人选择价格 bbb 的汉堡，剩余人选择价格 aaa 的，求总价。 0x00 解题思路 由小学数学得到： ans=a×(n−x)+b×xans=a\times (n-x)+b\times x ans=a×(n−x)+b×x 别的没什么好说的 0x02 AC Code 123456789101112131415#include<bits/stdc++.h>using namespace std;void solve(){ int n,x,a,b; cin>>n>>x>>a>>b; cout<<a*(n-x)+b*x<<endl;}int main(){ int t; cin>>t; while(t--){ solve(); } return 0;}

0x00 题目大意 给出平面上一些点，求以这些点的子集为顶点组成的凸多边形的面积的最小值。 0x01 解题思路 易证，最终的图形一定是一个三角形（如果是更多边形，必然可以削掉一块使得面积更小）。 看到数据范围：1≤n≤1001\le n\le 1001≤n≤100，完全可以 O(n3)O(n^3)O(n3) 枚举三角形，求最小面积。 如何求三角形面积？可以用这个公式： SΔABC=∣A.x×B.y+B.x×C.y+C.x×A.y−A.x×C.y−B.x×A.y−C.x×B.y∣2S_{\Delta ABC}=\dfrac{|A.x\times B.y+B.x\times C.y+C.x\times A.y-A.x\times C.y-B.x\times A.y-C.x\times B.y|}{2} SΔABC​=2∣A.x×B.y+B.x×C.y+C.x×A.y−A.x×C.y−B.x×A.y−C.x×B.y∣​ tips：不要用海伦公式，精度会炸。 如果三角形面积为 000，则说明当前三个点构不成三角形，如果所有组合面积都为 000，则无解。 0x02 AC...

0x00 题目大意 对于两个给定的正整数 xxx 和 yyy，找到另两个整数 aaa 和 bbb 满足： lcm⁡(x,y)gcd⁡(x,y)=ab\sqrt{\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}}=a\sqrt{b} gcd(x,y)lcm(x,y)​​=ab​ 求当 a×ba\times ba×b 最小时 aaa 和 bbb 的值。 0x01 解题思路 求出 lcm⁡(x,y)gcd⁡(x,y)=k\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}=kgcd(x,y)lcm(x,y)​=k，代入原式： k=ab\sqrt{k}=a\sqrt{b} k​=ab​ 左右平方： k=a2bk=a^2b k=a2b 此时要使得 ababab 最小，则要使得 aaa 最小（a2b=a(ab)a^2b=a(ab)a2b=a(ab)），故直接令 a=1a=1a=1 即可得最优答案。 0x02 AC...

详细的解析 解决vector问题 最小割=最大流 技巧：连+inf的边 Dinic code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960int n,m,s,t;struct edge{ int v,w,r;};vector<edge>G[10001];bool vis[10001];int d[10001],p[10001];bool bfs(){ memset(d,-1,sizeof(d)); memset(vis,0,sizeof(vis)); queue<int>q; q.push(s); vis[s]=true; d[s]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(auto...

0x00 题目大意 给出一棵树，在一个点上放一个棋子，两人轮流移动棋子到相邻位置，不可重复经过某个点，两人决策最优，问谁获胜。 0x01 初步分析 看一下样例，画个图分析一下： 然后看一下可以怎样移动： 发现每一条路径都去往叶子节点，显而易见，每个叶子节点的状态是确定的： 这个状态可以很快求出，接下来研究如何向上转移。 0x02 深入分析 由于叶子节点状态已知，所以考虑自底向上分析。 在这里，每一个节点上由谁选择（移到下一个点）很重要，我们用绿色字体标出每个节点上由谁选择： 可以看出，由谁选择取决于节点的深度。 易得，在最优决策中，总是要选择可以使得自己获胜的点，如果没有，则在这一点上出发对方获胜，否则自己获胜。 于是可以自底向上标出每一个点上的获胜者： 这时看一看起始节点上谁获胜就行了。 0x03 具体实现 在代码中，可以如图中用字符表示状态（这样直观但代码量大），但更推荐用布尔值来实现，这样可以把判断获胜者的运算转化为深度模 222 和逻辑运算，具体的写法可以自己琢磨。 求获胜者的步骤可以直接写在搜索的回溯部分，这样便于实现。 0x04...

Part1. 题目概述 你有一个数组，其顺序可以随意打乱。 你可以在其中任选一个数增加 kkk，这记为一次操作。 求最小的操作次数以使原数组为回文串。 若不可能，输出 −1-1−1。 Part2. 思路 首先看到只能增加 kkk，说明无论怎么操作，每个数除以 kkk 的余数不变。 要求得到回文串且顺序可以随意打乱，也就是说只要满足最终的数组只有不大于一个数出现的次数为奇数（这个数拿一个放中间，其他的左右两边对称放）。 再回到1，除以 kkk 的余数不变，那么可以对除以 kkk 的每一个余数分组，每一组都可以通过加 kkk 使得数字相等，比如这组样例的分组： 1213 32 3 9 14 17 10 22 20 18 30 1 4 28 余数为 000 余数为 111 余数为...

题意 有一个 nnn 个节点的环（nnn 是奇数），每个点 iii 有点权 aia_iai​，现在已知了边权 wi=12(ai+ai+1)w_i=\dfrac{1}{2}(a_i+a_{i+1})wi​=21​(ai​+ai+1​)，其中 wn=12(a1+an)w_n=\dfrac{1}{2}(a_1+a_n)wn​=21​(a1​+an​)，这个权值和可以任意对应，改变边权时 aia_iai​ 会自动调整，现在要求出两种边权的对应方法，分别使得 a1a_1a1​ 取得最大值和最小值。 思路 我们尝试把 a1a_1a1​ 表示一下（因为要求它的最值）。 易得方程组： \begin{equation*} \begin{cases} a_1+a_2=2w_1\\ a_2+a_3=2w_2\\ \cdots\\ a_{n-1}+a_n=2w_{n-1}\\ a_n+a_1=2w_n \end{cases} \end{equation*} 题目中的 nnn...

易错点\color{red}易错点易错点 肥皂水是乳浊液 二氧化碳不算污染物 水资源 类型 占比 海洋水 96.5% 陆地水 3.5% 咸水 1% 淡水 2.5% 大气水 微不足道 可利用 0.3% 水循环 海上内循环，海陆间循环，陆地内循环 水资源分布 不均匀 南多北少，东多西少，夏多冬少 二氧化碳 二氧化碳 + 氢氧化钙 ⟶ 碳酸钙 + 水二氧化碳\ +\ 氢氧化钙\ \longrightarrow\ 碳酸钙\ +\ 水二氧化碳 + 氢氧化钙 ⟶ 碳酸钙 + 水 CO2 + Ca(OH2)= CaCO3↓ + H2OCO_2\ +\ Ca(OH_2) \overset{}{=}\ CaCO_3 \downarrow \ +\ H_2OCO2​ + Ca(OH2​)= CaCO3​↓ + H2​O 二氧化碳 + 水 ⟶ 碳酸二氧化碳\ +\ 水\ \longrightarrow\ 碳酸二氧化碳 + 水 ⟶ 碳酸 CO2 + H2O = H2CO3CO_2\ +\ H_2O\...

地区 地形（区） 气候 湄公河平原 平原 热带季风气候 美国中部大平原 平原 温带大陆性气候 秘鲁 安第斯山区 高原山地气候 瑞士 阿尔卑斯山区 高原山地气候 日本 北部：温带季风气候 \\ 南部：亚热带季风气候 威尼斯 地中海气候 非洲热带草原 东非高原 热带草原气候 澳大利亚 西部高原，中部平原，东部山地 中西部：热带草原&热带季风气候 \\ 西南角：地中海气候 \\ 东南角：温带海洋性气候 波斯湾地区 主要高原，也有平原，沙漠广布 热带沙漠气候 以色列 以高原山地为主，沿海平原，沙漠广布 北部：地中海气候 \\ 南部：热带沙漠气候 莫斯科 东欧平原 温带大陆性气候 巴黎 巴黎盆地 温带海洋性气候 班加罗尔 德干高原 热带季风气候 蔚山 亚热带季风气候 巴西利亚 巴西高原 热带草原气候 南非 山地、高原（中部）为主，平原（东北部）面积较小 最主要：热带草原气候 \\ 西南沿海：地中海气候 \\ 西北地区：热带沙漠气候

1. 题目大意 在 N×NN \times NN×N 的棋盘里面放 KKK 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 888 个格子。 注意是8个方向。 对于全部数据，1≤N≤91 \le N \le 91≤N≤9，0≤K≤N×N0 \le K \le N\times N0≤K≤N×N。 从这个数据范围看出是状压动规，暴搜明显超时。 2. 思路分析 现在知道是状压动规，考虑如何建立状态、转移方程、边界。 状态 首先，1≤N≤91 \le N \le 91≤N≤9，可以想到用一个长 999 位的二进制串来表示状态。 思考一下转移必须的条件，可以把每一行作为一个阶段（于是有了第一维），还需要知道这一行的选取情况（第二维），此外，还要知道已经用掉的国王数量（第三维）。 于是有了具体的状态定义：令 dp[i][j][k] 表示第 iii 行，使用 jjj 的方法安放，已经用了 kkk...