UOJ#454. [UER #8]打雪仗 http://uoj.ac/problem/454 分析: 好玩的通信题~ 把序列分成三块,\(bob\)先发出这三块中询问点最多的一块给\(alice\). 对于这一块,显然点数大于等于\(\frac{n}{3}\),全部由\(alice\)输出. 对于剩下的两块,先由\(bob\)告诉是否应该输出,\(alice\)再决定是否输出. 这样,\(alice\)的次数是\(667+\frac{2n}{3}\),\(bob\)的次数是\(2+\frac{4

UOJ Easy Round#7 传送门:http://uoj.ac/contest/35 题解:http://matthew99.blog.uoj.ac/blog/2085 #1 题意: 在一个(2n+1)*(2n+1)的网格中,每次只能走到相邻的点, 从左上端出发到右下端,找到一条路径,使此路径经过的所有点权值和最小. 输入:从内到外输出每一圈的点值大小:数据范围n<=10^5: 比赛中: 拿到题目,看到那极有特色性的一个大方格,以及极为特殊的走法,和那10^5的数据量,算法上基本可以确定贪

数论/Trie/并查集 猜数 这题我是这样分析的…… $a*b=g*l=n=k^2 \ and \ (g|a,g|b) \Rightarrow (g*a')*(g*b' )=g*l=k^2 \\ \Rightarrow a' * b' =\frac{l}{g}=(\frac{k}{g})^2  \Rightarrow min(a'+b')=2* \sqrt{\frac{l}{g}}, max(a'+b')=1+\frac{l}{g}$ 然而算ans的时候还需要再乘g……我给忘了

