CF527C Glass Carving
很简单，直接用SET维护。
#include<bits/stdc++.h> #define its set<int>::iterator #define is mulitset<int>::iterator using namespace std; int w,h,n; multiset<int> sx; multiset<int> sy; set<int> x; set<int> y; inline int read(){ int x = 0; char c = getchar(); while(!isdigit(c)){ c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x; } int main(){ // scanf("%d%d%d", &w, &h, &n); w = read(), h = read(), n = read(); x.insert(0); x.insert(h); y.insert(w); y.insert(0); sx.insert(h); sy.insert(w); for(int i = 1;i <= n; i++){ char c; cin >> c; int p = read(); if(c == 'V'){ y.insert(p); its it,itt; it = y.lower_bound(p); itt = y.upper_bound(p); --it; int ls,rs; ls = p - *it; rs = *itt - p; int ss = *itt - *it; sy.erase(sy.find(ss)); sy.insert(ls); sy.insert(rs); } else{ x.insert(p); its it,itt; it = x.lower_bound(p); itt = x.upper_bound(p); --it; int ls,rs; ls = p - *it; rs = *itt - p; int ss = *itt - *it; sx.erase(sx.find(ss)); sx.insert(rs); sx.insert(ls); } int a,b; a = *(--sx.end()); b = *(--sy.end()); printf("%lld ", (1LL)*a*b); } return 0; }
#include<bits/stdc++.h> using namespace std; #define N 200010 int n; struct node{ int l, r; bool operator < (const node& a) const { if(r != a.r) return r < a.r; else return l < a.l; } } t[N]; int ans=0; int main(){ scanf("%d", &n); for(int i = 1;i <= n;i++){ int a,b; scanf("%d%d", &a, &b); t[i].l = a - b; t[i].r = a + b; } sort(t + 1,t + n + 1); int r= -(~0u >> 1); for(int i = 1;i <= n;i++){ if(t[i].l >= r){ ans++; r = t[i].r; } } printf("%d ", ans); return 0; }
CF140C New Year Snowmen
贪心思想，每次选择数量最多且不重复的三种雪球。
#include <bits/stdc++.h> using namespace std; #define N 1000100 #define ll long long #define isdigit(c) ((c)>='0'&&(c)<='9') int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } map <int, int> a; struct node{ int w, cnt; bool operator < (const node& a) const{ return cnt < a.cnt || (cnt == a.cnt && w > a.w); } } t[N]; priority_queue <node> q; struct answer{ int a, b, c; } ans[N]; inline void swap1(node& a, node& b){ node temp = a; a = b; b = temp; return ; } int main(){ int n = read(); int k = 0, maxn = -6666; int temp = 0; for(int i = 1;i <= n; i++){ int x = read(); if(a[x]) t[a[x]].cnt++; else { a[x] = ++temp; t[a[x]].cnt++; t[a[x]].w = x; maxn = max(a[x], maxn); } } for(int i = 1;i <= temp; i++) q.push(t[i]); while(q.size() >= 3){ node x = q.top(); q.pop(); node y = q.top(); q.pop(); node z = q.top(); q.pop(); x.cnt--; y.cnt--; z.cnt--; if(y.w < z.w) swap1(z, y); if(x.w < z.w) swap1(x, z); if(x.w < y.w) swap1(y, x); ans[++k] = (answer){x.w, y.w, z.w}; if(x.cnt) q.push(x); if(y.cnt) q.push(y); if(z.cnt) q.push(z); } printf("%d ", k); for(int i = 1;i <= k; i++) printf("%d %d %d ", ans[i].a, ans[i].b, ans[i].c); return 0; }
CF650A Watchmen
两种距离相等时，横坐标或者纵坐标一定相等。
#include <bits/stdc++.h> using namespace std; #define N 1000100 #define ll long long #define isdigit(c) ((c)>='0'&&(c)<='9') int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } struct node{ int x, y; bool operator < (const node& a) const{ return x < a.x || (x == a.x && y < a.y); } } t[N]; map <int , ll> a; map <int , ll> b; map <node, int> q; int main(){ int n = read(); ll ans = 0; ll temp1 = 0, temp2 = 0; for(int i = 1;i <= n; i++){ int x = read(), y = read(); t[i] = (node){x, y}; if(q[t[i]]) ans -= q[t[i]]; q[t[i]]++; ans += a[x]; ans += b[y]; a[x]++; b[y]++; } printf("%lld ", ans); return 0; } /* 第二种写法 （不推荐） #include <bits/stdc++.h> using namespace std; #define N 1000100 #define ll long long int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } struct node{ int x, y; bool operator < (const node& a) const{ return x < a.x || (x == a.x && y < a.y); } } t[N]; map <int , ll> a; map <int , ll> b; map <node, int> q; ll cntx[N], cnty[N]; int main(){ int n = read(); ll ans = 0; ll temp1 = 0, temp2 = 0; for(int i = 1;i <= n; i++){ int x = read(), y = read(); t[i] = (node){x, y}; if(q[t[i]]) ans -= q[t[i]]; q[t[i]]++; if(!a[x]) a[x] = ++temp1; if(!b[y]) b[y] = ++temp2; ans += cntx[a[x]]; ans += cnty[b[y]]; cntx[a[x]]++; cnty[b[y]]++; } printf("%lld ", ans); return 0; } */
CF466C Number of Ways
直接前缀和处理，然后一遍扫描，到达1/3 或者 2/3的时候进行操作。
#include <bits/stdc++.h> using namespace std; #define N 1000010 #define ll long long ll read(){ ll x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } ll sum[N]; int main(){ int n = read(); for(int i = 1;i <= n; i++){ ll x = read(); sum[i] = sum[i - 1] + x; } ll temp = 0, ans = 0; for(int i = 1;i <= n; i++){ if(i > 1 && i < n && sum[i] == sum[n] * 2 / 3) ans += temp; if(sum[i] == sum[n] / 3) temp++; } if(sum[n] % 3 != 0){ putchar('0'); } else printf("%lld ", ans); return 0; }
二分操作
#include <bits/stdc++.h> using namespace std; #define N 1000010 #define ll long long ll read(){ ll x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x * s; } ll dis[N]; /*差分数组*/ ll n, m, w; ll a[N]; bool check(ll now){ ll temp = 0, sum = 0; for(int i = 1;i <= n; i++){ temp += dis[i]; if(temp < now){ sum += now - temp; dis[i] += now - temp; if(i + w <= n) dis[i + w] -= now - temp; temp += now - temp; } } return sum <= m; } int main(){ n = read(), m = read(), w = read(); ll l = (~0u >> 1), r = -666; for(int i = 1;i <= n; i++){ a[i] = read(); dis[i] = a[i] - a[i - 1]; l = min(l, a[i]); r = max(r, a[i]); } r += m + 1; while(l < r - 1){ ll mid = l + r >> 1; if(check(mid)) l = mid; else r = mid; for(int i = 1;i <= n; i++) dis[i] = a[i] - a[i - 1]; } printf("%lld ", l); return 0; }