8.20 北校复习

==。

Div2 区间和

线段树+二分

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100010; map<LL,int> mark; int tot; struct Tree{ int l,r; int sum; int lazy; }tree[4*maxn]; void build(int node){ tree[node].sum = 0; if(tree[node].l == tree[node].r) return; int mid = (tree[node].l + tree[node].r) /2; tree[node*2].l = tree[node].l; tree[node*2].r = mid; tree[node*2+1].l = mid+1; tree[node*2+1].r = tree[node].r; build(2*node); build(2*node+1); return; } void tree_insert(int node,int pos){ if(tree[node].l == pos && tree[node].r == pos){ tree[node].sum++; return; } int mid=(tree[node].l+tree[node].r)/2; if(pos<=mid){ tree_insert(2*node,pos); } else tree_insert(2*node+1,pos); tree[node].sum = tree[node*2].sum + tree[node*2+1].sum; return; } int query(int node,int s,int e){ if(tree[node].l>=s&&tree[node].r<=e){ //printf("s = %d e = %d ans = %d\n",s,e,tree[node].sum); return tree[node].sum; } int ans = 0; int mid = (tree[node].l + tree[node].r)/2; if(s<=mid) ans+=query(node*2,s,e); if(e>mid) ans+=query(node*2+1,s,e); //printf("s = %d e = %d ans = %d\n",s,e,ans); return ans; } LL pre[maxn]; LL line[maxn]; int main(){ //freopen("1.txt","r",stdin); int n,L,R; while(~scanf("%d%d%d",&n,&L,&R)){ tot = 0; LL ans = 0; for(int i=0;i<n;i++){ int a; scanf("%d",&a); pre[i+1] = a + pre[i]; line[i] = pre[i+1]; if(pre[i+1]>=L && pre[i+1]<=R) ans++; //printf("pre = %d\n", pre[i+1]); } sort(line,line+n); for(int i=0;i<n;i++) if(!mark.count(line[i])) mark[line[i]] = ++tot; tree[1].l=1, tree[1].r=tot; build(1); for(int i=1;i<=n;i++){ LL* n1 = lower_bound(line,line+n,pre[i]-R); LL* n2 = upper_bound(line, line+n, pre[i]-L); n2--; if(n2>=n1){ int id1 = mark[*n1]; int id2 = mark[*n2]; ans+=query(1,id1,id2); //printf(" ans = %lld\n",ans); } tree_insert(1,mark[pre[i]]); } printf("%lld\n", ans); } return 0; }

Div2 更新学号

#include <bits/stdc++.h> using namespace std; int mark[9999999]; int id[5010]; int main(){ int n; while(~scanf("%d", &n)){ for(int i=0; i<n; i++) scanf("%d", &id[i]); sort(id,id+n); memset(mark, 0, sizeof(mark)); for(int i=0;i<n;i++){ for(int j=i+1; j<n; j++) mark[id[j]-id[i]]=1; } int ans = n; bool flag=false; while(!flag){ flag = true; for(int i=ans; i<1e7; i+=ans){ if(mark[i]){ //printf("i = %d\n", i); flag = false; break; } } ans++; } printf("%d\n", ans-1); } return 0; }

码题

Div1 wmq的A+B Problem

Div1 Triangles

Div1 wmq的征程