- 博客(67)
- 收藏
- 关注
RSS订阅原创 POJ 3368 & UVA 11235 - Frequent values
RMQ应用题。解题思路参考：http://blog.csdn.net/libin56842/article/details/46482803#include#include#include#include#define MAXN 100000+5using namespace std;int num[MAXN],a[MAXN];int n,q,seg_num
2017-05-03 13:13:22
312
原创 2016江苏省CPC省赛 I - Itinerary Planning
DescriptionMike moved to a new city.There are bus stations in the city, each has a unique name. Each bus has its designated schedule, and sequentially docks at a series of bus stations. Bus li
2017-04-28 22:49:05
656
原创 HDU 3183 - A Magic Lamp
题目思路请参考：http://blog.csdn.net/acdreamers/article/details/8692384RMQ请参考：http://blog.csdn.net/liang5630/article/details/7917702代码请参考：#include#include#include#include#include#define MAXN 1003u
2017-04-27 22:26:50
409
原创 POJ 3928 - Ping pong
#include#define MAX_N 20000+5int n,a[MAX_N],c[100000+5],MAX_ai;int pre_more[MAX_N],pre_less[MAX_N],suf_more[MAX_N],suf_less[MAX_N];long long ans;int lowbit(int x){return x&(-x);}void add(int i,i
2017-04-27 19:33:01
434
原创 POJ 3067 - Japan
抽象来说就是求逆序对的问题，虽然放在树状数组的章节里，但不一定要用树状数组，归并排序也可以……#include#include#define MAX 1000*1000+3using namespace std;struct Road{ int u,v;}road[MAX],tmp[MAX];int n,m,k;long long cnt;bool cmp(Road a,Ro
2017-04-25 20:34:48
305
原创 codeforces 792D - Paths in a Complete Binary Tree
#include#include#define lowbit(x) x&(-x)typedef long long ll;using namespace std;ll n,q,num,root;string s;int main(){ scanf("%I64d%I64d",&n,&q); root=(n+1)/2; for(ll q_i=1;q_i<=q;q_i++) {
2017-04-24 21:27:53
413
原创 UVA 11768 - Lattice Point or Not
首先本题需要用到扩展欧几里得算法……关于exgcd算法的一点简略证明：那么，对于函数exgcd(a,b)=(d,x,y)，其中d满足d=gcd(a,b); (x,y)满足ax+by=d;则exgcd(b,a mod b)=(d,x',y')，而此时，使用 x = y' ; y = x' - floor(a/b) * y' = x' - floor(a/b) *
2017-04-23 20:33:57
307
原创 HDU 6008 - Worried School
Worried SchoolTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 112 Accepted Submission(s): 34Problem DescriptionYou may alread
2017-04-22 20:52:37
1315
原创 codeforces 798B - Mike and strings
感觉自己好咸鱼呀……B题写了这么久，虽然可以算作1A（忽略一次少include一个头文件的CE）……思想很简单，每次选定一个字符串作为目标字符串，然后把其他所有字符串都当做测试字符串，计算出总共需要的步数，再在这些计算出的步数中找到最小的那个就是答案。#include#include#includeusing namespace std;char str[53][105];int
2017-04-22 00:13:12
997
原创 hihocoder 1284 - 机会渺茫
N有N_cnt个约数，M有M_cnt个约数，那么总共有N_cnt * M_cnt种对应情况。假设其中有D_cnt个对应结果是相等的，而这D_cnt个数正好是gcd(N,M)的所有约数。例如：N=18 , M=4218 = 1 * 18 ; 2 * 9 ; 3 * 6 ; N_cnt=642 = 1 * 42 ; 2 * 21 ; 3 * 14 ; 6 * 7 ; M_cnt=8
2017-04-19 23:04:15
374
原创 HDU 4675 - GCD of Sequence
解题思路参考：http://www.cnblogs.com/kuangbin/archive/2013/08/13/3255943.html如果gcd(b[1...n])=d，那么b[1...n]中每个b[i]都应是d的倍数，而b[1...n]是从a[1...n]修改k个数进而变过来的，那么，假设a[1...n]中有cnt个a[i]本来就是d的倍数，那么首先 ( n-cnt )个不
2017-04-17 22:16:11
405
原创 HDU 1222 - Wolf and Rabbit & HDU 1108 - 最小公倍数
水题，只是想借此记一下gcd函数的模板#includeint gcd(int m,int n){return n==0 ? m : gcd(n,m%n);}int main(){ int n,m,t; scanf("%d",&t); while(t--){ scanf("%d%d",&m,&n); if(gcd(n,m)==1) p
2017-04-17 13:35:58
335
原创 POJ 2377 - Bad Cowtractors
1A水过，kruskal#include#includeusing namespace std;int n,m;struct node{ int u,v,c;}edge[20000+5];bool cmp(node a,node b){return a.c>b.c;}int par[1005],rank[1005];void init(){ for(int i=1;i<=
2017-04-12 12:31:36
341
原创 POJ 3268 - Silver Cow Party
题目翻译来自：http://poj.org/showmessage?message_id=97785描述一只母牛从N块田中的任一块(1≤N≤1000)去参加盛大的母牛聚会，这个聚会被安排在X号田(1≤X ≤N)。一共有M(1 ≤ M ≤ 100,000)条单行道分别连接着两块田，且通过路i需要花Ti(1≤Ti≤100)的时间。每头母牛必需参加宴会并且在宴会结束时回到自己的领地，但是
2017-04-10 22:43:25
270
原创 POJ 2253 - Frogger
参考：http://www.cnblogs.com/tanhehe/p/3169865.html另外请参考：http://blog.csdn.net/PKU_ZZY/article/details/52434239#include#include#define N 205#define INF 1e60double max(double a,double b){return a>b
2017-04-09 21:39:30
297
原创 POJ 2240 - Arbitrage
Bellman-Ford算法的应用。请参考：http://www.cnblogs.com/freezhan/p/3238968.html至于里面说的：注意： 这里的松弛操作要循环 N 次才能过, 书上的松弛操作一直都是 N-1 次 对于为什么是 N 或者 N-1 次一直没有理解清楚是因为这题目
2017-04-09 10:42:34
313
原创 codeforces 279B - Books
二分查找。#includeint n,t,a[100000+5];bool judge(int num){ int sum=0; for(int j=1;j<=num;j++) sum+=a[j]; if(sum<=t) return true;//先把第一本书作为开始，读num本书，算出耗时 for(int i=2;i<=n-num+1;i++) { sum=sum-a[
2017-04-07 23:18:38
352
原创 POJ 2524 - Ubiquitous Religions
并查集水题。#include#includeusing namespace std;int m,n;int par[50000+5],rank[50000+5];void init() { for(int i=1;i<=n;i++) par[i]=i,rank[i]=0; } int find(int x) { if(par[x] == x)
2017-04-07 23:13:23
251
原创 POJ 3723 - Conscription
运用kruskal算法的最大生成树的基础题，直接1A。具体请参考：http://www.cnblogs.com/liangrx06/p/5083763.html#include#includeusing namespace std;int n,m,r;struct Node{ int x,y,d;}node[50000+5];int par[20000+5];bool cm
2017-04-06 22:51:32
359
原创 HDU 3345 - War Chess
#include#include#includeusing namespace std;int n,m,mv;char map[103][103];bool vis[103][103];struct type{ int i,j,mv; bool operator<(const type &oth)const { return mv<oth.mv
2017-04-05 23:06:11
318
原创 POJ 3522 - Slim Span
在所有生成树里，找到“最大边权值 减去 最小边权值”最小的那棵生成树。那么，对于已经某个确定的最小边的所有生成树，我们找到最小生成树，它的“最大边权值 减去 最小边权值”就是这些生成树里最小的。然后，我们枚举最小边即可。#include#include#includeusing namespace std;#define N 102#define M 5000#define
2017-04-05 17:32:33
402
原创 POJ 2388 - Who's in the Middle
排序的水题，主要拿来测试了一下快速排序和归并排序哪个速度快一点。#include#includeusing namespace std;void merge(int num[],int st,int md,int ed){ int l_len=md-st+1,r_len=ed-md; int l[l_len+2],r[r_len+2]; for(int i=1;
2017-04-04 10:26:26
342
原创 POJ 2236 - Wireless Network
并查集的应用。#include#includeusing namespace std;struct type{ int x,y;//电脑的坐标 bool state;//电脑是否已修复，已修复为1，未修复为0}c[1005];int par[1005],rank[1005],n,d;void init(int n){ for(int i=1;i<=n;i++){ par
2017-04-02 11:05:27
255
原创 POJ 1182 - 食物链
请参考《挑战程序设计竞赛第二版》P87~90 （并查集一章节）刚开始一直runtime error……一直查不出来……最后发现MAXN定义成50005太小了，要3*50005才行……真是蠢……#include#define MAXN 3*50000+5int par[MAXN],rank[MAXN];void init(int n){ for(int i=1;i<=n;i++)
2017-03-31 22:44:29
380
原创 POJ 2010- Moo University - Financial Aid
引用来自http://www.cnblogs.com/iiyiyi/p/4738644.html的思路【题目大意】给出C头奶牛的SAT成绩和申请奖学金，选出N头牛，使得总奖学金在≤F的情况下奶牛SAT成绩的中位数最大。【思路】假设before[i]表示前i头奶牛中n/2头奶牛奖学金总额的最小值，而after[i]表示后i头奶牛中n/2头奶牛奖学金总额的最小值。将C头奶牛按照SAT
2017-03-30 22:15:06
308
原创 POJ 3614 - Sunscreen
把牛按minSPF从小到大排序一下，防晒霜按SPF排序一下。然后遍历防晒霜lontion[1...L]，对于lotion[i]，把所有满足minSPF小于等于lontion[i].SPF的牛都找出来，入队。我们将这个队列定义为按cow[i].maxSPF的从小到大排序的优先队列，那么，每次取出的队首，都是当前要求最苛刻（SPF要求范围最小的）那头牛，先满足这些牛，如果当前这 种防晒霜能满足
2017-03-29 21:49:54
323
原创 codeforces 355C - Vasya and Robot
因为在允许的情况下，必然是左右手交替进行，这样不会增加多余的无谓的能量。然后根据不同的分界点，肯定会产生左手或右手重复使用的情况，这是就要加上Qr/Ql * 次数。一开始的想法，很直接，枚举每个分界点，计算出总共要用的能量，取最小的那个即是答案：#include#includeusing namespace std;int main(){ int n,l,r,Q_l,Q
2017-03-26 10:28:53
307
原创 POJ 3187 - Backward Digit Sums
依然是非常暴力的DFS，1~n这n个数字，全排列一遍，找到第一个符合的排列就是答案。#include#includeusing namespace std;int n,sum,num[11],finish=0;int cal(){ int temp[11][11]; for(int i=0;i<n;i++) temp[1][i]=num[i]; for(int i=2;i<=n
2017-03-24 10:12:15
284
原创 POJ 3050 - Hopscotch
超级大水题，一次过……以5*5的map的某一格 ( i , j ) 为起点，dfs到deep=6，直接把得到的那个数字插入到set容器里（set容器保证每个元素不重复），然后 i=1 to 5 { j = 1 to 5{...} } ，把每一格都作为起点进行搜索，最后set::size()就是答案#include #include#includeusing namespa
2017-03-23 21:26:41
276
原创 POJ 1753 - Flip Game
港真，这题，DFS太暴力了……就是16格，flip或者不flip，2^16情况全部测试一遍，找那个使得 judge() == 1（满足全棋盘同色），同时step最小。#include#includeusing namespace std;int chess[4][4];int dx[4]={0,-1,0,+1};int dy[4]={+1,0,-1,0};int cnt=99999
2017-03-23 15:44:29
287
原创 POJ 3669 - Meteor Shower
#include#include#includeusing namespace std;int dx[4]={+1,0,-1,0};int dy[4]={0,+1,0,-1};struct type{ int x,y,t;}meteor[50000+5],now,next;int n,map[305][305],latest;bool vis[305][305];int bf
2017-03-21 22:26:16
256
原创 POJ 1979 - Red and Black
“.”能走，“#”不能走，“@”为起点，求所有能走到的地方。BFS：#include#include#includeusing namespace std;int w,h;int dir[4][2]={{0,+1},{-1,0},{0,-1},{+1,0}};char t[23][23];bool vis[23][23];struct type{ int x,y;}s
2017-03-20 22:13:34
267
原创 HDU 1372 - Knight Moves
（感觉自己越来越懒了，题目都不用贴了……）谨以此纪念一下自己学会的第一道BFS~#include#include#includeusing namespace std;struct type{ int x,y,step;}st,ed;bool s[10][10];int dir[8][2] = {{-1,+2},{-2,+1},{-2,-1},{-1,-2},{1,-2},
2017-03-20 20:39:40
272
原创 codeforces 761D - Dasha and Very Difficult Problem
time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDasha logged into the system and began to solve problems. One of
2017-03-19 21:02:55
431
原创 POJ 3258 - River Hopscotch
题目大意：题目很长哈，简单来说，数轴上有n个石子，第i个石头的坐标为Di，现在要从0跳到L，每次条都从一个石子跳到相邻的下一个石子。现在FJ允许你移走M个石子，问移走这M个石子后，相邻两个石子距离的最小值的最大值是多少，因为移动有很多种方法，每一种有一个最小值距离，这些最小值里面的最大值（我之所以解释最后一句，是因为我兄弟他没懂--其实不是我翻译的，嘿嘿）。思路：在这里二分的对象当然是距离咯，
2017-03-16 22:27:05
328
原创 POJ 1456 - Supermarket
和HDU 1789 - Doing Homework again一个套路#include#includeusing namespace std;struct type{ int profit; int deadline;}prod[10000+5];bool day[10000+5];bool cmp(type x,type y){ return x.profit>y.pr
2017-03-16 21:45:10
244
原创 HDU 4430 - Yukari's Birthday
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5505 Accepted Submission(s): 1320Problem DescriptionToday is Yukari's n-th b
2017-03-14 22:58:28
310
原创 codeforces 782B - The Meeting Place Cannot Be Changed
time limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe main road in Bytecity is a straight line from south to north
2017-03-13 23:08:44
394
原创 codeforces 779D - String Game
time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputLittle Nastya has a hobby, she likes to remove some letters from
2017-03-13 22:57:47
392
原创 POJ 2456 - Aggressive cows
DescriptionFarmer John has built a new long barn, with N (2 His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the
2017-03-13 12:32:19
310
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人