按时间倒着dp
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 typedef pair<LL, LL> pii; 5 const int maxn = 2e6 + 10; 6 int u[maxn], v[maxn]; 7 LL st[maxn], ed[maxn]; 8 double p[maxn]; 9 vector<pii> vec; 10 map<LL, double> f[maxn]; 11 map<LL, double> :: iterator it; 12 vector<int> G[maxn]; 13 14 int main(){ 15 int m, n; 16 LL k; 17 scanf("%d %d %lld", &m, &n, &k); 18 for(int i = 1; i <= m; ++i){ 19 scanf("%d %d %lld %lld %lf", u + i, v + i, st + i, ed + i, p + i); 20 if(u[i] == 1 || ed[i] > k) {m--; i--; continue;} 21 vec.push_back(pii(st[i], u[i])); 22 vec.push_back(pii(ed[i], v[i])); 23 } 24 vec.push_back(pii(k + 1, 1)); 25 sort(vec.begin(), vec.end()); 26 vec.erase(unique(vec.begin(), vec.end()), vec.end()); 27 for(int i = 1; i <= m; ++i){ 28 int x = lower_bound(vec.begin(), vec.end(), pii(st[i], u[i])) - vec.begin(); 29 G[x].push_back(i); 30 } 31 for(int i = vec.size() - 1; i >= 0; i--){ 32 int x = vec[i].second; 33 LL now = vec[i].first; 34 double pre = x == 1 ? 1 : 0; 35 if(x != 1){ 36 it = f[x].upper_bound(now); 37 if(it != f[x].end()) pre = (*it).second; 38 } 39 double M = pre; 40 for(int j = 0; j < G[i].size(); ++j){ 41 int y = G[i][j]; 42 it = f[v[y]].upper_bound(ed[y]); 43 if(it == f[v[y]].end()) continue; 44 M = max(M, p[y] * (*it).second + (1 - p[y]) * pre); 45 } 46 f[x][now] = M; 47 } 48 it = f[0].begin(); 49 printf("%.10f\n", (*it).second); 50 return 0; 51 }
扫一圈
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 2e6 + 10; 4 int R[maxn][2], mp[maxn]; 5 vector<int> v; 6 int n, w, h, op[maxn], sz; 7 8 int M[maxn<<2], tag[maxn<<2]; 9 inline void gather(int p) 10 { 11 M[p] = max(M[p<<1], M[p<<1|1]); 12 } 13 inline void push(int p) 14 { 15 if(tag[p]) 16 { 17 tag[p<<1] += tag[p]; 18 tag[p<<1|1] += tag[p]; 19 M[p<<1] += tag[p]; 20 M[p<<1|1] += tag[p]; 21 tag[p] = 0; 22 } 23 } 24 void modify(int p, int tl, int tr, int l, int r, int v) 25 { 26 if(tl > tr) return; 27 if(tr < l || r < tl) return; 28 if(l <= tl && tr <= r) 29 { 30 tag[p] += v; 31 M[p] += v; 32 return; 33 } 34 push(p); 35 int mid = (tl + tr) >> 1; 36 modify(p<<1, tl, mid, l, r, v); 37 modify(p<<1|1, mid+1, tr, l, r, v); 38 gather(p); 39 } 40 int query(int p, int tl, int tr) 41 { 42 if(tl == tr) return tl; 43 push(p); 44 int mid = (tl + tr) >> 1; 45 if(M[p<<1] == n) return query(p << 1, tl, mid); 46 return query(p << 1 | 1, mid + 1, tr); 47 } 48 inline void update(int x, int y){ 49 int l, r; 50 if(op[x] == 0){ 51 l = R[x][0] + 2; 52 r = R[x][1] + 1; 53 modify(1, 1, sz + 1, l, r, y); 54 } 55 else{ 56 l = 1; 57 r = R[x][0] + 1; 58 modify(1, 1, sz + 1, l, r, y); 59 l = R[x][1] + 2; 60 r = sz + 1; 61 modify(1, 1, sz + 1, l, r, y); 62 } 63 } 64 65 void print(double x){ 66 if(x <= w) printf("%f %f", x, 0.0); 67 else if(x <= w + h) printf("%f %f", 1.0 * w, x - w); 68 else if(x <= w + w + h) printf("%f %f", w + w + h - x, 1.0 * h); 69 else printf("%f %f", 0.0, w + w + h + h - x); 70 } 71 double nxt_e(double x){ 72 if(x <= w) return w + 0.5; 73 if(x <= w + h) return w + h + 0.5; 74 if(x <= w + w + h) return w + w + h + 0.5; 75 return 0.5; 76 } 77 78 int main(){ 79 scanf("%d %d %d", &n, &w, &h); 80 sz = n + n; 81 for(int i = 1; i <= n; ++i){ 82 int X1, X2, Y1, Y2, S1, S2; 83 scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2); 84 if(Y1 == 0) S1 = X1; 85 else if(X1 == w) S1 = w + Y1; 86 else if(Y1 == h) S1 = w + h + (w - X1); 87 else S1 = w + w + h + (h - Y1); 88 if(Y2 == 0) S2 = X2; 89 else if(X2 == w) S2 = w + Y2; 90 else if(Y2 == h) S2 = w + h + (w - X2); 91 else S2 = w + w + h + (h - Y2); 92 if(S2 < S1) swap(S1, S2); 93 v.emplace_back(S1); 94 v.emplace_back(S2); 95 R[i][0] = S1; 96 R[i][1] = S2; 97 } 98 sort(v.begin(), v.end()); 99 for(int i = 1; i <= n; ++i){ 100 R[i][0] = lower_bound(v.begin(), v.end(), R[i][0]) - v.begin(); 101 R[i][1] = lower_bound(v.begin(), v.end(), R[i][1]) - v.begin(); 102 mp[R[i][0]] = mp[R[i][1]] = i; 103 } 104 for(int i = 1; i <= n; ++i) update(i, 1); 105 int ok = 0; 106 double now = w + w + h + h - 0.5; 107 for(int i = 0; i < sz; ++i){ 108 if(M[1] == n){ 109 int x = query(1, 1, sz + 1); 110 double nxt = max((x == 1 ? 0 : v[x-2]) + 0.5, nxt_e(now)); 111 puts("1"); 112 print(now); 113 putchar(' '); 114 print(nxt); 115 puts(""); 116 ok = 1; 117 break; 118 } 119 now = v[i] + 0.5; 120 update(mp[i], -1); 121 op[mp[i]] ^= 1; 122 update(mp[i], 1); 123 } 124 if(!ok) printf("2\n0.5 0.0 %f %f\n%f 0.0 0.5 %f\n", w - 0.5, 1.0 * h, w - 0.5, 1.0 * h); 125 return 0; 126 }
瞎比统计
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 int l[3333][6666], lu[3333][6666], ld[3333][6666]; 5 string G[6666]; 6 7 int c[3333][6666]; 8 void cl(){ 9 memset(c, 0, sizeof(c)); 10 } 11 int lowbit(int s) { 12 return s & (-s); 13 } 14 void modify(int op, int i, int x) { 15 while(i < 6666) c[op][i] += x, i += lowbit(i); 16 return; 17 } 18 int query(int op, int i) { 19 int ret = 0; 20 while(i > 0) ret += c[op][i], i -= lowbit(i); 21 return ret; 22 } 23 24 25 int main(){ 26 ios::sync_with_stdio(0); 27 cin.tie(0); 28 29 int r, c; 30 cin >> r >> c; 31 for(int i = 0; i <= r + r - 1; ++i) getline(cin, G[i]); 32 if(r % 2 == 0) r++; 33 for(int i = 0; i <= r + r - 1; ++i){ 34 while(G[i].length() < c + c) G[i] = G[i] + ' '; 35 } 36 37 for(int i = 1, x = 1; i <= r; i++, x += 2) { 38 for(int j = i % 2 ? 1 : 2, y = j + j - 2; j <= c; j += 2, y += 4){ 39 l[i][j] = lu[i][j] = 1; 40 if(j > 2 && G[x][y-1] == '-') l[i][j] = l[i][j-2] + 1; 41 if(i > 1 && j > 1 && G[x-1][y-1] == '\\') lu[i][j] = lu[i-1][j-1] + 1; 42 } 43 } 44 for(int i = r, x = i + i - 1; i >= 1; i--, x -= 2) { 45 for(int j = i % 2 ? 1 : 2, y = j + j - 2; j <= c; j += 2, y += 4){ 46 ld[i][j] = 1; 47 if(i < r && j > 1 && G[x+1][y-1] == '/') ld[i][j] = ld[i+1][j-1] + 1; 48 } 49 } 50 51 LL ans = 0; 52 for(int j = (r + c) % 2 ? c - 1 : c; j >= 1; j -= 2){ 53 for(int i = r; i >= 1 && j + r - i <= c; i--){ 54 int jj = j + (r - i); 55 int m = min(l[i][jj], ld[i][jj]) - 1; 56 ans += query(i, jj - 1) - query(i, jj - m - m - 1); 57 if(i == r || jj == c || lu[i+1][jj+1] == 1){ 58 for(int k = 1; k < lu[i][jj]; k++){ 59 int ni = i - k, nj = jj - k; 60 modify(ni, nj, 1); 61 } 62 } 63 } 64 } 65 for(int i = r - 1 - r % 2; i >= 1; i -= 2){ 66 for(int j = 1; j <= c && i - j + 1 >= 1; j++){ 67 int ii = i - (j - 1); 68 int m = min(l[ii][j], ld[ii][j]) - 1; 69 ans += query(ii, j - 1) - query(ii, j - m - m - 1); 70 if(ii == r || j == c || lu[ii+1][j+1] == 1){ 71 for(int k = 1; k < lu[ii][j]; k++){ 72 int ni = ii - k, nj = j - k; 73 modify(ni, nj, 1); 74 } 75 } 76 } 77 } 78 79 for(int i = 1; i < r; ++i) swap(G[i], G[r+r-i]); 80 for(int i = 1; i <= r + r - 1; ++i){ 81 for(int j = 0; j < G[i].length(); ++j){ 82 if(G[i][j] == '/') G[i][j] = '\\'; 83 else if(G[i][j] == '\\') G[i][j] = '/'; 84 } 85 } 86 cl(); 87 88 for(int i = 1, x = 1; i <= r; i++, x += 2) { 89 for(int j = i % 2 ? 1 : 2, y = j + j - 2; j <= c; j += 2, y += 4){ 90 l[i][j] = lu[i][j] = 1; 91 if(j > 2 && G[x][y-1] == '-') l[i][j] = l[i][j-2] + 1; 92 if(i > 1 && j > 1 && G[x-1][y-1] == '\\') lu[i][j] = lu[i-1][j-1] + 1; 93 } 94 } 95 for(int i = r, x = i + i - 1; i >= 1; i--, x -= 2) { 96 for(int j = i % 2 ? 1 : 2, y = j + j - 2; j <= c; j += 2, y += 4){ 97 ld[i][j] = 1; 98 if(i < r && j > 1 && G[x+1][y-1] == '/') ld[i][j] = ld[i+1][j-1] + 1; 99 } 100 } 101 102 for(int j = (r + c) % 2 ? c - 1 : c; j >= 1; j -= 2){ 103 for(int i = r; i >= 1 && j + r - i <= c; i--){ 104 int jj = j + (r - i); 105 int m = min(l[i][jj], ld[i][jj]) - 1; 106 ans += query(i, jj - 1) - query(i, jj - m - m - 1); 107 if(i == r || jj == c || lu[i+1][jj+1] == 1){ 108 for(int k = 1; k < lu[i][jj]; k++){ 109 int ni = i - k, nj = jj - k; 110 modify(ni, nj, 1); 111 } 112 } 113 } 114 } 115 for(int i = r - 1 - r % 2; i >= 1; i -= 2){ 116 for(int j = 1; j <= c && i - j + 1 >= 1; j++){ 117 int ii = i - (j - 1); 118 int m = min(l[ii][j], ld[ii][j]) - 1; 119 ans += query(ii, j - 1) - query(ii, j - m - m - 1); 120 if(ii == r || j == c || lu[ii+1][j+1] == 1){ 121 for(int k = 1; k < lu[ii][j]; k++){ 122 int ni = ii - k, nj = j - k; 123 modify(ni, nj, 1); 124 } 125 } 126 } 127 } 128 129 cout << ans << endl; 130 return 0; 131 }
贪心
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e4 + 10; 4 typedef pair<int, int> pii; 5 vector<int> v, o; 6 int deg[maxn]; 7 bool cmp(int i, int j){return deg[i] < deg[j];} 8 vector<pii> G; 9 10 int main(){ 11 int n, m, cnt = 0; 12 scanf("%d %d", &n, &m); 13 for(int i = 1; i <= n; ++i) v.push_back(i); 14 for(int i = 1; i <= m; ++i){ 15 int a, b; 16 scanf("%d %d", &a, &b); 17 a++, b++; 18 deg[a]++, deg[b]++; 19 } 20 sort(v.begin(), v.end(), cmp); 21 int ed = n; 22 for(int i = 0; i < ed; ++i) { 23 int x = v[i]; 24 if(deg[x] == 1){ 25 o.push_back(x); 26 cnt++; 27 } 28 else if(o.size() >= deg[x] - 1){ 29 for(int j = 0; j < deg[x] - 1; ++j){ 30 int y = o[o.size()-1]; 31 G.push_back(pii(x, y)); 32 o.pop_back(); 33 } 34 o.push_back(x); 35 cnt++; 36 } 37 else if(o.size() + ed - i - 1 >= deg[x] - 1){ 38 for(int j = 0; j < o.size(); ++j){ 39 int y = o[j]; 40 G.push_back(pii(x, y)); 41 } 42 for(int j = 0; j < deg[x] - 1 - o.size(); ++j){ 43 G.push_back(pii(x, v[--ed])); 44 } 45 o.clear(); 46 o.push_back(x); 47 cnt++; 48 } 49 else { 50 for(int j = 0; j < o.size(); ++j) G.push_back(pii(x, o[j])); 51 for(int j = i + 1; j < ed; ++j) G.push_back(pii(x, v[j])); 52 o.clear(); 53 break; 54 } 55 } 56 if(o.size() > 0){ 57 if(o.size() != 2) cnt--; 58 for(int i = 1; i < o.size(); ++i) G.push_back(pii(o[0], o[i])); 59 } 60 printf("%d\n%d %d\n", n - cnt, n, n - 1); 61 for(int i = 0; i < G.size(); ++i) printf("%d %d\n", G[i].first - 1, G[i].second - 1); 62 return 0; 63 }