为什么没有第八场呢？因为我上次咕了(之后会补的
题目链接：https://ac.nowcoder.com/acm/contest/889#question
B：
队友说是乱搞题。
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 9 typedef long long ll; 10 11 const ll MOD = 1000000007; 12 long long mod_exp(long long a, long long b) { //二分快速幂 13 long long res = 1; 14 while (b > 0) { 15 if (b & 1) res = (res * a) % MOD; 16 a = (a * a) % MOD; 17 b >>= 1; 18 } 19 return res; 20 } 21 22 long long solve(long long n, long long p) { 23 int Q = p - 1, S = 0; 24 while (Q % 2 == 0) { 25 Q >>= 1; 26 S++; 27 } 28 if (S == 1) { 29 return mod_exp(n, (p + 1) / 4); 30 } 31 int z; 32 while (1) { 33 z = 1 + rand() % (p - 1); 34 if (mod_exp(z, (p - 1) / 2) != 1) break; 35 } 36 long long c = mod_exp(z, Q); 37 long long R = mod_exp(n, (Q + 1) / 2); 38 long long t = mod_exp(n, Q); 39 long long M = S, b, i; 40 while (1) { 41 if (t % p == 1) break; 42 for (i = 1; i < M; i++) { 43 if (mod_exp(t, 1 << i) == 1) break; 44 } 45 b = mod_exp(c, 1 << (M - i - 1)); 46 R = (R * b) % p; 47 t = (t * b * b) % p; 48 c = (b * b) % p; 49 M = i; 50 } 51 return (R % p + p) % p; 52 } 53 54 int main() { 55 int T; 56 cin >> T; 57 while (T--) { 58 ll b, c; 59 cin >> b >> c; 60 ll dex = b * b - 4 * c; 61 dex = (dex + MOD) % MOD; 62 if (dex == 0) { 63 ll x1 = b * mod_exp(2, MOD - 2) % MOD; 64 cout << x1 << " " << x1 << endl; 65 continue; 66 } 67 if (mod_exp(dex, (MOD - 1) / 2) != 1) { 68 cout << "-1 -1" << endl; 69 continue; 70 } 71 ll rx = solve(dex, MOD); 72 ll x1 = (rx + b) * mod_exp(2, MOD - 2) % MOD; 73 ll x2 = (b - x1 + MOD) % MOD; 74 cout << min(x1, x2) << " " << max(x1, x2) << endl; 75 } 76 }
D：
乱搞的签到，给出的wiki毫无作用。二分按位枚举即可，之所以可以这么做是因为sum很小。
1 /* Nowcoder Contest 889 2 * Problem D 3 * Au: SJoshua 4 */ 5 #include <unordered_map> 6 #include <cstdio> 7 #include <vector> 8 #include <string> 9 #include <iostream> 10 #include <algorithm> 11 12 using namespace std; 13 14 int main(void) { 15 int n; 16 unsigned long long int s; 17 cin >> n >> s; 18 vector <unsigned long long int> nums(n); 19 unordered_map <unsigned long long int, int> mp; 20 for (int i = 0; i < n; i++) { 21 cin >> nums[i]; 22 } 23 int half = n / 2; 24 for (int i = 0; i < (1 << half); i++) { 25 unsigned long long int cur = 0; 26 for (int j = 0; j < half; j++) { 27 cur += ((i >> j) & 1) * nums[j]; 28 } 29 mp[cur] = i; 30 } 31 for (int i = 0; i < (1 << (n - half)); i++) { 32 unsigned long long int cur = 0; 33 for (int j = 0; j < n - half; j++) { 34 cur += ((i >> j) & 1) * nums[half + j]; 35 } 36 if (cur <= s) { 37 if (mp.count(s - cur)) { 38 int a = mp[s - cur]; 39 for (int j = 0; j < half; j++) { 40 cout << ((a >> j) & 1); 41 } 42 for (int j = half; j < n; j++) { 43 cout << ((i >> (j - half)) & 1); 44 } 45 cout << endl; 46 return 0; 47 } 48 } 49 } 50 return 0; 51 }
E：
H：
主席树(几乎)裸题，但是当时被二分check卡住了没想到怎么写，后来发现并不用二分。
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 = 2e5 + 10; 21 int root[maxn], cnt = 0; 22 ll preLen = 0; 23 24 struct Node { 25 ll sum; 26 int num, l, r; // 主席树维护区间元素个数，区间和 27 } segt[maxn * 40]; 28 29 void insert(int pos, int &cr, int lr, int curl, int curr) { 30 cr = ++cnt; segt[cr].num = segt[lr].num + 1; segt[cr].sum = segt[lr].sum + pos; 31 if (curl == curr) return; 32 int mid = curl + curr >> 1; 33 segt[cr].l = segt[lr].l, segt[cr].r = segt[lr].r; 34 if (pos <= mid) insert(pos, segt[cr].l, segt[lr].l, curl, mid); 35 else insert(pos, segt[cr].r, segt[lr].r, mid + 1, curr); 36 } 37 38 double query(int cr, int lr, int curl, int curr, double k, int remainNum) { 39 if (curl == curr) return (k - preLen) / remainNum; 40 int mid = curl + curr >> 1, currNum = segt[segt[lr].l].num - segt[segt[cr].l].num; 41 ll sum = preLen + segt[segt[lr].l].sum - segt[segt[cr].l].sum + (ll)mid * (remainNum - currNum); 42 if (sum - k < eps) { 43 preLen += segt[segt[lr].l].sum - segt[segt[cr].l].sum; 44 return query(segt[cr].r, segt[lr].r, mid + 1, curr, k, remainNum - currNum); 45 } else 46 return query(segt[cr].l, segt[lr].l, curl, mid, k, remainNum); 47 } 48 49 int main() { 50 int n, q; scanf("%d%d", &n, &q); 51 for (int i = 1; i <= n; i++) { 52 int x; scanf("%d", &x); 53 insert(x, root[i], root[i - 1], 1, 1e5); 54 } 55 while (q--) { 56 int l, r, x, y; scanf("%d%d%d%d", &l, &r, &x, &y); 57 ll totalLen = segt[root[r]].sum - segt[root[l - 1]].sum; 58 double perCutLen = (double)totalLen / y; 59 double remainLen = totalLen - perCutLen * x; 60 if (fabs(remainLen < eps)) remainLen = 0; 61 preLen = 0; 62 printf("%.10f ", query(root[l - 1], root[r], 1, 1e5, remainLen, r - l + 1)); 63 } 64 return 0; 65 }
J：
一道解法非常巧妙的题。实际上是要求一个分段函数的最小值，因为解出现的位置只有3种情况。
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,a) sort(a+1,a+1+a) 9 #define rep1(i,a,a) for(int i=a;i<=a;++i) 10 #define rep0(i,a,a) for(int i=a;i<a;++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 = 9e5 + 10; 21 ll a[maxn]; 22 23 int main() { 24 ll n; scanf("%lld", &n); 25 for (int i = 0; i < n; i++) { 26 ll l, r; scanf("%lld%lld", &l, &r); 27 a[i * 3] = l * 4, a[i * 3 + 1] = r * 4, a[i * 3 + 2] = (l + r) * 2 + 1; 28 } 29 sort(a, a + 3 * n); 30 ll ans = 0, cnt = 0, nu = 0, last = 0; 31 for (int i = 0; i < 3 * n; i++) { 32 nu += cnt * (a[i] / 2 - last); 33 ans = max(ans, nu); 34 last = a[i] / 2; 35 if (a[i] & 1) cnt -= 2; else cnt++; 36 } 37 printf("%lld ", ans); 38 return 0; 39 }