↓ Skip to main content
111qqz’s blog
  1. Categories/

ACM

2016

poj 3294 Girls' research (manacher,回文串)

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

tmp

·1 min
ACM 算法竞赛
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}

树边，前向边，后向边，横叉边

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

BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster (dp，类似01背包)

·3 mins
ACM 01背包 Dp
# 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.