CF1740 Div.1+Div.2 做题记录

无心随笔 / 2023-05-11 / 原文

A

CF题面

\(n\) 是素数，\(2\times n\) 不是素数，输出 \(n\) 即可。

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
void solve(){
    int n;
    read(n);
    write_endl(n);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

B

CF题面

周长可以平移，所以最小值为两边最小值之和加上剩下的边中的最大值的两倍。

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
struct node{
    int a,b;
}a[N];
int n;
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i].a),read(a[i].b);
        if(a[i].a>a[i].b){
            swap(a[i].a,a[i].b);
        }
    }
    int ans=0,mx=0;
    for(int i=1;i<=n;i++){
        ans+=a[i].a;
        mx=max(mx,a[i].b);
    }
    write_endl((ans+mx)*2);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

C

CF题面

先排序。首先 \(a_1\) 和 \(a_n\) 中必然有一个要被选，因为它选了必然不劣于让其它数被选，所以让其放在第三组。剩下两组中选择的数必然是排序后相邻的两个数，那么两组分别为前缀和后缀，则可以限定选到指定的相邻的两个数。在所有可能的答案中取最大值即可。

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,a[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=3;i<=n;i++){
        ans=max(ans,a[i]-a[1]+a[i]-a[i-1]);
    }
    for(int i=n-2;i;i--){
        ans=max(ans,a[n]-a[i]+a[i+1]-a[i]);
    }
    write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

D

CF题面

一个空白格子可以移到除了 \((1,1)\) 和 \((n,m)\) 以外的位置，所以只要有一个空白格子就可以从任何格子移到 \((n,m)\)。

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10;
int n,m,k,vis[N],a[N];
void solve(){
    read(n),read(m),read(k);
    for(int i=1;i<=k;i++){
        vis[i]=0;
        read(a[i]);
    }
    int pos=k,tot=0;
    for(int i=1;i<=k;i++){
        vis[a[i]]=1;
        tot++;
        if(pos==a[i]){
            while(vis[pos]){
                pos--;
                tot--;
            }
        }
        if(tot==n*m-3){
            puts("TIDAK");
            return;
        }
    }
    puts("YA");
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

E

CF题面

如果一个点有多个儿子被选入了最长不下降子序列，那么它及它的祖先都不会被选入。令 \(f_x\) 表示 \(x\) 号点被选入了最长不下降子序列后，子树答案最大值，显然这个值等于子树内最长链。令 \(g_x\) 表示 \(x\) 号不被选入后，子树答案最大值。\(g_x=\sum\limits_{y\in son_x}\max(f_y,g_y)\)。最后答案为 \(\max(f_1,g_1)\)。

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10;
int n,f[N],g[N];
vector<int>e[N];
void dfs(int u){
    f[u]=1;
    for(auto v:e[u]){
        dfs(v);
        f[u]=max(f[u],f[v]+1);
        g[u]+=max(f[v],g[v]);
    }
}
void solve(){
    read(n);
    for(int i=2;i<=n;i++){
        int fa;
        read(fa);
        e[fa].pb(i);
    }
    dfs(1);
    write_endl(max(f[1],g[1]));
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

F

CF题面

对于一个可重集 \(M\) 中任意的 \(S_1,S_2\) 两个集合，若 \(|S_1|>|S_2|\)，则 \(S_1\) 中必然存在一个 \(x\)，使得 \(x\) 可以被放到 \(s_2\) 中。所以将可重集 \(M,N\) 中的集合均按照集合大小从大到小排好序，若对于 \(\forall k\in[1,n],\sum\limits_{i=1}^k|M_i|\ge \sum\limits_{i=1}^kN_i\)，则若 \(M\) 能被组合出来，则 \(N\) 一定能被组合出来。那么知道 \(\sum\limits_{i=1}^k|M_i|\) 的最大值及取最大值的方案数即可。
非常显然的是 \(\sum\limits_{i=1}^k|M_i|\le \sum\limits_{i=1}^n\min(k,cnt_i)\)，且等号可以取到。其中 \(cnt_i\) 表示数字 \(i\) 的出现次数。
令 \(f_{i,j,k}\) 表示前 \(i\) 个集合大小不小于 \(k\)，大小之和为 \(j\) 的方案数。
\(f_{i,j,k}=f_{i,j,k+1}+[j>=k]\times f_{i-1,j-k,k}\)

点击查看代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2010,mod=998244353;
int n,cnt[N],a[N],s[N],f[2][N][N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        cnt[a[i]]++;
    }
    sort(cnt+1,cnt+n+1);
    for(int i=0;i<=n;i++){
        f[0][0][i]=1;
        for(int j=1;j<=n;j++){
            s[i]+=min(i,cnt[j]);
        }
    }
    int opt=0;
    for(int i=1;i<=n;i++){
        opt^=1;
        for(int j=0;j<=s[i];j++){
            f[opt][j][n/i+1]=0;
        }
        for(int k=n/i;k>=0;k--){
            for(int j=0;j<=s[i];j++){
                if(j>=k){
                    f[opt][j][k]=(f[opt][j][k+1]+f[opt^1][j-k][k])%mod;
                }
                else{
                    f[opt][j][k]=f[opt][j][k+1];
                }
            }
        }
    }
    write_endl(f[opt][n][0]);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}