FJNU2018低程F jq解救fuls （贪心乱搞）题解

时间：2022-11-03 06:46:09

题目描述

一天fuls被邪恶的"咕咕咕"抓走了,jq为了救fuls可谓是赴汤蹈火,费了九牛二虎之力才找到了"咕咕咕"关押fuls的地方。 
fuls被关在一个机关中，想要解救fuls必须解答出机关的问题，在机关上会显示两个整数N和M，jq必须在机关上输入N个只包含'A'和'C'的字符形成串str， 
在这个串中存在f(i,j),i<j,表示str[i]=='C'和str[j]=='A'的一个反AC对，此字符串必须包含刚好M个反AC对，如果有多个长度为N的串满足条件，那么字典序最大的那个才是正确的。 
字典序大小: 
        若字符串a>字符串b即存在位置i使得0<=j<i,a[j]==b[j],a[i]>b[i]。 

输入

第一行输入一个t表示样例个数。(1<=t<=100) 
接下来t行每行包含两个整数N和M(1<=N<=60,0<=M<=N*(N-1)/2) 

输出

每个样例输出一行字符串表示jq的答案，若某次询问无解则输出"jq lost fuls!"(输出无双引号)。 

样例输入

2

5 4

3 3

样例输出

CCCCA

jq lost fuls!

附送几组数据：

10 23
CCCCCACAAA
10 22
CCCCCAACAA
10 0
CCCCCCCCCC

思路：在队友AC的瞬间想到了思路...

问题可以理解为就是给你长度n，求字典序最大的、CA对数为m的答案。显然长度为n的串CA对数最大为Max = (n / 2) * (n - n / 2)。那么超过这个值就不存在答案。

显然A越少整个串就可能字典序越大，那么我们从A为0开始找，找到这种情况下形成最多的CA对数（即（n-a）*a），如果当前A的个数形成的CA对数已经>=m了，那么显然A最多就这么多了。

假设此时A个数为a，C的个数为c=n-a，此时已经满足c*a>=m。我们可以知道，如果交换CA，那么CA对数会减少1，那么我们只要不断逼近m，最后一直减一就能减到m了。所以我们不断减小c，但是继续满足c*a>=m，那么终有一天，会变成c*a>=m并且（c-1）*a<m，这时候已经逼近成功了。注意一下移动时只需要移动最后一个C就行了。然后在最后还没填完的地方加C。

为了防止有人误入此地看不懂题解，我决定模拟一下过程：

10 23

a = 0，最大0个CA对，pass

a = 1，最大9个CA对，pass

a = 2，最大16个CA对，pass

a = 3，最大21个CA对，pass

a = 4，最大24个CA对，开始逼近

c = 6，a = 4，显然c不可能再小了，此时的串为CCCCCCAAAA，值为24

移动最后一个C，变成CCCCCACAAA，值为23，末尾也不用填C，真相只有一个答案是CCCCCACAAA

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

char ans[];

int main(){

    int t;

    scanf("%d", &t);

    for(int p = ; p < t; p++){

        int n , m;

        scanf("%d%d", &n, &m);

        int Max = (n / ) * (n - n / );

        if(m > Max){

            printf("jq lost fuls!\n");

        }

        else{

            int len = n;

            int C, A;

            for(int i = ; i <= m; i++){

                int c = len - i, a = i;

                if(c + a <= len && c * a >= m){

                    while((c - ) * a >= m && a != ) c--;

                    C = c;

                    A = a;

                    break;

                }

            }

            for(int i = ; i <= C + A; i++){

                if(i <= C){

                    ans[i] = 'C';

                }

                else{

                    ans[i] = 'A';

                }

            }

            int M = C * A;

            int now = C;

            while(m < M){

                swap(ans[now], ans[now + ]);

                now++;

                M--;

            }

            for(int i = ; i <= C + A; i++)

                printf("%c", ans[i]);

            for(int i = ; i <= n - C - A; i++)

                printf("C");

            printf("\n");

        }

    }

    return ;

}

相关文章