首页 > 其他分享 >CF *2600 DP选练

CF *2600 DP选练

时间：2023-09-11 09:23:51浏览次数：43  
标签：2600 int CF -- 枚举 题目 选练 dp mod

CF258D

题目描述：

有一个长度为 \(n\) 的排列，有 \(m\) 次操作，操作为交换两个数 \(a,b\) ，每次操作都有 \(50\%\) 的概率进行，求进行 \(m\) 次操作后期望逆序对个数

\(n,m\le1000\)

题目分析：

看到 \(n\) 和 \(m\) 都只有 \(1000\) ，猜到复杂度应该是 \(n^2\) 或者是 \(n^2logn\) 的。

一个很显然的想法是设 \(f[x][y]\) 表示 \(x\) 和 \(y\) 的两个数能带来的逆序对期望。

初始化很显然，\(f[x][y]=a[x]>a[y]\)。

可以发现每次交换两个点，那么 \(f[x][y]=f[y][x]=0.5\)。

  • \(f[t][x]=f[t][y]=0.5\times (f[t][x]+f[t][y])\)

  • \(f[x][t]=f[y][t]=0.5\times (f[x][t]+f[y][t])\)

答案显然是 \(\sum_{i=1}^{n}\sum_{j=i+1}^nf[i][j]\)。

代码：

int n,m,a[N];
db dp[N][N],ans=0;
 
signed main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            dp[i][j]=a[i]>a[j];
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        for (int j=1;j<=n;j++){
            dp[j][x]=dp[j][y]=0.5*(dp[j][x]+dp[j][y]);
            dp[x][j]=dp[y][j]=0.5*(dp[x][j]+dp[y][j]);
        }
        dp[x][y]=dp[y][x]=0.5;
    }
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            ans=ans+dp[i][j];
    printf("%.8lf",ans);
    return 0;
}

CF1185G2

题目描述：

你现在正在选择歌曲。现在有 \(n\) 首歌，每首歌都有一个时长 \(t\) 和编号 \(g\)（\(g\le 3\)）。

现在需要求出有多少种选出来若干首歌排成一排的方案，使得任意相邻的编号不同，且所有歌的时长恰好为 \(T\)。

题目分析：

第一想法是直接设 \(dp[i][j][t]\) 表示前 \(i\) 首歌，最后一首的编号为 \(j\)，时长为 \(t\) ，但是发现是序列，不需要顺序，并且枚举的复杂度炸天，所以这个 \(dp\) 假了。

换一种方向思考，可不可以设 \(dp[i][j][k][t]\) 表示 \(1\) 编号的个数为 \(i\) 个，\(2\) 编号的个数为 \(j\) 个，\(3\) 编号的个数为 \(k\) 个，\(t\) 为时长。

发现可以直接做，但是编号问题还是非常的难搞，我们可以分成两部分考虑：

  1. 设 \(f[i][j][k]\) 表示 \(i\) 个 \(1\) 标号，\(j\) 个 \(2\) 标号，\(k\) 个 \(3\) 标号任意排列，并且邻近的两个数的编号不同的方案数。

    设 \(s[i][j][k][0/1/2]\) 表示 \(i\) 个 \(1\) 标号，\(j\) 个 \(2\) 标号，\(k\) 个 \(3\) 标号，最后一个加入的数的编号为 \(0/1/2\) 的方案数，转移很简单不说。

    那么有 \(f[i][j][k]=s[i][j][k][0]+s[i][j][k][1]+s[i][j][k][2]\)。

  2. 发现四维的 \(dp\) 太大了会炸掉空间，考虑把他分成两部分做，第一部分为 \(a[i][t]\) 表示 \(i\) 个 \(1\) 编号，总时长为 \(t\) 的方案数。第二部分为 \(b[i][j][t]\) 表示 \(i\) 个 \(2\) 编号，\(j\) 个 \(3\) 编号，总时长为 \(t\) 的方案数。

    转移复杂度分别是 \(n^2T\) 和 \(n^3T\) 的，第一个转移是简单的，第二个可以分成两部分做，先做 \(2\) 标号，再做 \(3\) 标号，这样复杂度可以从 \(n^4T\) 转化成 \(n^3T\)。

