『POJ 2159』 Ancient Cipher

发表于 2018-02-27 | 更新于 2018-09-15 | 分类于题解

这题简直太水了吧。。
只要对每个字母出现的次数统计并排序
然后分别对应的字母个数相等
就表明一定有转换方式。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;
string s1, s2;
int a[27], b[27];
int main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	cin >> s1 >> s2;
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
	for (register int i = 0; i < s1.size(); ++i)
	{
		a[s1[i] - 'A']++;
	}
	for (register int i = 0; i < s2.size(); ++i)
	{
		b[s2[i] - 'A']++; 
	}
	sort(a, a + 26);
	sort(b, b + 26);
	for (register int i = 0; i < 26; ++i)
	{
		if (a[i] != b[i])
		{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

计算凸多边形的面积

发表于 2018-02-07 | 更新于 2018-09-10 | 分类于讲解

题目

计算凸多边形的面积（pol）

问题描述：
按一定的顺序（顺、逆时针）给出一个多边形的各顶点坐标，求该多边形的面积。
输入：
第一行包含一个n，表示多边形顶点的个数( 0<=n<=100)
第2行到第n+1行，每行两个整数x，y（-10000<=x，y <= 10000）
输出：
输出有且只有一行，包含一个数s，s为多边形的面积，保留一位小数
样例：
pol.in
3
0 0
0 3
3 0

pol.out
4.5
题目及测试数据: https://github.com/Leoleepz/OI-Codes/tree/master/%E4%BB%BB%E6%84%8F%E5%A4%9A%E8%BE%B9%E5%BD%A2%E9%9D%A2%E7%A7%AF

第一种方法即为朴素的向量方法。我们可以把凸多边形拆成多个三角形的面积去做。我们会发现，如果用原点去构造三角形来操作，最终结果就是（逆时针坐标乘积-顺时针坐标乘积）÷2.

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#pragma warning(disable:4996) 

#define ComputeTriangleVectorArea CTVA
using namespace std;
struct Point
{
	double x, y;
};
vector <Point> Points;
double ComputeTriangleVectorArea(Point p1, Point p2, Point p3)
{   
    return (double)0.5 * ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y));   
}
double Compute(vector <Point> PointSet)
{
	if (PointSet.empty()) return 0.0;
	double area = 0.0;
	Point O;
	O.x = O.y = 0;
	for (register vector<Point>::iterator ii = PointSet.begin(); ii != PointSet.end() - 1; ++ii)
	{
		area += CTVA(O,(*ii),(*(ii + 1)));
	}
	area += CTVA(O,PointSet[PointSet.size() - 1], PointSet[0]);
	return abs(area);
}
int N;
int main()
{
	freopen("pol.in", "r", stdin);
    freopen("pol.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin >> N;
	for (register int i = 1; i <= N; ++i)
	{
		Point tmp;
		cin >> tmp.x >> tmp.y;
		Points.push_back(tmp);
	}
	printf("%0.1lf\n",Compute(Points));
	return 0;
}

第二种方法我脑洞了一下，用了定积分的方法。定积分有正有负，依次求和，重复部分由于正负会相互抵消，最后剩下的总面积的绝对值就是多边形的面积。

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#pragma warning(disable:4996) 
using namespace std;
struct Point
{
	double x, y;
};
vector <Point> Points;
inline double LinearIntegration(Point p1, Point p2)
{
	return (double)0.5 * (p2.x - p1.x) * (p2.y + p1.y);
}
inline double ComputeArea(vector <Point> PointSet)
{
	if (PointSet.empty()) return 0;
	double area = 0;
	for (register vector<Point>::iterator ii = PointSet.begin(); ii != PointSet.end() - 1; ++ii)
	{
		area += LinearIntegration((*ii),(*(ii + 1)));
	}
	area += LinearIntegration(PointSet[PointSet.size() - 1], PointSet[0]);
	return abs(area);
}
int N;
int main()
{
	freopen("pol.in", "r", stdin);
    freopen("pol.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin >> N;
	for (register int i = 1; i <= N; ++i)
	{
		Point tmp;
		cin >> tmp.x >> tmp.y;
		Points.push_back(tmp);
	}
	printf("%0.1lf\n",ComputeArea(Points));
	return 0;
}

米勒-拉宾素数判定 MR Prime Detect

发表于 2018-02-05 | 更新于 2018-09-10 | 分类于讲解

首先需要知道两个定理:

1、费马小定理：假如$p$是素数，且$\gcd(a,p)=1$，那么 $a(p-1)≡1(\text{mod}\ p)$。不知所云的萌新请点击此处‍自行脑补一下

2、二次探测定理：如果$p$是素数，$x$是小于$p$的正整数，那么要么$x=1$，要么$x=p-1$。

　　证明：这是显然的，因为相当于$p$能整除$(x+1)(x-1)$。

　　由于$p$是素数，那么只可能是$x-1$能被p整除(此时x=1) 或 x+1能被p整除(此时x=p-1)。

接着，如果$a^{n-1} ≡ 1 (\text{mod} n)$成立，Miller-Rabin算法不是立即找另一个$a$进行测试，而是看$n-1$是不是偶数。如果$n-1$是偶数，另$u=\dfrac{n-1}{2}$，并检查是否满足二次探测定理即$a^u ≡ 1$ 或$ a^u ≡ n - 1(\text{mod}\ n)$。

算法实现

Miller-Rabin算法随机生成底数$a$，进行多次调用函数进行测试，Miller-Rabin检测也存在伪素数的问题，但是与费马检测不同，MR检测的正确概率不依赖被检测数$p$，而仅依赖于检测次数。已经证明，如果一个数$p$为合数，那么Miller-Rabin检测的证据数量不少于比其小的正整数的$\dfrac{3}{4}p$，换言之，$k$次检测后得到错误结果的概率为$\left (\dfrac{1}{4} \right )^k$。我们在实际应用中一般可以测试$15\sim20$次。

代码：

#include <iostream>
#include <cmath>
using namespace std;

long long qpow(int a, int b, int r)
{
	long long ans = 1, buff = a;
	while (b)
	{
		if (b & 1)ans = (ans * buff) % r;
		buff = (buff * buff) % r;
		b >>= 1;
	}
	return ans;
}
bool Miller_Rabbin(int n, int a)
{
	int r = 0, s = n - 1, j;
	if (!(n%a))
		return false;
	while (!(s & 1))
	{
		s >>= 1;
		r++;
	}
	long long k = qpow(a, s, n);
	if (k == 1)
		return true;
	for (j = 0; j < r; j++, k = k * k % n)
		if (k == n - 1)
			return true;
	return false;
}
bool IsPrime(int n)
{
	int tab[] = { 2,3,5,7 };
	for (int i = 0; i < 4; i++)
	{
		if (n == tab[i])
			return true;
		if (!Miller_Rabbin(n, tab[i]))
			return false;
	}
	return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	long long n;
	while (1)
	{
		cin >> n;
		cout << IsPrime(n) << endl;
	}
	return 0;
}