题目大意
给你n,m,p,q
让你构造一个长度为n的数组，数组总和为m,这个数组中任意一段长度为p子区间的和为q,问你是否能够构造出这样的数组
思路
由于数组可以存在负数，考虑n能否被p整除，如果能被整除那么必须是m必须为 ( n ∗ q ) / p (n*q)/p (n∗q)/p
否则如果有余数我们可以让剩下的数放任意值来满足答案
//Author: zengyz
//2025-06-27 15:31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n,m,p,q;
cin>>n>>m>>p>>q;
if(p==1)
{
if(n*q!=m) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return;
}
int cnt=n/p;
int count=n%p;
int res=cnt*q;
if(res!=m&&count==0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _T = 1;
cin >> _T;
while(_T --)
{
solve();
}
return 0;
}
B. The Picky Cat
题目大意
给你一个数组长度为n，你可以将其中任意一个元素变为 a i a_i ai变为 − a i -a_i −ai
问是否能让第一个元素成为这个数组的中位数
思路
只需要关心绝对值即可，考虑第一个元素的正负两种情况，如果存在比第一个元素的绝对值大的元素超过n的一半，或者比第一个元素的绝对值的负数小的超过一半就算对
// Author: zengyz
// 2025-06-27 15:38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
int idx = abs(a[0]);
int cnt1=0,cnt2=0;
for(int i=1;i<n;i++)
{
if(abs(a[i])>idx)cnt1++;
if(-abs(a[i])<-idx)cnt2++;
}
if(n%2)
{
if(cnt1>=n/2||cnt2>=n/2)
{
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
else
{
if(cnt1>=n/2-1||cnt2>=n/2-1)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _T = 1;
cin >> _T;
while (_T--)
{
solve();
}
return 0;
}
C. Mex in the Grid
题目大意
给你一个n,求构造从 0 ～ n 2 − 1 0～n^2-1 0～n2−1的矩阵，使得矩阵的子矩阵的MEX最大
思路
将0放置在中间，然后以此将数绕着中心排列，这样会有MEX最大，难度在如何构造
这里从外围向里开始构造，初始化数组为-1,然后通过边界条件触发修改方向
// Author: zengyz
// 2025-06-27 15:46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void solve()
{
int n;
cin >> n;
vector<vector<int>> a(n + 1, vector<int>(n + 1, -1));
int t = 0;
int step = 1, cnt = n * n - 1;
int startx = 1, starty = 1;
while (cnt >= 0)
{
a[startx][starty] = cnt--;
int tx = startx + dir[t][0], ty = starty + dir[t][1];
if (tx < 1 || tx > n || ty < 1 || ty > n || a[tx][ty] != -1)
{
t = (t + 1) % 4;
tx = startx + dir[t][0], ty = starty + dir[t][1];
}
startx = tx, starty = ty;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _T = 1;
cin >> _T;
while (_T--)
{
solve();
}
return 0;
}
D. Quartet Swapping
题目大意
给你一个长度为n的排列，对于1<=i<=n-3,你可以交换 a i 和 a i + 2 ，以及 a i + 1 和 a i + 3 a_i和a_{i+2}，以及a_{i+1}和a_{i+3} ai和ai+2，以及ai+1和ai+3,问在经过任意次操作后字典序最小的排列是多少
思路
看第二个样例
5 4 3 1 2
，假设我们先交换后四个元素，令i=2，则有
5 1 2 4 3
再交换前四个元素,令i=1
2 4 5 1 3
发现 4 和 1 并没有改变位置，而最后一个元素i+3被置换到了最前面
这个数组奇数和偶数位置的数是不会影响的，
所以考虑贪心从1~n-3,从n-2开始后面没有另外三个数了
如果当前这个元素在最后三个，那么就先把他换到前面再进行交换
// Author: zengyz
// 2025-06-27 16:47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> a(20 * n + 1), b(20 * n + 1);
set<int> odd, even;
auto _swap = [&](int i, int j)
{
swap(a[i], a[j]);
swap(a[i + 1], a[j + 1]);
b[a[i]] = i, b[a[j]] = j;
b[a[i + 1]] = i + 1, b[a[j + 1]] = j + 1;
};
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[a[i]] = i;
if (i % 2)
odd.insert(a[i]);
else
even.insert(a[i]);
}
for (int i = 1; i <= n - 3; i++)
{
if (i % 2)
{
int idx = *odd.begin();
odd.erase(odd.begin());
if (b[idx] == n)
_swap(n - 3, n - 1);
_swap(i, b[idx]);
}
else
{
int idx = *even.begin();
even.erase(even.begin());
if (b[idx] == n)
_swap(n - 3, n - 1);
_swap(i, b[idx]);
}
}
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _T = 1;
cin >> _T;
while (_T--)
{
solve();
}
return 0;
}