CF
Problem - 1455D - Codeforces
贪心，从小到大遍历
因为a[i]>x才能交换
所以把大的换小，使其满足单调不递减
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[N];void solve()
{int n, x;int ans = 0;cin >> n >> x;for (int i = 0; i < n;i++){cin >> a[i];}for (int i = 1; i < n;i++){if(a[i]>=a[i-1])continue;for (int j = 0; j < i;j++){if(a[j]>x){swap(a[j], x);ans++;}}if(a[i]<a[i-1]){cout << -1 << endl;return;}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1957C - Codeforces（dp好题）
计算方案数
通过
\[dp[i]=dp[i-1]+dp[i-2]*(i-1)*2
\]
推最后的\(dp[n]\)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 1e9+7;
const int N=3e5+10;
LL dp[N];void solve()
{int n, k;cin >> n >> k;int r, c;while(k--){cin >> r >> c;n -= (r == c ? 1 : 2);}dp[0] = dp[1] = 1, dp[2] = 3;for (int i = 3; i <= n;i++){dp[i] = dp[i - 1] + dp[i - 2] * (2 * i - 2);dp[i] %= mod;}cout << dp[n] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}