ACM

poj 3294 题意：先做个简单替换，然后求替换后的字符串的最长回文串，以及这个最长回文串的开始和结束位置。 思路：manacher。需要注意的是，返回下标的时候如果字符串长度为偶数，那么中间是没有字符的，需要特判一下（我的做法是 left+(ans%2==0)）。

poj3974 题意：求最大长度的回文字串。 思路：manacher裸题，用来练习算法。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年04月18日 星期一 16时32分25秒 4File Name :code/poj/3974.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E6+7; 34char st[2*N]; 35int p[2*N]; 36 37int manacher(char *s) 38{ 39 int len = strlen(s); 40 for ( int i = len ; i >= 0 ; i-- ) 41 { 42 s[i+i+2]=s[i]; 43 s[i+i+1]='#'; 44 } 45 s[0]='$'; 46 47 int id = 0 ; 48 int maxlen = 0 ; 49 50 for ( int i = 2 ; i < 2*len+1 ; i++) 51 { 52 if (id+p[id]>i) p[i] = min(p[2*id-i],id+p[id]-i); 53 else p[i] = 1; 54 55 while (s[i+p[i]]==s[i-p[i]]) p[i]++; 56 if (id+p[id]<i+p[i]) id = i; 57 if (p[i]>maxlen) maxlen = p[i]; 58 } 59 return maxlen-1; 60} 61int main() 62{ 63 #ifndef ONLINE_JUDGE 64 freopen("code/in.txt","r",stdin); 65 #endif 66 int cas = 0 ; 67 while (scanf("%s",st)!=EOF) 68 { 69 if (st[0]=='E'&&st[1]=='N'&&st[2]=='D') break; 70 printf("Case %d: %d\n",++cas,manacher(st)); 71 72 } 73 74 #ifndef ONLINE_JUDGE 75 fclose(stdin); 76 #endif 77 return 0; 78}

题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。 于是去学习了一发。 感觉这篇博客讲得最详细manachar算法学习 于是切了个模板题练手。

1657: [Usaco2006 Mar]Mooo 奶牛的歌声 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 634 Solved: 447 [Submit][Status][Discuss] Description # Farmer John’s N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.

1656: [Usaco2006 Jan] The Grove 树木 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss] Description # The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She’s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn’t think you could pass ’through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here’s a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘’ represents Bessie’s start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++ The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she’s starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.

3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题 # Time Limit: 3 Sec Memory Limit: 128 MB Submit: 88 Solved: 79 [Submit][Status][Discuss] Description # 贝茜像她的诸多姊妹一样，因为从约翰的草地吃了太多美味的草而长出了太多的赘肉．所以约翰将她置于一个及其严格的节食计划之中．她每天不能吃多过H(5≤日≤45000)公斤的干草．贝茜只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了．她有一个完整

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 353 Solved: 190 [Submit][Status][Discuss] Description # Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are: 1 @ US$3 + 1 @ US$2 1 @ US$3 + 2 @ US$1 1 @ US$2 + 3 @ US$1 2 @ US$2 + 1 @ US$1 5 @ US$1 Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

1653: [Usaco2006 Feb]Backward Digit Sums # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 349 Solved: 258 [Submit][Status][Discuss] Description # FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this: 3 1 2 4 4 3 6 7 9 16 Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.

