tokers-CSDN博客

原创 Good Bye 2015 (One University One Question) Round III

A. Red packet题意： nn个人分mm元的红包，然后告诉你kk个人获得的红包大小，问你如果你想成为手气王（钱拿的最多），至少需要得到多大的红包，或者输出”Impossible”，如果不可能的话，注意红包必须分完,并且每个人获得的红包大小都是整数(>0)(> 0)分析：首先可以得到kk个人里的最大值MM，设现在剩下的钱是RR，那么首先要成为手气王，就必须得到至少M+1M+1，但是最多是

2016-02-07 13:58:35 1117

原创 LightOJ1021---Painful Bases (状压dp)

As you know that sometimes base conversion is a painful task. But still there are interesting facts in bases.For convenience let’s assume that we are dealing with the bases from 2 to 16. The valid symb

2015-06-09 20:24:36 1346

原创 LightOJ1020(博弈)

Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.Both Alice

2015-06-09 19:03:30 1127

原创 LightOJ1017---Brush (III) (dp)

Samir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his ro

2015-06-08 19:56:52 1327

原创 LightOJ1016---Brush (II) (贪心)

After the long contest, Samee returned home and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in

2015-06-08 18:23:47 925

原创 LightOJ1010---Knights in Chessboard (规律题)

Given an m x n chessboard where you want to place chess knights. You have to find the number of maximum knights that can be placed in the chessboard such that no two knights attack each other.Those who

2015-06-08 15:25:15 1529

原创 LightOJ1013---Love Calculator (dp)

Yes, you are developing a ‘Love calculator’. The software would be quite complex such that nobody could crack the exact behavior of the software.So, given two names your software will generate the perc

2015-06-07 22:10:52 1027

原创 LightOJ1012---Guilty Prince (并查集)

Once there was a king named Akbar. He had a son named Shahjahan. For an unforgivable reason the king wanted him to leave the kingdom. Since he loved his son he decided his son would be banished in a ne

2015-06-07 18:09:02 960

原创 LightOJ1011---Marriage Ceremonies (状压dp)

You work in a company which organizes marriages. Marriages are not that easy to be made, so, the job is quite hard for you.The job gets more difficult when people come here and give their bio-data with

2015-06-06 11:08:45 1330

原创 Codeforces Round #306 (Div. 2)

