首页 > 其他分享 >CSP模拟15

CSP模拟15

时间：2023-08-07 21:58:27浏览次数：51  
标签：15 int long 进位 ans include CSP 模拟 Mod

四道 CF。

虽然我没打过 CF，但我每天都在打 CF。

A. [CF1850G] The Morning Star

首先，对于两个互相满足条件的点，其方案数为 \(2\)。

那么对于 \(n\) 个互相满足条件的点，他们对答案的贡献是

\[2 \dbinom{n}{2}=n(n-1) \]

然后就是分类讨论四种相互满足条件的情况。

  1. 横坐标相同的点相互满足条件。
  2. 纵坐标相同的点相互满足条件。
  3. 横坐标与纵坐标之和相同的点相互满足条件（左上到右下）。
  4. 横坐标与纵坐标之差相同的点相互满足条件（左下到右上）。

我们可以用 map 维护相互满足条件的点的数量，由于我们 CF 的优秀赛制，unordered_map 被 hack 了，对着模数卡真哈人。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 200500;

int n,x,y;

long long ans = 0;

map<long long,long long> a1,a2,a3,a4;

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1;i <= n; i++) {
            cin >> x >> y;
            a1[x] ++;
            a2[y] ++;
            a3[x - y] ++;
            a4[x + y] ++;
        }

        for(auto i : a1)
            ans += i.second * (i.second - 1);
        for(auto i : a2)
            ans += i.second * (i.second - 1);
        for(auto i : a3)
            ans += i.second * (i.second - 1);
        for(auto i : a4)
            ans += i.second * (i.second - 1);

        cout << ans << "\n";
        a1.clear();
        a2.clear();
        a3.clear();
        a4.clear();
        ans = 0;
    }
    return 0;
}

B. [CF1852A] Ntarsis' Set

考虑二分答案。

对于一个数 \(x\)，假设删除了 \(y\) 个小于 \(x\) 的数，那么数 \(x\) 的新排名变成 \(x-y\)。

那么我们就枚举 \(k\) 次。对于每一次操作，我们找到最后一个小于等于 \(x\) 的数 \(a_i\) 的下标 \(y\)，那么 \(x\) 的新排名就变成了 \(x-y\)。

对于一个数 \(x\)，如果它是答案，那么所有小于 \(x\) 的数的排名都会被修改成 \(0\)；所有大于 \(x\) 的数的新排名都大于等于 \(1\)。

对于二分的上届，就算 \(a_1,a_2,\dots,a_n\) 是 \(1 \sim n\) 的排列，那么最多也就删掉前面 \(n \times k\) 个数，所以答案一定小于等于 \(n \times k + 1\)。

对于 \(ans\) 的初始值，我们直接设成 \(1\)，这样相当于起到了特判的作用。

Code

#include <bits/stdc++.h>
#define ll long long
#define int long long

using namespace std;

int N,K;
int a[200500],ans;

bool Check(ll x) {
    int k = K;
    while(k--) {
        int cur = lower_bound(a + 1,a + N + 1,x) - a;
        if(a[cur] > x || cur > N)
            cur --;
        // ↑ 找到 a 里最后一个小于等于 x 的下标 cur 
        x -= cur;// 删了数后它的新排名 
        if(x <= 0)
            return 0;
    }
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    int T = 1;
    while(T--) {
        cin >> N >> K;
        for(int i = 1;i <= N; i++) 
            cin >> a[i];

        int l = 1,r = N * K + 1,ans = 1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(Check(mid)) {
                ans = mid;
                r = mid - 1;
            }
            else 
                l = mid + 1;
        }
        cout << ans << "\n";
        for(int i = 1;i <= N; i++)
            a[i] = 0;
    }
    
    return 0;
}

C. [CF932E] Team Work

\[\begin{align} F(n,k) &=\sum\limits_{i=1}^n{n\choose i}i^k\tag{1}\\ &=n\sum\limits_{i=1}^n{n-1\choose i-1}i^{k-1} \tag{2}\\ &=n\left(\sum\limits_{i=1}^n{n\choose i}i^{k-1}-\sum\limits_{i=1}^n{n-1\choose i}i^{k-1}\right) \tag{3}\\ &=n(F(n,k-1)-F(n-1,k-1)) \tag{4} \end{align} \]

