The 2023 Guangdong Provincial Collegiate Programming Contest ACDIK
去年打了这场，当时没有补题，现在来直面恐惧。
A. Programming Contest
思路：签到
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int y1; cin>>y1;
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
int y2; cin>>y2;
ll ans = y2-y1+1;
for(int i = 1;i <= n; i++)
{
if(a[i]>=y1&&a[i]<=y2)ans--;
}
cout<<ans<<"\n";
}
return 0;
}
C. Trading
思路：排序+双指针
按照价格从大到小排序，从便宜的买入从贵的卖出，做一个双指针即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
array<int,2>a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i][0]>>a[i][1];
sort(a+1,a+1+n);
int l = 1,r = n;
ll ans = 0;
while(l<r)
{
int mn = min(a[l][1],a[r][1]);
ans += 1ll*(a[r][0]-a[l][0])*mn;
a[l][1] -= mn;
a[r][1] -= mn;
if(a[l][1]==0)l++;
if(a[r][1]==0)r--;
}
cout<<ans<<"\n";
}
return 0;
}
D. New Houses
思路：就是这个题！明明思路就是对滴，当时赛时没写出啊。
考虑\(i\)个人有邻居的最大值，注意可能所有人都没有邻居(2*n-1<=m)。每次让没有邻居的变成有邻居的，增加的是差值。
注意特判。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
array<ll,2>a[N];
ll d[N];
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t;
while(t--)
{
int n,m; cin>>n>>m;
ll ans = 0;
ll hav = 0,no = 0;
for(int i = 1;i <= n; i++)
{
cin>>a[i][0]>>a[i][1];
hav += a[i][0],no += a[i][1];
d[i] = a[i][0]-a[i][1];
}
if(n==1)
{
cout<<a[1][1]<<"\n";
continue;
}
if(n==m)
{
cout<<hav<<"\n";
continue;
}
sort(d+1,d+1+n,cmp);
//k个人有邻居，剩下的没有邻居：需要k+2(n-k) = 2n-k个房子
if(m>=2*n-1)//所有人都没有邻居
ans = no;
ll now = no;
now += d[1];
for(int i = 2;i <= n; i++)//i个人有邻居
{
now += d[i];
if(2*n-i<=m)ans = max(ans,now);
}
cout<<ans<<"\n";
}
return 0;
}
I. Path Planning
思路：考虑，当前的mex值由什么决定？是由当前没出现过的最小的决定。如果当前的最小值是x，那么<x的值一定都被取到了。我们可以考虑二分答案。但是问题又来了，怎么去check答案？由于我们只能往下和往右走，我们走出来的路径一定是呈现阶梯状的。
比如上图这样一个行驶路线，我们观察每一行，上一行的有边界一定<=这一行的左边界。那么依据这个做check即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
// #define ll int
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
// vector<vector<ll>> a(m+10, vector<ll>(n+10));
for(int i = 1; i <= n; i++)
for(int j = 1;j <= m; j++)
cin>>a[i*m+j];
auto judge = [&](ll x)
{
//<x都要取到
ll l = 0,r = 0;
for(int i = 1;i <= n; i++)
{
bool st = false;
ll tl = -1,tr = -1;
for(int j = 1;j <= m; j++)
{
if(a[i*m+j]<x&&!st)
tl = j,st = true;
if(a[i*m+j]<x&&st)
tr = j;
}
if(tl==-1)continue;
if(tl>=r)
l = tl,r = tr;
else return false;
}
return true;
};
ll l = 0,r = n*m;
while(l<=r)
{
ll mid = (l+r)>>1;
if(judge(mid))l = mid+1;
else r = mid-1;
}
cout<<l-1<<"\n";
}
return 0;
}
K. Peg Solitaire
思路：数据范围很小，直接暴搜。注意初始化！
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 10;
int a[N][N];
// 上 下 左 右
int dir[4][2] = {{-2,0},{2,0},{0,-2},{0,2}};
int n,m,k;
bool vaild(int op ,int x,int y)
{
if(op==0){//上
if(x-2>=1&&a[x][y]&&a[x-1][y]&&!a[x-2][y])
return true;
else return false;
}else if(op==1){
if(x+2<=n&&a[x][y]&&a[x+1][y]&&!a[x+2][y])
return true;
else return false;
}else if(op==2){
if(y-2>=1&&a[x][y]&&a[x][y-1]&&!a[x][y-2])
return true;
else return false;
}else{
if(y+2<=m&&a[x][y]&&a[x][y+1]&&!a[x][y+2])
return true;
else return false;
}
}
int ans;
void dfs(int now)
{
ans = min(ans,now);
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)if(a[i][j]==1){
for(int d = 0;d < 4; d++)if(vaild(d,i,j)){
int x = i,y = j,op = d;
if(op==0){//上
a[x][y] = 0,a[x-1][y] = 0,a[x-2][y] = 1;
dfs(now-1);
a[x][y] = 1,a[x-1][y] = 1,a[x-2][y] = 0;
}else if(op==1){
a[x][y] = 0,a[x+1][y] = 0,a[x+2][y] = 1;
dfs(now-1);
a[x][y] = 1,a[x+1][y] = 1,a[x+2][y] = 0;
}else if(op==2){
a[x][y] = 0,a[x][y-1] = 0,a[x][y-2] = 1;
dfs(now-1);
a[x][y] = 1,a[x][y-1] = 1,a[x][y-2] = 0;
}else{
a[x][y] = 0,a[x][y+1] = 0,a[x][y+2] = 1;
dfs(now-1);
a[x][y] = 1,a[x][y+1] = 1,a[x][y+2] = 0;
}
}
}
}
void solve()
{
cin>>n>>m>>k;
memset(a,0,sizeof(a));
for(int i = 1;i <= k; i++)
{
int x,y; cin>>x>>y;
a[x][y] = 1;
}
ans = k; dfs(k);
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
solve();
}
return 0;
}