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

10.12 CSP-S模拟30 改题记录

HZOJ

写在前面

貌似T3T4不太可改,遂先把前两题的写了。大概就是T1打表3小时没找到规律吧,喜提0pts。真是成也T1,败也T1。

Dearest Darling My universe
亲爱的 亲爱的宇宙啊
날 데려가 줄래
能否带我走
나의 이 가난한 상상력으론
去往凭靠我贫瘠的想象力
떠올릴 수 없는 곳으로
都无法想象到的地方
저기 멀리 from Earth to Mars
那远方 从地球去往火星
꼭 같이 가줄래
能否带我去啊
그곳이 어디든
不管那是何处 我们去寻找
오랜 외로움 그 반대말을 찾아서
与长久孤独相反的地方
어떤 실수로 이토록 우리는 함께일까
到底是因何失策 导致我们在一起呢
세상에게서 도망쳐 Run on
逃离这个世界 奔跑不停
나와 저 끝까지 가줘 My lover
与我走向那尽头 我的爱人
나쁜 결말일까 길 잃은 우리 둘 um
迷了路的我们俩是否最终会落下悲惨的结局
부서지도록 나를 꼭 안아
紧紧地抱住我 直到灰飞烟灭
더 사랑히 내게 입 맞춰 Lover
更深情地吻我吧 我的爱人
Love is all Love is all
爱是一切 爱是一切
Love Love Love Love

결국 그럼에도
归根到底 即便如此
어째서 우리는 서로일까
怎么我们还是彼此呢
세상에게서 도망쳐 Run on
逃离这个世界 奔跑不停
나와 저 끝까지 가줘 My lover
与我走向那尽头 我的爱人
나쁜 결말일까 길 잃은 우리 둘 um
迷了路的我们俩是否最终会落下悲惨的结局
찬찬히 너를 두 눈에 담아
细致入微地凝视注视你
한 번 더 편안히 웃어주렴
请你再快活地笑一次吧
유영하듯 떠오른 그날 그 밤처럼
像游泳那样浮上来 如同那天的夜晚一样
나와 함께 겁 없이 저물어줄래
你愿意和我一起无所畏惧地走到尽头吗?
산산히 나를 더 망쳐 Ruiner
将我摧毁得支离破碎的毁灭者
너와 슬퍼지고 싶어 My lover
想要与你共感悲伤 我的爱人
필연에게서 도망쳐 Run on
逃离这命运使然 奔跑不停
나와 저 끝까지 가줘 My lover
与我走向那尽头 我的爱人
일부러 나란히 길 잃은 우리 두 사람
故意选择一同迷失方向的我们俩
부서지도록 나를 꼭 안아
紧紧地抱住我 直到灰飞烟灭
더 사랑히 내게 입 맞춰 Lover
更深情地吻我吧 我的爱人
Our Love wins all Love wins all
我们的爱会战胜一切 战胜一切
Love Love Love Love

(话说我每次粘这么长一段会有人看吗)

A. 灯若辰星

小 L 给你出了一道简单数学题。

题意是对于\(n\) 个点,将\(i\) 号点分别向\(1-n\) 的排列\(a_i\) 号点连边,得到\(m\) 个连通块。对于每个连通块,其块内点对块的贡献是\(2^x\);对于整张图,每个连通块对总权值的贡献是\(2^{该连通块的权值}\)。给出\(q\) 个询问,每个询问给出\(n, m\) 和一个操作:
1 求问\(n\) 个点形成\(m\) 个连通块的方案数\(mod 2\) 的值
2 求问\(n\) 个点形成\(m\) 个连通块,连通块的权值和的种类数\(mod 2\) 的值

赛时嘛...就是狂打表,想复现一下昨天的奇迹。然鹅 。。。

首先看操作1。暴力打出来发现\(f_{i,j}=f_{i-1,j-1}+(i-1)*f{i-1,j}\)。转到输出\(mod\) 后的值时就发现,奇数个点的形态与该奇数-1的偶数个点的形态相同,然后当\(m\) 小于\(n/2\) 时答案一定为0。考虑去重。然后赛时就跑偏了跑去找复杂到用不了的规律,然后束手无策。实际上能观察到是个模2意义下的从杨辉三角的形态。考虑联系组合数结合卢卡斯定理。经过模拟发现只有在选是被选二进制下的子集时,组合数才为1。所以就将询问转到组合数上令\(x=(n+2)/2-1, y=m-(n-1)/2-1\),当$ (x\text{&}y)==y $ 时答案才为1。

