NOIp2018集训test-9-6(am)

本文主要是介绍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多个，就可以过这道题了。

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=1e6+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int K,tot,tt[N],no[N],pp[N];
20 
21 template<typename T>void read(T &x)  {
22     char ch=getchar(); x=0; T f=1;
23     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24     if(ch=='-') f=-1,ch=getchar();
25     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27 
28 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }
29 LL lcm(LL a,LL b) { return a*b/gcd(a,b); }
30 
31 struct fs {
32     LL up,dn;
33     fs(LL up,LL dn):up(up),dn(dn){}
34     friend fs operator +(const fs&A,const fs&B) {
35         LL up=A.up*B.dn+A.dn*B.up,dn=A.dn*B.dn;
36         LL d=gcd(up,dn);
37         return fs(up/d,dn/d);
38     }
39     friend fs operator -(const fs&A,const fs&B) {
40         LL up=A.up*B.dn-A.dn*B.up,dn=A.dn*B.dn;
41         LL d=gcd(up,dn);
42         return fs(up/d,dn/d);
43     }
44 };
45 
46 int tmp;
47 int a[10],mx;
48 map<int,int>mp;
49 void dfs(int pos,int pr,fs now,LL nl) {
50     if(pos==K+1) {
51         if(now.up==now.dn) {
52             //For(i,1,pos-1) printf("%d ",a[i]);
53             //puts("");
54             tt[++tot]=nl;
55             mp[nl]=1;
56         }
57         return ;
58     }
59     if(now.up>=now.dn) return;
60     if(mp[nl]) return ;
61     fs tp=fs(1,1)-now;
62     int up=tp.dn*(K-pos+1)/tp.up;
63     for(int i=up;i>=pr;i--) {
64         tp=now+fs(K-pos+1,i);
65         if(tp.up<tp.dn) break;
66         a[pos]=i;
67         dfs(pos+1,i,now+fs(1,i),lcm(nl,i));
68     } 
69 }
70 
71 int main() {
72 #ifdef ANS
73     freopen(".in","r",stdin);
74     freopen(".out","w",stdout);
75 #endif
76     read(K);
77     dfs(1,2,fs(0,1),1);
78     cout<<tmp<<endl;
79     sort(tt+1,tt+tot+1);
80     int ans=0;
81     For(i,1,tot) if(!no[i]) {
82         For(j,i+1,tot) if(tt[j]%tt[i]==0) no[j]=1;
83         pp[++ans]=tt[i];
84     }
85     cout<<ans<<endl;
86     For(i,1,ans) cout<<pp[i]<<" ";
87     puts(""); 
88     Formylove;
89 }

打表

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 typedef long long LL;
16 typedef double db;
17 using namespace std;
18 int T;
19 LL A,B,K; 
20 LL bs[8][20]={{},{},
21     {1,2},
22     {2,3,4},
23     {3,4,6,10},
24     {6,5,6,8,9,14,21},
25     {6,6,8,10,14,44,52},
26     {15,7,8,9,10,12,15,22,33,39,52,55,68,102,114,138},
27 };
28 
29 template<typename T>void read(T &x)  {
30     char ch=getchar(); x=0; T f=1;
31     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
32     if(ch=='-') f=-1,ch=getchar();
33     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
34 }
35 
36 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }
37 LL lcm(LL a,LL b) { return a*b/gcd(a,b); }
38 
39 LL rc[8][33007][2];
40 int tot,tt[8];
41 map<LL,int>mp;
42 void pre() {
43     For(id,2,7) {
44         int up=(1<<bs[id][0])-1;
45         tot=0; mp.clear();
46         For(i,1,up) {
47             LL l=1; int cc=0;
48             For(j,1,bs[id][0]) if(i&(1<<(j-1)))
49                 l=lcm(l,bs[id][j]),cc++;
50             if(mp[l]) ;
51             else mp[l]=++tot;
52             int x=mp[l];
53             rc[id][x][0]=l;
54             rc[id][x][1]+=((cc&1)?1:-1);
55         }
56         tt[id]=tot;
57     }
58 }
59 
60 LL solve(LL n,int K) {
61     if(!n) return 0;
62     LL rs=0;
63     For(i,1,tt[K]) 
64         rs+=n/rc[K][i][0]*rc[K][i][1];
65     return rs;
66 }
67 
68 #define ANS
69 int main() {
70 #ifdef ANS
71     freopen("divisor.in","r",stdin);
72     freopen("divisor.out","w",stdout);
73 #endif
74     read(T);
75     pre();
76     while(T--) {
77         read(A); read(B); read(K);
78         printf("%lld\n",solve(B,K)-solve(A-1,K));
79     }
80     Formylove;
81 }

View Code

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的那一部分。具体可以看看代码。

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int up=3e6+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int mm[up],nn[up],cntm[up],cntn[up];
20 LL sm[up],sn[up],M,N,m0,md,n0,nd,ans;;
21 
22 template<typename T>void read(T &x)  {
23     char ch=getchar(); x=0; T f=1;
24     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25     if(ch=='-') f=-1,ch=getchar();
26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28 
29 priority_queue<int>que;
30 
31 #define ANS
32 int main() {
33 #ifdef ANS
34     freopen("rabbit.in","r",stdin);
35     freopen("rabbit.out","w",stdout);
36 #endif
37     read(M); read(N);
38     read(m0); read(md); mm[m0]++; cntm[m0]++; sm[m0]+=m0; 
39     read(n0); read(nd); nn[n0]++; cntn[n0]++; sn[n0]+=n0;
40     For(i,0,M-2) { m0=((LL)m0*58+md)%(N+1); mm[m0]++; cntm[m0]++; sm[m0]+=m0; }
41     For(i,0,N-2) { n0=((LL)n0*58+nd)%(M+1); nn[n0]++; cntn[n0]++; sn[n0]+=n0; }
42     M-=cntm[0]; N-=cntn[0];
43     cntm[0]=mm[0]=cntn[0]=nn[0]=0;
44     For(i,2,N) cntm[i]+=cntm[i-1],sm[i]+=sm[i-1];
45     For(i,2,M) cntn[i]+=cntn[i-1],sn[i]+=sn[i-1];
46     ans=1e18;
47     For(i,1,N) {
48         For(j,0,mm[i]) {
49             LL a=cntm[i]-j;
50             LL b=cntn[M-a];
51             LL tp=N*M+sm[i]-(LL)j*i-a*N+sn[M-a]-M*b+a*b;
52             ans=min(ans,tp);
53         }
54     }
55     printf("%lld\n",ans);
56     Formylove;
57 }
58 /*
59 6 4
60 1 1 3 3 2 2
61 5 4 4 4
62 */