4 alan_cty

尚未进行身份认证

我要认证

蒟蒻一只 别打脸(⊙o⊙)哦

等级
TA的排名 6k+

北大集训总结

前言请问我是直接退役还是走形式呢Day 0早上的高铁中午到来之前北京下雪了但是我们到的时候已经停了(什么时候能够真正看一次下雪呢本来以为很快就能住下,结果被前台鸽了一万年点的外卖没地方吃只能去开幕式吃QwQ结果说好1h的开幕式15min就结束了(饭都没吃完试机给了三道看上去能做的题,口胡了做法写个暴力就跑了听说都是去年的题,B似乎有线性做法出题人被爆了。。。在北大饭堂吃饭,发现...

2019-12-17 22:00:09

CSP-S 2019摸鱼记

摸鱼一时爽,一直摸鱼一直爽Day 0Q:CSP和NOIP是什么关系A:没关系不管怎样我这个高三老咸鱼就是去打酱油的酒店好评,但卫生间的玻璃emmmm一言难尽还有WiFi极差,还好我有流量下了一晚上棋Day 1又是在二中,令人怀念呢没什么负担随便打打A是个一眼题B是个一眼题C不是个一眼题然后花了半个钟把A和B写完了,期间发现了A会爆ll要用ull剩2.5h搞C我就不信搞...

2019-11-20 15:21:11

[AGC020F]Arcs on a Circle

Description用n个长度为L[i]的圆弧随机覆盖长度为c的圆环,问圆环被完全覆盖的概率n<=6,c<=50Solution我还以为是一道niubi积分题_(:з」∠)_考虑把圆环在L最大的圆弧的左端点处断开,我们可以把环上的问题变成链上的问题然后,每个圆弧的左端点X[i]=P[i]+R[i],其中P[i]∈[0,C),R[i]∈(0,1)P[i]\in[0,C),R...

2019-11-06 21:58:06

[AGC022F]Checkers

Description令x=10100x=10^{100}x=10100,数轴上有n个点,第i个点的坐标为xix^ixi进行n-1次操作,第i次操作选择两个点A和B,将A变为A关于B的对称点,然后删去B最后会剩下1一个数,问这个数有多少种可能的取值n<=50Solution由于x很大,我们可以只考虑每个数的贡献容易知道每个数的贡献形式为±2^k如果我们选择A和B,就从B向A连...

2019-11-06 15:38:10

[AGC030E]Less than 3

Description给出两个长度为n的01串s和t你进行若干次操作,每次操作可以更改s中某一个位置上的值,每次操作前后需要保证s中不存在相邻3个一样的字符现在问把s变为t所需要的最小操作次数n<=5000Solutionniubi题我们在0->1之间画一条红线,在1->0之间画一条蓝线默认字符串开头结尾有无限多的红蓝线,我们可以发现两个字符串相等等价于这两个字符...

2019-11-01 11:11:12

[CF526G]Spiders Evil Plan

Description给出一棵n个点的树,边有边权q次询问每次询问给出点x和y,问选y条路径,满足这y条路径的并是一个连通块S,S包含x,且S内的边权和尽量大输出最大的边权和强制在线n,q<=10^5Solution先考虑一次询问我们可以以x为根,然后选2y个叶子到根的路径最长容易发现直径的某个端点一定被选,我们可以以某个直径端点为根建树不考虑包含x,问题变成选2y-1个...

2019-10-29 21:28:43

[AGC027E]ABBreviate

Description给出一个字符串s,每次操作可以选择子串aa变为b,也可以选择子串bb变为a问能得到的本质不同的字符串数量|s|<=10^5Solutionxjb编了7788还是去看题解了_(:з」∠)_首先,一个字符串能变成一个字符a或b,需要存在一步可行操作,即不为ababa…然后,一个字符串能变成a还是变成b,可以用(cnta+2*cntb)%3计算,若为0则不能变成...

2019-10-26 16:08:46

[CF578F]Mirror Box

Description有一个n*m的网格,每个格子是一个斜45°摆放的镜子现在有一些格子上的镜子不见了,你需要求出有多少种摆放镜子的方法,满足:1:从网格某一个边缘的中点射进来的光线会从这条边的一个临边射出2:网格图中每一条网格线都存在1中的一条光线,满足这条光线经过这个网格线n,m<=100,保证空格子的数量<=200Solution考虑把所有格点黑白染色,我们可以发现...

2019-10-26 15:22:50

[AGC032F]One Third

Description一个长度为1的环,随机角度切n刀,对于每一块长度为x的,取最接近1/3的,即|x-1/3|最小的那一块问这个最小值的期望n<=10^6Solution感觉还是有一些不明觉厉首先,对于一次在x的划分,在x画红线,在x+π/3画蓝线,在x-π/3画绿线,问题变成任意两条异色线之间的夹角的最小值由于所有线是对称?的所以可以只看某一段也就是说,令第一次划分的x为...

2019-10-24 10:04:50

[CF506E]Mr. Kitayuta's Gift

Description给出一个字符串s,你需要往其中插入n个小写字符得到字符串t,使得t是一个回文串问所有能得到的本质不同的t的个数|s|<=200,n<=10^9Solution先考虑最暴力的做法,我们设F[l][r][k]表示当前s[l…r]还没有被匹配,从外往里做到第k层转移直接考虑第k+1层选什么字符,视情况可以转移到F[l+1][r-1][k+1],F[l+1][...

2019-10-22 14:33:50

[CF506C]Mr. Kitayuta vs. Bamboos

Description有n个竹子,第i个竹子长度为h[i],每天的结束会长高a[i]现在有m天,每一天可以做k次操作,每次操作可以选择一个竹子砍掉p,即高度h[i]=max(h[i]-p,0)你需要最小化m天结束后最高的竹子的高度n<=100000,m<=5000,k<=10Solution先考虑二分答案ans,然后有两种做法:Solution 1:考虑每个竹子,...

2019-10-21 20:55:48

百度之星2019决赛旅游记

前言白嫖百度真开心Day 0坐前一天晚上的高铁到了北京成功成为最早到的选手然后就一直颓在酒店里下来拿午饭外卖的时候发现还有报道这个操作(来的比报道还早_(:з」∠)_晚上坐了大半个小时的车来到了不远处的酒店(北京真的堵晚宴emmmm作为南方人表示太辣了(加大力度去试机发现这电脑里面怎么什么都没有花了一万年下好了Dev-cpp,写了个NTT测速,溜了溜了Day 1比赛日题目...

2019-10-17 10:29:00

[Atcoder Grand Contest 038]简要题解?

前言放弃了AGC去打Comet OJ回过头来发现这场怎么这么zz啊亏了亏了题目链接01 Matrix这样构造(灵魂画师谢罪了)Code#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#defi...

2019-09-23 21:20:49

[Comet OJ - Contest #11]简要题解?

前言md又是rk4_(:з」∠)_可惜了要是ilnil过了E我们机房就可以加一个冰箱了题目链接eon模拟Code#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) ...

2019-09-23 09:45:05

[The Preliminary Contest for ICPC Asia Shanghai 2019]简要题解?

前言大概是第一场AK的ACM比赛?我太菜了,队友太强了.jpg先把自己负责的题写一写,剩下的咕了题目链接Lightning Routing ILCT模板题对于每条偏爱路维护正着和反着两条直径,用两个set维护所有虚儿子的最长链有板子就很舒服Code#include <set>#include <cstdio>#include <cstring&...

2019-09-15 18:55:47

[300iq Contest 1]简要题解

前言老年选手的智商训练(1/∞)题目链接Angle Beats考虑建图,发现每个∗*∗和+++的度数都为2,每个...的度数都为1对于每个∗*∗和+++拆两个点,这两个点互相连边对于一个∗*∗点,其中一个点向上/下的...连边,另一个向左右的...连边对于一个+++点,两个点都向上下左右的...连边考虑这张图的最大匹配,可以发现,答案为match-cnt,cnt为∗*∗和+++的数...

2019-09-06 20:00:32

带花树模板

背下来就好了。。。。#include <queue>#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)#def...

2019-09-06 11:10:40

「MtOI2019」幽灵乐团

Description求∏i=1A∏j=1B∏k=1C([i,j](i,k))f(type)\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}({[i,j]\over (i,k)})^{f(type)}i=1∏A​j=1∏B​k=1∏C​((i,k)[i,j]​)f(type)f(0)=1,f(1)=ijk,f(2)=(i,j,k)f(0)=1,f(1)...

2019-09-02 21:23:46

一句话题解

由于有些题是在是不想写就开个坑吧(老年选手的悲哀「MtOI2019」埋骨于弘川题目链接Solution显然所有f(n,k)都是2^x,不如取对数变成加法那么我们有f(n,0)=∑i=142f(n−i,0)∗if(n,0)=\sum_{i=1}^{42}f(n-i,0)*if(n,0)=∑i=142​f(n−i,0)∗i,这是一个线性递推并且f(n,k)=f(n−1,k)+f(n,k−1...

2019-09-02 20:25:57

[The 2019 Asia Yinchuan First Round Online Programming]简要题解

前言吃瓜吃瓜顺便我没有做过原题来试一试能打多少由于开学机房只剩我一个人只能单挑了_ (:з」∠) _有的题没时间写就口胡了题目链接Maximum Element In A StackSolution模拟Code#include <cstdio>#include <cstring>#include <algorithm>#define f...

2019-09-01 22:35:55

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。