[赛后总结]G2022 Regular Contest 02总结_综合

由于某人的某个~~不过脑袋~~的提议，现在我们开始常规赛互测了…
常规赛01很简单，没有AK是我的问题，就不打算写了。

赛时

T1

我的组合计数果然还是一样的烂…这一道题目就花了我将近一个小时的时间…
首先我以为计算相交的多米诺骨牌的方案数可以用一个二维dp来解决…结果怎么dp都是错的。然后发现情况很复杂，于是决定两个维度拆开来算。
试了半天才搞出来了一个比较可观的做法。
然后写完之后还调试了半天…最终还是把它给磕出来了…

T2

看完题目满脸问号，感觉是一道结论性的题目。
然后试着去找了找规律，感觉简单的让我有点难以相信…于是先去看看T3。

T3

一看就是那种满是套路的题目…
显然就是那种重新建图然后跑强连通的题目…
满分做法可能给还需要倍增优化建图?但是还是无法通过…
然后就开始码n方暴力，结果结束了还没调出来…

赛后总结

考的很差…
T1-首先不得不承认Codeforces风格的题目我还是做得很差，做一道题目就花了我那么长的时间。
T2-真没想到结论就这么简单…自闭了。
T3-忘了还有虚树这种东西…这种题真的好难码啊…
真的还有很长的路要走啊…

题解

骨牌战车 (domino)

咕了…

/*Lower_Rating*/
/*濂介毦....*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 3600
#define eps 1e-10
#define INF 2147483647
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}int n,h,w,ph,pw,ans;
int vx[MAXN+5],vy[MAXN+5];
int fac[MAXN+5],ifac[MAXN+5],f[MAXN+5][MAXN+5],g[MAXN+5][MAXN+5];
void prepare(){
    fac[0]=1;for(int i=1;i<=max(h,w);i++)fac[i]=mul(fac[i-1],i);ifac[max(h,w)]=fst_pow(fac[max(h,w)],MOD-2);for(int i=max(h,w)-1;i>=0;i--)ifac[i]=mul(ifac[i+1],i+1);
}
int Comb(int a,int b){
    if(b>a||a<0||b<0)return 0;return mul(fac[a],mul(ifac[a-b],ifac[b]));
}
int main(){
    freopen("domino.in","r",stdin);freopen("domino.out","w",stdout);h=read(),w=read(),n=read();for(int i=1;i<=2*n;i++){
    int x=read(),y=read();vx[x]++,vy[y]++;}prepare();f[0][0]=g[0][0]=1;for(int i=1;i<=h;i++)for(int j=0;j<=i/2;j++){
    f[i][j]=add(f[i][j],f[i-1][j]);if(i>=2&&j&&!vx[i]&&!vx[i-1])f[i][j]=add(f[i][j],f[i-2][j-1]);}for(int i=1;i<=w;i++)for(int j=0;j<=i/2;j++){
    g[i][j]=add(g[i][j],g[i-1][j]);if(i>=2&&j&&!vy[i]&&!vy[i-1])g[i][j]=add(g[i][j],g[i-2][j-1]);}ph=h,pw=w;for(int i=1;i<=h;i++)if(vx[i])ph--;for(int i=1;i<=w;i++)if(vy[i])pw--;for(int i=0;i<=ph;i++)for(int j=0;j<=pw;j++)ans=add(ans,mul(mul(f[h][i],mul(Comb(ph-2*i,j),fac[j])),mul(g[w][j],mul(Comb(pw-2*j,i),fac[i]))));printf("%d",ans);
}

谎言 (lie)

题解

这题有很多方法来找规律。
首先可以尝试打一下小数据的表来找规律，但是这样找有些复杂…
这题可以用网络流的思想来得到结论…但是应为我愚蠢的以为这是一套联赛考纲内的题然后就想都没想…
贴一下组题人题解:
[赛后总结]G2022 Regular Contest 02总结

/*Lower_Rating*/
/*dianfenzhi*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 40000
#define eps 1e-10
#define INF 2147483647
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}int T,n,a[MAXN+5],F;
LL sum;int main(){
    freopen("lie.in","r",stdin);freopen("lie.out","w",stdout);T=read();while(T--){
    n=read();sum=F=0;for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+n+1);for(int i=1;i<=n;i++){
    sum+=a[i];if(sum<1LL*i*(i-1)/2){
    puts("cake is lie.");F=1;break;}}if(F)continue;if(sum!=n*(n-1)/2)puts("cake is lie.");else puts("cake is not lie.");}
}

牢不可破的联盟 (union)

很无脑的数据结构题…
首先考虑 $n^2$ 暴力。
显然我们需要建出一个有关颜色的图，然后再跑强连通分量。
于是我们枚举每一种颜色，对这种颜色形成的连通块的点上出现的所有颜色都连边即可。
这个图有两个缺点，一是边数是 $O(n^2)$ 的，二是连图过程也是 $O(n^2)$ 的。
对于边数我们很容易想到一段路径倍增优化建图。
然后你会发现你只需要用到 $S_k$ 及其两两LCA的点，这显然就是虚树能够解决的问题。
于是你就可以开始愉快的码这个接近200行的代码了…