然后看操作2。这里我想着重说一下如何暴力求(因为赛时set存vector写挂了)。考虑二进制的性,总权值相同当且仅当连通块个数相同且每个连通块的点数相同。由于我们只用判种数,所以可以哈希一下,然后丢进set去重,然后直接看set的size即可(赛时咋这么糖)。然后就能注意到\(g_{i,j}=g_{i-1,j-1}+g_{i-1,j}*j\),形态与1十分类似,大概就是将1,转了个方向再扩展了一点。然后采取同样的考虑组合意义的方法做。判断0/1与1相同。然后就能A掉了。

代码
#include<bits/stdc++.h>
using namespace std;
int main(){freopen("light.in","r",stdin);freopen("light.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int q;cin>>q;while(q--){int n,m,opt;cin>>opt>>n>>m;if(m==0){cout<<(n==0);continue;} if(m>n){cout<<0;continue;}if(opt==1){if((m<<1)<n) cout<<0;else{int x=(n+2)/2-1,y=m-(n-1)/2-1;cout<<((x&y)==y);} }else{int a=n-1-m/2,b=n-m;if((!n*m)||m>n) cout<<0;if(b<0||b>a) cout<<0;else cout<<((a&b)==b);}}return 0;
}

B. 彻天之火

草木皆兵了看啥都像容斥。大概就是赛时写个暴力就跑了吧。

题意是给出一棵树,给出若干点对。对于每个点对我们可以选择其简单路径染色,或者其简单路径的补集染色。求问最优方案下被染色的路径最少为多少。

异或哈希好题。首先可以将题意转化为求边数-最大交集。我们只用知道交集大小,所以可以对每条路径赋上一个哈希值,然后求出所有边的异或和取出现次数最多的即可。

笑如死了思路就这么短。最后插一句:可以用树上差分求异或和,不要傻傻搓线段树。

代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
typedef unsigned long long ull;
int n,m;
int tot,to[maxn<<1],nxt[maxn<<1],h[maxn];
inline void adde(int x,int y){to[++tot]=y;nxt[tot]=h[x];h[x]=tot;
}
ull hs[maxn];
inline void dfs1(int x,int f){for(int i=h[x];i;i=nxt[i]){int y=to[i];if(y==f) continue;dfs1(y,x); hs[x]^=hs[y];}
}
mt19937_64 rnd(202510121439);
int ans;
unordered_map<ull,int> mp;
int main(){freopen("fire.in","r",stdin);freopen("fire.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1,u,v;i<n;i++) cin>>u>>v,adde(u,v),adde(v,u);ull k;for(int i=1,x,y;i<=m;i++) k=rnd(),cin>>x>>y,hs[x]^=k,hs[y]^=k;dfs1(1,0);for(int i=2;i<=n;i++)++mp[hs[i]],ans=max(ans,mp[hs[i]]);cout<<n-1-ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=29465

相关文章:

  • 编译GreatSQL with RocksDB引擎
  • ubuntu源码编译指定版本make
  • 【LeetCode】274. H 指数
  • python之多态
  • Linux安装JDK1.8 tomcat MariaDB(MySQL删减版)
  • Ubuntu系统部署Anaconda环境及Python语言的详细流程
  • python之继承
  • RK3568+MCU实时机器人解决方案 - 教程
  • 做题记录 #2
  • 深度学习开源书籍的技术解析
  • Nginx怎么去做负载均衡?
  • 向量库面试题
  • 02 常用快捷键和指令
  • 深圳公共资源交易中心 www.szzfcg.cn
  • mysql百分数转小数点格式
  • mysql误删的performance_schema库
  • 操作系统内存管理思维导图总结
  • 15
  • 取证复刻1
  • 如何在Ubuntu中查看编辑lvgl的demo和examples?
  • 英语_翻译
  • 操作系统(Linux)文件系统思维导图总结
  • mysql不等于<>取特定值反向条件的时候字段有null值或空值读取不到数据
  • linux查看/修改各种资源限制ulimit
  • MySQL非root安装-初始化数据库时unknown variable ‘defaults-file=**/my.cnf‘
  • python中mod函数怎么用
  • Educational Codeforces Round 101 (Rated for Div. 2) 题解
  • Centos7下docker的jenkins下载并配置jdk与maven
  • The 2024 ICPC Asia Shanghai Regional Contest
  • 英语_阅读_Fireflies_待读