当前位置: 首页 > news >正文

【学习笔记】NOMURA Programming Competition 2020

C - Folia

不难想到自底向上确定树的形态。可能要多尝试一下

一开始想错了好几个地方,服了

假设某一层有XXX个节点,那么上一层可能有⌈X2⌉,⌈X2⌉+1,...,X\lceil\frac{X}{2}\rceil,\lceil\frac{X}{2}\rceil+1,...,X2X,2X+1,...,X个节点(不包括叶子节点),那么我们可以很容易的递推求出每一层的[li,ri][l_i,r_i][li,ri]表示这一层点数的取值范围。但是并不是每一层的rir_iri都是能取到的,因为ri≤2ir_i\le 2^iri2i,而且2i2^i2i比较大不太好处理。

基于上述两个理由,我们考虑自顶向下确定每一层点的取值,每一层贪心取最大点数即可。并且可以证明答案不会超过long long

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,a[100005];
ll l[100005],r[100005],res=1;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<=n;i++)cin>>a[i];if(n&&a[0]){cout<<-1;return 0;}l[n]=r[n]=a[n];for(int i=n-1;i>=0;i--){l[i]=a[i]+(l[i+1]+1)/2;r[i]=a[i]+r[i+1];}if(l[0]>1){cout<<-1;return 0;} ll X=1;for(int i=1;i<=n;i++){X=min(r[i],2*(X-a[i-1]));if(X<l[i]){cout<<-1;return 0;}res+=X;}cout<<res;
}

D - Urban Planning

对于给定的{pi}\{p_i\}{pi},贡献就是nnn减去连通块的个数。

笑死,然而还是不会做

注意到{pi}\{p_i\}{pi}对应导出的图是一个基环树森林,因此环的数目等于连通块的数目,要算所有情况下环数目的和,可以对于每个环单独考虑它出现次数的方案数。该死,为什么我这一步都没转化出来就像计数了啊

然后先考虑pi=−1p_i=-1pi=1的情形。不过这道题的突破口好像不在这里,因为随便用组合数算算没啥难度

还是要考虑题目给定的{pi}\{p_i\}{pi}长什么样子。奇怪啊,竟然要对这一点特别提出来考虑 我们发现,其给出的图一定是由若干内向基环树和内向树构成 刚开始把内向树想成链了,真是奇怪。假设有MMM个基环树,那么对答案造成的贡献是固定M(N−1)KM(N-1)^KM(N1)K;假设有K′K'K个内向树,那么只有根节点指向的边不是固定的,注意我们的目标还是数环。

为什么题解的式子这么简洁

定义环上的关键点为内向树的根节点以及pi=−1p_i=-1pi=1的那些点。记这些点为{ai}\{a_i\}{ai},子树大小为{bi}\{b_i\}{bi},那么方案数为(n−1)!(N−1)K−n∏bi(n-1)!(N-1)^{K-n}\prod b_{i}(n1)!(N1)Knbi,其中nnn表示环上的点数。不难证明这个计数方式不重不漏。

