首页 > 其他分享 >P8422 题解

P8422 题解

时间：2023-02-24 16:33:18浏览次数：61  
标签：cnt return int 题解 color P8422 y1 y2

前言

题目传送门！

更好的阅读体验？

第三道大模拟，写篇题解庆祝一下。

文中粗体字是我踩坑的地方，欢迎统计我被坑了多少次。

思路

终局奖分很简单，放在主函数里，所以我们看每次的操作是怎样的。

首先判断操作不合法：

  • 给定的坐标超出范围。
  • 是空位置。
  • 不是相邻的。
  • 交换后仍然不合法。

注意不合法要把交换的东西复原。然后我们合法的话就一直操作，不合法了就跳出，跑下一次。

这里大家可以参考我的顺序：

  1. 统计主颜色，满了就看牌型奖分。
  2. 一直跑。先连通块统计组合奖分。
  3. 消除，包括特殊属性。消除的时候统计消除奖分。注意这里只标记不删除。
  4. 现在再删除。
  5. 自由掉落。
  6. 循环结束了。统计连锁奖分。

大部分操作还是比较简单的，比较恶心的操作就是牌型奖分。

首先我们统计的时候把主函数用 Node 存储。存储的颜色显然不能重复。

Node tmp = (Node){-114514, -114514};
for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++)
		if (del[i][j])
		{
			if (tmp.x == -114514) tmp.x = color[i][j];
			else if (tmp.y != color[i][j] && tmp.y == -114514) tmp.y = color[i][j];
		}
card[++cntcard] = tmp;
if (cntcard == 5)
{
	vector <int> empty; //没有任何意义的玩意，他是空的
	maxn = 0, dfs(1, empty);
	ans += maxn;
	cntcard = 0;
}

现在满五个了，直接枚举跳颜色 1 还是颜色 2 即可。

#define let(x) tmp.push_back(x), dfs(i + 1, tmp), tmp.pop_back()
void dfs(int i, vector <int> tmp)
{
	if (i > 5) {maxn = max(maxn, calc(tmp)); return;}
	if (card[i].x != -114514) let(card[i].x);
	if (card[i].y != -114514) let(card[i].y);
}

至于计算就比较简单了（但是判断较多，脑子不清醒最好不要做）。元素只有五个，所以用任何办法统计都可以，显然不会超时。

代码

