• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7044]Fall with Fake Problem

admin

11 月 28, 2021

二分$T$​​​​​​​​和$S$​​​​​​​​第一个不同的位置,即需要对于$s$​​​​​​​​,判定是否存在$T[1,s]=S[1,s]$​​​​​​​​且满足条件的$T$​​​​

(注:这里的条件不包含$T$的字典序最小)

显然$T[1,s]$​​已经确定,记其中第$i$​​种字母出现次数为$a_{i}$​​

而对于$T(s,n]$​,只有字典序(尽量大)和字符数量的限制,因此若交换两个字符能增大字典序显然不劣,重复交换这样的字符,不难得到最终字符从前往后是不上升的

设其中第$i$​​种字符有$b_{i}$​​个,即希望依次最大化$b_{26},b_{25},…,b_{1}$​​​​,不妨依次暴力枚举(共$sigma(k)$​​​种取值),并对后面的部分背包+bitset判定是否可行,即可得到该序列并进而比较与$S$的字典序

这一部分的复杂度为$o(alphasigma(k)frac{n}{omega}log n)$​​(其中$alpha=26$​​,$omega=64$​​)

进一步的,由于下一个位置一定不同,那么再之后的部分也仅有字典序(尽量小)和字符数量的限制,可以类似地求出,而下一个位置直接暴力枚举即可

这一部分的复杂度为$o(alpha^{2}sigma(k)frac{n}{omega})$

综上,(单组数据)复杂度为$o(alphasigma(k)frac{n}{omega}log n+alpha^{2}sigma(k)frac{n}{omega})$,可以通过​

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define A 26
 5 vector<int>v;
 6 bitset<N>bt[A+1];
 7 int t,n,m,a[A],b[A];
 8 char s[N];
 9 bool get_max(int n){
10     memset(b,0,sizeof(b));
11     for(int i=A-1;i>=0;i--){
12         bt[i].reset();
13         for(int j=0;(j<v.size())&&(a[i]<=v[j]);j++){
14             int x=v[j]-a[i];
15             if (x<=n)bt[i]|=(bt[i+1]<<x);
16         }
17     }
18     if (!bt[0][n])return 0;
19     for(int i=0;i<A;i++)
20         for(int j=0;(j<v.size())&&(a[i]<=v[j]);j++){
21             b[i]=v[j]-a[i];
22             if ((b[i]<=n)&&(bt[i+1][n-b[i]])){
23                 n-=b[i];
24                 break;
25             }
26         }
27     return 1;
28 }
29 bool check(int k){
30     memset(a,0,sizeof(a));
31     for(int i=1;i<=k;i++)a['z'-s[i]]++;
32     if (!get_max(n-k))return 0;
33     for(int i=0;i<A;i++)
34         for(int j=0;j<b[i];j++)
35             if (s[++k]!='z'-i)return s[k]<'z'-i;
36     return 1;
37 }
38 int main(){
39     bt[A][0]=1;
40     scanf("%d",&t);
41     while (t--){
42         scanf("%d%d%s",&n,&m,s+1);
43         v.clear();
44         for(int i=m;i;i--)
45             if (m%i==0)v.push_back(i);
46         v.push_back(0);
47         memset(a,0,sizeof(a));
48         if (!check(0)){
49             printf("-1
");
50             continue;
51         }
52         int l=0,r=n;
53         while (l<r){
54             int mid=(l+r+1>>1);
55             if (check(mid))l=mid;
56             else r=mid-1;
57         }
58         if (l==n){
59             printf("%s
",s+1);
60             continue;
61         }
62         memset(a,0,sizeof(a));
63         for(int i=1;i<=l;i++)a[s[i]-'a']++;
64         for(int i=s[l+1]-'a'+1;i<A;i++){
65             a[i]++;
66             if (get_max(n-l-1)){
67                 for(int j=1;j<=l;j++)printf("%c",s[j]);
68                 printf("%c",i+'a');
69                 for(int j=0;j<A;j++)
70                     while (b[j]--)printf("%c",j+'a');
71                 printf("
");
72                 break;
73             }
74             a[i]--;
75         }
76     }
77     return 0;
78 } 

View Code

发表回复