CSP模拟14

据joke3579说明，lyin做过今天的题但是给机会了。
而且题目名称不管怎样都很吊。

T1

三分理论不对但是能过。但是场上把所有端点扒下来排序三分炸了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const double eps=1e-6;
int ans;
int n;
int pos1[300010],pos2[300010];
struct node{
    int l,r;
}numa[300010],numb[300010];
bool cmp1(node a,node b){
    return a.r<b.r;
}
bool cmp2(node a,node b){
    return a.l<b.l;
}
int check(int mid){
    int p1=0,p2=0,sum1=0,sum2=0,ans=0;
    for(int i=1;i<=n;i++){
        if(numa[i].r<mid) pos1[++p1]=numa[i].r;
        if(numb[i].l>mid) pos2[++p2]=numb[i].l;
    }
    int p3=n-p1-p2;
    for(int i=1;i<=p1;i++){
        ans+=(i-1)*pos1[i]-sum1;
        ans+=p3*(mid-pos1[i]);
        sum1+=pos1[i];
    }
    for(int i=1;i<=p2;i++){
        ans+=(i-1)*pos2[i]-sum2;
        ans+=p3*(pos2[i]-mid);
        sum2+=pos2[i];
    }
    ans+=p1*sum2-p2*sum1;
    return ans;
}
signed main(){
    scanf("%lld",&n);
    double l=1e8,r=-1e8;
    for(int i=1;i<=n;i++){
        double x,y;scanf("%lf%lf",&x,&y);
        l=min(l,x);r=max(r,y);
        numa[i]=(node){(int)x,(int)y};numb[i]=(node){(int)x,(int)y};
    }
    sort(numa+1,numa+n+1,cmp1);
    sort(numb+1,numb+n+1,cmp2);
    while(r-l>=eps){
        double mid=(r-l)/3.0;
        int a=check((int)(l+mid)),b=check((int)(r-mid));
        if(a>=b)ans=a,l+=mid;
        else r-=mid;
    }
    printf("%lld\n",ans);
    return 0;
}

T2

按照每行 \(1\) 的个数排序扫，每一行整 个bitset压起来。
枚举选中的行有 \(i\) 个 \(1\) ，pre为前缀和，suf为后缀和，那么 \(pre_{i-1}\cap suf_{i+1}=\emptyset\) ，方案数是 \(\binom{|U-suf_i|-|pre_i|}{i-|pre_i|}\)
然后考察相等的，如果有那随便选，方案数 \(2^{num}\) 。

/*路人女主 润了
居然没人场切 然后集训队全场切了 什么叫差距啊
我第一次见瓶颈在读入的题*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;
const int mod=998244353;
int n,ans,jc[5010],inv[5010],pos[5010][5010];
char s[5010];
bitset<5010>a[5010],pre[5010],suf[5010];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int C(int n,int m){
    if(n<m||m<0)return 0;
    return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    scanf("%d",&n);jc[0]=inv[0]=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        suf[n+1][i]=1;
        for(int j=1;j<=n;j++){
            if(s[j]=='1')a[i][j]=1;
        }
        jc[i]=1ll*jc[i-1]*i%mod;
        inv[i]=qpow(jc[i],mod-2);
        int ret=a[i].count();
        pos[ret][++pos[ret][0]]=i;
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        for(int j=1;j<=pos[i][0];j++)pre[i]|=a[pos[i][j]];
    }
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1];
        for(int j=1;j<=pos[i][0];j++)suf[i]&=a[pos[i][j]];
    }
    for(int i=0;i<=n;i++){
        if((pre[i]|suf[i])==suf[i]){
            ans=(ans+qpow(2,pos[i][0])-1)%mod;
            int a1=pre[i].count(),a2=suf[i].count();
            ans=(ans+C(a2-a1,i-a1))%mod;
        }
    }
    printf("%d\n",ans);
    return 0;
}

T3

场上套了个三层容斥没套出来。赛后发现简单dp我是sb。中午发现Eafoo也套了容斥。
首先我们总数就是 \(\Large(2^{n-1})^{\underline {n}}\) （下划线不知道为什么放最大就能显示了），然后设 \(dp[i]\) 为 \(i\) 位异或和为 \(0\) 的。
然后我们考虑转移，有两种情况不合法：

1. 前 \(i-1\) 个异或和为 \(0\) 。
2. 前 \(i-2\) 个异或和为 \(0\) ，那么最后两个一定重复。这样只需要在前 \(i-1\) 个中选一个重复就行了，然后最后一个随便选（除了前面选过的 \(i-2\) 种）。
   于是转移方程就很显然。

/*春物 润了
考场上搞了容斥套容斥套容斥然后摆烂*/
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int mod=1000000007;
int n,ans,dp[10000010],p[10000010];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    int ret=qpow(2,n)-1;p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=1ll*p[i-1]*ret%mod,ret--;
    }
    dp[1]=dp[2]=0;ret=qpow(2,n);
    for(int i=3;i<=n;i++){
        dp[i]=(p[i-1]-dp[i-1]-1ll*(i-1)*(ret-i+1)%mod*dp[i-2]%mod+mod)%mod;
    }
    printf("%d\n",(p[n]-dp[n]+mod)%mod);
    return 0;
}

T4

考场上模出性质发现不会写而且饿了遂摆烂。
最大团板子，使用Bron-Kerbosch算法。

/*樱花庄 润了
麻了考场上推出来性质了然后不会找团*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int n,m,x,ans,a[50][50],v[50],cnt[50];
bool dfs(int x,int size){
    for(int i=x+1;i<=n;i++){
        if(cnt[i]+size<=ans)return false;
        if(!a[x][i])continue;
        int j;
        for(j=1;j<size;j++){
            if(!a[i][v[j]])break;
        }
        if(j==size){
            v[size]=i;
            if(dfs(i,size+1))return true;
        }
    }
    if(size>ans+1){
        ans=size-1;
        return true;
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        a[u][v]=a[v][u]=1;
    }
    ans=-1;
    for(int i=n;i>=1;i--){
        v[1]=i;
        dfs(i,2);
        cnt[i]=ans;
    }
    printf("%.6lf",0.5*x*(1.0*x/ans*(ans-1)));
    return 0;
}

总结：wssb。