Educational Codeforces Round 141 解题报告
\(\text{By DaiRuiChen007}\)
A. Make it Beautiful
所有 \(\{a_i\}\) 相等显然不行，把最大的 \(a_i\) 放最前面，只要第二个和第一个不同就可以随便排了
我这里是用出现次数进行分层，对于出现次数 \(\ge 1,\ge 2,\ge 3,\cdots\) 的值分别逆序排列
时间复杂度 \(\Theta(n\log n)\)，瓶颈在 map 统计出现次数上
#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
map <int,int> cnt;
vector <int> a,p[MAXN];
inline void solve() {
cnt.clear(),a.clear();
int n;
scanf("%d",&n);
a.resize(n);
for(int i=1;i<=n;++i) p[i].clear();
for(int i=0;i<n;++i) {
scanf("%d",&a[i]);
++cnt[a[i]];
p[cnt[a[i]]].push_back(a[i]);
}
if(cnt.size()==1) puts("NO");
else {
puts("YES");
for(int i=1;i<=n;++i) {
sort(p[i].begin(),p[i].end(),greater<int>());
for(int j:p[i]) printf("%d ",j);
}
puts("");
}
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
B. Matrix of Differences
大胆猜测答案为 \(n^2-1\) 即 \(1\sim n^2\) 都有
先考虑一行的情况，即把 \(1\sim n\) 重排成一个序列，使得相邻两个数的差恰好出现 \(1\sim n-1\)
简单模拟即可得到一个合法的序列：\(\{1,n,2,n-1,3,n-2,\cdots\}\)
因此构造一个长度为 \(n^2\) 的序列然后加几个拐点塞进 \(n\times n\) 的矩阵里即可
时间复杂度 \(\Theta(n^2)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=51;
int a[MAXN][MAXN];
inline void solve() {
int n;
scanf("%d",&n);
int L=1,R=n*n;
for(int i=1;i<=n;++i) {
if(i%2==1) {
for(int j=1;j<=n;++j) {
a[i][j]=(i+j)%2==1?R--:L++;
}
} else {
for(int j=n;j>=1;--j) {
a[i][j]=(i+j)%2==1?R--:L++;
}
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
printf("%d ",a[i][j]);
}
puts("");
}
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
C. Yet Another Tournament
显然首先应该击败尽可能多的人，这一步可以按 \(a_i\) 小到大贪心
然后假设你已经确定你最多击败 \(k\) 个人，那么第 \(1\sim k\) 个人获胜次数一定不超过 \(k\)，第 \(k+2\sim n\) 个人获胜次数一定超过 \(k\)，而第 \(k+1\) 个人获胜次数为 \(k\) 或 \(k+1\)，假如你能在不影响获胜次数的前提下击败 \(k+1\)，你的排名会更高
因此你只需要优先击败 \(k+1\)，然后判断剩下的 \(m\) 够不够你再击败 \(k-1\) 个人即可
时间复杂度 \(\Theta(n\log n)\)，瓶颈在对 \(\{a_i\}\) 排序上
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int MAXN=5e5+1;
int n,m,a[MAXN];
inline int calc(const vector<pii> &p) {
int lim=m;
for(int i=0;i<n;++i) {
if(p[i].first>lim) return i;
lim-=p[i].first;
}
return n;
}
inline void solve() {
scanf("%lld%lld",&n,&m);
vector <pii> p;
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),p.push_back(make_pair(a[i],i));
sort(p.begin(),p.end());
int ans=calc(p);
if(ans==n) printf("1\n");
else if(ans==0) printf("%lld\n",n+1);
else {
for(int i=0;i<n;++i) {
if(p[i].second==ans+1) {
auto del=p[i];
p.erase(p.begin()+i);
p.insert(p.begin(),del);
}
}
if(calc(p)==ans) printf("%lld\n",n-ans);
else printf("%lld\n",n-ans+1);
}
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
D. Different Arrays
先考虑什么时候两个不同的操作序列 \(X,Y\) 能够得到相同的 \(a\)
假设 \(j\) 是第一个 \(x_j\ne y_j\) 的位置，那么此时 \(X,Y\) 对应的序列中 \(a_j\) 分别变成 \(a_j-a_{j+1}\) 和 \(a_j+a_{j+1}\)，又因为往后的操作不会改变 \(a_j\) 的值，因此只有可能在 \(a_{j+1}=0\) 时会产生重复
因此我们考虑 \(dp_{i,x}\) 表示进行了第 \(i\) 次操作前，\(a_{i+1}=x\) 的方案数，得到如下转移：
dp_{i+1,a_{i+1}+x}&\gets dp_{i,x}\\
dp_{i+1,a_{i+1}-x}&\gets dp_{i,x}
\end{aligned}
\]
\(x=0\) 的时候产生的两个转移是重复的，只需要去掉其中一条转移即可，最终答案为 \(\sum_x dp_{n-1,x}\)
设 \(w\) 为 \(\{a_i\}\) 的值域，那么最终 \(x\) 的值域为 \(nw\)，朴素转移即可
时间复杂度 \(\Theta(n^2w)\)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int MAXN=301,W=1e5+1,MOD=998244353;
int a[MAXN],dp[MAXN][W<<1];
//a[i+1]=j after process (i-1,i,i+1)
signed main() {
int n,ans=0;
scanf("%lld",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
dp[1][a[2]+W]=1;
for(int i=2;i<n;++i) {
for(int x=-W;x<W;++x) {
dp[i][a[i+1]+x+W]=(dp[i][a[i+1]+x+W]+dp[i-1][x+W])%MOD;
if(x!=0) dp[i][a[i+1]-x+W]=(dp[i][a[i+1]-x+W]+dp[i-1][x+W])%MOD;
}
}
for(int x=0;x<2*W;++x) ans=(ans+dp[n-1][x])%MOD;
printf("%lld\n",ans);
return 0;
}
E. Game of the Year
转化题意，得到题目实际是让你求满足 \(\forall i\in[1,n]:\left\lceil\dfrac{a_i}k\right\rceil\le \left\lceil\dfrac{b_i}k\right\rceil\) 的 \(k\) 的数量
容易想到用整除分块对于每个 \((a_i,b_i)\) 进行二维数论分块计算 \(k\) 合法的区间，但是 \(\Theta(n\sqrt n)\) 的复杂度容易被卡常，事实上还有复杂度更加优秀的算法
转化一下 \(\left\lceil\dfrac{a_i}k\right\rceil\le \left\lceil\dfrac{b_i}k\right\rceil\)，显然对于 \(a_i\le b_i\)，这样的 \(k\) 恒成立，因此只考虑 \(a_i>b_i\) 的情况，就等价于不存在 \(t\) 使得 \(b_i\le tk<a_i\)，因此用差分对每个区间 \([a_i,b_i)\) 进行覆盖，如果 \(k\) 的某个倍数被覆盖那么 \(k\) 不合法
时间复杂度 \(\Theta(n\ln n)\)，瓶颈在枚举 \(k\) 和 \(k\) 的所有倍数上
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int a[MAXN],b[MAXN],d[MAXN];
inline void solve() {
int n;
vector <int> ans;
scanf("%d",&n);
for(int i=1;i<=n;++i) d[i]=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) if(a[i]>b[i]) ++d[b[i]],--d[a[i]];
for(int i=1;i<=n;++i) d[i]+=d[i-1];
for(int i=1;i<=n;++i) {
bool ok=true;
for(int j=i;j<=n;j+=i) {
if(d[j]) {
ok=false;
break;
}
}
if(ok) ans.push_back(i);
}
printf("%d\n",(int)ans.size());
for(int i:ans) printf("%d ",i);
puts("");
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
F. Double Sort II
先考虑只对 \(a\) 排序的最小花费，显然连接 \(i\to a_i\) 建图，对于图中的每一个大小为 \(|\mathbf C|\) 的置换环，根据复原置换的结论，我们需要 \(|\mathbf C|-1\) 次操作把这个环复原，设 \(cyc\) 为图中环的数量，答案为 \(n-cyc\)，我们可以理解为每个在每个环中选出一个 \(x\) 不操作
接下来考虑同时对 \(a\) 和 \(b\) 排序，类似上面，对于 \(a,b\) 中的每个环，分别选出一个 \(x\) 不操作，我们称 \(x\) 为这个环的“代表”
注意到只有 \(x\) 同时是 \(a\) 中所属环和 \(b\) 中所属环的“代表”，我们才可以不操作 \(x\)
因此把 \(a\) 中的每个环看成左部点，\(v\) 中的每个环看成其右部点，每个位置 \(i\) 看成一条连接 \(i\) 在 \(a\) 中所属环和在 \(b\) 中所属环的一条边，得到一张二分图，二分图的每条匹配边对应选择相应的 \(x\) 作为其在两边所在的环的“代表”然后跳过对 \(x\) 的操作
设其最大匹配大小为 \(|\mathbf M|\)，那么答案为 \(n-|\mathbf M|\)，求出匹配方案输出即可
时间复杂度 \(\Theta(n^2)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3001;
vector <int> G[MAXN];
int a[MAXN],b[MAXN],ia[MAXN],ib[MAXN],tar[MAXN];
bool vis[MAXN];
inline bool dfs(int x) {
for(int p:G[x]) {
if(vis[p]) continue;
vis[p]=true;
if(tar[p]==-1||dfs(tar[p])) {
tar[p]=x;
return true;
}
}
return false;
}
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
memset(vis,false,sizeof(vis));
for(int tot=0,i=1;i<=n;++i) {
if(ia[i]) continue;
++tot;
while(!vis[i]) {
vis[i]=true,ia[i]=tot;
i=a[i];
}
}
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
memset(vis,false,sizeof(vis));
for(int tot=0,i=1;i<=n;++i) {
if(ib[i]) continue;
++tot;
while(!vis[i]) {
vis[i]=true,ib[i]=tot;
i=b[i];
}
}
memset(tar,-1,sizeof(tar));
for(int i=1;i<=n;++i) G[ia[i]].push_back(ib[i]);
int tot=n;
for(int i=1;i<=n;++i) {
memset(vis,false,sizeof(vis));
if(dfs(i)) --tot;
}
printf("%d\n",tot);
for(int i=1;i<=n;++i) {
if(tar[ib[i]]==ia[i]) tar[ib[i]]=-1;
else printf("%d ",i);
}
puts("");
return 0;
}
