首页 > 其他分享 >2023-05 多校联合训练 ZJNU站 热身赛

2023-05 多校联合训练 ZJNU站 热身赛

时间:2023-05-13 19:56:27浏览次数:57  
标签:std 盒子 05 int t2 多校 2023 const define

猫猫接币币

给定两个容量分别为ab的盒子,已知第i秒天上会掉下i个金币,你会从第1秒开始接金币,每秒钟你可以选择任意一个盒子接金币,但是不能不选,你必须使得两个盒子刚好装满,请问是否存在某个时刻,使得恰好装满两个盒子,输出一个仅由 AB 组成的字符串,第\(i\)位的字符即表示第\(i\)秒用哪个盒子去接金币。

如果存在多种接金币的方法,输出任意一种正确接法即可

题解:贪心

假设第\(n\)秒恰好装满两个盒子,容易发现:\(\sum\frac{n(1+n)}{2} = a+b\)

存在一种这样的贪心构造:

对于\(1,2,3...n\)中这\(n\)个数字,我们从大到小装入盒子,哪个盒子能装就装哪个盒子

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

void solve()
{
    int a, b;
    cin >> a >> b;
    int n = 0;
    bool flag = false;
    for (int i = 1; i <= 2000; ++i)
    {
        n += i;
        if (n == a + b)
        {
            flag = true;
            n = i;
            break;
        }
    }
    if (!flag)
    {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    string ans;
    for (int i = n; i >= 1; i--)
    {
        if (a >= i)
        {
            a -= i;
            ans = "A" + ans;
        }
        else if (b >= i)
        {
            b -= i;
            ans = "B" + ans;
        }
    }
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

关于我转生成为位运算大师但做的却是一道关于前缀和的题目这件事

你的朋友刚学了位运算,但并不是特别的精通,他知道你是位运算大师,于是拿着下面这段伪代码来问你:

Input N
T = 0
While True:
   X = N # (N - 1)
   If N == X:
       Break
   End If
   T = T + 1
   N = X
End While
Output T

他定义了三个函数 \(f(x),g(x),h(x)\)分别表示当上述伪代码中的 # 符号被替换为 &(按位与)、|(按位或)以及 ^(按位异或)这三种运算符之后,输入 \(x\) 所得到的结果。

他给了你一个 \(n\),请你帮助他分别求出这三个函数的前缀和

\[\sum_{x=1}^{n}f(x),\sum_{x=1}^{n}g(x),\sum_{x=1}^{n}h(x), \]

题解:思维

我们观察三个函数:

  1. 对于第一个函数手模后我们不难发现,每一次&操作都会减少一个最低位的1,所以\(f(x)\)的值为\(x\)在二进制表示下1的个数
  2. 对于第二个函数我们不难发现只有\(x\)偶数时,\(g(x)=1\),否则\(g(x)=0\)
  3. 对于第三个函数我们不难发现只有\(x\)偶数时,\(g(x)=2\),否则\(h(x)=1\),特殊的\(h(1)=0\)

那么我们只需要快速算出前缀和即可:

  1. 对于第一个函数的前缀和,我们不难发现每一位存在周期性,假设周期为\(p\),每个周期中1的个数为\(p/2\),所以我们只需要计算\(x\)已经经过了几个周期即可,最后\(x\)对\(p\)取模后,观察是否有没有漏算1
000000
000001
000010
000011    
000100
000101    
000110
000111    

我们不难发现规律,对于第一位二进制,周期为\(2\),对于第二位二进制,周期为\(2^2\).....以此类推

  1. 对于第二个函数的前缀和我们只需要算出\([1,x]\)中有几个偶数即可,显然偶数的个数为$\lfloor \frac{x}{2} \rfloor $

  2. 对于第三个函数的前缀和我们只需要算出\([1,x]\)中有几个偶数和几个奇数即可,注意\(h(1)=0\),所以奇数的个数需要减去一

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n;

void solve()
{
    cin >> n;
    int p = 2;
    int ans1 = 0;
    int m = n + 1;
    while (m / p)
    {
        int t = p / 2;
        ans1 += t * (m / p);
        int t2 = m % p;
        if (t2 > t)
            ans1 += t2 - t;
        p *= 2;
    }
    int t = p / 2;
    ans1 += t * (m / p);
    int t2 = m % p;
    if (t2 > t)
        ans1 += t2 - t;
    int ans2 = n / 2;
    int ans3 = 2 * (n / 2) + (n - n / 2 - 1);
    cout << ans1 << " " << ans2 << " " << ans3 << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

标签:std,盒子,05,int,t2,多校,2023,const,define
From: https://www.cnblogs.com/Zeoy-kkk/p/17398041.html

相关文章

  • 2023.5.13——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • 每日总结2023-05-13
    今天对多线程进行探索: 使用步骤:具体使用: //步骤1:创建线程类(继承自Thread类)classMyThreadextendsThread{//步骤2:复写run(),内容=定义线程行为@Overridepublicvoidrun(){...//定义的线程行为}}//步骤3:创建线程对象,即......
  • day72(2023.5.13)
    1.Servlet技术详解 2.创建第一个Servlet案例 3.Tomcat运行过程 4.Servlet的生命周期 5.Servlet处理请求的原理 6.Servlet的作用 7.在Idea中创建Web工程 在Idea创建Web工程添加servlet-api.jar 在Idea中配置To......
  • Burp Suite Professional / Community 2023.5 (macOS, Linux, Windows) - Web 应用安
    BurpSuiteProfessional/Community2023.5(macOS,Linux,Windows)-Web应用安全、测试和扫描BurpSuiteProfessional,Test,find,andexploitvulnerabilities.请访问原文链接:https://sysin.org/blog/burp-suite-pro-2023/,查看最新版。原创作品,转载请保留出处。作者......
  • SolidWorks软件2023中文版下载安装,SolidWorks特色功能使用介绍
    SolidWorks是一款功能强大的3DCAD软件,广泛用于机械设计、生产制造、建筑设计等领域。在这些领域,SolidWorks软件的独特功能,如先进的拓扑优化、高级可视化和实时模拟等,为用户提供了方便快捷、智能高效的设计体验。一、先进的拓扑优化SolidWorks软件提取:soruan.top/TPqqfb.SolidWorks......
  • 2023年5月12日记录
    冒泡排序 #include<iostream>usingnamespacestd;#defineN10intmain(){ inta[N]; inti,j,y,count=0,t; cout<<"请为数组元素赋初值"<<endl; for(i=0;i<=N;i++){ cin>>a[i]; } for(i=0;i<=N-1;i++){ for(j=0;j<=N-1;j++) if(a[j......
  • 2023.5.12——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • day71(2023.5.12)
    1.JavaEE简介 2.服务器 3.Tomcat的使用 4.Tomcat下载与安装 5.Tomcat目录结构与介绍 6.Tomcat启动与关闭输入后,小猫出来啦! 7.Tomcat配置文件介绍 8.解决控制台乱码以及修改Tomcat监听端口 9.配置TomcatManage......
  • MPU6050一些问题与解决方案
    第一次参加电赛,调mpu6050调得想死,记录一些问题等待日后查询。 一.输出一直是0.可能1:没有初始化成功,见二。可能2:输出时用的是整型格式而不是浮点数格式。。。可能3:AD0引脚接了高电平(或者低电平),就是地址不对。二.初始化不能成功。我是和......
  • 2023/5/12每日随笔
        今天,上午上了计算机网络,对于应用层进行了学习,介绍了域名系统,就是人为的标识对于ip地址的转化,紧接着就介绍了域名系统,对于域名系统进行查询的方法,后进行了概论论的学习,学了数理统计的几个分布,x2,t,f分布,下午在web上将对与学生管理系统的作业进行了书写,晚上出去了一趟,去了......