Bomb
Problem Description
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. 阅读全文 »
BestCoder Round #64(Div.2) (3/4) (Div.1) (2/4)
maksyuki 发表于 比赛 分类，标签: 比赛-bestcoder
30
11月
2015
A Numbers
Problem Description
There is a number N.You should output "YES" if N is a multiple of 2, 3 or 5,otherwise output "NO". 阅读全文 »
hdu1011
28
11月
2015
Starship Troopers
Problem Description
You, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is 阅读全文 »
Codeforces Round #333(Div.2) (5/5) (Div.1) (3/5)
maksyuki 发表于 比赛 分类，标签: 比赛-codeforces
25
11月
2015
A Two Bases
After seeing the "ALL YOUR BASE ARE BELONG TO US" meme for the first time, numbers X and Y realised that they have different bases, which complicated their relations. 阅读全文 »
hdu2844
24
11月
2015
Coins
Problem Description
Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice 阅读全文 »
hdu1171
23
11月
2015
Big Event in HDU
Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into 阅读全文 »
hdu1203
23
11月
2015
I NEED A OFFER!
Problem Description
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱， 阅读全文 »
poj2229
23
11月
2015
Sumsets
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:
1) 1+1+1+1+1+1+1 阅读全文 »
hdu1284
23
11月
2015
hdu2159
22
11月
2015
FATE
Problem Description
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是， 阅读全文 »
BestCoder Round #63(Div.2) (4/4) (Div.1) (3/4)
maksyuki 发表于 比赛 分类，标签: 比赛-bestcoder
21
11月
2015
A sequence1
Problem Description
Given an array a with length n, could you tell me how many pairs (i,j) ( i < j ) for abs(ai−aj) mod b=c.
Input 阅读全文 »
hdu1260
15
11月
2015
Tickets
Problem Description
Jesus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.
Input
There are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:
1) An integer K(1<=K<=2000) representing the total number of people;
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.
Output
For every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.
Sample Input
2
2
20 25
40
1
8
Sample Output
08:00:40 am
08:00:08 am
Source
题目类型：线性DP
算法分析：dp[i]表示前i个人所花费的最小时间，状态转移方程为dp[i] = min (dp[i-1] + aa[i], dp[i-2] + bb[i])。最后规格化输出即可，注意输出时间的格式！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int dp[maxn], aa[maxn], bb[maxn]; int main() { // CFF; int t; scanf ("%d", &t); while (t--) { int n; scanf ("%d", &n); for (int i = 1; i <= n; i++) scanf ("%d", &aa[i]); for (int i = 2; i <= n; i++) scanf ("%d", &bb[i]); dp[1] = aa[1]; for (int i = 2; i <= n; i++) dp[i] = min (dp[i-1] + aa[i], dp[i-2] + bb[i]); bool is_am = true; int hour = 8 + dp[n] / 3600; hour %= 12; if (hour >= 12) is_am = false; int minu = dp[n] % 3600 / 60; int sec = dp[n] % 3600 % 60; if (hour < 10) printf ("0%d", hour); else printf ("%d", hour); if (minu < 10) printf (":0%d:", minu); else printf (":%d:", minu); if (sec < 10) printf ("0%d", sec); else printf ("%d", sec); if (is_am) puts (" am"); else puts (" pm"); } return 0; } |
hdu1176
15
11月
2015
免费馅饼
Problem Description
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。 阅读全文 »
hdu1257
11
11月
2015
最少拦截系统
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天, 阅读全文 »
Codeforces Round #329(Div.2) (2/5)
maksyuki 发表于 比赛 分类，标签: 比赛-codeforces
08
11月
2015
A 2Char
Andrew often reads articles in his favorite magazine 2Char. The main feature of these articles is that each of 阅读全文 »
poj3279
maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化
08
11月
2015
Fliptile
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 × N grid (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 when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".
Input
Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Output
Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
Sample Input
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
Sample Output
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
Source
题目类型：搜索
算法分析：枚举第一行反转的所用情况，然后按照第一行的情况更新之后行，最后第M行若出现’1’，则表示这种情况不成立
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; const int dx[] = {-1, 1, 0, 0, 0}; const int dy[] = {0, 0, -1, 1, 0}; int g[166][166], res[166][166], temp[166][166], tempg[166][166], row, col, ans; string ress; void rev (int x, int y) { for (int i = 0; i < 5; i++) { int tx = x + dx[i], ty = y + dy[i]; if (tx >= 0 && tx <= row - 1 && ty >= 0 && ty <= col - 1) tempg[tx][ty] = !tempg[tx][ty]; } } int SS () { for (int i = 1; i < row; i++) { for (int j = 0; j < col; j++) { if (tempg[i-1][j]) { rev (i, j); ans++; temp[i][j] = 1; } } } for (int i = 0; i < col; i++) if (tempg[row-1][i]) return -1; return ans; } string TT () { string res; for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) res += (char) (temp[i][j] + '0'); return res; } int dfs () { int minval = INF; for (int i = 0; i < (1 << col); i++) { memset (temp, 0, sizeof (temp)); for (int j = 0; j < col; j++) temp[0][col-1-j] = (i >> j) & 1; for (int j = 0; j < row; j++) for (int k = 0; k < col; k++) tempg[j][k] = g[j][k]; ans = 0; for (int j = 0; j < col; j++) if (temp[0][j]) { rev (0, j); ans++; } int tt = SS (); if (tt != -1) { string ss = TT (); if (minval > tt || (minval == tt && ss < ress)) { minval = tt, ress = ss; memcpy (res, temp, sizeof (temp)); } } } if (minval < INF) return minval; else return -1; } int main() { // CFF; while (scanf ("%d %d", &row, &col) != EOF) { for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) scanf ("%d", &g[i][j]); int tt = dfs (); if (tt == -1) puts ("IMPOSSIBLE"); else { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (j == 0) printf ("%d", res[i][j]); else printf (" %d", res[i][j]); } puts (""); } } } return 0; } |