P1141 70ptsTLE

#include<bits/stdc++.h>
using namespace std;
char a[2001][2001];
bool vis[2001][2001];
queue <int> x,y;
int p1[4]={1,-1,0,0},p2[4]={0,0,1,-1};
int n,m;
void bfs(int x1,int y1)
{
	
	for(int i=0;i<=3;i++)
	{
		if(x1+p1[i]>0&&x1+p1[i]<=n&&y1+p2[i]>0&&y1+p2[i]<=n&&!vis[x1+p1[i]][y1+p2[i]])
		{
			if(a[x1+p1[i]][y1+p2[i]]!=a[x1][y1])
			{
				x.push(x1+p1[i]);
				y.push(y1+p2[i]);
				vis[x1 + p1[i]][y1+p2[i]]=1;//就这里
			}
		 }
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
//			a[i][j]=getchar();
			cin >> a[i][j];
		}
//		getchar();
	}
	for(int i=1;i<=m;i++)
	{
		memset(vis,0,sizeof(vis));
		int x1,y1;
		cin>>x1>>y1;
		vis[x1][y1]=1;
		x.push(x1);
		y.push(y1);
		int js=0;
		while(!x.empty())
		{
			js++;
			bfs(x.front(),y.front());
// 			cout << x.front() <<' '<<y.front()<<endl;
			x.pop();
			y.pop();
		}
		cout<<js<<'\n';
	}
	return 0;
}

P1020 100pts WA

#include<bits/stdc++.h>
using namespace std;
int p1[100001],p2[100001];
int a[100001];
int n,tot=0;
int work1(int x){
	int l=0,r=tot,ans=1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]<=x){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
			ans=mid+1;
		}
	}
	return ans;
}
int work(int x){
	int l=0,r=tot,ans=1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]>=x){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
			ans=mid+1;
		}
	}
	return ans;
}
int main(){
	int n=0;
	while(cin>>p1[++n]);
	for(int i=1;i<=n;i++){
		if(p1[i]<=a[tot]){
			a[++tot]=p1[i];
		}
		else{
			a[work1(p1[i])]=p1[i];
		}
	}
	printf("%d\n",tot);
	for(int i=0;i<=tot;i++){
		a[i]=0;
	}
	tot=0;
	for(int i=1;i<=n;i++){
		if(p1[i]>=a[tot]){
			a[++tot]=p1[i];
		}
		else{
			a[work(p1[i])]=p1[i];
		}
	}
	printf("%d",tot);
	return 0;
}

P1182 80pts

#include<bits/stdc++.h>
using namespace std;
long long a[100001];
int main()
{
	long long n,m,l=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
        l=max(l,a[i]);
		a[i]+=a[i-1];
	}
	long long ans,r=a[n],mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		long long js1=0,js2=0;
		long long i=0;
		while(i<=n)
		{
			if(a[i]-js1>=mid)
			{
				js2++;
				js1=a[i-1];
			}
			i++;
		}
		if(js2>=m)
		{
			l=mid+1;
			ans=mid;
		}
		else
		{
			r=mid-1;
            ans=mid-1;
		}
	}
	cout<<max(ans,l);
	return 0;
}

P1256 70pts

#include<bits/stdc++.h>
using namespace std;
char a[200][200];
int ans[200][200];
bool vis[200][200];
queue<int> x,y;
int p1[4]={0,0,1,-1},p2[4]={1,-1,0,0};
int m,n;
void read(char &ch){
	while(ch>'1'||ch<'0'){
		ch=getchar();
	}
}
void bfs(int x1,int y1,int x2,int y2){
	//printf("%d %d %d %d\n",x1,y1,x2,y2);
	if(a[x1][y1]!='1')
		if(ans[x1][y1]==-1)
			ans[x1][y1]=abs(x1-x2)+abs(y1-y2);
		else
			ans[x1][y1]=min(ans[x1][y1],abs(x1-x2)+abs(y1-y2));
	for(int i=0;i<=3;i++){
		if(!vis[x1+p1[i]][y1+p2[i]]&&x1+p1[i]>=1&&x1+p1[i]<=n&&y1+p2[i]>=1&&y1+p2[i]<=m){
			vis[x1+p1[i]][y1+p2[i]]=1;
			x.push(x1+p1[i]);
			y.push(y1+p2[i]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			read(a[i][j]);
			ans[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='1'){
			for(int k1=1;k1<=n;k1++){
				for(int k2=1;k2<=m;k2++){
					vis[k1][k2]=0;
				}
			}
				x.push(i);
				y.push(j);
				while(!x.empty()){
					bfs(x.front(),y.front(),i,j);
					x.pop();
					y.pop();
				}
			}
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='1')
				printf("0 ");
			else
				printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}

实在是调不动了awa