Dicer's Blog

Life is hard, and I have my keyboard!

Codeforces-550

Div.3

不会写算数模拟,啊,我好菜。 A - Diverse Strings 排个序判断一下是否连续就好了。 B - Parity Alternated Deletions 维护两个数组,一个存奇数,一个存偶数。从大到小排个序,然后一个奇数一个偶数这样删掉。注意细节。 /*--------------------------------- @Author: Dicer @Date...

9th-HPU-校赛

敲代码真是太开心了

第九届河南理工大学算法程序设计大赛 比赛体验很好,就是自己太菜,极限那么题没写出来。 题目难度友好。 A. Asia区域赛 温馨的签到。 print(29+58+87+11+1+1) B. Asia区域制 就像组原老师说的那样,四位二进制转一位十六进制。 #include<bits/stdc++.h> using namespace std; int mai...

Codeforces-539

Div2

比赛连接 Sasha and His Trip 如果要去的城市小于油箱容积,那么不用充满油就够了,之后也不用加油了。 即: min(n-1, v) 如果城市数大于邮箱容积,那么先在1城充满油,然后每到一个城市就加一升油,如果当前剩余的油已经够接下来使用了就不用再加油了。 Sasha and Magnetic Machines 题目中明明都已经加粗说明了只能修改一次,然鹅我还是没注意。...

最小最大生成树

Life is hard,and I have my keyboard!

题目链接 一道有一点思维的kruskal的题目。 可以证明最小生成树中的最大边权就是能保证形成生成树的最小的最大值。 proof: Let MST = Minimum-spanning-tree of this Graph Let Edge<u, v, w> equal a edge of MST, there w is maximun of edges-weight i...

牛客寒假算法训练3

cnznb!!!

比赛链接 官方题解 A.处女座与线性代数 需要两个结论: 1.该n维点集中最多存在一个符合条件的点。 2.存在符合要求的点时,。 第一个比较容易想到,也容易利用向量的方向相反证明。 第二个证明就比较复杂了,比赛的时候大胆猜一下就好了。 有了两个结论之后,因为 k<=10,所以 n>25的直接输出0,剩下的暴力跑一下就好了。 B.处女座的比赛资格 因为有负权,所以Dijks...

牛客寒假算法训练2

处女座太强了

比赛链接 A.处女座的签到题 由于存储方式的原因,double的当数字比较大(1e18级别)的时候整数部分就不准确了。 因为左边都是整数,利用叉乘可以知道三角形面积的二倍一定是整数,所以先将面积的二倍存下来,输出的时候特判一下就可以了。 另外,nth_element()可以在最慢O(n)的情况下将第k小的数字,放在第k的位置上。 用法: nth_element(v.begin(), v.b...

树状数组

模板

树状数组 树状数组简单来说就是一种可以将数组的查询和修改的复杂度变成log级别。 首先说lowbit, 假设一个正整数x的二进制表示中第一个1出现在第k位,那么lowbit(x) = 2^(k-1)。 x 二进制 lowbit(x) 1 0001 1 2 0010 2 3 0011 1 4 0100 4 5 0101 1 6 0110 2 7 0111 1 8 1000 8 我们将l...

Good-Bye-2018

Everyone Rated!

2018年的最后一场cf,感觉自己打的还挺好的,cd两道数学题,都是猜出来的结论。 竟然在最后一场上蓝了,真的很开心。 A. New Year and the Christmas Ornament 注意y, b, r的关系不要看错了。 #include <bits/stdc++.h> using namespace std; int main(int argc, char ...

Codeforces-529

Div.3

A. Repeating Cipher 根据题意还原一下就好了。 #include <bits/stdc++.h> using namespace std; int main(int argc, char const *argv[]) { int n; string s, ans; cin >> n >> s; int j = 1; for(...

编程挑战赛-Round1

in HPU OJ

A. 子串问题 第一眼被一大段前缀后缀什么的骗到了,以为不可做。 然后再想,这不是sb题吗,出现次数最多的字串长度必为1。 s = input() a = {} mmax = 0 ans = '' for i in s: try: if i in a : a[i] += 1 if mmax < a[i]: mmax = a[i] ans = i if...