HihoCoder挑战赛14(2/4)

maksyuki 发表于 比赛 分类，标签:
30 8月 2015
0

A 不等式

描述

给定n个关于X的不等式，问最多有多少个成立。

每个不等式为如下的形式之一：

X < C

X <= C

X = C

X > C

X >= C

输入

第一行一个整数n。

以下n行，每行一个不等式。

数据范围:

1<=N<=50,0<=C<=1000

输出

一行一个整数，表示最多可以同时成立的不等式个数。

样例输入

4
X = 1
X = 2
X = 3
X > 0

样例输出

2

 

题目类型：暴力枚举

算法分析：由于C的范围为[0,1000]，则此时可以从-1~2000枚举X，然后计算满足条件的等式的数量

 

Codeforces Round #318(Div.2) (4/5) (Div.1) (2/5)

maksyuki 发表于 比赛 分类，标签:
30 8月 2015
0

bzoj3224

maksyuki 发表于 oj 分类，标签:
30 8月 2015
0

3224: Tyvj 1728 普通平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 阅读全文 »

BestCoder Round #53(Div.2) (2/4) (Div.1) (1/4)

maksyuki 发表于 比赛 分类，标签:
29 8月 2015
0

xdu1073

maksyuki 发表于 oj 分类，标签:
29 8月 2015
0

1073: Nunchakus

题目描述

输入

输出

样例输入

321 131 2 331 1 3

样例输出

阅读全文 »

xdu1036

maksyuki 发表于 oj 分类，标签:
29 8月 2015
0

1036: 分配宝藏

题目描述

两个寻宝者找到一个宝藏，里面包含着n件物品，每件物品的价值是w[i]。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值， 阅读全文 »

xdu1029

maksyuki 发表于 oj 分类，标签:
28 8月 2015
0

1029: 数一的逆袭

题目描述

数一是一个穷屌丝兼程序猿，是社会受剥削的底层人物，但是他有一个梦想，就是博得女神的欢心。这天，数一的女神说:"一直活在二次元的屌丝啊，一直活在二进制的程序猿啊，你们这群二货快告诉我这堆2是怎么回事？" 阅读全文 »

xdu1028

maksyuki 发表于 oj 分类，标签:
28 8月 2015
0

1028: 数字工程

题目描述

ACM实验室开启了一个数字工程项目，希望把正整数n通过一些特殊方法变成1。

可采用的方法有：（1）减去1；（2）除以它的任意一个素因子。 每操作一次消耗一个单位的能量。

阅读全文 »

lightoj1427

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1427 - Substring Frequency (II)

InputA string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string Pi, where the strings contain lower case English alphabets only. You have to find the number of times Pi occurs as a substring of T.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 106). Each of the next n lines contains a string Pi (1 ≤ |Pi| ≤ 500).

Output

For each case, print the case number in a single line first. Then for each string Pi, report the number of times it occurs as a substring of T in a single line.

Sample Input

Output for Sample Input
25ababacbabcababa

ac

a

abc

3

lightoj

oj

light

lit

 Case 1:2314

1

Case 2:

1

1

0

Notes

  1. Dataset is huge, use faster I/O methods.
  2. If S is a string then |S| denotes the length of S.

 

题目类型：AC自动机

算法分析：将子串插入到Trie树中，然后使用cnt数组统计在文本串T中，相应子串出现的个数即可，注意子串可能出现重复的情况！！！由于n比较小，所以可以使用O(n^2)的枚举将标号后面重复的相应子串的个数求解得到

 

lightoj1369

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1369 - Answering Queries

long long f( int A[], int n ) { // n = size of AThe problem you need to solve here is pretty simple. You are give a function f(A, n), where A is an array of integers and n is the number of elements in the array. f(A, n) is defined as follows:

long long sum = 0;

for( int i = 0; i < n; i++ )

for( int j = i + 1; j < n; j++ )

sum += A[i] - A[j];

return sum;

}

Given the array A and an integer n, and some queries of the form:

1)      0 x v (0 ≤ x < n, 0 ≤ v ≤ 106), meaning that you have to change the value of A[x] to v.

