[CF1030D] Vasya and Triangle

Vasya and Triangle

翻译:

Vasya有三个数n,m,k。他想要找到三个整点(x1,y1),(x2,y2),(x3,y3)满足0≤x1,x2,x3≤n,0≤y1,y2,y3≤m并且由这三点组成的三角形面积等于nm/k。

帮助Vasya找到这样的点(如果可能的话)。如果有多组解,输出任意一组即可。

Input

仅一行,包括三个整数n,m,k(1≤n,m≤10^9,2≤k≤10^9)。

Output

如果没有这样的点,输出"NO"。

否则在第一行输出"YES"。接下来三行每行包括两个整数xi,yi,代表点的坐标。如果有多组解,输出任意一组即可。

你可以任意输出大写或小写的英文字母。

Note

在第一组样例中三角形的面积等于nm/k=4。这个三角形的图示在下方。

在第二组样例中不存在三角形的面积满足nm/k=16/7。

Tutorial

将任意坐标都是整点的三角形面积加倍总会得到一个整数。这就是如果2nm不能被k整除,就没有合法的三角形的原因。

反之,总是存在满足条件的三角形。我们将会在接下来的算法里构造答案。首先,如果k是偶数那么就将它除2。接着,令g = gcd(k, n),在这里gcd(x, y)代表x和y的最大公约数。取k' = k / g,令 a = n / g 并使其作为三角形的一边长。然后令b = m / k'作为三角形的另一边长。现在,如果k是奇数我们应将其中一边长乘以2。如果a < n那么令a = 2a,否则就令b = 2b。b不会大于m,因为假如a=n那么b是严格小于m的。

答案就是由顶点(0, 0), (a, 0), (0, b)构成的三角形。你可以检查它的面积是否等于nm/k。

继续阅读[CF1030D] Vasya and Triangle

【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:
继续阅读【纪中】Day10+

【纪中】Day1

【队伍统计】
题意:在n个人中,有m条矛盾关系(u, v),表示编号为u的人想要排在编号为v的人前面。询问矛盾关系不超过k条的排列。
这题早上没有做,也没听讲,但看了眼题目感觉是深搜或者状压dp。
这里采用状压dp。用S表示当前已经排好队的状态,则f[s][k]表示当前状态违背的矛盾关系。对于一个要新加入的i,需要满足i不在排列中。设i与当前排列产生的矛盾关系为q,
那么f[s][k]则可以转移到f[s|(1 << (i - 1)) ][k + q]。暴力转移时间复杂度是O(2^n * n ^ 2 * k)。
由于矛盾关系没有重复,则可以把与i有矛盾关系的用二进制来表示。矛盾关系数便可以表示为&操作后的1个数。
T1【序列问题】
题意:给出一个序列,求每个区间的最大最小值的乘积和。
以前做过一道看上去相似的题目,先暴力预处理,再线段树修改。今天也是怎么想,但显然不对。。。
正解对序列进行分治,考虑过mid的区间[l,r]对答案的贡献。枚举右端点r,那么当右端点的指针往右移时,max增加,min减少,左端点l满足max 𝑙 = min(𝑟),则可以左移。于是,相同的max、min的贡献就可以O(1)求出。序列分治可以用递归处理。
T2【带权排序】
题意:序列A的每一个数在一个区间中随机生成,每个位置有权值si,求排序后A的期望。
期望。。。不会化!不会求!没听懂!
T3【概率博弈 】
题意:给出一颗以1为根的树,树上权值随机生成,求从根节点到叶节点的期望。
设当前要求ans > x。因为只会是向大于x或小于x的方向走,设权值 >x的为1,否则为0.相当于有m - x + 1个1,x- 1个0,则问题转化为求f[1]的概率。可用树形背包来解决。

第一天给我的感觉是题目好难,唯一看的出解的还不需要做。下午的讲题有点难懂,第一题分治方法好理解,但最关键的前缀和处理则一句跳过。第二题期望本来就不会,还要化简。第三题转化听懂了,但树形背包是什么???

Day12

【质数生成器】
题意:询问区间[m,n]里的质数,1<=m<=n<=10^9,n-m<=1000000。
显然线筛过不了1e9的数据,只能对[m,n]区间求质数。
一个数n如果是合数,那么必定会被sqrt(n)中的质数整除,考虑普通筛(233)。对于[m,n]中的数,只需枚举每个质数,将其在这个区间中的倍数筛去即可。
正确性:线筛只要将sqrt(n)中的质数筛出,大概是1e5左右,明显不会超时。[m,n]区间的普通筛是用质数去筛,比用每个数筛的时间大大减少。
【魔法树】
题意:一棵树,每个点有一种属性。一条路径上的魔法值是这样计算的:在起点的时候,魔法值为 1,每经过一条边,假设这条边拥有的魔法属性是 ci,如果这是奇数次经过带有 ci 魔法属性的边,则将魔法值乘上 ci 对应的魔法系数,否则将魔法值除以 ci 对应的魔法系数。
简化题目,即如果奇数次经过ci的点,那么答案就乘上di,否则这个ci对答案没用贡献。
考虑用二进制来表示每种属性的贡献,对于询问的两个点,只需以任意的点为树根,求出每个点的二进制数,在询问使^即可。
【hill】
题意:给出一座山,求一个最低的点能够看到所有地方。
简单的三分题。

