Codeforces Round #766 (Div. 2)
A. Not Shading题意:有 n × m ntimes m n×m 的方格,每个格子或黑或白, *** 作为选择一个黑色的格子将它所在的行或列染黑,问最少多少次 *** 作后 ( r , c ) (r, c) (r,c)所在的格子被染黑,不可能输出-1.
如果 ( r , c ) (r, c) (r,c)本身就是黑色,输出0
如果 ( r , c ) (r, c) (r,c)所在的行或列有黑色,输出1
如果格子内有黑色输出2
否则-1
#includeB. Not Sittingusing namespace std; typedef long long ll; const int N = 60; char mp[N][N]; int n, m, r, c; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while (T--) { cin >> n >> m >> r >> c; bool flag = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> mp[i][j]; if (mp[i][j] == 'B') flag = 1; } } if (!flag) { cout << -1 << endl; continue; } if (mp[r][c] == 'B') { cout << 0 << endl; continue; } bool flagr = 0, flagc = 0; for (int i = 1; i <= m; ++i) if (mp[r][i]=='B') flagr = 1; for (int i = 1; i <= n; ++i) if (mp[i][c]=='B') flagc = 1; if (flagr || flagc) { cout << 1 << endl; continue; } cout << 2 << endl; } return 0; }
题意:T和R在玩游戏,有 n × m ntimes m n×m个座位,刚开始T会选k个座位染色,然后R选择座位,R不会选择染色的座位但他想尽量离T近一些,R选完T选,T想尽量离R远一些,问当k取0到n-1的时候这个距离是多少
先染最中心的位置然后一圈一圈扩开来
就是T最后选的位置一定是四个角上,然后就是看每个位置离四个角最远距离是多少,先染距离近的,就是最中间
#includeusing namespace std; typedef long long ll; int dx[4] = {0, -1, 0, 1}; int dy[4] = {1, 0, -1, 0}; signed main() { int T; cin >> T; while (T--) { int n, m; cin >> n >> m; vector > a; a.resize(n +1, vector (m +1)); int x = (n + 1) / 2; int y = (m + 1) / 2; if (n % 2 == 0) x++; if (m % 2 == 0) y++; queue > que; que.push({x, y}); a[x][y] = x - 1 + y - 1; if (n % 2 == 0 && m % 2 == 0) { a[x - 1][y - 1] = a[x][y]; a[x - 1][y] = a[x][y]; a[x][y - 1] = a[x][y]; que.push({x - 1, y - 1}); que.push({x - 1, y}); que.push({x, y - 1}); } else if (n % 2 == 0) { a[x - 1][y] = a[x][y]; que.push({x - 1, y}); } else if (m % 2 == 0) { a[x][y - 1] = a[x][y]; que.push({x, y - 1}); } while(!que.empty()) { auto tmp = que.front(); que.pop(); for(int k = 0; k< 4; ++ k) { int nx = tmp.first + dx[k]; int ny = tmp.second + dy[k]; if(nx < 1 || nx > n) continue; if(ny < 1 || ny > m) continue; if(a[nx][ny] != 0) continue; a[nx][ny] = a[tmp.first][tmp.second] + 1; que.push({nx, ny}); } } vector res; for(int i =1;i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { res.push_back(a[i][j]); } } sort(res.begin(), res.end()); for(auto num: res) { cout << num << " "; } cout < C. Not Assigning 题意:定义质数树为所有边权或相邻两边权之和均为质数的数,现给出一棵树要求给边加边权使得满足上述要求
如果一个点的度数大于2必然会造成有相邻两边均为奇数质数,想加为大于2的偶数->合数的情况。
每个点的度数最多是2
这样就是一条链,2/5轮流给边加权
#includeD. Not Addingusing namespace std; typedef long long ll; const int N = 1e5 + 10; vector g[N]; int du[N]; vector > edges; map , int> mp; inline void init(int n) { for (int i = 0; i <= n; ++i) { g[i].clear(); du[i] = 0; } edges.clear(); } void dfs(int x, int p, int dep) { for (auto to : g[x]) { if (to == p) continue; pair tt; tt.first = min(x, to), tt.second = max(x, to); mp[tt] = (dep & 1) ? 2 : 5; dfs(to, x, dep + 1); } } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; init(n); for (int i = 1, u, v; i < n; ++i) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); du[u]++, du[v]++; int mn = min(u, v), mx = max(u, v); edges.push_back({mn, mx}); } bool flag = 1; int be = -1; for (int i = 1; i <= n; ++i) { if (du[i] > 2) flag = 0; if (du[i] == 1) be = i; } if (!flag) { cout << -1 << endl; continue; } dfs(be, -1, 0); for (auto tmp : edges) { cout << mp[tmp] << " "; } cout << endl; } } 题意:刚开始有n个不同的数,每次可以取两个数将他们的gcd放进去(如果gcd不在原数列中),问最多可以 *** 作几次
原数数字范围是1e6,总的数字范围也是1e6(因为不可能gcd出的数比原数还大,
枚举每个数在不在最后的数列里,
一个数x在最后数列里的条件是(1)它刚开始就在数列中(2)所有是x的倍数的数的gcd是x(取x的倍数是因为只有这些数可能gcd出x,如果这些数的总gcd都不能出x那x就出不来)
枚举倍数是个调和级数
#includeusing namespace std; typedef long long ll; const int N = 1e6 + 10; bool mp[N]; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int n; cin >> n; for (int i = 1, x; i <= n; ++i) { cin >> x; mp[x] = 1; } int cnt = 0; for (int i = 1; i < N; ++i) { if (mp[i]) { cnt++; continue; } int d = 0; for (int j = i; j < N; j += i) { if (mp[j]) { d = __gcd(d, j); } } if (d == i) { cnt++; } } cout << cnt - n << endl; return 0; } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)