滚动数组+离线 优化
邀请赛sb了,优化内存100年,保存下来,离线滚动数组优化下
B Array
JSZKC is the captain of the lala team.
There are NN girls in the lala team. And their height is [1,N][1,N] and distinct. So it means there are no two girls with a same height.
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 KK. Two plans are considered different if and only if there exists an ii with h_ihidifferent in these two plans.
As the answer may be very large, you should output the answer mod 10000000071000000007.
Input Format
The input file contains several test cases, each of them as described below.
- The first line of the input contains two integers NN and KK (1 \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 50005000 test cases.
Output Format
An integer in one line for each test case, which is the number of the plans mod 10000000071000000007.
样例输入
3 2 3 3
样例输出
2 1
题目来源
The 2018 ACM-ICPC China JiangSu Provincial Programming Contest
这个规律或者说推导还是没有那么难的,但是onsite就是想不到,被卡到死
#include<bits/stdc++.h> using namespace std; const int N=5005,MD=1e9+7; vector<pair<int,int> >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<N; t++) { i=t&1,dp[i][0]=1; for(int j=1;j<=t*(t-1)/2&&j<N; j++)dp[i][j]=((dp[i][j-1]+dp[i^1][j]-(j-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<tot;i++)printf("%d\n",ans[i]); }
2945: Adjacent Bit Counts
Total Submit: 32 Accepted:28
Description
For a string of n bits x1, x2, x3, …, xn, the adjacent bit count of the string (AdjBC(x)) is given by
x1*x2 + x2*x3 + x3*x4 + … + xn-1*xn
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 2n) 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
10
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
#include<stdio.h> 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<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second const int N=105; vector<pair<int,int> >P[N]; int dp[2][N][2],T,n,k,ca; int ans[1005]; int main() { scanf("%d",&T); for(int i=0;i<T;i++)scanf("%*d%d%d",&n,&k),P[k].pb(make_pair(n+1,i)); for(int ca=0,i;ca<N;ca++) { dp[0][0][0]=(ca==0),i=(ca&1); for(int j=1; j<N; j++) dp[i][j][0]=dp[i][j-1][0]+dp[i][j-1][1],dp[i][j][1]=dp[i^1][j-1][1]+dp[i][j-1][0]; for(auto X:P[ca])ans[X.se]=dp[i][X.fi][0]; } for(int i=0;i<T;i++) printf("%d %d\n",i+1,ans[i]); }
同样的问题也出现在多校的莫队题目,我觉得这种离线的做法是非常优雅的
B - Problem B. Harvest of Apples
Count the number of ways to pick at most mm apples.
InputThe first line of the input contains an integer TT (1≤T≤105)(1≤T≤105) denoting the number of test cases.
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
2 5 2 1000 500
Sample Output
16 924129523
因为状态的转移问题,所以这个可以分块转移
#include<stdio.h> #include<bits/stdc++.h> 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<long long,long long> #define pii pair<int,int> #define pq priority_queue const 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<pair<int,pair<int,int> > >lst[N]; int main() { v[0]=v[1]=f[0]=f[1]=1; for(int i=2; i<N; i++) f[i]=1LL*f[i-1]*i%MD,v[i]=1LL*v[MD%i]*(MD-MD/i)%MD; for(int i=2; i<N; i++) v[i]=1LL*v[i-1]*v[i]%MD; int T,chunk=sqrt(N),cnt = 1; for (int i = 1; i<N; i+=chunk,cnt++) for(int j=i; j<i+chunk && j<N; j++)in_chunk[j]=cnt; cnt--; scanf("%d",&T); for(int i=1,n,k; i<=T; ++i) { scanf("%d%d",&n,&k); lst[in_chunk[k]].push_back(make_pair(n,make_pair(k,i))); } for(int i=1; i<=cnt; ++i) if(lst[i].size()) { sort(lst[i].begin(),lst[i].end()); int t=0,in=lst[i][0].first,ik=-1; for(auto X:lst[i]) { while(in<X.fi)t=(t*1LL+t+MD-C(in++,ik))%MD; while(ik<X.se.fi)t=(t+C(in,++ik))%MD; while(ik>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; }
相关文章
- VB6中从内存中(Byte 字节数组)加载图片
- Java实现 LeetCode 525 连续数组
- Java实现 蓝桥杯VIP 算法提高 递归倒置字符数组
- C#数组之 []、List、Array、ArrayList应用
- Python实现字符串与数组相互转换功能示例
- 【数组&双指针】leetcode4. 寻找两个正序数组的中位数【困难, 未完】
- Leetcode.1248 统计「优美子数组」
- LeetCode-1774. 最接近目标价格的甜点成本【数组,背包问题,优化暴力,回溯】
- 华为OD机试 - 最大平分数组(Java & JS & Python)
- swift-for循环遍历,遍历字典,循环生成数组
- 【华为OD机试 2023】 计算数组中心位置(C++ Java JavaScript Python)
- 2344. 使数组可以被整除的最少删除次数-快速排序加贪心算法
- 浅析连续子向量,子数组和(一维,二维)问题
- array_map 去除数组参数里面左右两端空格
- 【PyTorch】numpy数组与pytorch的tensor相互转化
- HLS优化实战之数组