本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-27 08:23:59
A: The Same Calendar
题面翻译
给你一个年份$ N$，给出一个大于$ N$的年份$Y$，有如下两个要求
1.天数与份$ N$相同
2.该年的第一天的星期与份$ N$年相同
闰年有$366$天。整除$4$且不整除$100$的是闰年，整除$400$的也是闰年
样例 #1
样例输入 #1
2016
样例输出 #1
2044
样例 #2
样例输入 #2
2000
样例输出 #2
2028
样例 #3
样例输入 #3
50501
样例输出 #3
50507
数据范围
$100\%$的数据范围:$Y\leq 100,000$
提示
Today is Monday, the $ 13 $ th of June, $ 2016 $ .
B:Make Bipartite
题面翻译
给定一个 $N$ 个点，$M$ 条边的无向图，求问有多少对还未经连接的点对满足在连接它们后，该图为一个二分图.
注意这里点对 $(u,v)$ 和点对 $(v,u)$ 是同一对点对。
数据保证没有自环与重边。
输入格式
第一行两个数$N,M$,接下来$M$行，每行两个数 $(u,v)$，表示一条无向边。
输出格式
一个整数，表示选择方案总数。
样例 #1
样例输入 #1
5 4
4 2
3 1
5 2
3 2
样例输出 #1
2
样例 #2
样例输入 #2
4 3
3 1
3 2
1 2
样例输出 #2
0
样例 #3
样例输入 #3
9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8
样例输出 #3
9
数据范围
$100\%$的数据范围：$ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $，$ 0\ \leq\ M\ \leq\ \min\ \lbrace\ 2\ \times\ 10^5,\ N(N-1)/2\ \rbrace $， $ 1\ \leq\ u_i,\ v_i\ \leq\ N $，图为简单图。
C:Joty and Chocolate
题面翻译
Joty 有 $n$ 块瓷砖，编号为 $1,2,3,\cdots ,n$ ，Joty 可以把编号为 $a$ 的倍数的瓷砖刷成红色，同时她会得到 $p$ 块巧克力；她也可以把编号为 $b$ 的倍数的瓷砖刷成蓝色，同时她会得到 $q$ 块巧克力；如果这个瓷砖是 $a,b$ 的公倍 数，则她可以任选一个颜色并得到对应的巧克力报酬，也只能选择一种，并得到 对应的$p$或$q$ 块巧克力。
输入一行5个数据，$n,a,b,p,q$ 。
输出一个数据：表示 Joty 能得到的巧克力最多有多少？
输入格式
The only line contains five integers $ n $ , $ a $ , $ b $ , $ p $ and $ q $ ( ).
输出格式
Print the only integer $ s $ — the maximum number of chocolates Joty can get.
Note that the answer can be too large, so you should use $ 64 $ -bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
样例 #1
样例输入 #1
5 2 3 12 15
样例输出 #1
39
样例 #2
样例输入 #2
20 2 3 3 5
样例输出 #2
51
数据范围
$100\%$的数据范围:$Y\leq 100,000$ 1<=n,a,b,p,q<=10^{9} $
D:Iterated Linear Function
题面翻译
定义函数$g$:
①$g^0(x)=x$
②$g^n(x)=Ag^{n-1}(x)+B(n≠0)$
请求出$g^{n}(x)$的值。由于答案可能过大，请将其对$10^9+7$取模。
输入格式
一行，给定的两个整数s $ A $ , $ B $.
输出格式
一个整数$ s $ ，表示 $ g^{(n)}(x) $ modulo $ 10^{9}+7 $的结果 .
样例 #1
样例输入 #1
3 4 1 1
样例输出 #1
7
样例 #2
样例输入 #2
3 4 2 1
样例输出 #2
25
样例 #3
样例输入 #3
3 4 3 1
样例输出 #3
79
数据范围
$ n $ and $ x $ ( $ 1<=A,B,x<=10^{9},1<=n<=10^{18} $ )
E: Another Sith Tournament
题面翻译
你是一位骑士，与其他n-1个骑士同时爱上了LKJ，所以你们不得不通过决斗的方式来选出谁能最终得到LKJ。
幸运的是你知道任意骑士i击败骑士j的概率，你还被推选为组织委员。决斗一开始你需要任意选择两名骑士（包括自己）进行决斗，胜利方继续和你另外选择的一名骑士决斗，直到仅剩一人，最终的胜利者将得到LKJ。
你非常渴望取得胜利，想知道自己得到LKJ的最大概率是多少，注意你是1号。
第一行一个正整数$n$，表示一共有$n$名骑士。
接下来是一个$n * n$的实数矩阵，$A_{ij}$ 表示$i$战胜$j$的概率。
保证$ A_{ii} $为 0，且 $A_{ij}+A_{ji}=1$
输出一个数，表示你得到LKJ的概率，误差在$10^{-6}$以内。
题目描述
The rules of Sith Tournament are well known to everyone. $ n $ Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.
Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.
输入格式
The first line contains a single integer $ n $ ( $ 1<=n<=18 $ ) — the number of participants of the Sith Tournament.
Each of the next $ n $ lines contains $ n $ real numbers, which form a matrix $ p_{ij} $ ( $ 0<=p_{ij}<=1 $ ). Each its element $ p_{ij} $ is the probability that the $ i $ -th participant defeats the $ j $ -th in a duel.
The elements on the main diagonal $ p_{ii} $ are equal to zero. For all different $ i $ , $ j $ the equality $ p_{ij}+p_{ji}=1 $ holds. All probabilities are given with no more than six decimal places.
Jedi Ivan is the number $ 1 $ in the list of the participants.
输出格式
Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed $ 10^{-6} $ .
样例 #1
样例输入 #1
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0
样例输出 #1
0.680000000000000
鲁ICP备2025150228号