COCI 2015/2016 部分题目题解

B. PERICA

先将 $a$ 数组排序，那么依次遍历，当前遍历到的点与前面的点组合时一定是最大的，而后面的点一定是不小于它的，也就是说，这时是它会产生贡献的唯一时刻，而产生贡献的次数就是前面的数中选 $k-1$ 个数的方案数。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const ll mod=1e9+7;
int n,k,num;
ll a[N];
ll fac[N],inv[N];
ll res,ans;

ll C(int a,int b)
{
    if(a<b) return 0;
    return fac[a]*inv[a-b]%mod*inv[b]%mod;
}

ll qpow(ll a,ll b)
{
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*(ll)i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(ll)(i+1)%mod;
    for(int i=k;i<=n;i++){
        ans=(ans+a[i]*C(i-1,k-1)%mod)%mod;
    }
    cout<<ans<<"\n";

    return 0;
}

C. SAVEZ

非常的 DP，状态转移也很显然，设 $dp[i]$ 表示以第 $i$ 个字符串为子序列结尾的最长子序列长度，令 $mp[st]$ 为上一个字符串 $st$ 出现的位置，那么转移方程就是：

$$dp[i]=max\{\,dp[mp\,[st]\,]\,\}+1$$

其中 $st$ 代表 $s[i]$ 的某个前后缀。

于是我们可以处理每个字符串的每一个前后缀，具体来说，新建两个字符串 $t1,t2$ 表示该字符串的前缀与后缀，那么每往前遍历一个字符，就在 $t1$ 末尾加一个字符，在 $t2$ 开头加一个对应位置的字符，然后当 $t1,t2$ 相等时就可以转移了。

现在似乎是做完了，但提交后我们会发现 TLE 了，这里就涉及到一个比较冷门的点，字符串的底层逻辑其实是一个 $vector$，所以在前面加字符与比较其实都是 $O(|s|)$ 的，所以这样的做法是过不了的。

我们想到，此时超时的原因是字符串的更改与比较，那么想要优化这一点就会很自然地想到 Hash，将字符串转为数字，这样每次在开头与末尾加入一位的复杂度与比较的复杂度就都是 $O(1)$ 的了。

到此为止，这道题其实已经做完了，但还有一个很容易忽略但会导致 MLE 的问题，就是按照正常的想当然的写法我们会在读入时读 $s[i]$，也就是开一个字符串数组，但如果这样写了提交的话，会发现 MLE 然后只有 $70$ 分，但我们发现记录某次读入读进的是哪个字符串是无用的，转移时不会用到，所以每次不需要用数组存，只用一个字符串就可以了，这样交上去就能过了，而且会发现空间很小。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<unordered_map>
using namespace std;

const int N=2e6+5;
const int p=131,mod=1e9+7;
int n,ans;
string s;
unordered_map<int,int> f;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        int t1=0,t2=0;
        int ma=0;
        int power=1;
        for(int j=0;j<s.size();j++){
            t1=(1ll*t1*p+s[j]-'A'+1)%mod;
            t2=(1ll*(s[s.size()-j-1]-'A'+1)*power+t2)%mod;
            power=1ll*power*p%mod;
            if(t1==t2){
                auto t=f.find(t1);
                if(t!=f.end()){
                    ma=max(ma,t->second);
                }
            }
        }
        f[t1]=max(f[t1],ma+1);
        ans=max(ans,f[t1]);
    }
    cout<<ans<<'\n';

    return 0;
}