nyist专题
NYIST 1092 数字分隔（二）
本题是南阳理工学院ACM网站上的一道字符串处理题，很长时间不敲代码了手生得很，果然码了很长时间~ 描述 在一个遥远的国家，银行为了更快更好的处理用户的订单，决定将一整串的数字按照一定的规则分隔开来，分隔规则如下：1、实数的整数部分按照每三个数字用逗号分隔开（整数部分的高位有多余的0时，需先将多余的0过滤后，再进行数字分隔，如：0001234567 输出结果为1,234,56
nyist 364 田忌赛马
田忌赛马 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述 Here is a famous story in Chinese history. "That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes
nyist -- 组队赛（二）
比赛链接：http://acm.nyist.net/JudgeOnline/problemset.php?cid=193 题解报告：http://pan.baidu.com/s/1ntwPVkd 代码： A题：http://blog.csdn.net/u014225783/article/details/23997925 B题：http://paste.ubuntu.com/7268150
和GCD相关的“个数”及“求和”问题——hdu 2588、nyist 1007
hdu 2588 GCD http://acm.hdu.edu.cn/showproblem.php?pid=2588 大意： Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M. 分析：已知(a,b)=k --> (a/k, b/k)=1 所以，问题即是求解有多少个x
nyist 468 Fibonacci数列（六）(Miller-Rabin算法 大数素性测试)
Fibonacci数列（六） 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 大家都知道都知道素数的定义：大于1且只有1和其本身外没有其它因子的正整数。对应的我们可以这样定义"Fibonacci素数"：在Fibonacci数列中大于1且与小于它的Fibonacci数都互质的数。判断Fibonacci数列的第n项是否为"Fibonacci素数
nyist_acm 个人积分赛1（部分题解会补充）
Mirrored String II 看到题解说是马拉车算法，我赛时并没想到（好吧其实我是比赛完才知道有马拉车这个算法） 因为字符串的长度只有1000，直接暴力跑其实就可以了，但是要注意的是；回文串有俩种形式，一种是aba的另一种是baab的形式，这是需要注意的地方 //#pragma GCC optimize(3) //O2优化开启#include<iostream>#incl
Nyist 311 （完全背包）
描述 直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO 输入 第一行： N 表示有多少组测试数据（N<7）。 接下来每组测试数据的第一行有两个整数M，V。 M表示物品种
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