讲师：will7101 内容：模拟与枚举
作业名单：
- 简单模拟：P2615,P1014
- 排序：P1102
- 枚举：P1618,P2010
- 子集枚举：P1036
- 全排列枚举：P1706
P2615 神奇的幻方
#include<stdio.h>
#include<cctype>
using namespace std;
int n;
int a[40][40];
int tot;
int x,y;
inline int read()
{
int x=0;short w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w?-x:x;
}
inline int tox()
{
if(tot==1) return 1;//根据口诀，我们先判断1的位置，1是第一行的中间，所以它的x是1
if((tot-1)%n==0) return x+1;//口诀是如果重复的话是往下填，但是我们可以发现，只要填的数的前一个数是n的倍数，那么，它一定会重复，所以我们往下填就可以了，不需要判重的。（比如n=3，现在要填4，那么4的前一个数是3,3是3的倍数，而3的右上角正好有数，所以4可以直接往下填）
x--;//这个是常规的，往右上角填充。
if(x==0) x=n;//如果上出格了，我们要往下填。
return x;
}
inline int toy()
{
if(tot==1) return (n+1)/2;//同上，1是第一行的中间，所以它的y是n/2的上取整，我们用(n+1)/2代替。
if((tot-1)%n==0) return y;//解释同tox过程的第二行。
y++;//常规的往右上角填充
if(y>n) y=1;//如果右出格了往左边填。
return y;
}
int main ()
{
n=read();
tot=1;
while(tot<=n*n)
{
x=tox(),y=toy();//通过函数来算出x和y可以节省代码量。
a[x][y]=tot;
tot++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",a[i][j]);
}
putchar('\n');
}
return 0;
}P1014 Cantor表
算法1：模拟，按题意一个个枚举
时间复杂度O(n),基本可以通过本题n≤$10^7$
算法2：发现Z字形的每条斜线可以快速枚举，即枚举
1/1 , 1/2 , 3/1 , 1/4 , 5/1 , 1/6……找到要求的第n项所在斜线，再一个个枚举或计算得出答案。
时间复杂度O(√n),可以通过n≤$10^{14}$
算法2.5：枚举第n项在哪一行，计算得出答案。
比算法2好写,时间复杂度同算法2
算法3：二分法
发现第i条斜线（即分子分母之和$=i+1$的所有项）中包含$i \times (i-1)/2+1$至$i \times (i+1)$中的每一项，所以可以二分分子分母之和，再根据分子分母之和的奇偶性直接计算第n项。
时间复杂度$O(log_{2}n)$,可以通过n≤$10^{18}$。
二分参考代码：
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
long long l=1,r,mid,n,a;
cin>>n;
r=n;
while(l<r)
{
mid=(l+r)/2;
if(mid*(mid+1)/2<n)l=mid+1;
else r=mid;
}
a=n-l*(l-1)/2;
if(l%2==0)cout<<a<<'/'<<l+1-a;
else cout<<l+1-a<<'/'<<a;
return 0;
}P1102 $A-B$数对
这道题用stl库里的map解决很快，只要把A-B=C转换成A-C=B，然后找这N个数里有几个B就解决了。
#include <cstdio>
#include <map>
using namespace std;
map <int,int> boo;
int c,n,a[200001];
long long s;
int main(){
scanf("%d%d",&n,&c);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
boo[a[i]]++; a[i]-=c;
}
for (int i=1;i<=n;i++) s+=boo[a[i]];
printf("%lld",s);
}P1706 全排列问题
c++中STL有这样一个函数：
next_permutation( )这是一个求一个排序的下一个排列的函数，可以遍历全排列。
#include<bits/stdc++.h>
using namespace std;
int n,r,a[100];//a数组用来储存每一种排列
bool used[100];//used数组记录数字是否使用过
void print(){//输出函数
for (int i=1;i<=n;++i)
cout<<setw(5)<<a[i];//常宽为5，注意setw( )这个函数
printf("\n");//换行
}
void Search(int t){//搜索函数，t表示搜索到第几位
if (t > n){//已经完成搜索
print();//输出一种答案
return;//退出
}
for (int i=1;i<=n;++i){//这里需要注意，题目是排列而不是组合，因此从1枚举到n
if (!used[i]){//当前枚举数字没有使用过
a[t] = i;//用a数组记录下来
used[i] = true;//已使用过
Search(t+1);//继续搜索
a[t] = 0;//回溯，这里可以不要，但对于这种基础题，要培养写回溯的习惯
used[i] = false;//回溯
}
}
}
int main()
{
cin>>n;//读入
Search(1);//搜索
return 0;
}P1036 选数
首先，我们写一个dfs函数，赋予三个变量，分别为step, sum, cnt。 我们用step 来记录当前选的是第几个数，sum 是这个数，cnt是已选的可行的数。同时，我们可以用一个a数组来记录我们所选的数。最后进行素数判断，用sqrt的朴素版即可。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[10001]; //记录所选的数
int n,k,sum,total; //total为总方案数
inline void print() //打印函数
{
printf("%d",total);
}
inline bool prime(int x) //素数判断
{
for(register int i=2;i<=sqrt(x);i++)
if(x%i==0) return false;
else return true;
}
inline void dfs(int step,int sum,int cnt)
{
if(step==n+1||cnt==k) //如果已经进行到了n+1次，或者是已经选了k个数
{
if(prime(sum) && cnt==k) //如果sum为一个素数且已经选了k个数
total++; //总方案书+1
return; //返回
}
dfs(step+1,sum+a[step],cnt+1); //继续搜索，选择下一个数
dfs(step+1,sum,cnt); //继续枚举不选择下一个数的情况
return;
}
int main()
{
scanf("%d %d",&n,&k);
for(register int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0,0); //从第个数开始搜
print(); //最后打印结果
return 0;
}P1618 三连击（升级版）
仍然使用STL中的next_permutation函数。
#include<bits/stdc++.h>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
int main()
{
int A,B,C,h=0;
cin>>A>>B>>C;
int t=A*B*C;
A=t/A;
B=t/B;
C=t/C;
do{
if((100*a[1]+10*a[2]+a[3])*A==(100*a[4]+10*a[5]+a[6])*B&&(100*a[1]+10*a[2]+a[3])*A==(100*a[7]+10*a[8]+a[9])*C)//如果符合比例；
{
cout<<a[1]<<a[2]<<a[3]<<" "<<a[4]<<a[5]<<a[6]<<" "<<a[7]<<a[8]<<a[9]<<endl;//输出
h++;
}
}while(next_permutation(a+1,a+10));//STL中的下一个排列函数；
if(h==0) cout<<"No!!!";//没有解输出NO；
return 0;
}P2010 回文日期
我们可以一次性把所有的回文全部构造出来放到一个列表当中，然后根据输入的data1和data2日期来查表求解
根据日期1～31日 和月份1～12 一共有31*12=372个组合；考虑到4月、6月、9月和11月这4个月没有31日；2月没有30和31两天. （至于2月29日，按照回文对照的年是9220年是闰年有效）有效的回文数是372-4-2=366个。
全部回文的构造方法： 把需要去除的6个年份建立一个表badYear[6]，并且按照从小到大大顺序排列好。 把月份和日期按照回文方式反转后构成两个表month[31] 和day[12]，并排序； 对这两个表建立双重循环，就可以生成372个从小到大有序排列的年份，在生成的过程当中剔除badYear数组当中已有的6个年份，结果保留在year[366]这个数组当中；再根据这个数组来成声回文数组：cycleText[366]。
#include <iostream>
using namespace std;
int main ( ) {
int month[12] = { 01, 10, 11, 20,
21, 30, 40, 50,
60, 70, 80, 90, };
int day[31] = { 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 30, 31, 32, 40, 41, 42, 50, 51, 52, 60, 61, 62, 70, 71, 72, 80, 81, 82, 90, 91, 92, };
int badYear[6] = { 320, 1311, 1320, 1340, 1360, 1390, };
// 不存在的年份有6个； 不能写0320 否则就是当做8进制数据来处理了
int year[366];
string cycleText[366];
int count=0;
int t =0;
for ( int i=0; i<31; i++) {
for ( int j=0; j<12; j++) {
int y = day[i]*100+month[j];
// badYear也是排序过的，所以每次只要和最小的比较就好了
if ( badYear[t]==y ) {
// 找到一个badYear，下次比较下一个badYear
t++;
continue;
} else {
year[count++]=y;
};
};
};
for ( int i=0; i<366; i++) {
char temp[9]; temp[8]=0;
int t=year[i];
temp[3] = temp[4] = (t%10) + '0'; t /= 10;
temp[2] = temp[5] = (t%10) + '0'; t /= 10;
temp[1] = temp[6] = (t%10) + '0'; t /= 10;
temp[0] = temp[7] = t + '0';
cycleText[i] = temp;
};
string data1, data2;
cin >> data1 >> data2;
if ( data1 > data2 ) swap(data1, data2);
// 确保data1d<=data2;
count = 0;
for ( int i=0; i<366; i++ ) {
if ( cycleText[i] < data1 ) continue;
if ( cycleText[i] > data2 ) break;
count ++;
};
cout << count;
return 0;
}
