「CF261X」Codeforces Round #160 (Div. 1)
A. Maxim and Discounts
挑要求最小的优惠方案啦，最贵的那几个显然要花钱买，赠品当然也是选最贵的。。。恩变成了子问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; 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 m,n; int mn=inf; int a[100005]; ll ans; int main() { m=read(); for(int i=1;i<=m;i++) { int x=read();mn=min(mn,x); } n=read(); for(int i=1;i<=n;i++) { a[i]=read(); ans+=a[i]; } sort(a+1,a+n+1); for(int i=n-mn;i>=1;i-=(mn+2)) { ans-=a[i]; if(i>=2)ans-=a[i-1]; } cout<<ans; return 0; } |
B. Maxim and Restaurant
f(i,j,k)表示前i个人，选了j个，消耗为k的方案数
然后枚举选的人数+组合数学，注意不重复统计答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; 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; } double ans,fac[55]; int n,p,a[55]; ll f[55][55][55]; int main() { fac[0]=1;for(int i=1;i<=50;i++)fac[i]=fac[i-1]*i; n=read(); for(int i=1;i<=n;i++)a[i]=read(); p=read(); f[0][0][p]=1; for(int i=0;i<n;i++) for(int j=0;j<=i;j++) for(int k=0;k<=p;k++) if(f[i][j][k]) { f[i+1][j][k]+=f[i][j][k]; if(k>=a[i+1])f[i+1][j+1][k-a[i+1]]+=f[i][j][k]; } for(int i=1;i<=n;i++) for(int j=0;j<=p;j++) ans+=f[n][i][j]*fac[i]*fac[n-i]; printf("%.9lf",ans/fac[n]); return 0; } |
C. Maxim and Matrix
发现第m+1行的和就是2^(m二进制1的个数+1)
则t是2的幂次才有解，求<=n的ans数量
从大到小枚举每一位，如果n的这一位为1
1.这一位ans放0，则剩下的1在ans的低位任意放，排列组合
2.这一位ans放1，变成一个子问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; 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; } ll ans; ll n,t,m=1; ll c[70][70]; int main() { n=read();t=read(); if(t&(t-1)){puts("0");return 0;} for(ll i=1;i<t;i<<=1)m++; c[0][0]=1; if(m==1)ans--;n++; for(int i=1;i<60;i++) { c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } for(int i=60;i>=0;i--) { if(m<0)break; if((1LL<<i)&n) { ans+=c[i][m]; m--; } } if(!m)ans++; cout<<ans<<endl; return 0; } |
D. Maxim and Increasing Subsequence
t大于max(maxb,n)是没有意义的。。。
t取个min然后由于n*maxb有限制就变成了最长上升子序列裸题，可以用树状数组水
这题有比较特殊的地方
考虑1-n的ans数组每个位置最多增加t次，所以可以暴力QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; 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 T,n,b,t; int a[1000005],f[1000005]; int main() { T=read();n=read();b=read();t=read(); t=min(t,min(n,b)); while(T--) { for(int i=1;i<=n;i++)a[i]=read(); memset(f,0,sizeof(f)); for(int i=1;i<=t;i++) for(int j=1;j<=n;j++) { f[a[j]]=f[a[j]-1]+1; for(int k=a[j]+1;k<=b&&f[a[j]]>f[k];k++) f[k]=f[a[j]]; } printf("%d\n",f[b]); } return 0; } |
E. Maxim and Calculator
找出从l到r中x的数量，满足x的任意一个分解式\(\prod^t_{i=1}k_i\)中\(maxk+t<=p\)
显然x不能有一个质因子大于p，写个搜索发现1到10^9符合条件的只有300w
把这些数排序后放在a数组，做个100*300w的dp
f(i,j)表示使用<=i的因子，第j个数的最少因子个数，只要\(i+f(i,j)<=p\) a[j]就符合条件
\(f(i,j)=f(i-1,pos[a[j]/i])\);
对于每个i，\(pos[a[j]/i]\)是递增的，所以可以不hash。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; 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 l,r,p,num; int cnt,top,pri[105]; int a[3000005]; int f[3000005]; bool ans[3000005]; bool mark[105]; void dfs(int k,int now) { if(now>r)return; if(k==cnt+1){a[++top]=now;return;} while(1) { dfs(k+1,now); if((ll)now*pri[k]>r)return; now*=pri[k]; } } void pre() { for(int i=2;i<=p;i++) { if(!mark[i])pri[++cnt]=i; for(int j=1;j<=cnt&&pri[j]*i<=p;j++) { mark[pri[j]*i]=1; if(i%pri[j]==0)break; } } dfs(1,1); sort(a+1,a+top+1); } void dp() { for(int j=2;j<=top;j++)f[j]=inf; for(int i=2;i<=p;i++) { int pos=0; for(int j=1;j<=top;j++) if(a[j]%i==0) { while(a[j]/i>=a[pos+1]&&pos<=top)pos++; f[j]=min(f[j],f[pos]+1); if(i+f[j]<=p&&!ans[j]&&a[j]>=l)num++,ans[j]=1; } } } int main() { l=read();r=read();p=read(); pre(); dp(); printf("%d\n",num); return 0; } |
计数器 9774128
OI 课件=>
OI 课件=>
还有D题真的是树状数组吗？树状数组一般会出现i&(-i)这样的东西啊
感觉更像是前缀和^_^
我写的并不是啊。。。
实测D题暴力第11个点会炸