2)      1, meaning that you have to find f as described above.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers: n and q (1 ≤ n, q ≤ 105). The next line contains n space separated integers between 0 and 106 denoting the array A as described above.

Each of the next q lines contains one query as described above.

Output

For each case, print the case number in a single line first. Then for each query-type "1" print one single line containing the value of f(A, n).

Sample Input

Output for Sample Input
13 51 2 310 0 310 2 1

1

 Case 1:-404

Note

Dataset is huge, use faster I/O methods.

 

题目类型：简单数学

算法分析：首先将sum求出来，然后更新时只更新a[x]的值所引起的变化，查询时直接输出结果，注意两个int型变量相乘的中间结果也是int的，可能会溢出！！！

 

lightoj1337

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1337 - The Crystal Maze

To be more exact, the maze can be modeled as an M x N 2D grid where M denotes the number of rows and N denotes the number of columns. There are three types of cells in the grid:You are in a plane and you are about to be dropped with a parasuit in a crystal maze. As the name suggests, the maze is full of crystals. Your task is to collect as many crystals as possible.

  1. A '#' denotes a wall, you may not pass through it.
  2. A 'C' denotes a crystal. You may move through the cell.
  3. A '.' denotes an empty cell. You may move through the cell.

Now you are given the map of the maze, you want to find where to land such that you can collect maximum number of crystals. So, you are spotting some position x, y and you want to find the maximum number of crystals you may get if you land to cell (x, y). And you can only move vertically or horizontally, but you cannot pass through walls, or you cannot get outside the maze.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing three integers M, N and Q (2 ≤ M, N ≤ 500, 1 ≤ Q ≤ 1000). Each of the next M lines contains N characters denoting the maze. You can assume that the maze follows the above restrictions.

Each of the next Q lines contains two integers xi and yi (1 ≤ xi ≤ M, 1 ≤ yi ≤ N) denoting the cell where you want to land. You can assume that cell (xi, yi) is empty i.e. the cell contains '.'.

Output

For each case, print the case number in a single line. Then print Q lines, where each line should contain the maximum number of crystals you may collect if you land on cell (xi, yi).

Sample Input

Output for Sample Input
14 5 2..#...C#C.##..#..C#C

1 1

4 1

 Case 1:12

Note

Dataset is huge, use faster I/O methods.

 

题目类型：记忆化搜索

算法分析：本题其实求每一个连通块中所有水晶的数量，如果对于每个查询都调用一次DFS或者是BFS会TLE，此时应该使用记忆化搜索的思想使能通过调用一次搜索算法计算出的所有节点(在同一个连通块中)的水晶数量记录下来，然后对于已经计算过的查询操作(查询的坐标在已经计算过的连通块中)，则直接输出相应的记录即可

 

lightoj1325

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1325 - Distributing Chocolates

InputNow as the result can be large, I asked for the result modulo 100 000 007 (a prime). But after that I found that this problem is easier than I thought. So, I changed the problem a little bit. I will give you the number of my cousins K and the result modulo 100 000 007. Your task is to find the number of chocolates I have bought. If there are several solutions, you have to find the minimum one.I have bought n chocolates for my young cousins. Every chocolate is different. So, in the contest I added the problem that how many ways I can distribute the chocolates to my K cousins. I can give more chocolates to some cousins, and may give no chocolate to some. For example, I have three cousins and I bought 2 chocolates a and b. Then I can distribute them in the following 9 ways:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers K (2 ≤ K ≤ 107) and result (0 ≤ result < 100000007). You can assume that the input data is valid, that means a solution exists.

Output

For each case, print the case number and the minimum possible number of chocolates I have bought.

Sample Input

Output for Sample Input
23 92 100 Case 1: 2Case 2: 23502611

 

题目类型：离散对数

算法分析：直接使用BSGS算法求解即可

 

lightoj1319

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1319 - Monkey Tradition

1)       There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.In 'MonkeyLand', there is a traditional game called "Bamboo Climbing". The rules of the game are as follows:

2)       Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.

