ABC131F
题意：
给定\(n\)个点，如果存在一个四边形恰好缺一个点，则能补一个点，最多操作多少次？
所有数字小于等于\(10^5\)
题解：
把行数，列数当作点，把点当作边
对于一个点\((x,y)\)，从\(x_i\)向\(y_j\)之间连一条边。
对于恰好缺一个点的情况，这个连通块里有两个行点，两个列点，三条边，缺一条边。
对于四边形满点的情况，这个连通块里有两个行点，两个列点，四条边。
所以一个连通块的贡献是行点数×列点数-边数
\[ans=(\sum a_i*b_i)-n \]#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n;cin>>n;
int maxn=1e5;
vector<int> f(2*maxn+1),s1(2*maxn+1),s2(2*maxn+1);
for(int i=1;i<=2*maxn;++i) f[i]=i;
for(int i=1;i<=maxn;++i) s1[i]=1;
for(int i=maxn+1;i<=2*maxn;++i) s2[i]=1;
function<int(int)> find=[&](int k) -> auto
{
return f[k]==k?k:f[k]=find(f[k]);
};
for(int i=1;i<=n;++i)
{
int x,y;
cin>>x>>y;
int tx=find(x),ty=find(maxn+y);
if(tx==ty) continue;
s1[ty]+=s1[tx];
s2[ty]+=s2[tx];
f[tx]=ty;
}
int sum=0;
for(int i=1;i<=2*maxn;++i) if(find(i)==i)
{
//cout<<s1[i]<<' '<<s2[i]<<"!!!"<<endl;
sum+=s1[i]*s2[i];
}
cout<<sum-n<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC134F
题意：
一个\(1\sim n\)的排列\(p\)的怪异度定义为\(\sum_i |p_i-i|\)。
求怪异度为\(m\)的排列的数量，模\(1e9+7\)
\(1\leq n\leq 50,0\leq m\leq n^2\)
题解：
可以转化为有\(n\)个小球和\(n\)个盒子，一一配对，每个小球和自己盒子之间编号的差距和为\(k\)的放球方案数。
设一个不是人能想出来的\(dp\)方程：
\(dp[i][j][k]\)表示前\(i\)个小球中，有\(j\)个球和\(j\)个盒子还没配对呢，当前怪异度为\(k\)
考虑当前处理到的第\(i\)个小球和第\(i\)个盒子：
第一种情况，这两扔这不管，那么又多了一组不配对的球和盒子，而且前面的球和盒子都没被配上，都会贡献一点怪异度
\(dp[i][j][k]->dp[i+1][j+1][k+(2*j)+2]\)
第二种情况，这两贡献了一对配对，那么既可以是这个小球和前面的盒子配对了，也可以是这个盒子和这个小球配对了，或者第\(i\)个小球和第\(i\)个盒子配对了。
\((2*j+1)*dp[i][j][k]->dp[i+1][j][k+2*j]\)
第三种情况，这两贡献了两对配对，盒子和小球都在前面找对象，小球和盒子都有\(j\)种选择
\(j*j*dp[i][j][k]->dp[i+1][j-1][k+(2*j)-2]\)
这样就好了
另外，因为第一种转移\(k\)要额外\(+2\)，而\(j\)会\(+1\)，第三种转移\(k\)要额外\(-2\)，而\(j\)要\(-1\)
最后的答案是\(dp[n][0][m]\)，所以，\(+2\)和\(-2\)最后一定会抵消掉，也可以这么写转移
\(dp[i][j][k]->dp[i+1][j+1][k+2*j]\)
\((2*j+1)*dp[i][j][k]->dp[i+1][j][k+2*j]\)
\(j*j*dp[i][j][k]->dp[i+1][j-1][k+2*j]\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector dp(n+1,vector(n+1,vector<int>(m+1)));
dp[0][0][0]=1;
//dp[i][j][k] 前i个球中，有j个球和盒子还没配对，已经有k的价值
for(int i=0;i<n;++i)
{
for(int j=0;j<=n;++j)
{
for(int k=0;k<=m;++k)
{
if(k+2*j+2<=m&&j<n)
{
int &ret=dp[i+1][j+1][k+2*j+2];
ret=(ret+dp[i][j][k])%mod;
}
if(k+2*j<=m)
{
int &ret=dp[i+1][j][k+2*j];
ret=(ret+(2*j+1)*dp[i][j][k]%mod)%mod;
}
if(k+2*j-2<=m&&k+2*j-2>=0&&j>0)
{
int &ret=dp[i+1][j-1][k+2*j-2];
ret=(ret+j*j%mod*dp[i][j][k]%mod)%mod;
}
}
}
}
cout<<dp[n][0][m]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
1 2 5 10
*/