Training address： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38966#overview
A.Count Color --- POJ 2777
这题初看不好下手，再想想，T<=30，这时想到颜色可以用二进制来表示，然后父节点颜色种类为子节点的按位或得出的结果中化为二进制时1的个数，然后就是无脑线段树了。。
代码：
#include <iostream> #include <cstdio> #include <utility> #include <cstdlib> using namespace std; #define N 100010 struct node { int mark; int sum; }tree[4*N]; void pushup(int rt) { tree[rt].sum = tree[2*rt].sum | tree[2*rt+1].sum; } void build(int l,int r,int rt) { tree[rt].sum = 1; tree[rt].mark = 1; if(l == r) return; int mid = (l+r)/2; build(l,mid,2*rt); build(mid+1,r,2*rt+1); pushup(rt); } void pushdown(int l,int r,int rt) { if(!tree[rt].mark) return; if(tree[rt].mark) { tree[2*rt].sum = tree[2*rt+1].sum = tree[rt].sum; tree[2*rt].mark = tree[2*rt+1].mark = tree[rt].mark; tree[rt].mark = 0; } } void make(int l,int r,int aa,int bb,int co,int rt) { if(aa<=l && bb>=r) { tree[rt].mark = 1; tree[rt].sum = 1<<(co-1); return; } pushdown(l,r,rt); int mid = (l+r)/2; if(aa<=mid) make(l,mid,aa,bb,co,2*rt); if(bb>mid) make(mid+1,r,aa,bb,co,2*rt+1); pushup(rt); } int query(int l,int r,int aa,int bb,int rt) { if(aa>r||bb<l) return 0; if(aa<=l&&bb>=r) { return tree[rt].sum; } pushdown(l,r,rt); int mid = (l+r)/2; return query(l,mid,aa,bb,2*rt)|query(mid+1,r,aa,bb,2*rt+1); } int main() { int n,t,o; int i; int aa,bb,co; char ss[5]; scanf("%d%d%d",&n,&t,&o); build(1,n,1); int cnt; for(i=0;i<o;i++) { scanf("%s",ss); if(ss[0] == 'C') { scanf("%d%d%d",&aa,&bb,&co); make(1,n,aa,bb,co,1); } else if(ss[0] == 'P') { scanf("%d%d",&aa,&bb); int res; if(aa<=bb) res = query(1,n,aa,bb,1); else res = query(1,n,bb,aa,1); cnt = 0; while(res) { if(res&1) cnt++; res>>=1; } printf("%d ",cnt); } } return 0; }
B.Who Gets the Most Candies --- POJ 2886
(题解借鉴： ahfywff）
本题利用反素数的概念。反素数的定义：对于任何正整数x，其约数的个数记做f(x)。例如f(1)=1,f(6)=4。如果某个正整数x满足：对于任意i(0<i<x)，都有f(i)<f(x)，则称x为反素数。对于本题，设pos为不大于N的反素数，则第pos个出圈的孩子得到的糖果最多，为pos的约数个数。
出圈过程有点类似约瑟夫环。假设当前出圈的是剩余孩子中的第K个，他手中的数字为A。
若A大于零，下一个出圈的就应该是剩余孩子中的第(K-1+A-1)%n+1个；
若A小于零，下一个出圈的就应该是剩余孩子中的第((K-1+A)%n+n)%n+1个。
问题的关键是如何求得出圈孩子的原始位置，线段树的每个节点的sum存储了所在区间还有多少孩子留下，查询节点rt中第num个孩子的原始位置时，如果num<=st[2*rt].sum，则在左孩子节点中查询第num个孩子的原始位置；否则在右孩子节点中查询第num-st[2*rt].sum个孩子的原始位置。
代码：
/*12152 KB 1079 ms*/ #include <iostream> #include <cstdio> using namespace std; #define N 500010 int anti[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400, 55440,83160,110880,166320,221760,277200,332640,498960,500001}; int factor[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521}; int tree[4*N]; char name[N][11]; int num[N]; void build(int l,int r,int rt) { tree[rt] = r-l+1; if(l == r) return; int mid = (l+r)/2; build(l,mid,2*rt); build(mid+1,r,2*rt+1); } int query(int l,int r,int pos,int rt) { tree[rt]--; if(l == r) return l; int mid = (l+r)/2; if(pos<=tree[2*rt]) return query(l,mid,pos,2*rt); else return query(mid+1,r,pos-tree[2*rt],2*rt+1); } int main() { int n,k,pos,Maxcandy,i; while(scanf("%d%d",&n,&k)!=EOF) { i=0; int CN = n; while(anti[i]<=n) i++; pos = anti[i-1]; Maxcandy = factor[i-1]; build(1,n,1); for(i=1;i<=n;i++) { scanf("%s %d",name[i],&num[i]); } int flag; for(i=1;i<=pos;i++) { n--; flag = query(1,CN,k,1); if(n==0) break; if(num[flag]>0) k = (k + num[flag] - 2)%n + 1; else k = ((k + num[flag] - 1)%n+n)%n + 1; } printf("%s %d ",name[flag],Maxcandy); } }
G.Fast Matrix Operations ---UVA 11992
这题其实也不太难搞，关键是各方面要维护到，我写了两个多小时啊，最后还是有些地方没有照顾到，哎，太弱咯。。感觉自己在维护值方面还差一点火候。 这题看行数不超过20，想到在每一行都建一颗线段树，然后就搞吧。。代码有点长，将就着看吧。
(A.M : Attention to Maintain)
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <utility> #include <cstdlib> #define Mod 1000000007 using namespace std; #define N 1000010 struct node { int mini,maxi,sum; int addmark,setmark; }tree[21][4*N]; int i; void pushup(int i,int rt) { tree[i][rt].sum = tree[i][2*rt].sum + tree[i][2*rt+1].sum; tree[i][rt].mini = min(tree[i][2*rt].mini,tree[i][2*rt+1].mini); tree[i][rt].maxi = max(tree[i][2*rt].maxi,tree[i][2*rt+1].maxi); } void build(int i,int l,int r,int rt) { tree[i][rt].sum = tree[i][rt].mini = tree[i][rt].maxi = 0; tree[i][rt].setmark = -1; tree[i][rt].addmark = 0; if(l == r) return; int mid = (l+r)/2; build(i,l,mid,2*rt); build(i,mid+1,r,2*rt+1); pushup(i,rt); } void pushdown(int i,int l,int r,int rt) { if(tree[i][rt].setmark == -1 && tree[i][rt].addmark == 0) return; int mid = (l+r)/2; if(tree[i][rt].setmark >= 0) { tree[i][2*rt].sum = tree[i][rt].setmark*(mid-l+1); tree[i][2*rt+1].sum = tree[i][rt].setmark*(r-mid); tree[i][2*rt].mini = tree[i][2*rt+1].mini = tree[i][rt].setmark; //A.M tree[i][2*rt].maxi = tree[i][2*rt+1].maxi = tree[i][rt].setmark; //A.M tree[i][2*rt].addmark = tree[i][2*rt+1].addmark = 0; // 这个要写 tree[i][2*rt].setmark = tree[i][2*rt+1].setmark = tree[i][rt].setmark; tree[i][rt].setmark = -1; } if(tree[i][rt].addmark > 0) { tree[i][2*rt].sum += tree[i][rt].addmark*(mid-l+1); tree[i][2*rt+1].sum += tree[i][rt].addmark*(r-mid); tree[i][2*rt].maxi += tree[i][rt].addmark; //A.M tree[i][2*rt].mini += tree[i][rt].addmark; //A.M tree[i][2*rt+1].maxi += tree[i][rt].addmark; //A.M tree[i][2*rt+1].mini += tree[i][rt].addmark; //A.M tree[i][2*rt].addmark += tree[i][rt].addmark; tree[i][2*rt+1].addmark += tree[i][rt].addmark; tree[i][rt].addmark = 0; } } void add(int l,int r,int aa,int bb,int val,int rt) { if(aa>r||bb<l) return; if(aa<=l&&bb>=r) { tree[i][rt].addmark += val; //tree[i][rt].setmark = -1; --不要写这个 tree[i][rt].sum += (r-l+1)*val; tree[i][rt].maxi += val; tree[i][rt].mini += val; return; } pushdown(i,l,r,rt); int mid = (l+r)/2; if(aa<=mid) add(l,mid,aa,bb,val,2*rt); if(bb>mid) add(mid+1,r,aa,bb,val,2*rt+1); pushup(i,rt); } void setval(int l,int r,int aa,int bb,int val,int rt) { if(aa>r||bb<l) return; if(aa<=l&&bb>=r) { tree[i][rt].setmark = val; tree[i][rt].addmark = 0; tree[i][rt].sum = val*(r-l+1); tree[i][rt].maxi = tree[i][rt].mini = val; return; } pushdown(i,l,r,rt); int mid = (l+r)/2; if(aa<=mid) setval(l,mid,aa,bb,val,2*rt); if(bb>mid) setval(mid+1,r,aa,bb,val,2*rt+1); pushup(i,rt); } struct node_ans { int sum; int mini,maxi; }; node_ans query(int l,int r,int aa,int bb,int rt) { node_ans res,ka1,ka2; if(aa<=l && bb>=r) { res.sum = tree[i][rt].sum; res.maxi = tree[i][rt].maxi; res.mini = tree[i][rt].mini; return res; } pushdown(i,l,r,rt); int mid = (l+r)/2; if(bb<=mid) return query(l,mid,aa,bb,2*rt); else if(aa>mid) return query(mid+1,r,aa,bb,2*rt+1); else { ka1 = query(l,mid,aa,bb,2*rt); ka2 = query(mid+1,r,aa,bb,2*rt+1); res.sum = ka1.sum + ka2.sum; res.maxi = max(ka1.maxi,ka2.maxi); res.mini = min(ka1.mini,ka2.mini); return res; } } int main() { int r,c,m; int k,zuo; int x1,y1,x2,y2,val; int sum,mmax,mmin; while(scanf("%d%d%d",&r,&c,&m)!=EOF) { for(i=1;i<=r;i++) { build(i,1,c,1); } for(k=0;k<m;k++) { scanf("%d",&zuo); if(zuo == 1) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val); for(i=x1;i<=x2;i++) { add(1,c,y1,y2,val,1); } } else if(zuo == 2) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val); for(i=x1;i<=x2;i++) { setval(1,c,y1,y2,val,1); } } else { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); node_ans la; sum = 0; mmax = -Mod; mmin = Mod; for(i=x1;i<=x2;i++) { la = query(1,c,y1,y2,1); sum += la.sum; mmax = max(mmax,la.maxi); mmin = min(mmin,la.mini); } printf("%d %d %d ",sum,mmin,mmax); } } } }