#include<iostream>
using namespace std;
#define MAXSIZE 10000
class QElemType
{
public:int x,y;
};
class SQueue
{
public:int len;int front;//头指针，若队列不空，指向队列头元素int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置QElemType base[MAXSIZE];int InitQueue();//初始化一个队伍int QueueLength();//求队伍长度int EnQueue(QElemType e);//插入元素为e的新的队尾元素int DeQueue(QElemT...
阅读全文
很早以前做的了，拿出来记录下。
#include<stdio.h>
#include<string.h>
const int N=100001;
struct Node
{int v;struct Node *next;Node(int n=0,struct Node *P=NULL){v=n;next=P;}
}node[N];
struct Range{int b,e;
}range[N];
bool visited[N];
int c[N];
int n;
void Dfs(int p,int &id);
inline int Lowbit(int x){return x&(-x);
}
void Modify(int i,int v);
int Sum(int n);
int m...
阅读全文
#include<iostream>
using namespace std;
int main()
{char str1[10];char str2[10];char ch;int turn;int tempint;int i;int guess[2];//0代表左边那个,1代表右边那个while(1){guess[0]=0;guess[1]=11;while(1){cin>>tempint; if(!tempint)return 0;cin>>str1;cin>>str2;if(strcmp(str1,"too")==0){if(strcmp(str2,"high")==0){if(tempint<=guess[0]){guess[1]=tempint;continue;}else{if(tem...
阅读全文
自从上次偶尔用了一次线段树后就很喜欢这东西，做各种区间统计挺有用的。抽空又玩了下3468。也是一道很常见的数段树应用，统计区间的和，有时候又要更新区间的值。
#include<iostream>
using namespace std;
class TreeNode
{
public:int lIndex,rIndex;TreeNode *lNode;TreeNode *rNode;__int64 inc;__int64 sum;
};
//根据给定的数组建树
void BuildTree(TreeNode *tNode,int lIndex,int rIndex)
{tNode->lIndex...
阅读全文
check out后，这几天刚好闷骚期，随便玩了一道，典型的动态规划。一开始wrong answer，后来发现sumit时候忘记把测试时候ifstream 改回来，还有根据讨论，要用long double，改了一下就ok了。
开始DP前先推导下均方差公式，发现均方差就等于sqrt( sum(Xi^2)/n - (sum/n)^2 )，因为sum和n 已知，所以问题变成了求sum(Xi^2)/n的最小值，即每个矩形块的值的平方和的总和。
subChessSquare[i][j][h][w][n] 表示 以(i,j)为起点...
阅读全文
水题一道，关键是理解题目为最小生成树。纯粹为了复习并查集和Kruscal最小生成树。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Edge
{
public:
int nId1,nId2;
int length;
};
class LinkNode
{
public:
LinkNode()
{
nodeID=-1;
length=-1;
nextNode=NULL;
}
int nodeID;
int length;
LinkNode* nextNode;
};
class Node
{
public:
No...
阅读全文
一道world final的水题。说起这道题还有个小故事，我在msra当 intern时的舍友，曾经去面google总部inern时候被问的一道题目和这道题目挺像的，只是从二维变成一维，后来一个同学提起，就顺便刷了下。
最大的难点是理解题目，其实就是顺着题目的意思对每块地的海拔排个序后，一块地一块地的遍历过来就好，不过注意各种极端情况。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
...
阅读全文
很典型的一道并查集，动态的判断距离足够近的点就归为一类。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Node
{
public:
Node()
{
x=y=0.0f;
nodeID=-1;
parent=NULL;
rank=0;
}
Node(double xi,double yi,int id)
{
x=xi;
y=yi;
nodeID=id;
parent=NULL;
}
Node(double xi,double yi)
{
x=xi;
y=yi;
parent=NULL;
}
double ...
阅读全文
初看到这道题一般人的第一个想法基本上就是建图，找最短路。但一想到这个做法的无论代码长度还是算法复杂度都实在浪费时间之后，就决定还不如不做了，觉得应该有简单的做法。
想了下：从外围四个墙的某一个门进来，走到宝藏，最小走几个门，实际就是进门点和宝藏的连线goalLine穿过几个点。
证明不好证，但如果说明大体的思想其实挺简单的：思想有点像两点之间直线最短。不要去管纵横交错的小线段，只管一开始原始...
阅读全文
并查集，思路：将和bug i interact（我觉得“性交”会有误会）的归为一类，看同类的是否有interact行为（性行为），如果有输出Suspicious bugs found!
#include <iostream>
using namespace std;
class Node
{
public:
Node()
{
nodeID=0;
parent=NULL;
rank=0;
}
Node(int id)
{
nodeID=id;
parent=NULL;
rank=0;
}
int nodeID;
Node* parent;
int rank;
};
void MakeSet(Node* node)
{
nod...
阅读全文