The 22nd Japanese Olympiad in Informatics (JOI 2022/2023) Final Round 题解

2024 年 8 月 11 日 8点热度 0人点赞 0条评论

交题：https://cms.ioi-jp.org/documentation

A

给一个序列 $a_1,\cdots,a_n$ 。
执行 $n$ 个操作，第 $i$ 个操作为找出第 $i$ 个数前离其最近且与它相同的数的位置，把这两个数之间的数全部赋值 $a_i$ 。求最后的序列。

考虑第 $i$ 个操作执行完后， $i$ 之前每个数一定是连续出现正好一段或不出现。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p]) 
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) {
       \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){
    return (a*b)%F;}
ll add(ll a,ll b){
    return (a+b)%F;}
ll sub(ll a,ll b){
    return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){
    a=(a%F+b%F)%F;}
inline int read()
{
    
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {
    if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) {
     x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int a[201000];
map<int,pair<int,int> > h;
int main()
{
    
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
	int n=read();
	For(i,n) a[i]=read();	
	stack <pair<pair<int,int> , int > > st;
	For(i,n) {
    
		if(st.empty() || !h.count(a[i]) || h[a[i]] ==mp(0,0) ) {
    
			st.push(mp(mp(i,i),a[i]));
			h[a[i]]=mp(i,i);
		}else {
    
			while(!st.empty()) {
    
				auto p=st.top();st.pop();
				if(p.se==a[i]) {
    
					h[p.se]=mp(p.fi.fi,i);
					st.push(mp(h[p.se],a[i]));
					break;
				}else {
    
					h[p.se]=mp(0,0);
				}
			}
		}
	}
	while(!st.empty()) {
    
		auto p=st.top();st.pop();
		Fork(i,p.fi.fi,p.fi.se) a[i]=p.se;
	}
	For(i,n) cout<<a[i]<<endl;
	
	return 0;
}

B

给 $n$ 个点对，每个点对 $(x, y)$ 可以覆盖 $S={(a,b)|b<=y,|a-x|<=y-b}$ 。问取多少个点对能覆盖所有点对。

经典题

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p]) 
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) {
       \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){
    return (a*b)%F;}
ll add(ll a,ll b){
    return (a+b)%F;}
ll sub(ll a,ll b){
    return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){
    a=(a%F+b%F)%F;}
inline int read()
{
    
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {
    if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) {
     x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int n;
vector<pair<int,int> > v;
int main()
{
    
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
	int n=read();
	For(i,n) {
    
		int a=read(),b=read();
		v.pb(mp(b-a,a+b));
	}
	sort(ALL(v));
	stack<pair<int,int> > st;	
	for(int i=0;i<n;i++) {
    
		auto now=v[i];
		while(!st.empty()){
    
			auto t=st.top();
			if(t.fi<=now.fi && t.se <=now.se) {
    
				st.pop(); 
			}else break;
		}
		st.push(now);
	}
	cout<<SI(st)<<endl;
	
	
	return 0;
}

C

考虑n*n的四连通矩阵，每次可以上下左右走一个。
格子上有颜色（黑、白），且只有白色能走。现在你希望令2个白色格子连通。一次操作为把 $n * n$ 的矩阵赋值为白色。问至少几次操作实现目标。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p]) 
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) {
       \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){
    return (a*b)%F;}
ll add(ll a,ll b){
    return (a+b)%F;}
ll sub(ll a,ll b){
    return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){
    a=(a%F+b%F)%F;}
