FJNU2018低程F jq解救fuls （贪心乱搞）题解-白红宇

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

阅读量：6830 次

发布时间：2019-06-26

本文共 2201 字，大约阅读时间需要 7 分钟。

题目描述

一天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!"(输出无双引号)。

样例输入

25 43 3

样例输出

CCCCAjq 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
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               typedef long long ll;using namespace std;const int maxn = 1000 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;char ans[70];int main(){ int t; scanf("%d", &t); for(int p = 0; p < t; p++){ int n , m; scanf("%d%d", &n, &m); int Max = (n / 2) * (n - n / 2); if(m > Max){ printf("jq lost fuls!\n"); } else{ int len = n; int C, A; for(int i = 0; i <= m; i++){ int c = len - i, a = i; if(c + a <= len && c * a >= m){ while((c - 1) * a >= m && a != 0) c--; C = c; A = a; break; } } for(int i = 1; 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 + 1]); now++; M--; } for(int i = 1; i <= C + A; i++) printf("%c", ans[i]); for(int i = 1; i <= n - C - A; i++) printf("C"); printf("\n"); } } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/10023865.html

你可能感兴趣的文章