Preface 本着刷遍(只刷一遍)各大OJ的原则我找到了一场UOJ的比赛 无奈UOJ一般的比赛难度太大,我就精选了UER中最简单的一场打了一下,就当是CSP前的练习吧 A. [UER #5]万圣节的南瓜灯 一看就是要搞个结论的题目.首先我们看出来所有没有坏的格子要形成一棵树 那么对于\(n,m\le 1000\)的数据我们直接暴力连边并查集判断即可 然后考虑\(n,m\)较大时怎么做,我们发现树一定满足边数+1=点数,换句话说就是边数小于点数 那么我们容易发现对于\(2nm-m-4K<nm-k

然而UER我也照样跪…… 第一题 忘了取模sad || 操作符将整个区间分成了一些段,每个手机只会执行其中某一段,执行次数为这一段中&&的个数?+1? ans=ans*num[i]+1 倒着搞了一遍就过了?……然而我并不知道为什么…… //UER 2 A #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream>

[题目描述] 小Z在无意中发现了一个神奇的OJ,这个OJ有一个神奇的功能:每日签到,并且会通过某种玄学的算法计算出今日的运势.在多次试验之后,小Z发现自己的运势按照一定的周期循环,现在他找到了你,请通过他的记录,找出他运势的循环节. [输入数据] 第一行一个整数n,表示小Z记录的天数 接下来n行,表示每天的运势,用一个正整数表示,相同的整数表示相同的运势,不同的整数表示不同的运势. [输出数据] 一行若干个整数表示所有可能的小于等于n的循环节. [样例输入] 6 1 2 1 1 2 1 [样例输

第一题: 题目大意: 给出N个字符串,字符串的前面部分都是字母且都是一样的,后面部分是数字,按照后面的数字排序.N<=10000 解题过程: 1.第一题是真良心,一开始的做法是把后面的数字分离出来 比较大小,但是出现了傻逼错误样例过不去,就直接换了种方法,先比较长度再比较字典序. 结果就AC了. 2.如果按照最初的做法分离数字只能拿到70分,因为题目没说后面数字的范围,实际上是会爆long long的. 第二题: 题目大意: 有N个任务,每个任务有一个优先级p(各不相同),到达时间s,完成所需要

昨天晚上打的这个比赛,简直一颗赛艇啊-- 感觉发挥的并不好.比赛的时候比较紧张,最后一题还脑残写了个离散化结果爆零了,哎我怎么这么逗逼-- 讲讲比赛经过吧. 比赛之前逗逼地以为是8:00开始,然后淡定了5min就被告知是7:00--哎我怎么这么逗逼把开始时间都记错了2333-- 头比赛的时候在写xor和路径,一看还剩下1min+,马上就扔了开始数倒计时. 7:00准时发题,拿到题之后直接开读. A题目排列顺序,哎好像不太难的样子,不管了读完题再说. B题目交流通道,卧槽这什么图论还要计数的玩意儿

[多校联考2019(Round 5)] [ATCoder3912]Xor Tree(状压dp) 题面 给出一棵n个点的树,每条边有边权v,每次操作选中两个点,将这两个点之间的路径上的边权全部异或某个值,求使得最终所有边权为0的最小操作次数. \(v \leq 15,n \leq 10^5\) 分析 首先把边权转化为点权.记一个点的点权为与它相连的所有边的边权和.当我们给一条路径上的边异或上某个值时,路径端点的点权被异或了1次,而路径上不是端点的点有两条边被异或了,相当于异或了2次,权值不变.因此

原文链接:http://laphets1.gotoip3.com/?id=18 Description 给出一个由小写字母组成的字符串,其中一些字母被染黑了,用?表示.已知原来的串不是 一个回文串,现在让你求出字典序最小的可能的串.像’a’,’aba’,’abba’这样对称的串叫做回 文串. 每个测试点有5 组小测试点. Input 5 行,5 个字符串. Output 5 行,5 个字符串.若无解,输出”Orz,I can not find it!” 这个题目主要就是利用了一种贪心的思想  总

Description 给定一个多项式,输出其化简后的结果. Input 一个字符串,只含有关于字母x 的多项式,不含括号与分式,没有多余的空格. Output 一个字符串,化简后的多项式,按照次数从大到小的顺序输出各项. Input Sample x^3+3*x^4-2*x^3+1-x Output Sample 3*x^4-x^3-x+1 Hint 每项系数<10,次数<6,项数<20.字符串长度不超过100. 很烦的模拟   代码如下: #include<iostream&g

[题目描述] 天上红绯在游戏中扮演敏剑,对于高攻击低防御的职业来说,爆发力显得非常重要,为此,她准备学习n个技能,每个技能都有2个学习方向:物理攻击和魔法攻击.对于第i个技能,如果选择物理攻击方向,会增加ap_i的爆发力,如果选择魔法攻击的方向,会增加ad_i的爆发力.此外,还有一些combo,一个combo由两个技能组成,对于第i个combo,如果他们都是魔法攻击,会额外增加AD_i的爆发力,如果他们都是物理攻击,会额外增加AP_i的爆发力,如果他们不属于同一类型,会减少AX_i的爆发力.她找

[51nod 1295]Xor key(可持久化trie) 题面 给出一个长度为n的正整数数组A,再给出Q个查询,每个查询包括3个数,L, R, X (L <= R).求A[L] 至 A[R] 这R - L + 1个数中,与X 进行异或运算(Xor),得到的最大值是多少? 分析 可持久化trie裸题 代码 #include<iostream> #include<cstdio> #define maxb 31 #define maxn 200000 #define maxs 6

UOJ Test Round #1 T1:数字比大小的本质是按(长度,字典序)比大小. T2:首先发现单调性,二分答案,用堆模拟,$O(n\log^2 n)$. 第二个log已经没有什么可优化的了,但是第一个可以做到线性. 我们先将特殊题的p就当作是-1跑一边,设这个题的出现时间是tx,完成所需时间为sx,记录下每个题在[tx,T]上的出现时间.把所有题按优先级排序,可以发现如果找到了前i个满足出现时间之和为sx,那么这些时间区间正好可以被特殊题区间覆盖,找到这个i就确定了优先级,最后再模拟一遍

刷题训练 初学者 有一定语言基础,但是不了解算法竞赛,水平在联赛一等奖以下的. 参考书:<算法竞赛入门经典--刘汝佳>,<算法竞赛入门经典训练指南--刘汝佳> 题库:洛谷(历年题目),USACO training(有一定基础的可以考虑跳过前面几个Chapter),USACO月赛 进阶学习 联赛一等奖水平想要进步到安徽A队水平的. 参考书:<算法艺术与信息学竞赛--刘汝佳>,<算法导论>,<具体数学> 题库:bzoj(最经典的大量省选题和比较难的题

UOJ小清新题表 题目内容 UOJ链接 DZY开始有\(n\)个点,现在他对这\(n\)个点进行了\(m\)次操作,对于第\(i\)个操作(从\(1\)开始编号)有可能的三种情况: Add a b: 表示在\(a\)与\(b\)之间连了一条长度为\(i\)的边(注意,\(i\)是操作编号).保证\(1≤a,b≤n\). Delete k: 表示删除了当前图中边权最大的k条边.保证k一定不会比当前图中边的条数多. Return: 表示撤销第$ i−1$次操作.保证第\(1\)次操作不是Return

洛谷比赛 「EZEC」 Round 4 T1 zrmpaul Loves Array 题目描述 小 Z 有一个下标从 \(1\) 开始并且长度为 \(n\) 的序列,初始时下标为 \(i\) 位置的数字为 \(i\).有 \(m\) 个操作,每个操作会是以下四种之一. 1 对序列从小到大进行排序. 2 对序列从小到大进行排序后将其翻转,(译者注:就是从大到小排序). 3 x y 将下标为 \(x,y\) 的数交换位置.保证 \(x\neq y\) 且 \(1\le x,y\le n\). 4 将

向别人学习一波,记点流水帐.17.5.29开坑. 5.29 早晨看了道据说是树状数组优化DP的题(hdu5542),然后脑补了一个复杂度500^3的meet in the middle.然后死T...弃疗. 上午考试有一道sb线段树和一道简单数位DP.还有一道是毕姥爷在WC讲的"超立方体".对着数据范围的表格写了半天部分分然后你告诉我测试数据和这个数据范围根本不一样? 并不会FWT,又因为不太想学新算法,就决定不改题了. 下午先把某个课件的坑填完了.然后在bzoj上乱逛. 决定写写SD

这次打算法马拉松是在星期五的晚上,发挥还算正常(废话,剩下的题都不会= =). 讲讲比赛经过吧. 8:00准时发题,拿到之后第一时间开始读. A配对,看上去像是二分图最大权匹配,一看范围吓傻了,先跳过读后面的题. B完全二叉树的方差,大概看了一遍,好神的样子,跳过. C多项式?好吧没学过FFT和NTT的我肯定不会,跳跳跳. D最大值,哎呦这函数什么破玩意儿,看不懂,跳跳跳. E B君的射击,卧槽毕克大人您出题就算了出这么一道码农题是要闹那样,跳跳跳. F那些年,我们一起讲的故事,卧槽这特么简直就

今天终于有题了... 题目是COCI2016/2017 Round #4 T1一看就是NP问题,k<=50,开始想暴力,想了个n^4的,大概能过,就没去管它 T2想得太naive,丢了100分给的分 T3口胡AC实则懒得写 期望得分100... 我好鶸啊,鶸成一个zz 下午看各路大神谈笑风生,LazyJazz随便就切了3道题 %%% 课讲的是贪心与归纳,前半部分还是讲的简单的贪心和证明.感觉去年这个时候都听过一遍... 然后就跟馒神打头脑王者,偶尔看看题,一眼AC(废话你tm做过 晚上学习了一个

题目从难到易记录.解题过程中,如果不太熟悉,可以将题目中的表自己手动录入到自己的数据库中,就方便学习,测试. 185. Department Top Three Salaries 要求就是查询出每个部门工资在前三的人.题意值得注意的一点就是,要求找出的是工资数前三的人,而不是工资最高的前三位.区别就是前者查询出来的人可能大于3,而后者最大只能为3. 最终答案: select b.Name Department,a.Name Employee,a.Salary from (select Name,