C
双指针，排序
买便宜的，用最贵的卖出
#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,m;
int re[2]={1,4};
int bl[4]={2,3,5,6};
int f;
struct node
{int x,y;
}a[N];
bool cmp(node W,node Q)
{return W.x<Q.x;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){
// cin>>a[i].x>>a[i].y;scanf("%d%d",&a[i].x,&a[i].y);}sort(a+1,a+n+1,cmp);int ans=0;int l=1,r=n;while(l<r){int k=min(a[l].y,a[r].y);ans+=k*(a[r].x-a[l].x);a[r].y-=k;a[l].y-=k;if(a[r].y==0) r--;if(a[l].y==0) l++;}cout<<ans<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} K
爆搜+回溯
#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,m,k;
int a[30][30];
int f[][2]={{0,2},{0,-2},{2,0},{-2,0}};
int ff[][2]={{0,1},{0,-1},{1,0},{-1,0}};
int minn=6;
void dfs(int c)
{minn=min(minn,c);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]){for(int k=0;k<4;k++){int dx=i+f[k][0],dy=j+f[k][1];int tx=i+ff[k][0],ty=j+ff[k][1];if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[tx][ty]==1&&a[dx][dy]==0){a[i][j]=0;a[dx][dy]=1;a[tx][ty]=0;dfs(c-1);a[i][j]=1;a[dx][dy]=0;a[tx][ty]=1; }}}}}
}
void solve()
{memset(a,0,sizeof a);minn=6;cin>>n>>m>>k;for(int i=1;i<=k;i++) {int x,y;cin>>x>>y;a[x][y]=1;}dfs(k);cout<<minn<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} 注意python中global的运用
f = [[0, 2], [0, -2], [2, 0], [-2, 0]]
ff = [[0, 1], [0, -1], [1, 0], [-1, 0]]def dfs(c):global minn # 声明使用全局变量minn = min(minn, c)for i in range(1, n + 1):for j in range(1, m + 1):if a[i][j] == 1:for k in range(4):dx, dy = i + f[k][0], j + f[k][1]tx, ty = i + ff[k][0], j + ff[k][1]if dx >= 1 and dx <= n and dy >= 1 and dy <= m and a[tx][ty] == 1 and a[dx][dy] == 0:a[i][j] = 0a[dx][dy] = 1a[tx][ty] = 0dfs(c - 1)a[i][j] = 1a[dx][dy] = 0a[tx][ty] = 1T = int(input())while T:T -= 1n, m, k = map(int, input().split())a = [[0 for _ in range(m + 1)] for _ in range(n + 1)]global minnminn = 6 # 重置 min 值for _ in range(k):x, y = map(int, input().split())a[x][y] = 1dfs(k)print(minn)
D
枚举所有邻居的数量和不是邻居的数量
假设有k个邻居，那么剩余的n-k个邻居需要2*（n-k），所以房子的个数需要大于等于2*（n-k）+k
没有只有1个邻居的可能，还有一种可能就是所有人都没有邻居，那么需要的房子数量是2*n-1
所有可能取最大值
#include<bits/stdc++.h>using namespace std;#define int long long
const int N = 5e5 + 10;
int n,m,k;
struct node
{int x,y;
}a[N];
int sum[N];
bool cmp(node W,node E)
{return W.x-W.y>E.x-E.y;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].y;int ans=a[1].x;int res=0;for(int i=2;i<=n;i++){ans+=a[i].x;if(2*n-i<=m){res=max(res,ans+sum[n]-sum[i]);}}if(2*n-1<=m){res=max(res,sum[n]);}cout<<res<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} I
二分答案
对于不需要在图上操作的，尤其是，n*m数组太大的情况，可以使用i*m+j来存储每个点的值，
check（x）
只需要看整个图中比x小的数的坐标，只要这些小的数构成的路径满足题意（只能往右往下走）
（怎么样判断是否满足，一行一行遍历，并记录上一个点的列坐标，如果当前点的纵坐标小于上一个点的列坐标，则不满足题意，因为，当小于上一个点的列坐标，从上一个点走向当前点，上一个点只能往左走，才能走到当前点）
对于路径上其他大于x的点，不管怎么排列，x一定可以满足是这条路径最大的mex（x）
#include<bits/stdc++.h>using namespace std;#define int long long
const int N = 2e6 + 10;
int n,m,k;
int a[N];
int check(int x)
{int last=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i*m+j]<x){if(j<last) return 0;last=j;}}}return 1;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x;cin>>x;a[i*m+j]=x;} }int l=0,r=n*m;while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;elser=mid-1;} cout<<r<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
}