缓存机制
在电脑中有一种比内存读入还要快的东西叫做缓存，其定义是对于从内存里读入一个数组时，计算机会预测剩余的连续的部分数组是否会被用到，所以将他存进缓存，这样可以直接按顺序读入，不用查询，更加快。
那么对于我们的二维数组 (f[i][j]) 他是以长度为 (1 imes j) 的 (i) 个线段组成一个线性的长链，所以连续的数字之间是 (f[1][1],f[1][2]), 而并不是 (f[1][1],f[2][1]),
那么推广到我们的 (for) 循环上，若我们按照外层 (i)，内层 (j) 的顺序循环，得到的数组就是按照计算机存储顺序调用，因此可以直接从缓存里读入 ，但是当我们反过来，计算机无法预测我们的顺序，即缓存中的数组是无用的（当前），那么只能调用内存，时间的差距大约在 (10)左右
所以说对于循环的枚举顺序关系到时间复杂度是很重要的.尤其是矩阵乘除，不同的运输顺序造成的极值可达 (4) 倍，这就是后几个点被卡的原因，特别亏。
二分
解决问题，有 (m) 询问，数列已经排好序，求出小于 (x) 的有多少个
思路
知道最大的 (a_i<= x) ，那么就可以说答案就是 (i)
int n,m,a[B];
int main() {
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
while(m--)
{
int x=read();
int l=1, r=n, ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]<=x) l=mid+1, ans=mid;
else r=mid-1;
}
printf("%d
",ans);
}
return 0;
}
二分答案
给定 (N) 根绳子，要求你从中分出 (K) 段绳子，使得每段绳子长度一样并且必须是整数，问这 (K) 段绳子最长能够是多少。
思路
这个题应该好好地说一下，浪费了我一下午，让我的对double 和int有了重新的认识
做法的话很简单，二分长度 看行成的段数是否大于 (K),二分答案就好了
但是这个题需要用的精度，因为在二分的过程中得到的数始终是小数，但是我们定义的是整形，所以会无限死循环
再就是在最后的强制类型转换中，我发现了三种不用的输出方式，得到了三种不同的分数，过程惨痛
cout<<a;
这样直接是双精度输出，没什么变化
printf("%.f",a)
这个可神了，居然会自动四舍五入，太神奇了，我才知道，答案部分正确
int s=(int)a;
cout<<s;
强制类型转换，这个就可以将整数部分完整的得到了，这也是最后的正确答案，
double s[B],sum;
const double esp=1e-8;
int n,k;
main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
cin>>n>>k;
double mx=0;
for (int i=1;i<=n;i++)
{
cin>>s[i];
mx=max(mx,s[i]);
}
double l=0,r=mx;
while(l+esp<r)
{
double mid=(l+r)/2;
int num=0;
for (int i=1;i<=n;i++) num+=s[i]/mid;
if(num>=k) l=mid;
else r=mid;
}
int s=(int)l;
cout<<s;
return 0;
}
贪心
国王游戏
怎么对大臣排序？？？
绝对按照右手排，貌似不对,md
假设 (n==2) 时候的到一种 (cmp) 的函数，然后直接排序就可以了，这就是贪心，信息学是一门不需要证明的许可，不用证明，对于(\%90) 的贪心题都可这么做，(nb)
思路
我们不妨设 (n=2) 时，最大获益金币的人最小
那第一个人 (A) 为 (a.r,a.l), 第二个人 (B) 为 (b.r,b.l)
设皇上的左右手分别为 (z[0].l, z[0].r)
当 (A) 在 (B) 的前边时
(A) 的钱
[frac{z[0].l}{a.r}
]
(B) 的钱
[frac{z[0].l imes a.l}{b.r}
]
答案 (v1) 为 (max{frac{z[0].l}{a.r},frac{z[0].l imes a.l}{b.r}})
当 (B) 在 (A) 前面时
同理可得答案 (v2) 为 (max{frac{z[0].l}{b.r},frac{z[0].l imes b.l}{a.r}})
最终答案就是 (max{v1,v2})
那么当 (n!=2) 时呢，假设现在就这两个人需要我们讨论，我们不是需要国王到自己前面人左手的数嘛，我们设这个数为 (x) 那么式子的就是变成
[v1=max{frac{x}{a.r},frac{x imes a.l}{b.r}}\
v2=max{frac{x}{b.r},frac{x imes b.l}{a.r}}\
]
答案就是 (ans=max{v1,v2})
当我们把分母去掉即，(v1,v2) 都乘以(a.r imes b.r)
化简得
[v1=max{b.r imes x,x imes a.l imes a.r}\
v2=max{a.r imes x,x imes b.l imes b.r}\
]
我们发现 (x) 可以消掉，即在这里答案的大小不受 (x) 的影响，那么我们的式子就可以变成
[v1=max{b.r,a.l imes a.r}\
v2=max{a.r, b.l imes b.r}\
]
有了式子我们就可以利用冒泡排序，时间复杂度为 (O(n^2))
//冒泡排序
#include <iostream>
using namespace std;
struct node{
int l,r;
};
node z[100010];
int cmo(node a, node b)//a是否放在b的前面
{
int v1 = max(z[0].l/a.r, z[0].l*a.l / b.r);
int v2 = max(z[0].l/b.r, z[0].l*b.l / a.r);
if(v1<v2) return 1;
else return 0;
}
int main()
{
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++)
{
if(cmp(z[j+1],z[j])) swap(z[j+1], z[j]);
}
}// O(n^2)
其实就变成了比较这四个数的大小，这样就可以进行贪心了
贪心式子是否可以优化呢？
我们不难发现 (b.r<b.l imes b.r) 和 (a.r<a.l imes a.r)
那么我们比较这是两个还有意义嘛，他们两个本质上就比右侧的大，所以剔除就好了，因此式子就化简成
[ans=max{b.r imes b.l, a.r imes a.l}
]
贪心化简的本质
- 去分母
- 去除公共项
- 出去无用项，即不可能更好
- 简化完毕！
struct node{
int l, r;
};
node z[B];
int ans=1, n;
int cmp(node a, node b)
{
return a.l*a.r<b.l*b.r;
}
int main() {
scanf("%d",&n);
scanf("%d%d",&z[0].l,&z[0].r);
for (int i=1;i<=n;i++)
scanf("%d%d",&z[i].l,&z[i].r);
sort(z+1,z+1+n,cmp);
for (int i=0;i<n;i++) ans*=z[i].l;
printf("%d",ans/z[n].r);
return 0;
}
高精做法
#include <bits/stdc++.h>
using namespace std;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
int a;
int b;
long long a_b;
}node[1010];
int read() {
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
void times(int x) {
memset(add,0,sizeof(add));
for(int i=1;i<=ans[0];i++) {
ans[i]=ans[i]*x;
add[i+1]+=ans[i]/10;
ans[i]%=10;
}
for(int i=1;i<=ans[0]+4;i++) {
ans[i]+=add[i];
if(ans[i]>=10) {
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
if(ans[i]!=0) {
ans[0]=max(ans[0],i);
}
}
return ;
}
int divition(int x) {
memset(add,0,sizeof(add));
int q=0;
for(int i=ans[0];i>=1;i--) {
q*=10;
q+=ans[i];
add[i]=q/x;
if(add[0]==0 && add[i]!=0) {
add[0]=i;
}
q%=x;
}
return 0;
}
bool compare() {
if(sum[0]==add[0]) {
for(int i=add[0];i>=1;i--) {
if(add[i]>sum[i]) return 1;
if(add[i]<sum[i]) return 0;
}
}
if(add[0]>sum[0]) return 1;
if(add[0]<sum[0]) return 0;
}
void cp () {
memset(sum,0,sizeof(sum));
for(int i=add[0];i>=0;i--) {
sum[i]=add[i];
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
int n=read();
for(int i=0;i<=n;i++) {
node[i].a=read(),node[i].b=read();
node[i].a_b=node[i].a*node[i].b;
}
sort(node+1,node+n+1,cmp);
ans[0]=1,ans[1]=1;
for(int i=1;i<=n;i++) {
times(node[i-1].a);
divition(node[i].b);
if(compare()) {
cp();
}
}
for(int i=sum[0];i>=1;i--)
printf("%d",sum[i]);
return 0;
}
输入输出优化
快出
char s[10000000];
int l=0;
void print(int x)
{
int y=0,z=0;//倒写
while (x!=0)
{
y=y*10+x%10;
z++;
x/=10;
}
for (int a=1;a<=z;a++)
{
s[l++]=y%10+'0';
y/=10;
}
s[l++]='
';
}
空间的计算方法
- (char) 1 字节
- (int) 4字节
- (long long) 8 字节
- (1M=1024K)
- (10^7=10M)
搜索
- BFS
- DFS
题型： 给 (N) 个数选 (k) 个数
求和最小---最优解问题
求方案数---解数量问题
给出一种符合条件的方案---可行解问题
如何判断使用哪种搜索手段
BFS
- 必须最优解问题，从当前状态到另外一个状态代价变化 必须为1
DFS
- ，剩下的都是DFS
搜索优化
可行性剪枝
明显不可能的解直接扔掉
最优性剪枝
不可能成为最有解的剪枝
void dfs(int p, int nowsum, int nowuse)//考虑地p，和为nowsum,选了nowuse个数
{
if (nowuse>k) return;//可行性剪枝
if (nowuse + n-p+1 < k) return;//可行性剪枝
if (nowsum>=ans) return;//最优性剪枝
if（p>n）
{
ans=min(nowsum,k);
return;
}
dfs(p+1,nowsum,nowuse);
dfs(p+1,nowsum+a[p];nowsue+1);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0,0);
printf("%d",ans);
return 0;
}
搜索顺序优化
如果排序后再接搜索的话，搜索顺序会受到影响，即先搜索可行性优解
可以选择可以使答案更好或者更快地到答案的题
靶心数
void dfs(int p, int nowsum, int nowuse)//考虑地p，和为nowsum,选了nowuse个数
{
if (nowuse>k) return;//可行性剪枝
if (nowuse + n-p+1 < k) return;//可行性剪枝
if (nowsum>=ans) return;//最优性剪枝
if（p>n）
{
ans=min(nowsum,k);
return;
}
dfs(p+1,nowsum+a[p];nowsue+1);
dfs(p+1,nowsum,nowuse);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort（a+1,a+1+n）;
dfs(1,0,0);
printf("%d",ans);
return 0;
}
靶心数独
struct node{
int rank,sum;
}cou[10];
int a[10][10],hang[10][10],lie[10][10],gong[10][10],s[100][4],u,ok,most=-1,have;
bool cmp(node a,node b)
{
return a.sum<b.sum;
}
void dfs(int p, int sorce)
{
if(p==u){
if(sorce>most) most=sorce;
return;
}
for (int i=1;i<=9;i++)
{
if(!hang[s[p][0]][i] && !lie[s[p][1]][i] && !gong[s[p][3]][i])
{
hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=1;
dfs(p+1,sorce+(s[p][2]*i));
hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=0;
}
}
return;
}
int which(int i, int j)
{
if (i<=3){
if (j<=3) return 1;
else if (j<=6) return 2;
else return 3;
}
else if (i<=6)
{
if (j<=3) return 4;
else if (j<=6) return 5;
else return 6;
}
else
{
if(j<=3) return 7;
else if(j<=6) return 8;
else return 9;
}
}
int point(int i,int j)
{
if(i==1||j==1||i==9||j==9) return 6;
else if(i==2||j==2||i==8||j==8) return 7;
else if(i==3||j==3||i==7||j==7) return 8;
else if(i==4||j==4||i==6||j==6) return 9;
else return 10;
}
int main()
{
for (int i=1;i<=9;i++) cou[i].rank=i;
for (int i=1;i<=9;i++)
for (int j=1;j<=9;j++)
{
cin>>a[i][j];
if(a[i][j]>0)
{hang[i][a[i][j]]=lie[j][a[i][j]]=gong[which(i,j)][a[i][j]]=1; have+=a[i][j]*point(i,j);}
else cou[i].sum++;
}
sort(cou+1,cou+10,cmp);//搜索顺序
for (int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
if(a[cou[i].rank ][j]==0)
s[u][0]=cou[i].rank,s[u][1]=j,s[u][2]=point(cou[i].rank,j),s[u++][3]=which(cou[i].rank,j);
}
dfs(0,have);
printf("%d
",most);
return 0;
}
N皇后
int n,b[B],js,c[B],d[B],a[B];
int print()
{
js++;
if(js<=3)
{
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
puts("");
}
}
void dfs(int x)
{
for(int i=1;i<=n;i++)
{
if((!b[i]) && (!c[i+x]) && (!d[x-i+n]))
{
a[x]=i;
b[i]=1;
c[i+x]=1;
d[x-i+n]=1;
if(x==n)
{
print();
}
else
dfs(x+1);
b[i]=0;
c[i+x]=0;
d[x-i+n]=0;
}
}
}
main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n=read();
dfs(1);
cout<<js;
fclose(stdin);
fclose(stdout);
return 0;
}
八数码
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n;
main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n=read();
queue<int>q;
map<int,int>m;
m[n]=0;
q.push(n);
while (!q.empty())
{
int u=q.front(),x=0,y=0;
int n=u;
int c[4][4];
q.pop();
if(u==123804765) break;
for (int i=2;i>=0;i--)
for (int j=2;j>=0;j--)
{
c[i][j]=u%10;
u/=10;
if(!c[i][j]) x=i,y=j;
}
for (int i=0;i<=3;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(x1<0 || x1>2 || y1<0 || y1>2) continue;
swap(c[x1][y1],c[x][y]);
int sum=0;
for (int j=0;j<=2;j++)
for (int k=0;k<=2;k++)
{
sum=sum*10+c[j][k];
}
if(!m.count(sum))
{
m[sum]=m[n]+1;
q.push(sum);
}
swap(c[x1][y1],c[x][y]);
}
}
printf("%lld",m[123804765]);
fclose(stdin);
fclose(stdout);
return 0;
}