2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure
做出大小两个凸包，即所有点的凸包和前 k 个点的凸包
按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间
相当于切掉凸包的一个角，加入一个三角形
若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳
切掉部分的面积顺便维护
由于坐标范围较大，用 double 精度会炸
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 #define L(x) (x == 1?tops : x - 1) #define R(x) (x == tops?1 : x + 1) using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, cnt, top, tops; ll sqr(ll x) { return x*x; } struct P{ ll x,y; P(ll _x=0,ll _y=0){x=_x;y=_y;} friend P operator-(P a,P b){ return P(a.x-b.x,a.y-b.y); } friend ll operator*(P a,P b){ return a.x*b.y-a.y*b.x; } friend bool operator<(P a,P b){ if(fabs(a.y-b.y)<0)return a.x<b.x; return a.y<b.y; } friend ll dis2(P a){ return sqr(a.x)+sqr(a.y); } }p[100005], q[100005], qs[100005]; bool cmp(P a,P b) { if(fabs((a-p[1])*(b-p[1]))<0)return dis2(p[1]-a)<dis2(p[1]-b); return (a-p[1])*(b-p[1])>0; } bool cmp2(P a, P b) { if(fabs((a - q[1]) * (b - q[1])) < 0) return dis2(a - q[1]) < dis2(b - q[1]); return (a - q[1]) * (b - q[1]) > 0; } void graham() { top = 0; for(int i=1;i<=cnt;i++) if(p[i]<p[1])swap(p[i],p[1]); sort(p+2,p+cnt+1,cmp); for(int i=1;i<=cnt;i++) { while(top>1&&(q[top]-q[top-1])*(p[i]-q[top-1])<=0) top--; q[++top]=p[i]; } } ll solve() { ll S = 0; qs[tops + 1] = qs[1]; for(int i = 1; i <= tops; i++) S += qs[i] * qs[i + 1]; ll ans = S; int l = 1, r = 1; ll tmp = 0; while((qs[l] - q[1]) * (qs[L(l)] - q[1]) >= 0) { tmp -= (qs[l] - qs[r]) * (qs[L(l)] - qs[l]); l = L(l); } for(int i = 1; i <= top; i++) { while((qs[r] - q[i]) * (qs[R(r)] - q[i]) <= 0) { tmp += (qs[r] - qs[l]) * (qs[R(r)] - qs[l]); r = R(r); } while((qs[R(l)] - q[i]) * (qs[l] - q[i]) < 0) { tmp += (qs[R(l)] - qs[r]) * (qs[l] - qs[r]); l = R(l); } ans = max(ans, S - tmp + (qs[r] - q[i]) * (qs[l] - q[i])); } return ans; } int main() { n = read(); m = read(); cnt = m; for(int i = 1; i <= n; i++) p[i].x = read(), p[i].y = read(); graham(); for(int i = 1; i <= top; i++) qs[i].x = q[i].x, qs[i].y = q[i].y; tops = top; cnt = n; graham(); ll ans = solve(); printf("%lld", ans / 2); if(ans & 1)puts(".5"); else puts(".0"); return 0; } |
G.Maximum Islands
L 的上下左右直接贪心为 W
然后剩下的就是个经典的骑士共存问题，黑白染色最小割
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int cnt = 1, ans, c1, c2; int n, m, ind, T; int id[45][45]; string a[45]; int xx[4] = {1, -1, 0, 0}, yy[4] = {0, 0, 1, -1}; struct edge{ int to, next, v; }e[10000005]; int last[2005],dis[2005],q[2005],h[2005],cur[2005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } bool bfs() { int head=0,tail=1; for(int i=0;i<=T;i++)h[i]=-1; q[0]=0;h[0]=0; while(head!=tail) { int x=q[head];head++; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==-1&&e[i].v) { h[e[i].to]=h[x]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[x]+1==h[e[i].to]&&e[i].v) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; if(e[i].v)cur[x]=i; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void addw(int i, int j) { for(int k = 0; k < 4; k++) { int x = i + xx[k], y = j + yy[k]; if(x < 1 || y < 1 || x > n || y > m)continue; if(a[x][y] == 'C')a[x][y] = 'W'; } } void dfs2(int x, int y) { if(x < 1 || y < 1 || x > n || y > m || a[x][y] != 'L')return; a[x][y] = 'W'; for(int i = 0; i < 4; i++) dfs2(x + xx[i], y + yy[i]); } int main() { n = read(); m = read(); for(int i = 1; i <= n; i++) { cin >> a[i]; a[i] = ' ' + a[i]; } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == 'L') addw(i, j); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == 'L') { ans++; dfs2(i, j); } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) id[i][j] = ++ind; T = ind + 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == 'C') { ans++; int u = id[i][j]; if(((i + j) & 1)) { insert(0, u, 1); for(int k = 0; k < 4; k++) { int x = i + xx[k], y = j + yy[k]; if(x < 1 || y < 1 || x > n || y > m || a[x][y] == 'W')continue; int v = id[x][y]; insert(u, v, inf); } } else insert(u, T, 1); } while(bfs()) { for(int i=0;i<=T;i++)cur[i]=last[i]; ans-=dfs(0,inf); } printf("%d\n", ans); return 0; } |
H.Paint
离散化，f(i)表示考虑前 i 个段，最多能染多少
将区间按照右端点排序后树状数组优化 dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n, K; ll t[400005], H[400005]; struct data{ ll l, r; }a[200005]; bool cmp(data a, data b) { return a.r < b.r; } void modify(int x, ll v) { for(int i = x; i <= 2 * K; i += i & -i) t[i] = max(t[i], v); } ll query(int x) { if(x == 0)return 0; ll ans = 0; for(int i = x; i; i -= i & -i) ans = max(ans, t[i]); return ans; } int main() { n = read(); K = read(); for(int i = 1; i <= K; i++) { a[i].l = read(), a[i].r = read(); H[2 * i - 1] = a[i].l; H[2 * i] = a[i].r; } sort(H + 1, H + 2 * K + 1); sort(a + 1, a + K + 1, cmp); for(int i = 1; i <= K; i++) { a[i].l = lower_bound(H + 1, H + 2 * K + 1, a[i].l) - H; a[i].r = lower_bound(H + 1, H + 2 * K + 1, a[i].r) - H; } ll ans = 0; for(int i = 1; i <= K; i++) { ll x = query(a[i].l - 1); x += H[a[i].r] - H[a[i].l] + 1; ans = max(ans, x); modify(a[i].r, x); } cout << n - ans << endl; return 0; } |
J.Shopping
从左端点开始，设剩下的钱为 S，每次二分 + rmq找到之后第一个小等于 S 的物品
由于 S 每次减半，复杂度 \(O(30nlogn)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, q; int Log[200005]; ll a[200005], f[18][200005]; ll query(int l, int r) { int t = Log[r - l + 1]; return min(f[t][l], f[t][r - (1 << t) + 1]); } ll solve(ll S, int l, int r) { int k = l; while(k <= r) { S = S % a[k]; k++; int tmp = k; int L = tmp, R = r; k = r + 1; while(L <= R) { int MID = (L + R) >> 1; if(query(tmp, MID) > S)L = MID + 1; else R = MID - 1, k = MID; } } return S; } int main() { Log[0] = -1; for(int i = 1; i <= 200000; i++) Log[i] = Log[i >> 1] + 1; n = read(), q = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 0; i <= 17; i++) for(int j = 1; j + (1 << i) - 1 <= n; j++) if(i == 0)f[i][j] = a[j]; else f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]); for(int i = 1; i <= q; i++) { ll S = read(), l = read(), r = read(); printf("%lld\n", solve(S, l, r)); } return 0; } |
Subscribe
计数器 9774197
OI 课件=>
OI 课件=>