咸鱼烤前的垂死挣扎

敲黑板当当当~

从今晚（28）起，日更 “咸鱼烤前的垂死挣扎”。

日更的内容是对当天学习的模板做一个小小的总结

日更的的口号是——

　　　　　　　　　　不是还没到最后一刻嘛~

　　　　　小哥哥再坚持一下嘛~

搜索

P1379 八数码难题

题面：

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

思路：

隐形图要做转化处理（压缩，解压），然后就是跑上一圈BFS啦~

注意特判(＾Ｕ＾)ノ~ＹＯ

（听说还可以用康托展开处理，待我学会去去就来~）

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct node{
 8     string s;
 9     int step;
10 }a,e;
11 int sum,ans,tot;
12 int dx[4]={-1,0,0,1},dy[4]={0,1,-1,0};
13 char b[3][3];
14 string n,m;
15 bool flag[88888888];
16 queue <node > q;
17 
18 string change(){
19     string c;
20     sum=0;
21     for(int i=0;i<3;i++)
22         for(int j=0;j<3;j++){
23             c+=b[i][j];
24             if(!(i==2&&j==2))sum=sum*10+b[i][j]-'0';    //注意求的是前 8位的和 
25         }
26     return c;
27 }
28 
29 void bfs(){
30     while(!q.empty()){
31         int tot=0,x,y;
32         a=q.front();
33         q.pop();
34         for(int i=0;i<3;i++)        // 解压 
35             for(int j=0;j<3;j++){
36                 if(a.s[tot]=='0') x=i,y=j;
37                 b[i][j]=a.s[tot++];
38             }
39         for(int i=0;i<4;i++){        // 四个方向扫一遍 
40             if(x+dx[i]>-1&&x+dx[i]<3&&y+dy[i]>-1&&y+dy[i]<3){
41                 swap(b[x][y],b[x+dx[i]][y+dy[i]]);
42                 e.s=change();    // 压缩->字符串 
43                 if(e.s=="123804765"){
44                     printf("%d",a.step+1);
45                     exit(0);
46                 }
47                 if(!flag[sum]){
48                     flag[sum]=1;
49                     e.step=a.step+1;
50                     q.push(e);
51                     
52                 }
53                 swap(b[x][y],b[x+dx[i]][y+dy[i]]);    //回溯 
54             }
55         }
56     }
57 }
58     
59 int main()
60 {
61     cin>>n;
62     m="123804765";
63     a.s=n,a.step=0;
64     q.push(a);
65     for(int i=0;i<8;i++) sum=sum*10+n[i]-'0';
66     for(int i=0;i<8;i++) ans=ans*10+m[i]-'0';
67     flag[sum]=1;
68     
69     if(sum==ans) printf("0");    //注意特判 
70     else bfs();
71     
72     return 0;
73 }

继续练我可怜的广搜！

P2296 寻找道路

题面：

在有向图

1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件

注意：图

从终点反向BFS，求出所有可以到达终点的点　　available[]

　　2. 对每个点判断是否自己指向的节点都可以到达终点　　ans[]

　　3. 从起点正向BFS，求最短路

总结：

　　未知的起点，确定的终点。反向跑图。

 1 #include<cstdio>
 2 #include<queue>
 3 #include<vector>
 4 #define N 10010
 5 using namespace std;
 6 int read(){
 7     int x=0,f=1; char c=getchar();
 8     while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
 9     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
10     return f*x;
11 }
12 int n,m,s,t;
13 int ava[N],ans[N],dis[N];//available
14 queue < int > q;
15 vector < int > cd[N];
16 vector < int > rd[N];
17 int main()
18 {
19     n=read(),m=read();
20     for(int x,y,i=1;i<=m;i++){
21         x=read(),y=read();
22         rd[y].push_back(x);
23         cd[x].push_back(y);
24     }
25     s=read(),t=read();
26     ava[t]=1,q.push(t);
27     while(!q.empty()){
28         int u=q.front();
29         q.pop();
30         for(int i=0;i<rd[u].size();i++){
31             int v=rd[u][i];
32             if(!ava[v]){
33                 ava[v]=1;
34                 q.push(v);
35             }
36         }
37     }
38     if(!ava[s]){ 
39         printf("-1"); return 0;
40     }
41     for(int i=1;i<=n;i++){
42         if(ava[i]){
43             int k=0;
44             for(int j=0;j<cd[i].size();j++){
45                 if(!ava[cd[i][j]]){
46                     k=1;
47                     break;
48                 }
49             }
50             if(k==0) ans[i]=1;
51         }
52     }
53     dis[s]=1,q.push(s);
54     while(!q.empty()){
55         int u=q.front();
56         q.pop();
57         if(u==t){
58             printf("%d",dis[t]-1);
59             return 0;
60         }
61         for(int i=0;i<cd[u].size();i++){
62             int v=cd[u][i];
63             if(ans[v]&&!dis[v]){
64                 dis[v]=dis[u]+1;
65                 q.push(v);
66             }
67         }
68     }
69     return 0;
70 }

