11D_Beyonder's Blog

Problem Description 大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是NNN 毫升和MMM 毫升 可乐的体积为S（S<101）S （S<101）S（S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S=N+M，101＞S＞0，N＞0，M＞0S=N+M，101＞S＞0，N＞0，M＞0S=N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。 Input 三个整数 : SSS 可乐的体积 , NNN 和 MMM是两个杯子的容量，以"0 0 0"结束。 Output 如果能平分的话请输出最少要倒的次数，否则输出"NO"。 Sample Input 7 4 3 4 1 3 0 0 0 ...

Problem Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits c ...

Description Given a positive integer nnn, write a program to find out a nonzero multiple m of nnn whose decimal representation contains only the digits 000 and 111. You may assume that nnn is not greater than 200 and there is a corresponding m containing no more than 100100100 decimal digits. Input The input file may contain multiple test cases. Each line contains a value of n(1<=n<=200)n (1 <= n <= 200)n(1<=n<=200). A line containing a zero terminates the input. Output For e ...

Description Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M×NM × NM×N grid (1≤M≤15,1≤N≤15)(1 ≤ M ≤ 15,1 ≤ N ≤ 15)(1≤M≤15,1≤N≤15) of square tiles, each of which is colored black on one side and white on the other side. As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded wh ...

Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N(0≤N≤100000)N (0 ≤ N ≤ 100000)N(0≤N≤100000) on a number line and the cow is at a point K(0≤K≤100000)K (0 ≤ K ≤ 100000)K(0≤K≤100000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. Walking: FJ can move from any point XXX to the points X−1X - 1X−1 or X+1X + 1X+1 in a single minute Teleporting: FJ can move from any po ...

Description You are trapped in a 3D3D3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. Is an escape possible? If yes, how long will it take? Input The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers ...

Description 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kkk 个棋子的所有可行的摆放方案 CCC。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数，n,kn,kn,k，用一个空格隔开，表示了将在一个n×nn×nn×n 的矩阵内描述棋盘，以及摆放棋子的数目。 n<=8,k<=nn <= 8 , k <= nn<=8,k<=n 当为-1 -1时表示输入结束。 随后的 nnn 行描述了棋盘的形状：每行有nnn个字符，其中’#’ 表示棋盘区域，’ .’ 表示空白区域（数据保证不出现多余的空白行或者空白列）。 Output 对于每一组数据，给出一行输出，输出摆放的方案数目 CCC（数据保证C<231C<2^{31}C<231）。 Sample Input 2 1 #. .# 4 4 …# …#. .#… #… -1 -1 Sample Output 2 1 Idea 典型的搜索算法， ...

A. Even Subset Sum Problem You are given an array aaa consisting of nnn positive integers. Find a non-empty subset of its elements such that their sum is even (i.e. divisible by 222) or determine that there is no such subset. Both the given array and required subset may contain equal values. Input The first line contains a single integer t(1≤t≤100)t (1≤t≤100)t(1≤t≤100), number of test cases to solve. Descriptions of t test cases follow. A description of each test case consists of two lines. Th ...

理论阐述 树状数组的优越性 暴力求逆序对的方法就是利用双指针的移动，时间复杂度为O(n2)O(n^2)O(n2)，而树状数组能在O(nlog⁡n)O(n\log n)O(nlogn)内完成逆序对个数的求解。 树状数组使用方法 用a[i]a[i]a[i]存储出现的数，用树状数组ccc统计比a[i]a[i]a[i]小的数。顺序读取a[i]a[i]a[i]，每一次都将比a[i]a[i]a[i]小的数的个数增加111，即add(a[i],1)add(a[i],1)add(a[i],1)，然后将逆序对个数加上i−query(a[i])i-query(a[i])i−query(a[i])。 举例 有555个数，分别为5,3,4,2,15,3,4,2,15,3,4,2,1，当读入数据555时，c=[0,0,0,0,1]c=[0,0,0,0,1]c=[0,0,0,0,1]；当读入数据333时，c=[0,0,1,1,1]c=[0,0,1,1,1]c=[0,0,1,1,1]；当读入数据444时，c=[0,0,1,2,1]c=[0,0,1,2,1]c=[0,0,1,2,1]......... 离散化 当数 ...

A. Kuroni and the Gifts Kuroni has n daughters. As gifts for them, he bought nnn necklaces and nnn bracelets: the iii-th necklace has a brightness aia_iai​, where all the aia_iai​ are pairwise distinct (i.e. all aia_iai​ are different), the iii-th bracelet has a brightness bib_ibi​, where all the bi are pairwise distinct (i.e. all bib_ibi​ are different). Kuroni wants to give exactly one necklace and exactly one bracelet to each of his daughters. To make sure that all of them look unique, the ...