代码实现 1#include <iostream> 2#include <vector> 3#include <cstring> 4#include <set> 5#include <algorithm> 6#include <cstdio> 7 8using namespace std; 9const int N=1E4+7; 10int n,k,Q; 11int siz; 12int pos[N]; 13int sum[N]; 14int dis[N]; 15bool vis[N]; 16vector < pair<int,int> > edge[N]; 17 18struct node 19{ 20 int l,r; 21 int id; 22 23 bool operator < (node b)const 24 { 25 if (pos[l]==pos[b.l]) return r<b.r; 26 return pos[l]<pos[b.l]; 27 } 28 29 30}q[N]; 31 32 33void dfs( int u,int val) 34{ 35 vis[u] = true; 36 dis[u+1] = val; 37 38 int Siz = edge[u].size(); 39 for ( int i = 0 ; i < Siz ; i ++) 40 { 41 int v = edge[u][i].first; 42 43 if (!vis[v]) 44 { 45 dfs(v,val+edge[u][i].second); 46 } 47 } 48} 49int main() 50{ 51 52 freopen("in.txt","r",stdin); 53 siz = 100; 54 for ( int i = 0 ; i < 10000 ; i++) pos[i] = i/siz; 55 while (scanf("%d %d %d",&n,&k,&Q)!=EOF) 56 { 57 memset(vis,false,sizeof(vis)); 58 memset(dis,0,sizeof(dis)); 59 memset(sum,0,sizeof(sum)); 60 for ( int i = 1 ;i < n ; i++) 61 { 62 int u = i; 63 int v = i/k; 64 edge[u].push_back(make_pair(v,i)); 65 edge[v].push_back(make_pair(u,i)); 66 } 67 68 for ( int i = 1 ;i <= Q ; i++) 69 { 70 scanf("%d %d",&q[i].l,&q[i].r); 71 q[i].id = i; 72 } 73 74 sort(q+1,q+Q+1); 75 76 dfs(0,0); 77 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1]+dis[i]; 78 } 79}

题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路： dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];

转载自： 原文链接 树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。 在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义 vis = 0，表示该顶点没没有被访问 vis = 1，表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回 vis = 2,，表示该顶点已经被访问，其子孙后代也已经访问完，也已经从该顶点返回 可以vis的3种值表示的是一种顺序关系和时间关系

1652: [Usaco2006 Feb]Treats for the Cows # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 290 Solved: 226 [Submit][Status][Discuss] Description # FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: * The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. * Like fine wines and delicious cheeses, the treats improve with age and command greater prices. * The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). * Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 700 Solved: 393 [Submit][Status][Discuss] Description # Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. Help FJ by determining: * The minimum number of stalls required in the barn so that each cow can have her private milking period * An assignment of cows to these stalls over time

1650: [Usaco2006 Dec]River Hopscotch 跳石子 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss] Description # Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 <= L <= 1,000,000,000). Along the river between the starting and ending rocks, N (0 <= N <= 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L). To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river. Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 <= M <= N). FJ wants to know exactly how much he can increase the shortest distance before he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

1649: [Usaco2006 Dec]Cow Roller Coaster # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description # The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 <= L <= 1,000). The roller coaster comprises a collection of some of the N (1 <= N <= 10,000) different interchangable components. Each component i has a fixed length Wi (1 <= Wi <= L). Due to varying terrain, each component i can be only built starting at location Xi (0 <= Xi <= L-Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component. Each component i has a “fun rating” Fi (1 <= Fi <= 1,000,000) and a cost Ci (1 <= Ci <= 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows’ total budget is B (1 <= B <= 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 562 Solved: 352 [Submit][Status][Discuss] Description # The cows are having a picnic! Each of Farmer John’s K (1 <= K <= 100) cows is grazing in one of N (1 <= N <= 1,000) pastures, conveniently numbered 1…N. The pastures are connected by M (1 <= M <= 10,000) one-way paths (no path connects a pasture to itself). The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

1646: [Usaco2007 Open]Catch That Cow 抓住那只牛 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 915 Solved: 441 [Submit][Status][Discuss] 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 <= 100,000) on a number line and the cow is at a point K (0 <= K <= 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. * Walking: FJ can move from any point X to the points X-1 or X+1 in a single minute * Teleporting: FJ can move from any point X to the point 2*X in a single minute. If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 451 Solved: 226 [Submit][Status][Discuss] Description # 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了’x’。例如下图：

1643: [Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 330 Solved: 278 [Submit][Status][Discuss] Description # 农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。 贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积为N(1<=N<=10,000)个单位面积的部分。 贝茜对选出这样四块草皮的方法数很感兴趣，如果她得到了一个4个单位面积的部分，那么她可以有5中不同的方法选4块草皮：(1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,0,2).顺序是有效的：(4,3,2,1)和(1,2,3,4)是不同的方法。