A::::::::::::::::小明的彩灯：（差分）
【问题描述】
小明拥有 N 个彩灯，第 i 个彩灯的初始亮度为 ai。
小明将进行 Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。
求 Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。
【输入格式】
第一行包含两个正整数 N，Q，分别表示彩灯的数量和操作的次数。
第二行包含 N 个整数，表示彩灯的初始亮度。
接下来 Q 行每行包含一个操作，格式如下：
l r x，表示将区间 l∼r 的彩灯的亮度 +x。
【输出格式】
输出共 1 行，包含 N 个整数，表示每个彩灯的亮度。
【样例输入】
5 3 2 2 2 1 5 1 3 3 4 5 5 1 1 -100
【样例输出】
0 5 5 6 10
【评测数据规模】
对于所有评测数据，1≤N,Q≤5×105，0≤ai≤109，11≤l≤r≤N，−109≤x≤109。
#include <iostream> using namespace std; int n,m; long long a[500005]; long long b[500005]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]-a[i-1]; } for(int i=1;i<=m;i++){ int l,r; long long x; cin>>l>>r>>x; b[l]=b[l]+x; b[r+1]=b[r+1]-x; } for(int i=1;i<=n;i++){ a[i]=b[i]+a[i-1]; } for(int i=1;i<=n;i++){ if(a[i]<0){ cout<<0<<' '; }else{ cout<<a[i]<<' '; } } return 0; }
B::::::::::::::::解立方根：（二分）
题目描述
给定一个正整数 N，请你求 N 的立方根是多少。
输入描述
第 1 行为一个整数 T，表示测试数据数量。
接下来的 T 行每行包含一个正整数 N。
1≤T≤105，0≤N≤105。
输出描述
输出共 T 行，分别表示每个测试数据的答案（答案保留 3 位小数）。
输入输出样例
示例 1
输入
3 0 1 8
输出
0.000 1.000 2.000
运行限制
最大运行时间：5s
最大运行内存: 128M
#include <iostream> #include <stdio.h> #include <cmath> using namespace std; int t,n; double l(int n){ double l=0,r=1e5; double res=0; while(r>=l){ double mid=(l+r)/2.0; if(mid*mid*mid-n>1e-12){ r=mid-0.000001; }else if(mid*mid*mid-n<-1e-12){ l=mid+0.000001; res=mid; }else{ return mid; } } } int main(){ cin>>t; for(int i=0;i<t;i++){ cin>>n; printf("%.3lf\n",l(n)); } return 0; }
C::::::::::::::::：走迷宫（BFS）
题目描述
给定一个 N×M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。
已知迷宫的入口位置为(x1,y1)，出口位置为 (x2,y2)。问从入口走到出口，最少要走多少个格子。
输入描述
输入第 1行包含两个正整数 N,M，分别表示迷宫的大小。
接下来输入一个 N×M 的矩阵。若 Gi,j=1 表示其为道路，否则表示其为障碍物。
最后一行输入四个整数x1,y1,x2,y2，表示入口的位置和出口的位置。
1≤N,M≤102，0≤Gi,j≤1，1≤x1,x2≤N，1≤y1,y2≤M。
输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出 -1−1。
输入输出样例
示例 1
输入
5 5 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 5 5
输出
8
运行限制
最大运行时间：1s
最大运行内存: 128M
#include <iostream> #include <queue> using namespace std; int n,m; int ans; int a[105][105]; int b[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; bool flage; int x1,y1,x2,y2; struct zuo{ int x,y; int r; zuo(int xx,int yy,int rr){ x=xx; y=yy; r=rr; } }; queue<zuo> q; bool c[105][105]; bool check(int x,int y){ return x>0&&x<=n&&y>0&&y<=m; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } cin>>x1>>y1>>x2>>y2; q.push(zuo(x1,y1,0)); c[x1][y1]=1; while(!q.empty()){ int x=q.front().x; int y=q.front().y; int r=q.front().r; q.pop(); if(x==x2&&y==y2){ ans=r; flage=true; break; } for(int i=0;i<4;i++){ int tx=x+b[i][0]; int ty=y+b[i][1]; if(check(tx,ty)&&a[tx][ty]==1&&!c[tx][ty]){ c[tx][ty]=1; int rr=r+1; q.push(zuo(tx,ty,rr)); } } } if(flage){ cout<<ans; }else{ cout<<-1; } return 0; }
D::::::::::::::::：小明的背包（01背包问题）
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 NN 件物品，第 ii 件物品的体积为 wi，价值为 vi。
小明想知道在购买的物品总体积不超过 VV 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行每行包含 2 个正整数 w,v，表示物品的体积和价值。
1≤N≤102，1≤V≤103，1≤wi,vi≤103。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 20 1 6 2 5 3 8 5 15 3 3
输出
37
运行限制
最大运行时间：1s
最大运行内存: 128M
#include <iostream> #include <cmath> using namespace std; int n; int wi[105]; int vi[105]; int dp[105][10005]; int v; int main(){ cin>>n>>v; for(int i=1;i<=n;i++){ cin>>wi[i]>>vi[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=v;j++){ dp[i][j]=dp[i-1][j]; if(j>=wi[i]){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi[i]]+vi[i]); } } } cout<<dp[n][v]; return 0; }
