2022-6-26

　　昨晚熬夜学会了git的基本使用方法。其实git非常简单，有人手把手教或者有好的教程的话三小时就可以完全学会。但是如果使用的教程不正确的话就会像我一样花去整整一周的时间还学不会，有几天晚上花大把大把的时间逐一搜索不知道哪里有问题的操作，解决了旧问题400又出现新问题403，如果不是问了老蒋我恐怕会接着搜索怎么解决网络问题。。。从此打磨掉对git的学习信心。不止git,arduino和html也是一样的，当时老师讲课不清不楚，我什么也听不懂就开始做作业，作业过程中遇到问题又根本没人解答。。不失去信心才怪呢。其实都是很简单的事，只不过没找对老师罢了。

　　总之一句话，选择教材比学习更重要。

　　今天计划在早上把网宿杯第二轮初赛中我有点思路但又没解决的题目写出来。以后将每一道有深意的题目归类至不同的标签然后记录下来，每隔一段时间就回来看看。

　　对于模板，以后把代码和题目全部留在博客园，我自己就不存模板了，毕竟每一次打模板都可能会出现不同的错误，只有多次打模板才能从多个角度发现问题，对模板更加熟悉。

　　也许你以为要将每条蛇的长度更新更新再更新，一次又一次地遍历来看看它最多可以吃到多大，知道不能再吃时通过判断有没有其他蛇来决定它能不能胜出。这个程序可以用while循环实现，while的条件是还能吃，但是这个程序我想着就头大，虽然有这个思路，但在赛场上我并没有写出来。

　　看看本文的标签，有序变无序：我们将蛇以大小为依据排序，所有蛇中一定以某一条为界限，它以上的都可以胜出，它和它以下的都不行（因为吃长蛇的路上只要有一处过不去，如果比A更长的B都不能胜利，那A就一定不能成为赢家，毕竟在吃吃吃以后A和B会变成同样规模的蛇）。这条特殊的边界蛇的特点就是：吃掉所有比它小的蛇，它还是吃不了比它更大的那条，这样的蛇也许不止一条，我们要的蛇所有满足这个条件的蛇中最长的那条。

　　注意ai的取值范围，10^9和int是一个数量级，但做sum运算的话就开个long long。

code:

 1  1 #include 
 2  2 using namespace std;
 3  3 int a[200005];
 4  4 long long sum[200005];
 5  5 int main(){
 6  6     int n;
 7  7     cin>>n;
 8  8     for(int i=1;i<=n;i++){
 9  9         cin>>a[i];
10 10     }
11 11     sort(a+1,a+n+1);
12 12     int index=0;
13 13     for(int i=1;i<=n;i++){
14 14         sum[i]=sum[i-1]+a[i];
15 15         if(i2*sum[i]1]){
16 16             index=i;
17 17         }
18 18     }
19 19     cout<index;
20 20     return 0;
21 21 }

洛谷1605题

　　要注意的点：

　　在地图中，有障碍的地方和已经走过的地方性质是一样的，不必为了障碍专门开一个数组，浪费空间。

　　记得初始化：初始点相当于已经走过了，不要再走。（巨坑，时隔半年才被我发现）

code:

 1 #include
 2  2 using namespace std;
 3  3 int b[6][6];//整张地图 ,0表示可以去，1表示不能去 
 4  4 int n,m,t,sx,sy,fx,fy,total;//s是start，f是final,total是结果 
 5  5 int hx[]={0,0,1,-1};
 6  6 int hy[]={1,-1,0,0};
 7  7 void walk(int x,int y){
 8  8     if(x==fx&&y==fy){
 9  9         total++;
10 10         return;
11 11     }
12 12     else{
13 13         int k;
14 14         for(k=0;k<4;k++){
15 15             int nx=x+hx[k];
16 16             int ny=y+hy[k];
17 17             if(b[nx][ny]==0&&nx>=1&&ny>=1&&nx<=m&&ny<=n){
18 18                 b[nx][ny]=1;
19 19                 walk(nx,ny);
20 20                 b[nx][ny]=0;
21 21             }
22 22         }
23 23     }
24 24 }
25 25 int main(){
26 26     cin>>n>>m>>t>>sx>>sy>>fx>>fy;
27 27     b[sx][sy]=1;
28 28     for(int i=1;i<=t;i++){
29 29             int tempx;
30 30             int tempy;
31 31             cin>>tempx>>tempy;
32 32             b[tempx][tempy]=1;
33 33     }
34 34     walk(sx,sy);
35 35     cout<<total;
36 36     return 0; 
37 37 }

 洛谷1644题：

　　非常简单的DFS，连回溯都用不上：因为小马只会往右跳，根本跳不回左边去。所以连图都不用建，毕竟建图是为了储存已经走过的信息，这里不可能有重复走的可能（有递进条件只会往右跳决定），所以不建图嘿嘿。

code：

 1 #include
 2 using namespace std;
 3 int b[20][20];//整张地图 ,0表示可以去，1表示不能去 
 4 int fx,fy,total;//f是final,total是结果 
 5 int hx[]={2,1,2,1};
 6 int hy[]={1,2,-1,-2};
 7 void walk(int x,int y){
 8     if(x==fx&&y==fy){
 9         total++;
10         return;
11     }
12     else{
13         for(int k=0;k<4;k++){
14             int nx=x+hx[k];
15             int ny=y+hy[k];
16             if(ny>=0&&nx<=fx&&ny<=fy){
17                 walk(nx,ny);
18             }
19         }
20     }
21 }
22 int main(){
23     cin>>fy>>fx;
24     walk(0,0);
25     cout<<total;
26     return 0; 
27 }

