备孕百度之星-9月23日

明天考试，慌得一批。希望可以把自己学过的都做会。

网格路径

//#include <bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int n;
// 快读
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 

ll llread(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}


char chs[11][11];
int vis[11][11];
int l = 0, r = 0;

void dfs1(int x, int y){
	if(l == 1) return ;

	if(x >= n || y >= n) return ;
	if(chs[x][y] == '#') return ;
	if(vis[x][y]) return ;
	if(x == (n-1) && y == (n-1)) {
		l = 1;
		return ;
	}
	vis[x][y] = 1;
	dfs1(x, y+1);
	dfs1(x+1, y);
}
void dfs2(int x, int y){
	if(r == 1) return ;

	if(x >= n || y >= n) return ;
	if(chs[x][y] == '#') return ;
	if(vis[x][y]) return ;
	if(x == (n-1) && y == (n-1)) {
		r = 1;
		return ;
	}
	vis[x][y] = 1;
	
	dfs2(x+1, y);
	dfs2(x, y+1);
}


int main()
{
	int T;
	read(T);
	while(T-- > 0){
		read(n);
//		cout << n; 
		for(int i = 0; i < n; i++) 
			for(int j = 0; j < n; j++) {
				cin >> chs[i][j];
			}
		for(int i = 0; i < n; i++) memset(vis[i], 0, sizeof(vis[i]));
		int res = 0;
		if(chs[0][1] == '.'){
			dfs1(0,0);
			res += l;
		}
		
		if(chs[1][0] == '.'){
			dfs2(1,0);
			res += r;
		}
		if(chs[0][0] == '#'){
			
		cout << 0 << endl;
		}else{
			
		cout << res << endl;
		}
		l = 0;//忘了这里，改了好久
		r = 0;
	} 
}

赛前狂wa是好事，要记得每次进入while(T)的时候，做好初始化工作。

虫族基地

有时wa了好多次，没有考虑所有情况。一开始只想到两个虫族基地相连，然后枚举横向和纵向的奇偶性，推导出相连的时间，后面又自己想到可以某个虫族基地去起始点。后面看题解才意识到独占一列的情况。（看了数据量，没有bfs，这点倒是进步了）

#include <bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int n;
// 快读
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 

ll llread(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}

int main(){
	int T;
	ll n,m,x1,x2, i;
	read(T);
	while(T-- > 0){
		llread(n);
		llread(m);
		llread(x1);
		llread(x2);
		if(x1 == 1 || x2 == m) {
			cout << 0 << endl;
			continue;
		}
		ll c1 = x1 - 1;//占起点 
		ll c2 = m - x2;//占终点 
		if(x1 == x2 || abs(x1 - x2) == 1){
			i = (n-2+1)/2;
			ll res = min(min(c1, n-1), min(c2, i));//考虑独占一列 
			cout << (res * res) << endl;
		}else{
			i = abs(x1 - x2) - 1 + n-1;
			ll l = i / 2;
			ll res = min(min(c1, n-1), min(c2,l));
			cout << (res * res) << endl;
		}
		
	}
}