Iterfun's Blog

高精度计算有几种常见的类型： 两个很大的整数相加A, B的位数均小于等于10⁶ 两个很大的整数相减A, B的位数均小于等于10⁶ 一个很大的整数乘以一个比较小的整数A的位数小于等于10⁶，B的数值小于等于10⁹ 一个很大的整数除以一个比较小的整数A的位数小于等于10⁶，B的数值小于等于10⁹ 还有 两个很大的整数相乘 和 两个很大的整数相除 这两种情况，不过不常用，暂时不学了。 我们写数字习惯从高位开始写，但是模拟加减乘除时由于要做进位的操作，所以从低位开始存比较方便。即：数组第 0 位存个位，第 1 位存十位，第 2 位存百位······ 高精度加法C = A + B用变量 t 表示进位，要么是 1 要么是 0 。 123456789101112131415161718192021vector<int> add(vector<int> &A, vector<int> &B) { vector<int> C; // 和 int t = 0; // 1表示进位，0表示不进位 for ...

题意 输入格式输入一个正整数 N。 输出格式输出4个非负整数，按从小到大排序，中间用空格分开。 数据范围0<N<5∗10^6 样例1 input 5 output 0 0 1 2 思路这题三重循环暴力能过，反而比正常做法还快找到解。。。不愧是暴力杯。 (～￣▽￣)～不管它水不水，我们先来看看两种正常点的做法：哈希和二分。 好吧最后我们想想为什么这道题暴力更快：我们三重枚举理论上时间复杂度是O(N^3)（最坏），但问题是这道题它的答案都很小，所以我们早早就能找到解。这题不典型。 代码1234567891011121314151617181920212223242526272829303132333435363738394041// 二分做法#include <cstring>#include <iostream>#include <algorithm>#include <cmath>using namespace std;const int N = 2500005;struct Sum { ...

题意You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow: “1 p v” – An update query asks to change the value at position p in array a to v. “2” – A query asks to print the minimum number of required operations to convert array a to a zero array. A zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract ...

（本博客不给出详细证明过程。） 数论 质数 约数 同余 其他 线性代数 矩阵 消元 线性变换 线性空间 组合数学 组合计数 容斥原理 相关的重要数列、函数 概率论 概率 数学期望 01分数规划模型 博弈论 博弈的基本概念 SG函数的应用 质数质数的判定试除法 O(√N) 利用性质：若一个正整数 N 为合数，则存在一个能整除N的数T，其中2≤T≤√N。根据这一性质，我们只需要依次检查 2~√N 之间的所有整数是否能整除N。试除法的时间复杂度是O(√N)。 1234567// 试除法判定质数bool ispr(int n) { if (n < 2) return 0; // 特判0和1这两个整数，它们既不是质数也不是合数 for (int i = 2; i <= n/i; ++i) // 从2扫描到√N if (n%i == 0) return 0; return 1;} 质数的筛选 用筛法求出 1~N 中所有的质数。除了筛质数以外，埃筛的思想可以推广到很多场景中去，挺有用的。 先来看第一种筛法—— ...

题意There are N people in an xy-plane. Person i is at (Xi,Yi). The positions of all people are different. We have a string S of length N consisting of L and R.If Si= R, Person i is facing right; if Si= L, Person ii is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively. For example, the figure below shows the movement of people when S =(X1,Y1)=(2,3),(X2,Y2)& ...

题意Feras bought to his nephew Saleem a new game to help him learning calculating. The game consists of a board with 4 rows and 4 columns with 16 cubes. Every cube has a number from 1 to 16. Let’s define the power of a column as the sum of its elements. In the same way, the power of a row is the sum of its elements. Saleem should arrange the cubes in the board such that the power of all columns and all rows are equal. To make the game easier, the nice uncle, Feras, will help him arranging 7 cubes, ...

题意The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constructed a dictionary of words, They are interested only in the longest common suffix, That is, a suffix common to three or more words in the dictionary… A suffix is any substring that starts from some arbitrary position in the string and reaches the end of the string. As the ACM team was also prepari ...

题意微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。 输入格式输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F₁⋯Fₖ”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fᵢ（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 10⁷ 编号。数字间以空格分隔。 输出格式统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。 输入样例 5bob 11 ...

题意本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。 输入格式输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。 输出格式首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。 样例1 input 9 2 6 5 5 -1 5 6 4 7 output 4 1 9 思路这道题就是开vector二维数组存父子关系，然后就搜呗。感觉深搜比广搜直接。 具体做法都是先把每个爹的儿子们记录下来，其中是-1的那个是老祖宗，我们从老祖宗开始往下搜。用maxd更新最大辈分。 第3种思路：用并查集存爹，然后边打标记边枚举每个儿子，分别递归找爹。 思路1（DFS）1234567891011121314151617181920212223242 ...

题意在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。 输入格式输入在第一行给出一个正整数N（≤10⁴），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人： K P[1] P[2] ⋯ P[K] 其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10⁴。 之后一行给出一个非负整数Q（≤10⁴），是查询次数。随后Q行，每行给出一对被查询的人的编号。 输出格式首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。 输入样例4 3 10 1 2 2 3 4 4 1 5 7 8 3 9 6 4 2 10 5 3 7 输出样例10 2 Y N 思路并查集模板题。用set存人，方便去重和统计。 代码1234567891011121314151617181920212 ...