2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

C. Connect the Points

本场比赛的小水题。

题目大意：给定平面上3个点，要求给出至多100条横或竖的线段使3个点连通。

本题最大的难点在于理解题意：我一开始以为这道题的意思是要用这些线段构造一条简单路径把三个点连起来，然后WA飞了；后来才知道不一定非得是简单路径，只要连通就行了，然后这题的做法就很trivial了：假设x坐标从小到大排序为(x1,y1)，(x2,y2)，(x3,y3)，那么三条线段就是(x1,y1,x2,y1)，(x2, min{y1,y2,y3}, x2, max{y1,y2,y3} )，(x2,y3,x3,y3)。

#define INL inline
#define REG register
#define U unsigned
#define M ((l+r)>>1)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <memory.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct Point{
    ll x,y;
}seq[6][3];
#define absval(x) max((x),(-(x)))
ll dist(Point p1,Point p2){
    return absval(p1.x-p2.x)+absval(p1.y-p2.y);
}
bool cmp(Point p1,Point p2){
    return p1.x==p2.x?p1.y<p2.y:p1.x<p2.x;
}

int n;
struct Segment{
    int x1,y1,x2,y2;
    Segment(){
        x1=y1=x2=y2=0;
    }
    Segment(int _x1,int _y1,int _x2,int _y2){
        x1=_x1;
        y1=_y1;
        x2=_x2;
        y2=_y2;
    }
}segs[100];

int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    Point p[3];
    for(int i=0;i<3;i++){
        cin>>p[i].x>>p[i].y;
    }
    sort(p,p+3,cmp);
    ll miny=min(p[0].y,min(p[1].y,p[2].y)),maxy=max(p[0].y,max(p[1].y,p[2].y));
    if(p[0].x!=p[1].x){
        segs[n++]=Segment(p[0].x,p[0].y,p[1].x,p[0].y);
    }
    if(p[1].x!=p[2].x){
        segs[n++]=Segment(p[2].x,p[2].y,p[1].x,p[2].y);
    }
    if(miny!=maxy){
        segs[n++]=Segment(p[1].x,miny,p[1].x,maxy);
    }
    cout<<n<<endl;
    for(int i=0;i<n;i++){
        cout<<segs[i].x1<<' '<<segs[i].y1<<' '<<segs[i].x2<<' '<<segs[i].y2<<endl;
    }
    return 0;
}

D. Deletive Editing

本场比赛的大水题。

题目大意：给一个字符串S，一个目标串T，一次删除操作为：指定一个字母，删除字符串中从左到右数的第一个这个字母（如"DETERMINED"，进行一次删除’E’的操作后变为"DTERMINED"）；问S经过有限次删除操作之后能否得到T。

考虑得不到T的情况：首先如果T中出现了S没有出现过的字母的话肯定是得不到T的；除此之外还有一种可能：S=“ABA”，T=“AB”，这时也得不到T，因为我们删不掉B后面那个A。

有很多乱搞的方法都能判断出这两种得不到T的情况，我的做法类似于双指针：用一个计数数组cntr[26]记录每个字母的出现次数，i最初位于S的最右端，j最初位于T的最右端。如果S[i]!=T[j]，那么cntr[S[i]-‘A’]++，i–；如果S[i]==T[j]，此时我们需要检查cntr[S[i]-‘A’]是否为0；如果不为0，说明出现了"挡在另一个字母后面的删不掉的相同字母"，直接false；否则说明这个匹配可以实现，i–，j–；最终退出的时候如果j没有完全退出T，也就是T没有完成匹配，那也是false。

后来又口胡了一个更接近此题本质的写法：每个T中的字符都找到S中从右往左数的第一个相同字符的位置，如果对应位置出现了逆序对则说明得不到T。

#define INL inline
#define REG register
#define U unsigned
#define M ((l+r)>>1)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <memory.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int cntr[26];
int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    while(n--){
        string f,t;
        cin>>f>>t;
        int j=t.length()-1;
        bool ans=1;
        for(int i=f.length()-1;i>=0&&j>=0;i--){
            if(f[i]==t[j]){
                if(cntr[t[j]-'A']){
                    ans=0;
                    break;
                }
                else{
                    j--;
                }
            }
            else{
                cntr[f[i]-'A']++;
            }
        }
        if(!ans||j>=0){
            cout<<"NO"<<endl;
        }
        else{
            cout<<"YES"<<endl;
        }
        memset(cntr,0,sizeof(cntr));
    }
    return 0;
}