复杂度O(n2)O(n^2)O(n2)。代码非常简单,只需要一个简单的背包即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,m,K,fa[5005],p[5005],sz[5005],vs[5005];
ll fac[5005],F[5005],dp[5005],res;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){cin>>n;for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;fac[0]=F[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,F[i]=F[i-1]*(n-1)%mod;for(int i=1;i<=n;i++){cin>>p[i];K+=(p[i]==-1);if(~p[i]){int u=find(i),v=find(p[i]);if(u!=v){fa[u]=v,sz[v]+=sz[u];}else{vs[u]=1,m++;}}}dp[0]=1;for(int i=1;i<=n;i++){if(fa[i]==i){if(!vs[i]){res=(res+(sz[i]-1)*F[K-1])%mod;for(int j=n;j>=1;j--){dp[j]=(dp[j]+dp[j-1]*sz[i])%mod;}}else{res=(res+F[K])%mod;}}}for(int i=2;i<=K;i++){if(dp[i]){res=(res+fac[i-1]*dp[i]%mod*F[K-i])%mod;}}cout<<(F[K]*n-res+mod)%mod;
}

E - Binary Programming

姑且先把这套题做着吧,其他的题也没精力翻了

考虑倒着做,然后贪心 这个过程中可能会产生一堆假做法,但是不要慌张

我企图直接贪心,然而产生了错误,我是joker,这里数据删除了

从何贪起呢,我们观察到111一定是放在最后删的,事实上这也是一个非常显然的结论。另一个观察我没有注意到,那就是无论怎么操作,相邻两个111对答案的贡献都是一样的,因此我们考虑把相邻的111删去,这样就不存在相邻的111

然后就非常好搞了。设某个111前面000的个数为xxx,后面000的个数为yyy,那么对于奇数位上的111,贡献最大是⌊x2⌋+1+y\lfloor\frac{x}{2}\rfloor+1+y2x+1+y,对于偶数位上的111,贡献最大是⌊x−12⌋+1+y\lfloor\frac{x-1}{2}\rfloor+1+y2x1+1+y,显然这是可以取到的。

复杂度O(n)O(n)O(n)

做这种题比较爽的地方是只要有了正确的思路就很好搞,不然就会有很多种情况

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll res,zero,one,sum;
char s[200005];
int main(){scanf("%s",s+1),n=strlen(s+1);for(int i=1;i<=n;i++)sum+=(s[i]=='0');for(int i=1;i<=n;i++){if(s[i]=='0'){zero++;}else{one++;if(i+1<=n&&s[i+1]=='1'){res+=sum+1;one++;i++;}else{if(one&1)res+=zero/2+1+sum-zero;else res+=(zero-1)/2+1+sum-zero;}}}for(int i=1;i<=one;i++){res+=i/2;}cout<<res;
}

F - Sorting Game

该死,看到后面把前面的操作忘了,直接把Snuke\text{Snuke}Snuke的操作搞忘了,怪不得做不出来,先数据删除一波

一看到这个邻值交换就感到非常亲切,序列{ai}\{a_i\}{ai}合法等价于对于任意i<ji<ji<j,从高往低位找到第一个ci=1,cj=0c_i=1,c_j=0ci=1,cj=0时,其后面数位上的数完全相同。

嗯,读错题过后少考虑了一些因素,反而有帮助?

但是这个限制显然不能拿来直接计数。因为是平时训练题所以也懒得打表

到这里能发散的点还是挺多的,直接猜结论可能不一定会导向正确的方向

这题好做的原因可能还是在于没有什么特殊的限制,因此大胆猜测最终dpdpdp式子并不复杂

观察这个限制有点像数位dpdpdp。那么最基础的想法就是从高到低位考虑,打个表观察一下,于是不难发现这个想法的动机 然而这不是我最初的思路。。。 :对于i<ji<ji<jaia_iaiaja_jaj的最高位分别是111,000,那么其剩余的数位一定完全相同。首先我们要知道,对于不存在子串101010的情况,其方案数等价于dpn,m−1dp_{n,m-1}dpn,m1。其中dpn,mdp_{n,m}dpn,m表示nnn个数,mmm个数位的方案数。

另一方面,如果存在这样的i,ji,ji,j,我们猜测可以把i,ji,ji,j以及它之间的东西一起压缩掉变成同一个数,假设中间有KKK个位置最高位不确定那么剩下的方案数就是dpn−K−1,m−1dp_{n-K-1,m-1}dpnK1,m1 。中间KKK个数最高位可以任取,方案数2K2^K2K于是留给了我们一个艰巨的任务:证明这样的方案数是等价的。

至于这么压缩为什么是等价的,可以先写代码验证一番 ,或者更严谨地,因为后面数位的数都是复制粘贴所以可以只保留i,ji,ji,j两个数,因为不存在101010所以都只能比后j−1j-1j1位,于是就是等价的。

综上所述,dpn,m=(n+1)×dpn,m−1+∑k=0n−2dpn−k−1,m−1×2k×(n−k−1)dp_{n,m}=(n+1)\times dp_{n,m-1}+\sum_{k=0}^{n-2}dp_{n-k-1,m-1}\times 2^k\times (n-k-1)dpn,m=(n+1)×dpn,m1+k=0n2dpnk1,m1×2k×(nk1)

利用换元把式子写成dpn,m=(n+1)×dpn,m−1+∑k=1n−1dpk,m−1×2n−1−k×kdp_{n,m}=(n+1)\times dp_{n,m-1}+\sum_{k=1}^{n-1}dp_{k,m-1}\times 2^{n-1-k}\times kdpn,m=(n+1)×dpn,m1+k=1n1dpk,m1×2n1k×k 就可以O(1)O(1)O(1)转移了。

复杂度O(nm)O(nm)O(nm)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,m;
ll dp[5005][5005],sum[5005][5005],F[5005],F2[5005];
int main(){cin>>m>>n;F[0]=1;for(int i=1;i<=n;i++)F[i]=F[i-1]*2%mod;F2[0]=1;for(int i=1;i<=n;i++)F2[i]=F2[i-1]*(mod+1)/2%mod;for(int j=1;j<=m;j++){dp[0][j]=1;for(int i=1;i<=n;i++){if(j>1){dp[i][j]=((i+1)*dp[i][j-1]+sum[i-1][j-1]*F[i-1])%mod;}else{dp[i][j]=F[i];}sum[i][j]=(sum[i-1][j]+dp[i][j]*F2[i]%mod*i)%mod;}}cout<<dp[n][m];
}

相关文章:

【学习笔记】NOMURA Programming Competition 2020

C - Folia 不难想到自底向上确定树的形态。可能要多尝试一下 一开始想错了好几个地方&#xff0c;服了 假设某一层有XXX个节点&#xff0c;那么上一层可能有⌈X2⌉,⌈X2⌉1,...,X\lceil\frac{X}{2}\rceil,\lceil\frac{X}{2}\rceil1,...,X⌈2X​⌉,⌈2X​⌉1,...,X个节点&…...

iis下常用程序的伪静态规则列表(包括wordpress、thinkphp)

shopex discuz2.0 discuz2.5 discuz3.x 淘宝客 ecshop phpwind参照http://www.west.cn/faq/list.asp?unid797通过主机面板设置即可 wordpress设置&#xff1a; 第一步&#xff1a; 1.新建一个“chineseurl.php”文件&#xff1a;在里面写入以下代码上传到wordpress安装目录。…...

【Python语言基础】——Python Select From

Python语言基础——Python Select From 文章目录 Python语言基础——Python Select From一、Python Select From一、Python Select From 从表中选取 如需从 MySQL 中的表中进行选择,请使用 “SELECT” 语句: 实例 从表 “customers” 中选取所有记录,并显示结果: import m…...

数据增广真有那么神奇吗?

作者&#xff1a;皮皮雷 来源&#xff1a;投稿 编辑&#xff1a;学姐 论文题目 How Effective is Task-Agnostic Data Augmentation for Pretrained Transformers? 论文作者 S. Longpre, Y. Wang, and C. DuBois 论文发表于 2020 EMNLP findings 摘要 任务无关的数据增广…...

常用基础硬件知识 - 判断MOS管导通

目录1. 概述2. 判断MOS管的导通1. 概述 本文主要记录下基础的硬件知识&#xff0c;方便自己查阅。 2. 判断MOS管的导通 在产品硬件设计中&#xff0c;有时需要程序控制一些电源使能。 1.原理图已经标出了G极(gate)—栅极、S极(source)—源极、D极(drain)—漏极。 如果没有标…...

2023金三银四,测试人还能找到好工作吗?

嫌看文章麻烦的朋友点这里&#xff1a;2023最新软件测试行业变革细谈之我们该如何应对&#xff1f; 按照往年的惯例&#xff0c;春节后复工的 3 月、4 月是人员跳槽最频繁的时候&#xff0c;俗称“金三银四”。然而&#xff0c;市场大环境的影响&#xff0c;很多行业感受到了一…...

c++构造函数

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录一、构造函数1.构造函数的形式2.构造函数的调用时机3.委托构造函数4.复制构造函数二、析构函数本文仅为个人笔记 视频链接&#xff1a;https://www.bilibili.com/vid…...

redis 未授权访问漏洞

redis 未授权访问漏洞 目录 redis 未授权访问漏洞 漏洞描述 漏洞原因&#xff1a; 漏洞危害 漏洞复现&#xff1a; 漏洞复现 写webshell: 写计划任务&#xff1a;centos默认在/var/spool/cron 写ssh公钥实现ssh登录&#xff1a; 漏洞描述&#xff1a; Redis默认情况下…...

如何制作一个自定义的winpe?

winpe制作过程 获取相关资源 https://www.aliyundrive.com/s/MP58JbRsm76 文件存放位置 将压缩包存放在一个全英文目录下了,我这里选择了D:/winpe目录 解压文件 将三个压缩包进行解压到当前目录,如下图所示 创建一个mount目录,并在mount目录下分别创建boot和install目…...

QString转为2进制,8进制,10进制,16进制介绍

首先看段代码&#xff1a; bool ok false;QString ss "11";qDebug()<<"-----"<<ss.toInt(&ok,2)<<ss.toInt(&ok,10)<<ss.toInt(&ok,16)<<ss.toInt(&ok,8);结果&#xff1a; ----- 3 11 17 9 bool ok fal…...

2023-3-2-22:01随笔

好久没怎么更新技术分享博客了。去年从2022年1月3日到2023年1月份一直专注于ADAS的行车横向功能的研发与实车调试&#xff0c;2022年写了几篇项目经验的文章&#xff0c;像LQR算法&#xff08;虽然和同事&#xff08;志同道合&#xff0c;技术追求的民哥&#xff09;写出的工程…...

学习红客技术必备,手把手教你成为“安防第一人”

互联网时代已悄悄来临&#xff0c;作为新时代的人们&#xff0c;我们日常生活、工作、学习方面都需要借助互联网来完成&#xff0c;这样&#xff0c;又产生一种新的问题&#xff0c;那就是网络安全的问题&#xff0c;有时我们拼命加班好不容易完成的东西&#xff0c;在一夜之间…...

Git系列:常见指令辨析

Git系列&#xff1a;常见指令辨析指令辨析工作区、暂存区、版本库傻傻分不清楚&#xff1f;主干和分支的关系是什么&#xff1f;git fetch/merge/pull辨析日志查看时&#xff0c;git log与git reflog的区别是&#xff1f;git diff和status的区别是&#xff1f;相关资料本文小结…...

并发编程实战-构建自定义的同步工具

文章目录1.状态依赖性的管理1.1 示例&#xff1a;将前提条件的失败传递给调用者1.2 示例&#xff1a;通过轮询与休眠来实现简单的阻塞1.3 条件队列2.使用条件队列2.1 条件谓词2.2 过早唤醒2.3 丢失的信号2.4 通知2.5 示例&#xff1a;阀门类2.6 子类的安全问题2.7 入口协议与出…...

HBase集群部署

目录 一、前期准备 二、HBase下载 1. 查看HBase与hadoop版本对应关系 2. hbase的下载 3. 将hbase的tar包上传到linux 下 二、安装hbase 1. 解压 2. HBase的文件配置 主机名hadoop版本HBase版本hadoop安装路径Hbase安装路径HadoopMaster3.3.02.4.3/home/hadoop/softwareh…...

网络传输:linux下的网络请求和下载(ping wget curl)、端口

一、下载和网络请求 1.ping命令 可以通过ping命令&#xff0c;检查指定的网络服务器是否可连通状态 语法&#xff1a;ping [-c num] ip或主机名 选项&#xff1a; -c 检查的次数&#xff0c;若不使用-c&#xff0c;将无限次数持续检查参数&#xff1a;ip或主机名&#xff0c…...

阅读(1)-----六级

目录 1.单词不懂怎么办&#xff1f; 1.1构词法 1.2上下文 2.句子不通怎么办&#xff1f; 3.时间不够怎么办 &#xff1f; 4.题型 4.1细节题 问文章的细节 4.2主旨题(文章主旨和段落主旨) 4.3语义题 4.4观点题 &#xff08;一共三种&#xff0c;支持、反对和中立 &…...

【Python实战】快看:”又中奖了,中大奖了“周围的小伙伴都惊呆了~你还不麻溜滴~(代码版彩票小游戏上线啦)

导语 哈喽&#xff01;北鼻们&#xff0c;晚上好。 夕阳&#x1f307;的第一缕阳光送给小可爱们~每天都要加油鸭&#xff01; 所有文章完整的素材源码都在&#x1f447;&#x1f447; 粉丝白嫖源码福利&#xff0c;请移步至CSDN社区或文末公众hao即可免费。 彩票是一个恒古不…...

【python】控制台中文输出乱码解决方案

注&#xff1a;最后有面试挑战&#xff0c;看看自己掌握了吗 文章目录控制台原因解决方法方法一方法二方法三如果是os.system函数乱码控制台原因 一般的情况下&#xff0c;还是我们的源码文件的编码格式问题。我们一般是要把源码文件的编码格式改成utf-8就好了&#xff0c;但是…...

一名IC验证工程师的成长路径是怎么样的?来听听工程师的见解

IC验证这个岗位对于非科班的学生是比较友好的&#xff0c;因为验证需要具备的技能UVM&#xff0c;SV&#xff0c;C等&#xff0c;非科班和科班的差距不会拉开太大。因其岗位需求量巨大而格外受到了大家的青睐&#xff0c;甚至成为不少学生的转行首选。 验证对于IC的重要性 IC…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...