题目链接：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){ // 一行全为0
flag = 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){ // 一列全为1
flag = 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";
}
