NOI2014 - 起床困难综合症

【LuoguP2114】【BZOJ3668】【UOJ2】【VijosP1864】【NOI2014】起床困难综合症
题目链接1: https://www.luogu.org/problemnew/show/P2114
题目链接2: https://www.lydsy.com/JudgeOnline/problem.php?id=3668
题目链接3: http://uoj.ac/problem/2
题目链接4: https://vijos.org/p/1864

前言

用了一个原创的做法, 模拟配合搜索, 非常玄学的过了这道题. 好像还没有这种做法的题解.

分析

题意比较好理解, 当我看到这句话:

最终受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力

依次经过N扇门是重点, 大大降低了这道题的难度.

由此想到最为暴力的方法, 从1到M枚举每一个数, 然后模拟N个操作, 算出每个数最后的伤害取个最大. 复杂度$ O(NM) $ 太大了.

然后考虑到位运算的性质, 我们只需要求出每一个二进制位上的变化就行了, 然后再把这些位组合起来, 求出一个初始不大于M但最终最大的数. 这个组合可以用搜索, 复杂度大概是 $ O(N \log t + t) $

看数据范围, $\log t$ 比30小, 我使用一个数组$ num[31][2] $, 第一维代表二进制的位数, 第二维代表初始为 0 还是 1, 初始化这个数组.

然后可以$ O(n \log t) $ 在线预处理, 直接模拟就行了. 预处理后的num数组就是每一个二进制位的变化.

然后就是求最终那个数, 因为M不是一个二的次幂, 所以不能循环求解, 但是可以用搜索.

如果学过01Trie, 上面的操作可以和它很相似, 求异或最大和本题的搜索的思路也类似. 然后加个条件判断和最优化剪枝就能完美通过本题了.

然后开int貌似会炸, 需要开long long, 但是最终答案应该是不会超int.

代码

未吸氧评测详情: Accepted 100

用时: 371ms / 内存: 932KB

#include <iostream>
#include <stdio.h>
#include <limits.h>
using namespace std;
#define int long long
int n, m, tmpx, num[32][2];
char tmps[4];
int ans= -1;
void dfs(int nown, int total, int tmpans) {
	if(total > m || tmpans <= ans) return;
	if(nown == -1) {
		ans= tmpans;
		return;
	}
	dfs(nown - 1, total, tmpans + (num[nown][0] << nown));
	dfs(nown - 1, total + (1 << nown), tmpans + (num[nown][1] << nown));
	return;
}
signed main() {
	cin >> n >> m;
	for(int i= 0; i < 31; i++) num[i][1]= 1;
	for(int i= 0; i < n; i++) {
		cin >> tmps >> tmpx;
		for(int j= 0; j < 31; j++) {
			int ch= (tmpx >> j) & 1;
			if(tmps[0] == 'A')
				num[j][0]&= ch, num[j][1]&= ch;
			else if(tmps[0] == 'O')
				num[j][0]|= ch, num[j][1]|= ch;
			else
				num[j][0]^= ch, num[j][1]^= ch;
		}
	}
	dfs(30, 0, 0);
	cout << ans << endl;
	return 0;
}

2020-01-11

LuoguP3695 - CYaRon!语

题解

NOI2014 - 起床困难综合症

前言

分析

代码

评论

目录

链接

分类

标签云

最新文章

归档

标签

最新文章

归档

标签

Your browser is out-of-date!