首页 > 其他分享 >CF1292E Rin and The Unknown Flower 题解

CF1292E Rin and The Unknown Flower 题解

时间：2022-11-14 07:44:18浏览次数：55  
标签：ch int 题解 询问 times Rin Unknown dfrac 代价

IO 交互题 fflush(stdout) 害人不浅！!1

注意到如果我们发起询问 C 和 O 就可以花费 2 的代价知道整个串，不过代价过高，所以我们考虑减小点代价。

考虑发起询问 CO,CH,CC，这样我们必然可以知道除了最后一位以外所有 C 的位置，然后类似的询问 HO,OO，这样我们必然可以知道除了第一位以外所有 O 的位置（前面问过一次 CO）。

考虑第二位至第 \(n-1\) 位，注意到此时里面不确定的位置必然都是 H，因为如果有 C 或者 O 肯定已经被问出来了。

这样就只剩下第一位和第 \(n\) 位了，又第一位不会是 C，最后一位不会是 O，于是至多只有 4 种情况，问 3 次即可知道答案。

代价为 \(5\times\dfrac{1}{4}+3\times\dfrac{1}{n^2}\)，易知该式在 \(n\ge5\) 时小于等于 1.4。

然后 \(n\ge4\)，所以 \(n=4\) 还要另外想办法。下面大分类讨论预警，可以画个决策树理解。

注意到上面问了五个串 CO,CH,CC,HO,OO，\(n=4\) 不行的关键在于后面 3 次是错代价过大，然而这些试错是必须的，所以只能减少前面的询问。

考虑先询问 CO,CH,CC,HO，如果我们当前已经问出来了至少两个位置，那么剩下只有至多两个位置不确定且前三位必然不是 C，最坏情况有六种可能，试五次错即可，代价 \(4\times\dfrac{1}{4}+5\times\dfrac{1}{16}=1.3125\)。

如果这些都没问出来，那么只有两种可能，一种是含有 OO 一种是含有 HH，然后在决策树上发现这样问完后只需要问一次长度为 4 的串即可，没超 1.4，于是问一下 OO。

如果有，说明只可能是 OOOO,OOOH,OOOC,OOHC,OOHH 这四种情况（剩余情况肯定前面都被问出来了），同时已知 OOOO 不用询问，如果有两个位置不确定必是 OOHC,OOHH 中一种，否则是 OOOH,OOOC 中一种，无论哪种代价都是 \(5\times\dfrac{1}{4}+\dfrac{1}{16}=1.3125\)。

否则中间两位必然是 HH，第一位只能是 O,H，最后一位只能是 C,H，然而我们不能询问 3 次（否则代价为 \(1.4375\)），于是问一下 HHH，这样可以确定这两位是不是 H，如果不是那也只有一种情况，代价 \(5\times\dfrac{1}{4}+\dfrac{1}{9}\approx1.361<1.4\)。

做完了，我写代码的时候 \(n\ge5\) 写了 1k，\(n=4\) 写了 3k /fad

Code：

