最新要闻
- 皮俑是什么做成的?皮俑为什么救吴邪?
- 擅长画虎的画家是?擅长画虎的十大画家
- 神奇宝贝的观看顺序是什么?神奇宝贝的大结局是什么?
- 用上半固态电池!赛力斯发布海外新车型SERES 5:订单超2万
- 国产骄傲!中国年度十大畅销新能源车型:外资仅有特斯拉上榜
- 每日播报!游客滑雪失控致女生被撞倒后抽搐 医生:危险数极高、常见骨折
- 拿老款忽悠当新款卖 女车主退车被日系4S店老板辱骂
- 风调雨顺的意思是什么?风调雨顺的下联是什么?
- 小年为什么分南方和北方?小年为什么吃麻糖?
- 女粉丝入手小米13 曾是十年资深果粉:被小米和雷军打动
- 当前滚动:二手车商要“气晕”!美国已有特斯拉新车价格低于二手车
- 低调的江西 盛产新能源富豪
- 2023央视春晚主持人阵容公布:首次迎来双90后
- 每日头条!衡山雾凇火了 多名游客滑冰下山很危险 景区调整开放时间
- 世界信息:把车变成船 比亚迪真会玩
- 天天报道:《中国奇谭》值得这么夸吗?
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
AtCoder Beginner Contest 285 解题报告
AtCoder Beginner Contest 285 解题报告
\(\text{DaiRuiChen007}\)
Contest Link
A. Edge Checker 2
假设 \(a\ge b\),当且仅当 \(\left\lfloor\dfrac a2\right\rfloor=b\) 时成立
(相关资料图)
时间复杂度 \(\Theta(1)\)
#includeusing namespace std;signed main() {int a,b;scanf("%d%d",&a,&b);if(a
B. Longest Uncommon Prefix
对于每个 \(i\) 从小到大不断增加 \(l\) 的值并判断即可
时间复杂度 \(\Theta(n^2)\)
#includeusing namespace std;const int MAXN=5001;char s[MAXN];signed main() {int n;scanf("%d%s",&n,s+1);for(int i=1;i
C. abc285_brutmhyhiizp
设 \(n=|S|\),字符串下标从 \(1\) 开始
从最高位开始考虑,假设最高位的字母是 \(\texttt C\),那么最高位填 \(\texttt A,\texttt B\) 或空的字符串一定更小,这样的字符串总数是 \(3\times 26^{n-1}\) 个,而最高位填 \(\texttt C\) 的串继续比较下一位即可
对于第二位、第三位……也类似统计即可
时间复杂度 \(\Theta(n)\)
#include#define int long longusing namespace std;const int MAXN=20;char s[MAXN];signed main() {int ans=0;scanf("%s",s+1);int n=strlen(s+1);for(int i=n,x=1;i>=1;--i,x*=26) ans+=(s[i]-"A"+1)*x;printf("%lld\n",ans);return 0;}
D. Change Usernames
连接所有的 \(S_i\to T_i\),发现得到的图上每个点的出入度 \(\le 1\),因此这张图上只可能有若干个环和若干条链
注意到环一定不行,而链一定可行,因此对原图做拓扑排序判环即可
时间复杂度 \(\Theta(n\log n)\),瓶颈在用 map
实现字符串哈希上
#includeusing namespace std;const int MAXN=2e5+1;map rec;vector G[MAXN];int siz=0,deg[MAXN];inline int id(string S) {if(rec.find(S)==rec.end()) rec[S]=++siz;return rec[S];}signed main() {int n;cin>>n;for(int i=1;i<=n;++i) {string u,v;cin>>u>>v;G[id(u)].push_back(id(v));++deg[id(v)];}queue q;for(int i=1;i<=siz;++i) if(!deg[i]) q.push(i);while(!q.empty()) {int p=q.front(); q.pop();for(int v:G[p]) {--deg[v];if(!deg[v]) q.push(v);}}for(int i=1;i<=siz;++i) {if(deg[i]>0) {puts("No");return 0;}}puts("Yes");return 0;}
E. Work or Rest
考虑 dp,用 \(dp_i\) 表示前 \(i\) 天在第 \(i\) 天休息时的最大价值,状态转移方程如下:
\[dp_i=\max_{j=1}^i\{dp_j+\operatorname{cost}(j,i)\}\]其中 \(\operatorname{cost}(l,r)\) 表示在 \(l,r\) 两天休息,中间不休息的情况下 \(l+1\sim r-1\) 获得的最大价值,通过前缀和优化可以在 \(\Theta(1)\) 的时间内计算
注意到第 \(n\) 天可能和下周的第一天结合产生贡献,为了解决这个问题,我们不妨把有休假的日子设为第 \(1\) 天,这样答案就是 \(dp_{n+1}\) 了
#include#define int long longusing namespace std;const int MAXN=5005;int a[MAXN],sum[MAXN],dp[MAXN];inline int cost(int l,int r) {int k=r-l-1;return sum[(k+1)/2]+sum[k/2];}signed main() {int n;scanf("%lld",&n);for(int i=1;i<=n;++i) {scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}memset(dp,-0x3f,sizeof(dp));dp[1]=0;for(int i=2;i<=n+1;++i) {for(int j=1;j
F. Substring of Sorted String
用 \(26\) 棵树状数组分别统计每个字母在特定区间中出现的次数
每次回答询问时先得到区间中的最小字母 \(lo\) 和最大字母 \(hi\),先判断字母 \(lo+1\sim hi-1\) 中的每个字母是不是都全部在 \([l,r]\) 中,然后简单模拟得到在每个字母对应的区间再判断这个区间是否全是该字母即可
时间复杂度 \(\Theta(|\Sigma|\times n\log n)\),\(\Sigma\) 为字符集
#includeusing namespace std;const int MAXN=1e5+1;int n,q;struct BitTree {int tree[MAXN];inline int lowbit(int x) { return x&-x; }inline void Modify(int x,int v) {for(;x<=n;x+=lowbit(x)) tree[x]+=v;}inline int q(int x) {int ret=0;for(;x;x-=lowbit(x)) ret+=tree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}}A[26];char str[MAXN];signed main() {scanf("%d%s%d",&n,str+1,&q);for(int i=1;i<=n;++i) {A[str[i]-"a"].Modify(i,1);}while(q--) {int op;scanf("%d",&op);if(op==1) {int x; char c;scanf("%d %c",&x,&c);A[str[x]-"a"].Modify(x,-1);str[x]=c;A[str[x]-"a"].Modify(x,1);} else {bool ok=true;int l,r;scanf("%d%d",&l,&r);int lo=26,hi=0;for(int i=0;i<26;++i) {if(A[i].Query(l,r)>0) {lo=min(lo,i),hi=max(hi,i);}}int x=l;for(int i=lo;i<=hi;++i) {int k=A[i].Query(l,r);if(lo
G. Tatami
用 \(1\times 2\) 骨牌覆盖网格图立刻想到黑白染色建立二分图,对于已经被 \(1\times 1\) 覆盖的方格先删除,我们只需要为所有 \(c_{i,j}=2\) 的位置找到匹配即可,剩下的位置用 \(1\times 1\) 填补
正解好像是网络流,这里只提供一种乱搞做法:
对于每个 \(c_{i,j}=2\) 的没有匹配的点,直接在二分图上暴力搜出增广路,如果搜不出来增广路则输出 No
时间复杂度 \(\Theta(h^2w^2)\)
注意到实际上很难卡满时间复杂度,因此注意一下实现的常数(例如用时间戳标记对此复用 vis[]
数组避免过多的 memset
操作)即可通过本题
#include using namespace std;const int MAXN=301,MAXV=1e5+1;vector G[MAXV];int tar[MAXV],vis[MAXV];inline bool dfs(int x,int t) {if(vis[x]==t) return false;vis[x]=t;for(int p:G[x]) {if(vis[p]==t) continue;vis[p]=t;if(tar[p]==-1||dfs(tar[p],t)) {tar[p]=x,tar[x]=p;return true;}}return false;}const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};char a[MAXN][MAXN];int id[MAXN][MAXN]; signed main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%s",a[i]+1);for(int i=1,cnt=0;i<=n;++i) {for(int j=1;j<=m;++j) {id[i][j]=++cnt;}}for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j) {if(a[i][j]=="1"||(i+j)%2==0) continue;for(int k:{0,1,2,3}) {int x=i+dx[k],y=j+dy[k];if(x<1||x>n||y<1||y>m) continue;if(a[x][y]=="1") continue;G[id[i][j]].push_back(id[x][y]);G[id[x][y]].push_back(id[i][j]);}}}memset(tar,-1,sizeof(tar));for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j){if(a[i][j]=="2") {if(tar[id[i][j]]!=-1) continue;if(!dfs(id[i][j],id[i][j])) {puts("No");return 0;}}}}puts("Yes");return 0;}
Ex. Avoid Square Number
显然立刻想到容斥,记 \(S_i\) 为至少存在 \(i\) 个平方数的方案数,那么得到:
\[\text{Answer}=\sum_{i=0}^n (-1)^i\times \binom ni\times S_i\]那么原问题转化为求 \(S_i\),\(S_i\) 可以转化为对于每个质因数 \(p_j\),求出把 \(E_j\) 拆成至少 \(i\) 个偶数的方案数的总乘积
考虑一次性处理出对于所有 \(E_j\) 的答案,对使用质因子数量建立生成函数,即 \(F_i(x)=\sum_{k=0}^\infty x^k\times f_{i,k}\),其中 \(f_{i,k}\) 为把 \(k\) 拆成至少 \(i\) 个偶数的方案数,那么我们知道 \(S_i=\prod_{j=1}^n f_{i,E_j}\)
而 \(F_i(x)\) 的值也是一个非常经典的问题,推导形过程如下:
\[\begin{aligned}F_i(x)&=(x^0+x^2+x^4+x^6+\cdots)^i\times(x^0+x^1+x^2+x^3+\cdots)^{n-i}\\[2ex]&=\left(\dfrac{1}{1-x^2}\right)^i\times\left(\dfrac 1{1-x}\right)^{n-i}\\&=\dfrac{1}{(1-x)^n\times (1+x)^i}\end{aligned}\]注意到我们可以每次暴力卷积计算出 \(F_0(x)\),而每次转移 \(F_{i}(x)\to F_{i+1}(x)\) 只需要乘上 \((1+x)^{-1}=1-x+x^2-x^3+x^4\cdots\) 就可以得到下一个 \(F\)
设 \(w=\max_{i}^k\{E_i\}\),那么所有的多项式都只需要在 \(\bmod x^{w+1}\) 意义下进行
注意到乘 \(\dfrac 1{1-x}\) 等价于做前缀和,乘 \(\dfrac 1{1+x}\) 等价于做前缀差(不等于差分,可以自己推导一下),因此多项式操作的复杂度都是 \(\Theta(w)\)
求出 \(F_0(x)\) 的复杂度是 \(\Theta(nw)\),而接下来依次计算 \(F_1(x)\sim F_n(x)\) 的总复杂度也是 \(\Theta(nw)\),每次通过 \(F_i(x)\) 求 \(S_i\) 的复杂度是 \(\Theta(k)\),执行 \(n\) 次,而容斥的复杂度是 \(\Theta(n)\)
综上,时间复杂度为 \(\Theta(nw+nk)\)
#include#define int long longusing namespace std;const int MAXN=1e4+1,MOD=1e9+7;int n,k,E[MAXN],p[MAXN];inline void sum(vector &F) {for(int i=1;i &F) {for(int i=1;i>1;}return ret;}signed main() {scanf("%lld%lld",&n,&k);fac[0]=inv[0]=1;for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%MOD,inv[i]=ksm(fac[i],MOD-2);for(int i=1;i<=k;++i) scanf("%lld",&E[i]);vector F(MAXN);F[0]=1;for(int i=1;i<=n;++i) sum(F);for(int i=0;i<=n;++i) {p[i]=1;for(int j=1;j<=k;++j) p[i]=(p[i]*F[E[j]])%MOD;del(F);}int ans=0;for(int i=0,f=1;i<=n;++i,f*=-1) {ans=(ans+MOD+f*binom(n,i)*p[i]%MOD)%MOD;}printf("%lld\n",ans);return 0;}
AtCoder Beginner Contest 285 解题报告
新一代云原生日志架构 - Loggie的设计与实践
皮俑是什么做成的?皮俑为什么救吴邪?
擅长画虎的画家是?擅长画虎的十大画家
神奇宝贝的观看顺序是什么?神奇宝贝的大结局是什么?
用上半固态电池!赛力斯发布海外新车型SERES 5:订单超2万
国产骄傲!中国年度十大畅销新能源车型:外资仅有特斯拉上榜
每日播报!游客滑雪失控致女生被撞倒后抽搐 医生:危险数极高、常见骨折
拿老款忽悠当新款卖 女车主退车被日系4S店老板辱骂
风调雨顺的意思是什么?风调雨顺的下联是什么?
小年为什么分南方和北方?小年为什么吃麻糖?
液晶显示器故障怎么解决?液晶显示器故障维修大全
qq空间打不开是什么原因?qq空间打不开怎么办?
cf怎么鬼跳没声音?cf鬼跳教程按键手法
土豆网怎么下载?土豆网怎么没有了?
环球热讯:1.PyQt5【窗口组件】小部件-QWidgt
阿里云邮箱怎么注册?阿里云邮箱怎么发送邮件?
女粉丝入手小米13 曾是十年资深果粉:被小米和雷军打动
当前滚动:二手车商要“气晕”!美国已有特斯拉新车价格低于二手车
低调的江西 盛产新能源富豪
2023央视春晚主持人阵容公布:首次迎来双90后
每日头条!衡山雾凇火了 多名游客滑冰下山很危险 景区调整开放时间
Ansible 学习笔记 - 批量巡检站点 URL 状态
世界观速讯丨node和npm如何升级版本
世界信息:把车变成船 比亚迪真会玩
天天报道:《中国奇谭》值得这么夸吗?
【世界播资讯】首搭麒麟电池 全球MPV续航最长!极氪009开启交付
三星Galaxy S23系列售价泄露:12GB+1TB版本超1万元
行驶1900多米!祝融号已在火星留下近4000个“中”字
C#代码整洁之道读后总结与感想
【快播报】私家车与油罐车高速并排堵路 货车司机看不下去 主动让路
环球消息!男子开车时被激光笔照射 瞬间眼前一片黑!专家称可能会永久损伤
世界观点:小编要失业了 美国科技媒体CNET用AI写文章:读者完全没发现
天天快看点丨马斯克回应车主维权:涨价也没人给我补差价 就这吧
视焦点讯!太傲慢!微信更新内容仅“九个字” 网友:怕大家知道更新了什么吗?
全球速看:油车也有续航焦虑 高速服务区爆满:排队一小时 加油限量100元
消息!小米上架抗原试剂盒:19.9元5个 现货供应
《三体》电视剧开播 广受好评 网友:没看过原著的也被深深吸引
世界最新:2023春节档预售票房破亿:《流浪地球2》排片率第一 吴京/刘德华主演
世界今日报丨Recyclerview列表视频自动播放方案
观天下!QSAN A Quantum-probability based Signed Attention Network for Explainable Fa
剧版《三体》高热开播:收视率蹿升至第一、破腾讯视频记录
尼泊尔客机坠毁:机上72人不幸全部遇难
AMD显卡的尴尬!一个月了 两大品牌仍然没有RX 7900
世界新动态:中国首次全尺寸超导航行试验成功!时速50公里、冲击1000公里
全球信息:AJAX使用记录
环球热头条丨糖醋排骨里竟然藏着"量子点"!它咋这么厉害?
天天观天下!2个大厂 100亿级 超大流量 红包 架构方案
世界视点!CodeQL练习1
实时:day02-Spring基本介绍02
【天天速看料】Redis——数据类型
每日焦点!小朋友把山东的雪带回福建:半路化了 崩溃大哭
天天日报丨尼泊尔客机坠毁遇难人数升至68人:没有中国公民
环球快资讯:golang 为图片加水印
mysql--时间
环球焦点!王思聪打人后行政拘留为什么能暂缓执行?罗翔科普
天天观速讯丨AMD悄悄公布31个CPU漏洞:4个极危险、Zen4高枕无忧
今日热文:Nginx面试题(史上最全 + 持续更新)
当前快讯:Atcoder Regular Contest ARC 153 A B C D 题解
焦点关注:PhotoEnhancer人工智能一键修复老照片,老照片修复,图像去噪
男子花32万买比亚迪海豹 内心崩溃:汽配城都没这么难看
焦点要闻:节能版酷睿i9-13900T现身:35W战平12900K
观天下!腾讯开出48人惩治名单 马化腾曾称内部贪腐“触目惊心”
Phi的反函数
【环球热闻】110度高烧不退!AMD RX 7900 XTX退换货率高达11%
为啥北方二十三过小年 南方却是二十四?和康熙乾隆有关
观察:无广告一年免费用!通信UOS家庭版22.0开始推送
111111
男子买898元零食P图付款 被抓现行:实际支付了1分钱
天天通讯!基于传奇车型AE86!丰田推出两款新能源概念改装车
CF构造题1600-1800(2)
女子骑电动车载两人闯红灯被撞 被判全责 网友:这才是公正
苹果回应iPhone车祸监测误报频发:正收集相关反馈
《新·福音战士剧场版:终》国内海报抄袭!竹也文化官方布道歉声明
Python开发的常用组件
每日观察!推荐一本正在看的书
环球今热点:几十年数学难题被谷歌研究员意外突破 当年差点被导师赶出门
B站2022百大UP主出炉:手工耿入选 走向世界的手工匠人
天天亮点!稳居春节档票房前三:《流浪地球2》官方揭秘太空电梯创作思路
世界讯息:12月新能源销量排名出炉:比亚迪吉利长安强攻 特斯拉扛不住了?
【全球独家】读编程与类型系统笔记08_面向对象变成的元素
观速讯丨长征第462发!我国成功发射一箭14星:“共享”火箭了解下
国内《新·福音战士剧场版:终》限定海报被指抄袭 官方正在联系画师确认
无法恢复!微软杀软Defender误删开始菜单/任务栏捷方式
天天观点:排量830cc 马自达转子发动机正式回归!首车发布
天天亮点!雨雪降温重心转移至南方 大范围雨雪天气明日结束
天天短讯!一步一步实现若依框架--2.3防止重复提交 repeat_submit
焦点快播:2022一年 特斯拉车主为地球节省20亿美元油费
每日消息!全球首现!四川一地发现新物种:长得特别好看
每日动态!《三体》剧版今日CCTV8、腾讯视频全网首播:会员提前看三集
天天观点:使用ActiveMQ Artemis进行重连
环球热议:千万别在有WiFi的房间里摆这种姿势
焦点观察:微软收购动视暴雪更难了!NVIDIA出手阻挠
环球观焦点:联名中国第一科幻IP!荣耀80 Pro《三体》动画定制版来了:限量卖
【全球独家】淘汰所有老款!新一代PS5主机年内到来:不向下兼容
环球热门:无磷配方 低泡易漂 绿伞洗衣液6斤17.9元
每日焦点!碰撞测试能拿一星 创维是造了什么“神仙”车
全球播报:中国科幻顶级IP首登荧屏!《三体》电视剧今晚央视、腾讯视频首播
中国制造多牛?世界最先进工厂:我们占了近一半
今日热文:堪比抢iPhone 泰国车主凌晨排队买!比亚迪泰国发运破万台