web analytics

Codeforces Global Round 6 笔记

掉了33的rating

A

B

没写出来的 C

题目大意: 让你构造一个矩阵,1,每行每列的gcd不同。2,这些gcd各不相同。3,这些gcd的最大值与最小值的差最小

采用平移的感觉的构造方式。因为本来r*c矩阵的gcd就有r+c个,那么我们就想办法让这些gcd刚好是1~r+c。

那么我们就让第i行的gcd为i,第j列的gcd为r+j。

那么为了保证这些gcd不重复,我们填的数就有所要求:

第一行我们填 r+1… c+1 第一行的gcd一定就是1(这样构造第一行我们就可以保证每一行的gcd都不会跟每一列的gcd重复。

因为我们i行的gcd要是i 那么我们可以让这一行均为 \(i * ( j + r )\)这样这一行的gcd就是i

因为我们j列的gcd要是 r+j,如果第一行第一列的数就是r+1 那么我们要让这一列数的gcd就是r+1 就让这列的每个数在这个基础上每次加r+1就好。也就是让我们这列上的数都是\(i * ( j + r )\)

很巧妙发现如果这样\(i * ( j + r )\)构造,行和列都可以满足我们的要求(第i行的gcd为i,第j列的gcd为r+j)。

当然这道题需要特判一下行为1 或者列为1 或者行和列均为1的情况。

D

题目大意: n个人m笔交易 然后让你简化这些交易

因为借出去的钱和收到的钱是守恒的,所以我们就可以贪心的手法,每次算一下这个人总的收支情况,然后瞎凑对子就可以了。