第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
关于数学的疑问
蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的
1、简单数学(基础运算)
2、位运算
3、线性代数
4、离散数学(组合数学)
5、初等数论(整数的性质)
6、概率论
7、几何
虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。
算法训练 士兵杀敌（二）
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。
小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。
南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。
输入格式
多组测试数据，以EOF结尾；
每组第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000)
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操
作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.
输出格式
对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行
样例输入
5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5
样例输出
6
8
8
20
题解：
C语言
#include<stdio.h> int main() { int pr=5; while(pr--) { int n,m; int shu[10001]; scanf("%d%d",&n,&m); int i; for(i=0;i<n;i++) { scanf("%d",&shu[i]); } while(m--) { getchar(); int sum=0; char x[10]; int p,q; scanf("%s %d %d",x,&p,&q); if(x[0]=='Q') { for(;p<=q;p++) sum+=shu[p-1]; printf("%d\n",sum); } else { shu[p-1]+=q; } } } }
C++语言
#include<stdio.h> #include<string.h> int p[1000010],n; int lowbit(int x) { return x&(-x); } void add(int i,int x) { while(i<=n) { p[i]+=x; i+=lowbit(i); } } int sum(int x) { int res=0; while(x>0) { res+=p[x]; x-=lowbit(x); } return res; } int main() { int m,i,x,a,b; char s[10]; while(scanf("%d%d",&n,&m)!=EOF) { memset(p,0,sizeof(p)); for(i=1;i<=n;i++) { scanf("%d",&x); add(i,x); } for(i=1;i<=m;i++) { scanf("%s",s); if(s[0]=='Q') { scanf("%d%d",&a,&b); int res=sum(b)-sum(a-1); printf("%d\n",res); } else { scanf("%d%d",&a,&x); add(a,x); } } } return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer x = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); while(x.nextToken()!=x.TT_EOF) { int n=(int)x.nval; x.nextToken(); int m=(int)x.nval; int aa[]=new int[n]; for(int i=0;i<n;i++) { x.nextToken(); aa[i]=(int)x.nval; } while(m--!=0) { x.nextToken(); String s=x.sval; if(s.equals("QUERY")) { x.nextToken(); int i=(int)x.nval-1,sum=0; x.nextToken(); int j=(int)x.nval-1; for(;i<=j;i++) sum+=aa[i]; System.out.println(sum); } else { x.nextToken(); int i=(int)x.nval-1; x.nextToken(); aa[i]+=(int)x.nval; } } } } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
T = 5 while T > 0: T -= 1 a = list(map(int, input().split())) b = list(map(int, input().split())) c = [] for x in range(a[1]): d = list(input().split()) if d[0] == 'QUERY': c.append(sum(b[int(d[1]) - 1:int(d[2])])) else: b[int(d[1]) - 1] += int(d[2]) for x in range(len(c)): print(c[x])
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
