万湖之国

万湖之国的形成
时间限制:10000MS 内存限制:65535K
提交次数:0 通过次数:0

语言:G++;GCC;VC
描述
N国原是一块平原上,没有湖,直到一颗小行星撞入大气层碎成成千上万的碎片,碎片再撞击地面形成
一个一个的坑, 下雨之后,最终形成万湖之国。
现在科学家想用计算机模拟万湖之国形成过程,假设每一块碎片撞击地面,都撞出一个园形坑,现在知道
每一个碎片造成的坑的圆心和半径,问每个坑都注满水后,最终形成多少个湖?

输入格式
第一行一个整数N,1<=N<=100,000,表示坑的数量
此后N行,每一行三个double实数,前两个数是圆心的坐标x和y,最后一个数是圆半径(不大于1000)
(数据随机产生,分布均匀)

 

scauoj[树状数组]繁忙的公路

繁忙的公路
时间限制:6000MS 内存限制:65535K
提交次数:0 通过次数:0

语言:G++;GCC
描述
在一条笔直的大道(单方向行车道)上,汽车川流不息。道路从起点到终点,等距离的标记了1到N,
即起点是1,然后分别是2、3、4…..,终点是N。每一个标记处,安装了智能探头,可以感知
在该点处车辆的增减数量。
一开始,整条道路上,没有车,然后,是不断接收到的智能探头发回的信息,格式如下:
H 5 9
H表明收到的是智能探头的回传信息,5表示标记5处的车辆信息,9表示该处车辆增加了9辆。
同时,在某个时刻,需要查询在一段连续的道路上,共有多少辆车
查询格式如下:
Q 3 10
Q表明收到的是查询,3是起点,10是终点(包括3和10两处)
要求编程实现正确处理上述信息处理和查询

输入格式
第一行一个整数N(1<=N<=1,000,000),表示标记范围是1到N
第二行一个整数M(1<=M<=100,000),表示探头信息(或查询)的总数量
此后M行,每行一个探头信息或查询请求
输出格式
每逢遇到查询的时候,输出查询范围内的有多少辆车,占一行,查询结果最大不超过2的63次方

source

继续阅读“scauoj[树状数组]繁忙的公路”

today

并查集

静态问题:

前缀和数组(两项相见就是区间的和)

动态问题:

树状数组

 

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int main(){

int a[100],n,b[100];

scanf(“%d”,&n);

for(int i=0;i<n;i++){

scanf(“%d”,&a[i]);

}

b[0]=1;

for(int i=1;i<n;i++){

int max=0;

for(int j=i-1;j>=0;j–){

if(a[i]>a[j]&&b[j]>max) max=b[j];

}

b[i]=max+1;

}

printf(“%d”,*max_element(b,b+n));

}

#include
#include
#include
using namespace std;
int L[1000][1000];
char A[1000],B[1000];
int main(){
int i,j;
gets(A);gets(B);
int ca=strlen(A),cb=strlen(B);
for(i=cb;i>=0;i–) L[ca][i]=0;
for(i=ca;i>=0;i–) L[i][cb]=0;
for(i=ca-1;i>=0;i–){
for(j=cb-1;j>=0;j–){
if(A[i]==B[j]) L[i][j]=L[i+1][j+1]+1;
else L[i][j]=max(L[i+1][j],L[i][j+1]);
}
}
printf(“%d”,L[0][0]);
}

#include
#include
#include
using namespace std;
int main(){
int a[100],n,b[100];
scanf(“%d”,&n);
for(int i=0;i=0;j–){
if(a[i]>a[j]&&b[j]>max) max=b[j];
}
b[i]=max+1;
}
printf(“%d”,*max_element(b,b+n));
}

#include<cstdio>
int p[]={0,0,1,1,0,1,0,1}
void printper(int n,int A[],int cur){
if(cur==n){
for(int i=0;i<n;i++)printf(“%d”,A[i]);
putchar(‘\n’);
}
else
{
for(int i=0;i<=9;i++){
int ok=1;
if(cur>0&&!P[A[cur-1]+i])ok=0;
if(ok){
A[cur]=i;
printper(n,Aa,cur+1);
}
}
}
int main() {

return 0;
}

已知中序遍历和后序遍历生成二叉树

已知二叉树的中序遍历序列char ino以及后续遍历序列char post,请用算法生成该二叉树(用二叉树链表的形式储存)

#include<cstdio>
#include<malloc.h>
#include<cstring>
#define OK 1
#define ERROR 0

typedef int Status;
typedef char ElemType;

typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

int n;
Status search(char a[],char ch)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==ch) return i;
}
return -1;
}

Status CrtBT(BiTree &T,char ino[],char post[],int is,int ps,int n)//中序遍历和后序遍历生成二叉树 ,ino末尾下标is+n-1,pos末尾下标ips+n -1
{

int k;
if(n==0) T=NULL;
else
{
k=search(ino,post[ps+n-1]);//先找到中序遍历中后序遍历的最后一个根节点
if(k==-1) T=NULL;
else

{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T) return ERROR;
T->data=post[ps+n-1];
if(k==is) T->lchild=NULL;
else CrtBT(T->lchild,ino,post,is,ps,k-is);
if(k==is+n-1) T->rchild=NULL;
else CrtBT(T->rchild,ino,post,k+1,ps+k-is,n-(k-is)-1);
}
}
return OK;
}

Status Print(ElemType e)
{
printf(“%c”,e);
return OK;
}

Status PreOrderTraverse(BiTree T,Status(*visit)(ElemType))
{
if(T)
{
if(visit(T->data))
if(PreOrderTraverse(T->lchild,visit))
if(PreOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else return OK;
}

int main()
{
BiTree T;
char ino[1000],post[1000];

printf(“输入中序遍历:\n”);
scanf(“%s”,ino);
printf(“输入后序遍历:\n”);
scanf(“%s”,post);
n=strlen(ino);
CrtBT(T,ino,post,0,0,n);
printf(“先序遍历输出:\n”);
PreOrderTraverse(T,Print);
return 0;
}

巧妙暴力2:三角形2

思路利用内切圆半径与三角形三边的关系,以及a^2+b^=c^2减少要循环的变量,只需要循环a,即可通过表达式b和c,一直循环到位等腰直角三角形位置,具体表达式推导如下:

b=t^2-a^2/2t     上面写反了

D  三角形2

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制

描述

著名的数学家毕达哥拉斯可能从来都不曾想过有人居然会问他这样的一个问题:给出一个整数,存在多少个直角三角形,
它的内切圆半径等于这个整数,而且其他边的长度也是整数。既然毕达哥拉斯不可能预见到有计算机的出现,
如果他回答不出来,那谁又能责怪他呢?但是现在既然你有了计算机,那么回答不出来就说不过去了。

 

输入格式

第一行有一个整数n,代表有多少个数据(1<=n<=20)。接下来有n行,每行代表一个数据。一个数据就是一个整数r,内切圆半径(1<=r<=100)。

输出格式

每个数据都必须有相应的输出。两个数据的输出之间有一个空行。
对于每一个数据,如果找不到解,则输出一个空行。如果找到解,就把符合条件的所有直角三角形输出。每个三角形占一行,输出该三角形三边,按由短到长,
必须先输出短边,然后一个逗号,再输出长边。两个三角形之间不能有空行,而且必须按照短边升序排列。

输入样例

2
5
10

输出样例

11,60,61
12,35,37
15,20,25

21,220,221
22,120,122
24,70,74
25,60,65
28,45,53
30,40,50