[BZOJ 2190]仪仗队
这个题啊……有规律可循。
我们可以发现，关于答案有如下规律：
然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）
代码：
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 | /************************************************************** Problem: 2190 User: danihao123 Language: C++ Result: Accepted Time:28 ms Memory:976 kb****************************************************************/ #include <cstdio>#include <algorithm>using namespace std;const int maxn=40005;#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++) int phi[maxn];int n;void sieve(){ register int i,j; phi[1]=1; CUS_REP(i,2,n) if(!phi[i]) for(j=i;j<=n;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); }} int main(){ register int i,ans=2; scanf("%d",&n); sieve(); /* #ifdef DEBUG CUS_REP(i,1,n) printf("%d\n",phi[i]); #endif */ CUS_REP(i,2,n-1) ans+=phi[i]; printf("%d\n",ans*2-1); return 0;} |
[BZOJ 3531]旅行
发现自己好久没写树链剖分了……唉……
言归正传，这道题很容易想到的做法就是每种宗教开一个线段树，到各个宗教的线段树里面操作即可。
很可惜，直接开线段树的话肯定会MLE。我们可以考虑动态开点，对于不需要的点一律不开。这样内存消耗量就大减了。
注意一些细节：
- 查询时判断当前结点是不是NULL。
- 删除前最好判断一下这个结点是不是NULL吧，以防万一。
- 删除操作时，如果结点没有用了，就删。但是注意，记得delete前要把原指针设为NULL，直接delete会引起悬垂指针问题导致爆炸！
代码：
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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | /************************************************************** Problem: 3531 User: danihao123 Language: C++ Result: Accepted Time:10404 ms Memory:34872 kb****************************************************************/ #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=100005;int n;namespace SegmentTree{ struct Node{ int sumv,maxv; Node *lc,*rc; Node(){ sumv=maxv=0; lc=rc=NULL; } void maintain(){ if(lc!=NULL){ if(rc!=NULL){ sumv=lc->sumv+rc->sumv; maxv=max(lc->maxv,rc->maxv); }else{ sumv=lc->sumv; maxv=lc->maxv; } }else{ if(rc!=NULL){ sumv=rc->sumv; maxv=rc->maxv; } } } }; Node* T[maxn]; int p,v; void _Delete(Node* &o,int L,int R){ if(o==NULL) return; if(L==R){ Node *temp=o; o=NULL; delete temp; }else{ int M=L+(R-L)/2; if(p<=M) _Delete(o->lc,L,M); else _Delete(o->rc,M+1,R); if(o->lc==NULL && o->rc==NULL){ Node *temp=o; o=NULL; delete temp; }else{ o->maintain(); } } } inline void Delete(int c,int pos){ p=pos; _Delete(T[c],1,n); } void _Insert(Node* &o,int L,int R){ if(o==NULL) o=new Node(); if(L==R){ o->sumv=o->maxv=v; }else{ int M=L+(R-L)/2; if(p<=M) _Insert(o->lc,L,M); else _Insert(o->rc,M+1,R); } o->maintain(); } inline void Insert(int c,int pos,int value){ p=pos; v=value; _Insert(T[c],1,n); } int ql,qr; int _query_max(Node *o,int L,int R){ if(o==NULL) return 0; if(ql<=L && R<=qr) return o->maxv; int M=L+(R-L)/2,ans=0; if(ql<=M) ans=max(ans,_query_max(o->lc,L,M)); if(qr>M) ans=max(ans,_query_max(o->rc,M+1,R)); return ans; } inline int query_max(int c,int l,int r){ ql=l; qr=r; return _query_max(T[c],1,n); } int _query_sum(Node *o,int L,int R){ if(o==NULL) return 0; if(ql<=L && R<=qr) return o->sumv; int M=L+(R-L)/2,ans=0; if(ql<=M) ans+=_query_sum(o->lc,L,M); if(qr>M) ans+=_query_sum(o->rc,M+1,R); return ans; } inline int query_sum(int c,int l,int r){ ql=l; qr=r; return _query_sum(T[c],1,n); }};#define REP(i,n) for(i=0;i<(n);i++)#define REP_B(i,n) for(i=1;i<=(n);i++)#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])int first[maxn];int next[maxn*2],to[maxn*2];int graph_tot=0;inline void AddEdge(int u,int v){ graph_tot++; next[graph_tot]=first[u]; first[u]=graph_tot; to[graph_tot]=v;} int dep[maxn],fa[maxn],son[maxn],siz[maxn];bool vis[maxn];void dfs_1(int x,int father,int depth){ vis[x]=true; fa[x]=father; dep[x]=depth; siz[x]=1; int i,temp,max_siz=0; GRAPH_REP(i,x){ temp=to[i]; if(!vis[temp]){ dfs_1(temp,x,depth+1); siz[x]+=siz[temp]; if(siz[temp]>max_siz){ son[x]=temp; max_siz=siz[temp]; } } }}int hld_cnt=0;int rlg[maxn];int d[maxn];int tid[maxn],top[maxn];void dfs_2(int x,int a){ vis[x]=true; top[x]=a; tid[x]=++hld_cnt; SegmentTree::Insert(rlg[x],hld_cnt,d[x]); if(son[x]) dfs_2(son[x],a); else return; int i,temp; GRAPH_REP(i,x){ temp=to[i]; if(!vis[temp]){ dfs_2(temp,temp); } }}int query_max(int c,int x,int y){ if(top[x]==top[y]){ if(tid[x]>tid[y]) swap(x,y); return SegmentTree::query_max(c,tid[x],tid[y]); } if(dep[top[x]]<dep[top[y]]) swap(x,y); return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));}int query_sum(int c,int x,int y){ if(top[x]==top[y]){ if(tid[x]>tid[y]) swap(x,y); return SegmentTree::query_sum(c,tid[x],tid[y]); } if(dep[top[x]]<dep[top[y]]) swap(x,y); return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);}inline void Replace(int pos,int direction){ int c=rlg[pos]; SegmentTree::Delete(c,tid[pos]); SegmentTree::Insert(direction,tid[pos],d[pos]); rlg[pos]=direction;}inline void Update(int pos,int v){ d[pos]=v; SegmentTree::Insert(rlg[pos],tid[pos],v);} int main(){ register int i; int q,u,v; char buf[5]; scanf("%d%d",&n,&q); REP_B(i,n){ scanf("%d%d",&d[i],&rlg[i]); } REP_B(i,n-1){ scanf("%d%d",&u,&v); AddEdge(u,v); AddEdge(v,u); } dfs_1(1,0,1); memset(vis,0,sizeof(vis)); dfs_2(1,1); while(q--){ memset(buf,0,sizeof(buf)); scanf("%s%d%d",buf,&u,&v); if(buf[0]=='C'){ if(buf[1]=='W'){ Update(u,v); }else{ Replace(u,v); } }else{ if(buf[1]=='M'){ printf("%d\n",query_max(rlg[u],u,v)); }else{ printf("%d\n",query_sum(rlg[u],u,v)); } } } return 0;} |
[BZOJ 1878]HH的项链
扫描线处女作TAT
直接离线，按左端点排序扫描。每个点要保存后继相同节点，每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。
代码：
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 | /************************************************************** Problem: 1878 User: danihao123 Language: C++ Result: Accepted Time:1344 ms Memory:8444 kb****************************************************************/ #include <cstdio>#include <cctype>#include <algorithm>using namespace std;const int maxn=50001,maxm=200001;int T[maxn];int n;inline int lowbit(int x){ return x&(-x);}inline void update(int p,int v){ while(p<=n){ T[p]+=v; p+=lowbit(p); }}inline int query(int p){ register int ans=0; while(p>0){ ans+=T[p]; p-=lowbit(p); } return ans;} struct Query{ int l,r; int id; int ans; bool operator <(const Query& x) const{ return l==x.l?r<x.r:l<x.l; }};Query Q[maxm];bool cmp2(const Query& a,const Query& b){ return a.id<b.id;} // I/O优化inline int readint(){ char c=getchar(); register int x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); } return x;}int bf[10];inline void writeint(int x){ register int p=0; if(x==0){ bf[p++]=0; }else{ while(x){ bf[p++]=x%10; x/=10; } } for(register int i=p-1;i>=0;i--) putchar('0'+bf[i]);} int next[maxn];int A[maxn];int pos[1000001];int main(){ int m,maxA=0; register int i,j; n=readint(); for(i=1;i<=n;i++){ A[i]=readint(); maxA=max(maxA,A[i]); } for(i=n;i;i--){ next[i]=pos[A[i]]; pos[A[i]]=i; } for(i=1;i<=maxA;i++) if(pos[i]) update(pos[i],1); m=readint(); for(i=1;i<=m;i++){ Q[i].l=readint(); Q[i].r=readint(); Q[i].id=i; } sort(Q+1,Q+1+m); register int tot=1; for(i=1;i<=m;i++){ while(tot<Q[i].l){ if(next[tot]) update(next[tot],1); tot++; } Q[i].ans=query(Q[i].r)-query(Q[i].l-1); } sort(Q+1,Q+1+m,cmp2); for(i=1;i<=m;i++){ writeint(Q[i].ans); putchar('\n'); } return 0;} |
[BZOJ 2243]染色
树剖好题……
这能说明几个问题：
- 人傻自带大常数
- 不看题解难AC
