CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » farmer_john » jjleo » 2020.05.16-2020.05.22
2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/05/22 22:12]
jjleo [CF455D] 		2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/06/25 23:06] (当前版本)
jjleo ↷ 页面2020-2021:teams:farmer_john:2020.05.16-2020.05.22被移动至2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22
行 76: 行 76:
  printf("​%d",​ f[1][1]); ​  printf("​%d",​ f[1][1]); ​
 } </​code></​hidden>​ } </​code></​hidden>​
-=====CF455D===== +=====CF300D===== 
-卷积dp+卷积dp。
 <​hidden><​code cpp>#​include <​bits/​stdc++.h>​ <​hidden><​code cpp>#​include <​bits/​stdc++.h>​
 #define maxn 1086 #define maxn 1086
行 112: 行 112:
 }</​code></​hidden>​ }</​code></​hidden>​
 =====CF319C===== =====CF319C=====
-<​hidden><​code cpp></​code></​hidden>​+斜率优化。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 +#define maxn 100086 
 +using namespace std; 
 + 
 +typedef long long ll; 
 + 
 +int n; 
 +ll a[maxn], b[maxn], f[maxn]; 
 +int q[maxn], l, r; 
 + 
 +inline double k(int i, int j){ 
 + return 1.0 * (f[i] - f[j]) / (b[j] - b[i]); 
 +} 
 + 
 +int main(){ 
 + scanf("​%d",​ &n); 
 + for(int i = 1;i <= n;i++) scanf("​%lld",​ &​a[i]);​ 
 + for(int i = 1;i <= n;i++) scanf("​%lld",​ &​b[i]);​ 
 + f[1] = 0, q[0] = 1; 
 + for(int i = 2;i <= n;i++){ 
 + while(l < r && k(q[l], q[l + 1]) <= a[i]) ++l; 
 + f[i] = f[q[l]] + a[i] * b[q[l]]; 
 + //​printf("​%d %d %lld--\n",​ i, q[l], f[i]); 
 + while(l < r && k(q[r], q[r - 1]) >= k(q[r], i)) --r; 
 + q[++r] = i; 
 + } 
 + printf("​%lld",​ f[n]); 
 +}</​code></​hidden>​ 
 +=====CF455D===== 
 +数据结构，分块+deque。 
 +<​hidden><​code cpp>#​include <​bits/​stdc++.h>​ 
 +#define maxn 100086 
 +#define maxm 320 
 +using namespace std; 
 + 
 +int f[maxm][maxn];​ 
 +int n, sn; 
 +int opt, l, r, k; 
 +int m, x; 
 +deque<​int>​ q[maxm]; 
 +int lastans; 
 + 
 +int main(){ 
 + scanf("​%d",​ &n), sn = (int)sqrt(n);​ 
 + for(int i = 1;i <= n;i++){ 
 + scanf("​%d",​ &x); 
 + int ii = (i - 1) / sn; 
 + q[ii].push_back(x),​ ++f[ii][x];​ 
 + } 
 + scanf("​%d",​ &m); 
 + while(m--){ 
 + scanf("​%d",​ &​opt);​ 
 + if(opt == 1){ 
 + scanf("​%d%d",​ &l, &r); 
 + l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1; 
 + if(l > r) swap(l, r); 
 + int ll = (l - 1) / sn, rr = (r - 1) / sn, li = (l - 1) % sn, ri = (r - 1) % sn; 
 + //​printf("​%d %d %d %d--\n",​ ll, rr, li, ri); 
 + if(ll == rr){ 
 + int x = q[ll][ri];​ 
 + q[ll].erase(q[ll].begin() + ri); 
 + q[ll].insert(q[ll].begin() + li, x); 
 + }else{ 
 + int x = q[ll].back();​q[ll].pop_back(),​ --f[ll][x];​ 
 + for(int i = ll + 1;i < rr;i++){ 
 + q[i].push_front(x),​ ++f[i][x];​ 
 + x = q[i].back(),​ q[i].pop_back(),​ --f[i][x];​ 
 + } 
 + q[rr].push_front(x),​ ++f[rr][x];​ 
 + x = q[rr][ri + 1], --f[rr][x], q[rr].erase(q[rr].begin() + ri + 1);//​debug:​已经pushfront了所以下标都要+1  
 + ++f[ll][x],​ q[ll].insert(q[ll].begin() + li, x); 
 + } 
 + }else{ 
 + scanf("​%d%d%d",​ &l, &r, &k); 
 + l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1, k = (k + lastans - 1) % n + 1; 
 + if(l > r) swap(l, r); 
 + int ll = (l - 1) / sn, rr = (r - 1) / sn, li = (l - 1) % sn, ri = (r - 1) % sn; 
 + int ans = 0; 
 + if(ll == rr){ 
 + for(int i = li;i <= ri;i++) ans += q[ll][i] == k;  
 + }else{ 
 + for(int i = ll + 1;i < rr;i++) ans += f[i][k]; 
 + //​printf("​%d %d %d %d--\n",​ ll, rr, li, ri); 
 + for(int i = li;i < sn;i++) ans += q[ll][i] == k;  
 + for(int i = 0;i <= ri;i++) ans += q[rr][i] == k;  
 + } 
 + printf("​%d\n",​ lastans = ans); 
 + } 
 + } 
 +}</​code></​hidden>​
 =====CF383E===== =====CF383E=====
