本鶸鸡于本月10号参加了蔽校的选拔赛，成绩差的死，大部分的题都是赛后花了好长时间才补出来的，其中有些题还是靠QAQorz大佬帮忙才能解决，感谢Qls对我的帮助~接下来就附带上我的暴力题解，大佬们有更好的想法请一定要告诉我啊~
Problem H: 逃出*
题目链接：http://113.240.233.2:8081/JudgeOnline/problem.php?cid=1015&pid=7
题目描述：给你一个n*m的图，地图上'.'代表可以走的地方，而'#'代表障碍物不能走，
'A'代表小偷，'B'代表警察，'E'代表出口。每个位置可以向（上，下，左，
右）四个方向走一格，花费一个单位时间，现在给出小偷，警察和出口所在
位置，警察为了捉住小偷会先到出口的位置守株待兔，如果警察在小偷之前
或同时到达出口，或者小偷到达不了出口，输出"No",否则输出"Yes"。
数据范围：T<=50，n<=500,m<=500
这个因为是两个起点一个终点，所以完全可以从终点开始搜，完全没必要跑两个bfs。但是比赛时一直在纠结警察会不会在路上抓到小偷，然后思考了半小时，默默地看着好几个人A了，最后实在没办法了，就试了下不能在路上抓到小偷，，然后就A了，然后就开始思考为啥自己那么喜欢多想，不然就是1A了-_-||
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int w,h,ans;
int sx,sy,k;
char mp[25][25];
int vis[25][25];
struct node{
int x,y,step;
}nw,nxt;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int bfs(int x,int y){
nw.x=x,nw.y=y,nw.step=0;
vis[y][x]=1;
queue<node> q;
q.push(nw);
while(!q.empty()){
nw=q.front();q.pop();
if(mp[nw.y][nw.x]=='*'){
memset(vis,0,sizeof(vis));
vis[nw.y][nw.x]=1;
mp[nw.y][nw.x]='.';
if(k==1){
k--;
return nw.step;
}
k--;
return nw.step+bfs(nw.x,nw.y);
}
for(int i=0;i<4;i++){
nxt.x=nw.x+dx[i],nxt.y=nw.y+dy[i];
if(nxt.x>=0 && nxt.x<h && nxt.y>=0 && nxt.y<w && vis[nxt.y][nxt.x]==0 && mp[nxt.y][nxt.x]!='x'){
nxt.step=nw.step+1;
vis[nxt.y][nxt.x]=1;
q.push(nxt);
}
}
}
return 0;
}
int main(){
while(~scanf("%d%d",&h,&w)){
if(w==0 && h==0) break;
for(int i=0;i<w;i++){
scanf("%s",mp[i]);
}
k=0,ans=0;
for(int i=0;i<w;i++){
for(int j=0;j<h;j++){
if(mp[i][j]=='o'){
sx=j,sy=i;
}
if(mp[i][j]=='*'){
k++;
}
}
}
ans=bfs(sx,sy);
if(k>0){
printf("-1\n");
}
else{
printf("%d\n",ans);
}
}
}
Problem I: 简单题
题目链接：http://113.240.233.2:8081/JudgeOnline/problem.php?cid=1015&pid=8
题目描述：给你N个数Q次操作。其中每次操作包括1.从l到r的所有元素都加x和查询，2.求第l个元素到第r个元素间的数据的平均值，保留两位小数
数据范围：N <= 100000,Q <= 100000，数列中的每个元素 <= 100，0<=X<=100
这题就是一个纯裸的线段树，但是比赛时由于带的板子出了问题，没发现&&忘记开long long猛WA3发-_-!，还好及时发现，最后竟然还拿了本题的一血（雾。所以这题就是带副没有错误的好板子（-_-!）和记得开long long就行~
#include <cstdio>
typedef long long ll;
const int maxn=1e5+7;
int t,n,q;
int a[maxn];
struct node{
int l,r;
ll sum,lazy;
}tree[maxn*4];
void push_down(int i){
if(tree[i].lazy!=0 && tree[i].l!=tree[i].r){
ll x=tree[i].lazy;
tree[i*2].lazy+=x;
tree[i*2+1].lazy+=x;
tree[i*2].sum+=x*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].sum+=x*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lazy=0;
}
return;
}
void push_up(int i){
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
return;
}
void build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
tree[i].lazy=0;
if(l==r){
tree[i].sum=a[l];
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
}
void update(int i,int l,int r,ll x){
push_down(i);
if(tree[i].r==r &&tree[i].l==l){
tree[i].sum+=x*(r-l+1);
tree[i].lazy+=x;
return;
}
int mid=(tree[i].l+tree[i].r)/2;
if(r<=mid) update(i*2,l,r,x);
else if(l>mid) update(i*2+1,l,r,x);
else{
update(i*2,l,mid,x);
update(i*2+1,mid+1,r,x);
}
push_up(i);
}
ll query(int i,int l,int r){
push_down(i);
if(tree[i].l==l &&tree[i].r==r){
return tree[i].sum;
}
int mid=(tree[i].l+tree[i].r)/2;
if(l>mid) return query(i*2+1,l,r);
else if(r<=mid) return query(i*2,l,r);
else{
return query(i*2,l,mid)+query(i*2+1,mid+1,r);
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
scanf("%d",&q);
int x;
for(int i=0;i<q;i++){
scanf("%d",&x);
if(x){
int l,r;
scanf("%d%d",&l,&r);
double ans=1.0*query(1,l,r)/(r-l+1);
printf("%.2f\n",ans);
}
else{
int l,r;
ll s;
scanf("%d%d%lld",&l,&r,&s);
update(1,l,r,s);
}
}
}
}