「BZOJ3308」九月的咖啡店
Description
深绘里在九份开了一家咖啡让，如何调配咖啡民了她每天的头等大事
我们假设她有N种原料，第i种原料编号为i,调配一杯咖啡则需要在这
里若干种兑在一起。不过有些原料不能同时在一杯中，如果两个编号
为i,j的原料，当且仅当i与j互质时，才能兑在同一杯中。
现在想知道，如果用这N种原料来调同一杯咖啡，使用的原料编号之和
最大可为多少。
Input
一个数字N
Output
如题
Sample Input
10
Sample Output
30
HINT
1<=N<=200000
题解
直观感受是，所有质因数分别单独存在于一个数中
但是还要考虑到，俩个质因数一起存在于一个数中可以更优
如3，5，n=20
9+5<3*5
听说，至多俩个质因数存在于一个数中0.0
且一个大于根号n，一个小于根号n
于是就能费用流最大费用匹配了（不断增广至费用<0）
一个优化是，先假设所有质因数单独存在，把这部分收益加入答案
若a,b能配对
a，b连边 权值\(V_{ab}-V_a-V_b\)
这样费用流就跑的飞起了
|
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int ans,dis[200005]; int n,tot,T,cnt=1; int last[200005],pri[200005],q[200005]; bool mark[200005],inq[200005]; vector<int>q1,q2; struct edge{ int to,next,v,c; }e[2000005]; void insert(int u,int v,int w,int c) { e[++cnt]=(edge){v,last[u],w,c};last[u]=cnt; e[++cnt]=(edge){u,last[v],0,-c};last[v]=cnt; } bool spfa() { for(int i=0;i<=T;i++)dis[i]=-inf; int head=0,tail=1; q[0]=T;dis[T]=0; while(head!=tail) { int now=q[head];head++;if(head==200000)head=0; inq[now]=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].v&&dis[now]-e[i].c>dis[e[i].to]) { dis[e[i].to]=dis[now]-e[i].c; if(!inq[e[i].to]) { q[tail++]=e[i].to; if(tail==200000)tail=0; inq[e[i].to]=1; } } } return dis[0]>0; } int v(int n,int x) { ll t=x;while(x*t<=n)t*=x; return t; } void build() { for(int i=1;i<=tot;i++) { int t=pri[i]; if(t*2>n){ans+=t;continue;} if((ll)t*t<=n) { insert(0,i,1,0); ans+=v(n,t); q1.push_back(i); } else { insert(i,T,1,0); ans+=t; q2.push_back(i); } } for(int i=0;i<q1.size();i++) for(int j=0;j<q2.size();j++) { int a=pri[q1[i]],b=pri[q2[j]]; if(a*b<=n) { int tmp=v(n/b,a)*b; if(tmp>v(n,a)+b) insert(q1[i],q2[j],1,tmp-(v(n,a)+b)); } else break; } } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(e[i].v&&dis[x]-e[i].c==dis[e[i].to]&&!mark[e[i].to]) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; ans+=e[i].c*w;used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { for(int i=0;i<=T;i++)mark[i]=0; mark[T]=1; while(mark[T]) mark[T]=0,dfs(0,inf); } } int main() { n=read(); for(int i=2;i<=n;i++) { if(!mark[i])pri[++tot]=i; for(int j=1;pri[j]*i<=n&&j<=tot;j++) { mark[pri[j]*i]=1; if(i%pri[j]==0)break; } } T=n+1; build(); zkw(); printf("%d\n",ans+1); return 0; } |
计数器 9920757
OI 课件=>
OI 课件=>
黄学长你好，我认为“至多俩个质因数存在于一个数中，且一个大于根号n，一个小于根号n”不能成立。
考察n=624时 对于5和11 显然5<11<sqrt(n) 但是5^3+11^2=125+121<605=5*11*11
需要证明的应该是“当两个小于sqrt(n)的质数放在一起时,肯定不比让他们分别和大质数匹配更优”，而无法证明“两个小于sqrt(n)的质数分开放,比放在一起时更优”的错误结论
(ps.其实上述结论来自数学迷
51nod最新的比赛的最后一题貌似也是这个问题。标程给的是状压，但是实际上至多两个质因数存在于一个数中……不知道为什么。
怎么又看不到了。。。。。
对于大于sqrt（n）的质数：
对于在n/2+1到n中很明显都要取
对于在n/3+1到n/2中，这些数只有可能与2组合起来成为解之一，设x1<x2,那么x1*2+x2<x2*2+x1，所以在此区间内，只有一个数是有可能与其他质数组合成为解的（最大的那个），于是其他的数可以提前加到解里面（因为其与其他质数组合的解必定更差）
。。。。。。
对于在n/p+1到n/p中，设x1<x2,那么x1*p+x2<x2*p+x1，以此类推。
那么图的规模就只有sqrt（n），就可以过了。
神牛试试加这个优化看看如何http://wenzhang.baidu.com/page/view?key=49163da31247db6f-1428110857 看能不能跑到100ms之内
求证明“至多俩个质因数存在于一个数中，且一个大于根号n，一个小于根号n”
PE上并没有人给出证明