-<​hidden><​code cpp></​code></​hidden>​+容斥dp+高维前缀和。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 + 
 +using namespace std; 
 + 
 +int n; 
 +int f[1 << 25]; 
 +char s[233]; 
 +int ans; 
 + 
 +int main(){ 
 + scanf("​%d",​ &n); 
 + for(int i = 1;i <= n;i++){ 
 + scanf("​%s",​ s + 1); 
 + int x = 0; 
 + for(int j = 1;j <= 3;j++){ 
 + x |= 1 << (s[j] - '​a'​);​ 
 + } 
 + for(int j = x;j;j = (j - 1) & x){ 
 + if(__builtin_popcount(j) & 1) f[j]++; 
 + else f[j]--; 
 + } 
 + } 
 + for(int i=0;​i<​24;​i++) 
 + for(int j=0;​j<​(1<<​24);​j++) 
 + if(j&​(1<<​i))f[j]+=f[j^(1<<​i)];​ 
 + for(int i=0;​i<​(1<<​24);​i++) 
 + ans=ans^(f[i]*f[i]);​ 
 + printf("​%d",​ ans); 
 +}</​code></​hidden>​
 =====CF1045G===== =====CF1045G=====
-<​hidden><​code cpp></​code></​hidden>​+思维+二维数点。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 +#define maxn 100086 
 +using namespace std; 
 + 
 +struct Node{ 
 + int son[2], val, pri, siz; 
 +}t[maxn]; 
 + 
 +int cnt; 
 +int root[maxn];​ 
 + 
 + 
 +inline int rand() 
 +{ 
 +    static int seed=12345;​ 
 +    return seed=(int)seed*482711LL%2147483647;​ 
 +} 
 + 
 +inline int ls(int x){ 
 + return t[x].son[0];​ 
 +} 
 + 
 +inline int rs(int x){ 
 + return t[x].son[1];​ 
 +} 
 + 
 +void up(int x){ 
 + t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1; 
 +} 
 + 
 +int newnode(int val){ 
 + cnt++; 
 + t[cnt].val = val; 
 + t[cnt].pri = rand(); 
 + t[cnt].siz = 1; 
 + return cnt; 
 +} 
 + 
 +void split(int x, int val, int &a, int &​b){//​x起始 val权值 a b为两个根编号  
 + if(!x){ 
 + a = b = 0; 
 + return; 
 + } 
 + if(t[x].val <= val) a = x, split(rs(x),​ val, t[x].son[1],​ b); 
 + else b = x, split(ls(x),​ val, a, t[x].son[0]);​ 
 + up(x); 
 +}  
 + 
 +int merge(int x, int y){//​返回根编号  
 + if(x == 0 || y == 0) return x + y; 
 + if(t[x].pri > t[y].pri){ 
 + t[x].son[1] = merge(rs(x),​ y); 
 + up(x); 
 + return x; 
 + }else{ 
 + t[y].son[0] = merge(x, ls(y)); 
 + up(y); 
 + return y; 
 + } 
 +}  
 + 
 +int n, k; 
 + 
 +struct N{ 
 + int x, r, q; 
 +}a[maxn]; 
 + 
 +inline bool cmp(N x, N y){ 
 + return x.r > y.r; 
 +} 
 + 
 +long long ans; 
 + 
 +int b[maxn], n0; 
 +int A, B, C, D; 
 + 
 +int main(){ 
 + scanf("​%d%d",​ &n, &k); 
 + for(int i = 1;i <= n;i++) scanf("​%d%d%d",​ &​a[i].x,​ &​a[i].r,​ &​a[i].q),​ b[i] = a[i].q; 
 + sort(a + 1, a + 1 + n, cmp);  
 + sort(b + 1, b + 1 + n); 
 + n0 = unique(b + 1, b + 1 + n) - (b + 1); 
 + for(int i = 1;i <= n;i++){ 
 + int x = lower_bound(b + 1, b + 1 + n0, a[i].q) - b; 
 + for(int j = x;j <= n0 && b[j] - b[x] <= k;j++){ 
 + split(root[j],​ a[i].x - a[i].r - 1, A, B); 
 + split(B, a[i].x + a[i].r, C, D); 
 + ans += t[C].siz; 
 + root[j] = merge(A, merge(C, D)); 
 + } 
 + for(int j = x - 1;j && b[x] - b[j] <= k;j--){ 
 + split(root[j],​ a[i].x - a[i].r - 1, A, B); 
 + split(B, a[i].x + a[i].r, C, D); 
 + ans += t[C].siz; 
 + root[j] = merge(A, merge(C, D)); 
 + } 
 + split(root[x],​ a[i].x, A, B); 
 + root[x] = merge(A, merge(newnode(a[i].x),​ B)); 
 + } 
 + printf("​%lld",​ ans); 
 +}</​code></​hidden>​
 =====CF797D===== =====CF797D=====