A.给定一个字符串,问是否存在不重叠的两个串”AB”和”BA”,顺序任意.先从左到右遍历一遍,然后找出最靠左的”AB”的位置和”BA”的位置然后从右往左遍历一遍,找出最靠右的”BA”的位置和”AB”的位置然后比较一下就行了/************************************************************************* > File

2015-06-05 22:14:21 872

原创 LightOJ1009---Back to Underworld (bfs染色)

The Vampires and Lykans are fighting each other to death. The war has become so fierce that, none knows who will win. The humans want to know who will survive finally. But humans are afraid of going to

2015-06-05 13:00:35 1298

原创 LightOJ1008---Fibsieve`s Fantabulous Birthday (规律)

Fibsieve had a fantabulous (yes, it’s an actual word) birthday party this year. He had so many gifts that he was actually thinking of not having a party next year.Among these gifts there was an N x N g

2015-06-05 12:25:32 1309

原创 POJ2407---Relatives(求单个数的欧拉函数)

Description Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such t

2015-06-04 18:24:27 1651

原创 POJ1284---Primitive Roots(求原根个数, 欧拉函数)

Description We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, …, p-1 }. For example, the consecutive power

2015-06-04 18:04:35 1104

原创 LightOJ1007---Mathematically Hard (欧拉函数)

Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.In this problem, you will be given two integers a and b. You have to find the summation o

2015-06-04 17:59:16 1488

原创 LightOJ1006---Hex-a-bonacci(矩阵快速幂)

Given a code (not optimized), and necessary inputs, you have to find the output of the code for the inputs. The code is as follows:int a, b, c, d, e, f;int fn( int n ) { if( n == 0 ) return a;

2015-06-03 21:47:34 1019

原创 LightOJ1005---Rooks(简单组合数学)

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one

2015-06-03 21:10:37 1503

原创 LightOJ1003---Drunk(拓扑排序判环)

One of my friends is always drunk. So, sometimes I get a bit confused whether he is drunk or not. So, one day I was talking to him, about his drinks! He began to describe his way of drinking. So, let m

2015-06-03 10:38:57 1346

原创 LightOJ1002---Country Roads (最短路变形)

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of m

2015-06-02 20:27:40 1091

原创 hdu2227---Find the nondecreasing subsequences(dp+树状数组)

Problem Description How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, …., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subseque

2015-06-02 18:52:33 690

原创 Codeforces Round #240 (Div. 1)---B.Mashmokh and ACM(dp)

Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. I

2015-06-02 12:41:32 1077

原创 POJ1337---A Lazy Worker(dp)

Description There is a worker who may lack the motivation to perform at his peak level of efficiency because he is lazy. He wants to minimize the amount of work he does (he is Lazy, but he is subject

2015-06-01 23:50:14 719

原创 URAL1091---Tmutarakan Exams(dp)

University of New Tmutarakan trains the first-class specialists in mental arithmetic. To enter the University you should master arithmetic perfectly. One of the entrance exams at the Divisibility Depar

2015-05-31 13:12:26 776

原创 hdu5249---KPI(二分+树状数组)

Problem Description 你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。Input 有大约100组数据。每组数据第一行有一个n(1≤n≤10000)

2015-05-31 13:10:41 875

原创 hdu5248---序列变换(二分答案+贪心)

Problem Description 给定序列A={A1,A2,…,An}, 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：Bi/************************************************************************* > File Name: hdu5248.cpp > Author: ALex

2015-05-31 13:08:49 1585

原创 hdu5246---超级赛亚ACMer(贪心)

Problem Description 百小度是一个ACMer，也是一个超级赛亚人，每个ACMer都有一个战斗力，包括百小度。 所谓超级赛亚人的定义，是说如果在对抗中刚好接近极限状态，那就会激发斗志，实力提升.具体来说，就是百小度现在要接受一些ACMer的挑战了，这些ACMer有n个人，第i个人的战斗力是a[i]。 百小度接下来可以自主安排与这n个ACMer的PK顺序，他要想在PK赛中赢过另外一个

2015-05-31 13:06:47 1073

原创 UVA12186--- Another Crisis (树形dp)

Description Download as PDFA couple of years ago, a new world wide crisis started, leaving many people with economical problems. Some workers of a particular company are trying to ask for an increase

2015-05-28 22:04:55 1073

原创 POJ2773---Happy 2006(容斥+二分)

Description Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9…are all relatively prime to 2006.Now your job is eas

2015-05-28 19:46:17 746

原创 hdu4059---The Boss on Mars(容斥原理+前n项的4次方和)

Problem Description On Mars, there is a huge company called ACM (A huge Company on Mars), and it’s owned by a younger boss.Due to no moons around Mars, the employees can only get the salaries per-year

2015-05-28 18:30:20 1013

原创 ZOJ2836---Number Puzzle(容斥原理)

Given a list of integers (A1, A2, …, An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list.InputThe inp

2015-05-28 16:00:02 1032

原创 hdu5245---Joyful(期望)

Problem Description Sakura has a very magical tool to paint walls. One day, kAc asked Sakura to paint a wall that looks like an M×N matrix. The wall has M×N squares in all. In the whole problem we den

2015-05-28 13:45:03 1597

原创 UVA10325--- The Lottery (容斥)

The Sports Association of Bangladesh is in great problem with their latest lottery ‘Jodi laiga Jai’. There are so many participants this time that they cannot manage all the numbers. In an urgent meet

2015-05-27 20:49:30 828

原创 Codeforces Round #305 (Div. 2)D---Mike and Feet(单调栈)

Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-t

2015-05-27 20:09:25 924

原创 Codeforces Round #305 (Div. 2)C---Mike and Frog(扩欧+乱搞)

Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h1 and height of Abol is h2. Each second, Mike waters Abol and Xaniar.So,

2015-05-27 20:08:18 1127

原创 hdu1796---How many integers can you find(容斥原理)

Problem Description Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example,

2015-05-26 21:34:33 691

原创 hdu4135---Co-prime(容斥原理)

Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime

2015-05-26 21:02:21 596

原创 LightOJ1408---Batting Practice (期望,推公式)

After being all out for 58 and 78 in two matches in the most prestigious tournament in the world, the coach of a certain national cricket team was very upset. He decided to make the batsmen practice a

2015-05-26 20:09:24 1243

原创 UVA1347---Tour(dp,双调TSP)

dp[i][j]dp[i][j]表示在1~max(i,j)都已经被走过的情况下,第一个人在i点,第二个人在j点时,走完剩下的点还需要的最短距离规定第一个人领先第二个人所以dp[i][j]dp[i][j]可以转移到dp[i+1][j]dp[i + 1][j]和dp[i+1][i]dp[i + 1][i](等价于dp[i][i+1]dp[i][i + 1])/******************

2015-05-25 20:41:52 813

原创 UVA1025---A Spy in the Metro(简单dp)

dp[i][j]dp[i][j]表示时刻i,在车站j,等待的最少时间有3中方案: 等一分钟往左搭车往右搭车/************************************************************************* > File Name: uva1025.cpp > Author: ALex > Mail: zchao1

2015-05-25 20:03:20 658

原创 hdu4825---Xor Sum(Trie + 贪心)

Problem Description Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个集合，集合中包含了N个正整数，随后 Prometheus 将向 Zeus 发起M次询问，每次询问中包含一个正整数 S ，之后 Zeus 需要在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大，随即同意

2015-05-25 14:59:25 877

线段树总结

空空如也