滚动数组+离线优化

阅读量：6290 次

发布时间：2019-06-22

本文共 5292 字，大约阅读时间需要 17 分钟。

邀请赛sb了，优化内存100年，保存下来，离线滚动数组优化下

B Array

JSZKC is the captain of the lala team.

There are

JSZKC has to arrange them as an array from left to right and let $h_ihi be the height of the i^{th}ithgirl counting from the left. After that, he can calculate the sum of the inversion pairs. A inversion pair counts if h_i>h_jhi>hj with i<ji<j.$

Now JSZKC wants to know how many different arranging plans with the sum of the inversion pairs equaling $h_ihidifferent in these two plans.$

As the answer may be very large, you should output the answer mod

Input Format

The input file contains several test cases, each of them as described below.

The first line of the input contains two integers $\le N \le 5000,0 \le K \le 5000)(1≤N≤5000,0≤K≤5000), giving the number of girls and the pairs that JSZKC asked.$

There are no more than

Output Format

An integer in one line for each test case, which is the number of the plans mod

样例输入

3 23 3

样例输出

题目来源

这个规律或者说推导还是没有那么难的，但是onsite就是想不到，被卡到死

#include
     
      using namespace std;const int N=5005,MD=1e9+7;vector
      
       
         >V[N];int dp[2][N],ans[N];int main(){    int tot=0,n,k;    while(~scanf("%d%d",&n,&k))V[n].push_back(make_pair(k,tot++));    for(int t=1,i; t
        
         =0?dp[i^1][j-t]:0))%MD+MD)%MD;        for(auto X:V[t])ans[X.second]=dp[i][X.first];    }    for(int i=0;i

2945: Adjacent Bit Counts

Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit: 32 Accepted:28

Description

For a string of n bits x₁, x₂, x₃, …, x_n, the adjacent bit count of the string (AdjBC(x)) is given by

x₁*x₂ + x₂*x₃ + x₃*x₄ + … + x_n-1*x_n

which counts the number of times a 1 bit is adjacent to another 1 bit. For example:

AdjBC(011101101) = 3

AdjBC(111101101) = 4

AdjBC(010101010) = 0

Write a program which takes as input integers n and k and returns the number of bit strings x of n bits (out of 2ⁿ) that satisfy AdjBC(x) = k. For example, for 5 bit strings, there are 6 ways of getting

AdjBC(x) = 2:

11100, 01110, 00111, 10111, 11101, 11011

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number (n) of bits in the bit strings, followed by a single space, followed by a decimal integer (k) giving the desired adjacent bit count. The number of bits (n) will not be greater than 100 and the parameters n and k will be chosen so that the result will fit in a signed 32-bit integer.

Output

For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of n-bit strings with adjacent bit count equal to k.

Sample Input

1 5 2

2 20 8

3 30 17

4 40 24

5 50 37

6 60 52

7 70 59

8 80 73

9 90 84

10 100 90

Sample Output

1 6

2 63426

3 1861225

4 168212501

5 44874764

6 160916

7 22937308

8 99167

9 15476

10 23076518

这个题目的式子还是没有那么难的吧，就是0和1的转换

初始代码

#include
       
        int dp[102][102][2],T,n,k,ca;int main(){    dp[0][0][0]=1;    for(int i=0; i<102; i++)        for(int j=1; j<102; j++)dp[i][j][0]=dp[i][j-1][0]+dp[i][j-1][1],dp[i][j][1]=(i==0?0:dp[i-1][j-1][1])+dp[i][j-1][0];    scanf("%d",&T);    while(T--)scanf("%d%d%d",&ca,&n,&k),printf("%d %d\n",ca,dp[k][n+1][0]);}

01滚动数组优化+先存进数组进行离线查询

#include
       
        using namespace std;#define pb push_back#define fi first#define se secondconst int N=105;vector
        
         
           >P[N];int dp[2][N][2],T,n,k,ca;int ans[1005];int main(){    scanf("%d",&T);    for(int i=0;i

同样的问题也出现在多校的莫队题目，我觉得这种离线的做法是非常优雅的

There are

nn apples on a tree, numbered from 11 to nn.

Count the number of ways to pick at most mm apples.

InputThe first line of the input contains an integer T

Each test case consists of one line with two integers n,mn,m (1≤m≤n≤105)(1≤m≤n≤105).

OutputFor each test case, print an integer representing the number of ways modulo 109+7109+7.Sample Input

25 21000 500

Sample Output

16924129523

因为状态的转移问题，所以这个可以分块转移

#include
       
        #include
        
         using namespace std;#define lson l,mi,rt<<1#define rson mi+1,r,rt<<1|1#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define pb push_back#define fi first#define se second#define ll long long#define sz(x) (int)(x).size()#define pll pair
         
          #define pii pair
          
           #define pq priority_queueconst int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;const ll LL_INF=0x3f3f3f3f3f3f3f3f;const double eps=1e-9,e=exp(1),PI=acos(-1.);int f[N],v[N],in_chunk[N],res[N];int C(int n,int m){    if(m<0||m>n) return 0;    return 1LL*f[n]*v[m]%MD*v[n-m]%MD;}vector
           
            
             
               > >lst[N];int main(){ v[0]=v[1]=f[0]=f[1]=1; for(int i=2; i
              
               X.se.fi)t=(t+MD-C(in,ik--))%MD; res[X.se.se]=t; } } for(int i=1; i<=T; ++i)printf("%d\n",res[i]); return 0;}