统计答案把两者乘起来就好。

代码：

int n,T;
int t1[56][2507],t2[57][57][2507];
int s[56][56][56][4],f[56][56][56];
vector<int> a,b,c;
int A,B,C,fac[1007];
PII tmp[57];
int cnt;

void add(int &x,int y){
    x=(x+y)%mod;
}

void dp1(){
    s[1][0][0][0]=s[0][1][0][1]=s[0][0][1][2]=1;
    for(int i=0;i<=A;i++){
        for(int j=0;j<=B;j++){
            for(int k=0;k<=C;k++) {
                for(int d=0;d<3;d++){
                    if(int v=s[i][j][k][d]){
                        if(d) add(s[i+1][j][k][0],v);
                        if(d^1) add(s[i][j+1][k][1],v);
                        if(d^2) add(s[i][j][k+1][2],v);
                    }
                }
                add(f[i][j][k],s[i][j][k][1]);
                add(f[i][j][k],s[i][j][k][2]);
                add(f[i][j][k],s[i][j][k][0]);
                f[i][j][k]=f[i][j][k]*fac[i]%mod*fac[j]%mod*fac[k]%mod;
            }
        }
    }
}

void dp2(){
    t1[0][0]=1;
    for (int i=0;i<A;i++){
        for (int j=i;j>=0;j--){
            for (int t=T-a[i];t>=0;t--){
                add(t1[j+1][t+a[i]],t1[j][t]);
            }
        }
    }
    t2[0][0][0]=1;
    for (int i=0;i<B;i++){
        for (int j=i;j>=0;j--){
            for (int t=T-b[i];t>=0;t--){
                add(t2[j+1][0][t+b[i]],t2[j][0][t]);
            }
        }
    }
    for (int i=0;i<C;i++){
        for (int j=B;j>=0;j--){
            for (int k=i;k>=0;k--){
                for (int t=T-c[i];t>=0;t--){
                    add(t2[j][k+1][t+c[i]],t2[j][k][t]);
                }
            }
        }
    }
}

