目录

T1 数的划分思路：答案 T2 排座椅思路答案 T3 逆序对思路 T4 棋盘思路答案

T1 数的划分

点这里转到题目网页

思路：

本蒟蒻一直以为很简单且已经做过，结果做了才知道自己根本不会……， 看了题解才知道这是一道搜索题 大概思路就是深搜，从第一位数开始一直往下搜下一位数，每搜到一个满足条件的第K位数就结果加一……

答案

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int a[N], n, m, ans; void dfs(int k){ if(n == 0) return ;//输入0还用得着划分吗？ if(k == m) { if(n >= a[k - 1]) ans ++;//剩余的n要是比前一位大，那么这个队列就是合法的 return ; } for(int i = a[k - 1]; i <= n / (m - k + 1); i ++){//必须保证下一位数大于等于它的前一位数，这样才可以保证数列不重复； a[k] = i; n -= i; dfs(k + 1); n += i;//还原现场…… } } int main(){ cin >> n >> m; a[0] = 1; dfs(1); cout << ans << endl; return 0; }

T2 排座椅

点这里转到题目网页

思路

先记录下在每条通到右边划分的最大收益为多少（划分x1, x2时，我们会选择在坐标较小的一个右边划分，这样可以使最后隔开交头接耳的同学的数量最多）

答案

#include<bits/stdc++.h> using namespace std; const int N = 1010; int m, n, k, l, d; struct node { int pos;//开这个 位置 参数 是为了最后的输出时，按照序列数从小到大输出用的 int num; }r[N], c[N]; bool cmp1(node a, node b){ return a.num > b.num; } bool cmp2(node a, node b){ return a.pos < b.pos; } int main(){ cin >> m >> n >> k >> l >> d; int x1, x2, y1, y2; while(d --){ cin >> x1 >> y1 >> x2 >> y2;//会交头接耳的两位同学的坐标 int x = min(x1, x2);//这里处理的时候，分别从横、纵坐标较小的一个划分，尽量将划分的收益集中在坐标较小的地方 int y = min(y1, y2); if(x1 == x2){//如果两位同学的x轴相同，那么只好从y轴方向将其划分了 c[y].pos = y;//从y划分的时候，y的位置就在y上……有点憨 c[y].num ++;//从y划分后，交头接耳的同学又少了一对（收益+1） } else { r[x].pos = x; r[x].num ++; } } sort(r + 1, r + m, cmp1); sort(c + 1, c + n, cmp1); sort(r + 1, r + k + 1, cmp2); sort(c + 1, c + l + 1, cmp2); for(int i = 1; i <= k; i ++){ cout << r[i].pos; if(i < k) cout << " "; } cout << endl; for(int i = 1; i <= l; i ++){ cout << c[i].pos; if(i < l) cout << ' '; } return 0; }

T3 逆序对

点这里转到题目网页

思路

归并排序模板题，本蒟蒻又又又白学了，考试时只会暴力算法……

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int a[N], n, m, b[N]; long long ans; void merge(int l, int mid, int r){ int i, j, k; i = l, j = mid + 1, k = l; while(i <= mid && j <= r) if(a[i] > a[j]){ b[k ++] = a[j ++]; ans += mid - i + 1; } else b[k ++] = a[i ++]; // 这里这样做，是把前半部分和后半部分分别看做是两个队列，每次将两个指针i, j其中较小的一个出队，储存在数组b当中。 // 而每次让j指针上的数入队，就说明当前j位置的数比前半部分的队列余剩的所有数都要小，也就是找到了mid - i + 1个逆序对 // 所以不要ans += (j - i);这里的j具体意义是整一个数组里面第j位，i是整个数组里面第i位，他们中间有很多已经出列的数仍然涵盖其中，所以(j - i)并非i，j之间的逆序对数！ /* 例子：1 4 | 2 3 ， 1 2(+1) 3(+1) 4;因为当2和3要进入b的时候，会越过4,当2越过4之后,3就在4的后面,所以两个都是+1。 而“越过”就代表相邻的这两个数顺序不对，每越过一次就有一对……所以[i, mid]之间有mid - i + 1对。 */ while(i <= mid) b[k ++] = a[i ++]; while(j <= r) b[k ++] = a[j ++]; for(int i = l; i <= r; i ++) a[i] = b[i]; } void mergesort(int l, int r){ if(l >= r) return ; int mid = (l + r) / 2; mergesort(l, mid); mergesort(mid + 1, r); merge(l, mid, r); } int main(){ cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; mergesort(1, n); cout << ans << endl; return 0; }

T4 棋盘

点这里……

思路

按条件深搜……（言简意赅好吧？）

答案

本蒟蒻改正过后的：

#include<bits/stdc++.h> using namespace std; const int N = 105; int M[N][N]; int f[N][N]; int X[4] = {-1, 1, 0, 0}, Y[4] = {0, 0, -1, 1}; int m, n; int x, y, c; int flag = 0; bool pan(int xx, int yy){//判断位置是否合法 return xx > 0 && xx <= m && yy > 0 && yy <= m; } void dfs(int x, int y, int z, int s){ //当前位置x, y, 魔法使用了吗？,到这一步的花费； if(!pan(x, y)) return ;//不合法的返回 if(s >= f[x][y]) return ;//花费明显不合理的返回 f[x][y] = s;//更新为更小的花费 if(x == m && y == m){ flag = 1; return; } //st[x][y] = 1;//代表来过了 。注： 不必要了，只需要加上第22行 这个条件就不会出现同同颜色循环的情况了！ for(int i = 0; i < 4; i ++){ int xx = x + X[i], yy = y + Y[i]; if(M[xx][yy] == -1){//再判颜色:无色 且魔法没有被用掉 if(!z){ M[xx][yy] = M[x][y]; dfs(xx, yy, 1, s + 2); M[xx][yy] = -1;//颜色要消失 } } else{ if (M[xx][yy] == M[x][y]){//同色 直接走 dfs(xx, yy, 0, s); } else {//不同色 dfs(xx, yy, 0, s + 1); } } } return ; } int main(){ cin >> m >> n; memset(f, 0x3f, sizeof f); memset(M, -1, sizeof M); for(int i = 1; i <= n; i ++){ cin >> x >> y >> c; M[x][y] = c; } dfs(1, 1, 0, 0); if(flag) cout << f[m][m]; else cout << "-1"; return 0; } /* 走到下一个点的要求： 1 本轮未走过！ 2 无色的的话还有魔法可以使用！ 3 */

本蒟蒻参考的：

#include<bits/stdc++.h> using namespace std; int m,n; int clor[105][105],money[105][105]; //clor是记录颜色的数组 ，0无色，1红色，2黄色 //money是记录走到(x,y)的最少花费 int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0}; int x,y,c; bool flag=0; //判断有无解 bool pan(int x,int y) { return x>=1&&x<=m&&y>=1&&y<=m; } void dfs(int x,int y,int step,bool use) //走到了(x,y),花费为step，use表示是否使用了魔法 { if(!pan(x,y)) return; //不合法直接退出 if(step>=money[x][y]) return ; //最小值判断 //如果走到(x,y)的花费比之前搜到的结果还大，那么直接退出 money[x][y]=step; //更新成更小花费 if(x==m&&y==m) { flag=1; return; }//有解 for(int i=0;i<=3;i++) //四连通深搜 { int xx=x+dx[i],yy=y+dy[i]; if(pan(xx,yy)) //新节点合法 { if(clor[xx][yy]!=0) //新节点有颜色 { if(clor[xx][yy]==clor[x][y]) //新节点与原来节点同色 dfs(xx,yy,step,0); else //新节点与原来节点不同色 dfs(xx,yy,step+1,0); } else if(!use) //新节点无色，没有使用过魔法，可以使用魔法 { clor[xx][yy]=clor[x][y]; //暂时变色 dfs(xx,yy,step+2,1); clor[xx][yy]=0; //回溯 } } } } int main() { scanf("%d%d",&m,&n); memset(money,0x3f,sizeof(money)); //初始化极大值 for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&c); clor[x][y]=c+1; } dfs(1,1,0,0); if(flag==1) { printf("%d\n",money[m][m]); } else { printf("-1\n"); } return 0; }