对于 \((1) \Rightarrow (2)\)，考虑直接提出一个 \(\dfrac{n}{i}\)。

对于 \((2) \Rightarrow (3)\)，考虑帕斯卡公式，移项

\[\dbinom{n}{i}=\dbinom{n-1}{i}+\dbinom{n-1}{i-1} \]

最后得到一个递归式。

我们发现在计算 \(F(n,k)\) 的过程中，有许多部分是被重复计算的，很明显会 TLE。

由于在递归式中，\(n\) 的范围是 \(n-k \sim n\)，所以我们可以记忆化，把时间复杂度降低到 \(\mathcal{O}(k^2)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

#define int long long

const int Mod = 1e9 + 7;

int N,K;

long long fac[2005000];

long long Pow(long long a ,long long b) {
    b = (b + Mod - 1) % (Mod - 1);
    long long res = 1 ;
    long long base = a;
    while(b > 0) {
   	    if(b & 1)
   		    res = (res * base) % Mod;

   	    base = (base * base) % Mod;
   	    b >>= 1;
   }
   return res;
}

long long Inv(long long x) {
    return Pow(x % Mod,Mod - 2) % Mod;
}

long long C(long long n,long long m) {
    if(m > n)
		return 0;
    
	return fac[n] * Inv((fac[m] * fac[n - m])) % Mod;
}

long long Lucas(long long n,long long m) {
    if(m == 0)
		return 1;
    return (Lucas(n / Mod,m / Mod) * C(n % Mod,m % Mod)) % Mod;
}

void Work0() {
    fac[0] = 1;
    for(int i = 1;i <= N; i++)
        fac[i] = fac[i - 1] * i % Mod;
    
    long long ans = 0,tmp;
    for(int i = 1;i <= N; i++) {
        tmp =  Lucas(N,i) * Pow(i,K) % Mod;
        ans = (ans + tmp) % Mod;
    }
    cout << ans;
    return ;
}

int vis[5100][5100];

int F(int n,int k) {
    if(vis[k][n - (N - K - 2)] != -1)
        return vis[k][n - (N - K - 2)];

    if(k == 0)
        return Pow(2,n) - 1;

    return vis[k][n - (N - K - 2)] = (n * (F(n,k - 1) - F(n - 1,k - 1)) % Mod + Mod) % Mod;
}

signed main() {
    cin >> N >> K;
    if(N <= 200500) {
        Work0();
        return 0;
    }
    memset(vis,255,sizeof(vis));

    cout << (F(N,K) + Mod) % Mod;
    return 0;
}

D. [CF1188D] Make Equal

刚开始读错题意了，还以为是直接求 popcount，显然 T4 不可能这么简单。

然后打了一个假的暴力，只有 \(\text{20 \ pts}\)。

谁能教我 40 分暴力怎么打？？？

啊哦，原来是枚举太多导致 TLE 了，好，又多挂 20 分！

题目大意

给出 \(n\) 个数字 \(a_1,a_2,\dots,a_n\)，每次操作可以给其中一个数加上 \(2\) 的非负整数次幂。求最少的操作次数，使得这 \(n\) 个数相等。

思路

记 \(b_i = \max\limits_{1 \leq k \leq n}{a_k} - a_i\)，这道题的目的是求一个值 \(x\) 使得

\[\sum_{i=1}^n \operatorname{popcount}(x + b_i) \]

最小，其中 \(\operatorname{popcount}(x)\) 表示数 \(x\) 在二进制下 \(1\) 的个数。

考虑 DP。

考虑二进制下 \(x + b_i\) 的第 \(k\) 位，发现这一位的决策与下面这些有关：

  • \(x\) 的第 \(k\) 位是否填 \(1\)；
  • \(b_i\) 的第 \(k\) 位是否为 \(1\)；
  • 第 \(k-1\) 位是否进位。

其中，\(x\) 是我们要决策的，\(b_i\) 是已知的，考虑第三种情况。

如果直接进行记录的话很明显要爆炸。但我们发现，第 \(k-1\) 位的进位情况与 \(b_i \mod 2^k\) 有关。

\(b_i \mod 2^k\) 的值越大，就更加容易进位，如果将 \(b_i\) 按照 \(b_i \mod 2^k\) 的值从大到小排序，能产生进位的数一定是 \(b_i\) 的一段前缀。

设 \(dp_{i,j}\) 表示有 \(j\) 个数进位到第 \(i\) 位的最优解（最小操作次数）。

考虑转移，对于第 \(i\) 位，我们要考虑 \(b_k\) 在二进制下第 \(i\) 位是否为 \(1\) 和在第 \(i-1\) 位进位的数的个数。

钦定第 \(i - 1\) 位有 \(j\) 个数进位，记 \(tot\) 为当前这一位为 \(1\) 的 \(b_k\) 的个数；\(cnt\) 为前 \(j\) 个数中当前这一位为 \(1\) 的数的个数。

考虑下面四种情况，表示满足前面两句条件的数有多少个：

  1. \(x+b_k\) 在第 \(i-1\) 位没有进位，\(b_k\) 的第 \(i\) 位为 \(1\)，有 \(tot-cnt\) 个；
  2. \(x+b_k\) 在第 \(i-1\) 位没有进位，\(b_k\) 的第 \(i\) 位为 \(0\)，有 \(n-j-(tot-cnt)\) 个；
  3. \(x+b_k\) 在第 \(i-1\) 位有进位，\(b_k\) 的第 \(i\) 位为 \(1\)，有 \(cnt\) 个；
  4. \(x+b_k\) 在第 \(i-1\) 位有进位，\(b_k\) 的第 \(i\) 位为 \(0\)，有 \(j-cnt\) 个。

那么考虑第 \(i\) 位的决策：

  • 如果 \(x\) 取 \(0\)，那么第 \(3\) 种产生进位，第 \(1,4\) 种的 \(x+b_k\) 的第 \(i\) 位为 \(1\)，产生贡献；
  • 如果 \(x\) 取 \(1\)，那么第 \(1,3,4\) 种产生进位，第 \(2,3\) 种的 \(x+b_k\) 的第 \(i\) 位为 \(1\)，产生贡献；

然后就可以进行转移。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

const int N = 200500;
#define int long long

int n,k;

int a[N],b[N],id[N];

int dp[63][N],num[3][N];

bool cmp(int x,int y);
void Ready();
void Clac(int i,int x,int y);

signed main() {
    cin >> n;
    for(int i = 1;i <= n; i++)
        cin >> a[i];
    
    Ready();

    for(k = 0;k <= 60; k++) {// 二进制下每一位
        sort(id + 1,id + n + 1,cmp);

        for(int i = 1;i <= n; i++) {
            num[0][i] = num[0][i - 1];
            num[1][i] = num[1][i - 1];
            num[b[id[i]] >> k & 1][i] ++;
            // 第 k 位为 1 或 0 的数的个数 
        }

        for(int i = 0,x,y;i <= n; i++) {
            x = num[0][n] + num[1][n - i] - num[0][n - i];
            y = num[1][n] - num[1][n - i];
            Clac(i,x,y);

            x = num[1][n] + num[0][n - i] - num[1][n - i];
            y = n - num[0][n - i];
            Clac(i,x,y);
        }
    }
    cout << dp[61][0];
    return 0;
}

bool cmp(int x,int y) {
    if((b[x] & ((1ll << k) - 1)) < (b[y] & ((1ll << k) - 1)))
        return 1;
    return 0;
}

void Ready() {
    sort(a + 1,a + n + 1);
    for(int i = 1;i <= n; i++) {
        b[i] = a[n] - a[i];
        id[i] = i;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;

    return ;
}

void Clac(int i,int x,int y) {
    dp[k + 1][y] = min(dp[k + 1][y],dp[k][i] + x);
    return ;
}

标签：15,int,long,进位,ans,include,CSP,模拟,Mod
From： https://www.cnblogs.com/baijian0212/p/csp-15.html

相关文章

  • 2023.8.7 模拟赛
    A有一个01串，只有一位是\(1\)，你每次可以翻转一个长为\(k\)的串，求出使得每个位置为\(1\)最少翻转多少次。其中有一些位是存在\(1\)的。\(n10^5\)考虑求出一个点能翻转一次到哪些点，只要不碰到边界即可。考虑线段树优化建图，建立奇偶两颗线段树。然后deque优化BFS......
  • 「赛后总结」暑假 CSP 模拟赛系列 2（8.1~8.3）
    「赛后总结」暑假CSP模拟赛系列2（8.1~8.3）点击查看目录目录「赛后总结」暑假CSP模拟赛系列2（8.1~8.3）20230801（letitdownround）T2神（eldenring）T4动（genshin）20230802（Max_QAQround2）T1随T3AT4C20230803（zero4338round）T2sT3pT4m20230801（letitdownround）蚌。整活大......
  • CSP-J1 2022 讲解
    各题考察知识点单选题面向对象/面向过程（编程思想）栈（根据入栈序列得到出栈序列）int类型指针数组和链表的区别栈和队列（栈先进后出，队列先进先出）中缀表达式转前缀表达式哈夫曼树/哈夫曼编码完全二叉树编码规律有向连通图中边的个数bfs/dfs，栈和队列的应用双向循环链......
  • CSP模拟15
    TheMorningStar统计$x,y,x-y,x+y$开$longlong$Ntarsis'Set考场降智删除数实质是降低排名.显然答案有单调性,直接二分答案.每次减小排名.判断是否合法.Code#include<cstdio>#defineintlonglongusingnamespacestd;constintN=2e5+5;inlineintrea......
  • CSP-J/S第一轮初赛 ~持续更新~
    CSP-J/S初赛2022更新的初赛知识汇总基础算法链表插入删除数据，操作数据O（1），遍历是O(n),可以进行动态调整。指针指向的是上下节点，链表储存数据下一个节点上一个节点。动态调整：插入一定量的节点，进行调整。插入节点：考虑信息覆盖（这些信息后面是否会再被用到）。寻找和读取比较慢......
  • CSP模拟15
    CSP模拟15T1CF1850GTheMorningStar水题但是考场写挂了直接写阶乘会\(RE\)（这里\(A\)阶乘可以优化成两个数相乘）可以分解为4种不同斜率的直线用\(map\)存（点击查看代码#include<iostream>#include<cstdio>#include<map>#include<cstring>usingnamespacestd;#de......
  • 2023.8 模拟赛日志
    2023暑假集训ab班day1127round。预期：\(0+25+0=25\)实际：\(80+20+0=100\)题目：23ab-day1划（待写）不会做，搞了很久最后逐一假掉。竟然有分。题解是一些恶心的区间分类，比较简单，可惜了。好像有很多做法23ab-day1Heinrich树论科技，跳过。写了暴力换根。23ab-day1朝花夕拾......
  • 【考后总结】8 月 CSP-S 模拟赛 2
    8.7CSP模拟15只因你太美-蔡徐坤>只因你太美baby只因你太美baby>>只因你实在是太美baby只因你太美baby>>迎面走来的你让我如此蠢蠢欲动>>这种感觉我从未有>>CauseIgotacrushonyouwhoyou>>你是我的我是你的谁>>再多一眼看一眼就会爆......
  • Cilium系列-15-7层网络CiliumNetworkPolicy简介
    系列文章Cilium系列文章前言今天我们进入Cilium安全相关主题,介绍CiliumNetworkPolicies相比于Kubernetes网络策略最大的不同:7层网络策略能力.CiliumNetworkPolicy7层能力CiliumNetworkPolicy与标准NetworkPolicy的最大区别之一是支持L7协议感知规则。在......
  • ThinkPad P15vGen2 拆解评析
    ThinkPadP15vGen2拆解评析夜之子  5人赞同了该文章准备工具：3.0规格十字螺丝刀、塑料撬棒。1.用螺丝刀拧下后盖全部螺丝，从CD面接缝处用撬棒划开即可打开后盖。注：后盖螺丝均为防脱设计，拧松即可。2.内部全貌。3.内存、硬盘对应位置均有黑色麦拉......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99