3)       When the whistle is blown, the monkeys start climbing the bamboos and they are not allowed to jump to a different bamboo throughout the game.

4)       Since they are monkeys, they usually climb by jumping. And in each jump, the ith monkey can jump exactly pi meters (pi is a prime). After a while when a monkey finds that he cannot jump because one more jump may get him out of the bamboo, he reports the remaining length ri that he is not able to cover.

5)       And before the game, each monkey is assigned a distinct pi.

6)       The monkey, who has the lowest ri, wins.

Now, the organizers have found all the information of the game last year, but unluckily they haven't found the height of the bamboo. To be more exact, they know N, all pi and corresponding ri, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 12). Each of the next n lines contains two integers pi (1 < pi < 40, pi is a prime) and ri (0 < ri < pi). All pi will be distinct.

Output

For each case, print the case number and the minimum possible value of L that satisfies the above conditions. If there is no solution, print 'Impossible'.

Sample Input

Output for Sample Input
235 47 6

11 3

4

2 1

3 2

5 3

7 1

 Case 1: 69Case 2: 113

 

题目类型：CRT

算法分析：直接使用中国剩余定理求解即可，注意在迭代求解时要注意%M防止溢出ans = (ans % M + M) % M，本题不存在Impossible的情况

 

lightoj1294

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1294 - Positive Negative Sign

-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12Given two integers: n and m and n is divisible by 2m, you have to write down the first n natural numbers in the following form. At first take first m integers and make their sign negative, then take next m integers and make their sign positive, the next m integers should have negative signs and continue this procedure until all the n integers have been assigned a sign. For example, let n be 12 and m be 3. Then we have

If n = 4 and m = 1, then we have

-1 +2 -3 +4

Now your task is to find the summation of the numbers considering their signs.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing two integers: n and m (2 ≤ n ≤ 109, 1 ≤ m). And you can assume that n is divisible by 2*m.

Output

For each case, print the case number and the summation.

Sample Input

Output for Sample Input
212 34 1 Case 1: 18Case 2: 2

 

题目类型：数学题

算法分析：直接模拟计算会TLE，这里应该将负数项和正数项分开，发现每一个序列都构成一个等差序列，然后直接使用公式计算出两个序列的和，最后两个序列和再相减即可

 

lightoj1266

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1266 - Points in Rectangle

InputAs the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer q (1 ≤ q ≤ 30000) denoting the number of queries. Each query is either one of the following:

1)      0 x y, meaning that you have got a new point whose co-ordinate is (x, y). But the restriction is that, if a point (x, y) is already listed, then this query has no effect.

2)      1 x1 y1 x2 y2 meaning that you are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).

You can assume that the values of the co-ordinates lie between 0 and 1000 (inclusive).

Output

For each case, print the case number in a line first. Then for each query type (2), you have to answer the number of points that lie inside that rectangle. Print each of the results in separated lines.

Sample Input

Output for Sample Input
190 1 10 2 6

1 1 1 6 6

1 2 2 5 5

0 5 5

1 0 0 6 5

0 3 3

0 2 6

1 2 1 10 10

 Case 1:202

3

Note

Dataset is huge, use faster I/O methods.

 

题目类型：二维树状数组

算法分析：由于题目中点的坐标最大值<=1000，所以可以直接使用二维树状数组存图，再维护一个布尔数组hasval[x][y]表示(x,y)处是否有点，如果有则不进行UpDate操作，反之则UpDate，每次直接查询矩阵中有多少点即可

 

lightoj1259

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1259 - Goldbach`s Conjecture

Every even integer, greater than 2, can be expressed as the sum of two primes [1].Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Now your task is to check whether this conjecture holds for integers up to 107.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).

Output

For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where

1)      Both a and b are prime

2)      a + b = n

3)      a ≤ b

Sample Input

Output for Sample Input
264 Case 1: 1Case 2: 1

Note

  1. An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, ...

 

题目类型：素数筛+枚举

算法分析：使用Euler筛将素数表预先打出，然后对于每个读入的n，枚举小于等于n/2的素数，满足条件的cnt自加即可

 

12345 下一页 最后一页