1 条题解

  • 0
    @ 2023-5-19 16:42:57

    首先，这题的输入就很恶心，我们可以用下面的代码成功输入：

    for(int i = 1;i <= n; i++)
	{
		cin >> str;
		if(str == ";")continue;
		int l = 0, r = 0, num = 0;
		int type = 0;
		for(int j = 0;j < str.size(); j++)
		{
			if(isdigit(str[j]) && type == 0)
			{
				num = num * 10 + (str[j] - '0');
			}
			else if(type == 2 && isdigit(str[j]))
			{
				r = r * 10 + (str[j] - '0');
			}
			else if(str[j] == '-')
			{
				type = 2;
				l = num;
			}
			else if(str[j] == ',' || str[j] == ';')
			{
				if(type == 2)update(i, l, r);//将l~r涂成黑色
				else update(i, num, num);//将num涂成黑色
				num = l = r = 0;
				type = 0;
			}
		}

    其中， update(i, l, r) 表示第 ii 行的 l∼rl \sim r 的这些方块涂成黑色，具体什么内容就看我们要用哪种方法做这道题。

    暴力

    直接暴力跑一个 dfs⁡\operatorname{dfs}，能拿到大概 6464 分并且附上 RE\color{#9D3DCF}\text{RE} 的好成绩（bushi）

    /*****************************************
备注：solution1
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e4 + 10;
const int MR = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;
const int debug1 = false;
int mp[MAXN][MAXN] = {0};
int idx[MAXN][MAXN] = {0};//color
int n;
void update(int h, int l, int r)//color the l~r
{
	for(int kkk = l;kkk <= r; kkk++)mp[h][kkk] = 1;//start color
}
void print()//print the map
{
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= n; j++)
		{
			cout << mp[i][j] << ' ';
		}
		cout << endl;
	}
}
void dfs(int row,int col,int id)
{
    if (row < 1 || row > n || col < 1 || col > n)return;
    if((mp[row][col] != 1) || (idx[row][col] > 0))
        return;
    idx[row][col] = id;
    for(int drow=-1;drow<=1;drow++){
        for(int dcol=-1;dcol<=1;dcol++){
            dfs(row + drow, col + dcol, id);
        }
    }
}
int len[MR];
struct node
{
    int num, appear;//什么数字 长度
}box[MR];
bool cmp(node a,node b)
{
    return a.num > b.num;
}
signed main()
{	
	cin >> n;
	string str;
	for(int i = 1;i <= n; i++)
	{
		cin >> str;
		if(str == ";")continue;
		int l = 0, r = 0, num = 0;
		int type = 0;
		for(int j = 0;j < str.size(); j++)
		{
			if(isdigit(str[j]) && type == 0)
			{
				num = num * 10 + (str[j] - '0');
			}
			else if(type == 2 && isdigit(str[j]))
			{
				r = r * 10 + (str[j] - '0');
			}
			else if(str[j] == '-')
			{
				type = 2;
				l = num;
			}
			else if(str[j] == ',' || str[j] == ';')
			{
			    if(debug)printf("num:%d l:%d r:%d type:%d\n", num, l, r, type);
				if(type == 2)update(i, l, r);//update block l~r
				else update(i, num, num);//update block num
				num = l = r = 0;
				type = 0;
			}
		}
	}
	int cnt = 0;
    for(int i = 1;i <= n; i++)
	{
        for(int j = 1;j <= n; j++)
		{
            if(idx[i][j] == 0 && mp[i][j] == 1)
            {
            	dfs(i, j, ++cnt);
			}
        }
    }
    if(debug1)cout << cnt << endl;
    for(int i = 1;i <= n; i++)
    {
    	for(int j = 1;j <= n; j++)
    	{
    		len[idx[i][j]]++;
		}
	}
    int mxx = -INF;
	for(int i = 1;i <= cnt; i++)box[len[i]].appear++, box[len[i]].num = len[i], mxx = max(mxx, len[i]);
    sort(box + 1,box + mxx + 1, cmp);
    for(int i = 1;i <= cnt; i++)
    {
        if(box[i].num == 0 || box[i].appear == 0)continue;
        cout << box[i].num << ' ' << box[i].appear << endl;
    }
	if(debug1){cout << endl; print();}
	return 0;
}

    这代码甚至没有 TLE\color{#052242}\text{TLE}，太感动了。

    因为是 30000×3000030000\times 30000，棋盘放不下所以分析个 Δ\Delta 啊（，接下来我们考虑优化。

    优化

    首先，我们把这个图画出来

    连通块就是指 连通的块，我们可以这样子想，只看两行，题目说过不超过 1000×1000=1061000 \times 1000 = 10^6，我们可以就 储存黑格子 有多少个。什么意思呢，就是当前如果和上一行的黑格子相邻，我们就将这两个格子 合并 一个格子，然后再判断左右两边的格子和这个合并的格子相不相邻，然后把他们 看成一块，这样的方法我们可以用什么数据结构存储呢？当然是 并查集 了，当然维护并查集我们还需要一个数组 siz⁡\operatorname{siz} 来储存大小，那么这题思路就讲完了，直接看代码吧。

    /*****************************************
备注：
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define int LL
const int MAXN = 1e6 + 10;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int fa[MAXN],siz[MAXN], cnt;
int now[MAXN], pre[MAXN];
int get(int x)
{
	return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void merge(int x,int y)
{
	x = get(x);y = get(y);
	if(x == y)return ;
	if(siz[x] < siz[y])
	{
		fa[x] = y;
		siz[y] += siz[x];
	}
	else
	{
		fa[y] = x;
		siz[x] += siz[y];
	}
}
int make_new(){siz[++cnt] = 1;return cnt;}
signed main()
{
	for(int i = 1;i <= 1000000; i++)fa[i] = i;
	int n;string str;
    cin >> n;
	for(int i = 1;i <= n; i++)
	{
        memcpy(pre, now, sizeof(pre));
        memset(now, 0, sizeof(now));
		cin >> str;
		if(str == ";")continue;
		int l = 0, r = 0, num = 0;
		int type = 0;
		for(int j = 0;j < str.size(); j++)
		{
			if(isdigit(str[j]) && type == 0)
			{
				num = num * 10 + (str[j] - '0');
			}
			else if(type == 2 && isdigit(str[j]))
			{
				r = r * 10 + (str[j] - '0');
			}
			else if(str[j] == '-')
			{
				type = 2;
				l = num;
			}
			else if(str[j] == ',' || str[j] == ';')
			{
                if(type == 0)
                {
                    //only one
                    now[num] = make_new();
                    if(pre[num])merge(now[num], pre[num]);//如果上一行是黑色的
                }
                else if(type == 2)
                {
                    now[l] = make_new();
                    if(pre[l])merge(now[l], pre[l]);//如果上一行是黑色的
                    for(int huhe = l + 1;huhe <= r; huhe++)
                    {
                        now[huhe] = make_new();
                        if(pre[huhe])merge(pre[huhe], now[huhe]);
                        merge(now[huhe], now[huhe - 1]);
                    }
                }
				num = l = r = 0;
				type = 0;
			}
		}
	}
	int ans[MAXN];
	for(int i = 1;i <= cnt; i++)if(fa[i] == i)ans[siz[i]] ++;
	for(int i = 1000;i >= 1; i--)
	{
		if(ans[i]  >= 1)cout << i << ' ' << ans[i] << endl;
	}
	return 0;
}

    这代码甚至 TLE\color{#052242}\text{TLE}，太感动了（

    为什么呢，因为 可能每次的 l∼rl\sim r 的暴力操作再配上并查集合并操作就会炸掉。考虑再优化一下。

    直接将每次输入的 l∼rl \sim r 得格式的格子创建一个大的连通块， 当前的 siz[?]⁡=r−l+1\operatorname{siz[?]} = r - l + 1，然后判断当前这个连通块和上一行有没有相交即可。

    （注意：并查集初始化一定要变成 10610^6，我在这里卡了 30min⁡30 \operatorname{min}）

    AC 代码

    /*****************************************
备注：
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define int LL
const int MAXN = 1e6 + 10;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int fa[MAXN],siz[MAXN], cnt;
char str[MAXN];
struct node
{
	int l, r, pos;//l ~ r的黑格子，pos表示上一行第pos位跟当前的l~r有相邻 
}now[MAXN], pre[MAXN];
int ncnt, pcnt; 
int ans[MAXN];
int get(int x)
{
	return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void merge(int x,int y)
{
	x = get(x);y = get(y);
	if(x == y)return ;
	if(siz[x] < siz[y])
	{
		fa[x] = y;
		siz[y] += siz[x];
	}
	else
	{
		fa[y] = x;
		siz[x] += siz[y];
	}
}
int make_new(int x){siz[++cnt] = x;return cnt;}
void copy()
{
	for(int i = 1;i <= ncnt; i++)
	{
		pre[i] = now[i];
		now[i] = {0, 0, 0};
	}
	pcnt = ncnt,ncnt = 0;
} 
int read(int &j)
{
    int r = 0;
    while(isdigit(str[j]))r = r * 10 + (str[j++] - '0');
    return r;
}
signed main()
{
	for(int i = 1;i <= 1000000; i++)fa[i] = i;
	int n;
    cin >> n;
	for(int i = 1;i <= n; i++)
	{
        // copy();
		memcpy(pre,now,sizeof(node)*ncnt);
	    pcnt = ncnt,ncnt = 0;
		int pos = 0;
		cin >> (str + 1);
		for(int j = 1;j <= strlen(str+1); j++)
		{
            if(str[j] == ';')break ;
		    int l = read(j), r = l;
			if(str[j] == '-')
			{
                j++;
                r = read(j);
			}
            now[ncnt] = {l, r, make_new(r - l +1)};
            for(;pos < pcnt && pre[pos].r < l; pos++)
            {
            }
            for(;pos < pcnt && pre[pos].l <= r; pos++)
            {
                merge(now[ncnt].pos, pre[pos].pos);
            }
            ncnt++;
            if(pos)pos--;
		}
	}
	for(int i = 1;i <= cnt; i++)if(fa[i] == i)ans[siz[i]] ++;
	for(int i = 1000;i > 0; i--)
	{
		if(ans[i])cout << i << ' ' << ans[i] << endl;
	}
	return 0;
}
    • 1

    [Baltic2004]Ships

    信息

    ID
    1364
    时间
    5000ms
    内存
    64MiB
    难度
    10
    标签
    (无)
    递交数
    16
    已通过
    1
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. 版权申诉
    6. Language
    7. 兼容模式
    8. 主题
    2. © 2021-2024 Hydro.ac
    4. Worker 0 in 52ms
    5. Hydro v4.12.0 Professional