REFLECTIONS

刚刚结束了 ACM 的集训,仔细反思了第一学期的大学学习生活。 首先要说的是上课,在一开始的时候,我每次都会提前很久去占座。但是这样的情况并没有持续很久,有一段时间由于感觉老师讲得太慢,经常上课开小差。但是事后自习想了想,还是决定回到开学时的状态。但是这时候我却惊讶的发现,并不需要占座了,就算是踩着上课铃去上课,也依旧可以坐到第一排(线性代数除外)。解决了态度问题,接下来还是有一个不可回避的问题,有时候觉得讲得太慢,不想听。所以就带了自己的书,讲到不懂的,就认真听课,其余时间就好好看自己的书,学习别的东西...

2015年2月6日 · 2 分钟 · 934 字 · Kai Wang

ACM-ICPC 寒假练习 01

这一系列的练习主要在 Virtual Judge 上进行,题目为小白书上的题目推荐。 UVa 10055 求两方军队人数的差值,直接相减即可。 不过要注意两个数的大小关系。 #include <iostream> using namespace std; int main() { long long x, y; while(cin >> x >> y) { if(x > y) { swap(x, y); } cout << y - x << endl; } return 0; } UVa 10071 简单物理题,求两倍时间内匀速运动的路程。即 $s = 2vt$。 #include <iostream> using namespace std; int main() { int x, y; while(cin >> x >> y) { cout << x * y * 2 << endl; } return 0; } UVa 10300 根据题目描述推导公式,$$ \mathrm{ans} = \sum{\left(\frac{x}{y}\cdot y\cdot z\right)} = \sum{xz}$$ 题中讲到了首先计算每只动物的占地面积,乘以环境友好常数,再乘以动物数目。这里可以直接将动物数目约去。 #include <iostream> using namespace std; int main() { int T, N, x, y, z; cin >> T; for(int i...

2015年2月6日 · 4 分钟 · 1599 字 · Kai Wang

SGU 127 - Telephone directory

Description CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then $K$ lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing $N$ records, but since the information is confidential, without the phones locations. Input The first line contains a natural number $K$ ($0 < K < 255$) - the maximum number of lines that one page can contain. The second line contains a natural $N$ ($0 < N < 8000$) - number of phone numbers supplied. Each of following $N$ lines contains a number consisting of 4 digits - phone numbers in any order, and it is known, that numbers in this list cannot repeat. Output First line should contain a natural number $P$ - the number of pages in the telephone directory. Sample Input 5...

2015年2月5日 · 2 分钟 · 538 字 · Kai Wang

SGU 112 - a^b - b^a

Description You are given natural numbers $a$ and $b$. Find $a^b - b^a$. Input Input contains numbers $a$ and $b$ ($1\leq a,b\leq 100$). Output Write answer to output. Sample Input 2 3 Sample Output -1 Analysis 非常明显的高精度,再观察一下样例,要处理减法,而且有负数,注意一下好了。 Solution #include <iostream> #include <memory.h> using namespace std; const int MAX = 1024; const int HEX = 10000; const int BIT = 4; class Huge { public: Huge(); Huge(int x); ~Huge(); public: Huge& operator *= (int x); Huge& operator - (Huge &x); bool operator > (Huge x); public: friend ostream& operator << (ostream &out, Huge &x); public: int m_pData[MAX]; int m_nLen; }; Huge::Huge() { memset(m_pData, 0, sizeof(m_pData)); m_nLen = 1; } Huge::Huge(int x) { memset(m_pData, 0, sizeof(m_pData)); m_pData[1] = x; m_nLen = 1; } Huge::~Huge() { } bool Huge::operator > (Huge x) { if(this->m_nLen != x.m_nLen) { return this->m_nLen > x.m_nLen; } else { for(int i = this->m_nLen; i >= 1; i--) { if(this->m_pData[i] != x.m_pData[i]) { return this->m_pData[i] > x.m_pData[i]; } } } return true; } Huge& Huge::operator *= (int x) { for(int i = 1; i <= this->m_nLen; i++) { this->m_pData[i] *= x; } for(int i = 1; i <= this->m_nLen; i++) { this->m_pData[i + 1] += this->m_pData[i] / HEX; this->m_pData[i] %= HEX; } while(this->m_pData[this->m_nLen + 1]) { this->m_nLen++; } return *this; } Huge& Huge::operator -...

2015年2月5日 · 1 分钟 · 460 字 · Kai Wang

SGU 113 - Nearly prime numbers

Description Nearly prime number is an integer positive number for which it is possible to find such primes $P_1$ and $P_2$ that given number is equal to $P_1\cdot P_2$. There is given a sequence on $N$ integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise. Input Input file consists of $N + 1$ numbers. First is positive integer $N$ ($1\leq N\leq 10$). Next $N$ numbers followed by $N$. Each number is not greater than $10^9$. All numbers separated by whitespace(s). Output Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case. Sample Input 1 6 Sample Output Yes Analysis 考虑到数据范围不是很大,$10^9$ 以内仅有五千多万个质数,可以通过打表来解决。打表自然是筛法求素数。 每次读入数据以后,只要比较到 $\sqrt{X}$ 就可以了,这样我们就可以在 $O\left(\sqrt{n}\right)$ 的时间内求出结果。 这里有个小小的注意点,我们在循环的时候,最好使用 i * i <= X 来代替 i...

2015年2月5日 · 1 分钟 · 479 字 · Kai Wang

SGU 107 - 987654321 problem

