A. Painting the Ribbon

暴力模拟即可

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n,m,k;cin>>n>>m>>k;vector<int> a(n+5);int f=0;for(int i=1;i<=n;i++){a[i]=f;f=(f+1)%m;}int cnt=0;for(int i=1;i<=n;i++){if(a[i]!=0) cnt++;}if(cnt>k) cout<<"YES"<<endl;else cout<<"NO"<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);// cout.tie(0);int t;t = 1;cin >> t;while (t--){solve();}system("pause");return 0;
}

B. Make It Ugly

思路：显然，当一个数组的开头和结尾不同时，其一定是不好的，我们思考，是否存在其他方式让数组变得不好，自己造几组样例手玩一下就会发现，当数组中存在两个不同的数，并且这两个数相邻，且不等于数组开头/结尾时，这个数组是不好的，所以我们把数组变得不好的方式有三种：
其一是让数组的开头和结尾不同，其二便是让两个不同的数相邻。
按照上述策略进行贪心即可。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n;cin>>n;vector<int> a(n+5);map<int,int> mp;for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;int cnt=n;if(mp.size()==1) {cout<<-1<<endl;return ;}int last=0;for(int i=1;i<=n;i++){if(a[i]!=a[1]){cnt=min(cnt,i-last-1);last=i;}}cnt=min(cnt,n-last);cout<<cnt<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);// cout.tie(0);int t;t = 1;cin >> t;while (t--){solve();}system("pause");return 0;
}

C. Long Multiplication

思路：这种题目一般是具有什么性质，对于给定的两个数，我们容易发现，无论两个数的数位如何交换，其和不会改变，那么令 $x+y=c$ , $x=c-y$,对于给定的$x\times y$,我们可以表示为$$f=(c-y)\times y$$,容易得到，当$x=c/2$时，整个式子会得到最大值，那么此时的$x$和$y$ 相等，所以我们想让$f(x)$的值越大，那么$x$和$y$的差值就要越小，因此贪心的去构造交换即可。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{string a,b;cin>>a>>b;for(int i=0;i<a.size();i++){if(a[i]==b[i]) continue;else if(a[i]<b[i]){for(int j=i+1;j<a.size();j++){if(a[j]<b[j]) swap(a[j],b[j]);}break;}else if(a[i]>b[i]){for(int j=i+1;j<a.size();j++) if(a[j]>b[j]) swap(a[j],b[j]);break;} }cout<<a<<endl;cout<<b<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);// cout.tie(0);int t;t = 1;cin >> t;while (t--){solve();}system("pause");return 0;
}

D. Colored Balls

思路：考虑一组的贡献，容易得到，定义一组的总个数为$sum$，最大值为 $mx$, 那么这一组的贡献为$min(mx,(sum+1)/2)$，为什么呢，
当除最大值之外的所有值之和小于最大值时，我们为了保证一组内每种颜色的球不超过 1 个，那么至少得分出 $mx$组。
当其大于最大值时，贡献为$(sum+1)/2$,这样保证是最小的，为什么呢，我们每次将数组中的最大值和次大值减一，最后只会剩下1个或0个，因此向上取整即可。
计算完一组的贡献，我们考虑如何进行$2^n$组，当我们放入$a_i$时，我们无法确定此时具体的贡献，所以我们很容易想到，对a数组进行从小到大的排序，然后使用$f[k]$表示总和为$k$时的方案数，因为知道了当前总和，所以我们枚举$a_i$即可。
具体的方案数则是可以用背包进行维护，有时候对于这种每个数选或是不选从而构成$2^n$级别的题目，则可以考虑背包，同时对于背包问题，当其数据范围过小时，我们是可以用状压去解决背包问题的，即用一个二进制数去枚举当前这一位选或是不选。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"template<const int T>
struct ModInt {const static int mod = T;int x;ModInt(int x = 0) : x(x % mod) {}ModInt(long long x) : x(int(x % mod)) {} int val() { return x; }ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }ModInt operator / (const ModInt &a) const { return *this * a.inv(); }bool operator == (const ModInt &a) const { return x == a.x; };bool operator != (const ModInt &a) const { return x != a.x; };void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }void operator /= (const ModInt &a) { *this = *this / a; }friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}ModInt pow(int64_t n) const {ModInt res(1), mul(x);while(n){if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}ModInt inv() const {int a = x, b = mod, u = 1, v = 0;while (b) {int t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}if (u < 0) u += mod;return u;}};
using mint = ModInt<998244353>;mint dp[N];void solve()
{int n;cin>>n;vector<int> a(n+5);for(int i=1;i<=n;i++) cin>>a[i];sort(a.begin()+1,a.begin()+1+n);mint ans=0;dp[0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=5000;j++){if(j<=a[i]) ans+=dp[j]*a[i];else ans+=dp[j]*((j+a[i]+1)/2);}for(int j=5000;j>=a[i];j--) dp[j]+=dp[j-a[i]];//对当前ai去跑背包即可}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);// cout.tie(0);int t;t = 1;// cin >> t;while (t--){solve();}system("pause");return 0;
}

同时可以将d题改变一下，同样是计算$2^n$组，但每一组的贡献为该组的最大值，计算最后的答案。
这样就将a数组从大到小进行排序，考虑当前$a_i$对答案的贡献即可。

E. Chain Reaction

ok又是经典问题
思路：我们考虑$k=1$的情况，那么对于每个$a_i$而言，其只有在$a_i>a_{i-1}$时，才会产生贡献，所以整个序列的贡献为：$$\sum _{i=1}^{i=n}max(0,a_i-a_{i-1})$$
那么我们考虑 $k$ 等于任意值的情况，显然为$max(\lceil \frac{a_i}{k}\rceil -\lceil \frac{a_{i-1}}{k}\rceil ,0)$
因此对于上述的情况，$a_i$的贡献为+1，$a_{i-1}$的贡献为-1，我们统计每个位置对应的贡献即可。
最后应该如何进行计算呢，我们会发现当$a_i$处于某个区间时，其$\frac{a_i}{k}$的值是一定的，所以我们可以枚举这个定值$x$，从而得到当$a_i$处于$[(x-1)\ast k+1,x\ast k]$，其值是一定的。最后便可以得到答案。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n;cin>>n;vector<int> a(n+5);for(int i=1;i<=n;i++) cin>>a[i];int mx=*max_element(a.begin()+1,a.begin()+1+n);vector<ll> c(N);for(int i=1;i<=n;i++) {if(a[i]>a[i-1]) c[a[i]]++,c[a[i-1]]--;//计算每个值对应的贡献}for(int i=1;i<=mx;i++) c[i]+=c[i-1];//因为我们需要进行区间计算，所以先得算出前缀和for(int i=1;i<=mx;i++){ll res=0;for(int j=1;j<=(mx+i-1)/i;j++){//即枚举上文所说的x，res+=j*(c[min(j*i,mx)]-c[(j-1)*i]);}cout<<res<<" ";}cout<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin >> t;while (t--){solve();}system("pause");return 0;
}