西瓜队（划掉），Kuma Rider久违的第一场训练，四小时瞎打.jpg
A.水题，排序
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<map> #include<functional> #include<vector> using namespace std; typedef long long ll; #define lowbit(i) ((i)&(-i)) const ll maxv = 1e5 + 5; ll n,d[maxv], c[maxv]; void update(ll x, ll v) { for (ll i = x; i < maxv; i+=lowbit(i)) { c[i] += v; } } ll getsum(ll x) { ll sum = 0; for (ll i = x; i > 0; i -= lowbit(i)) { sum += c[i]; } return sum; } int main() { scanf("%lld", &n); for (ll i = 1; i <= n; i++) { scanf("%lld", &d[i]); } sort(d+1 , d+1 + n); ll ans = 0; for (ll i = 1; i <= n; i++) { ll num = getsum(i-1); num = (i - 1) - num; //printf("%lld %lld ", i, num); ans += num; update(d[i], 1); } ans *= 2; printf("%lld ", ans); }
B.找到树的直径，倍增地跳跃计算答案
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<map> #include<functional> #include<vector> using namespace std; typedef long long LL; int n; vector<int>e[500005]; bool vis[500005]; int Root, Tail; int BFS(int st) { for (int i = 1; i <= n; i++)vis[i] = false; queue<int>q; q.push(st); vis[st] = true; int ret = st; while (!q.empty()) { int t = q.front(); q.pop(); ret = t; for (int i = 0; i < e[t].size(); i++) { int to = e[t][i]; if (!vis[to]) { q.push(to); vis[to] = true; } } } return ret; } int len; void DFS(int nx, int pr, int st) { len = max(len, st); for (int i = 0; i < e[nx].size(); i++) { int to = e[nx][i]; if (to != pr) { DFS(to, nx, st + 1); } } } int main() { scanf("%d", &n); for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d %d", &u, &v); e[u].push_back(v); e[v].push_back(u); } Root = BFS(1); Tail = BFS(Root); len = 0; DFS(Root, -1, 1); //printf("%d %d ", Root, Tail); int ans = 0; int tl = 1; while (tl<len-1) { ans++; tl <<= 1; } printf("%d ", ans); }
C.水题
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<map> using namespace std; char s[10005]; int main() { scanf("%s", s); int len = strlen(s); int lsc = 0, pcms = 0; for (int i = 0; i < len-2; i++) { if (s[i] == 'L'&&s[i + 1] == 'S'&&s[i + 2] == 'C')lsc++; } for (int i = 0; i < len - 3; i++) { if (s[i] == 'P'&&s[i + 1] == 'C'&&s[i + 2] == 'M'&&s[i + 3] == 'S')pcms++; } if (pcms > lsc)printf("PCMS "); else if (pcms < lsc)printf("LSC "); else printf("Tie "); }
D.比赛没来得及写的题。（1953.1.1居然是星期六！！一直以为是星期日！！！）
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<iostream> #include<map> #include<vector> #include<set> #include<queue> using namespace std; int days[13] = { 0, 31, 28 ,31 ,30 ,31 ,30 ,31 ,31 ,30 ,31 ,30 ,31 }; int q, st, ed, day, month, gi[8], ans[404]; bool isleap(int year) { return (year % 400 == 0) || ((year % 4 == 0) && (year % 100)); } int cal(int yy, int mm, int dd) { int sum = 0; for (int i = 1; i < mm; i++) { sum += days[i]; if (isleap(yy) && i == 2) sum++; } return sum+dd-1; } void cycle(int mm,int dd) { int cnt=1,now = 6;//1953/1/1是星期六 for (int i = 1583; i <= 1583 + 399; i++) { if (mm == 2 && dd == 29 && !isleap(i)) { ans[cnt++] = 0; } else { ans[cnt++] = (cal(i, mm, dd) + now - 1) % 7 + 1; } if (isleap(i)) now = (now + 366 - 1) % 7 + 1; else now = (now + 365 - 1) % 7 + 1; } } int main() { scanf("%d", &q); while (q--) { memset(ans, 0, sizeof(ans)); memset(gi, 0, sizeof(gi)); scanf("%d %d %d %d", &st, &ed, &month, &day); cycle(month, day); int numed = (ed-1583 + 1) / 400; int numst = (st - 1583) / 400; for (int i = 1; i <= 400; i++) { gi[ans[i]] += (numed - numst); } int mped = ed - 1583 + 1 - numed * 400; int mpst = st - 1583 - numst * 400; for (int i = 1; i <= mpst; i++) { gi[ans[i]]--; } for (int i = 1; i <= mped; i++) { gi[ans[i]]++; } printf("%d", gi[7]); for (int i = 1; i <= 6; i++) { printf(" %d", gi[i]); } puts(""); } return 0; }
E.还没看，待补
F.还没写，待补
G.还没写，待补
H.几何板子题，两圆交点，我抄错板子错了好久quq
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<cmath> #include<map> #include<functional> #include<vector> using namespace std; const double eps = 1e-5; struct Point { double x, y; Point(double _a, double _b) :x(_a), y(_b) {} Point() {} }; Point intersection(const Point &u1, const Point &u2, const Point &v1, const Point &v2) { Point res = u1; double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x)) / ((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x)); res.x += (u2.x - u1.x)*t; res.y += (u2.y - u1.y)*t; return res; } double dis(const Point &p1, const Point &p2) { return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); } void play(const Point &c, double r, const Point &l1, const Point &l2, Point &p1, Point &p2) { Point p = c; p.x += l1.y - l2.y; p.y += l2.x - l1.x; p = intersection(p, c, l1, l2); double t = sqrt(r*r - dis(p, c)*dis(p, c)) / dis(l1, l2); p1.x = p.x + (l2.x - l1.x)*t; p1.y = p.y + (l2.y - l1.y)*t; p2.x = p.x - (l2.x - l1.x)*t; p2.y = p.y - (l2.y - l1.y)*t; } void play2(const Point &c1, double r1, const Point &c2, double r2, Point &p1, Point &p2) { Point u, v; double t = (1 + (r1*r1 - r2*r2) / dis(c1, c2) / dis(c1, c2)) / 2; u.x = c1.x + (c2.x - c1.x)*t; u.y = c1.y + (c2.y - c1.y)*t; v.x = u.x + c1.y - c2.y; v.y = u.y - c1.x + c2.x; play(c1, r1, u, v, p1, p2); } double x1, x2, r1, yy, y2, r2; int main() { cin >> x1 >> yy >> r1; cin >> x2 >> y2 >> r2; Point ans1, ans2; if (r1 > r2) { swap(x1, x2); swap(yy, y2); swap(r1, r2); } double ds = dis(Point(x1, yy), Point(x2, y2)); if (r2 >= ds) { printf("%.6lf %.6lf ", x1, yy); return 0; } play2(Point(x1, yy), r1, Point(x2, y2), r2, ans1, ans2); printf("%.6lf %.6lf ", ans1.x, ans1.y); return 0; }
I.瞎搞
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<cmath> #include<map> #include<functional> #include<vector> using namespace std; typedef long long ll; const double eps = 1e-5; ll ax[1001000]; int main(void) { ll n; scanf("%lld", &n); for (int i = 0; i < n; i++) { scanf("%lld", &ax[i]); } if (n == 1) { printf("0 "); return 0; } else if (n == 2) { printf("%lld ", min(abs(ax[1] - ax[0]),abs(ax[1]+ax[0]))); return 0; } vector<ll>v; ll sum = 0; for (int i = 0; i<n - 1; i++) { sum += abs(ax[i + 1] - ax[i]); v.push_back(abs(ax[i + 1] + ax[i]) - abs(ax[i + 1] - ax[i])); } sort(v.begin(), v.end()); if (v[0] < 0) { sum += v[0]; } if (v[1] < 0) { sum += v[1]; } printf("%lld ", sum); }
J.还没写，待补
K.水题，四个角满足即可
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<vector> #include<map> #include<functional> #include<vector> using namespace std; typedef long long LL; int n; int main() { int n, m, k; int cnt = 0; scanf("%d %d %d", &n, &m, &k); for (int i = 1; i <= k; i++) { int x, y; scanf("%d %d", &x, &y); if (x == 1 && y == m) cnt++; else if (x == 1 && y == 1) cnt++; else if (x == n&&y == 1) cnt++; else if (x == n&&y == m) cnt++; } int tmp = 4; if (n == 1 && m == 1) tmp = 1; else if (n == 1 || m == 1) tmp = 2; printf("%d ", tmp - cnt); return 0; }
L.还没写，待补