-<​hidden><​code cpp></​code></​hidden>​+思维+二叉搜索树。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 +#define maxn 100086 
 +using namespace std; 
 + 
 +int n; 
 +int val[maxn];​ 
 +int son[maxn][2];​ 
 +bool tag[maxn];​ 
 + 
 +map<int, bool> mp; 
 +int ans; 
 + 
 +void dfs(int x, int l, int r){ 
 + if(val[x] < l && r < val[x]) mp[val[x]] = true; 
 + if(son[x][0] != -1) dfs(son[x][0],​ min(l, val[x]), r); 
 + if(son[x][1] != -1) dfs(son[x][1],​ l, max(r, val[x])); 
 +} 
 + 
 +int main(){ 
 + scanf("​%d",​ &n); 
 + for(int i = 1;i <= n;i++){ 
 + scanf("​%d%d%d",​ &​val[i],​ &​son[i][0],​ &​son[i][1]);​ 
 + if(son[i][0] != -1) tag[son[i][0]] = true; 
 + if(son[i][1] != -1) tag[son[i][1]] = true; 
 + } 
 + for(int i = 1;i <= n;i++){ 
 + if(!tag[i]){ 
 + dfs(i, 1e9 + 1, -1); 
 + break; 
 + } 
 + } 
 + for(int i = 1;i <= n;i++) if(!mp[val[i]]) ans++; 
 + printf("​%d",​ ans); 
 +}</​code></​hidden>​
 =====CF979D===== =====CF979D=====
-<​hidden><​code cpp></​code></​hidden>​+01Trie+数论。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 +#define maxn 100086 
 +using namespace std; 
 + 
 +int son[maxn << 8][2], val[maxn << 8]; 
 + 
 +int cnt = maxn; 
 + 
 +void insert(int x, int y){ 
 + for(int i = 1 << 20;i;i >>= 1){ 
 + bool z = (y & i) != 0; 
 + if(!son[x][z]) son[x][z] = ++cnt, val[son[x][z]] = maxn; 
 + x = son[x][z], val[x] = min(val[x], y); 
 + //​printf("​%d %d %d--\n",​ x, i, val[x]); 
 + } 
 +} 
 + 
 +int query(int x, int y, int s){ 
 + int ans = 0; 
 + for(int i = 1 << 20;i;i >>= 1){ 
 + //​printf("​%d %d %d %d--\n",​ x, y, s, i); 
 + bool z = (y & i) != 0; 
 + if(val[son[x][z ^ 1]] <= s) x = son[x][z ^ 1], ans += (z ^ 1) * i; 
 + else if(val[son[x][z]] <= s) x = son[x][z], ans += z * i; 
 + else return -1; 
 + } 
 + return ans; 
 +} 
 + 
 +int n; 
 +int opt, x, y, z; 
 + 
 +int main(){ 
 + scanf("​%d",​ &n); 
 + val[0] = maxn; 
 + while(n--){ 
 + scanf("​%d",​ &​opt);​ 
 + if(opt == 1){ 
 + scanf("​%d",​ &x); 
 + for(int i = 1;i * i <= x;i++){ 
 + if(x % i) continue; 
 + insert(i,​ x); 
 + if(i * i != x) insert(x / i, x); 
 + } 
 + }else{ 
 + scanf("​%d%d%d",​ &x, &y, &z); 
 + if(x % y){ 
 + puts("​-1"​);​ 
 + continue;​ 
 + } 
 + printf("​%d\n",​ query(y, x, z - x)); 
 + } 
 + } 
 +}</​code></​hidden>​
 =====CF1093G===== =====CF1093G=====
