A:先将 \(a\) 降序排序,此时只有位置 \(2\) 有可能不满足条件。找到最小的 \(i\ge 2\) 使得 \(a_1\neq a_i\)(不存在则无解),然后交换 \(a_2,a_i\),即为一个解。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, a[55];
bool cmp(int x, int y)
{
return x > y;
}
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1, cmp);
for(int i=2;;i++)
{
if(i > n)
{
cout << "NO" << endl;
return;
}
if(a[i] != a[1])
{
swap(a[2], a[i]);
break;
}
}
cout << "YES" << endl;
for(int i=1;i<=n;i++)
{
cout << a[i] << ' ';
}
cout << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
B:
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, a[55][55];
void solve()
{
cin >> n;
int cur1 = 1, cur2 = n * n;
for(int i=1;i<=n;i++)
{
if(i % 2)
{
for(int j=1;j<=n;j++)
{
if((i + j) % 2 == 0)
{
a[i][j] = cur1++;
}
else
{
a[i][j] = cur2--;
}
}
}
else
{
for(int j=n;j;j--)
{
if((i + j) % 2 == 0)
{
a[i][j] = cur1++;
}
else
{
a[i][j] = cur2--;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout << a[i][j] << ' ';
}
cout << endl;
}
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
C:
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, m, pa[500005];
struct Node {
int x, id;
} a[500005];
bool cmp(Node x, Node y)
{
return x.x == y.x ? x.id > y.id : x.x < y.x;
}
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i].x;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
for(int i=1;i<=n;i++)
{
pa[a[i].id] = i;
}
int sum = 0;
for(int i=1;i<=n;i++)
{
if(sum + a[i].x > m)
{
int ans = 1;
for(int j=1;j<=n;j++)
{
ans += (i - 1 < (j >= i) + a[j].id - 1);
}
int ID = pa[i];
if(ID >= i && sum - a[i - 1].x + a[ID].x <= m)
{
ans--;
}
cout << ans << endl;
return;
}
sum += a[i].x;
}
cout << 1 << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
D:
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f, mo = 998244353;
int n, a[305], dp[305][180010];
int qpw111(int x, int y)
{
if(!y)
{
return 1;
}
int tmp = qpw111(x, y / 2);
return tmp * tmp % mo * (y % 2 ? x : 1) % mo;
}
int qpw(int x, int y)
{
int phimo = mo - 1;
return qpw111(x % mo, (y % phimo + phimo) % phimo);
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
dp[1][a[2] + 90000] = 1;
dp[2][a[3] + a[2] + 90000] = 1;
if(a[2])
{
dp[2][a[3] - a[2] + 90000] = 1;
}
for(int i=2;i<n-1;i++)
{
for(int j=-90000;j<=90000;j++)
{
if(!j)
{
(dp[i + 1][a[i + 2] + 90000] += dp[i][90000]) %= mo;
}
else
{
if(a[i + 2] + j <= 90000)
{
(dp[i + 1][a[i + 2] + j + 90000] += dp[i][j + 90000]) %= mo;
}
if(a[i + 2] - j <= 90000)
{
(dp[i + 1][a[i + 2] - j + 90000] += dp[i][j + 90000]) %= mo;
}
}
}
}
int ans = 0;
for(int i=0;i<=180000;i++)
{
(ans += dp[n - 1][i]) %= mo;
}
cout << ans << endl;
return 0;
}