MoonChasing

发表于 更新于 分类于 ， ， 本文字数： 4.1k 阅读时长 ≈ 7 分钟

D. Mishka and Interesting sum

time limit per test: 3.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Description

Little Mishka enjoys programming. Since her birthday has just passed, her friends decided to present her with array of non-negative integers a1, a2, …, an of n elements!

阅读全文 »

发表于 更新于 分类于 本文字数： 39 阅读时长 ≈ 1 分钟

夜雨寄北

李商隱

君問歸期未有期，巴山夜雨漲秋池。
何當共剪西窗燭，卻話巴山夜雨時。

发表于 更新于 分类于 本文字数： 353 阅读时长 ≈ 1 分钟

最近训练时敲代码总爱在 if 语句中有位算符时踩坑， 比如 if(i&1==0) 或 if(i&i-1 == 0)，本意是想判 i 是否为偶数和 i 是否为 2 的幂，但这么写都是错误的，导致程序不能输出正确结果。每次 debug 时又不明所以，耗了很长时间才找到。在这里记录下。

错误的原因是 == 运算符优先级要高于 & | ^ 这三个位运算符，故导致上面代码的判断顺序实际为 if(i & (1==0)) 和 if(i & (i-1 == 0))。 很痛苦呀，有没有。

建议：

  • 判断式中如果同时存在位运算符和小于等于大于时，将位运算符表达式加上括号
  • 判等时，如果一边是常数一边是变量，将常数放于判等左边。 （TAT，当时听郝斌老师讲这条时还不以为意，心想判等自己肯定不会写成 = , 现在想来，真是内牛满面呀，这条规则实在太好了）

发表于 更新于 分类于 本文字数： 79 阅读时长 ≈ 1 分钟

臨江仙 送錢穆父

蘇軾

一別都門三改火，天涯踏盡紅塵。依然一笑作春溫。無波真古井，有節是秋筠。 惆悵孤帆連夜發，送行淡月微雲。樽前不用翠眉顰。人生如逆旅，我亦是行人。

发表于 更新于 分类于 ， ， 本文字数： 4.2k 阅读时长 ≈ 8 分钟

传送门： 2018 Multi-University Training Contest 2 1007 Naive Operations

题目

Naive Operations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 502768/502768 K (Java/Others)

Problem Description

In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for $a_l,a_{l+1}…a_r$
2. query l r: query $\sum_{i=l}^r \lfloor a_i / b_i \rfloor$

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 1k 阅读时长 ≈ 2 分钟

归并排序思路很简单， 但自己一直不会敲， 也没敲过。 大学算法课本上的代码丑得不行， 嫌弃得要死。 所以自己只知道它的思想。 这几天打高校遇到了求逆序数对的问题，用树状数组来写会爆内存，需要用到归并的思想。于是自己打算好好看一下归并排序，发现紫书上的代码非常简洁，心喜，很快就记住了这段代码，并用自己喜欢的风格敲了一遍。

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 2k 阅读时长 ≈ 4 分钟

传送门：https://www.nowcoder.com/acm/contest/141/H

题目描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem.

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 5.9k 阅读时长 ≈ 11 分钟

传送门：https://www.nowcoder.com/acm/contest/141/A

题目描述

Eddy was a contestant participating in ACM ICPC contests. ACM is short for Algorithm, Coding, Math. Since in the ACM contest, the most important knowledge is about algorithm, followed by coding(implementation ability), then math. However, in the ACM ICPC World Finals 2018, Eddy failed to solve a physics equation, which pushed him away from a potential medal.

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 547 阅读时长 ≈ 1 分钟

当元素较少时，可以使用二进制码来表示集合。集合 ${0， 1， 2， \ldots，n-1}$ 的子集可以用如下方式编码成整数。$$f (S) = \sum_{i \in S} 2^i$$

像这样表示之后，一些集合运算可以对应地写成如下方式。

  • 空集 $\phi$——0
  • 只含有第 $i$ 个元素的集合 ${i}$——$1<<i$
  • 含有全部 $n$ 个元素的集合 ——$(1<<n)-1$
  • 判断第 $i$ 个元素是否属于集合 $S$—— if( S>>i&1 ) 或 if(S & (1<<i))
  • 向集合 $S$ 加入第 $i$ 个元素 ——S |= 1<<i
  • 从集合 $S$ 中去除第 $i$ 个元素 ——S&~(1<<i)
  • 集合 $S​$ 和集合 $T​$ 的交集 ——S&T
  • 集合 $S$ 和集合 $T$ 的并集 ——S|T
  • 切换第 i 位 ——S ^= 1<<i
  • 判断某状态是否有相邻的两者相同 ——if( S & S<<1 )
  • 把一个数字二进制下最靠右的第一个 1 去掉 ——S = S&(S-1)

此外，想要将集合 {0,1,….,n-1} 所有子集枚举出来的话，可以像下面这样写

1
2
3
4
for(int S=0; S < 1<<n; S++)
{
	//对子集的操作    
}
0%