↓ 跳过正文
111qqz

技术归档

这里保留完整的技术写作历史。较早的竞赛题解和课程笔记作为归档内容保存，不参与 首页精选；个人日记、面试记录和敏感内容不会在正式站点发布。

2016

hdu 1950 Bridging signals (LIS)

·1 分钟
ACM LIS
题目链接 题意：有两跟柱子并排竖直放置，每根柱子有n个结点，从上往下标号1..n， 两根柱子间的结点间要连线，给出计划连接的情况。a[i]表示左边结点i连接右边结点a[i].但是要求连线不能交叉，所以计划可能不能全部执行。现在问最多能连接多少条线。 思路：由于不能交叉，而左边的结点是按照顺序给出的，所以右边连接的结点只能是越来越大。其实就是求a[i]的最长上升子序列。感觉算是LIS的一个比较巧妙的应用？ 由于n还是很大。所以必须nlogn的做法。

最长上升子序列nlogn解法

·2 分钟
ACM Dp LIS
首先回顾一下n^2的做法。 状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j]) 1for ( int i = 1 ; i <= n ; i++) cin>>a[i]; 2 3 for ( int i = 1 ; i <= n ; i++) 4 { 5 dp[i] = 1; 6 for ( int j = 1 ; j < i ; j++) 7 { 8 if (a[i]>a[j]) 9 dp[i] = max(dp[i],dp[j]+1); 10 } 11 ans = max(ans,dp[i]); 12 } 然后我们发现，使得dp[i]得到同一个值的dp[j]可能有多个，那么选择哪个呢？ 假设 x<y<i，a[x]<a[y],dp[x]==dp[y]，那么我们选择x好还是y好呢？ 显然是x好。为什么？因为选择x潜力大。因为可能在x,y之间存在一个z,满足a[x]<a[z]<a[y],如果选择a[y]，就没有办法选择可能使长度更长的a[z]了。通俗得说。。我们要求的是最长上升子序列。。你一开始就弄那么大。。。后面还上哪上升去啊。。。长度小啊。。。

bzoj 1602: [Usaco2008 Oct]牧场行走 (bfs,优先队列)

·2 分钟
ACM Bfs
Description N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

bzoj1600 [Usaco2008 Oct]建造栅栏 （排列组合）

·2 分钟
ACM 排列组合
勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： *只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

bc #74 div1 1001 || hdu 5636 Shortest Path (floyd？)

·2 分钟
ACM Floyd 图论
题目链接 题意：有一条n个节点的链，节点i和节点j的距离为abs(i-j) 现在新增加三条边，距离也都为1，然后给出m个询问，每组询问给出两个点s,t，问s,t之间的最短距离。 思路：比赛的时候没搞出来。 观察特点，对于大多数点来说，都是没有直接的改变，只是增加了三条边。总的思路是：之前s到t的距离为abs(s-t),通过枚举中间经过的特殊点，观察是否能使得距离减小。

codeforces #346 div 2 C. Tanya and Toys (暴力乱搞)

·2 分钟
ACM Brute Force Set 乱搞
题目链接 题意:有1E9个礼物，第i个礼物价钱是i,然后现在已经有n个不重复的礼物，a[i],m元钱，想尽可能多得买不同种类的礼物，还能买多少个。 思路：先不考虑已经买的，从1连续买到k,然后考虑子啊这个区间内已经买的，等于实际上没有花钱。 反正就是暴力搞啊搞啊。。我也不知道怎么搞。。 结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

codeforces #346 div 2 B. Qualifying Contest (排序)

·2 分钟
ACM 排序
题目链接 题意：给出选手个数n，下面n行每个选手的信息“名字 区域编号 分数”.保证每个区域至少两个选手。问每个区域能否唯一确定一支二人的队伍（尽可能选分数高的，当要选的人里有分数相同的则不能确定。 思路：排序啊。。。然后搞啊。。结果发现思路没缕清。。。在某一个区域中，决定是否能唯一确定队伍的是第二个人和第三个人的成绩，和第一个人无关。 特殊处理一个区域只有两个人参加的，这种情况肯定能唯一确定队伍。 妈蛋，这种傻逼题卡了一个小时。。。。

codeforces #346 div 2 A. Round House

·1 分钟
ACM 算法竞赛
题目链接 水题 乱搞。 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月30日 星期三 23时59分47秒 4File Name :code/cf/#346/A.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; 33int n,a,b; 34int main() 35{ 36 #ifndef ONLINE_JUDGE 37 freopen("code/in.txt","r",stdin); 38 #endif 39 cin>>n>>a>>b; 40 a = a + b; 41 while (a<=0) a+=n; 42 while (a>n) a-=n; 43 cout<<a<<endl; 44 45 #ifndef ONLINE_JUDGE 46 fclose(stdin); 47 #endif 48 return 0; 49}

codeforces 652 B. z-sort (简单构造)

·1 分钟
ACM 构造
题目链接 题意：给出n个元素的序列，问能否得到一个新的序列，使得奇数位置非递减排列，偶数位数非递增排列。 思路：感觉一定可以啊。。。排序以后直接构造。。。

codeforces 334 B. Eight Point Sets (暴力)

·1 分钟
ACM Brute Force
题目链接 题意：给出8个点，问能否构成一个8元素集合，使得x1/* *********************************************** Author :111qqz Created Time :2016年03月31日 星期四 13时39分27秒 File Name :code/cf/problem/334B.cpp ************************************************ */