脚本宝典收集整理的这篇文章主要介绍了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",&amp;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("%lldn",dp[1][k]);
      return 0;
  }
  
  

脚本宝典总结

以上是脚本宝典为你收集整理的2020-2021 ACM-ICPC Latin American Regional Programming Contest K. Keylogger （dp,前缀和）全部内容，希望文章能够帮你解决2020-2021 ACM-ICPC Latin American Regional Programming Contest K. Keylogger （dp,前缀和）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。