signed main(){
    scanf("%lld%lld",&n,&T);
    for (int i=1;i<=n;i++){
        int x=read(),y=read();
        if (y==1) a.p_b(x);
        else if (y==2) b.p_b(x);
        else c.p_b(x);
    }
    A=a.size();B=b.size();C=c.size();
    fac[0]=1;
    for (int i=1;i<=1000;i++) fac[i]=(fac[i-1]*i)%mod;
    dp1();dp2();
    int ans=0;
    for (int j=0;j<=B;j++){
        for (int k=0;k<=C;k++){
            for (int t=0;t<=T;t++){
                if (t2[j][k][t]){
                    for (int i=0;i<=A;i++){
                        if (t1[i][T-t]){
                            add(ans,t1[i][T-t]*t2[j][k][t]%mod*f[i][j][k]);
                        }
                    }
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

CF1223F

题目描述：

给一个序列进行栈操作，从左到右入栈，若当前入栈元素等于栈顶元素，则栈顶元素出栈，否则当前元素入栈。若进行操作后栈为空，说明这个序列可以被删除。

现在给你一个长度为 \(n\) 的序列 \(a\)，问 \(a\) 中有多少个子串可以被删除

题目分析：

第一思路是设 \(dp[l][r]\) 表示 \(l,r\) 这个区间是否是一个可删除区间，发现复杂度是 \(n^3\) ，寄。

第二思路是枚举右端点 \(r\)，找到左端点 \(l\) 可以在的位置，为了方便统计答案，设 \(dp[r]\) 表示以 \(r\) 为右端点的合法区间的个数。那么如果以 \(r\) 为右端点的最短合法区间的左端点为 \(l\) ，那么有 \(dp[r]=dp[l-1]+1\)。

如上图，可以发现左边的合法区间和右边的区间并且来仍然是合法区间，并且多了 \(l,r\) 这个合法区间，所以 \(dp[r]=dp[l-1]+1\)。

发现目前最麻烦的就是 \(l-1\) ，当然可以直接暴力枚举，找到 \(l\)，但是 \(n\le 1e5\) 所以很好卡。

想想有什么方法可以存出来第一个合法区间的值，想到用 \(map[i][a[i]]\) 表示以 \(i\) 为右端点，\(a[i]\) 最后出现的位置

那么 \(map[i-1][a[i]]\) 就是 \(l\)，并 \(map[i]=map[l-1]\) ，因为你发现这段区间合法之后，以后就再也不会用到这个区间了，相当于这个区间被抹除了。

代码：

int n,a[N],pre[N],dp[N];
map<int,int> mp[N];

void solve(){
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=n;i++){
        pre[i]=0;
        if (mp[i-1][a[i]]){
            int pos=mp[i-1][a[i]];
            pre[i]=pos;
            swap(mp[i],mp[pos-1]);
        }
        mp[i][a[i]]=i;
    }
    int ans=0;
    for (int i=1;i<=n;i++){
        if (!pre[i]) continue;
        dp[i]=dp[pre[i]-1]+1;
        ans+=dp[i];
    }
    printf("%lld\n",ans);
    for (int i=1;i<=n;i++) mp[i].clear(),dp[i]=0;
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}

CF382E

题目描述：

有一个 \(n\) 个节点的树，除了 \(1\) 号节点至多与另外 \(2\) 个节点连边，其余至多与 \(3\) 个结点连边（也就是二叉树）。

两个树是相同的，当且仅当每个节点的相连节点都相同。

求有多少种不同的这样的树，满足最大匹配是 \(k\)，答案对 \(1e9+7\) 取模。

题目分析：

对于最大匹配显然的一个贪心就是，从叶子节点开始匹配，如果该点和他的父亲都没有被匹配，那么选上就好了。

看起来就很难做，所以大概率是个 \(dp\)。

设 \(dp[i][j][0/1]\) 表示 \(i\) 个点的子树里有 \(j\) 个匹配，并且根节点是否被匹配上的方案数。

为了不记重复的答案，枚举是就保证 \(l_n\le r_n\)。

每次转移枚举一个子树的信息，另一个子树可以算出来，设左子树的大小为 \(l_n\)，右子树的大小为 \(r_n\)，那么转移的时候要乘上一个系数：\(\binom {l_n+r_n}{l_n}\times (l_n+r_n+1)\)，前面是因为要在这些数里面，找出 \(l_n\) 个数作为左子树，右边是因为要从 \(l_n+r_n+1\) 个数里面找出一个数作为根。

注意虽然保证了 \(l_n\le r_n\) ，但是还有 \(l_n=r_n\) 的情况，直接将答案除于二就好了。

发现枚举顺序比较难搞，所以直接 \(dfs+\) 记搜就好了。

int dp[55][55][2],n,k;
int fac[N],ifac[N];
bool vis[55][55][2];

int qmi(int a,int k){
    int res=1;
    for (;k;k>>=1,a=a*a%mod) if (k&1) res=res*a%mod;
    return res;
}

int C(int n,int m){
    if (n<m||n<0||m<0) return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int Dp(int n,int k,int p){
    if (vis[n][k][p]) return dp[n][k][p];
    if (n==0&&k==0&&p==1) return 1;
    else if (n==0) return 0;
    if (n==1&&k==0&&p==0) return 1;
    else if (n==1) return 0;
    FOR(l_n,0,n-1){
        int r_n=n-l_n-1;
        if (r_n<l_n) break;
        FOR(l_k,0,k){
            FOR(l_p,0,1){
                FOR(r_p,0,1){
                    if ((!l_p||!r_p)&&p){
                        int r_k=k-l_k-1;
                        int tmp=Dp(l_n,l_k,l_p)*Dp(r_n,r_k,r_p)%mod*C(l_n+r_n,l_n)%mod*(l_n+r_n+1)%mod;
                        if (l_n==r_n) tmp=tmp*qmi(2,mod-2)%mod;
                        dp[n][k][p]=(dp[n][k][p]+tmp)%mod;
                    }
                    else if (l_p&&r_p&&!p){
                        int r_k=k-l_k;
                        int tmp=Dp(l_n,l_k,l_p)*Dp(r_n,r_k,r_p)%mod*C(l_n+r_n,l_n)%mod*(l_n+r_n+1)%mod;
                        if (l_n==r_n) tmp=tmp*qmi(2,mod-2)%mod;
                        dp[n][k][p]=(dp[n][k][p]+tmp)%mod;
                    }
                }
            }
        }
    }
    vis[n][k][p]=1;
    return dp[n][k][p];
}

signed main(){
    scanf("%lld%lld",&n,&k);fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    ifac[n]=qmi(fac[n],mod-2);
    for (int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    printf("%lld\n",(Dp(n,k,0)+Dp(n,k,1)%mod)*qmi(n,mod-2)%mod);
    return 0;
}

CF1699E

题目描述：

给你个一个初始有 \(n\) 个元素的可重复集合 \(A\)，其中每个元素都在 \(1\) 到 \(m\) 之间。

每次操作可以将 \(A\) 中的一个元素（称之为 \(x\)）从 \(A\) 中删除，然后从 \(A\) 中加入两个元素 \(p,q\)，满足 \(p·q=x\) 且 \(p,q>1\)。

定义 \(A\) 的平衡值为 \(A\) 中的最大数减去最小数，求任意次操作后可以得到的最小平衡值。

题目分析：

上来想到设 \(dp[x][y]\) 表示 \(x\) 为 \(A\) 中最大，\(y\) 为 \(A\) 中最小，但是光存数组空间就炸了，所以说这种方法不可行。（说不定可以做，但是我不会优化/kk）

后来又想到了把他质因数分解之后可不可做，发现好像更麻烦了。

考虑既然是极差最小，可不可以枚举最小值，然后把所有数都分解为大于等于最小值的数，让分解后的数最小。

设 \(dp[i][j]\) 表示讲将数 \(i\) 分解成大于等于 \(j\) 的数，能分解出来的最小的数是什么。

转移的话就分类讨论一下：

  • 若 \(j\nmid i\)，则 \(dp[i][j+1]\to dp[i][j]\) （因为 \(j\) 这个数没法被分解出来，根据定义，要从 \(j+1\) 转移过来）
  • 若 \(j\mid i\)，则 \(dp[\frac{i}{j}][j]\to dp[i][j]\)

那么我们可以从大到小枚举最小值，去掉第二维，并且 \(j\nmid i\) 的转移也不需要了。

注意为了防止分解出来的数 \(\le i\)，枚举他的倍数的时候要从 \(i\times i\) 开始枚举。

还要保证 \(i\le \min{a_k}\)，不然 \(\min{a_k}\) 再怎么分解都比 \(i\) 小。

最后还需要计算最大值，直接暴力找最大值出现的地方复杂度就炸开了，但是可以发现一个性质：

当最小值变小的时候，最大值也同样会变小，所以可以搞一个双指针，做到 \(O(n)\)。

总复杂度为 \(O(nlogn)\)。

代码：

int n,m,a[N],tot[N],dp[N];
bool vis[N];
vector<int> G[N];

void Main(){
    scanf("%lld%lld",&n,&m);int mn=INF;
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        vis[a[i]]=1;
        mn=min(mn,a[i]);
    }
    for (int i=1;i<=m;i++){
        dp[i]=i;
        if (vis[i]) tot[dp[i]]++;
    }
    int ans=INF,mx=m;
    for (int i=m;i>=1;i--){
        for (int j=i*i;j<=m;j+=i){
            if (vis[j]) tot[dp[j]]--;
            dp[j]=min(dp[j],dp[j/i]);
            if (vis[j]) tot[dp[j]]++;
        }
        while(!tot[mx]) mx--;
        if (i<=mn) ans=min(ans,mx-i);
    }
    printf("%lld\n",ans);
    for (int i=1;i<=m;i++) vis[i]=tot[i]=0;
}
signed main(){
    int T=read();
    while(T--) Main();
    return 0;
}

CF1700F

题目描述：

给定两个 \(2\times n\) 的 \(01\) 矩阵 \(A\) 和 \(B\)，定义一次操作为交换 \(A\) 中两个相邻的值，输出使 \(A=B\) 的最小操作次数，如果无法使 \(A=B\)，那么输出 \(-1\)。

题目分析：

我们先考虑只有一行应该怎么做，是一个很典的问题，设 \(a_i\) 表示 \(A\) 的前缀和，\(b_i\) 表示 \(B\) 的前缀和，那么答案就是 \(\sum_{i=1}^{n}|a_i-b_i|\)，思考下这个过程是在干什么，

相当于枚举每个间隔，\(A\) 有多少个 \(1\)，\(B\) 有多少个 \(1\)，看看每个格子需要被经过多少次。

考虑两行怎么做，什么时候上下行会交换？

和上面一样分析，对于每个间隔，同样是两个绝度值相减，上下交换的时候，当且仅当 上一行为 01 下一行为 10 的情况，或者上一行为 10 下一行为 01 的情况，因为这样上下行交换一次，可以节约 \(2-1\) 的贡献。

注意交换完之后前缀的大小也要更新。

代码：

int n,a[3][N],b[3][N];
int A,B;

signed main(){
    scanf("%lld",&n);
    for (int i=1;i<=2;i++){
        for (int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
            A+=a[i][j];
        }
    }
    for (int i=1;i<=2;i++){
        for (int j=1;j<=n;j++){
            int x=read();
            b[i][j]=b[i][j-1]+x;B+=x;
        }
    }
    if (A!=B) return puts("-1"),0;
    int a1=0,a2=0,ans=0;
    for (int i=1;i<=n;i++){
        a1+=a[1][i],a2+=a[2][i];
        if (a1<b[1][i]&&a2>b[2][i]) a1++,a2--,ans++;
        if (a1>b[1][i]&&a2<b[2][i]) a1--,a2++,ans++;
        ans+=abs(a1-b[1][i])+abs(a2-b[2][i]);
    }
    printf("%lld\n",ans);
    return 0;
}

CF1111D

题目描述：

有一个恶棍的聚居地由几个排成一排的洞穴组成，每一个洞穴恰好住着一个恶棍。

每种聚居地的分配方案可以记作一个长为偶数的字符串，第\(i\)个字符代表第\(i\)个洞里的恶棍的类型。

如果一个聚居地的分配方案满足对于所有类型，该类型的所有恶棍都住在它的前一半或后一半，那么钢铁侠可以摧毁这个聚居地。

钢铁侠的助手贾维斯有不同寻常的能力。他可以交换任意两个洞里的野蛮人（即交换字符串中的任意两个字符）。并且，他可以交换任意次。

现在钢铁侠会问贾维斯\(q\)个问题。每个问题，他会给贾维斯两个数\(x\)和\(y\)。贾维斯要告诉钢铁侠，从当前的聚居地分配方案开始，他可以用他的能力创造多少种不同的方案，使得与原来住在第\(x\)个洞或第\(y\)个洞中的恶棍类型相同的所有恶棍都被分配到聚居地的同一半，同时满足钢铁侠可以摧毁这个聚居地。

如果某一个洞里的恶棍在两种方案中类型不同，则这两种方案是不同的。

题目分析：

考虑没有 \(x,y\) 的限制怎么做。

首先类型相同的要放在同一部分，所以每个类型相同的都要一起算贡献，因此下文我们用 \(c_i\) 表示 \(i\) 这个数出现过多少次方便统计贡献。

可以发现，我们想求的其实就选任意多个类型 \(c\)，让他们的和加起来为 \(n/2\)，假如选出来的集合是 \(S\)，那么贡献就是 \(\prod_{i\in S}\binom{n}{c_1}\binom{n-c_1}{c_2}\binom{n-c_1-c_2}{c_2}...\)，这样乘下去，化简一下就是 \(\frac{\frac{n}{2}!}{\prod_{i\in S}c_i!}\)，这只是算了左边的，那么右边的答案就是 \(\frac{\frac{n}{2}!}{\prod_{i\notin S}c_i!}\)，两者组合起立之后对答案的贡献就是：

\[\frac{(\frac{n}{2}!)^2}{\prod_{i}c_i} \]

所以我们本质上只需要用 \(dp\) 算出来 \(n/2\) 可以凑出来的方案数，乘上上面的系数，就可以得到答案了

现在我们考虑加上 \(x,y\) 的限制怎么做。

一个思路是用可删除 dp 做。

另一个思路是强制一个不选，另一个用前缀和后缀 dp 合并得到答案。

这些东西都可以预处理得到，最后答案 \(O(1)\) 输出即可。

代码：

这里给一份通俗易懂的，因为有 memset ，所以需要卡卡常数并且用 c++20 才能过。

char s[N];
int cnt[54],tmp=1,Q,n;
int fac[N],ifac[N];
int ans[54][54],f[54][N],g[54][N];

int qmi(int a,int k){
    int res=1;
    for (;k;k>>=1,a=a*a%mod) if (k&1) res=res*a%mod;
    return res;
}

int get(char s){
    if (s>='a'&&s<='z') return s-'a'+1;
    else return s-'A'+1+26;
}

void add(int &x,int y){
    x=(x+y)%mod;
}

signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);fac[0]=1;
    for (int i=1;i<=n;i++) cnt[get(s[i])]++;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    ifac[n]=qmi(fac[n],mod-2);
    for (int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    tmp=fac[n/2]*fac[n/2]%mod*2%mod;
    for (int i=1;i<=52;i++) tmp=tmp*ifac[cnt[i]]%mod;
    for (int i=1;i<=52;i++){
        memset(f,0,sizeof f);memset(g,0,sizeof g);
				f[0][0]=1;
        for (int j=0;j<52;j++){//前 j 个不算 i 的方案数
            for (int k=0;k<=n/2;k++){
                add(f[j+1][k],f[j][k]);
                if (j+1!=i&&cnt[j+1]) add(f[j+1][k+cnt[j+1]],f[j][k]);
            }
        }
				g[53][0]=1;
        for (int j=53;j>1;j--){//后 j 个不算 i 的方案数
            for (int k=0;k<=n/2;k++){
                add(g[j-1][k],g[j][k]);
                if (j-1!=i&&cnt[j-1]) add(g[j-1][k+cnt[j-1]],g[j][k]);
            }
        }
        for (int j=1;j<=52;j++){
            for (int k=0;k<=n/2;k++)
                add(ans[i][j],f[j-1][k]*g[j+1][n/2-k]%mod);
        }
    }
    for (int i=1;i<=52;i++){
        for (int j=1;j<=52;j++){
            ans[i][j]=ans[i][j]*tmp%mod;
        }
    }
    scanf("%lld",&Q);
    while(Q--){
        int x=read(),y=read();
        printf("%lld\n",ans[get(s[x])][get(s[y])]);
    }
    return 0;
}

可过的代码：Code。

标签：2600,int,CF,--,枚举,题目,选练,dp,mod
From： https://www.cnblogs.com/taozhiming/p/17686578.html

相关文章

  • sol. CF1680F Lenient Vertex Cover
    CF1680FLenientVertexCover下面用\(G\)表示一个环的边集，记作环\(G\)。我们令一个环\(G\)的价值为它经过的返祖边数量，记作\(Z(G)\)，下面给出核心结论：若存在一条边\(e_0\)经过所有\(Z(G)=1\)的奇环，且不经过任意一个\(Z(G)=1\)的偶环，那么\(e_0\)经过所有奇环......
  • 【题解】CF1830E Bully Sort
    考虑一次交换，我们发现，被选出来的\([i,j]\)的区间里\(p_i\)一定是最大的，\(p_j\)一定是最小的。然后我们会发现，我们原序列的逆序对数量会减少\(2(j-i)-1\)，而\(\sum|p_i-i|\)会减少\(2(j-i)\)那么答案就是原序列的两部分相减（神奇的性质又增加了！）。至于我们的后半部分显......
  • CF题解合集
    CF比赛题解合集\(\downarrow2023.09.04\)CF1952,CF19541952A.Ntarsis'Set有一个集合，初始状态里面有数字\(1\)、\(2\)、\(3\)、\(4\)、\(5\)、......、\(10^{1000}\)。现在给你一个长度为\(n\)数组\(a(1\leqa_i\leq10^9)\)，要进行\(k\)次操作，每次操作将当前......
  • cf edu 1700
    1430D.StringDeletion因为要最大话操作次数，所以我们每次删除的时候删除没有被删除最左侧连续相同长度大于等于2的部分。想清楚贪心策略后，用快慢指针就可以\(O(N)\)实现本体。#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn;strings;......
  • 【题解】CF1830B The BOSS Can Count Pairs
    你考虑，我们观察数据范围，发现可以是\(O(n\sqrtn)/O(n\logn)\)的，我们又看到乘法，便有几个大概的想法：数论分块\(O(\sqrtn)\)枚举其中一个乘数还有什么……（笔者学识浅陋，读者可以帮忙补充）我们可以找到两种\(O(n^2)\)做法：\(O(n^2)\)枚举数对\((i,j)\)然后进行判断。......
  • CF431B 题解
    思路分析答题思路一道纯暴力题！因为我们发现数据最大是\(5\)，而枚举全排列的时间复杂度为\(\mathcalO(n!)\)，对于这种极小的数据范围是丝毫不用顾虑的，因为我们只需要执行\(120\)次。如何快速求出一个数组的全排列？我们可以使用dfs，一层一层获取这个数组的全排列。但是STL......
  • CF387B 题解
    思路分析因为最终要使得\(a,b\)相同，所以我们应该希望让相同的数字尽量相同。所以，我们需要先对\(a\)和\(b\)进行排序，这样子就可以使用双指针的方法来维护最终值了。我们定义\(l\)指针指向\(a_l\)，\(r\)指针指向\(b_r\)。因为题目要求添加数字的次数最少，所以我们希望尽......
  • CF 1863 B
    B.SplitSort一开始想麻烦了，搞的没思路。这道题只需要遍历一遍数组并查询当前查询的数小\(1\)的数是否查询过，如果没有查询过就代表该数在这个数的后面，\(Ans\)就需要加一，最后输出就行。代码#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;typedeflonglon......
  • CF 1863 C
    C.MEXRepetition通过观察样例，直接猜结论可知，例如第二个样例\([0,1,3]\)后面其实有一个隐藏数字（2），所以完整的排列为\([0,1,3,2]\)。然后每一次操作都是把最后的一位数字移到整个排列的最前面，并把最后一位隐藏，所以直接取模就能求出最后的排列。代码#include<bits/stdc++.h......
  • CF758F
    题目链接description求满足长度为\(n\)，所有项都是\([l,r]\)间的正整数且公比为非1有理数的等比数列的数量。\(n\leq10^7,1\leql\leqr\leq10^7\)solution先不考虑公比不能为1的限制，对于\([l,r]\)间的正整数\(a,b\)，它们可以分别作为首项末项构成等比数列的一个必......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99