CodeForces - 1282D Enchanted Artifact

传送门：CodeForces - 1282D

题目描述

This is an interactive problem.

After completing the last level of the enchanted temple, you received a powerful artifact of the 255th level. Do not rush to celebrate, because this artifact has a powerful rune that can be destroyed with a single spell s, which you are going to find.

We define the spell as some non-empty string consisting only of the letters a and b.

At any time, you can cast an arbitrary non-empty spell t, and the rune on the artifact will begin to resist. Resistance of the rune is the edit distance between the strings that specify the casted spell t and the rune-destroying spell s.

Edit distance of two strings s and t is a value equal to the minimum number of one-character operations of replacing, inserting and deleting characters in s to get t. For example, the distance between ababa and aaa is 2, the distance between aaa and aba is 1, the distance between bbaba and abb is 3. The edit distance is 0 if and only if the strings are equal.

It is also worth considering that the artifact has a resistance limit — if you cast more than n+2 spells, where n is the length of spell s, the rune will be blocked.

Thus, it takes n+2 or fewer spells to destroy the rune that is on your artifact. Keep in mind that the required destructive spell s must also be counted among these n+2 spells.

Note that the length n of the rune-destroying spell s is not known to you in advance. It is only known that its length n does not exceed 300.

思路分析

因为最多有300个，所以可以询问两次300个a和300个b，可以得到a的数量和b的数量以及总长度n，定义一个长度为n全部为a的字符串，再遍历n-1，每次将当前位变为b，判断操作次数是否变少，如果没有就说明这一位不是b，再变回a，最后根据剩余b的数量特判最后一位。次数刚好n+2。

样例输入

2

2

1

2

3

0

样例输出

aaa

aaab

abba

bba

abaaa

aabba

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;

string get(char a,int n){
    string x="";
    while(n--)
        x+=a;
    return x;
}

int query(string s){
    cout<<s<<endl;
    int x;
    cin>>x;
    if(!x)
        exit(0);
    return x;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int cnta=300-query(get('a',300));
    int cntb=300-query(get('b',300));
    int n=cnta+cntb;
    string s=get('a',n);
    for(int i=0;i<n-1;i++){
        s[i]='b';
        int x=query(s);
        if(x<cntb){
            cntb=x;
        }
        else{
            s[i]='a';
            cnta--;
        }
    }
    if(cntb)
        s[n-1]='b';
    query(s);



    return 0;
}