I

交互题

一张n*m的地图里有两个宝藏，有如下两种操作：

1. SCAN x y 系统返回(x, y)到两个宝藏的曼哈顿距离和

2. DIG x y 系统返回(x, y)处是否有宝藏

要求在7次操作内找到2个宝藏

设宝藏四个坐标为x1, x2, y1, y2

查询(1, 1) 设返回值为a，有a = (x1+x2)+(y1+y2)-4

查询(n, 1) 返回b = 2m-(x1+x2)+(y1+y2)-2

推出 x1+x2 = (a-b+2+2m)/2

y1+y2 = a-(x1+x2)+4

查询((x1+x2)/2, 1) 返回 c = x1-x2+y1+y2-2

查询(1, (y1+y2)/2) 返回 d = x1+x2-2+y1-y2

推出 x1 = ((x1+x2)+c-(y1+y2)+2)/2 y1 = ((y1+y2)+d-(x1+x2)+2)/2

于是x1x2y1y2已知

先挖掘x1y1 若没有宝藏则宝藏为x1y2 x2y1

否则挖掘 x2y1

PS ：珍爱生命，交互题远离stdio, 尽量用iostream（（（

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;

void work(){
	int n, m;
	cin>>n>>m;
	int a, b, c, d;
	int xx, yy;
	int x1, y1, x2, y2;
	printf("SCAN 1 1\n");
	fflush(stdout);
	cin>>a;
	printf("SCAN %d 1\n", n);
	fflush(stdout);
	cin>>b;
	xx = (a-b+2+2*n)/2;
	yy = a - xx + 4;
	printf("SCAN %d 1\n", xx/2);
	fflush(stdout);
	cin>>c;
	printf("SCAN 1 %d\n", yy/2);
	fflush(stdout);
	cin>>d;
	
	x1 = (xx+c-yy+2)/2;
	x2 = xx-x1;
	y1 = (yy+d-xx+2)/2;
	y2 = yy-y1;
	
	printf("DIG %d %d\n", x1, y1);
	fflush(stdout);
	int e;
	cin>>e;
	if(e == 1){
		printf("DIG %d %d\n", x2, y2);
		fflush(stdout);
		cin>>e;
	}else{
		printf("DIG %d %d\n", x1, y2);
		fflush(stdout);
		cin>>e;
		printf("DIG %d %d\n", x2, y1);
		fflush(stdout);
		cin>>e;
	}
}

int main(){
	int t;
	cin>>t;
	
	while(t--)work();
	
	return 0;
}

J. Job Lookup

题目大意：给定一个n*n的矩阵，要求构造一棵包含从1到n的所有数字的二叉搜索树，设i和j在二叉搜索树上的距离为dij，要求最小化${\sum }_{i=1}^n{\sum }_{j=1}^n{c}_{\text{ij}}{d}_{\text{ij}}$，输出二叉搜索树的构造方案（即从1到n每个节点连接的父亲，根节点的父亲为0）。n的规模是200。

一个容易想到的想法是dp[i][j]表示[i,j]这个区间内构造出的二叉搜索树的最小花费，然后很容易想到这样定义的dp是不具有最优子结构的，假了。

然后不太容易想到一个更类似于贪心的想法：dp[i][j]表示[i,j]"向区间外连出去"的最小花费，这是具有最优子结构的，而且转移也比较好想：dp[i][j]=dp[i][k-1]+dp[k+1][j]+sum(1,i-1,I,j)+sum(j+1,n,I,j)，其中sum(L,R,l,r)表示c从(L,l)到(R,r)的子矩阵的二维区间和（容易想到这个子矩阵的意义是[L,R]到[l,r]中每一个数互连的花费），这个转移的意义就是[i,j]这个区间构成的二叉搜索树的子树必然会以某个数为根，然后一旦添加了这个根，虽然我们还不知道这棵树的具体形态，但[i,j]这个区间内的所有数向区间外的所有数互连的代价必然都多加了一倍（因为向k走是多走了1个距离），最后就能最小化代价了。

