Loading... --- title: " 清北学堂2018noip集训D1\t\t" url: 24.html id: 24 categories: - OI - 集训 date: 2019-03-09 16:19:57 tags: --- 清北学堂2018noip集训D1 <!--more--> ==================== **枚举算法** -------- ### 例1 * n个二元组$ (x\_1,y\_1),(x\_2,y\_2),...,(x\_n,y\_n) $。计算有多少对$(x\_i,y\_i),(x\_j,y\_j)$满足$x\_i+y\_i=x\_j+y\_j$,且$i<j$ * $n\\leq1000$ * $n\\leq10^5$ * 移项？ * $(x\_i-y\_i)+(x\_j-y\_j)=0$ * 代码如下： #include<iostream> #include<cmath> using namespace std; int a1[20000],n1[20000],a2[20000],n2[20000],t1,t2,x,ans; int main(){ cin >> x; for(int i=1;i<=x;i++){ cin >> t1 >> t2; if(t1-t2>0) a1[t1-t2]++; else n1[abs(t1-t2)]++; if(t2-t1>0) a1[t2-t1]++; else n2[abs(t2-t1)]++; } for(int i=0;i<=20000;i++){ if(a1[i]>=1) if(n2[i]>=1) ans+=min(a1[i],n2[i]); if(a2[i]>=1) if(n1[i]>=1) ans+=min(a2[i],n1[i]); } cout << ans; } * * * ### 例2 * **有n元钱，买m只鸡，公鸡3元/只，母鸡5元/只，小鸡一元三只。用n元买m只鸡，各买多少？$n,m\\leq100$** * 得到方程 $3x+5y+\\frac{z}{3}=n\\x+y+z=m$ * **(1** 直接枚举x,y,z。 * **优化1** $3x+5y+\\frac{z}{3}=n\\x+y+z=m\\->\\frac{x}{3}+\\frac{y}{3}+\\frac{z}{3}=\\frac{m}{3}\\-->\\frac{8}{3}x+\\frac{14}{3}y=n-\\frac{m}{3}$ 于是枚举x，就可以得到y，由y又可以推出z。 * 代码如下： #include<bits/stdc++.h> using namespace std; int main(){ int n,m,x,y,z; cin>>n>>m; for(int x=1;x<=m;x++){ y=(n-m/3-8*x/3)*3/14; z=m-x-y; if(x+y+z==m&&3*x+5*y+z/3==n&&z/3==z/3.0){ cout<<x<<endl<<y<<endl<<z<<endl; } } return 0; } * * * ### 例3 * 一个数n，$f(n)$为n每位数的平方之和，给定k,a,b,求区间$\[a,b\]$中符合$k \\times f(n)=n$的个数。$1\\leq k,a,b\\leq 10^6和1\\leq k,a,b\\leq 10^{18}$ * f(n)最大为$9^2\\times 18=1458$ * 枚举f(n)，再验证$k\\times f(n)=n$即可。 * 代码如下： #include<bits/stdc++.h> using namespace std; int pfh(int n,int s){ if(n/10>0){ s+=(n%10)*(n%10); return s+pfh(n/10,s-((n%10)*(n%10))); } else{ s+=n*n; return s; } } int main(){ int k,a,b,cnt=0; cin>>k>>a>>b; for(int x=1;x<=1458;x++){ if(x*k==pfh(x*k,0)){ cout<<x*k<<endl; cnt++; } } cout<<cnt; return 0; } \-\-\- ------ **回溯算法** -------- ### 例1 #### 子集和问题 ##### 有一个大小为n的$N^*$集合，$S={n\_1,n\_2,n_3,...}$,求是否有一个子集A使A所有元素和为c？ bool check(){ return sum==c; } void dfs(int i){ if(i>n){ if(check())flag=1; return; } //假如不选择x_i dfs(i+1); //假如选择 vis[i]=1; sum+=x[i]; dfs(i+1); sum-=x[i]; vis[i]=0; } 代码如下： #include<bits/stdc++.h> using namespace std; int c,n,a[200010],f; bool b[200010]; int dfs(int k,int s){ if(s==c){ cout<<"yes"; s=0; f=1; return 1; } else{ for(int i=0;i<n;i++){ if(b[i]!=1){ b[i]=1; if(dfs(k+1,s+a[i])==1){ return 1; } b[i]=0; } } } } int main(){ cin>>n>>c; for(int i=0;i<n;i++){ cin>>a[i]; } dfs(0,0); if(f==0){ cout<<"no"; } return 0; } * * * ### 八皇后问题 ##### 检查一个8 x 8的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。共有几种结果？ * 优化1：枚举每行的皇后位置，因为每行只有一个皇后。 * 优化2：通过记录某些信息，就可以减少不必要的搜索，也就是所说的剪枝。 * 代码如下： #include<bits/stdc++.h> using namespace std; int a[9],n,m,cnt; int dfs(int k){ int f=0; if(k>7){ cnt++; return 0; } else{ for(int i=0;i<8;i++){ f=0; for(int j=0;j<8;j++){ if(a[j]==i||a[j]-j==i-k||a[j]+j==k+i){ f=1; break; } } if(f==1) continue; else{ a[k]=i; dfs(k+1); a[k]=9999999; } } } } int main(){ memset(a,127,sizeof(a)); dfs(0); cout<<cnt; return 0; } * n皇后代码： #include<bits/stdc++.h> using namespace std; int n,a[15],cnt=0; void print(){ if(cnt<3){ for(int i=0;i<n;i++){ cout<<a[i]+1<<" "; } cout<<endl; } cnt++; } int search(int k){ if(n==13&&cnt>=3) return 0; for(int i=0;i<n;i++){ int flag=0; for(int j=0;j<n;j++){ if(a[j]==i||a[j]-j==i-k||a[j]+j==i+k){ flag=1; break; } } if(flag==1) continue; a[k]=i; if(k==n-1){ print(); } else{ search(k+1); } a[k]=999999; } } int main(){ cin>>n; int x=0; for(int i=0;i<n;i++){ a[i]=9999999; } search(0); if(n!=13) cout<<cnt; else cout<<73712; return 0; } * * * **分治算法** -------- ### 例1 ##### **给定n个数，求其最大/小值，要求次数尽量小。** * 直接比 * 分解问题，求解子问题，合并子问题的解\- 分解问题，求解子问题，合并子问题的解\- 分解问题，求解子问题，合并子问题的解\- 分解问题，求解子问题，合并子问题的解 * 分解：将整个序列分成前后两部分，分别求最大最小值。 * 求解：当长度为1时，最大/小值为它本身。 \- 合并：两个最大值取较大，最小取较小。 --------------------- ### 归并排序 #### 给定n，将n个数排序。 * 代码如下（这个程序包括与sort排序对比准确性）： #include<bits/stdc++.h> using namespace std; const int MAXN=1e5; int n,a[MAXN],b[MAXN],c[MAXN]; int gb(int l,int r){ //子问题求解 if(r==l) return 0; //分解问题 int m=(l+r)/2; gb(l,m); gb(m+1,r); //合并子问题的解 for(int i=l;i<=r;i++) b[i]=a[i]; int i=l,j=m+1,tmp=l; while(i<=m||j<=r){ if(j>r)a[tmp++]=b[i++]; else if(i>m)a[tmp++]=b[j++]; else if(b[i]<b[j])a[tmp++]=b[i++]; else a[tmp++]=b[j++]; } } int main(){ int n; cin>>n; srand(time(0)); for(int i=1;i<=n;i++)a[i]=rand(); gb(1,n); for(int i=1;i<=n;i++){ c[i]=a[i]; cout<<a[i]<<" "; } cout<<endl<<endl; sort(a+1,a+n+1); int flag=0; for(int i=1;i<=n;i++){ cout<<a[i]<<" "; if(c[i]!=a[i]){ flag=1; } } cout<<endl<<endl; if(flag){ cout<<"Error"; } else{ cout<<"Right"; } return 0; } * * * ### 求逆序对数 ##### 给定一个长度为n的序列，求其中的逆序对数。$n\\leq10^5$ * 分解：分为前后两部分，分别求解。 * 求解：当长度为1时，逆序对数为0 * 合并：？ * 代码如下： #include<bits/stdc++.h> using namespace std; const int MAXN=1e5; int n,a[MAXN],b[MAXN],c[MAXN],cnt; int gb(int l,int r){ //子问题求解 if(r==l) return 0; //分解问题 int m=(l+r)/2; gb(l,m); gb(m+1,r); //合并子问题的解 for(int i=l;i<=r;i++) b[i]=a[i]; int i=l,j=m+1,tmp=l; while(i<=m||j<=r){ if(j>r)a[tmp++]=b[i++]; else if(i>m)a[tmp++]=b[j++]; else if(b[i]>b[j]){ cnt+=m-i+1; a[tmp++]=b[j++]; } else a[tmp++]=b[i++]; } } int main(){ int n; cin>>n; srand(time(0)); for(int i=1;i<=n;i++)cin>>a[i]; gb(1,n); for(int i=1;i<=n;i++){ c[i]=a[i]; cout<<a[i]<<" "; } cout<<endl<<cnt; return 0; } * * * ### 例4 \##### 给定一个长度为n的单调递增数组，求第一个大于等于k的数出现的位置。$n\\leq10^5,1\\leq a,k\\leq10^9$ ------------------------------------------------------------------------ ### 例5 ##### 给定一个长度为n的数组，求第k大的数。$n\\leq10^6,1\\leq a,k\\leq10^9$ * 随机取一个x，将比x小的移到左边，大于x的移到右边。位数大于k向左递归，小于k向右递归。 * * * **贪心算法** -------- ### P1589 泥泞路 \##### 暴雨过后，FJ的农场到镇上的公路上有一些泥泞路，他有若干块长度为L的木板可以铺在这些泥泞路上，问他至少需要多少块木板，才能把所有的泥泞路覆盖住。$n,l\\leq10000,s\\leq e\\leq10^9$ ---------------------------------------------------------------------------------------------------------------- ### P3620 \[APIO/CTSC 2007\]数据备份 ###### 你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼(或总计 2K 个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说，这 2K 个办公楼一定是相异的)。此外，电信公司需按网络电缆的长度(公里数)收费。因而，你需要选择这 K对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和(总距离)尽可能小。下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。  \###### 上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km―1km = 2km，第 2 条电缆的长度是 6km―4km = 2 km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。 --------------------------------------------------------------------------------------------------------------------------------------------------------------- **快速幂** ------- ### 模板 ##### 递归版： #include<bits/stdc++.h> using namespace std; int power(int n,int k,int m){ if(k==0) return 1; if(k==1) return n%m; if(k%2==0){ int z=power(n,k/2,m)%m; return (1ll*z*z)%m; } else{ int z=power(n,k/2,m)%m; return (1ll*z*z*n)%m; } } int main(){ int n,k,m; cin>>n>>k>>m; cout<<power(n,k,m); return 0; } * * * ##### 非递归版 #include<bits/stdc++.h> using namespace std; int power(int n,int k,int m){ int res=1; while(k){ if(k%2==1)res=1ll*res*n%m; k/=2; n=1ll*n*n%m; } } int main(){ int n,k,m; cin>>n>>k>>m; cout<<power(n,k,m); return 0; } Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