这次打大模拟激进了一点，所以就没写多少注释，但是看懂很容易的吧（

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
//这两个是关键字，所以就替换掉，代码中没有影响
#define y1 jojojo
#define round jinitaimei
using namespace std;
#define squ(x) ((x) * (x))
const int N = 55, dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, k, q, color[N][N], tag[N][N];
void swp(int x1, int y1, int x2, int y2) {swap(color[x1][y1], color[x2][y2]), swap(tag[x1][y1], tag[x2][y2]);}
bool near(int x1, int y1, int x2, int y2)
{
	for (int i = 0; i < 4; i++)
		if (x1 + dict[i][0] == x2 && y1 + dict[i][1] == y2 || x2 + dict[i][0] == x1 && y2 + dict[i][1] == y1)
			return true;
	return false;
}
struct Node {int x, y;};
bool del[N][N];
bool chk()
{
	memset(del, false, sizeof del);
	bool flag = false;
	for (int x = 1; x <= n; x++)
		for (int y = 1; y <= m; y++)
			for (int i = 0; i < 4; i++)
			{
				int dx = x + dict[i][0], dy = y + dict[i][1], ddx = dx + dict[i][0], ddy = dy + dict[i][1];
				if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
				if (ddx < 1 || ddx > n || ddy < 1 || ddy > m) continue;
				if (color[x][y] != 0 && color[x][y] == color[dx][dy] && color[x][y] == color[ddx][ddy])
					del[x][y] = del[dx][dy] = del[ddx][ddy] = flag = true;
			}
	return flag;
}
bool vis[N][N]; int siz;
void dfs(int x, int y)
{
	siz++, vis[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int dx = x + dict[i][0], dy = y + dict[i][1];
		if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
		if (del[dx][dy] && color[x][y] == color[dx][dy] && !vis[dx][dy]) dfs(dx, dy);
	}
}
int ans, round;
void remove(int x, int y)
{
	if (color[x][y] == 0 || vis[x][y]) return;
	vis[x][y] = true, ans += round * color[x][y];
	if (tag[x][y] == 1 || tag[x][y] == 3) {for (int i = 1; i <= m; i++) remove(x, i);}
	if (tag[x][y] == 2 || tag[x][y] == 3) {for (int i = 1; i <= n; i++) remove(i, y);}
	if (tag[x][y] == 4)
	{
		for (int i = max(1, x - 1); i <= min(n, x + 1); i++)
			for (int j = max(1, y - 1); j <= min(m, y + 1); j++)
				remove(i, j);
	}
	else if (tag[x][y] == 5)
	{
		for (int i = max(1, x - 2); i <= min(n, x + 2); i++)
			for (int j = max(1, y - 2); j <= min(m, y + 2); j++)
				remove(i, j);
	}
	else if (tag[x][y] == 6)
	{
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (color[i][j] == color[x][y])
					remove(i, j);
	}
}
void drop()
{
	for (int i = n; i; i--)
		for (int j = 1; j <= m; j++)
			if (color[i][j] == 0)
			for (int ii = i - 1; ii; ii--)
				if (color[ii][j] != 0)
				{
					swp(i, j, ii, j);
					break;
				}
	
}
Node card[105]; int cntcard;
int calc(vector <int> v)
{
	int cntbox[105] = {}; vector <int> cnt[10];
	for (int x : v) cntbox[x]++;
	for (int i = 0; i < 105; i++) cnt[cntbox[i]].push_back(i);
	for (int i = 0; i < 10; i++) sort(cnt[i].begin(), cnt[i].end());
	
	if ((int)cnt[1].size() == 5) return 50 + cnt[1][4];
	if ((int)cnt[1].size() == 3 && (int)cnt[2].size() == 1) return 100 + cnt[2][0] * 2;
	if ((int)cnt[1].size() == 1 && (int)cnt[2].size() == 2) return 200 + cnt[2][1] * 2 + cnt[2][0];
	if ((int)cnt[1].size() == 2 && (int)cnt[3].size() == 1) return 300 + cnt[3][0] * 3;
	if ((int)cnt[2].size() == 1 && (int)cnt[3].size() == 1) return 500 + cnt[3][0] * 3 + cnt[2][0];
	if ((int)cnt[1].size() == 1 && (int)cnt[4].size() == 1) return 750 + cnt[4][0] * 5;
	if ((int)cnt[5].size() == 1) return 1000 + cnt[5][0] * 10;
    return 0;
}
int maxn;
#define let(x) tmp.push_back(x), dfs(i + 1, tmp), tmp.pop_back()
void dfs(int i, vector <int> tmp)
{
	if (i > 5) {maxn = max(maxn, calc(tmp)); return;}
	if (card[i].x != -114514) let(card[i].x);
	if (card[i].y != -114514) let(card[i].y);
}
void play()
{
	Node tmp = (Node){-114514, -114514};
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (del[i][j])
			{
				if (tmp.x == -114514) tmp.x = color[i][j];
				else if (tmp.x != color[i][j] && tmp.y == -114514) tmp.y = color[i][j];
			}
	card[++cntcard] = tmp;
	if (cntcard == 5)
	{
		vector <int> empty;
		maxn = 0, dfs(1, empty);
		ans += maxn;
		//printf("mx = %d\n", maxn);
		cntcard = 0;
	}
	for (round = 1;; round++)
	{
		memset(vis, false, sizeof vis);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (del[i][j] && !vis[i][j])
					siz = 0, dfs(i, j), ans += 50 * squ(siz - 3);
		memset(vis, false, sizeof vis);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (del[i][j] && !vis[i][j])
					remove(i, j);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (vis[i][j])
					color[i][j] = 0;
		drop();
		
//		system("cls");
//		printf("当前%d局势\n", round);
//		for (int i = 1; i <= n; i++, putchar('\n'))
//			for (int j = 1; j <= m; j++)
//				printf("(%d,%d) ", color[i][j], tag[i][j]);
//		system("pause");
		
		if (!chk()) break;
	}
	ans += 80 * squ(round - 1);
//	printf("奖金 %d\n", ans);
}
bool solve(int x1, int y1, int x2, int y2)
{
	if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) return false;
	if (x2 < 1 || x2 > n || y2 < 1 || y2 > m) return false;
	if (color[x1][y1] == 0 || color[x2][y2] == 0 || !near(x1, y1, x2, y2)) return false;
	swp(x1, y1, x2, y2);
	if (chk()) {play(); return true;}
	else {swp(x1, y1, x2, y2); return false;} //不成功要换回来！ 
}
int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &q);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &color[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &tag[i][j]);
	int allOK_score = 1000, wonderful_score = 10000;
	while (q--)
	{
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		if (!solve(x1, y1, x2, y2)) allOK_score = 0;
	}
	for (int i = 1; i <= n && wonderful_score; i++)
		for (int j = 1; j <= m && wonderful_score; j++)
			if (color[i][j] != 0)
				wonderful_score = 0;
	cout << ans + allOK_score + wonderful_score;
	return 0;
}

