网站开发如何共用菜单栏,宜宾市珙县住房城乡建设网站,如何进行网站维护,怎样制作网站教程voteplus 【问题描述】 R 君博客上有⼀个投票板块#xff0c;⼤家可以使⽤投票的⽅式来表达⾃⼰对某些问题的赞成或反对的意见。 投票结果是公开的#xff0c;但是 R 君会把这个结果化成⼀个最简分数#xff0c;如 1:2,4:3。 注意到同⼀个最简分数可能代表了不同的总⼈数⼤家可以使⽤投票的⽅式来表达⾃⼰对某些问题的赞成或反对的意见。 投票结果是公开的但是 R 君会把这个结果化成⼀个最简分数如 1:2,4:3。 注意到同⼀个最简分数可能代表了不同的总⼈数如 300 ⼈赞同 600⼈反对与 1 ⼈赞同 2 ⼈反对显⽰的都是 1:2。 Neetenin 同学发现了这⼀点但是 Neetenin 同学想猜出有多少⼈参加了投票他使⽤的⽅法是先看结果⾃⼰投⼀票赞同后再看结果。 ⽐如⼀个当前的投票结果是 1:2但是 Neetenin 同学投了⼀票赞成后变成了 301:600 Neetenin 同学就知道⼀共有 3006001901 ⼈参加了此次投票。 现在 Neetenin 同学把之前和之后的结果都告诉你让你算算⼀共有多少⼈参加了投票 当然 Neetenin 可能也有看错了的时候所以当问题⽆解的时候请输出”fake”(不含双引号)。 【输入格式】 ⼀⾏四个整数 a,b,c,d表⽰前⼀次结果是 a:b后⼀次结果是 c:d。 【输出格式】 输出⼀个整数或⼀个字符串”fake”(不含双引号)表⽰参加投票的总⼈数包含 Neetenin 同学。 【样例输入 1】 1 4 1 3 【样例输出 1】 16 【样例输入 2】 1 3 1 4 【样例输出 2】 fake 【数据规模及约定】 对于前 50% 的数据 1 ≤ a; b; c; d ≤ 100000。 对于前 50% 的数据 1 ≤ 答案 ≤ 100000。 对于前 100% 的数据 1 ≤ a; b; c; d ≤ 10^9。 对于前 100% 的数据 1 ≤ 答案 ≤ 10^9。 【题解】 设之前是x人投赞成y人反对那么不难列出\(\displaystyle\frac x y\frac a b,\frac{x1}y\frac c d\)。 把这个方程组乱搞搞就能得到\(\displaystyle x\frac{ad}{bc-ad},y\frac{bd}{bc-ad}\)。 判断\(bc-ad0\)并且ad和bd都能整除即可输出否则当然是fake了 fire 【问题描述】 森林着⽕了⽕势还在不断蔓延。 R 君作为森林管理员看到⽕势失去控制、在森林中四处蔓延⼼⾥很慌。 经过 R 君平⽇仔细的研究这个森林的⽕势传播可以看成⼀个 n 个节点的带边权的⽆向图 (节点标号为 1-n)每个节点代表森林的⼀个区域⼀条边 (u,v,w) 代表着⽕势从区域 u 传播到区域 v 需要花费 w 的时间。并且整个森林是⼀个连通图⼀旦着⽕没有节点可以幸免。 通过⾃动化的 IoT 设备 R 君观察到了 0 时刻有 k 处起⽕点然后⼤⽕就按照⽕势传播图的规则蔓延开来。 不幸的是森林⾥有 q 个区域存在着居民所以 R 君⾮常想知道⽕势蔓延到这 q 个区域的时间从⽽展开营救⾏动。 然⽽ R 君觉得这个问题太难了于是找到了学 OI 的你。 【输入格式】 第⼀⾏四个整数 n, m, k, q表⽰图的点数、边数、起⽕点数量、存在居民的区域数量。 接下来 m ⾏每⾏三个正整数 u, v, w表⽰⼀条 u 到 v边权为 w 的⽆向边。 接下来⼀⾏ k 个正整数表⽰ 0 时刻 k 个起⽕点的节点编号。 接下来⼀⾏ q 个正整数表⽰询问的 q 个居民区的节点编号。 【输出格式】 输出 q ⾏每⾏⼀个整数表⽰⽕势蔓延到该点的时间。 【样例输入】 5 5 2 5
1 2 5
1 3 2
2 3 5
2 4 5
3 5 2
2 5
5 4 3 2 1 【样例输出】 0 5 2 0 4 【数据规模及约定】 对于前 10% 的数据 1 ≤ n ≤ 100。 对于另外 20% 的数据图为⼀棵树。 对于另外 20% 的数据 k1。 对于另外 20% 的数据 q1。 对于前 100% 的数据 1 ≤ n; m ≤ 10000, 1 ≤ k; q; u; v ≤ n, 1 ≤ w ≤10000。 【题解】 建立一个炒鸡src向所有着火的点连边权为0的边跑最短路。实际操作的时候可以直接把所有着火的点的dis设为0并放到堆中跑dij。 matrix 【问题描述】 ⼩ Y ⼗分喜欢计数⼀天他遇到了这样的⼀个问题 有⼀个 n ⾏ m 列的矩阵刚开始每个位置的数字都是 0。⼩ Y ⾸先进⾏ r 次这样的操作选择⼀⾏ (可与之前选择重复) 把这⼀⾏的每个数字1。之后⼩ Y 进⾏ c 次这样的操作选择⼀列 (可与之前选择重复) 把这⼀列的每个数字 1。 最后⼩ Y 数了⼀下矩阵⾥总共有 k 个位置的数字是奇数。 但是⼩ Y 忘了之前是怎么操作的了所以现在⼩ Y 想知道有多少种操作⽅案能够使得最后⼀共有 k 个位置的数字是奇数。 两种操作⽅案不同当且仅当存在某⾏或某列进⾏操作的次数不同。 因为答案很⼤所以只需输出这个答案除以 109 7 的余数。 【输入格式】 输⼊包含⼀⾏五个空格隔开的整数 n,m,r,c,k。 【输出格式】 输出包含⼀个整数表⽰答案。 【样例输入】 2 2 2 2 4 【样例输出】 4 【数据规模和约定】 对于 20% 的数据 1 ≤ n; m; r; c ≤ 4 对于 50% 的数据 1 ≤ n; m; r; c ≤ 2000 对于 100% 的数据 1 ≤ n; m; r; c ≤ 10^5; 0 ≤ k ≤ nm。 【题解】 很值得思考很有趣的一道题。 我们先假设矩阵操作后有x行操作了奇数次有y列操作了奇数次。 那么不难列出x(m-y)y(n-x)k即mxnyk2xy。我们可以枚举x而推出y从而得出所有合法的x和y。这里给出根据x求y的式子\(\displaystyle y\frac{k-mx}{n-2x}\)很容易推出来。 但是我们观察到分母是\(n-2x\)如果\(n-2x0\)那么怎么办 我们可以考虑当\(n-2x0\)时相当于操作完所有的行后恰好有一半的行是奇数另一半的行是偶数。那么如果再操作列奇数元素的数量是不改变的。。所以当2kmn时y可以取任意合法值否则y无解。 注意到还有\(m-2y0\)的情况也要考虑一下。我们可以直接枚举x求y枚举y求x把所有合法的(x,y)塞到一个set里不就得了。。。其实最完美的做法是只枚举x并判断那种情况。但是这里再告诉你一个事实其实那种情况只需要判断是否有2kmn即可如果有那么那种情况一定存在且其他情况不存在。这个结论可以通过GeoGebra探索出来。 我们处理出所有合法的(x,y)后就枚举刚才处理的所有(x,y)并计算贡献。显然的是行和列的贡献是独立的这里只考虑行的贡献。首先我们一共有n行最后有x行被操作奇数次那么方案数为\(\mathrm{C}_{n}^x\)。我们先把这x次操作干完然后剩下的就可以每两个操作组成一对去操作同一行操作完成之后那行还是偶数一共有\(\displaystyle\frac {r-x}{2}\)个操作对。由于每一行可以操作多次那么就是多重集的组合数\(\mathrm{C}_{n\frac{r-x}{2}-1}^{\frac{r-x}{2}}\)了。 所以最后一个(x,y)的贡献为\(\mathrm{C}_{n}^x\times\mathrm{C}_{n\frac{r-x}{2}-1}^{\frac{r-x}{2}}\times\mathrm{C}_{m}^y\times\mathrm{C}_{m\frac{c-y}{2}-1}^{\frac{c-y}{2}}\)。答案为所有(x,y)的贡献。 注意如果\(r-x\)或者\(c-y\)不是偶数那么贡献为0 转载于:https://www.cnblogs.com/oier/p/9776024.html
