今天是思维题大手子。
CF2130B
左转这个东西很烦，把它规约掉。
由于是一定要到 \(n\) 的，因此左转之后必须要右转，考虑单位元，也就是左走一格之后往右走一格是怎么个事。也就是多加一倍这两个格子里的数。
考虑这两个格子的组合，就只有 \([0,1],[1,1],[1,2],[2,2]\)，相当于我们一次走到头之后，可以从中间选择一些两个格子来回走，让数字和 \(+1,+2\) 或者 \(+3\)。
于是一定不能让 \(0,1\) 挨一块，不然怎么样都可以凑。
但是这样之后 \(+2,+3\) 的区段一定是存在的，因为题目保证至少包含各一个 \(0,1,2\)。
于是不能凑出的情况就是我们一次走到头之后差值不是 \(2\) 或 \(3\) 的倍数。\(000022221111\) 这样构造即可。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=1e4+4;
bool ql[N];
void solve(){int n,s;cin>>n>>s;vector<int> vc;int ct[5];memset(ct,0,sizeof ct);vc.clear();int sum=0;for(int i=1;i<=n;i++){int x;cin>>x;ct[x]++;sum+=x;vc.push_back(x);}if(sum>s){for(int v:vc)cout<<v<<' ';cout<<'\n';return ;}if(sum==s){cout<<-1<<'\n';return ;}int delta=s-sum;if(ql[delta]){cout<<-1<<'\n';return ;}else{for(int i=1;i<=ct[0];i++)cout<<0<<' ';for(int i=1;i<=ct[2];i++)cout<<2<<' ';for(int i=1;i<=ct[1];i++)cout<<1<<' ';cout<<'\n';}return ;
}
int main(){ql[2]=1;ql[3]=1;for(int i=1;i<=5000;i++){if(ql[i])ql[i+2]=ql[i+3]=1;}int t;cin>>t;while(t--){solve();}return 0;
}
CF2129A
注意到让 \(g(S')=0\) 是容易的，就是找到一个建好的图上的生成树。
然后注意到在题设里面成环这种东西很唐是因为这相当于把值域盖了两次。
于是猜一下我们在让 \(g(S')=0\) 的时候最大化 \(f(S')\) 就是对的，最大化 \(f\) 的方法是最大生成树。
交了下发现猜的是对的。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=6000;
struct e{int u,v,w,id;
}ek[N];
bool cmp(e x,e y){return x.w>y.w;
}
int fa[N];
int _find(int u){return u==fa[u]?u:fa[u]=_find(fa[u]);}
void solve(){memset(ek,0,sizeof ek);int n;cin>>n;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;ek[i]={a,b,abs(a-b),i};}sort(ek+1,ek+1+n,cmp);for(int i=1;i<=2*n;i++)fa[i]=i;vector<int> ans;for(int i=1;i<=n;i++){int t1=_find(ek[i].u),t2=_find(ek[i].v);if(t1==t2)continue;ans.push_back(ek[i].id);fa[t1]=t2;}cout<<ans.size()<<'\n';sort(ans.begin(),ans.end());for(int v:ans)cout<<v<<' ';cout<<'\n';return ;
}
int main(){int t;cin>>t;while(t--){solve();} return 0;
}
CF2129B
很好的题，仍然考虑单位元。
我们从小到大考虑这些数，原因是一个数如果尽可能小或者尽可能大，它进行 \(2\times n-i\) 的变换的变化量也是最大的，之后对其他比它大的元素变换，不会改变这两个数之间的关系（是或者不是逆序对）。
举例子，假设 \(n=5,a_1=2,a_2=4\)，我们钦定 \(a_1=2\) 是最优的。
此时，若你再去考虑 \(a_2\)，你会发现无论取 \(a_2=4\) 还是 \(a_2=6\)，\(a_1,a_2\) 永远不会再变成逆序对。
也就是说，这样考虑是没有后效性的。
于是我们可以轻易统计出变换还是不变换一个数对逆序对数量的贡献，取最小值加入答案即可。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=6000;
int a[N];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; int ans=0;for(int i=1;i<=n;i++){int p=0;for(int j=1;j<=n;j++){if(i==a[j]){p=j;break;}}int up=0,dn=0;for(int j=1;j<p;j++){if(a[j]>i)up++;}for(int j=p+1;j<=n;j++){if(a[j]>i)dn++;}ans+=min(up,dn);}cout<<ans<<'\n';
}
int main(){int t;cin>>t;while(t--){// init();solve();}return 0;
}
CF2119D
也是好题，需要一些关键的转化，但是这种转化看起来比较公式啊，之前没见过导致的。
发现对着一个 \(a\) 求 \(f(a)\) 非常恶心，于是从一种移除点的方式入手去构造 \(a\)，就是考虑算贡献。
考虑一个长为 \(n\) 的序列 \(p\) 来表示我们移除点的顺序，因为题目中并未要求将全部点移除，因此我们用 \(p_i=0\) 来表示我们在第 \(i\) 次操作中没有移除任何点。
由题目中对 \(a\) 的限制，这个排列应满足 \(0\le p_i\le i\)，且不为零的 \(p_i\) 应互不相同，因为你不能把一个位置移除两次。
这样，我们可以找到所有删除序列为 \(p\) 的 \(a\) 的数量，也就是简单的将所有不为 \(0\) 的 \(p_i\) 相乘。这个应该很容易理解。这样，这个 \(p\) 会在每一个 \(a\) 的 \(f(a)\) 中贡献一次。定义所有删除序列为 \(p\) 的 \(a\) 的数量为排列 \(p\) 的权值。
于是我们只需要统计出所有满足条件的 \(p\) 的权值和就可以了。这个东西是好 DP 的。
设 \(f_{i,j}\) 表示前 \(i\) 个 \(a_i\) 删了 \(j\) 个位置的权值和。
当 \(p_i=0\) 时，也就是不删点，有 \(f_{i,j} \leftarrow f_{i-1,j}\)
当 \(p_i \ne 0\) 时，我们前面已经删了 \(j-1\) 的点，此时我们能删的位置还有 \(i\) 个，我们在这一次能删的地方还有 \(i-j+1\) 个。
但这样统计权值就不好办了，因为我们不确定要删的是哪个数。
我们再进行一步转化，令 \(f_{i,j}\) 表示考虑了后 \(n\sim i\) 个位置，删了 \(j\) 个位置的权值和。
为什么现在要从后往前考虑呢，因为能把 \(i\) 位置删了的 \(p\) 只能是 \(p_i\sim p_n\)
若我们决策删掉 \(i\)，也就是说我们要把 \(i\) 塞到 \(p_i\sim p_n\) 的一个里面，会对答案产生 \(i\) 的贡献。但是由于我们已经给 \(j-1\) 个 \(p\) 塞过不为零的值了，还能给 \(n-i+1-(j-1)\) 个为 \(0\) 的位置塞。于是 \(f_{i,j} \leftarrow f_{i+1,j-1}\times (n-i+1-(j-1)) \times i\)
若我们决策不删 \(i\)，也就是说我们要把 \(0\) 塞到 \(p_i\sim p_n\) 的一个里面，不会对答案产生贡献，于是 \(f_{i,j} \leftarrow f_{i+1,j}\)
初始值是 \(f_{n,0}=1,f_{n,1}=n\)，答案是 \(\sum_{i=0}^{n} f_{1,i}\)，因为没有要求全删完。
如此转移即可。代码挺短的。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=5005;
int dp[N][N];
int n,m;
void init(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)dp[i][j]=0;}return ;
}
void solve(){cin>>n>>m;dp[n][0]=1;dp[n][1]=n;for(int i=n-1;i>=1;i--){for(int j=0;j<=n-i+1;j++){if(j==0){dp[i][j]=dp[i+1][j];continue;}dp[i][j]=(1ll*dp[i+1][j-1]*((n-i+1)-(j-1))%m*i%m+dp[i+1][j])%m;}}ll ans=0;for(int i=0;i<=n;i++){ans=(ans+dp[1][i])%m;}cout<<ans<<'\n';
}
int main(){int t;cin>>t;while(t--){init();solve();}return 0;
}