Day11

【虚】
题意:从数轴的原点开始,有1/4的概率往左或往右走,有1/2的概率被-1s(站在原地不动)。询问t时到p点的概率。
把一个点拆成两个点,则题目可化成有1/2的概率往左或往右走,询问2t时到2p点的概率。可用排列组合求解。
【传送】
题意:一张n*m的图,从(1,1)开始,可以往左或往下走,在一些点有传送门,可以传送到另一个点,询问最大收益。
tarjin缩点+spfa即可。(为什么说的那么简单?因为我还没写出来)。
【串】
题意:n次操作,有p的概率出现1,否则为0。每个长度为x的1可以获得x^3的分数,求答案的期望。
假设在i之前已经出现了x个1,那么如果新加入的是1,对答案的贡献是(x + 1)^3 - x^3, 化简得3x^2 + 3x + 1。
所以,现在只需要维护x^2、x的期望即可。
x的期望:x1[i] = (x1[i - 1] + 1) * x
x^2的期望:x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * x
答案期望:sum += (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * x

Day8

【日历游戏】
题意:对一个日期有两种操作:1.跳到日历上的下一天。2.跳到日历上的下个月的同一天(如果不存在,则不能这么做)。询问先手是否必胜。
博弈论+记忆化搜索,对于先手必胜的日期,它的下一天或下个月同一天先手必败。对于先手必败的日期,其后一天或下个月先手必胜。
【二叉查找树】
题意:求将n个数加入二叉树,并使其高度恰好为h的方案数。
考虑树形dp。设f[x][h]表示有x个节点的子树,并以x为父节点,高度为h的方案数,设g[x][h]表示有x个节点的子树,并以x为父节点,高度小于等于h的方案数。
那么f[x][h] = (f[x - 1][h - 1]*f[n - x][h - 1] - g[x - 1][h - 2] * g[n - x][h - 2]) * C(x - 1, n - 1);
由于f[x - 1]的相乘会计算重复的,所以要减去重复计算的,最后的排列组合是计算将剩下的数放入x的子树中的方案数。
【我们爱数数】
题意:规定第i人坐在i - 1、i、i + 1的位置上是开心的,询问使>=k的人开心的方案数。
DFS + DP + 容斥。令f[i][j][s]表示1-i位子有j个人已经坐下且这j个人一定开心,s表示i和i+1是否坐下。首先暴力枚举初始状态,即1、2位置是否坐人,坐的人是谁。
那么f[i][j][s >> 1 ] += f[i - 1][j][s];
f[i][j][(s | (1 << d)) >> 1] += f[i - 1][j - 1][s](d=0,1,2,分别表示第i-1,i,i+1个人坐第i个位置)。
最后判断一下初态和终态是否矛盾。
设ans[n][j]表示j个人一定开心的方案(存在重复)。ans[n][j] = f[n][j][s] * (n - j)!。
因为ans中剩下的n - j不一定是不开心的,所以在统计中会出现重复的状态。
最后用容斥来求方案数。

Day5

【匹配】
简单的模拟题,这里略过。

【矩形】
题意:给出n条直线,求组成的矩形个数。
60%的做法,先枚举两条平行的直线,再枚举垂直于前两条直线且有交点的线,用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时,考虑优化上面的算法,用bitset记录每两条直线是否相交,那么,求垂直于两条直线且相交就变成了求两条直线bitset的和(&)。由于直线分为两种,垂直于x轴与平行于x轴,可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组(线段树)来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。

【历史】
题意:每次连一条边,询问两个点是否在t之前不联通,在当前时刻联通,强制在线。
由于强制在线的是连接的边,对于询问并没有要求强制在线,那么,先将询问存下来,对于t之前的状态可在t时记录,t的状态可直接得到。
正解是可持久化并查集, 用可持久化线段树维护可持久化数组,由于修改的只能是一个数,所以合并并查集时不能用路径压缩,需要用启发式合并,那么,对于每个询问只需查找当前数组和前t的数组即可。

代码如下(可持久化并查集代码明天补充)

继续阅读Day5

3634【HNSDFZ集训】B 君的教育

题意:

  求出一个满足Σpk=x+yi(kS)的非负整数序列。

题解:

  由于p=-1+i(这里i是虚数),所以其满足p^n=2[p^(n1)+p^(n2)](这个我也不知道为什么,请自行探索)

然后在发现在不考虑一个p^k最多只能用1次的情况下,可以用p^0p^1x+yi表示出来。然后根据上面推出来的这个式子,k从0开始,若p^k用了奇数次,就把它调整成1次,偶数次就调整成0次,如此向后,最终一定能得到解集。

关于c++中的complex

关于虚数i

代码如下: 继续阅读3634【HNSDFZ集训】B 君的教育