2020-2021 ACM-ICPC Latin American Regional Programming Contest K. Keylogger (dp,前缀和)

  • 2020-2021 ACM-ICPC Latin American Regional Programming Contest  K. Keylogger  (dp,前缀和)

  • 题意:你的键盘有\(k\)个按键,矩阵\(T_{i,j}\),表示第\(i\)个键和第\(j\)个键之间的输入频率,并带有一个\(L\)的修正,\(T\)的每一行都是非递减的,现在你忘了你的密码,但是你知道你密码的相邻两个字符的输入频率,你需要构造一个序列,这个序列需满足\(T_{S_i,S_{i+1}}-L \le P_i \le T_{S_iS_{i+1}}+L\),问你一共可以构造多少可能的序列并对\(10^9+7\)取模。

  • 题解:对于\(P_1\),我们要现在\(T\)中找一个合法的\({i,j}\),那么对于\(P_2\),我们就只能考虑\(j,x\),也就是说第一个位置必须是\(j\),那这很明显是可以状态转移的,所以这题我们考虑dp。比如说对于\(P_1\)我们找到了\(i,j\),那么\(P_2\)的贡献之一就可以由\(i,j\)转移而来,但是不好写,我们反着来,先找\(P_n\),因为这样如果我们有合法的位置,因为上一层算过了,就能直接转移到这一层来。具体转移就是看每一行,二分找一个满足\(T_{S_i,S_{i+1}}-L \le P_i \le T_{S_iS_{i+1}}+L\)的区间,说明我们可以从区间内的上一层的这些行转移过来。设\(dp[i][j]\)表示第\(P_i\)个间隔,第\(j\)行的所有可能序列数,假如\(pos1,pos2\)分别表示第\(j\)行合法的区间的左端点和右端点,所以有:\(dp[i][j]=\sum_{k=pos1}^{pos2}dp[i-1][k]\).这个复杂度是\(O(k)\)的,但因为区间是连续的所以可以用前缀和优化,操作之后\(dp[i][j]\)表示第\(P_i\)个间隔,前\(j\)行的所有可能序列数。

  • 代码:

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
    
    int k,L;
    int T[770][770];
    int n;
    int P[N];
    ll dp[100010][800];
    
    int main() {
        scanf("%d %d",&k,&L);
        for(int i=1;i<=k;++i){
            for(int j=1;j<=k;++j){
                scanf("%d",&T[i][j]);
            }
        }
        scanf("%d",&n);
        for(int i=1;i<n;++i){
            scanf("%d",&P[i]);
        }
        for(int i=1;i<=k;++i) dp[n][i]=i;
        for(int i=n-1;i>=1;--i){
            for(int j=1;j<=k;++j){
                dp[i][j]=dp[i][j-1]; //前缀和
                int pos1=upper_bound(T[j]+1,T[j]+1+k,P[i]+L)-T[j];
                int pos2=lower_bound(T[j]+1,T[j]+1+k,P[i]-L)-T[j];
                ll res1,res2;
                res1=dp[i+1][pos1-1];
                res2=dp[i+1][pos2-1];
                dp[i][j]=(dp[i][j]+res1-res2+mod)%mod;
            }
        }
        printf("%lld\n",dp[1][k]);
        return 0;
    }
    
    
上一篇:The 2021 ICPC Asia Regionals Online Contest (I)


下一篇:[Leetcode Weekly Contest]258