为什么我用线段数这么不灵活呢？
大概思路是线段数记录某牛之前的坐标小于这个牛的牛的坐标和和牛的个数
然后其他部分线性数组记录
OK，贴代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 20005
class cow
{
public:
int v;
int pos;
cow(){};
~cow(){};
};
bool cmp(cow a,cow b)
{
return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组，保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组，保存小于等于某坐标和索引的牛的个数…又来发解题报告了
这回是树状DP
/*
* 树状DP
* 首先把数据想象成树状的
* 由于输入数据为树状，不需要构建树
* 可令degree[i]为包括i且以i为根节点的所有子节点数量
* dp[i]为删除i后的最大子节点数量或父亲节点数量 （这里我理解了很久）
*/
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[10002];
int dp[10002] = {0}
,degree[10002] = {0}
,isJudged[10002] = {0};
int search(int pos,int &n);
int main()
{
int n,i,a,b;
bool isnone = true;
scanf("%d",&n);…题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528
这题又是线段树+离散化
慢慢的对离散化有点感觉了,但是这题我还是错了3次
题目大意是一层一层地叠板子,问最后能看到几块
输入是板子的开始和结束位置
由于输入的是闭区间线段开始我就构造闭区间线段的线段树,但是后来发现很多问题,
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3277
线段树+离散化
ACM预选赛过去了,可是我们队什么都没拿到,这给我们的打击是相当大的,这也很大程度上体现了我们的不足
一直没能静下心,来,今天决定不能再这么悲伤下去,我要奋斗,继续学习,就从之前的断点线段树开始
题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549
这道题伤了我很久脑筋
因为是a+b+c=d,数据量是1000,很自然地想到a+b=d-c
这样转化为n^2的算法.
但是我开始枚举d-c的集合二分查找a+b的几何不知道为什么WA掉了
后面就想其他的办法,参考了一下别人的做法,我觉得差不多和我一样,然后重写.我也和他一样无耻的用STL库函数了
//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
long length = 1,lth;
LISTYPE lR[LISMAXN];
lR[0] = list[0];
for(int i = 1 ; i < n ; i ++)
{
//二分查找,复杂度 log(n)
int…//Prime连通路模块
#define N 1000 //最大数据规模
#define MAXNUM 3000000 //最大路径长度
typedef double PrimeType;//路径类型
PrimeType PrimeRecord[N];
PrimeType dis[N][N];
int isLined[N] = {1,0};
PrimeType GetPrimeLength(const long n)
{
PrimeType tmpLen = MAXNUM;
long tmpPos = 0,left = n - 1;
PrimeType sumLen = 0;
for(long i = 1 ; i < n ; i ++)
PrimeRecord[i] = dis[0][i];
while(left --)
{
tmpLen = MAXNUM;…//MULDATATYPE为矩阵元素类型,MAXMAT为最大矩阵大小
typedef long MULDATATYPE;
#define MAXMAT 100
#define inf 1000000000
#define fabs(x) ((x)>0?(x):-(x))
#define zero(x) (fabs(x)<1e-10)
struct mat
{
long n,m;
MULDATATYPE data[MAXMAT][MAXMAT];
void operator =(const mat& a);
mat operator +(const mat& a);
mat operator -(const mat& a);
//0-1邻接矩阵
mat operator &(const mat& a);
mat operator |(const mat& a);
};…今天在湖南的OJ上做题,发现不到两小时,他服务器就挂了,但是发现他和POJ上的一些题一样而且是连号的,就到POJ上继续了，我们队出了6题。
A题是POJ的3507 Judging Olympia这题是队友干掉的,我没看
B题是POJ的3508 Hide That Number同样是队友AC掉,我没看
懒惰了，暂时休息一下
这次我只AC了一题（在结束的那一刻，另一题在题目来源地网站上AC了，我们的OJ上仍然WA，我们OJ的Special Judge真是—_—!）
H题是用木棒拼数字，给出木棒数量，要求算出拼出的最大和最小数字
今天战绩还行，AC了5题，今天总体没有太复杂的算法题，不过测试数据强度比之前有所增加 我的钱四题很早就过了，但是第五题很晚才出主要是代码写得太混乱，思路也错了两次 我过的题有五道，分别是ABCDG
A题是计算两个多边形的最近距离
点到直线距离
// (x0,y0)到(x1,y1)和(x2,y2)确定的直线的距离
double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2)
{
//化为ax+by+c=0的形式
double a = y1-y2;
double b = x2-x1;
double c = x1*y2-x2*y1;
double d = (a*x0+b*y0+c)/sqrt(a*a+b*b);
/*
如果是线段判断垂足
double xp = (b*b*x0-a*b*y0-a*c)/(a*a+b*b);
double yp = (-a*b*x0+a*a*y0-b*c)/(a*a+b*b);
double xb = (x1>x2)?x1:x2;…//n每个用例的点个数
//MAXN为最大点个数
//PTYPE为坐标值类型
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN 1005
#define EPS 1e-10
typedef double PTYPE;
struct point
{
PTYPE x,y;
};
struct node
{
PTYPE k;
};
int cmp(const void * a, const void * b)
{
return((*(PTYPE*)a-*(PTYPE*)b>0)?1:-1);
}
node numK[MAXN * MAXN / 2];
point pt[MAXN];
int main()
{
int n , maxNum = 1 , tmpNum = 0;…我没看题,队友很快AC我就没花时间看
DP题,但是我们确实都没想到方法,实在是我们的经验不足
B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位,那么交换次数不变(新增的数为i+1,最大). 如果把新增的数放在第1到i位之间的话有i种放法, 对于每一种fn[i][j]的排列中我们总能找到一种序列使得{(.)(.)()(.)(.)…(i+1)},["()表示一个元素"] 中(i+1)和()交换位置后前i个元素的排列和其相同 又因为(*)的位置可以有i种放法,以此我们发现,fn[i+1][j]=fn[i][j]+fn[i][j-1]×i 继续贴代码:
根的关系:
$$ x1 + x2 + x3 = (-\frac{b}{a}) $$$$ x1 \times x2 + x1 \times x3 + x2 \times x3 = \frac{c}{a} $$$$ x1 \times x2 \times x3 = (-\frac{d}{a}) $$牛顿迭代解方程(x0附近的根)
double Newton_Iterative(double a,double b,double c,double d,double x0)
{
double f0,f0d,x;
x = x0;
do
{
x0 = x;
f0 = ((a * x + b) * x + c) * x + d;
f0d = ( 3 * a * x + 2 * b ) * x + c;
x = x0 - f0 / f0d;
}…校赛个人赛第三场部分解题报告（A,D,F,I）
这次我完成了四道题分别是A,D,F,I
一大半时间我都花在了A上，我犯了很究级的错误
首先是VC6.0的algorithm里没有min函数，而我用min做变量名导致CE4次，找了半天才找出来
校赛个人赛第六，七场总结
这两场比赛体现了英文水平的重要性
第六场的题目超长，用词还诡异，话了很长时间才看懂
这两场题目都比较有难度，第六场我只出了2题
A题是很诡异的统计，是一道纯模拟就能过的题，其他的不多说了
POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了
言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up
大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数
最初的想法很简单
枚举没两个点连成的直线,然后枚举每个点,计算通过这条直线的点的个数,但是这个方法的复杂度为O(n^3)
这题是一道DP问题,我的想法如下:
1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;
2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)
//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
for(int i = 0 ; i <= n ; i ++)
DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
DSet[id] = findP(DSet[id]);
return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
a = findP(a);
b = findP(b);
if(a > b)
a ^= b ^= a ^= b;
DSet[b] = a;
return a;
}