　　洛谷1219：

　　经典的八皇后问题啊，关键之处在于用下标之和，下标之差表示双对角线，这里的对角线和跳马，迷宫之中的地图是一样的，只不过这里的”地图“不止一个，而是有行，左右对角线三处。此题中还有一个关键点在于表示出前三个回答，我们在走迷宫类问题中也会遇到这种需求：写出走迷宫的路径，怎么解决呢？当然是在搜索过程中把每一步储存在一个路径数组stepx,stepy中，一旦可以到达终点那就输出这两个step数组中记录的路径，不用专门去清空这两个数组，因为每次搜索新的路径都会覆盖原有的路径，无论新路径是对的还是错的，最终能不能走到终点，都会覆盖，但只有成功的路径才会被输出。

 code:

 1 #include
 2 using namespace std;
 3 int n,i,res;
 4 int a[50],b[50],c[50],d[50];
 5 void print(){
 6     if(res<3){
 7         for(i=1;i<=n;i++){
 8             cout<" ";
 9         }
10         cout<<endl;
11     }
12     res++;
13 }
14 void search(int step){
15     if(step>n){
16         print();
17         return;
18     }
19     else{
20         for(int j=1;j<=n;j++){
21             if(b[j]==0&&c[step+j]==0&&d[step-j+n]==0){
22                 b[j]=1,c[step+j]=1,d[step-j+n]=1,a[step]=j;
23                 search(step+1);
24                 b[j]=0,c[step+j]=0,d[step-j+n]=0;
25             }
26         }
27     }
28 }
29 int main(){
30     cin>>n;
31     search(1);
32     cout<<res;
33     return 0; 
34 }

 洛谷1596：

看看哪个点是有水的，顺着这个点延伸出去，把所有和它是一个坑的都变成干旱，最后数一数整个图中有几个点是有水的，那就有几个水坑。我愿称之为缩点法——缩片成点。

 1 #include
 2 using namespace std;
 3 char a[105][105];
 4 int res,m,n;
 5 void dfs(int x,int y){
 6     a[x][y]='.';
 7     for(int i=-1;i<=1;i++){
 8         for(int j=-1;j<=1;j++){
 9             int nx=x+i;
10             int ny=y+j;
11             if(nx>=0&&nx=0&&ny'W'){
12                 dfs(nx,ny);
13             }
14         }
15     }
16 }
17 int main(){
18     cin>>n>>m;
19     int i,j;
20     for(i=0;i){
21         scanf("%s",a[i]);
22     }
23     for(i=0;i){
24         for(j=0;j){
25             if(a[i][j]=='W'){
26                 dfs(i,j);
27                 res++;
28             }
29         }
30     }
31     cout<<res;
32     return 0; 
33 }

注意：最初我是想先搜索。再数水坑的个数的，但是你难道准备先开个for循环，找到第一个水坑，然后for继续，然后找到第二个水坑时停下来吗。这纯属扯淡，因为有几个坑是数据决定的，你根本不知道，所以要让两个行为同时进行。在for循环的时候遇到一个坑就res++，遇到一个就++，这样全遍历完了，坑也数出来了。还有一个点：注意横纵坐标，这是很值得注意的，比如跳马那一题，数据先给列数再给行数，就是为了误导你，让你把行当列用，把列当行用，让你过不了。

注意，BFS如果要回溯的话时间复杂度是指数级，所以数据规模通常不大。BFS通常用于解决方案数（1219八皇后，1644跳马，马拉车），数个数（1596水坑数）类问题。

DFS:主要解决最优解类问题。

洛谷1379八数码难题

　　这题的思路是简单的BFS，没什么好说，问题在于如何表示状态，用图结构的话，我不会表示图和步数的关系，但如果用一个字符串（哈希）来储存该结构，我就可以用map和int作为键和值来储存每种状态的步数（从初始状态走到现在走了多少步）。这里注意map的用法。

　　注意用字符串表示图案时，用字符串的find函数找出0的位置，再用/和%找到横纵坐标。

　　在写代码过程中有个错误：BFS是用不到函数递归的，整个过程中只调用了一次函数，而DFS则用到递归，要反复调用函数。

　　自己的一个小优化：设置一个flag变量来记录有没有找到最优解，如果找到的话就直接return,不用把每种方案都搜索出来，节省了许多时间。

code:

 1 #include
 2 using namespace std;
 3 map<string,int> d;//从初始状态到目前状态需要走几步 
 4 int step,flag;
 5 int hx[]={0,0,1,-1};
 6 int hy[]={1,-1,0,0};
 7 string res="123804765",begin;
 8 queue <string>q;
 9 void bfs(int step){
10     while(q.size()&&flag==0){
11         string t=q.front();
12         step=d[t];
13         if(t==res){
14             flag=1;
15             cout<<d[t];
16             return;
17         }
18         q.pop();
19         int k=t.find('0');
20         int a=k/3,b=k%3;
21         for(int i=0;i<4&&flag==0;i++){
22             int dx=a+hx[i],dy=b+hy[i];
23             if(dx>=0&&dx<3&&dy>=0&&dy<3){
24                 swap(t[k],t[3*dx+dy]);
25                 if(d[t]==0)d[t]=step+1,q.push(t);
26                 swap(t[k],t[3*dx+dy]);
27             }
28         }
29     } 
30 }
31 int main(){
32     string begin;
33     cin>>begin;
34     q.push(begin);
35     bfs(0);
36     return 0; 
37 }

 　　晚上想学点初等数论，和线性代数一样，概念能听懂，做题就不会，呸！

　　了解了下整除，带余除法和辗转相除。