Description For given number $N$ you must output amount of $N$-digit numbers, such, that last digits of their square is equal to 987654321. Input Input contains integer number $N$ ($1\leq N\leq 10^6$). Output Write answer in output file. Sample Input 8 Sample Output 0 Analysis 在一定意义上,这也是一道数学题。 由于一个数平方的后X位,只与这个数字的后X位有关系,所以我们不妨使用下面的程序打一个表来看一下。 #include <iostream> using namespace std; int main() { // sqrt(987654321) > 30000 for(long long i = 30000; i <= 999999999; i++) { long long x = i * i; if(x % 1000000000 == 987654321) { cout << i << " "; } } return 0; } 打完表以后,我们发现只有 8 个数字满足条件,而且分布在 100,000,000 到 999,999,999 之间。 下面我们来推导满足题目条件的答案与输入的位数 $N$ 的关系:$$\mathrm{ans} = \begin{cases}0, & N \leq 8\\ 8, & N = 9\\ 72\times 10^{N - 10}, & N \geq 10\end{cases}$$ 最后一...

2015年2月5日 · 2 分钟 · 510 字 · Kai Wang

SGU 184 - Patties

Description Petya is well-known with his famous cabbage patties. Petya’s birthday will come very soon, and he wants to invite as many guests as possible. But the boy wants everybody to try his specialty of the house. That’s why he needs to know the number of the patties he can cook using the stocked ingredients. Petya has $P$ grams of flour, $M$ milliliters of milk and $C$ grams of cabbage. He has plenty of other ingredients. Petya knows that he needs $K$ grams of flour, $R$ milliliters of milk and $V$ grams of cabbage to cook one patty. Please, help Petya calculate the maximum number of patties he can cook. Input The input file contains integer numbers $P$, $M$, $C$, $K$, $R$ and $V$, separated by spaces and/or line breaks ($1 \leq P, M, C, K, R, V \leq 10000$). Output Output the maximum number of patties Petya can cook. Sample Input 3000 1000 500 30 15 60 Sample Output 8 Analysis 简单的数学分析就知道,所求答案为 $\left\lfloor\frac{P}{K}\right\rfloor$,$\left\lfloor\frac{M}{R}\right\rf...

2015年1月30日 · 1 分钟 · 483 字 · Kai Wang

SGU 135 - Drawing Lines

Description Little Johnny likes to draw a lot. A few days ago he painted lots of straight lines on his sheet of paper. Then he counted in how many zones the sheet of paper was split by these lines. He noticed that this number is not always the same. For instance, if he draws 2 lines, the sheet of paper could be split into 4, 3 or even 2 (if the lines are identical) zones. Since he is a very curious kid, he would like to know which is the maximum number of zones into which he can split the sheet of paper, if he draws $N$ lines. The sheet of paper is to be considered a very large (=infinite) rectangle. Input The input file will contain an integer number: $N$ ($0\leq N\leq 65535$). Output You should output one integer: the maximum number of zones into which the sheet of paper can be split if Johnny draws $N$ lines. Sample Input #1 0 Sample Output #1 1 Sample Input #2 1 Sample Output #2 2 Analysis 数学题。直线分平面数,我们也可以通过找规律的方法来求出它的公式: 线段数 $N$ 平面数 $M$ 0 1 1 1 + 1 = 2 2 2 + 2 = 4 3 4 + 3 = 7 4 7 + 4 = 11 5 11 + 5 = 16 6 16...

2015年1月29日 · 1 分钟 · 397 字 · Kai Wang

SGU 115 - Calendar

Description First year of new millenium is gone away. In commemoration of it write a program that finds the name of the day of the week for any date in 2001. Input Input is a line with two positive integer numbers $N$ and $M$, where $N$ is a day number in month $M$. $N$ and $M$ is not more than 100. Output Write current number of the day of the week for given date (Monday – number 1, … , Sunday – number 7) or phrase “Impossible” if such date does not exist. Sample Input 21 10 Sample Output 7 Analysis 翻看日历,我们可以知道 2001 年 1 月 1 日为星期一。 这样,我们只需要计算输入的日期为该年中的第几天就行了。 当然,要记得判断输入的日期是否合法。 Solution #include <iostream> using namespace std; const int pDay[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int main() { int N, M, ans = 0; cin >> N >> M; if((M > 12 || N > 31) || (M == 4 || M == 6 || M == 9 || M == 11) && N > 30 || M == 2 && N > 28) { cout << "Impossible" << endl; } else...

2015年1月29日 · 1 分钟 · 286 字 · Kai Wang

SGU 123 - The Sum

Description The Fibonacci sequence of numbers is known: $F_1 = 1$; $F_2 = 1$; $F_{n+1} = F_n + F_{n-1}$, for $n>1$. You have to find $S$ - the sum of the first $K$ Fibonacci numbers. Input First line contains natural number $K$ ($0<K<41$). Output First line should contain number $S$. Sample Input 5 Sample Output 12 Analysis 考虑到数据范围,这道题目只要模拟一下就行了。但是我还是比较喜欢使用数学方法来求解。 令 $S_n$ 表示斐波那契数列的前 $N$ 项和,那么我们很容易求得 $S_n = F_{n+2} - 1$。 Solution #include <iostream> using namespace std; const int MAX = 64; int f[MAX]; int main() { int N; cin >> N; f[1] = f[2] = 1; for(int i = 3; i <= N + 2; i++) { f[i] = f[i - 1] + f[i - 2]; } cout << f[N + 2] - 1 << endl; return 0; } 这道题目应该是非常简单的。当然,如果你不知道斐波那契数列可以在$O(n)$时间内求得,那么这道题目对于你来说还是有一定难度...

2015年1月29日 · 1 分钟 · 252 字 · Kai Wang