首页 > 代码库 > NYOJ 士兵杀敌（1~5）
NYOJ 士兵杀敌（1~5）
士兵杀敌（1）： http://acm.nyist.net/JudgeOnline/problem.php?pid=108
分析：前缀和
1 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 int a[1000005]; 7 int sum[1000005]; 8 9 int main()10 {11 int n,m;12 scanf("%d%d",&n,&m);13 14 sum[0] = 0;15 for(int i=1;i<=n;i++) {16 scanf("%d",&a[i]);17 sum[i] = sum[i-1] + a[i];18 }19 20 while(m--) {21 int m,n;22 scanf("%d%d",&m,&n);23 if(m>n)24 swap(m,n);25 printf("%d\n",sum[n]-sum[m-1]);26 27 }28 29 return 0;30 }31
士兵杀敌（2）：http://acm.nyist.net/JudgeOnline/problem.php?pid=116
分析：树状数组（单点更新，区间求和）
1 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int maxn = 1000000+5; 7 8 int C[maxn]; 9 int n,m;10 11 12 int lowbit(int x) {13 return x&-x;14 }15 16 //A[1] + A[2] + ... + A[x]17 int sum(int x) {18 int ret = 0;19 while(x>0) {20 ret +=C[x];21 x-=lowbit(x);22 }23 return ret;24 }25 26 //A[x] +=d;27 void add(int x,int d) {28 while(x<=n) {29 C[x] +=d;30 x+=lowbit(x);31 }32 }33 34 int main()35 {36 scanf("%d%d",&n,&m);37 for(int i=1;i<=n;i++) {38 int x;39 scanf("%d",&x);40 add(i,x);41 }42 43 char cmd[10];44 for(int i=0;i<m;i++) {45 scanf("%s",cmd);46 if(cmd[0]==‘A‘)47 {48 int x,d;49 scanf("%d%d",&x,&d);50 add(x,d);51 }52 else {53 int u,v;54 scanf("%d%d",&u,&v);55 printf("%d\n",sum(v)-sum(u-1));56 }57 }58 59 return 0;60 }61
士兵杀敌（3）：http://acm.nyist.net/JudgeOnline/problem.php?pid=119
分析：RMQ
1 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int maxn = 100005; 7 8 struct RMQ { 9 10 int dmin[maxn][20];11 int dmax[maxn][20];12 13 void RMQ_init(const vector<int>& A) {14 int n = A.size();15 for(int i=0;i<n;i++)16 {17 dmin[i][0] = A[i];18 dmax[i][0] = A[i];19 }20 21 for(int j=1;(1<<j)<=n;j++) {22 for(int i=0;i+(1<<j)-1<n;i++) {23 dmin[i][j] = min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);24 dmax[i][j] = max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);25 }26 }27 }28 29 int RMQ_min(int L,int R) {30 int k = 0;31 while((1<<(k+1))<=R-L+1)32 k++;33 return min(dmin[L][k],dmin[R-(1<<k)+1][k]);34 }35 36 int RMQ_max(int L,int R) {37 int k = 0;38 while((1<<(k+1))<=R-L+1)39 k++;40 int ans = max(dmax[L][k],dmax[R-(1<<k)+1][k]);41 return ans;42 }43 44 45 }sol;46 47 int main()48 {49 int n,m;50 scanf("%d%d",&n,&m);51 vector<int> v;52 for(int i=0;i<n;i++) {53 int x;54 scanf("%d",&x);55 v.push_back(x);56 }57 sol.RMQ_init(v);58 59 for(int i=0;i<m;i++) {60 int l,r;61 scanf("%d%d",&l,&r);62 l--;r--;63 printf("%d\n",sol.RMQ_max(l,r)-sol.RMQ_min(l,r));64 }65 66 return 0;67 }68
士兵杀敌（4）：http://acm.nyist.net/JudgeOnline/problem.php?pid=123
分析：区间更新，单点查询；
线段树超时，要优化线段树，线段树这么高级，我可不会改板子啊 (*^__^*)
解法：利用树状数组的逆过程！！！
add的时候，就把路上的C[x] 全都加上；（add(qR,v);add(qL-1,v)）
询问的时候，往右上走，看看总共有多少给这个点产生了影响；
1 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int maxn = 1000000+5; 7 int C[maxn]; 8 int m,t; 9 int lowbit(int x)10 {11 return x&-x;12 }13 14 void add(int star,int num) {15 while(star>0) {16 C[star]+=num;17 star-=lowbit(star);18 }19 }20 21 int sum(int star) {22 int sum = 0;23 while(star<=m) {24 sum+=C[star];25 star+=lowbit(star);26 }27 return sum;28 }29 30 int main()31 {32 scanf("%d%d",&t,&m);33 while(t--) {34 char cmd[10];35 scanf("%s",cmd);36 if(cmd[0]==‘A‘) {37 int u,v,c;38 scanf("%d%d%d",&u,&v,&c);39 add(v,c);40 add(u-1,-c);41 }42 else {43 int pos;44 scanf("%d",&pos);45 printf("%d\n",sum(pos));46 }47 }48 49 return 0;50 }51
士兵杀敌（5）：http://acm.nyist.net/JudgeOnline/problem.php?pid=228
分析：区间更新，线段查询；
线段树又超时了 (ノへ￣、)
解法：巧用数组，记录下来每个区间的更新的起点，和结束的起点，然后累加计算出正确数组；
再求一个前缀和；
1 /* 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int maxnode = 1000001<<2; 7 int _min,_max,_sum; 8 int qL,qR,v; 9 10 struct IntervalTree 11 { 12 int sumv[maxnode], minv[maxnode], maxv[maxnode], addv[maxnode]; 13 void maintain(int o, int L, int R) 14 { 15 int lc = o*2, rc = o*2+1; 16 sumv[o] = minv[o] = maxv[o] = 0; 17 if(R > L) 18 { 19 sumv[o] = sumv[lc] + sumv[rc]; 20 minv[o] = min(minv[lc], minv[rc]); 21 maxv[o] = max(maxv[lc], maxv[rc]); 22 } 23 if(addv[o]) 24 { 25 minv[o] += addv[o]; 26 maxv[o] += addv[o]; 27 sumv[o] += addv[o] * (R-L+1); 28 } 29 } 30 31 void update(int o, int L, int R) 32 { 33 int lc = o*2, rc = o*2+1; 34 if(qL <= L && qR >= R) 35 { 36 addv[o] += v; 37 } 38 else 39 { 40 int M = L + (R-L)/2; 41 if(qL <= M) update(lc, L, M); 42 if(qR > M) update(rc, M+1, R); 43 } 44 maintain(o, L, R); 45 } 46 47 void query(int o, int L, int R, int add) 48 { 49 if(qL <= L && qR >= R) 50 { 51 _sum += (sumv[o] + add * (R-L+1))%10003; 52 _min = min(_min, minv[o] + add); 53 _max = max(_max, maxv[o] + add); 54 } 55 else 56 { 57 int M = L + (R-L)/2; 58 if(qL <= M) query(o*2, L, M, add + addv[o]); 59 if(qR > M) query(o*2+1, M+1, R, add + addv[o]); 60 } 61 } 62 63 }tree; 64 65 int main() 66 { 67 int n,c,q; 68 scanf("%d%d%d",&n,&c,&q); 69 while(c--) { 70 scanf("%d%d%d",&qL,&qR,&v); 71 tree.update(1,1,n); 72 } 73 74 while(q--) { 75 _sum = 0; 76 scanf("%d%d",&qL,&qR); 77 tree.query(1,1,n,0); 78 printf("%d\n",_sum); 79 } 80 81 return 0; 82 } 83 */ 84 85 #include <bits/stdc++.h> 86 87 using namespace std; 88 89 const int maxn = 1000005; 90 int num[maxn]; 91 92 int main() 93 { 94 int n,c,q; 95 memset(num,0,sizeof(num)); 96 scanf("%d%d%d",&n,&c,&q); 97 for(int i=0;i<c;i++) { 98 int l,r,v; 99 scanf("%d%d%d",&l,&r,&v);100 num[l]+=v;101 num[r+1]-=v;102 }103 104 for(int i=1;i<=n;i++) {105 num[i]+=num[i-1];106 }107 108 for(int i=1;i<=n;i++) {109 num[i]=(num[i]+num[i-1])%10003;110 }111 while(q--) {112 int l,r;113 scanf("%d%d",&l,&r);114 printf("%d\n",(num[r]-num[l-1]+10003)%10003);115 }116 117 return 0;118 }
NYOJ 士兵杀敌（1~5）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。