洛谷 P1044 [NOIP2003 普及组] 栈
题目背景
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
题目描述
宁宁考虑的是这样一个问题:一个操作数序列,1,2,⋯ ,n1,2,\cdots ,n1,2,⋯,n(图示为 1 到 3 的情况),栈 A 的深度大于 nnn。
现在可以进行两种操作:
将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作);
将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)。
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。
(原始状态如上图所示)
你的程序将对给定的 nnn,计算并输出由操作数序列 1,2,⋯ ,n1,2,\cdots,n1,2,⋯,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只 ...
洛谷 P2392 kkksc03考前临时抱佛脚
题目背景
kkksc03 的大学生活非常的颓废,平时根本不学习。但是,临近期末考试,他必须要开始抱佛脚,以求不挂科。
题目描述
这次期末考试,kkksc03 需要考 444 科。因此要开始刷习题集,每科都有一个习题集,分别有 s1,s2,s3,s4s_1,s_2,s_3,s_4s1,s2,s3,s4 道题目,完成每道题目需要一些时间,可能不等(A1,A2,⋯ ,As1A_1,A_2,\cdots,A_{s_1}A1,A2,⋯,As1,B1,B2,⋯ ,Bs2B_1,B_2,\cdots,B_{s_2}B1,B2,⋯,Bs2,C1,C2,⋯ ,Cs3C_1,C_2,\cdots,C_{s_3}C1,C2,⋯,Cs3,D1,D2,…,Ds4D_1,D_2,\ldots,D_{s_4}D1,D2,…,Ds4)。
kkksc03 有一个能力,他的左右两个大脑可以同时计算 222 道不同的题目,但是仅限于同一科。因此,kkksc03 必须一科一科地复习。
由于 kkksc03 还急着去处理洛谷的 bug,因此他希望尽快把事情做完,所以他希望知道能够完成复习 ...
洛谷 P1045 [NOIP2003 普及组] 麦森数
题目描述
形如 2P−12^{P}-12P−1 的素数称为麦森数,这时 PPP 一定也是个素数。但反过来不一定,即如果 PPP 是个素数,2P−12^{P}-12P−1 不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是 P=3021377P=3021377P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入 PPP(1000<P<31000001000<P<31000001000<P<3100000),计算 2P−12^{P}-12P−1 的位数和最后500位数字(用十进制高精度数表示)。
输入格式
文件中只包含一个整数 PPP(1000<P<31000001000<P<31000001000<P<3100000)。
输出格式
第一行:十进制高精度数 2P−12^{P}-12P−1 的位数。
第 2-11 行:十进制高精度数 2P−12^{P}-12P−1 的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)。
不必验证 ...
CF1486B Eastern Exhibition
You and your friends live in nnn houses. Each house is located on a 2D plane, in a point with integer coordinates. There might be different houses located in the same point. The mayor of the city is asking you for places for the building of the Eastern exhibition. You have to find the number of places (points with integer coordinates), so that the summary distance from all the houses to the exhibition is minimal. The exhibition can be built in the same point as some house. The distance between t ...
CF1485D Multiples and Power Differences
You are given a matrix aaa consisting of positive integers. It has nnn rows and mmm columns.
Construct aaa matrix bbb consisting of positive integers. It should have the same size as aaa, and the following conditions should be met:
1≤bi,j≤1061≤b_{i,j}≤10^61≤bi,j≤106;
bi,jb_{i,j}bi,j is a multiple of ai,ja_{i,j}ai,j;
the absolute value of the difference between numbers in any adjacent pair of cells (two cells that share the same side) in - bbb is equal to k4k^4k4 for some integer k≥1k≥1k≥1 (k ...
CF1485C Floor and Mod
A pair of positive integers (a,b)(a,b)(a,b) is called special if ⌊ab⌋=a mod b\left\lfloor\frac{a}{b}\right\rfloor=a \bmod b⌊ba⌋=amodb. Here, ⌊ab⌋\left\lfloor\frac{a}{b}\right\rfloor⌊ba⌋ is the result of the integer division between aaa and bbb, while a mod ba \bmod bamodb is its remainder.
You are given two integers xxx and yyy. Find the number of special pairs (a,b)(a,b)(a,b) such that 1≤a≤x1≤a≤x1≤a≤x and 1≤b≤y1≤b≤y1≤b≤y.
Input
The first line contains a single integer ttt (1≤t≤1001≤t≤1001≤t≤1 ...
CF1485B Replace and Keep Sorted
Given a positive integer kkk, two arrays are called kkk-similar if:
they are strictly increasing;
they have the same length;
all their elements are positive integers between 111 and kkk (inclusive);
they differ in exactly one position.
You are given an integer kkk, a strictly increasing array aaa and qqq queries. For each query, you are given two integers li≤ril_i≤r_ili≤ri. Your task is to find how many arrays bbb exist, such that bbb is kkk-similar to array [ali,ali+1…,ari][a_{l_i},a_{l_i+1 ...
洛谷P3915 树的分解
题目描述
给出 nnn 个点的树和 kkk,问能否把树划分成 nk\frac{n}{k}kn 个连通块,且每个连通块的点数都是 kkk。
输入格式
第 111 行,111 个整数 TTT,表示数据组数。接下来 TTT 组数据,对于每组数据:
第 111 行,222 个整数 nnn, kkk;
接下来 n−1n-1n−1 行,每行 222 个整数 ai,bia_i,b_iai,bi,表示边 ai,bia_i,b_iai,bi。点用 1,2,⋯ ,n1,2,\cdots,n1,2,⋯,n 编号。
输出格式
对于每组数据,输出YES或NO。
输入输出样例
输入 #1
12345678924 21 22 33 44 21 21 31 4
输出 #1
12YESNO
说明/提示
对于 60%60\%60% 的数据,1≤n,k≤1031 \le n,k \le 10^31≤n,k≤103;
对于 100%100\%100% 的数据,1≤T≤101 \le T \le 101≤T≤10, 1≤n,k≤1051 \le n ,k \le 10^51≤n,k≤105。
思路
摘取自洛谷用户Yo ...
CF1477B Nezzar and Binary String
Nezzar has a binary string sss of length nnn that he wants to share with his best friend, Nanako. Nanako will spend qqq days inspecting the binary string. At the same time, Nezzar wants to change the string sss into string fff during these qqq days, because it looks better.
It is known that Nanako loves consistency so much. On the iii-th day, Nanako will inspect a segment of string sss from position lil_ili to position rir_iri inclusive. If the segment contains both characters ‘0’ and ‘1’, Nan ...
CF1328D Carousel
The round carousel consists of nnn figures of animals. Figures are numbered from 111 to nnn in order of the carousel moving. Thus, after the nnn-th figure the figure with the number 111 follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the iii-th figure equals tit_iti.
You want to color each figure in one of the colors. You think that it’s boring if the carousel contains two different figures (wit ...