首页 > 代码库 > Codeforces 216D Spider's Web 树状数组+模拟
Codeforces 216D Spider's Web 树状数组+模拟
题目链接:http://codeforces.com/problemset/problem/216/D
题意:
对于一个梯形区域,如果梯形左边的点数!=梯形右边的点数,那么这个梯形为红色,否则为绿色,
问:
给定的蜘蛛网中有多少个红色。
2个树状数组维护2个线段。然后暴力模拟一下,因为点数很多但需要用到的线段树只有3条,所以类似滚动数组的思想优化内存。
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<vector> #include<set> using namespace std; #define N 10010 #define L(x) (x<<1) #define R(x) (x<<1|1) #define ll int int maxn; struct hehe{ int c[100505]; void init(){memset(c, 0, sizeof c);} inline int Lowbit(int x){return x&(-x);} void change(int i, int x)//i点增量为x { while(i <= maxn) { c[i] += x; i += Lowbit(i); } } int sum(int x){//区间求和 [1,x] int ans = 0; for(int i = x; i >= 1; i -= Lowbit(i)) ans += c[i]; return ans; } }tree[2]; int ans; vector<int>l,r,o; void work(){ if(o.size()<=1)return; tree[0].init(); tree[1].init(); for(int i = 0; i < l.size(); i++) tree[0].change(l[i],1); for(int i = 0; i < r.size(); i++) tree[1].change(r[i],1); int L = o[0]; for(int i = 1; i < o.size(); i++){ int R = o[i]; if(L+1<=R-1){ int Z = tree[0].sum(R-1)-tree[0].sum(L); int Y = tree[1].sum(R-1)-tree[1].sum(L); ans += (Z!=Y); } L = R; } } vector<int>a,tmp1, red, tmp2, tmpend; void Red(){ red.clear(); int HHH,EEE; scanf("%d",&HHH); while(HHH--){scanf("%d",&EEE);red.push_back(EEE);} sort(red.begin(),red.end()); } int n; int main(){ int i,j,num; maxn = 100010; while(~scanf("%d",&n)){ ans = 0; l.clear(); r.clear(); tmp1.clear(); a.clear(); tmp2.clear(); tmpend.clear(); Red(); l = tmp1 = red; Red(); tmp2 = o = red; for(i = 3; i <= n; i++){ Red(); r = red; if(i==n)tmpend = red; work(); l = o; o = r; } r = tmp1; work(); l = tmpend; o = tmp1; r = tmp2; work(); cout<<ans<<endl; } return 0; } /* 3 2 1 3 3 1 3 2 3 1 3 2 ans: 0 2 */ /* ll n,m,k; ll a[N]; ll gcd(ll x,ll y){ if(x>y)swap(x,y); while(x){ y%=x; swap(x,y); } return y; } int main(){ ll i, j, u, v, que; while(cin>>n>>m>>k){ for(i = 1; i <= n; i++)cin>>a[i]; ll _gcd = a[1]; for(i = 2; i <= n; i++)_gcd = gcd(_gcd,a[i]); for(i = 1; i <= n; i++)a[i]/=_gcd; } return 0; } /* */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。