第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
前言
算法训练 操作格子
C语言
C 语言
Java语言
Python语言
第六届——第十三届省赛题解
第六届——第十二届省赛题解
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 操作格子
资源限制
内存限制：256.0MB C/C 时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
有n个格子，从左到右放成一排，编号为1-n。 共有m次操作，有3种操作类型： 1.修改一个格子的权值， 2.求连续一段格子权值和， 3.求连续一段格子的最大值。 对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。 接下来一行n个整数表示n个格子的初始权值。 接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间x,y内格子权值和，p=3时表示求区间x,y内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。 每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3 1 2 3 4 2 1 3 1 4 3 3 1 4
样例输出
6 3
数据规模与约定
对于20%的数据n <= 100，m <= 200。 对于50%的数据n <= 5000，m <= 5000。 对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000
题解：
C语言
代码语言：javascript复制#include <stdio.h>
#define N 100000
#define A 1000
#define B 100
int sum(int* a, int m, int n)
{
int i,s=0;
for (i=m;i<=n;i )
s =a[i];
return s;
}
int max(int* a, int m, int n)
{
int i,s=a[m];
for (i=m 1;i<=n;i )
if (s<a[i])
s=a[i];
return s;
}
int main()
{
int i,j,k,m,n;
int a[100000],b[100000][3],c[A][2]={0};
scanf("%d%d",&n,&m);
for (i=0; i<n;i )
scanf("%d",&a[i]);
for (i=0;i<m;i )
for (j=0;j<3;j )
scanf("%d", &b[i][j]);
for (i=0;i<(n B-1)/B;i )
{
c[i][0]=c[i][1]=a[i * B];
for (j=i*B 1;j<i*B B && j<n;j )
{
c[i][0] =a[j];
if (c[i][1]<a[j])
c[i][1]=a[j];
}
}
for (i=0;i<m;i )
{
if (b[i][0]==1)
{
c[(b[i][1]-1)/B][0] =b[i][2]-a[b[i][1]-1];
k=(b[i][1]-1)/B;
if (c[k][1]<=b[i][2])
{
c[k][1]=b[i][2];
}
else if (a[b[i][1]-1]==c[k][1])
{
a[b[i][1]-1]=b[i][2];
c[k][1]=max(a,k*B,k*B B>n ? n-1 : k*B B-1);
}
a[b[i][1]-1]=b[i][2];
}
else if(b[i][0]==2)
{
int s=0;
b[i][1]--, b[i][2]--;
int o=b[i][2]/B-b[i][1]/B;
if (o<2)
{
s=sum(a,b[i][1],b[i][2]);
}
else
{
s=sum(a,b[i][1],(b[i][1] B)/B*B-1);
s =sum(a, b[i][2]/B*B, b[i][2]);
for (j = b[i][1]/B 1;j<b[i][2]/B;j )
s = c[j][0];
}
printf("%dn",s);
}
else if (b[i][0]==3)
{
int s = 0,t;
b[i][1]--, b[i][2]--;
int o=b[i][2]/B-b[i][1]/B;
if (o<2)
{
s=max(a, b[i][1],b[i][2]);
}
else
{
s=max(a,b[i][1],(b[i][1] B)/B*B-1);
t=max(a,b[i][2]/B*B,b[i][2]);
if (s<t)s=t;
for (j=b[i][1]/B 1;j<b[i][2]/B;j )
if (s<c[j][1])
s=c[j][1];
}
printf("%dn",s);
}
}
return 0;
} C 语言
代码语言：javascript复制#include <cstdio>
#include <algorithm>
struct Tree
{
int sum, max;
};
Tree tree[1 << 18];
void scan(int &n)
{
char c;
c = getchar();
if (c == EOF) {
return ;
}
while (c < '0' || c > '9') {
c = getchar();
}
n = c - '0';
while (c = getchar(), c >= '0' && c <= '9') {
n *= 10;
n = c - '0';
}
}
void put(int n)
{
int cnt = 0;
char s[16];
if (n == 0) {
putchar('0');
return ;
}
for( ; n; n /= 10) {
s[cnt ] = n % 10 '0';
}
while (cnt--) {
putchar(s[cnt]);
}
}
void update(int n, int v)
{
for (n = (1 << 17),tree[n].sum = tree[n].max = v, n >>= 1; n; n >>= 1) {
tree[n].max = std::max(tree[n n].max, tree[n n 1].max);
tree[n].sum = tree[n n].sum tree[n n 1].sum;
}
}
int query(int s, int t, int func)
{
int sum = 0, max = 0;
for (s = (1 << 17) - 1, t = (1 << 17) 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
if (~s & 1) {
sum = tree[s ^ 1].sum;
max = std::max(max, tree[s ^ 1].max);
}
if (t & 1) {
sum = tree[t ^ 1].sum;
max = std::max(max, tree[t ^ 1].max);
}
}
return func ? max : sum;
}
int main()
{
int n, m, i, a, b, c;
scan(n);scan(m);
for (i = 1; i <= n; i) {
scan(a);
update(i, a);
}
while (m--) {
scan(c);scan(a);scan(b);
c == 1 && (update(a, b), 0);
c == 2 && (put(query(a, b, 0)), putchar('n'), 0);
c == 3 && (put(query(a, b, 1)), putchar('n'), 0);
}
return 0;
}Java语言
代码语言：javascript复制import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static int[] array;
static long []mark;
static long []Tree;
static int[] Max;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter pt=new PrintWriter(System.out);
st.nextToken();
int n=(int)st.nval;
array=new int[n 1];//图方便从1开始
mark=new long[4*n 4];
Tree=new long[4*n 4];
Max=new int[4*n 4];
st.nextToken();
int m=(int)st.nval;
for(int i=1;i<=n;i ) {
st.nextToken();
array[i]=(int)st.nval;
}
build(1,n,1);
for(int i=0;i<m;i ) {
st.nextToken();
if((int)st.nval==1) {
st.nextToken();
int a=(int)st.nval;
st.nextToken();
int v=(int)st.nval;
update(a,a,v,1,1,n);
}
else if((int)st.nval==2){
st.nextToken();
int a=(int)st.nval;
st.nextToken();
int b=(int)st.nval;
pt.println(query(a, b, 1, 1, n));
}
else {
st.nextToken();
int a=(int)st.nval;
st.nextToken();
int b=(int)st.nval;
pt.println(getMax(a, b, 1, 1, n));
}
}
pt.close();
}
public static void build(int l,int r,int p) {
if(l==r) {
Tree[p]=array[l];
Max[p]=array[l];
}
else {
int mid=l (r-l)/2;
build(l,mid,p*2);
build(mid 1,r,p*2 1);
Tree[p]=Tree[p*2] Tree[p*2 1];
Max[p]=Math.max(Max[p*2], Max[p*2 1]);
}
}
public static void update(int l,int r,int d,int p,int nowL,int nowR) {
if(r<nowL||l>nowR)
return;
if(l<=nowL&&r>=nowR) {
Tree[p]=d;//懒标记的规则就是在更新当前的mark之前 已经修改了当前的tree的值
Max[p]=d;
}
else {
int mid=nowL (nowR-nowL)/2;
update(l,r,d,p*2,nowL,mid);
update(l,r,d,p*2 1,mid 1,nowR);
Tree[p]=Tree[p*2] Tree[p*2 1];
Max[p]=Math.max(Max[p*2], Max[p*2 1]);
}
}
public static long query(int l,int r,int p,int cl,int cr) {
if (cl> r || cr < l)
return 0;
else if (cl >= l && cr <= r)
return Tree[p];
else
{
int mid =cl (cr-cl)/2;
return query(l, r, p * 2, cl, mid) query(l, r, p * 2 1, mid 1, cr );
// 上一行拆成三行写就和区间修改格式一致了
}
}
public static int getMax(int l,int r,int p,int cl,int cr) {
if(cl>r||l>cr) {
return 0;
}
if(cl>=l&&cr<=r)
return Max[p];
int mid=cl (cr-cl)/2;
return Math.max(getMax(l,r,p*2,cl,mid),getMax(l,r,p*2 1,mid 1,cr));
}
}Python语言
代码语言：javascript复制n,m = map(int,input().split())
value = list(map(int,input().split()))
num = []
a = [ dict() for j in range(4*n)]
# print(a)
def update(k):
node = a[k]
node['sum'] = a[k * 2]['sum'] a[k * 2 1]['sum']
node['max'] = max(a[k * 2]['max'], a[k * 2 1]['max'])
def built(k,l,r):
node = a[k]
node['l'] = l
node['r'] = r
if l == r:
node['sum'] = value[l]
node['max'] = value[l]
else:
mod = int((r l)/2)
built(2*k,l,mod)
built(2*k 1,mod 1,r)
update(k)
def chang(k,x,y):
node = a[k]
if node['l']==node['r']:
node['sum'] = y
node['max'] = y
else:
mod = int((node['r'] node['l'])/2)
if x>mod:
chang(k*2 1,x,y)
else:
chang(k*2,x,y)
update(k)
def Sum(k,l,r):
node = a[k]
if node['l']==l and node['r']==r:
return node['sum']
else:
mod = int((node['r'] node['l'])/2)
if r<=mod:
return Sum(k*2,l,r)
elif l>mod:
return Sum(k*2 1,l,r)
else:
return Sum(k*2,l,mod) Sum(k*2 1,mod 1,r)
def Max(k,l,r):
node = a[k]
if node['l'] == l and node['r'] == r:
return node['max']
else:
mod = int((node['r'] node['l']) / 2)
if r <= mod:
return Max(k * 2, l, r)
elif l > mod:
return Max(k * 2 1, l, r)
else:
return max(Max(k * 2, l, mod),Max(k * 2 1, mod 1, r))
built(1,0,n-1)
for i in range(m):
p,x,y = map(int,input().split())
if p == 1:
chang(1,x-1,y)
if p == 2:
s=Sum(1,x-1,y-1)
num.append(s)
if p == 3:
m = Max(1,x-1,y-1)
num.append(m)
for i in num:
print(i)没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
第六届——第十三届省赛题解
所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。
第六届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123284163 |
|---|---|
第七届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123285783 |
第八届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123302677 |
第九届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123303285 |
第十届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123319090 |
第十一届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123320205 |
第十二届Java省赛C组第一套 | https://laoshifu.blog.csdn.net/article/details/123413141 |
第十二届Java省赛C组第二套 | https://laoshifu.blog.csdn.net/article/details/123413271 |
第十三届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/128891276 |
第六届——第十二届省赛题解
所有题目均有题解，部分第10题非最优解，至少跑20%数据。
第六届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123440705 |
|---|---|
第七届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123442982 |
第八届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443626 |
第九届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443908 |
第十届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123444946 |
第十一届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123445601 |
第十二届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123446589 |
