gdcpc前一天上午搞了场训练，水题挺多，还算增强信心。(这么简单的题目居然还是div1，这赛区……
最终9题，平均每人3题，我写ACF。被hry压了一道E (难受啊。
下午去中大试机，win7系统就算了，键盘垃圾得要死 (就我工软院机房那种巧克力键盘)，还居然用的是云桌面，不能用alt+tab、win+d这种快捷键 (这真的难受。
随便写了写热身赛，看到有个sb线段树 (跟 https://ac.nowcoder.com/acm/contest/200/B?&headNav=www 一模一样) 我都不是很想写 (困得要死。
但是我知道明天的比赛绝对没有早上的训练这么水。希望能正常发挥，拿个Ag吧。
题目链接：http://codeforces.com/gym/101982
A：
温暖签到。
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define sot(a,b) sort(a+1,a+1+b) 28 #define rep1(i,a,b) for(int i=a;i<=b;++i) 29 #define rep0(i,a,b) for(int i=a;i<b;++i) 30 #define repa(i,a) for(auto &i:a) 31 #define eps 1e-8 32 #define int_inf 0x3f3f3f3f 33 #define ll_inf 0x7f7f7f7f7f7f7f7f 34 #define lson curPos<<1 35 #define rson curPos<<1|1 36 /* namespace */ 37 using namespace std; 38 /* header end */ 39 40 int k; 41 string a, b; 42 43 int main() 44 { 45 cin >> k >> a >> b; 46 int same = 0, diff = 0; 47 int len = a.size(); 48 for (int i = 0; i < len; i++) 49 if (a[i] != b[i]) diff++; else same++; 50 if (same <= k) cout << same + diff - k + same << endl; 51 else cout << k + diff << endl; 52 return 0; 53 }
B：
枚举答案即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int maxn = 10010000; 8 9 int N[maxn]; 10 int p[maxn]; 11 int mu[maxn]; 12 int cnt; 13 void sha() 14 { 15 N[1] = 1; 16 mu[1] = 1; 17 for (int i = 2; i < maxn; i++) 18 { 19 if (!N[i]) 20 { 21 p[++cnt] = i; 22 mu[i] = -1; 23 } 24 for (int j = 1; j <= cnt; j++) 25 { 26 if (i * p[j] >= maxn) break; 27 N[i * p[j]] = 1; 28 if (i % p[j] == 0) 29 { 30 mu[i * p[j]] = 0; 31 break; 32 } 33 else 34 { 35 mu[i * p[j]] = -mu[i]; 36 } 37 } 38 } 39 } 40 41 int sum[maxn]; 42 typedef long long ll; 43 44 ll cal(ll n, ll m) 45 { 46 long long ans = 0; 47 if (n > m) swap(n, m); 48 for (int i = 1, la = 0; i <= n; i = la + 1) 49 { 50 la = min(m / (m / i), n / (n / i)); 51 ans += (sum[la] - sum[i - 1]) * (n / i) * (m / i); 52 } 53 return ans; 54 } 55 56 int main() 57 { 58 sha(); 59 ll a, b, x, y; 60 cin >> a >> b >> x >> y; 61 for (int i = 1; i < maxn; i++) 62 { 63 sum[i] = sum[i - 1] + mu[i]; 64 } 65 ll ans = cal(b, y) - cal(a - 1, y) - cal(b, x - 1) + cal(a - 1, x - 1); 66 cout << ans << endl; 67 return 0; 68 }
C：
简单dp。
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define rep1(i,a,b) for(int i=a;i<=b;++i) 28 #define rep0(i,a,b) for(int i=a;i<b;++i) 29 #define repa(i,a) for(auto &i:a) 30 #define eps 1e-8 31 #define int_inf 0x3f3f3f3f 32 #define ll_inf 0x7f7f7f7f7f7f7f7f 33 #define lson curPos<<1 34 #define rson curPos<<1|1 35 /* namespace */ 36 using namespace std; 37 /* header end */ 38 39 const int maxn = 1e3 + 10; 40 const ll mod = 998244353; 41 map<ll, ll>cnt; 42 vector<ll>v; 43 ll a[maxn], dp[maxn][maxn], ans[maxn][maxn]; 44 45 int main() 46 { 47 int n, k; 48 ll x; 49 scanf("%d%d", &n, &k); 50 rep1(i, 1, n) 51 { 52 scanf("%lld", &x); 53 if (!cnt[x]) v.push_back(x); 54 cnt[x]++; 55 } 56 n = v.size(); 57 rep1(i, 1, n) a[i] = cnt[v[i - 1]]; 58 rep1(i, 1, n) 59 { 60 dp[1][i] = a[i] % mod; 61 ans[1][i] = (dp[1][i] + ans[1][i - 1]) % mod; 62 } 63 rep1(i, 2, k) 64 { 65 rep1(j, 1, n) 66 { 67 dp[i][j] = a[j] * ans[i - 1][j - 1] % mod; 68 ans[i][j] = (dp[i][j] + ans[i][j - 1]) % mod; 69 } 70 } 71 printf("%lld ", ans[k][n]); 72 return 0; 73 }
D：
数位dp，队友搞出来的，我没看懂。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long ll; 9 ll f[130][1110][130]; 10 ll mod = 1000000009; 11 12 int main() 13 { 14 ll Mod, bit; 15 cin >> Mod >> bit; 16 f[1][1 % Mod][1] = 1; 17 for (int i = 1; i <= bit; i++) 18 { 19 for (int j = 0; j < Mod; j++) 20 { 21 for (int k = 0; k <= i; k++) 22 { 23 f[i + 1][(j * 2) % Mod][k] += f[i][j][k]; 24 f[i + 1][(j * 2 + 1) % Mod][k + 1] += f[i][j][k]; 25 f[i + 1][(j * 2) % Mod][k] %= mod; 26 f[i + 1][(j * 2 + 1) % Mod][k + 1] %= mod; 27 } 28 } 29 } 30 ll ans = 0; 31 for (int i = 1; i <= bit; i++) 32 { 33 for (int j = 0; j <= i; j++) 34 { 35 ans += f[i][0][j] * j; 36 ans %= mod; 37 } 38 } 39 cout << ans << endl; 40 return 0; 41 }
E：
没做。胡老师写的是最小割。
F：
超级classic的扫描线套线段树，不用看板子都能写。
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define sot(a,b) sort(a+1,a+1+b) 28 #define rep1(i,a,b) for(int i=a;i<=b;++i) 29 #define rep0(i,a,b) for(int i=a;i<b;++i) 30 #define repa(i,a) for(auto &i:a) 31 #define eps 1e-8 32 #define int_inf 0x3f3f3f3f 33 #define ll_inf 0x7f7f7f7f7f7f7f7f 34 #define lson curPos<<1 35 #define rson curPos<<1|1 36 /* namespace */ 37 using namespace std; 38 /* header end */ 39 40 const int maxn = 2e5 + 10; 41 int n, cntx[maxn], cnty[maxn], cnt1 = 0, cnt2 = 0; 42 ll ans = 0; 43 vector<pair<int, int>>v[maxn]; 44 45 //muban 46 47 struct Rectangle 48 { 49 int x[2], y[2]; 50 void read() 51 { 52 rep0(i, 0, 2) scanf("%d%d", &x[i], &y[i]); 53 if (x[0] > x[1]) swap(x[0], x[1]); 54 if (y[0] > y[1]) swap(y[0], y[1]); 55 cntx[++cnt1] = x[0], cntx[++cnt1] = x[1], cnty[++cnt2] = y[0], cnty[++cnt2] = y[1]; 56 } 57 }; 58 59 struct Node 60 { 61 ll sum, val, lazy; 62 Node() {} 63 Node(ll a, ll b, ll c): sum(a), val(b), lazy(c) {} 64 //maintain 65 Node operator+(const Node &rhs) 66 { 67 return Node(sum + rhs.sum, val + rhs.val, 0); 68 } 69 70 void solve() 71 { 72 val = sum - val; lazy ^= 1; 73 } 74 }; 75 76 Node segt[maxn << 2]; 77 Rectangle r[maxn]; 78 79 void _hash() 80 { 81 sot(cntx, cnt1); sot(cnty, cnt2); 82 cnt1 = unique(cntx + 1, cntx + 1 + cnt1) - cntx - 1, cnt2 = unique(cnty + 1, cnty + 1 + cnt2) - cnty - 1; 83 rep1(i, 1, n) 84 { 85 rep0(j, 0, 2) 86 { 87 r[i].x[j] = lower_bound(cntx + 1, cntx + 1 + cnt1, r[i].x[j]) - cntx; 88 r[i].y[j] = lower_bound(cnty + 1, cnty + 1 + cnt2, r[i].y[j]) - cnty; 89 } 90 } 91 } 92 93 void build(int curPos, int curL, int curR) 94 { 95 segt[curPos] = Node(0, 0, 0); 96 if (curL == curR) 97 { 98 segt[curPos].sum = cnty[curL + 1] - cnty[curL]; 99 return; 100 } 101 int mid = (curL + curR) >> 1; 102 build(lson, curL, mid); build(rson, mid + 1, curR); 103 segt[curPos] = segt[lson] + segt[rson]; 104 } 105 106 void pushdown(int curPos) 107 { 108 if (!segt[curPos].lazy) return; 109 segt[lson].solve(); segt[rson].solve(); segt[curPos].lazy = 0; 110 } 111 112 void update(int curPos, int curL, int curR, int qL, int qR) 113 { 114 if (qL <= curL && curR <= qR) 115 { 116 segt[curPos].solve(); return; 117 } 118 int mid = (curL + curR) >> 1; 119 pushdown(curPos); 120 if (qL <= mid) update(lson, curL, mid, qL, qR); 121 if (qR > mid) update(rson, mid + 1, curR, qL, qR); 122 segt[curPos] = segt[lson] + segt[rson]; 123 } 124 125 int main() 126 { 127 scanf("%d", &n); 128 rep1(i, 1, 2 * n) v[i].clear(); 129 rep1(i, 1, n) r[i].read(); 130 _hash(); 131 rep1(i, 1, n) 132 { 133 v[r[i].x[0]].pb(r[i].y[0], r[i].y[1] - 1); 134 v[r[i].x[1]].pb(r[i].y[0], r[i].y[1] - 1); 135 } 136 n *= 2; 137 build(1, 1, n); 138 rep0(i, 1, cnt1) 139 { 140 for (auto i : v[i]) update(1, 1, n, i.first, i.second); 141 ans += segt[1].val * (cntx[i + 1] - cntx[i]); 142 } 143 printf("%lld ", ans); 144 return 0; 145 }
G：
分类讨论弱智题。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int maxn = 200000; 8 9 double cal(double x, double y, double x1, double y1) 10 { 11 double a = (x1 - x); 12 double b = (y1 - y); 13 return sqrt(a * a + b * b); 14 } 15 16 int main() 17 { 18 double x, y, x1, y1, x2, y2; 19 cin >> x >> y >> x1 >> y1 >> x2 >> y2; 20 double ans = 1e9; 21 if (x1 <= x2) 22 { 23 if (x1 <= x && x <= x2) 24 { 25 ans = min(abs(y1 - y), abs(y2 - y)); 26 } 27 } 28 else 29 { 30 if (x2 <= x && x <= x1) 31 { 32 ans = min(abs(y1 - y), abs(y2 - y)); 33 } 34 } 35 if (y1 <= y2) 36 { 37 if (y1 <= y && y <= y2) 38 { 39 ans = min(abs(x1 - x), abs(x2 - x)); 40 } 41 } 42 else 43 { 44 if (y2 <= y && y <= y1) 45 { 46 ans = min(abs(x1 - x), abs(x2 - x)); 47 } 48 } 49 ans = min(ans, cal(x, y, x1, y1)); 50 ans = min(ans, cal(x, y, x1, y2)); 51 ans = min(ans, cal(x, y, x2, y1)); 52 ans = min(ans, cal(x, y, x2, y2)); 53 printf("%.3lf ", ans); 54 return 0; 55 }
H：
队友跟我说完，我看了一眼范围(n<=1e6)，妥妥的暴力。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int MAXN = 1000000; 8 9 bool check[MAXN + 10]; 10 bool isPrime[MAXN + 10]; 11 int prime[MAXN + 10]; 12 int tot; 13 14 void getPrime(int N = MAXN) 15 { 16 memset(check, false, sizeof(check)); 17 tot = 0; 18 for (int i = 2; i <= N; i++) 19 { 20 if (!check[i]) 21 { 22 prime[tot++] = i; 23 isPrime[i] = true; 24 } 25 for (int j = 0; j < tot; j++) 26 { 27 if (i * prime[j] > N) break; 28 check[i * prime[j]] = true; 29 if (i % prime[j] == 0) break; 30 } 31 } 32 } 33 34 35 int main(void) 36 { 37 getPrime(); 38 int x; 39 scanf("%d", &x); 40 int ans = 0; 41 while (x >= 4) 42 { 43 for (int i = 0; i < tot; i++) 44 { 45 if (isPrime[x - prime[i]]) 46 { 47 int diff = x - 2 * prime[i]; 48 if (diff % 2 == 0) 49 { 50 x = diff; 51 break; 52 } 53 } 54 } 55 ans++; 56 } 57 printf("%d ", ans); 58 return 0; 59 }
I：
cdq分治？不懂。
J：
完全没看题，看队友代码好像又是签到。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 int main(void) 7 { 8 int n, s; 9 scanf("%d %d", &n, &s); 10 int maxi = 0; 11 while (n--) 12 { 13 int t; 14 scanf("%d", &t); 15 maxi = max(maxi, t); 16 } 17 printf("%d ", (maxi * s + 999) / 1000); 18 return 0; 19 }
K：
队友觉得很可写，但是算法一直都是错的。
L：
好像又是傻题。枚举就完事了。
1 #include<cstdio> 2 #include<cstring> 3 4 using namespace std; 5 const int maxn = 200000; 6 struct Node 7 { 8 int a, b; 9 } A[maxn]; 10 11 int main() 12 { 13 int n; 14 scanf("%d", &n); 15 for (int i = 1; i <= n; i++) 16 { 17 scanf("%d%d", &A[i].a, &A[i].b); 18 } 19 for (int ans = n; ans >= 1; ans--) 20 { 21 int tot = 0; 22 for (int i = 1; i <= n; i++) 23 { 24 if (A[i].a <= ans && ans <= A[i].b) 25 { 26 tot++; 27 } 28 29 } 30 if (tot == ans) 31 { 32 printf("%d ", ans); 33 return 0; 34 } 35 } 36 printf("-1 "); 37 38 39 return 0; 40 }
M：
我跟队友都觉得很像是贪心，但是都fake。