judgeonline专题

1996年分区联赛提高组之三挖地雷 JudgeOnline 1071

1996年分区联赛提高组之三挖地雷 Time Limit:1000MS Memory Limit:65536K Total Submit:197 Accepted:87 Description 　　在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。　　例如： <

http://acm.nyist.net/JudgeOnline/problem.php?pid=431

这一题真是纠结啊，，，一开始用c++超时，，，，，最后全改成c才行，，赤裸裸的并查集应用。。。代码： #include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;int father[10005],num[10005],d[10005];int n,m;

http://acm.nyist.net/JudgeOnline/problem.php?pid=118次小生成树

昨天做的次小生成树的用的是标记法，，，今天用的的是，，，，添边，删边法，，代码： #include<iostream>#include<cstdio>#include<algorithm>#define N 501#define M 9999999#define MM -999999using namespace std;int map[N][N],maxs[N][N],d

http://acm.nyist.net/JudgeOnline/problem.php?pid=211有向图传递闭包问题

这一题是有向图的传递闭包问题，，，而这提的要求就是输出有多少牛可以确定名次的。算法思想：求出每个牛的出度和入度之和看是否等于n-1（n为牛的个数），我这里是用floyd算法写的，，， #include<iostream>#include<algorithm>#include<string.h>#include<cstdio>#define N 105#define FOR(i,s,t)

http://acm.nyist.net/JudgeOnline/problem.php?pid=301递推求值

矩阵运算。。。这一题让我明白了一些事，在做题的时候一定要考虑数的取值范围。。。否者会多吃WA的这一题我就是因为这wa了好几次。。。 #include<iostream>#include<string.h>#include<cstdio>#include<algorithm>#define M 1000007typedef long long L;typedef struct{

http://acm.nyist.net/JudgeOnline/problem.php?pid=148矩阵求fibonacci数列

好久没做关于矩阵运算的题了，今天复习一下，。。核心矩阵幂运算二分法。。。 AC代码： #include<iostream>#include<string.h>#include<cstdio>#include<algorithm>#define M 10000typedef struct{ int s[2][2];}Node;Node a,b;int n;Node c

http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化

这一题一开始是胸有成竹的，本想1A的，但是接二连三的wa了好几次。。。把我满满的自信心消磨殆尽了。。我一遍一遍的寻找错误，就是找不到。。最后实在没办法要了后台的数据。。运行一看。令我大跌眼眶。。。。竟然都对了，，但为什么WA呢？可能是这一题判题写错了？，最后在不抱希望的情况下我把%I64d改成了%lld，竟然AC了，苦逼的孩子。。oj竟然不支持%I64d..... AC代码： #inclu

http://acm.nyist.net/JudgeOnline/problem.php?pid=90

整数划分时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+

http://acm.nyist.net/JudgeOnline/problem.php?pid=58

bfs搜索水题进行时~~~~ #include<iostream>#include<string.h>#include<cstdio>#include<string>#include<queue>using namespace std;int map[9][9]={1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,0,0,1,1,0

http://acm.nyist.net/JudgeOnline/problem.php?pid=221

已知一棵树的先序和中序遍历，求该树的后序遍历，，，例如： DBACEGF ABCDEFG ACBFGED AC代码： #include<stdio.h>#include<string.h>void build(int n,char *s1,char *s2)//构造后序遍历过程{if(n<=0) return;int p=strchr(s2,s1[0])-s2;build(p,s

http://acm.nyist.net/JudgeOnline/problem.php?pid=119

一开始想的是写两个查询一个找最大值，一个找最小值，没想到却tle，，最后写了一个查询，，却莫名其妙的过了，杯具的线段树求法~~~~ #include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<climits>#include<algorithm>using namespace std;co

http://acm.nyist.net/JudgeOnline/problem.php?pid=150

栈的应用水题，， #include<string>#include<stack>#include<string.h>#include<iostream>using namespace std;string a[20];int main(){int n;string s,s1;while(cin>>n){ stack<char> Q;cin>>s>>s1;int i=0,j=0

http://acm.nyist.net/JudgeOnline/problem.php?pid=510

题意中文不解释。。思路：以每个物品当做图中的顶点，以优惠的价格为边权，建图，这里让求需要的最少金币，故可以转化为最短路问题，这里引入一个超级源点0，可以看做是每个物品都可以和自己交换，但没有优惠价格，当找不到可交换的物品时（只能和自己交换），则返回当前的最短路径长度，即是所需要的最少金币。 #include<iostream>#include<vector>#include<algo

http://acm.nyist.net/JudgeOnline/problem.php?pid=3

一道计算几何求多边形重心问题，题意:已知一多边形没有边相交，质量分布均匀。顺序给出多边形的顶点坐标，求其重心。 1，质量集中在顶点上。n个顶点坐标为(xi,yi)，质量为mi，则重心　　X = ∑( xi×mi ) / ∑mi 　　Y = ∑( yi×mi ) / ∑mi 　　特殊地，若每个点的质量相同，则　　X = ∑xi / n 　　Y = ∑yi / n 2，质量分布均匀。

http://acm.nyist.net/JudgeOnline/problemrank.php?pid=525

可以当做STL的入门题，，杯具的是我竟然忘记考虑字符串最后一个不应定是以5结束，因此总是少一个数据。。 #include<string>#include<set>#include<iostream>#include<cstdio>#include<stdlib.h>using namespace std;int main(){string s;while(cin>>s){mul

http://acm.nyist.net/JudgeOnline/problem.php?pid=520

最大素因子时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 i c e最近正在学习数论中的素数，但是现在他遇到了一个难题：给定一个整数n,要求我们求出n的最大素因子的序数,例如：2的序数是1,3的序数是2,5的序数是3，以此类推. 研究数论是需要很大的耐心的，为了惩罚那些没有耐心读完题目的童鞋，我们规定：1的最大素因子序数是0. 输入有多

幸运三角形http://acm.nyist.net/JudgeOnline/problem.php?pid=491

经典的dfs题，子集的构造方法为难点。。 AC代码： #include<iostream>#include<cstdio>#include<string.h>#define N 25using namespace std;bool num[N][N];int res[N][N];int n,sum,half;void dfs(int cur){if(cur==n+1){su