NOIp2018集训test-9-6(am)

Problem A. divisor

发现x为k可表达一定可以表示成这种形式，如k=3,x=(1/3+1/2+1/6)x。

于是可以搜索k(k<=7)个1/i加起来等于1的情况，如果一个数是这些i的lcm的倍数这个数就是k可表达的。

std并没有给出它的搜索程序，我的搜索写得很不优秀，所以我写搜索写了很久。

一是用double会炸精度，于是我手写了分数类。

然后是搜的时候按从大到小搜，每次会有一个上限。

这样爆搜的话可以搜出6的，要搜出7的的话，因为实际上搜的是lcm,记录一下出现过的lcm,如果中途出现了这个lcm就直接return,。每次搜的时候是从up到dn搜的，一开始我在想要让lcm小的先出现应该先搜小的啊，李巨告诉我，先搜小的会让后面的up变得很大，而先搜大的，最开始的up也就7，后面的up也被限制得比较小，能先跑出较小的lcm，让这个优化有用。

这样对于每个k能搜出一些数，如果是这些数的倍数就可以k表达，这一步李巨直接ycl打表法代替，打出k表达数，从小到达一个一个把剩下的的倍数删除直到删完所有数，吊打爆搜。

这样就可以容斥做了，如果直接容斥最大的个数有15会炸，发现一些数的乘积是重复出现的，预处理出所有不同的数前面的容斥系数，不同的最多好像是300多个，就可以过这道题了。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=1e6+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int K,tot,tt[N],no[N],pp[N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }

 LL lcm(LL a,LL b) { return a*b/gcd(a,b); }

 struct fs {

     LL up,dn;

     fs(LL up,LL dn):up(up),dn(dn){}

     friend fs operator +(const fs&A,const fs&B) {

         LL up=A.up*B.dn+A.dn*B.up,dn=A.dn*B.dn;

         LL d=gcd(up,dn);

         return fs(up/d,dn/d);

     }

     friend fs operator -(const fs&A,const fs&B) {

         LL up=A.up*B.dn-A.dn*B.up,dn=A.dn*B.dn;

         LL d=gcd(up,dn);

         return fs(up/d,dn/d);

     }

 };

 int tmp;

 int a[],mx;

 map<int,int>mp;

 void dfs(int pos,int pr,fs now,LL nl) {

     if(pos==K+) {

         if(now.up==now.dn) {

             //For(i,1,pos-1) printf("%d ",a[i]);

             //puts("");

             tt[++tot]=nl;

             mp[nl]=;

         }

         return ;

     }

     if(now.up>=now.dn) return;

     if(mp[nl]) return ;

     fs tp=fs(,)-now;

     int up=tp.dn*(K-pos+)/tp.up;

     for(int i=up;i>=pr;i--) {

         tp=now+fs(K-pos+,i);

         if(tp.up<tp.dn) break;

         a[pos]=i;

         dfs(pos+,i,now+fs(,i),lcm(nl,i));

     }

 }

 int main() {

 #ifdef ANS

     freopen(".in","r",stdin);

     freopen(".out","w",stdout);

 #endif

     read(K);

     dfs(,,fs(,),);

     cout<<tmp<<endl;

     sort(tt+,tt+tot+);

     int ans=;

     For(i,,tot) if(!no[i]) {

         For(j,i+,tot) if(tt[j]%tt[i]==) no[j]=;

         pp[++ans]=tt[i];

     }

     cout<<ans<<endl;

     For(i,,ans) cout<<pp[i]<<" ";

     puts("");

     Formylove;

 }

打表

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 typedef long long LL;

 typedef double db;

 using namespace std;

 int T;

 LL A,B,K;

 LL bs[][]={{},{},

     {,},

     {,,},

     {,,,},

     {,,,,,,},

     {,,,,,,},

     {,,,,,,,,,,,,,,,},

 };

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }

 LL lcm(LL a,LL b) { return a*b/gcd(a,b); }

 LL rc[][][];

 int tot,tt[];

 map<LL,int>mp;

 void pre() {

     For(id,,) {

         int up=(<<bs[id][])-;

         tot=; mp.clear();

         For(i,,up) {

             LL l=; int cc=;

             For(j,,bs[id][]) if(i&(<<(j-)))

                 l=lcm(l,bs[id][j]),cc++;

             if(mp[l]) ;

             else mp[l]=++tot;

             int x=mp[l];

             rc[id][x][]=l;

             rc[id][x][]+=((cc&)?:-);

         }

         tt[id]=tot;

     }

 }

 LL solve(LL n,int K) {

     if(!n) return ;

     LL rs=;

     For(i,,tt[K])

         rs+=n/rc[K][i][]*rc[K][i][];

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("divisor.in","r",stdin);

     freopen("divisor.out","w",stdout);

 #endif

     read(T);

     pre();

     while(T--) {

         read(A); read(B); read(K);

         printf("%lld\n",solve(B,K)-solve(A-,K));

     }

     Formylove;

 }

Problem B. rabbit

容易建出最大流模型，s向每堆胡萝卜连mi的边，每堆干草向t连ni的边，每堆胡萝卜向每堆干草连1的边。

根据最大流最小割定理，答案就是这个图的最小割，发现这个图的最小割可以表示成，s和胡萝卜的边中选a条边权和为Sa割掉，t和干草的边中选b条边权和为Sb的割掉，中间再割掉(n-a)*(m-b)条边。

ans=Sa+Sb+(n-a)*(m-b)

展开

ans=n*m+Sa-a*m+Sb-b*n+a*b

把权值全放到每条边上，a中的边权本为w的边权就是w-m，b中的边权本为w的边权就是w-n+a，最后的常数n*m不用管。

那么枚举a中选多少条边，按边权排序后选最小的那么多条，再选对于的b边权中小于0的那一部分。具体可以看看代码。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int up=3e6+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int mm[up],nn[up],cntm[up],cntn[up];

 LL sm[up],sn[up],M,N,m0,md,n0,nd,ans;;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 priority_queue<int>que;

 #define ANS

 int main() {

 #ifdef ANS

     freopen("rabbit.in","r",stdin);

     freopen("rabbit.out","w",stdout);

 #endif

     read(M); read(N);

     read(m0); read(md); mm[m0]++; cntm[m0]++; sm[m0]+=m0;

     read(n0); read(nd); nn[n0]++; cntn[n0]++; sn[n0]+=n0;

     For(i,,M-) { m0=((LL)m0*+md)%(N+); mm[m0]++; cntm[m0]++; sm[m0]+=m0; }

     For(i,,N-) { n0=((LL)n0*+nd)%(M+); nn[n0]++; cntn[n0]++; sn[n0]+=n0; }

     M-=cntm[]; N-=cntn[];

     cntm[]=mm[]=cntn[]=nn[]=;

     For(i,,N) cntm[i]+=cntm[i-],sm[i]+=sm[i-];

     For(i,,M) cntn[i]+=cntn[i-],sn[i]+=sn[i-];

     ans=1e18;

     For(i,,N) {

         For(j,,mm[i]) {

             LL a=cntm[i]-j;

             LL b=cntn[M-a];

             LL tp=N*M+sm[i]-(LL)j*i-a*N+sn[M-a]-M*b+a*b;

             ans=min(ans,tp);

         }

     }

     printf("%lld\n",ans);

     Formylove;

 }

 /*

 6 4

 1 1 3 3 2 2

 5 4 4 4

 */

Problem C. drinks

什么神题（解），不会。

巴特西

NOIp2018集训test-9-6(am)

最新文章

热门文章