[补档]noip2019集训测试赛（十）

一时失言乱红尘 2023-08-17 16:58 99阅读 0赞

## Problem A: fibonacci ##

#### Time Limit: 2000 ms Memory Limit: 256 MB ####

### Description ###

小y最近迷上了fibonacci数列，他定义了一种数列叫fibonacccccci数列：

1、这个数列包含至少2个元素；

2、f\[0\]和f\[1\]是任意选取的；

3、f\[n+2\]=f\[n+1\]+f\[n\] (n>=0)；

现在，给出一个数列a\[1..n\]，你可以改变数列元素的顺序，使得a\[1..m\]满足fibonacccccci数列的条件，请求出最大的m。

### Input ###

第一行1个数n，表示数列长度；

第二行n个数，表示a\[1..n\]。

### Output ###

输出一行一个数，表示最大的m。

Sample Input
    
    3
    1 2 -1 
    
    Sample Output
    
    3

### HINT ###

对于20%的数据满足：n<=7；

对于100%的数据满足：n<=500，0<=|a\[i\]|<=10^9。

## Solution ##

1e9范围内的斐波那契数列只有46项

即使他一个负数一个整数来搞，几项后也会变回正常的斐波那契

所以直接暴力

#include<bits/stdc++.h>
    using namespace std;
    map<int,int> mp;
    int a[200001];
    int f[200001];
    int cnt;
    int t;
    int main(){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            mp[a[i]]++;
        }
        sort(a+1,a+1+n);
        int ans=0;
        ans=max(mp[0],ans);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            if(a[i]==0&&a[j]==0)continue;
            map<int,int>mp2;
            mp2[a[i]]++;
            mp2[a[j]]++;
            cnt=2;  
            f[1]=a[i];
            f[2]=a[j];
            while(++mp2[f[cnt-1]+f[cnt]]<=mp[f[cnt-1]+f[cnt]]){
                cnt++;
                f[cnt]=f[cnt-1]+f[cnt-2];
            }
            ans=max(ans,cnt);
        }
        printf("%d",ans);
    }

## Problem B: K-th String ##

#### Time Limit: 1000 ms Memory Limit: 256 MB ####

### Description ###

Alice有 n(n≤26) 张牌，牌上分别标有前 n 个英文小写字母。例如，如果 n=3 ，则Alice有3张牌，分别标有"a", "b", "c" 。Alice可以通过排列这些卡牌来构造字符串 t 。考虑字符串 t 的所有子串（共 n(n+1)/2 个），按照字典序从小到大排名第 k 的子串为 s 。现在，给你正整数 n,k 和字符串 s ，问有多少种可能的字符串 t 。将答案对10^9+7取模。

例如： 当 n=3,t="cab"时，排序后的子串为"a", "ab", "b", "ca", "cab", "cab"，排名第3的子串为"b"。当 n=3,k=3,s="b" 时 ，则 t 可能为"cab"或"bac" ，故答案为2种。

### Input ###

第一行两个整数 n,k(1≤n≤26,1≤k≤n(n+1)/2)。

第二行一个字符串 s，s 中仅包含前 n 个字母，且 s 中的字母两两不同。

### Output ###

输出一行表示答案。将答案对 10^9+7 取模。

Sample Input
    
    3 3
    b
    
    Sample Output
    
    2

### HINT ###

对于30%的数据， 1≤n≤8

对于所有数据， 1≤n≤26

## Solution ##

设\\(dp\[i\]\[j\]\[k\]\[0/1\]\\)为已经选了i个字符，有j个比\\(s\[1\]\\)小的字符（除了s内的字符），而有k个比s字典序小的子串的方案中，s是否出现过，的方案数。

那么转移方程：

1、当前选择的字符比s\[1\]大：\\(dp\[i+1\]\[j\]\[k\]\[0/1\]+=dp\[i\]\[j\]\[k\]\[0/1\]\\)

2、当前选择的字符比s\[1\]小：此时会多贡献\\(n-i\\)个比s字典序小的子串，所以有：

\\(dp\[i+1\]\[j+1\]\[k+(n-i)\]\[0/1\]+=dp\[i\]\[j\]\[k\]\[0/1\]\\)

3、我们在这里直接插入s

那么这个时候设它会贡献num个比\\(s\[1\]\\)小的字符，len为s长度

设\\(d=(i-1) \\times \[s\[i\]<s\[1\]\]\\)，那么有

\\(dp\[i+len\]\[j\]\[k+(n-i) \\times num-d\]\[1\]+=dp\[i\]\[j\]\[k\]\[0\]\\)

\\(k+(n-i) \\times num-d\\)换成一个更直观一点的说法，就是\\(\\displaystyle \\sum^\{len\}\_\{j=1\}\{(n-i-j+1)\\times\[s\[j\]<s\[1\]\]\}\\)，其中i为已经选择了i个字符

最后的话我们发现大于\\(s\[1\]\\)的字符和小于\\(s\[1\]\\)的字符是可以互换的，所以排列一波带走。

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int p=1e9+7;
    int n,k,a[30];
    char s[30];
    int f[30][30][2000][2];
    void add(int &a,int b){
        a=a+b>p?a+b-p:a+b;
    } 
    signed main(){
        scanf("%lld%lld",&n,&k);
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            a[i]=s[i]-'a'+1;
        k-=len;
        f[0][0][0][0]=1;
        int num=s[1]-'a'+1;
        int d=0,d2=0;
        for(int i=1;i<=len;i++){
            if(s[i]<=s[1]) num--;
            if(s[i]<s[1]){d+=i-1;d2++;}
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<=num;j++)
                for(int o=0;o<=n*(n+1)/2;o++)
                    for(int u=0;u<=1;u++)
                        if(f[i][j][o][u]){
                            add(f[i+1][j][o][u],f[i][j][o][u]);
                            add(f[i+1][j+1][o+n-i][u],f[i][j][o][u]);
                            if(!u&&i+len<=n)
                                add(f[i+len][j][o+(n-i)*d2-d][1],f[i][j][o][u]);
                        }
        int ans=f[n][num][k][1];
        for(int i=1;i<=num;i++)
            ans=ans*i%p;
        for(int i=1;i<=n-num-len;i++)
            ans=ans*i%p;
        printf("%lld\n",ans);
    }

转载于:https://www.cnblogs.com/youddjxd/p/11437230.html