A题：签到提直接模拟就行了
//A
#include<iostream>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int t,a,b,c,d,sum=0;
signed main()
{
cin>>t;
while(t--)
{
sum=0;
map<int,int>ma;
cin>>a>>d;
for(int i=1;i<=d;i++)
{
cin>>c;
ma[c]=1;
}
cin>>b;
for(int i=a;i<=b;i++)
{
if(ma[i]!=1)
sum++;
}
cout<<sum<<endl;
}
return 0;
}C题
思路：这个题就是考了一个贪心和双指针，就是每次到最便宜的商店去买，到最贵的商店卖，
代码如下
//C
#include<iostream>
#include<algorithm>
#include<map>
#define IOS ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
#define int long long
using namespace std;
struct asd{
int a, b;
}p[100010];
bool cmp(asd x,asd y)
{
return x.a<y.a;
}
signed main()
{
IOS
int t,a,b,n;
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>p[i].a>>p[i].b;
}
int sum=0;
sort(p,p+n,cmp);
for(int i=0,j=n-1;i<j;)
{
if(p[i].a==p[j].a)break;
else
{
if(p[i].b==p[j].b)
{
sum+=(p[j].a-p[i].a)*p[j].b;
i++,j--;
}
else if(p[i].b>p[j].b)
{
sum+=(p[j].a-p[i].a)*p[j].b;
p[i].b-=p[j].b;
j--;
}
else
{
sum+=(p[j].a-p[i].a)*p[i].b;
p[j].b-=p[i].b;
i++;
}
}
}
cout<<sum<<endl;
}
return 0;
}D题
思路：这个题其实也是贪心，就是按满意度差值排序，按后用前缀和维护一下，最后遍历一遍就出来了
代码如下
//D
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n,m,k,s[10][10],mi=1e9,cnt;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs()
{
mi=min(cnt,mi);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j])
{
for(int l=0;l<4;l++)
{
int a=i+dx[l],b=j+dy[l];
if(s[a][b])
{
int c=a+dx[l],d=b+dy[l];
if(c>0&&d>0&&c<=m&&d<=n&&s[c][d]==0)
{
s[i][j]=0;
s[a][b]=0;
s[c][d]=1;
cnt--;
dfs();
s[i][j]=1;
s[a][b]=1;
s[c][d]=0;
cnt++;
}
}
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
memset(s,0,sizeof s);
while(t--)
{
cin>>m>>n>>k;
mi=k;
cnt=k;
for(int i=1;i<=k;i++)
{
int a,b;
cin>>a>>b;
s[a][b]=1;
}
dfs();
cout<<mi<<'\n';
}
return 0;
} K题
直接暴力DFS就行了
//K
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int s[10][10];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int ans,n,m;
void dfs(int num)
{
ans=min(ans,num);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]==0) continue;
for(int k=0;k<4;k++)
{
int a=i+dx[k],b=j+dy[k];
int c=a+dx[k],d=b+dy[k];
if(s[a][b]==0||s[c][d]==1) continue;
if(c>=1&&c<=n&&d>=1&&d<=m)
{
s[i][j]=0,s[a][b]=0,s[c][d]=1;
num--;
dfs(num);
num++;
s[i][j]=1,s[a][b]=1,s[c][d]=0;
}
}
}
}
}
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int k;
cin>>n>>m>>k;
memset(s,0,sizeof(s));
int x,y;
ans=k;
while(k--)
{
cin>>x>>y;
s[x][y]=1;
}
dfs(ans);
cout<<ans<<'\n';
}
return 0;
}I题
思路：可以用二分答案解决。关键在于 check 函数，它可以这么写：题目中说每次只能向右或向下走，所以每一步的横坐标肯定都大于等于上一步，可以使用一个变量y记录，因此当某个点小于 check 函数传入的答案并且当前点的横坐标要比前一个小时，就说明这个答案不对，否则当前点的横坐标大于等于前一个时，更新 y
代码如下
#include<iostream>
#include<algorithm>
#include<map>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
map<pair<int,int>,int>m;
int t,a,b;
bool asd(int x)
{
int y=0;
for(int i=1;i<=a;i++)
{
for(int j=1;j<=b;j++)
{
if(m[{i,j}]<x)
{
if(y>j)
return 0;
y=max(y,j);
}
}
}
return 1;
}
signed main()
{
IOS
cin>>t;
while(t--)
{
cin>>a>>b;
for(int i=1;i<=a;i++)
{
for(int j=1;j<=b;j++)
{
cin>>m[{i,j}];
}
}
int l=0,r=a*b;
while(l<r)
{
int mid=(l+r+1)/2;
if(asd(mid))
l=mid;
else
r=mid-1;
}
cout<<l<<endl;
}
return 0;
}