-<​hidden><​code cpp></​code></​hidden>​+高维曼哈顿距离+线段树。 
 +<​hidden><​code cpp>#include <​bits/​stdc++.h>​ 
 +#define maxn 200086 
 +using namespace std; 
 + 
 +struct Node{ 
 + int sum[32]; 
 +  
 + Node(){ 
 + memset(sum,​ -0x3f, sizeof(sum));​ 
 + } 
 +  
 + inline int & operator [] (int i){ 
 + return sum[i]; 
 + } 
 +  
 +}t[maxn << 2]; 
 + 
 + 
 +#define ls(x) (x << 1) 
 +#define rs(x) (x << 1 | 1) 
 + 
 +inline void up(int x){ 
 + for(int i = 0;i < 32;i++) t[x][i] = max(t[ls(x)][i],​ t[rs(x)][i]);​ 
 +}  
 + 
 +void modify(int x, int l, int r, int pos, Node d){ 
 + if(l == r){ 
 + t[x] = d; 
 + return; 
 + } 
 + int mid = l + r >> 1; 
 + if(mid >= pos) modify(ls(x),​ l, mid, pos, d); 
 + else modify(rs(x),​ mid + 1, r, pos, d); 
 + up(x); 
 +} 
 + 
 +Node query(int x, int l, int r, int ll, int rr){ 
 + if(ll <= l && r <= rr) return t[x]; 
 + int mid = l + r >> 1; 
 + Node a, b; 
 + if(mid >= ll){ 
 + b = query(ls(x),​ l, mid, ll, rr); 
 + for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]); 
 + } 
 + if(mid < rr){ 
 + b = query(rs(x),​ mid + 1, r, ll, rr); 
 + for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]); 
 + } 
 + return a; 
 +} 
 + 
 +int n, k, x, y; 
 +int q, opt; 
 +Node a; 
 + 
 + 
 +int main(){ 
 + scanf("​%d%d",​ &n, &k); 
 + for(int i = 1;i <= n;i++){ 
 + memset(a.sum,​ 0, sizeof(a.sum));​ 
 + for(int j = 0;j < k;j++){ 
 + scanf("​%d",​ &x); 
 + for(int l = 0;l < 32;l++){ 
 + if(l & (1 << j)) a[l] += x; 
 + else a[l] -= x; 
 + } 
 + } 
 + modify(1, 1, n, i, a); 
 + } 
 + scanf("​%d",​ &q); 
 + while(q--){ 
 + scanf("​%d",​ &​opt);​ 
 + if(opt == 1){ 
 + int i; 
 + scanf("​%d",​ &i); 
 + memset(a.sum,​ 0, sizeof(a.sum));​ 
 + for(int j = 0;j < k;j++){ 
 + scanf("​%d",​ &x); 
 + for(int l = 0;l < 32;l++){ 
 + if(l & (1 << j)) a[l] += x; 
 + else a[l] -= x; 
 + } 
 + } 
 + modify(1,​ 1, n, i, a); 
 + }else{ 
 + scanf("​%d%d",​ &x, &y); 
 + a = query(1, 1, n, x, y); 
 + int ans = -1e9; 
 + for(int i = 0;i < (1 << k);i++) ans = max(ans, a[i] + a[(1 << k) - 1 - i]); 
 + printf("​%d\n",​ ans); 
 + } 
 + }  
 +}</​code></​hidden>​
2020-2021/teams/farmer_john/jjleo/2020.05.16-2020.05.22.1590156744.txt.gz · 最后更改: 2020/05/22 22:12 由 jjleo

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3