希望能帮助到大家！

标签：cnt,return,int,题解,color,P8422,y1,y2
From： https://www.cnblogs.com/liangbowen/p/17151985.html

相关文章

  • 树剖练习题题解总和（动态更新）
    这篇博客的练习题题解1、P3384【模板】轻重链剖分/树链剖分模板题，详见此#include<iostream>#include<cstdio>#include<vector>usingnamespacestd;intn,m,r,p,t[......
  • P3571 [POI2014]SUP-Supercomputer 题解
    首先有一个结论，树中存在一个深度\(dep\)，使得深度小于等于\(dep\)的点只需\(dep\)次覆盖完，而大于\(dep\)的除最后一次外其他每次都可以填充\(k\)次。证明：在\(dep......
  • P4768 [NOI2018] 归程 题解
    这是一个悲伤的题目，自这道题后，\(\text{Noi}\)再无\(\text{SPFA}\)。首先讲一下重构树是啥。重构树是基于\(\text{kurskal生成树}\)算法的一棵树，对于每一次合并一条......
  • P3247 [HNOI2016]最小公倍数 题解
    题意简述：给定一个无向图，边权带两个值\((a,b)\)，给定\(q\)次询问，每次询问给定两个点，求两个点直接是否有\(\max(a)=x\)且\(\max(b)=y\)的简单或非简单路径。解：如果......
  • P2489 [SDOI2011]迷宫探险 题解
    题意简述：一个\(n\timesm\)的带墙体单入口多出口迷宫中有\(k\)个陷阱，陷阱分为有害或无害，有害会使人掉血，给出所有垃圾的有害与无害的所有排列组成的概率，给定人的血量，求......
  • P4416 [COCI2017-2018#1] Plahte 题解
    题意简述：给定\(n\)个互不相交，可以重叠的矩阵，对某些点染色，这个点上的所有矩阵会被染上这个颜色，求最后每个矩阵会有多少种颜色。解：我们可以先把矩阵拆成上下两条水平线......
  • CF1034A Enlarge GCD 题解
    题意简述：删去最少的数使所有的数的\(\text{gcd}\)增加。解：先对每个数除以所有数的\(\text{gcd}\)，然后剩下的需要找到所有数的质因子，找到一个最多的序列中数拥有的质......
  • CF436E Cardboard Box 题解
    一道经典的反悔贪心题。考虑每次选择使总星数加一，那么总共有四种情况。一、对于一关没有星，选一颗星，代价为\(a_i\)。二、对于一关有一颗星，再选一颗星，代价为\(b_i-a_i\)......
  • CF204E Little Elephant and Strings 题解
    由于是多个串，还与每个子串的信息有关，很容易想到用SA或广义SAM。这里选择用SA。首先先把字符串转化为数组，连接起来，中间用一些不会出现的数。处理出后缀数组与\(height......
  • P5842 [SCOI2012]Blinker 的仰慕者 题解
    题意简述：求\([l,r]\)内各个数位积为\(k\)的数的和。解：在看题解前，请先确认自己是否精通了数位dp模板题，否则会很难理解。对于朴素的数位dp，我们可以记录\(f_{i,j......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99