另外这题要求我们输出方案，所以我们还需要记录对于每一个区间[i,j]，转移的最优的k，记为root[i][j]，递归得到方案即可（看代码就清楚了）。

#define INL inline
#define REG register
#define U unsigned
#define M ((l+r)>>1)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <memory.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=233;
const ll inf=1145141919810000000;
inline int read(){
    int sum=0,sign=1;
    char tmp=getchar();
    while(tmp<'0'||tmp>'9'){
        sign=tmp=='-'?-1:1;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return sum*sign;
}
ll c[maxn][maxn],dp[maxn][maxn];
int root[maxn][maxn],ans[maxn];
ll sum(int L,int R,int l,int r){
    if(L>R||l>r){
        return 0;
    }
    return c[R][r]-c[L-1][r]-c[R][l-1]+c[L-1][l-1];
}
void display(int fa,int l,int r){
    int pos=root[l][r];
    //cout<<pos<<' '<<l<<' '<<r<<endl;
    ans[pos]=fa;
    if(l>=r){
        return;
    }
    display(pos,l,pos-1);
    display(pos,pos+1,r);
}
int main(){
    freopen("J.in","r",stdin);
    freopen("J.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ll x=read();
            c[i][j]=x+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=sum(1,i-1,i,i)+sum(i+1,n,i,i);
        root[i][i]=i;
    }
    for(int len=2;len<=n;len++){
        for(int l=1,r=l+len-1;r<=n;l++,r++){
            dp[l][r]=inf;
            for(int k=l;k<=r;k++){
                ll newval=dp[l][k-1]+dp[k+1][r]+sum(1,l-1,l,r)+sum(r+1,n,l,r);
                if(newval<dp[l][r]){
                    dp[l][r]=newval;
                    root[l][r]=k;
                }
            }
        }
    }
    display(0,1,n);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
    return 0;
}

L

给一张有向图和一个起点s，要求找一个终点t（不与s重叠），使得s到t有两条没有公共点的简单路径（s,t两点除外）

以s的所有儿子为根进行DFS，如果两棵不同根的BFS树有交集，那么就找到了一个t

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int maxn = 1e6+5;

struct mode{
	int to, next;
}edge[maxn];

int head[maxn];
int cnt = 0;
int n, m, root;
int fa[maxn] = {0};
int vis[maxn] = {0};
int num1 = 0, num2 = 0;
int ans1[maxn] = {0};
int ans2[maxn] = {0};

void join(int x, int y){
	edge[++cnt].next = head[x];
	edge[cnt].to = y;
	head[x] = cnt;
}

void dfs(int x, int f, int top){
	if(x == root)return;
	if(vis[x] != 0 && vis[x] != top){
		int p = x;
		while(p != root){
			ans1[++num1] = p;
			p = fa[p];
		}
		ans1[++num1] = root;
		ans2[++num2] = x;
		p = f;
		while(p != root){
			ans2[++num2] = p;
			p = fa[p];
		}
		ans2[++num2] = root;
		
		cout<<"Possible"<<endl;
		cout<<num1<<endl;
		for(int i = num1;i >= 1;i--){
			printf("%d ", ans1[i]);
		}cout<<endl;
		cout<<num2<<endl;
		for(int i = num2;i >= 1;i--){
			printf("%d ", ans2[i]);
		}cout<<endl;
		exit(0);
	}
	if(vis[x] == top)return;
	vis[x] = top;
	fa[x] = f;
	
	for(int i = head[x];i;i = edge[i].next){
		int to = edge[i].to;
		dfs(to, x, top);
	}
}

int main(){
	
	cin>>n>>m>>root;
	
	for(int i = 1;i <= m;i++){
		int x, y;
		scanf("%d%d", &x, &y);
		join(x, y);
	}
	
	for(int i = head[root];i;i = edge[i].next){
		dfs(edge[i].to, root, edge[i].to);
	}
	
	cout<<"Impossible"<<endl;
	
	return 0;
}