A
/*Huyyt*/ #include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef unsigned long long ull; const ll LLmaxn = 2e18; int main() { string a; cin >> a; int b=0, c=0; for (int i = 0; i < a.size(); i++) { if (a[i] == '-') { b++; } else { c++; } } //cout<<b<<" "<<c<<endl; if (c == 0) { cout << "YES" << endl; return 0; } if (b % c != 0) { cout << "NO" << endl; } else { cout << "YES" << endl; } return 0; }
B
解:
注意只要是上下对称或者是左右对称就可以使得 1-4 有一条路径的话 2-3 也有相对应的一条路径
剩下的就容易构造了
/*Huyyt*/ #include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef unsigned long long ull; const ll LLmaxn = 2e18; char ans[5][105]; int main() { int n, k; cin >> n >> k; for (int i = 1; i <= 4; i++) { for (int j = 1; j <= n; j++) { ans[i][j] = '.'; } } int sum = (n - 2) * 2; if (k > sum) { cout << "NO" << endl; return 0; } cout << "YES" << endl; if (k % 2 == 0) { int cur = k; for (int j = 2; j <= n - 1 && cur; j++) { for (int i = 2; i <= 3 && cur; i++) { ans[i][j] = '#'; cur--; } } } else { k--; ans[2][n / 2 + 1] = '#'; for (int i = 2; i <= 3 && k; i++) { for (int j = 2; j <= n / 2 && k; j++) { ans[i][j] = ans[i][n - j + 1] = '#'; k -= 2; } } } for (int i = 1; i <= 4; i++) { for (int j = 1; j <= n; j++) { cout << ans[i][j]; } cout << endl; } return 0; }
C
解:
可以用并查集维护每个点最小到达的地方 也因为N<=1E5,K<=256 直接暴力模拟也可以
/*Huyyt*/ #include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef unsigned long long ull; const ll LLmaxn = 2e18; char ans[5][105]; int main() { int n, k; cin >> n >> k; for (int i = 1; i <= 4; i++) { for (int j = 1; j <= n; j++) { ans[i][j] = '.'; } } int sum = (n - 2) * 2; if (k > sum) { cout << "NO" << endl; return 0; } cout << "YES" << endl; if (k % 2 == 0) { int cur = k; for (int j = 2; j <= n - 1 && cur; j++) { for (int i = 2; i <= 3 && cur; i++) { ans[i][j] = '#'; cur--; } } } else { k--; ans[2][n / 2 + 1] = '#'; for (int i = 2; i <= 3 && k; i++) { for (int j = 2; j <= n / 2 && k; j++) { ans[i][j] = ans[i][n - j + 1] = '#'; k -= 2; } } } for (int i = 1; i <= 4; i++) { for (int j = 1; j <= n; j++) { cout << ans[i][j]; } cout << endl; } return 0; }
D
卡题意...
给出一个数组,把里面的数字分组,使得每一个组里面的数两两相乘都是完全平方数.
问最少可以分成的组数k是多少.
现在一个人有一个数组,他想知道这个数组的连续子数组中,使得上面的问题答案分别为1到n的数组有多少个.
第一种做法:
注意当一个数X的因数有完全平方数Y的时候 把这个数替换为X/Y并不影响结果
当一个数是0的时候要特判 要因为0乘任何数都是0可以加入任意一组
#include <stdio.h> #include <string.h> #include <algorithm> #include <set> #include <math.h> using namespace std; const int N = 500100; int a[N]; int b[N]; int c[N]; bool vis[N]; int mabs(int x) { return x >= 0 ? x : -x; } int main() { int n; int cnt = 0; scanf("%d",&n); for (int i = 0;i < n;i++) { scanf("%d",&a[i]); if (a[i] != 0) cnt++; } if (cnt == 0) { printf("%d ",n * (n + 1) / 2); for (int i = 1;i < n;i++) printf("0 "); } else { for (int i = 0;i < n;i++) { if (a[i] == 0) continue; int tmp = mabs(a[i]); for (int j = 2;j * j <= tmp;j++) { int t = j * j; while (a[i] % t == 0) { a[i] /= t; } //if (a[i] < t) break;加了这个就wa，卡了一晚上，考虑的应该是绝对值的情况 } } for (int i = 0;i < n;i++) c[i] = a[i]; sort(c,c+n); int js = unique(c,c+n) - c; for (int i = 0;i < n;i++) { if (a[i] == 0) continue; int p = lower_bound(c,c+js,a[i]) - c + 1; a[i] = p; } for (int i = 0;i < n;i++) { memset(vis,0,sizeof(vis)); int num = 0; for (int j = i;j < n;j++) { if (!vis[a[j]] && a[j] != 0) { num++; vis[a[j]] = 1; } int tt = max(num,1); b[tt]++; } } for (int i = 1;i <= n;i++) { printf("%d ",b[i]); } } return 0; }
第二种做法:
可以证明当A*B为完全平方数B*C也为完全平方数时 A*C也是完全平方数
所以只要N^2遍历 用并查集维护每个数属于哪个集合就行 注意0可以属于任意一个集合
#include<bits/stdc++.h> using namespace std; const int N = 5001; long long a[N]; int ans[N], fa[N], d[N]; int bz[N]; int n, sum, tot; bool check(long long x) { if (x < 0) { return 0; } long long y = sqrt(x); return y * y == x || (y - 1) * (y - 1) == x || (y + 1) * (y + 1) == x; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { fa[i] = i; } for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i]) { for (int j = 1; j <= d[0]; j++) if (check(a[i]*a[d[j]])) { fa[i] = d[j]; break; } if (fa[i] == i) { d[++d[0]] = i; } } } for (int i = 1; i <= n; i++) { sum = 0; tot++; for (int j = i; j <= n; j++) { if (a[j] && bz[fa[j]] != tot) { bz[fa[j]] = tot, sum++; } ans[max(sum, 1)]++; } } for (int i = 1; i <= n; i++) { cout << ans[i] << ' '; } return 0; }
E
给你N个点 组成的一颗树 分别从1标号到N 每个点的粉丝数量为2^i个
要求是选择K个点删除 使得剩下没被删的点保持连通且剩下的粉丝数量最大
一旦某个点被删除则其不能通过且该点的粉丝数量清零
假如做法顺着做 找出需要删除那些点的话 因为要保证连通性所以删除一个点需要删除掉他所有子树的点 不好做
题目提示你K<N 所以点N是一定可以保留的 就以N为根倍增预处理祖先 倒着做 找出不需要删除的点即可
/* Huyyt */ #include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define mkp(a,b) make_pair(a,b) #define pb push_back using namespace std; typedef long long ll; const long long mod = 1e9 + 7; const int N = 1e6 + 5; inline int readint() { char c = getchar(); int ans = 0; while (c < '0' || c > '9') { c = getchar(); } while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0', c = getchar(); } return ans; } vector<int> tree[N]; bool check[N]; int father[N][21]; int deep[N]; void dfs(int x, int level) { for (int i = 0; father[father[x][i]][i]; i++) { father[x][i + 1] = father[father[x][i]][i]; } deep[x] = level; for (int i = 0; i < tree[x].size(); i++) { int to = tree[x][i]; if (to == father[x][0]) { continue; } father[to][0] = x; dfs(to, level + 1); } } int main() { int n, k; n = readint(), k = readint(); //cout << n << " " << k << endl; int u, v; for (int i = 1; i < n; i++) { u = readint(),v = readint(); tree[u].pb(v); tree[v].pb(u); } k = n - k; k--, check[n] = 1; dfs(n, 1); for (int i = n - 1; i >= 1 && k; i--) { int aim = -1; int now = i; if (check[i]) { continue; } for (int j = 20; j >= 0; j--) { if (father[now][j] == 0 || check[father[now][j]]) { continue; } now = father[now][j]; } if (deep[i] - deep[now] + 1 <= k) { now = i; while (now != 0 && !check[now]) { check[now] = 1; k--; now = father[now][0]; } } } for (int i = 1; i <= n - 1; i++) { if (!check[i]) { cout << i << " "; } } return 0; }