洛谷 P2181 对角线
题目描述
对于一个 nnn 个定点的凸多边形,他的任何三条对角线都不会交于一点。请求图形中对角线交点的个数。
例如,六边形:
输入格式
第一行一个 nnn,代表边数。
输出格式
第一行输出交点数量
输入输出样例
输入1
3
输出1
0
输入2
6
输出2
15
说明/提示
$50\%$ 的测试数据 $3\leqslant n\leqslant100$;
$100\%$ 的测试数据 $3\leqslant n\leqslant 100000$。
分析
由于任何三条对角线不会交于一点,故对于每一个交点,只有两条对角线经过,所以一个交点与四个顶点相关联,即四个顶点确定一个交点,答案为Cn4=n(n−1)(n−2)(n−3)24C_n^4=\frac {n(n-1)(n-2)(n-3)}{24}Cn4=24n(n−1)(n−2)(n−3)。直接这样算用```unsigned long long``也会爆,所以可以将式子改写为$\frac{{\frac{{\frac{{n(n - 1)}}{2} \times (n - 2)}}{3} \times (n - 3)} ...
Codeforces Round #625 (Div. 2)
A. Contest for Robots
Polycarp is preparing the first programming contest for robots. There are nnn problems in it, and a lot of robots are going to participate in it. Each robot solving the problem$ i$ gets$ p_i$ points, and the score of each robot in the competition is calculated as the sum of pip_ipi over all problems$ i$ solved by it. For each problem, pip_ipi is an integer not less than$ 1$.
Two corporations specializing in problem-solving robot manufacturing, “Robo-Coder Inc.” and “B ...
洛谷P1328 生活大爆炸版石头剪刀布
题目描述
石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样,则不分胜 负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。
升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:
斯波克:《星际迷航》主角之一。
蜥蜴人:《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。
现在,小 A和小 B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 666 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-…”,而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为 555 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-…”
已知小 A和小 B 一共进行 $N $次猜拳。每一次赢的人得 111分,输的得 000 分;平局两人都得 000 分。现请你统计 NNN 次猜拳结束之后两人的得分。
...
“华为杯”中国矿业大学程序设计学科竞赛重现赛
A-细胞分裂
题目描述
CB不光是ACM大佬,同时也是生物领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。
CB博士手里现在有N种细胞,编号从1~N,一个第i种细胞经过1秒钟可以分裂为Si个同种细胞(Si为正整数)。现在他需要选取某种细胞的一个放进培养皿,让其自由分裂,进行培养。一段时间以后,再把培养皿中的所有细胞平均分入MMM个试管,形成MMM份样本,用于实验。CB博士的试管数MMM很大,普通的计算机的基本数据类型无法存储这样大的MMM值,但万幸的是,MMM总可以表示为m1m_1m1的m2m_2m2次方,即M=m1m2M=m_1^{m_2}M=m1m2 ,其中m1,m2m_1,m_2m1,m2 均为基本数据类型可以存储的正整数。
注意,整个实验过程中不允许分割单个细胞,比如某个时刻若培养皿中有4个细胞,Hanks博士可以把它们分入2个试管,每试管内2个,然后开始实验。但如果培养皿中有5个细胞,博士就无法将它们均分入2个试管。此时,博士就只能等待一段时间,让细胞们继续分裂,使得其个数可以均分,或是干脆改换另一种细胞培养。
为了能让实验尽早开始,CB博士在 ...
扩展欧几里得算法
算法描述
扩展欧几里得算法可直接计算不定方程方程 ax+by=gcd(a,b),(a,b∈Z)ax+by=gcd(a,b),(a,b\in Z)ax+by=gcd(a,b),(a,b∈Z) 的一组整数解,并返回 gcd(a,b)\gcd(a,b)gcd(a,b)。
理论基础
裴蜀定理(Bézout’s lemma)
定理描述
对任何整数 aaa、b{\displaystyle b}b 和 c{\displaystyle c}c,关于未知数 x{\displaystyle x}x 和 y{\displaystyle y}y 的线性丢番图方程:ax+by=c{\displaystyle ax+by=c}ax+by=c 当且仅当 gcd(a,b)∣c\gcd(a,b)|cgcd(a,b)∣c 时有整数解。
证明
先证:
对于任意整数 a,ba,ba,b ,存在一对整数 x,yx,yx,y ,满足 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)。
在欧几里得算法(Euclidean algorithm)的最后一步,即 b=0 时,显然有一对整数 x= ...
高精度算法
高精度算法模板
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200 ...
洛谷P1056 排座椅
题目描述
上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 DD 对同学上课时会交头接耳。
同学们在教室中坐成了 MMM 行NNN 列,坐在第 iii 行第$ j$ 列的同学的位置是$ (i,j),为了方便同学们进出,在教室中设置了,为了方便同学们进出,在教室中设置了,为了方便同学们进出,在教室中设置了 K$ 条横向的通道,LLL 条纵向的通道。
于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了 222个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。
输入格式
第一行,有 555 个用空格隔开的整数,分别是 M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)M,N,K,L,D(2 \le N,M \le 1000,0 \le K<M, ...
肇庆学院"菜鸟杯"程序设计竞赛2019(同步赛)
C-最大模数
题目描述
一次周六新生训练后,一个师妹来找JAJA_Xin。
师妹:“师兄,为什么今天我对面那个师兄那么冷漠。”
JAJA_Xin:“噢你居然还不认识大名鼎鼎的魏队,正常啦,魏队很傲的,因为你们太菜,所以你懂的。”
师妹:“那怎么才能让那个师兄觉得我不菜,你可以帮我去问问吗?”
乐于助人的JAJA_Xin怎么可能拒绝师妹呢,跑去问魏队。
魏队:“简单啊,我出一道题,能做出来就不算很菜了,就出一道数学题吧,简单一点,让他们可以做。”
Ra=[(a−1)n+(a+1)n]R_a = [ (a−1)^n + (a+1)^n ]Ra=[(a−1)n+(a+1)n](((modmodmod $ a^2$$)$$ ,(n>0)例如当
例如当例如当a=4, n=2时,时,时,Ra=32 +52 =34$,而34mod16=234mod16 =234mod16=2,故Ra=2R_a=2Ra=2。由于n可以是任意大于0的正整数,所以存在很多RaRaRa的解,找到任意一个Ra就算做出来这道题。例如,当a=4a=4a=4的时候,RaRaRa的取值可以是222或者是888。
“你怎 ...
Codeforces Round #624 (Div.3)
A. Add Odd or Subtract Even
You are given two positive integers a and b.
In one move, you can change a in the following way:
Choose any positive odd integer x (x>0) and replace a with a+x;
choose any positive even integer y (y>0) and replace a with a−y.
You can perform as many such operations as you want. You can choose the same numbers x and y in different moves.
Your task is to find the minimum number of moves required to obtain b from a. It is guaranteed that you can always obtain b ...
牛客小白月赛22
A-操作序列
题目描述
给出一个长度无限的数列,初始全部为零,有三种操作:
增加操作:给下标为 ttt 的数加 ccc 。特别注意,如果在下标 [t−30,t+30][t-30,t+30][t−30,t+30] 内有不为零的数,增加操作无效。
削减操作:让数列中下标最小的不为零数变为零。
查询操作:查询数列中下标为 ttt 的数字是多少。
输入描述
第一行包含一个整数 N,1≤N≤106N,1 \le N \le 10^6N,1≤N≤106,表示操作总数。
随后 N 行,每行由两个数字或一个数字组成。
若一行中有两个数字,分别代表增加操作的$ t,c$ 。
若一行中只有数字−1-1−1,执行削减操作。
若一行中只有一个不为 −1-1−1的数字,则代表查询操作的数字 ttt。
保证t,ct,ct,c均为非负整数且在整形范围内。
输出描述
削减操作时,先输出该数字,再变为零。
若序列元素全为零,则削减操作无效,此时输出 “skipped”。
查询时,输出该位置上的数。
示例1
输入
7
140 1
120 2
100 3
120
100
−1-1−1
100
输出
0
3
3
0
...