题目链接:Dashboard - Educational Codeforces Round 173 (Rated for Div. 2) - Codeforces
总结:翻译插件用不了了,B题题意一直没看懂,C题出思路了好久才写出来,评价为太久没打了。
A. Coin Transformation
tag:模拟
B. Digits
tag:思维
Description:给定两个数 n , d n, d n,d,写成一个数 d d d d d . . . ddddd... ddddd...,由 n ! n! n!个 d d d拼接而成。判断 1 − 9 1-9 1−9中的奇数有哪些数是它的除数。
Solution: 1 1 1显然是;当 n > = 3 n >= 3 n>=3,此时 n ! n! n!是 3 3 3的倍数;当d == 5
时,5是;7:当n == 3
时, 111111 111111 111111是7的倍数。当 n > = 4 n>=4 n>=4时,均为 111111 111111 111111的倍数,因此是7的倍数;9和3相同使用数位和判断。
- 长度为x的一连串的数是d的倍数,那么长度为nx的一连串数也一定是d的倍数。
C. Sums on Segments
tag:思维
Description:给定一个数组,里面的元素只有一个元素不是-1或1,其余全是-1或1,求所有不同子数组的和。n <= 1e5
。
Solution:先考虑不含特殊数字,那么能够得到的数是一个连续的区间,范围为[min, max]
;用特殊数字将其分隔为左右两个区间。
- 包含特殊数字的变化区间为,从该数字往左右两端扩展到最大值和最小值。
void solve(){int n;cin >> n;vector<int> a(n);int idx = 0;for (int i = 0; i < n; i ++){cin >> a[i];if (a[i] != 1 && a[i] != -1){idx = i;}}int ri = 0, ra = 0;int mi = 0, ma = 0;int ans = 0;int li = 0, la = 0;if (idx != -1){for (int i = idx + 1, t = 0; i < n; i ++){t += a[i];ri = min(ri, t);ra = max(ra, t);}for (int i = idx - 1, t = 0; i >= 0; i --){t += a[i];li = min(li, t);la = max(la, t);}}int rri = 0, rra = 0;int ti = 0, ta = 0;for (int i = idx + 1; i < n; i ++){ti += a[i];ta += a[i];if (ti > 0){ti = 0;}if (ta < 0){ta = 0;}rri = min(rri, ti);rra = max(rra, ta);}int lli = 0, lla = 0;ti = ta = 0;for (int i = idx - 1; i >= 0; i --){ti += a[i];ta += a[i];if (ti > 0){ti = 0;}if (ta < 0){ta = 0;}lli = min(lli, ti);lla = max(lla, ta);}set<int> st;for (int i = lli; i <= lla; i ++)st.insert(i);for (int i = rri; i <= rra; i ++)st.insert(i);for (int i = li + ri; i <= la + ra; i ++)st.insert(i + a[idx]);st.insert(0);cout << st.size() << endl;for (auto i : st){cout << i << " ";}cout << endl;}
D. Problem about GCD
tag:数学
Description:给定三个数l, r, G
,需要求出a, b
满足l <= a <= b <= r, gcd(a, b) == G
,满足|a - b|
最大,当有多对答案时,输出a
最小的一对,否则输出-1 -1
。1 <= l <= r <= 1e18, 1 <= G <= 1e18
。
Solution:当G == 1时,等价于找出两个互质的数,两个互质的数之间的差距不会太大,直接暴力枚举即可;当G != 1时,先处于G即可。
trick:两个互质的数之间的差距不会太大,枚举的复杂度大概为 l o g 2 log^2 log2。
void solve(){int l, r, g;cin >> l >> r >> g;l = (l + g - 1) / g;r = r / g;for (int len = r - l; len >= 0; len --)for (int i = l; i + len <= r; i ++){int j = i + len;if (gcd(i, j) == 1){cout << i * g << " " << j * g << endl;return;}}cout << "-1 -1\n";
}
E. Matrix Transformation
tag:按位思考
Description:给定两个n * m
的矩阵a,b,可以对a矩阵执行任意顺序、任意次数的以下两种操作。
- 对第i行的所有元素,按位与上x;
- 对第j列的所有元素,按位或上x;
Solution:将矩阵按位分隔为01矩阵,每一位都是独立的。那么两种操作等价于将一行全变为0,将一列全变为0;
- 为了防止修改原数组,我们反过来操作矩阵b,如果一行全为0或一列全为1则进行标记;注意当一行被标记后,除了该行其余列为1的列需要标记。
- 判断未被标记的元素是否相等即可。
void solve(){int n, m;cin >> n >> m;vector a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> a[i][j];for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> b[i][j];for (int bit = 0; bit <= 30; bit ++){ // 枚举每一位vector<int> row(n + 1), col(m + 1);while (1){auto trow = row, tcol = col;for (int i = 1; i <= n; i ++){bool flag = true; // 每一位是否相同for (int j = 1; j <= m; j ++){if ((b[i][j] >> bit) & 1 == 1 && tcol[j] == 0){ // 一行全为0flag = false;}}if (flag){trow[i] = 1;;}}for (int i = 1; i <= m; i ++){bool flag = true; for (int j = 1; j <= n; j ++){if (((b[j][i] >> bit) & 1) == 0 && trow[j] == 0){ // 一列全为1flag = false;}}if (flag){tcol[i] = 1;;}}if (row == trow && col == tcol){break;}row = trow;col = tcol;}for (int i = 1; i <= n; i ++){if (row[i])continue;for (int j = 1; j <= m; j ++){if (col[j])continue;if (((a[i][j] >> bit) & 1) != ((b[i][j] >> bit) & 1)){cout << "No\n";return;}}}}cout << "Yes\n";
}