inline int read()
{
    
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {
    if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) {
     x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int r,c,n,sx,sy,tx,ty;
int dir[4][2]={
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};
bool inside(int x,int y) {
    
    return 1<=x && x<=r &&1<=y &&y<=c;
}
vector<string> a;
bool state(int x,int y){
    
	return a[x-1][y-1]=='#';
}
pair<int,int> dis[6000000+10];
int id(int x,int y) {
    
	return c*(x-1)+y;
}
void pri(pair<int,int> p) {
    
	printf("(%d,%d)",p.fi,p.se);
}
void pri(vector<pair<int,int> > v) {
    
	for(auto a:v) {
    
		pri(a);cout<<":";
		int x=a.fi,y=a.se;
		pri(dis[id(x,y)]);cout<<" ";
	}cout<<endl;
}
void bfs() {
    
	vector<pair<int,int> > q0,qa,qb;
	int nowdis=0;
	For(i,r*c) dis[i]=mp(INF,INF);
	dis[id(sx,sy)]=mp(0,n);
	q0.pb(mp(sx,sy));
	while(SI(q0)) {
    
		int nxdis=nowdis+1;
		// relax q0
		for(int i=0;i<SI(q0);i++) {
    
			auto t=q0[i];
			int x=t.fi,y=t.se;
			auto now_dis=dis[id(x,y)];
			Rep(di,4) {
    
				int nx=x+dir[di][0],ny=y+dir[di][1];
				if(!inside(nx,ny)) continue;
				if(dis[id(nx,ny)]!=mp(INF,INF)) continue;
				int sta=state(nx,ny);
				if(sta==0) {
     //white
					dis[id(nx,ny)] = now_dis;
					q0.pb(mp(nx,ny));
				}
			}
		}	
		// q0 -> qa

		Rep(i,SI(q0)) {
    
			qa.pb(q0[i]);
		}
		Rep(i,SI(qa)) {
    
			auto t=qa[i];
			int x=t.fi,y=t.se;
			auto now_dis=dis[id(x,y)];
			Rep(di,2) {
    
				int nx=x+dir[di][0],ny=y+dir[di][1];
				if(!inside(nx,ny)) continue;
				if(dis[id(nx,ny)]!=mp(INF,INF)) continue;
				int sta=state(nx,ny);
				if(now_dis.fi==nowdis) {
    
					dis[id(nx,ny)] = mp(nxdis,1);
				}else if(now_dis.se+1<=n){
    
					dis[id(nx,ny)] = mp(nxdis,now_dis.se+1);
				}else continue;
				qa.pb(mp(nx,ny));
				
			}
		}
		//qa -> ab
		Rep(i,SI(qa)) {
    
			qb.pb(qa[i]);
		}
		
		Rep(i,SI(qb)) {
    
			auto t=qb[i];
			int x=t.fi,y=t.se;
			auto now_dis=dis[id(x,y)];
			Fork(di,2,3) {
    
				int nx=x+dir[di][0],ny=y+dir[di][1];
				if(!inside(nx,ny)) continue;
				if(dis[id(nx,ny)]!=mp(INF,INF)) continue;
				int sta=state(nx,ny);
				if(now_dis.fi==nowdis) {
    
					dis[id(nx,ny)]=mp(nxdis,n+1);
				}else if(now_dis.fi==nxdis && now_dis.se<n &&  n+1<=2*n ) {
    
					dis[id(nx,ny)]=mp(nxdis,n+1);
				}else if(now_dis.fi==nxdis && now_dis.se==n && n+2<=2*n ) {
    
					dis[id(nx,ny)]=mp(nxdis,n+2);
				}else if(now_dis.fi==nxdis && now_dis.se>n && now_dis.se+1<=2*n ) {
    
					dis[id(nx,ny)]=mp(nxdis,now_dis.se+1);
				}else continue;
				qb.pb(mp(nx,ny));
			}
		}
// 
// cout<<nowdis<<endl;
// cout<<"q0"<<endl;
// pri(q0);
// cout<<"qa"<<endl;
// pri(qa);
// cout<<"qb"<<endl;
// pri(qb);
// 
		
		
		
		//ab -> qc(q0)
		q0.resize(0);
		for(int i=0;i<qb.size();i++) {
    
			
			auto t=qb[i];
			int x=t.fi,y=t.se;
			auto now_dis=dis[id(x,y)];
			if(now_dis.fi==nxdis)
				q0.pb(qb[i]);
		}
		qa.resize(0),qb.resize(0);
		nowdis++;
	}
// For(i,r) {
    
// For(j,c) pri(dis[id(i,j)]),putchar(' ');
// puts("");
// }
	cout<<dis[id(tx,ty)].fi<<endl;

}
int main()
{
    
// freopen("C.in","r",stdin);
// freopen(".out","w",stdout);
	cin>>r>>c>>n;
// For(i,r) For(j,c) cout<<id(i,j)<<' ';
	cin>>sx>>sy>>tx>>ty;
	
    For(i,r) {
    
    	string s;
    	cin>>s;
    	a.pb(s);
    }
	bfs();
	return 0;
}