T1
Problem
Solution
感觉我写的也不是正解。。。
我是先找出每个循环节的长度l。。。然后用快速幂求出10 ^ k % l的值。。Code
#include#include #include #include #include using namespace std;#define ll long longll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}ll T[1000005];int main(){ ll n = read(), m = read(), k = read(), x = read(); T[0] = x; int l; for (int i = 1; i <= n; i++) { x = (x + m) % n; T[i] = x; if (T[i] == T[0]) { l = i; break; } } ll ans = 1, now = 10; while (k > 0) { if (k % 2 == 1) ans = ans * now % l; now = now * now % l; k /= 2; } printf("%d\n", T[ans]);}
T2
Problem
Solution
首先可以证明当Ai在A中大小排名和Bi在B中大小排名相等时，其差的平方时最小的。。
因此只要控制排名相等就可以了。。所以先排序，然后建立一个排名在A中和B中位置的关系。。。最后用归并排序求逆序对。。 证明（两个数）：设A中两个数a < b，B中两个数c < d ans1 = (a - c) ^ 2 + (b - d) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 - 2 * a * c - 2 * b * d ans2 = (a - d) ^ 2 + (b - c) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 - 2 * a * d - 2 * b * c 又因为a * c + b * d - a * d - b * c = (a - b) * (c - d) > 0 所以ans1 < ans2Code
#include#include #include #include #include using namespace std;#define ll long longll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}ll ans = 0;int X[100005], T[100005];struct node{ int val, id;}a[100005], b[100005];int cmp(node x, node y){ return x.val < y.val;}void merge(int xl, int xr, int yl, int yr){ int l = xl, r = yr, now = l; while (xl <= xr && yl <= yr) { if (X[xl] <= X[yl]) T[now++] = X[xl++]; else { T[now++] = X[yl++]; ans = (ans + xr - xl + 1) % 99999997; } } while (xl <= xr) T[now++] = X[xl++]; while (yl <= yr) T[now++] = X[yl++]; for (int i = l; i <= r; i++) X[i] = T[i];}void mergesort(int l, int r){ if (l == r) return; int mid = (l + r) >> 1; mergesort(l, mid); mergesort(mid + 1, r); merge(l, mid, mid + 1, r);}int main(){ int n = read(); for (int i = 1; i <= n; i++) a[i].val = read(), a[i].id = i; for (int i = 1; i <= n; i++) b[i].val = read(), b[i].id = i; sort(a + 1, a + n + 1, cmp); sort(b + 1, b + n + 1, cmp); for (int i = 1; i <= n; i++) X[b[i].id] = a[i].id; mergesort(1, n); printf("%lld\n", ans);}