最新要闻
- 女子骑电动车载两人闯红灯被撞 被判全责 网友:这才是公正
- 苹果回应iPhone车祸监测误报频发:正收集相关反馈
- 《新·福音战士剧场版:终》国内海报抄袭!竹也文化官方布道歉声明
- 环球今热点:几十年数学难题被谷歌研究员意外突破 当年差点被导师赶出门
- B站2022百大UP主出炉:手工耿入选 走向世界的手工匠人
- 天天亮点!稳居春节档票房前三:《流浪地球2》官方揭秘太空电梯创作思路
- 世界讯息:12月新能源销量排名出炉:比亚迪吉利长安强攻 特斯拉扛不住了?
- 观速讯丨长征第462发!我国成功发射一箭14星:“共享”火箭了解下
- 国内《新·福音战士剧场版:终》限定海报被指抄袭 官方正在联系画师确认
- 无法恢复!微软杀软Defender误删开始菜单/任务栏捷方式
- 天天观点:排量830cc 马自达转子发动机正式回归!首车发布
- 天天亮点!雨雪降温重心转移至南方 大范围雨雪天气明日结束
- 焦点快播:2022一年 特斯拉车主为地球节省20亿美元油费
- 每日消息!全球首现!四川一地发现新物种:长得特别好看
- 每日动态!《三体》剧版今日CCTV8、腾讯视频全网首播:会员提前看三集
- 环球热议:千万别在有WiFi的房间里摆这种姿势
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
CF构造题1600-1800(2)
H. Hot Black Hot White(COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred))
题意
有 \(n\) 个石头,每个石头有一个值 \(a_i\),现在需要给这 \(n\) 个石头染色,要求 \(\frac{n}{2}\) 为白色,\(\frac{n}{2}\) 为黑色( \(n\) 为偶数),并且任何两个颜色不相同的石头 \(i\),\(j\) 满足 :
\[concat(a_i,a_j) \times concat(a_j,a_i) + a_i \times a_j \not\equiv Z \bmod 3\]求 \(Z\) 与 染色方法。
\(concat(x, y)\) 表示 \(y\) 的十进制连接在 \(x\) 的十进制右边,例如:\(concat(10,24) = 1024\)
(资料图)
思路
令 \(len(x)\) 表示 \(x\) 的十进制表示法中的位数,所以 \(concat(x, y) = x \times10^{len(y)} + y\)
我们可以发现 \(10\) 的任何次幂模 \(3\) 是等于 1 的,所以 \(concat(x, y) \bmod 3= ((x \bmod 3)\times 1 + (y \bmod 3)) \bmod 3\)
有了上面的发现,我们可以轻松的化简题中的公式:
\[\begin{aligned}(concat(a_i, a_j) \times concat(a_j, a_i) + a_i \times a_j) \bmod 3 &= (((a_i + a_j) \times (a_j + a_i)) \bmod 3 + a_i \times a_j\mod 3) \bmod 3 \\&= ((a_i^2 + a_j^2 + 2a_ia_j) \bmod 3 + a_i \times a_j\mod 3) \bmod 3\\&= ((a_i^2 + a_j^2) \bmod 3 + 3a_ia_j \bmod 3) \bmod 3\\&= (a_i^2+a_j^2) \bmod 3\end{aligned}\]也就是说我们要满足 \(a_i^2 + a_j^2 \not\equiv Z \bmod 3\) 这样的条件。
对于这个新的公式,我们同样有新的发现:
\[a_i^2 \bmod 3 = (a_i \bmod 3)^2 \bmod 3\]\(a_i \bmod 3\) 的值只能是 \(0,1, 2\),\(a_i^2 \bmod 3\) 的值只能是 \(0, 1\)。
我们可以贪心的让值相同的 \(\frac{n}{2}\) 个数为白色(一定可以找到这么多数,因为数组现在只有两个值),为黑色的数可能有两个值\(0,1\)或者可能有一个值。
这是我们发现 \(a_i^2 + a_j^2 \bmod 3\) 的值最多只能是两个不同的数,而 \(Z \bmod 3\) 有三个不同的数,一定存在一个 \(Z\)。
实现
void solve_problem() { int n; std::cin >> n; std::vector a0, a1; for (int i = 0; i < n; i++) { int a; std::cin >> a; a = a % 3; a = a * a % 3; if (a == 0) a0.push_back(i); else a1.push_back(i); } int Z = -1; std::string ans(n,"0"); if (a0.size() > n/2) { Z = 2; for (int i = 1; i <= n/2; i++) { ans[a0[i]] = "1"; } } else { Z = 0; for (int i = 1, j = (int)a1.size() - 1; i <= n/2; i++, j--) { ans[a1[j]] = "1"; } } std::cout << Z << "\n" << ans << "\n";}
F. Equate Multisets(Codeforces Round #805 (Div. 3))
题意
有两个集合 \(a\),\(b\) (集合中的数可以重复),每次操作可以选择集合 \(b\) 的任何一个元素 \(x\) 进行以下两种操作的一种:
- \(x = x \times 2\)
- \(x = \lfloor\frac{x}{2}\rfloor\)
求经过确定次数的操作后,两集合是否能相等(回答 YES
或 NO
)。
思路
首先可以发现如果 \(a\) 数组中的数是由 \(b\) 数组中的数最后通过 \(\times 2\) 转变来的,那么 \(a\) 数组中的这个数是偶数。
怎么运用这个发现呢?
我们可以考虑两个数组的最大值:
如果最大值是 \(a\) 数组的,那么他一定是最后通过 \(\times2\) 操作转变来的,并且它一定要是偶数
如果最大值是 \(b\) 数组的,那么这个数要转变为 \(a\) 数组中的数一定要进行 \(\lfloor\frac{x}{2}\rfloor\) 操作,因为 \(\times2\) 只会让它更大
如果两个数组的最大值相等,那么很可能不进行任何操作。
我们可以维护两个优先队列来取最大值:
如果最大值是 \(a\) 数组的,我们把它进行 \(\lfloor\frac{x}{2}\rfloor\) 在放进队列中,如果它是奇数,显然,这组数据是不能相等的。
如果最大值是 \(b\) 数组的,我们同样把它进行 \(\lfloor\frac{x}{2}\rfloor\) 在放进队列中,只不过不用考虑奇偶了。
如果两个数组的最大值相等,就把这两数
pop
掉。
最坏的情况我们可以对一个数进行 \(30\) 次 \(\lfloor\frac{x}{2}\rfloor\) 操作,\(2n\) 个数就是 \(60n\) 次 \(\lfloor\frac{x}{2}\rfloor\) 操作,但实际上远远达不到这么多。
实现
void solve_problem() { std::priority_queue, std::less> qa, qb; int n; std::cin >> n; for (int i = 1; i <= n; i++) { int a; std::cin >> a; qa.push(a); } for (int i = 1; i <= n; i++) { int a; std::cin >> a; qb.push(a); } while (!qa.empty() && !qb.empty()) { int a = qa.top(); qa.pop(); int b = qb.top(); qb.pop(); if (a != b) { if (a > b) { if (a & 1) { std::cout << "NO\n"; return; } else { a /= 2; } } else { b /= 2; } qa.push(a); qb.push(b); } } std::cout << "YES\n";}
D. Cyclic Rotation(Codeforces Global Round 20)
题意
有数组 \(a\),\(b\),每次可以对数组 \(a\) 进行操作,选择两个下标 \(l\) 和 \(r\) 并且 \(a_l = a_r\),使得 \(a[l\cdots r] = [a_{l+1},a_{l+2},\cdots a_r,a_l]\),求经过确定次操作后是否可以使两个数组相等(回答 YES
或 NO
)。
思路
首先可以发现进行过操作之后,选定的这个区间最后两个数是相等的,我们可以考虑反向操作,对数组进行还原。
我们从后向前进行双指针遍历,一个维护数组 \(a\) 的下标 \(i\), 一个维护数组 \(b\) 的下标 \(j\)。
当 \(a_i = b_j\) 时,直接 \(i-1\), \(j-1\) 即可
当 \(a_i \neq b_j\) 并且 \(b_j = b_{j+1}\) 时,我们可以把 \(b_j\) 存起来,因为它可以放到前面的任意位置,接着进行 \(j-1\)
当 \(a_i \neq b_j\) 并且 \(b_j \neq b_{j+1}\) 时,把 \(a_i\) 与存起来的数进行比较,如果可以找到与 \(a_i\) 相同的,那么他们两个就是匹配的,把这个数在存起来的数中拿出,然后进行 \(i-1\) ;如果没有找到,那这两个数组是不可能通过操作来相等的。
我们可以用 std::map
来存数。
实现
void solve_problem() { int n; std::cin >> n; std::vector a(n), b(n); for (auto &x : a) std::cin >> x; for (auto &x : b) std::cin >> x; if (b.back() != a.back()) { std::cout << "NO\n"; return; } std::map cnt; for (int i = n - 2, j = n - 2; i >= 0;) { if (j < 0 || a[i] != b[j]) { if (j >= 0) { if (b[j] == b[j + 1]) { cnt[b[j]]++; j--; continue; } } if (cnt[a[i]] != 0) { cnt[a[i]]--; i--; } else { std::cout << "NO\n"; return; } } else { i--; j--; } } std::cout << "YES\n";}
-
CF构造题1600-1800(2)
H HotBlackHotWhite(COMPFEST14-PreliminaryOnlineMirror(Unrated,ICPCRules,TeamsPreferred
来源: 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 泰国车主凌晨排队买!比亚迪泰国发运破万台
世界快报:微信全新拜年红包上线!支持语音祝福录制 动画效果太萌了
当前头条:Python树与树算法
B站大会员促销:12个月年卡到手价98元
天天动态:污染环境?代表建议允许春节分区分时燃放烟花 留住年味
每日消息!吓哭孩子!《中国奇谭》导演回应家长炮轰被网友赞:要走出国门征服老外
吃惊!杭州湿度达到100% 墙壁、窗台“挤”出水:网友吐槽难受到爆
当前聚焦:Linux中查看日志的常用命令
环球聚焦:算法学习笔记(8.2): 上下界网络流
当前最新:直播:央视网络春晚 最美女主播王冰冰亮相:王心凌等也来了
动态焦点:屏幕最小的第二代骁龙8旗舰!曝三星Galaxy S23卖6500元
老款iPhone激活原生灵动岛!DynamicCow教程来了
python批量发邮箱
有了这份Java面试中的葵花宝典,让你面试起飞!!!
每日时讯!还买什么Zen3/Zen4 6核酷睿i5-12490F到手1139元(首发1499)
焦点速讯:公司年终奖老员工人手1个30克金牌 感谢忠诚引热议:网友问还招人吗?
世界微资讯!Codeforces Round #843 (Div. 2) A1A2BCE(D待补)
储量超100万吨 瑞典发现欧洲最大稀土矿床:有望结束进口依赖
环球即时:首发4999元 Bose家庭娱乐扬声器550发布:支持TrueSpace增强原音
苹果iOS 17新特性和新功能抢先看!今年6月登场
有家长炮轰《中国奇谭》 导演回应:审美提高了就理解了
世界速看:Codeforces 1630 E Making It Bipartite 题解 (Dilworth定理)
世界播报:使用 Elasticsearch 搭建自己的搜索系统,这个厉害了。。
理解宏定义
2023春节新片预售票房破3000万:黑马杀出 《流浪地球2》仅排第三
数字化“乡村小道”跑得不舒服,试试低代码“高速公路”
当前看点!一位民办二本学生的年终总结
今日看点:荣耀首款小折叠屏来了:5千档真香
世界信息:今晚8点播出 王冰冰、撒贝宁等人组团剧透央视网络春晚
3999元解决安卓四大不可能 一加11成酷安最热机型:领先第二名一倍
认识Java语言
读编程与类型系统笔记07_子类型
张朝阳称年轻人不要只追求赚钱和快乐:想法不对 你会很痛苦 本人风趣回应
当前热讯:网易开始解散暴雪游戏相关团队!分手已成定局
世界微头条丨特斯拉海外大降价 美国新车主:恶心、不愿再看一眼爱车
全球快消息!门票值了!大熊猫看到游客后展示“才艺”:抱着竹子连续翻跟头
省钱还是抠门?马斯克不交房租:员工在工作日被房东赶出
当前视点!Netty-核心模块组件-4
环球视点!微信将处理假冒仿冒官方组织公众号:严重违规直接删号
全体起立!马自达MX-30 R-EV官图发布:转子发动机回归
全球要闻:雷军晒奖杯:《小米创业思考》获2022豆瓣年度大奖 揭秘小米创业经历
和女神视频聊天再也不害羞了!NVIDIA新技术让你“暗送秋波”:画面以假乱真
今日热讯:新娘刚下婚车遭痱子粉迎面砸脸引网友热议:婚闹是素质缺乏没教养?
当前讯息:“爱妻”来了!理想L7“皇后座”到底有多爽?1米2的腿部空间感受下
万元LV误标1599元被秒拍 得物回应:多次确认无异 无权干预
ruoyi打包jar分离配置部署
环球热消息:今晚8点见!2023央视网络春晚节目单发布:王心凌、董宇辉首次加盟
数论笔记-同余
“背菜女孩”家人回应1年赚20万 不穷:虚构捏造博眼球视频获流量应被整治
每日简讯:国铁西安局回应火车内设麻将桌:系主题定制列车 还有KTV、影院
【焦点热闻】苹果1200万像素为何胜过安卓1亿像素?历代iPhone相机揭秘:果然是神优化
记好这24个ES6方法,用于解决实际开发的JS问题
C#、TS和Dart对比3:编译时常量和运行时常量
2023性能战神!卢伟冰:Redmi K60 Pro是用户追求性能的不二之选
环球要闻:卡梅隆发文diss漫威电影:超级英雄演的像大学生
【天天报资讯】集体涨价!Intel 13代酷睿8款新U开卖:65W 24核高达4889元
为什么人类很难准确预测未来?
全球快看点丨《和平精英》开枪时的振动:居然可以造福盲人
当前消息!模板-线段树
全球热点!算法学习笔记(8.1): 网络最大流算法 EK, Dinic, ISAP
学习笔记——Spring简介;Spring搭建步骤;Spring的特性;Spring中getBean三种方式;Spring中的标签
实时:AcWing257 关押罪犯
当前关注:使用vscode调试PHP底层C源码
特斯拉降价后:门店半小时售10台 老车主直呼被损失4万
焦点速读:特斯拉降价引海外热议:这是《孙子兵法》!欲消灭传统车企
你拿多少?报告称2022年终奖人均2.19万元 一线城市近3万元
环球今日讯!果香浓郁!徐福记DODO综合果味棒棒糖 60支19.9元
【世界速看料】保护隐私!微信键盘iOS 1.0.2版更新:体积膨胀到237MB
全球观天下!联想GeekPro 2023主机首销6199元起:13代i5+RTX 3060
【天天快播报】春节前最后一次成品油调价来了!或迎2023年首次降价
关注:畅想未来:2023年手机还能怎样进化?