最近事务繁多，很久没写文章了。正好趁刚换新队友的第一场训练，记录一下。
题目中规中矩。
A：
solver：lzh
完全没看，好像是个傻逼题。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() { 4 int a, b, n; scanf("%d%d%d", &a, &b, &n); 5 int c = b, d = a, ans = 0, cur = 1; 6 while (c != n || d != n) { 7 if (!cur) { 8 c += b - a; 9 if (c > n)c = n; 10 } else { 11 d += b - a; 12 if (d > n)d = n; 13 } 14 cur ^= 1; 15 ans++; 16 } 17 printf("%d\n", ans); 18 }
E：
solver：zyh、lzh
给定一棵树，树上有若干个重要点。问是否存在一个点到所有重要点距离相等。
树的直径瞎搞。
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<int>v[200010]; int mark[200010], ismark[200010]; int st[200010], num = 0, ans = 0, ansn; int dep[200010]; void dfs1(int x, int pre, int d) { st[++num] = x; if (ismark[x] && ans < d)ans = d, ansn = st[num + 1 >> 1]; for (auto i : v[x]) if (i != pre) dfs1(i, x, d + 1); num--; } void dfs2(int x, int pre, int d) { dep[x] = d; for (auto i : v[x]) if (i != pre) dfs2(i, x, d + 1); } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 2; i <= n; i++) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } for (int i = 1; i <= m; i++)scanf("%d", &mark[i]), ismark[mark[i]]++; if (m == 1) { printf("YES\n1\n"); return 0; } dfs1(mark[1], -1, 0); if (ans & 1) { printf("NO\n"); return 0; } dfs2(ansn, -1, 1); for (int i = 2; i <= m; i++) if (dep[mark[i - 1]] != dep[mark[i]]) { printf("NO\n"); return 0; } printf("YES\n%d\n", ansn); }
H：
solver：czq
给定n个数，要求把这n个数分成连续的尽量少的块，并且每块和<=t。
由于有多个询问，故可以预处理出每个询问能装多少个数。然后每个询问直接模拟统计答案。
1 /* basic header */ 2 #include <bits/stdc++.h> 3 /* define */ 4 #define ll long long 5 #define dou double 6 #define pb emplace_back 7 #define mp make_pair 8 #define sot(a,b) sort(a+1,a+1+b) 9 #define rep1(i,a,b) for(int i=a;i<=b;++i) 10 #define rep0(i,a,b) for(int i=a;i<b;++i) 11 #define eps 1e-8 12 #define int_inf 0x3f3f3f3f 13 #define ll_inf 0x7f7f7f7f7f7f7f7f 14 #define lson (curpos<<1) 15 #define rson (curpos<<1|1) 16 /* namespace */ 17 using namespace std; 18 /* header end */ 19 20 const int maxn = 1e6 + 10; 21 int n, a[maxn], pos[maxn], cnt[maxn], preSum[maxn], maxx; 22 23 int solve(int x) { 24 if (x < maxx) return -int_inf; 25 if (cnt[x]) return cnt[x]; 26 int res = 0, i = 0; 27 while (i < n) { 28 res += x; 29 res = min(res, 1000000); 30 i = pos[res]; 31 res = preSum[i]; 32 cnt[x]++; 33 } 34 return cnt[x]; 35 } 36 37 int main() { 38 scanf("%d", &n); 39 for (int i = 1; i <= n; i++) { 40 scanf("%d", &a[i]); 41 maxx = max(maxx, a[i]); 42 preSum[i] = preSum[i - 1] + a[i]; 43 for (int j = preSum[i - 1]; j < preSum[i]; j++) pos[j] = i - 1; 44 } 45 for (int i = preSum[n]; i <= 1000000; i++) pos[i] = n; 46 int q; scanf("%d", &q); 47 while (q--) { 48 int x; scanf("%d", &x); 49 int ret = solve(x); 50 if (ret != -int_inf) printf("%d\n", solve(x)); 51 else puts("Impossible"); 52 } 53 return 0; 54 }
I：
solver：czq
给定三维空间内的n个点，要求构造一个尽量小的四棱锥(底面两边与坐标轴平行，且锥面与底面夹角为45度)，使得该四棱锥能包含n个点。
因为锥面与底面夹角为45度，故可以拆开分别考察xOz和yOz两个平面，构造出两个等腰直角三角形之后再合并答案。
1 /* basic header */ 2 #include <bits/stdc++.h> 3 /* define */ 4 #define ll long long 5 #define dou double 6 #define pb emplace_back 7 #define mp make_pair 8 #define sot(p,b) sort(p+1,p+1+b) 9 #define rep1(i,p,b) for(int i=p;i<=b;++i) 10 #define rep0(i,p,b) for(int i=p;i<b;++i) 11 #define eps 1e-8 12 #define int_inf 0x3f3f3f3f 13 #define ll_inf 0x7f7f7f7f7f7f7f7f 14 #define lson (curpos<<1) 15 #define rson (curpos<<1|1) 16 /* namespace */ 17 using namespace std; 18 /* header end */ 19 20 const int maxn = 1e3 + 10; 21 struct Point { 22 int x, y, z; 23 } p[maxn]; 24 int n, l1 = INT_MAX, l2 = INT_MAX, r1 = -INT_MAX, r2 = -INT_MAX; 25 26 int main() { 27 scanf("%d", &n); 28 for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); 29 for (int i = 1; i <= n; i++) { 30 l1 = min(p[i].x - p[i].z, l1); l2 = min(p[i].y - p[i].z, l2); 31 r1 = max(p[i].x + p[i].z, r1); r2 = max(p[i].y + p[i].z, r2); 32 } 33 int currx = l1 + r1 >> 1, curry = l2 + r2 >> 1; 34 int h1 = max(currx - l1, curry - l2), h2 = max(r1 - currx, r2 - curry); 35 printf("%d %d %d\n", currx, curry, max(h1, h2)); 36 return 0; 37 }
J：
solver：czq
显然倒着构造会好构造很多。对于点对(i,j)，计算所有的k(i<k<j)对a[i][j]的贡献即可。如果不一样，说明点i与点j之间存在边。
1 /* basic header */ 2 #include <bits/stdc++.h> 3 /* define */ 4 #define ll long long 5 #define dou double 6 #define pb emplace_back 7 #define mp make_pair 8 #define sot(ans,b) sort(ans+1,ans+1+b) 9 #define rep1(i,ans,b) for(int i=ans;i<=b;++i) 10 #define rep0(i,ans,b) for(int i=ans;i<b;++i) 11 #define eps 1e-8 12 #define int_inf 0x3f3f3f3f 13 #define ll_inf 0x7f7f7f7f7f7f7f7f 14 #define lson (curpos<<1) 15 #define rson (curpos<<1|1) 16 /* namespace */ 17 using namespace std; 18 /* header end */ 19 20 const int maxn = 510; 21 int n, a[maxn][maxn], ans[maxn][maxn]; 22 23 int main() { 24 scanf("%d", &n); 25 for (int i = 1; i <= n; i++) 26 for (int j = 1; j <= n; j++) 27 scanf("%1d", &a[i][j]); 28 for (int i = n - 1; i >= 1; i--) 29 for (int j = i; j <= n; j++) { 30 int contribute = 0; 31 for (int k = i + 1; k < j; k++) contribute = (contribute + ans[i][k] * a[k][j]) % 10; 32 if (contribute != a[i][j]) ans[i][j] = 1; 33 } 34 for (int i = 1; i <= n; i++) { 35 for (int j = 1; j <= n; j++) printf("%d", ans[i][j]); 36 puts(""); 37 } 38 return 0; 39 }
K：
solver：lzh、czq
细节贪心题，枚举A的最大可能上下边界，得出可行的左右边界，再分割剩下的区域。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<int, char> pic; 5 typedef pair<int, int> pii; 6 char s[1010][1010], ans[1010][1010]; 7 pii p[30]; 8 vector<pic> v[1010]; 9 int pt[1010]; 10 void solve(pii l, pii r) { 11 for (int i = 1; i <= 1000; i++)v[i].clear(), pt[i] = 0; 12 for (int i = 2; i <= 26; i++) 13 if (l.first <= p[i].first && p[i].first <= r.first && 14 l.second <= p[i].second && p[i].second <= r.second) 15 v[p[i].first].push_back(make_pair(p[i].second, i + 'a' - 1)); 16 17 for (int i = l.first; i <= r.first; i++) 18 sort(v[i].begin(), v[i].end()); 19 20 for (int i = l.first; i <= r.first; i++) 21 if (v[i].size() == 0 && pt[i - 1]) { 22 for (int j = l.second; j <= r.second; j++)ans[i][j] = ans[i - 1][j]; 23 pt[i] = 1; 24 } else if (v[i].size() == 1) { 25 for (int j = l.second; j <= r.second; j++)ans[i][j] = v[i][0].second; 26 pt[i] = 1; 27 } else if (v[i].size() > 1) { 28 pt[i] = 1; 29 int pre = l.second; 30 for (auto j : v[i]) { 31 for (; pre <= j.first; pre++)ans[i][pre] = j.second; 32 } 33 34 for (; pre <= r.second; pre++)ans[i][pre] = ans[i][pre - 1]; 35 } 36 37 for (int i = r.first; i >= l.first; i--) 38 if (!pt[i]) 39 for (int j = l.second; j <= r.second; j++) 40 ans[i][j] = ans[i + 1][j]; 41 } 42 int main() { 43 int n, m; scanf("%d%d", &n, &m); 44 pii A; 45 for (int i = 1; i <= n; i++) { 46 scanf("%s", s[i] + 1); 47 for (int j = 1; j <= m; j++) 48 if (s[i][j] != '.') { 49 if (s[i][j] != 'A') { 50 p[s[i][j] - 'A' + 1] = make_pair(i, j); 51 v[i].push_back(make_pair(j, s[i][j] + 'a' - 'A')); 52 } else A = make_pair(i, j); 53 } 54 } 55 56 int tmp = 0; 57 pii L, R; 58 for (int i = 1; i <= n; i++) { 59 priority_queue<int>l; 60 priority_queue<int, vector<int>, greater<int>>r; 61 l.push(0); 62 r.push(m + 1); 63 for (int j = i; j <= n; j++) { 64 int gg = 0; 65 for (int k = 2; k <= 26; k++) 66 if (i <= p[k].first && p[k].first <= j) { 67 if (p[k].second == A.second) { 68 gg++; break; 69 } else if (p[k].second < A.second)l.push(p[k].second); 70 else r.push(p[k].second); 71 } 72 if (gg)break; 73 if (i <= A.first && A.first <= j && l.top() < A.second && A.second < r.top() 74 && (j - i + 1) * (r.top() - l.top() - 1) > tmp) { 75 tmp = (j - i + 1) * (r.top() - l.top() - 1); 76 L = make_pair(i, l.top() + 1); 77 R = make_pair(j, r.top() - 1); 78 } 79 } 80 } 81 if (L.first != 1)solve(make_pair(1, 1), make_pair(L.first - 1, m)); 82 if (R.first != n)solve(make_pair(R.first + 1, 1), make_pair(n, m)); 83 if (L.second != 1)solve(make_pair(L.first, 1), make_pair(R.first, L.second - 1)); 84 if (R.second != m)solve(make_pair(L.first, R.second + 1), make_pair(R.first, m)); 85 86 for (int i = 2; i <= 26; i++)ans[p[i].first][p[i].second] = 'A' + i - 1; 87 for (int i = L.first; i <= R.first; i++) 88 for (int j = L.second; j <= R.second; j++) 89 ans[i][j] = 'a'; 90 ans[A.first][A.second] = 'A'; 91 92 for (int i = 1; i <= n; i++, printf("\n")) 93 for (int j = 1; j <= m; j++) 94 printf("%c", ans[i][j]); 95 }
M：
solver：zyh
没看，签到。
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 using namespace std; 5 int a[10001]; 6 map<int, int> M; 7 int main() { 8 int T; 9 long long ans = 0; 10 scanf("%d", &T); 11 while (T--) { 12 int n; 13 M.clear(); 14 ans = 0; 15 scanf("%d", &n); 16 for (int i = 0; i < n; ++i) { 17 scanf("%d", &a[i]); 18 M[a[i]]++; 19 } 20 for (int j = 0; j < n; ++j) { 21 M[a[j]]--; 22 if (M[a[j]] == 0) M.erase(a[j]); 23 for (int i = 0; i < j; ++i) { 24 int k = 2 * a[j] - a[i]; 25 26 if (M.find(k) != M.end()) ans += M[k]; 27 } 28 } 29 printf("%lld\n", ans); 30 } 31 }