最新要闻
- 世界观天下!上调幅度2000到6000元!比亚迪宣布调整相关车型官方指导价
- 【环球热闻】今晚20点播出!央视跨年晚会阵容官宣:短道速滑运动员武大靖加盟
- 口碑崩盘豆瓣评分跌至5.4!《三体》动画第五集上线你还追吗?
- 全球快看:满满维生素!可口可乐innocent果汁大促:三瓶券后不到15元
- 天天热门:长绒棉亲肤透气 浪莎男士中筒袜子5双21.55元
- 每日讯息!2023元旦档预售总票房破1亿元:《阿凡达2:水之道》第一
- 《王者荣耀》铠荣耀典藏皮肤今晚上线!三形态特效帅炸
- 头条:游戏火爆全球 海外营收过半!米哈游获评全国文化企业30强
- 环球速读:史上财富损失第一人:马斯克财产缩水破人类记录
- 即时:官旗抄底:新疆大红乌苏啤酒500ml*12罐整箱59.9元
- 环球即时:沙特球队官宣C罗加盟 本人回应:是时候来亚洲分享经验了
- 一加11R外观泄露:双曲面屏、后置三摄
- 当前观点:联想YOGA新款笔记本曝光:双屏显示、支持360度翻转
- 天天快资讯:0糖、0脂肪!Nevercoffee咖啡:10盒到手16.41元
- 天天快资讯丨兴泉铁路全线开通:8个老区终于坐上火车
- 【世界报资讯】电脑上没有“锤子大爆炸”:自己做一个!
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
Codeforces Good Bye 2022 CF 1770 A~E 题解
题目链接
A. Koxia and Whiteboards
注意每一步替换操作都是强制的,而不是可选的。所以就用一个multiset维护所有的数,每次选一个最小的替换掉即可。
(资料图片仅供参考)
时间复杂度\(O(nlogn)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;LL t,n,m,a[110],b[110];int main(){ fileio(); cin>>t; rep(tn,t) { scanf("%lld%lld",&n,&m); multiset st; rep(i,n) scanf("%lld",&a[i]),st.insert(a[i]); rep(i,m) { scanf("%lld",&b[i]); //if(*st.begin()
B. Koxia and Permutation
k=1的情况,输出任意排列都可以。k>1时,发现一个包含数n的长度为k的字段的权值至少为n+1,盲猜存在一种排法使得最大权值就是n+1。其实下面的排法就满足要求:\(n,1,n-1,2,n-2,3\cdots\)。比如n=7时,排列就是\(7,1,6,2,5,3,4\)。在这种排法下,如果一个子段的最大值\(x>\frac n2\),由于它右边的数是\(n+1-x\),左边的数是\(n-x\),所以子段的权值绝对不会超过\(n+1\)。子段的最大值\(\le \frac n2\)时权值不可能达到\(n+1\)。所以这种构造是正确的。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;int t,n,k;int main(){ fileio(); cin>>t; rep(tn,t) { cin>>n>>k; int lb=1,ub=n; while(lb
C. Koxia and Number Theory
我们先\(O(n^2)\)地枚举数组中的每对数(a,b),看看如果要求\(gcd(a+x,b+x)=1\)的话x需要满足什么条件。如果a=b显然无解。否则令a,b中较小的为c,较大的为c+d。则我们要求\(gcd(c+x,d)=1\),也就是对于d的每个质因数,c+x都不能是这个质因数的倍数,也就是对于任意\(e|d,e是质数\),满足\(x \neq -c (mod \ e)\)。枚举了所有\(O(n^2)\)对数之后我们会得到若干个限制,如果存在某个质数p,我们要求\(x\ mod \ p\neq 0,x\ mod\ p\neq 1\cdots x\ mod\ p\neq p-1\),也就是所有p个限制都占满了,那肯定无解;否则根据中国剩余定理一定有解。
但是在上面枚举的过程中,\(d\)的数据范围是1e18,没法分解质因数。注意到一共只会产生\(\frac{n(n-1)}2\)个限制,所以在\(p>\frac{n(n-1)}2\)的情况下是不可能占满p个限制导致无解的,故只需考虑这个范围内的质数。
时间复杂度没仔细算,反正肯定是能过的。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;LL t,n,a[110],cnt[800][6000],lim;vector pri;bool isp(LL x){ for(LL i=2;i*i<=x;++i) if(x%i==0) return false; return true;}void precalc(){ for(LL i=2;i<=6000;++i) if(isp(i)) pri.pb(i);}int main(){ fileio(); precalc(); cin>>t; repn(tn,t) { cin>>n; rep(i,n) cin>>a[i]; LL tot=(n+1)*n/2+10; lim=0; rep(i,pri.size()) if(pri[i]<=tot) ++lim; bool bad=false; rep(i,n) { for(int j=i+1;j
D. Koxia and Game
按照游戏的过程正着分析看不出什么,我们倒着看看。方便起见把删数的那个人称为K,选数的那个人称为M。考虑这三个序列的最后一个数组成的multiset\(\{a_n,b_n,c_n\}\),如果K删掉了某个元素使得剩下的两个元素不相等,那K是不可能赢的,因为M总能找出一个元素使得最后形成的序列不是排列。所以\(a_n,b_n,c_n\)三个数不能全不同,至少得有两个相同的,且K一定是留下两个相同的数。倒数第二个位置同理,顺着推下去其实前面的每个位置都同理。
所以现在问题变成了这样:有两个数列a和b,对于每个i你可以在\(a_i,b_i\)中选恰好一个数,要求最后选出的序列是排列,求方案数。对于\(a_i=b_i\)的位置,会额外有\(n\)的方案数(因为原问题中\(c_i\)在这里可以乱选)。如果有解的话,最后把这个额外的方案数乘上就行了,下面的思考过程忽略这个额外的方案数。
转化成图论问题:把每个数看成一个点,对于每个i,在\(a_i,b_i\)之间连一条无向边。这个图中可能有自环和重边。建完图之后发现图是由一些连通块组成的。如果一个连通块内的点数和边数不相等,显然无解。否则这个连通块就是一个基环树,我们需要为每个点选一条相邻的边与其匹配,使得每条边恰好被匹配一次,并求出方案数。如果基环是一个自环,那显然只有1种方案。否则有两种方案,因为基环有两种匹配的方向。所以每个连通块的方案数都是1或2,全部乘起来就行了。
时间复杂度\(O(nlogn)\),因为要使用并查集维护图(其实直接搜也可以O(n))。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;const LL MOD=998244353;LL t,n,a[100010],b[100010],cnt[100010],fa[100010],sc[100010],sz[100010];LL Find(LL x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}int main(){ fileio(); cin>>t; rep(tn,t) { cin>>n; rep(i,n) scanf("%lld",&a[i]); rep(i,n) scanf("%lld",&b[i]); repn(i,n) cnt[i]=sc[i]=0,fa[i]=i,sz[i]=1; LL mul=1; rep(i,n) { if(a[i]==b[i]) ++sc[a[i]],++cnt[a[i]],(mul*=n)%=MOD; else { ++cnt[a[i]]; if(Find(a[i])!=Find(b[i])) fa[Find(a[i])]=Find(b[i]); } } repn(i,n) if(Find(i)!=i) cnt[Find(i)]+=cnt[i],sc[Find(i)]+=sc[i],++sz[Find(i)]; bool bad=false; repn(i,n) if(Find(i)==i) { if(cnt[i]!=sz[i]){bad=true;break;} if(sc[i]==0) (mul*=2)%=MOD; } if(bad) puts("0"); else printf("%lld\n",mul); } termin();}
E. Koxia and Tree
我一开始想的是:对每个点求出进行完所有操作后这个位置包含蝴蝶的概率,然后用这个概率加权求出两两之间的距离和。不幸的是这么做是错的,因为每个点包含蝴蝶的概率并不独立,它们之间是有关联的,比如k=1时答案应该是0,这个方法算出的答案就不是0。
换一种思路。先把1定为树的根。对于每个子树,我们想求出从它的根到其父亲的那条边,在画出蝴蝶两两之间路径时期望被走了多少次。把所有边的这个值加起来就得到了蝴蝶两两之间距离和的期望,除以蝴蝶对数就得到答案了。对于点i,令\(sz_i=\)初始状态下(没开始操作的时候)i的子树内的蝴蝶数量。发现所有操作做完后i子树内的蝴蝶数量只有三种可能:\(sz_i-1,sz_i,sz_i+1\),因为每条边最多运送一只蝴蝶,也最多只有一只蝴蝶能被运进或运出子树。如果能分别求出这三种情况发生的概率,也就能求出最终答案了。比如子树内蝴蝶数量为\(sz_i\)的概率是p,则对蝴蝶两两之间距离和的期望的贡献是\(sz_i\cdot(n-sz_i)\cdot p\)。这里我们计算期望时只有一个变量,不存在什么独立性的问题,所以正确性是有的。
对于一个点i,假设从它连向父亲的边的编号为j。如果我们知道在进行了j-1次操作后点i有蝴蝶的概率(p)与点i的父亲有蝴蝶的概率(q),那就能求出上面说的三个概率了。这里p和q是独立的、没有关联的,因为前j-1次操作都是在这条边两侧的两个连通块内进行的,互不影响。所以这么做是有正确性的。
从前到后依次进行操作,并同时维护每个点有蝴蝶的概率,这点也是很容易做到的。假设当前边连接(x,y),则令\(p_x=p_y=np,其中np=\frac{p_x+p_y}2\)即可,按照题目定义推一推就能得到。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL n,k,a[300010],inv2=qpow(2,MOD-2),ans=0,dep[300010],sz[300010];vector g[300010];vector e;LL dfs(LL pos,LL par){ sz[pos]=a[pos]; rep(i,g[pos].size()) if(g[pos][i]!=par) { dep[g[pos][i]]=dep[pos]+1; sz[pos]+=dfs(g[pos][i],pos); } return sz[pos];}int main(){ fileio(); cin>>n>>k; LL x;rep(i,k){scanf("%lld",&x);a[x]=1;} LL y; rep(i,n-1) { scanf("%lld%lld",&x,&y); e.pb(mpr(x,y)); g[x].pb(y);g[y].pb(x); } dfs(1,0); rep(i,n-1) { x=e[i].fi;y=e[i].se; if(dep[x]>dep[y]) swap(x,y);//x上y下 LL pls=a[x]*(1LL-a[y]+MOD)%MOD*inv2%MOD,sub=a[y]*(1LL-a[x]+MOD)%MOD*inv2%MOD,mid=(1LL-pls-sub+MOD+MOD)%MOD; (ans+=sz[y]*(k-sz[y])%MOD*mid)%=MOD; (ans+=(sz[y]+1)*(k-sz[y]-1)%MOD*pls)%=MOD; (ans+=(sz[y]-1)*(k-sz[y]+1)%MOD*sub)%=MOD; LL sum=(a[x]+a[y])%MOD; (sum*=inv2)%=MOD; a[x]=a[y]=sum; } LL tot=(k-1)*k/2%MOD; (ans*=qpow(tot,MOD-2))%=MOD; cout<
-
Codeforces Good Bye 2022 CF 1770 A~E 题解
题目链接A KoxiaandWhiteboards注意每一步替换操作都是强制的,而不是可选的。所以就用一个multiset维...
来源: Codeforces Good Bye 2022 CF 1770 A~E 题解
世界观天下!上调幅度2000到6000元!比亚迪宣布调整相关车型官方指导价
【环球热闻】今晚20点播出!央视跨年晚会阵容官宣:短道速滑运动员武大靖加盟
每日简讯:分布式排队叫号系统源码出售
口碑崩盘豆瓣评分跌至5.4!《三体》动画第五集上线你还追吗?
WPF 实现通知属性的N种方式
P3Depth: Monocular Depth Estimation with a Piecewise Planarity Prior
全球滚动:从USB存储设备启动树莓派
全球快看:满满维生素!可口可乐innocent果汁大促:三瓶券后不到15元
天天热门:长绒棉亲肤透气 浪莎男士中筒袜子5双21.55元
每日讯息!2023元旦档预售总票房破1亿元:《阿凡达2:水之道》第一
《王者荣耀》铠荣耀典藏皮肤今晚上线!三形态特效帅炸
头条:游戏火爆全球 海外营收过半!米哈游获评全国文化企业30强
快播:Unreal学习笔记1-打印输出
环球速读:史上财富损失第一人:马斯克财产缩水破人类记录
即时:官旗抄底:新疆大红乌苏啤酒500ml*12罐整箱59.9元
环球即时:沙特球队官宣C罗加盟 本人回应:是时候来亚洲分享经验了
一加11R外观泄露:双曲面屏、后置三摄
MySQL报错解决
当前观点:联想YOGA新款笔记本曝光:双屏显示、支持360度翻转
天天快资讯:0糖、0脂肪!Nevercoffee咖啡:10盒到手16.41元
天天快资讯丨兴泉铁路全线开通:8个老区终于坐上火车
【世界报资讯】电脑上没有“锤子大爆炸”:自己做一个!
环球快播:辽宁吉林多地现不明飞行物:外星飞船?还是韩国制造?
天天速讯:女子因上厕所未在工位被领导打:网友集体愤怒
天天日报丨知情人士:李子柒短期内或不考虑复出 业内看好重回顶流
速递!奥迪最帅量产电车!RS e-tron GT上市:146.88万秒杀保时捷
网友在苹果官方旗舰店买iPhone 13:取消订单却不给退款
快讯:三大件不再是重点 调查显示:84.5%消费者更看重汽车智能化
环球微动态丨ColorOS 13 2023年Q1适配计划出炉:10款机型喜提正式版
环球新动态:2022年总结与反思
全球热文:显卡清库存告一段落 价格已经到底:AMD、NVIDIA不会再便宜
【全球新要闻】RTX 4090游戏本狂野!一脚踢翻桌面RTX 3090
有你吗?我国千兆宽带用户达到8707万户 同比增长157%
全球最新:联想SmartPaper墨水平板曝光:10.3寸大屏、23ms低延迟
天天即时:国产游戏《大多数》称《九霄大陆》是盗版 把自己破解了
【天天时快讯】HDU 6801 Game on a Circle 题解 (推式子,多项式)
LeetCode-400. 第N位数字
全球观热点:红黑树起源以及插入解析
世界简讯:“最牛00后”:成都122岁长寿老人朱郑氏去世 家人100多名
全球快看点丨女子圣诞节送男友PS5:送礼前先把自己感动哭了
【全球速看料】比亚迪发布公告:终止拆分半导体业务上市
世界热门:新能源车国补即将取消 零跑表态:零跑C01不涨价
【全球独家】复习Stream流,函数式接口,方法引用
【天天新视野】最贵国产电动车高合HiPHi X宣发闹乌龙:零百加速45分钟
全球信息:杀死110公斤牛 北半球最凶猛的鸟金雕复仇人类:缝了40针
热资讯!软嫩多汁 拒绝合成肉:大希地整切牛排55.8元/斤好价
新能源车二手车:又红火起来了
全球热消息:腾讯今年股价曾腰斩 累计回购超9000万股 耗资超337亿港元
环球快消息!特色功能(锐捷智慧教室)
RX 7900 XTX温度烧到110度 AMD终于回应了:请联系客服支持
全球热议:盗版电影画质越发高得可怕 英国正版组织怒出手:嫌疑人落网
苹果允许安装第三方商店 但用户愿意吗?
【独家】RTX 4070 Ti官方偷跑!跑分都亮出来了
东方甄选直播一周年:股价翻800% 腾讯亏惨了
Android Emulator Container 配置
京东自营次日达 抗原检测试剂盒4.9元/份:15分钟出值
每日焦点!百度“萝卜快跑”首批获准在京开展全无人自动驾驶测试
当前观察:洗鞋机竟成了香饽饽!市场一片繁荣
2000年来首次发生!苹果2022年第四季度未发布任何新Mac产品
当前视讯!扬州高邮湖大桥几十辆车相撞 事故原因又是团雾
当前滚动:亲测有效! Studio One 6 V6.0.1 音乐编曲工具 含win/mac版
stm32读写sd卡代码解析和调试总结
前沿热点:Django路由层
全球微头条丨湖南汽车商会:汽车平台大涨价 4S店给汽车之家引流费一年最低23万
焦点热门:与热爱同行 18年魅族用户已是曹操出行CEO:希望有天把Flyme放进车机
环球关注:比亚迪仰望汽车来了!搭载最具颠覆性的尖端技术
天天快讯:太烂没人看?《阿凡达2》全球票房破11亿美元:中国内地贡献排第二
全球热头条丨零百6.9秒、纯电续航100km:坦克500 PHEV亮相广州车展
即时焦点:org.quartz.JobPersistenceException: Couldn't retrieve trigger: invalid stre
焦点热讯:MyBatis分页实现
世界百事通!现代细胞计数分析平台丨OMIQ简介
全球新动态:世界第一国际象棋手3分钟比赛迟到2分半 仅用22秒取胜
今日聚焦!奖金收入143万美元!Faker断层领跑韩国职业选手总奖金榜
跨年冷空气来了!跨年夜最冷大城市排行榜出炉:哈尔滨嗷嗷冷
世界快报:微信支付分大升级:订单信息一目了然 再不必担心扣费不明
全球百事通!卡梅隆R级《蜘蛛侠》电影图曝光:原定小李子主演
世界看热讯:亲测有效! Wondershare UniConverterV14.1.7 Wondershare PDFelement Professiona
今日快讯:基于局部直方图相关算法的近似优化和提速。
焦点速讯:Java集合快速失败和安全失败机制
全球新消息丨Python教程:如何创建多线程?
Django与数据库连接
每日观察!三星手机工业设计要焕然一新了!前奔驰中国首席大牛加盟:全权操刀
世界短讯!全新红旗H6亮相2022广州国际车展:压垮合资中型轿车又一力作
B站跨年晚会节目单官宣:邓紫棋首唱《三体》片尾曲《面壁者》
焦点热讯:Kafka的终极UI工具丨Offset Explorer功能简介
提前加满 2023开年油价第一涨:预计每升多花0.21元
员工超54万!京东为一线员工薪酬福利开支超330亿元
搭配紫光展锐国产芯:微软新Surface RT预计明年夏季推出
MyBatis-ResultMap
环球视讯!魅友人物纪录片《我有一个朋友》首映 80后CEO龚昕:我的青春是魅族
世界实时:搭乘猎鹰9号火箭 韩国首个月球探测器成功入轨:位列世界第七
【新视野】《王者荣耀》2023年首个新版本定了:新英雄莱西全员免费得
焦点观察:3.0T V6发动机卖成白菜价 长城皮卡山海炮上市:22.88万起
AIRIOT答疑第3期|如何使用物联网平台的可视化组态引擎?
鲁大师12月新机性能/流畅榜发布:小米直接包揽性能榜前三!
【环球时快讯】面包车行驶中车内起火 突然爆炸车顶掀飞数米高
【环球新要闻】大礼包抄底价:良品铺子坚果礼盒1440g装49元
80后宝妈辞职后做沙滩代写:月入过万
JJJJ车厘子有多大?JJJJ车厘子价格是多少?