首页 > 代码库 > 2017-2-26福建四校联考
2017-2-26福建四校联考
哎我好菜啊 从来没打过表的萌新这次想打个表结果打太多了长度超限了（后来发现根本没必要打表）
---------我是分割线
A.矩形
给定一个2*n的矩形，每个位置有一个正权值，你要把它恰好分成m个矩形，使得所有矩形的和的最大值最小并求出最小的最大值。
n<=100000 m<=100
题解：
首先很显然m只是一个附加条件，如果你能分<m段，那么你一定能分m段。
看到最大值最小，最小值最大的问题，很自然想到二分答案。
然后我们用一个dp来check。用f[i]表示前i*2的矩形至少要分几段。
每次转移的时候，我们考虑分一个2*x的矩形还是分成多个1*x的矩形
可以预先二分处理好每个点在两种情况下最远从哪里更新，计算分f[i]时首先跳一次,表示分一个2*x的矩形
否则考虑分1*x的矩形，用两个指针分别表示两行，每次选择坐标大的指针向前跳，然后用两个指针最大值那里的dp值更新答案。
由于最多分m段，所以我们每个点最多跳m次就可以收工了。
复杂度n*(n+m)*logn
#include<iostream> #include<cstdio> #define INF 200000000 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m; ll maxn=0; ll s[100005],s1[100005],s2[100005]; int f[100005]; int l1[100005],l2[100005],l3[100005]; int getp(ll*S,int l,int r,ll lim) { int mid,ans,num=r; while(l<=r) { mid=(l+r)>>1; if(S[num]-S[mid]>lim) l=mid+1; else r=mid-1,ans=mid; } return ans; } bool check(ll lim) { for(int i=1;i<=n;i++) { l1[i]=getp(s,0,i,lim); l2[i]=getp(s1,0,i,lim); l3[i]=getp(s2,0,i,lim); f[i]=INF; } for(int i=1;i<=n;i++) { f[i]=min(f[i],f[l1[i]]+1); for(int j=i,k=i,l=1;l<=m&&(j||k);l++) { if(j<k)k=l3[k]; else j=l2[j]; f[i]=min(f[i],f[max(j,k)]+l); } } return f[n]<=m; } int main() { freopen("rec.in","r",stdin); freopen("rec.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;++i) s1[i]=read(),maxn=max(maxn,s1[i]); for(int i=1;i<=n;++i) s2[i]=read(),maxn=max(maxn,s2[i]); for(int i=1;i<=n;++i) { s1[i]=s1[i]+s1[i-1];s2[i]=s2[i]+s2[i-1]; s[i]=s1[i]+s2[i]; } ll l=maxn,r=1e15,mid,ans; while(l<=r) { mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } cout<<ans; return 0; }
2.数列
给定n,k定义一个正整数数列的贡献为所有数的乘积，求所有数列和为n，项数不超过k的数列的贡献之和。
n<=10^9,k<=30000
看到这题我就打表观察了一下，乱差分一下发现是一个多项式，然而多项式的一套理论和算法我都不会，所以我就继续乱搞，突然发现可以用组合数来表示！！！
然后发现没办法算阶乘（我傻，其实不用） 就分段打表阶乘...结果一不小心打多了....（gg）
出题人题解：
简单做法：可以用组合数。我是打表乱推的， 所以引用一下ditoly大佬的解释。
所以就是这样 复杂度O(k)
#include<iostream> #include<cstdio> using namespace std; #define mod 998244353 #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m; ll f[60005],v[60005]; ll ans=0; ll pow(int x,int p) { ll sum=1; for(ll i=x;p;p>>=1,i=(i*i)%mod) if(p&1) sum=sum*i%mod; return sum; } int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); n=read();m=read();f[0]=1;if(n<m) m=n; for(int i=1;i<m<<1;i++) f[i]=f[i-1]*i%mod; for(int i=1;i<m<<1;i++) v[i]=pow(f[i],mod-2); ll x=n; for(int i=1;i<=m;i++) { ans=(ans+x*v[(i<<1)-1]%mod)%mod; x=x*(n-i)%mod*(n+i)%mod; } cout<<ans; return 0; }
3.奇怪的题，没人做，也没数据，假装只有两道题。
2017-2-26福建四校联考
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。