T1 VUK P7775

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

struct node{
	int x,y;
};

int dis[4][2]={0,1,1,0,0,-1,-1,0};
int n,m;
char c;
int s[505][505];
node hunt[300000];
int hl;
int sx,sy,ex,ey;
bool vis[505][505];
queue<node>q;

bool check(int check_x){
	while(!q.empty()) q.pop();//因为可能队列还没空就return 1，所以每次检验要清空队列
	memset(vis,0,sizeof(vis));
	q.push({sx,sy});
	vis[sx][sy]=1;
	while(!q.empty()){
		int nx=q.front().x,ny=q.front().y;
		q.pop();
		if(nx==ex&&ny==ey)return 1;
		for(int i=0;i<4;i++){
			int tx=nx+dis[i][0],ty=ny+dis[i][1];
			if(tx>0&&ty>0&&tx<=n&&ty<=m&&!vis[tx][ty]&&s[tx][ty]>=check_x){
				vis[tx][ty]=1;
				q.push({tx,ty});
			}
		}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			s[i][j]=1e9;
			if(c=='+') q.push({i,j}),s[i][j]=0;
			if(c=='V') sx=i,sy=j;
			if(c=='J') ex=i,ey=j;
		}
	}
	while(!q.empty()){//预处理
		int nx=q.front().x,ny=q.front().y;
		q.pop();
		for(int i=0;i<4;i++){
			int tx=nx+dis[i][0],ty=ny+dis[i][1];
			if(tx>0&&ty>0&&tx<=n&&ty<=m&&s[tx][ty]>s[nx][ny]+1){
				s[tx][ty]=s[nx][ny]+1;
				q.push({tx,ty});
			}
		}
	}
	int left=0,righ=min(s[sx][sy],s[ex][ey]),mid,ans;
	while(left<=righ){
		mid=left+righ>>1;
		if(check(mid)){
			ans=mid;
			left=mid+1;
		}
		else righ=mid-1;
	}
	cout<<ans<<'\n';
	return 0;
}

T2 统计数字 P1097

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

const int M=2e5+5;
int n,a[M],t=-1,s;

int main(){
	cin>>n;
	for(int i=0;i<n;++i) cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<=n;++i){
		if(i==n||t!=a[i]){
			if(t!=-1) printf("%d %d\n",t,s);
			t=a[i],s=0;
		}
		s++;
	}
	return 0;
}

T3 数字统计 P1179

# include<iostream>
using namespace std;

int l,r,sum=0;

int f(int x){
	int s=0;
	while(x){
		s+=(x%10==2);
		x/=10;
	}
	return s;
}

int main(){
	cin>>l>>r;
	for(int i=l;i<=r;++i) sum+=f(i);
	cout<<sum;
	return 0;
}

T4 分巧克力 P8647

# include<iostream>
using namespace std;
# define max(a,b) a>b?a:b

const int M=1e5+5;
int n,k,h[M],w[M],ma=0;
int l,r,mid,ans;

int cnt(int i,int x){
	return (h[i]/x)*(w[i]/x);
}

bool check(int x){
	int s=0;
	for(int i=0;i<n;++i) s+=cnt(i,x);
	return s>=k;
}

int main(){
	cin>>n>>k;
	for(int i=0;i<n;++i){
		cin>>h[i]>>w[i];
		ma=max(h[i],ma);
		ma=max(w[i],ma);
	}
	l=1,r=ma;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}

T5 全球变暖 P8662

# include<iostream>
# include<queue>
using namespace std;

struct point{
	int x,y;
};

point make(int a,int b){
	point t;
	t.x=a,t.y=b;
	return t;
}

const int M=1e3+5;
int n,sum=0;
char a[M][M];
bool vis[M][M]={0};
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
queue<point> q;

void bfs(int x,int y){
	bool flag=0;
	while(!q.empty()) q.pop();
	q.push(make(x,y));
	vis[x][y]=1;
	while(!q.empty()){
		point t=q.front();
		q.pop();
		int x1=t.x,y1=t.y;
		bool f=1;
		for(int i=0;i<4;++i){
			int x2=x1+dx[i],y2=y1+dy[i];
			if(!vis[x2][y2]&&a[x2][y2]=='#'){
				q.push(make(x2,y2));
				vis[x2][y2]=1;
			}
			if(a[x2][y2]=='.') f=0;
		}
		if(f) flag=(f||flag);
	}
	if(!flag) ++sum;
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j) cin>>a[i][j];
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(!vis[i][j]&&a[i][j]=='#') bfs(i,j);
		}
	}
	cout<<sum;
	return 0;
}