刷atcoder

刷题 atcoder

难度评价规则：颜色+分数，分数最高10

例如：黄5表示中位黄题

评分为主观，不保证合理

难度不一定递增，可能有水题

abc350d

发现一个连通块最后一定可以补成完全图，于是维护连通块即可

线性复杂度，直接跑染色就行

难度评价：橙8～黄1

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m;
vector<int> e[N];
int col[N],siz[N];
int tot;
void dfs(int now){
    if(col[now]) return;
    col[now]=tot;
    for(int v:e[now]){
        dfs(v);
    }
}
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    for(int i=1;i<=n;i++) if(!col[i]) tot++,dfs(i);
    for(int i=1;i<=n;i++) siz[col[i]]++;
    for(int i=1;i<=tot;i++) ans+=(siz[i]*(siz[i]-1))/2;
    ans-=m;
    cout<<ans<<"\n";
}

ABC350E

看到这个概率，意识到是期望

设 $dp_i$ 为把 $i$ 变成 $0$ 的 期望 最小花费

然后我们可以知道第二种操作 $dp_i=y+\dfrac{1}{6}\sum\limits_{j=1}^{6} dp_{i/j}$

移项合并可得 $dp_i=\dfrac{6}{5}y+\dfrac{1}{5}\sum\limits_{j=2}^{6}dp_{i/j}$

所以总的dp式子就是 $dp_n=\min(x+dp_{n/a},\dfrac{6}{5}y+\dfrac{1}{5}\sum\limits_{j=2}^{6}dp_{n /j})$

记忆化搜索即可

评分：绿1

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,double> dp;
int n,a,x,y;
double dfs(int now){
    if(now==0) return 0;
    if(dp[now]) return dp[now];
    double sum1,sum2=0;
    sum1=x+dfs(now/a);
    for(int i=2;i<=6;i++){
        sum2+=dfs(now/i);
    }
    sum2+=6.0*y;
    sum2/=5;
    return (dp[now]=min(sum1,sum2));
}
signed main(){
    cin>>n>>a>>x>>y;
    printf("%.15lf\n",dfs(n));
}

MAD TEAM

二分+枚举状态压缩($O(n^2 2^5\log A)$)/二分+状压dp($O(n2^5 \log A)$)

此处选择带个方的做法，好实现

二分不多说了，记 $S$ 作为一个二进制数，第 $i$ 位表示 $i$ 能否满足

用 $cnt_S$ 表示刚好状态为 $cnt_S$ 的数有几个，然后对 $cnt$ 处理一下可得出至少为 $S$ （也就是可以多满足一点点）的有几个

暴力枚举加判断即可

评分：绿3

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3005;
int n;
int a[N][6];
int ton[35];
int sum[35];
bool check(int x){
    memset(ton,0,sizeof ton);
    memset(sum,0,sizeof sum);
    for(int i=1;i<=n;i++){
        int tik=0;
        for(int j=1;j<=5;j++){
            tik<<=1;
            if(a[i][j]>=x) tik++;
        }
        ton[tik]++;
    }
    for(int S=0;S<(1<<5);S++){
        for(int i=S;i;i=(i-1)&S){
            sum[i]+=ton[S];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int tik=0,ti=0,tj=0;
            for(int k=1;k<=5;k++){
                tik<<=1;ti<<=1;tj<<=1;
                if(a[i][k]<x and a[j][k]<x) tik++;
                if(a[i][k]>=x) ti++;
                if(a[i][k]>=x) tj++;
            }
            int nd=0;
            if(ti&tik==tik) nd++;
            if(tj&tik==tik) nd++;
            if(sum[tik]>nd or !tik) return 1;
        }
    }
    return 0;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i][3]>>a[i][4]>>a[i][3]>>a[i][4]>>a[i][5];
    int l=1,r=1e9,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans<<'\n';
}

ARC124B

就想玩玩arc结果开门水题

还是写一下吧

显然取值的范围上界是 $O(n)$ 级别的，就是用 $a_1\oplus b_k$ 的不同数字

然后枚答案，如果枚举到 $x$，同时 $x$ 满足 $a_i \oplus x$ 产生的数组排序后就是 $b$ ，那么 $x$ 可以是答案

复杂度 $O(n^2\log n)$

评分：黄6

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int n;
int a[N],b[N];
set<int> may;
set<int> ans;
int de[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) may.insert(a[1]^b[i]);
    for(int x:may){
        for(int i=1;i<=n;i++){
            de[i]=(a[i]^x);
        }
        sort(de+1,de+n+1);
        bool flg=1;
        for(int i=1;i<=n;i++){
            if(de[i]!=b[i]){flg=0;break;} 
        }
        if(flg) ans.insert(x);
    }
    cout<<ans.size()<<"\n";
    for(int x:ans){
        cout<<x<<"\n";
    }
}