2023CCPC哈尔滨站

2023CCPC哈尔滨站https://contest.ucup.ac/contest/1412

B. Memory 

int main() {
    int n;
    std::cin >> n;
 
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
 
    std::string res;
 
    int x = 0, Dec = 0;
    // 整数位 x 和 小数位符号 Dec
 
    for (int i = 0; i < n; i++) {
        x += a[i];
 
        if (x != 0)
            res.push_back(x > 0 ? '+' : '-');
        else {
            if (Dec != 0)
                res.push_back(Dec > 0 ? '+' : '-');
            else
                res.push_back('0');
        }
 
        if (std::abs(x) & 1)
            Dec = (x > 0 ? 1 : -1);
        x /= 2;
    }
 
    std::cout << res;
}

G. The Only Way to the Destination

思路：

题意中给出了几个很重要的信息：

1、墙只有纵向
2、爱丽丝确保在放置 k 面墙后，所有空网格都保持连接，迷宫中至少有一个空网格。并且保证不同的墙没有共同的网格
3、保证每对空格之间至少有一条简单路径相连

本来的想法是bfs，但是数据量过大，想想看如果有多条简单路径时会怎么样。

首先对两列，如果左边连续的空网格和右边连续的空网格结合在一起，那么肯定不行，比如第三个样例，第二列两个连续的空网格和第三列两个连续的空网格形成了一个2*2的空格，这时不管其他地方怎么样，一定不可能满足条件了。

因此如果 n > 1 时，每两列必须要有一堵墙，否则两个空列接在一起一定不可能满足条件，这样的话 m 最多只有2k+1，否则一定不可能满足条件。而 n = 1时由于一定会有一条简单路径，而且也不可能出现其他简单路径，这时一定满足条件，特判直接返回即可。

其次，如果有多条简单路径，还不是连续网格相接，那么一定是环造成的。一个最简单的环就是一个矩形，这时它两边会有两个竖线（也就是连续空网格）将上下两条线相连，从左到右画的话，在连上后面的竖线时，就会导致成环，也就是把两个联通的部分又连接起来了，而成环的话，就必须有一条竖线把联通部分再相连。因此我们只用看后面的这段连续的空网格是否将多个联通的部分连接起来即可。

我们可以从左到右枚举列，对每一列，从上到下枚举连续空网格区间，看他是否将前面多个联通的部分再次相连。也就是枚举前面一列对应的区间内的空网格区间，判断两两是否联通，如果有联通，就说明有环，答案就是NO，否则将它们联通起来。

如何判断联通：

• 如果前面一列没区间，说明这一块是凭空产生的，分配一个颜色
• 有区间的话如果不连通的颜色都唯一，这时这几种颜色联通，并查集维护一致性
• 如果某个联通的颜色不唯一，说明无解

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
 
struct wall
{
	int x1, x2, y;
	
	bool operate<(wall x) // 重载小于号，用于排序 
	{
		if (y != x.y)
			return y<x.y;
		
		return x1 < x.x1;
	}
	
}w[10000];
 
int n, m, k;
 
struct node
{
	int l, r, color; // 记录连续空区间的左右端点，及其颜色 
};
 
vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间 
 
int c, f[10000];
 
// 使用并查集，保持统一性 
int find(int x)
{
	while (x != f[x])
		x = f[x];
	return x;
}
 
void merge(int x, int y)
{
	f[find(y)] = find(x);
}
 
int findl(int l)
{
	for (int i=0; i<lst.size(); ++i)
		if (lst[i].r >= l)
			return i;
	return -1;
}
 
int findr(int r)
{
	for (int i=lst.size()-1; i>=0; --i)
	{
		if (lst[i].l <= r)
			return i;
	}
	return -1;
}
 
bool solve()
{
	if (n == 1)
		return true;
	for (int i=1; i<10000; ++i)
		f[i] = i;
		
	for (int col = 1, i = 0; lstr; col<=m; ++col)
	{
		lstr = 0; // 记录上一个墙的右端点, 因此可以计算出下一段空区间为[lstr+1, w[].x1-1]
		cur.clear();
		while(i+1<=k && w[i+1].y == col)
		{
			i++;
			if (lstr+1 <= w[i].x1-1)
			{
				cur.push_back((node){lstr+1, w[i].x1-1, -1}); // 中间有空隙 
			}
			
			lstr = w[i].x2;
		}
		if (lstr+1 <= n)
			cur.push_back((node){lstr+1, n, -1});
			
		int l, r, lidx, ridx, lstf; // 枚举空区间的左右端点，以及前一个左右区间 
		for (auto &tmp: cur)
		{
			l = tmp.l;
			r = tmp.r;
			lidx = findl(l);
			ridx = findr(r);
			lstf = -1; // 所属颜色
			
			for (int i=lidx, tl, tr; i<=ridx; ++i)
			{
				tl = max(l, lst[i].l);
				tr = min(r, lst[i].r);
				
				if (tr - tl >= 1)
					return false;
				
				if (lstf != -1)
				{
					if (find(lst[i].color != lstf))
						merge(lstf, lst[i].color);
					else
						return false; // 两个颜色已经连通 
				}
				else
					lstf = find(lst[i].color);
			} 
			
			if (lstf != -1)
				tmp.color = lstf;
			else
			{
				tmp.color = c;
				c++;
			}
		}
		
		lst = cur; //对lst重新初始化 使其表示前一列 
	}
	return true;
}
 
int main()
{
	
	cin >> n >> m >> k;
	for (int i=1; i<=k; ++i)
	{
		cin >> w[i].x1 >> w[i].x2 >> w[i].y;
	}
	sort(w+1, w+k+1);
	
	if (solve())
		cout << "yes";
	else
		cout << "no";
}

L.Palm Island

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
 
int T,n;
int a[maxn],t[maxn];
pair<int,int> b[maxn];
 
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>t[i];
		for(int i=1;i<=n;i++){
			b[i].second=i;
			cin>>b[i].first;
		}
		sort(b+1,b+n+1);
		for(int i=1;i<=n;i++)
			a[i]=b[t[i]].second;
		
		for(int round=1;round<n;round++){
			for(int i=1;i<n;i++)
				if(a[i]>a[i+1]){
					swap(a[i],a[i+1]);
					printf("2");
				}
				else printf("1");
			printf("1");
		}
		puts("");
	}
	return 0;
}