区间DP

使用特征：每次可以消去一个区间，之后左右两边会合并起来。具有最优子问题结构且状态满足无后效性。

解法：先枚举区间长度 / 操作次数，再枚举左端点 / 起始位置，后枚举区间断点 / 结束位置进行转移。

（一） czy把妹　　　（见模拟赛篇）

（二）能量项链

题面：

在

需要时，

$特别注意：$

$并未要求按顺序合并，事实说明按顺时针方向摆放珠子，合并时可以选择任意相邻的两个珠子合并，只要总能量最大即可。$

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define re register
 4 #define in inline
 5 #define N 2000
 6 using namespace std;
 7 int read(){
 8     int x=0,f=1; char c=getchar();
 9     while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
10     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
11     return x*f;
12 }
13 int n,ans;
14 int head[N],tail[N],f[N][N];
15 int main()
16 {
17     n=read();
18     for(re int i=1;i<=n;i++) head[i]=head[n+i]=read();
19     for(re int i=1;i<=n;i++) tail[i]=tail[n+i]=head[i+1];
20     tail[n]=tail[2*n]=head[1];
21     
22     for(int t=1;t<=n-1;t++)　　//合并次数
23         for(int i=1;i<=2*n-t;i++){　　//起始位置
24             int j=i+t;　　//计算结束位置
25             for(int k=i;k<=j-1;k++)　　//决策
26                 f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
27         }
28     for(int i=1;i<=n;i++)
29         ans=max(ans,f[i][i+n-1]);
30     printf("%d",ans);
31     return 0;
32 }

总结一些数论小板子：

快速幂

1 ll ksm(ll a,ll b,int mod){
2     ll ret=1;
3     while(b){
4         if(b&1) ret=ret*a%mod;　　// b&1 表示 b在二进制下最后一位是1
5         a=a*a%mod;
6         b>>=1;
7     }
8     return ret;
9 }

裴蜀定理

问题：给出n个数(A1...An) 现求一组整数序列(X1...Xn) 使得 S=A1X1+...AnXn>0, 且S的值最小

解法： $a x + b y = c, x \in N$

 1 #include<cstdio>
 2 using namespace std;
 3 int ans;
 4 int gcd(int a,int b){
 5     return !b ?a : gcd(b,a%b);
 6 }
 7 int main()
 8 {
 9     int n,m;
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++){
12         scanf("%d",&m);
13         m=(m>0)?m:-m;       //数据中有负数，要将其变为正数再求gcd
14         ans=gcd(ans,m);
15     }
16     printf("%d
", ans);
17     return 0;
18 }

无线通讯网【最小生成树】

题意：

他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

思路：

做本题首先应该知道一共有p个点就是树有p-1条边，有s个卫星电话就是不用连接最大的s-1条边。

求树中前（p-s）条边里的最大边即可。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define re register
 5 #define in inline
 6 #define ll long long
 7 #define N 250010
 8 using namespace std;
 9 in int read(){
10     int x=0,f=1; char c=getchar();
11     while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
13     return x*f;
14 }
15 
16 struct node{
17     int u,v;
18     double w;
19 }edge[N];
20 int s,p,cnt,tot,fa[N],px[N],py[N];
21 
22 int getfather(int x){
23     if(x==fa[x]) return x;
24     return fa[x]=getfather(fa[x]);
25 }
26 
27 in bool cmp(node x,node y){
28     return x.w<y.w;
29 }
30 
31 double solve(int i,int j){
32     double dis=(double)sqrt((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j]));
33     return dis;
34 }
35 
36 void kruskal(){
37     sort(edge+1,edge+1+cnt,cmp);
38     for(re int i=1;i<=cnt;i++){
39         int x=getfather(edge[i].u);
40         int y=getfather(edge[i].v);
41         if(x==y) continue;
42         fa[y]=x;
43         if(++tot==p-s){
44             printf("%.2lf",edge[i].w);
45             exit(0);
46         }
47     }
48 }
49 
50 int main()
51 {
52     s=read(),p=read();
53     for(re int i=1;i<=p;i++) px[i]=read(),py[i]=read();
54     for(re int i=1;i<=p;i++) fa[i]=i;
55     for(re int i=1;i<p;i++)
56         for(re int j=i+1;j<=p;j++){
57             double dis=solve(i,j);
58             cnt++;
59             edge[cnt].u=i,edge[cnt].v=j,edge[cnt].w=dis;
60         }
61     kruskal();
62     return 0;
63 }