/*
========= Plozia =========
	Author:Plozia
	Problem:CF1292E Rin and The Unknown Flower
	Date:2022/11/13
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;
#define Flu fflush(stdout)
#define rt return

const int MAXN = 50 + 5;
int n;
char str[MAXN], Next[6][2] = {{'H', 'H'}, {'H', 'O'}, {'O', 'H'}, {'O', 'O'}, {'H', 'C'}, {'O', 'C'}};

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	rt sum * fh;
}

void Solve2()
{
	puts("? CC"); Flu; int k = Read(), cnt = 0;
	for (int i = 1; i <= k; ++i) { ++cnt; int x = Read(); str[x] = str[x + 1] = 'C'; }
	puts("? CO"); Flu;
	k = Read(); for (int i = 1; i <= k; ++i) { ++cnt; int x = Read(); str[x] = 'C', str[x + 1] = 'O'; }
	puts("? CH"); Flu;
	k = Read(); for (int i = 1; i <= k; ++i) { ++cnt; int x = Read(); str[x] = 'C', str[x + 1] = 'H'; }
	puts("? HO"); Flu;
	k = Read(); for (int i = 1; i <= k; ++i) { ++cnt; int x = Read(); str[x] = 'H', str[x + 1] = 'O'; }
	if (cnt > 0)
	{
		cnt = 0; for (int i = 1; i <= n; ++i) cnt += (str[i] == '?');
		if (cnt == 0) { printf("! %c%c%c%c\n", str[1], str[2], str[3], str[4]); Flu; rt; }
		if (cnt == 1)
		{
			if (str[1] == '?')
			{
				printf("? H%c%c%c\n", str[2], str[3], str[4]); Flu;
				k = Read(); if (k) { Read(); printf("! H%c%c%c\n", str[2], str[3], str[4]); Flu; rt; }
				printf("! O%c%c%c\n", str[2], str[3], str[4]); Flu; rt;
			}
			printf("? %c%c%cH\n", str[1], str[2], str[3]); Flu;
			k = Read(); if (k) { Read(); printf("! %c%c%cH\n", str[1], str[2], str[3]); Flu; rt; }
			printf("? %c%c%cO\n", str[1], str[2], str[3]); Flu;
			k = Read(); if (k) { Read(); printf("! %c%c%cO\n", str[1], str[2], str[3]); Flu; rt; }
			printf("! %c%c%cC\n", str[1], str[2], str[3]); Flu; rt;
		}
		if (str[1] == '?' && str[4] == '?')
		{
			for (int i = 0; i < 5; ++i)
			{
				printf("? %c%c%c%c\n", Next[i][0], str[2], str[3], Next[i][1]); Flu;
				int k = Read(); if (k) { Read(); printf("! %c%c%c%c\n", Next[i][0], str[2], str[3], Next[i][1]); Flu; rt; }
			}
			printf("! O%c%cC\n", str[2], str[3]); Flu; rt;
		}
		if (str[1] == '?')
		{
			for (int i = 0; i < 3; ++i)
			{
				printf("? %c%c%c%c\n", Next[i][0], Next[i][1], str[3], str[4]); Flu;
				int k = Read(); if (k) { Read(); printf("! %c%c%c%c\n", Next[i][0], Next[i][1], str[3], str[4]); Flu; rt; }
			}
			printf("! OO%c%c\n", str[3], str[4]); Flu; rt;
		}
		for (int i = 0; i < 5; ++i)
		{
			printf("? %c%c%c%c\n", str[1], str[2], Next[i][0], Next[i][1]); Flu;
			int k = Read(); if (k) { Read(); printf("! %c%c%c%c\n", str[1], str[2], Next[i][0], Next[i][1]); Flu; rt; }
		}
		printf("! %c%cOC\n", str[1], str[2]); Flu; rt;
	}
	puts("? OO"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { ++cnt; int x = Read(); str[x] = str[x + 1] = 'O'; }
	if (cnt)
	{
		cnt = 0; for (int i = 1; i <= n; ++i) cnt += (str[i] == '?');
		if (cnt == 0) { printf("! %c%c%c%c\n", str[1], str[2], str[3], str[4]); Flu; rt; }
		if (cnt == 1)
		{
			puts("? OOOC"); Flu; int k = Read();
			if (k) { Read(); puts("! OOOC"); Flu; rt; }
			else { puts("! OOOH"); Flu; rt; }
		}
		puts("? OOHC"); Flu; int k = Read(); if (k) { Read(); puts("! OOHC"); Flu; rt; }
		puts("! OOHH"); Flu; rt;
	}
	puts("? HHH"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = str[x + 1] = str[x + 2] = 'H'; }
	printf("! %cHH%c\n", (str[1] == '?') ? 'O' : str[1], (str[4] == '?') ? 'C' : str[4]); Flu; rt; 
}
void Solve()
{
	n = Read(); for (int i = 1; i <= n; ++i) str[i] = '?';
	if (n == 4) { Solve2(); rt; } int k;
	puts("? CO"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = 'C', str[x + 1] = 'O'; }
	puts("? CC"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = str[x + 1] = 'C'; }
	puts("? CH"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = 'C', str[x + 1] = 'H'; }
	puts("? HO"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = 'H', str[x + 1] = 'O'; }
	puts("? OO"); Flu; k = Read(); for (int i = 1; i <= k; ++i) { int x = Read(); str[x] = 'O', str[x + 1] = 'O'; }
	for (int i = 2; i < n; ++i) if (str[i] == '?') str[i] = 'H';
	for (int i = 0; i < 5; ++i)
	{
		if (i == 1 || i == 3) continue ;
		printf("? %c", (str[1] == '?') ? Next[i][0] : str[1]);
		for (int _ = 2; _ < n; ++_) printf("%c", str[_]);
		printf("%c\n", (str[n] == '?') ? Next[i][1] : str[n]); Flu;
		k = Read();
		if (k)
		{
			Read();
			printf("! %c", (str[1] == '?') ? Next[i][0] : str[1]);
			for (int _ = 2; _ < n; ++_) printf("%c", str[_]);
			printf("%c\n", (str[n] == '?') ? Next[i][1] : str[n]); Flu; rt;
		}
	}
	printf("! %c", (str[1] == '?') ? 'O' : str[1]);
	for (int _ = 2; _ < n; ++_) printf("%c", str[_]);
	printf("%c\n", (str[n] == '?') ? 'C' : str[n]); Flu; rt;
}

int main()
{
	int t = Read(); while (t--) { Solve(); if (Read() == 0) rt 0; } rt 0;
}

标签：ch,int,题解,询问,times,Rin,Unknown,dfrac,代价
From： https://www.cnblogs.com/Plozia/p/16887884.html

相关文章

  • SpringMVC执行流程（理解）-流程，小总结
    SpringMVC执行流程（理解）使用的案例还是上一篇的博客第1章SpringMVC*概述-注册中央调度区，定义页面，修改视图解析器-a-tao必须奥利给-博客园(cnblogs.com)1.使用Sp......
  • Spring —— AOP总结
    AOP总结              ......
  • 第1章SpringMVC*概述-注册中央调度区，定义页面，修改视图解析器
    第1章SpringMVC概述1.1SpringMVC简介SpringMVC也叫Springwebmvc。是Spring框架的一部分，是在Spring3.0后发布的。1.2SpringMVC优点1.基于MVC架构......
  • TheNameCalculator题解
    TheNameCalculator题解题目链接：TheNameCalculator题解首先看程序开启的保护，有Canary和NX栈不可执行。IDA打开程序，shift+F12查看字符串，发现有"Hereisyourflag:"。点......
  • String.Remove()、String.Substring()
    https://blog.csdn.net/n_moling/article/details/78953658Remove(intstartIndex)：删除此字符串中从指定位置到最后位置的所有字符。Remove(intstartIndex,intlength......
  • 833——B题题解
    题目链接题目大意：给一串字符串（只包含0~9），定义一个最优子串的定义：如果该子串同字符种类数大于最最多字符出现数，那么这个子串可以被称为最优子串。解题思路：大眼一看这个数......
  • [ARC086F] Shift and Decrement 题解
    linkSolution一个简易的贪心想法是我们肯定是对于一个相同的序列求出操作到它的最小操作次数，看能否\(\leK\)。注意到我们在第\(x\)次A操作后进行\(-1\)操作相当于......
  • 833(DIV2)——C题题解
    题目链接题目大意：给定n个数，你可以对数值为0的数改变其为任意值，问最后前缀和为0的个数的最大值。思路：这题比较可惜，自己的思路没有问题，但是他少了一些东西。对数组进行前......
  • LG_P4588 [TJOI2018] 数学计算 题解
    LuoguP4588题解这个玩意还是挺好想到的，也不难看出他是一个线段树。没想到可以评上蓝。考虑每次操作对于答案的贡献。由于\(x=1\)，所以我们相当于是在维护一堆数的积，初始......
  • DTOJ 3498 无限剑制 题解
    题面题目链接题解想了好久，其实很水tt想写题解主要是因为这题题面是Fate很有意思我们注意到“所有\(v_i\)值域在\([1,5]\)”这个部分分，这种情况下，初始的不同情......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99