求小于n与n互质的数（冇得证明）

发表于 2019-06-03

数论真吉尔难啊啊啊！！！！！
这里就直接是公式了
小于n的质数的个数
设n=p^k,m为小于n的质数的个数m=(p-1)p^k-1它们的和total=n m/2;

dfs应用

发表于 2019-06-01

题目:牛客网想开了第二题
首先求一个数约数的个数的公式
举个例子
12=2²x3¹ 那12的约数的个数就是（2+1）（1+1）个
所以这道题的思路就是求他的n以内中最大的数的因数的的指数的乘积的最大值，如果用暴力的话肯定会超时，而一般情况下越大的范围一般就他的约数的个数就越多。
根据唯一分解定理，ans=p1^e1xp2^e2……pk^ek,pi为素数且p1=e2>=…>=ek，(贪心)即后一个素数的幂肯定小于等于前一个素数的幂，这里就用dfs来搜索他的个数。
他的数据给的是10⁹所以不用太多的因数，15个足够。
code:

#include<iostream>
using namespace std;

typedef long long ll;

ll res[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

ll total=0;
ll number;

void dfs(ll k,int lim,ll num,ll cnt){
    if(k>14) return;
    total=max(total,cnt);
	int i=1;
	for(i;i<=lim;i++){
		if(num<=number/res[k]){
			num*=res[k];
			dfs(k+1,i,num,cnt*(i+1));
		}else break;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	int i=0;
	for(i;i<t;i++){
		cin>>number;
		total=1;
		dfs(0,15,1,1);
		cout<<total<<endl;
	}
	return 0;
}

注意：这里用的是num<=number/res[k] 主要是防止ll爆掉如果用res[k]num<=number，long long 可能就爆了。

krustal,最小生成树

发表于 2019-05-27

tc is coming,上周的考试真是难受啊！！！！！！！
sad，可是还是要好好学算法啊！！！
讲道理，我感觉那些博客画那些图还有点看不懂，还是直接说比较好。。。。
他要求的其实就是n个点连起来最短的距离。基本可以这么理解。他最重要的一点就是先将个点到各点的距离从小到大排序，然后取最小的就是，这样就可以取到最小值了！！！！！
然后怎么判断有没有重复？那就是并查集来判断有没有在同根了。
下面上提目：
最小生成树

code:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct wtc {
	int from,to;
	ll len;
};

wtc tc[500100];
int pa[210000],ran[210000];

bool judge(wtc a,wtc b) {
	return a.len < b.len;
}

int find(int a) {
	return a == pa[a] ? a : pa[a] = find(pa[a]);
}

void unite(int a,int b) {
	int x = find(a);
	int y = find(b);
	if(x!=y) {
		if(ran[x] > ran[y]) pa[y] = x;
		else {
			pa[x] = y;
			if(x == y) ran[x]++;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	int i = 0;
	for(; i < m; i++)	cin>>tc[i].from >> tc[i].to >> tc[i].len;
	sort(tc,tc + m,judge);
	for(i = 1; i <= n; i++) pa[i] = i;
	int k = 1;
	ll total = 0;
	for(i = 0; i < m; i++) {
		if(k == n) break;
		if(pa[tc[i].from] != pa[tc[i].to]) {
		    total += tc[i].len;
		    unite(tc[i].from,tc[i].to);
			k++;
		}
	}
	cout<<total;
	return 0;
}

能不能用二维数组或者一个bool数组判断是否有遍历过？答案是不行的。因为数组和bool只能判断是否用过，这样可能会忽略掉一些东西。比如
1 2 1
3 4 1
2 3 1
这样的一组数据用bool或者数组存的话只会加上前两种的长度，不会加上第三个，各样他们就不能连在一起了。并查集则可以将他们连在一起，已经连接过的便不再连接，又因为这里的数组是用sort拍过序的，所以取得就是最小值。

欧拉筛法

发表于 2019-05-24

勤奋tc又来了这回是欧拉筛法
先从头开始吧，一般的素数筛选基本就是从1开始计算然后一直除到那个数为止。基本就是两个for循环

for(int i = 0;i <= sqrt（n）;i++)
{
	for(int j = 2;j < i;j++)
	{
		if(i%j) break;
	}
	if(j == i) num[k++] = i;
}

这一种的复杂度很大大概是o（n * sqrt（n））这是一种复杂度很大的算法，一般不会用这个。这里就有一个欧拉筛法了，时间复杂度大概在o（n）左右我们可以知道，每一个素数的n倍都是合数，所以我们找到一个素数的时候就可以将他的n次倍都标计。
以下是代码

#include<iostream>
using namespace std;

int num[1000000];
bool vis[100000];


void f(int a) {
	int i = 2;
	for(i; i <= a; i++) {
		if(!vis[i])
			num[++num[0]] = i;
		int len = num[0];
		int j = 1;
		for(j; j <= len && i * num[j] <= a; j++) {
			vis[i * num[j]] = true;
			if(i%num[j] == 0) break;
		}
	}
}

int main() {
	int n;
	cin>>n;
	f(n);
	int len = num[0];
	for(int i = 1; i <= len; i++) cout<<num[i]<<" ";
	return 0;
}

一个合数有可能不止一个因数，所以这样写的话可能就会导致一个数被重复标记，这样会多余耗时很多，所以我们在这添加一步，i%num[j] == 0 break；当num[j]是i的因数时，说明i有多个因数，他的更大的倍数可以由其他的更大的数来筛选掉，后面的筛选就没有必要了，所以从这里跳出循环。

迪杰斯特拉&&优化 author：tc

发表于 2019-05-23

勤劳的tc又来来了啊，这回是迪杰斯特拉啊，呃呃不会英文好难受。。sad。主要是不想学习。。。。
还是写博客舒服
Dijkstra
nice百度到了
eee dijkstra主要是求最短路但是不能有负值不然会有死循环？！他的主要思想就是贪心。先找到每个点离源点最近的点，再根据这个点可以到的那些点，更新源点到这个点，再到这个点可以到的那些点的最短值。然后一步依布更新最后求得最短值。
题目：非负源最短路

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

int mat[2510][2510];
int lenth[5000];
int maxn = 0x3f3f3f;
bool bj[2510];
int n;

void disk(int des) {
	int i = 0;
	memset(lenth,88,sizeof(lenth));
	for(i = 1; i <= n; i++)
		lenth[i] = mat[des][i];
	bj[des] = true;
	int sta = des;
	for(i = 1; i <= n; i++) {
		maxn = 0x3f3f3f;
		int j = 1;
		for(j; j <= n; j++)
			if(!bj[j] && maxn > lenth[j]) {
				maxn = lenth[j];
				sta = j;
			}
		bj[sta] = true;
	    j = 1;
		for(;j <= n;j++)
			lenth[j] = min(lenth[j],mat[sta][j] + lenth[sta]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	int m,s,t;
	cin >> n >> m >> s >> t;
	int i,j;
	memset(mat,maxn,sizeof(mat));
	int sub,sub1,value;
	for(i = 0; i < m; i++) {
		cin >> sub >> sub1 >> value;
		mat[sub][sub1] = value;
		mat[sub1][sub] = value;
	}
	disk(s);
	cout<<lenth[t];
	return 0;
}

可以看到，每回都要用循环更新源点到每个点之间最短值的最短值，这是很费时间的，所以这里我们可以用stl库里面的优先队列来优化，只取他的最大值。这里的还要用到greater/less greater是将小的放前面，从小到大排序stl默认好像是less。。。

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>


using namespace std;

typedef long long ll;

int mat[2510][2510];
int lenth[5000];
int maxn = 0x3f3f3f;
int n;
typedef pair<int,int> pa;

priority_queue<pa,vector<pa>,greater<pa> > rec;

void disk(int des) {
	int i = 0;
	pa p;
	memset(lenth,88,sizeof(lenth));
	for(i = 1; i <= n; i++) {
		lenth[i] = mat[des][i];
		rec.push(pa(mat[des][i],i));
	}
	int sta = des;
     while(!rec.empty())
     {
     	p = rec.top();
     	rec.pop();
     	int sub = p.first;
     	sta = p.second;
     	int j;
     	for(j = 1;j <= n;j++)
     	{
     		if(lenth[j] > lenth[sta] + mat[sta][j])
     		{
     			lenth[j] = lenth[sta] + mat[sta][j];
     			rec.push(pa(lenth[j],j));
			 }
		 }
	 }
}

int main() {
	ios::sync_with_stdio(false);
	int m,s,t;
	cin >> n >> m >> s >> t;
	int i,j;
	memset(mat,maxn,sizeof(mat));
	int sub,sub1,value;
	for(i = 0; i < m; i++) {
		cin >> sub >> sub1 >> value;
		mat[sub][sub1] = value;
		mat[sub1][sub] = value;
	}
	disk(s);
	cout<<lenth[t];
	return 0;
}

最长上升子序列&&low_bound

发表于 2019-05-23

复杂度nlogn;
这里主要是贪心的思想；
既然要求最长上升子序列那么，就要保证，第i（i > 0)个数他是的比他前一个数大的最小的一个数
就有个数组存储当前的最长序列及他的值。
当第i个数比这个个数组最后一个元素大的时候，那么此序列就添加一个数，反之，就在当前数列找一个刚好比他的的数来，然后替代他，
这里是最关键的一步这里就不停的更新，他的最小值。然偶这里用的是二分查找。这里可以使用low_bound函数，他是查找当前最小的比num这个数大的数，然后返回地址不存在则返回end，upper_bound则反之

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

int v[1100000],f[1100000];

void me(int a)
{
	int i = 0;
	for(i;i < a;i++) v[i] = 0,f[i] = 0;
}

int main(){
	int n ;
	ios::sync_with_stdio(false);
	while(cin >> n)
	{
		int i = 0;
		while(i < n) cin>>v[i++];
		f[0] = v[0];
		int len = 0;
		for(i = 1;i < n;i++)
		{
			if(v[i] > f[len]) f[++len] = v[i];
			else{
				int j = lower_bound(f,f+len,v[i]) - f;
				f[j] = v[i];
			}
		}
		cout<<++len<<endl;
	    me(n);
	}
	return 0;
}

这是个虚假的title;并查集

发表于 2019-05-22

并查集之前学过，但是没完全理解，之前像写想写博客就好好想了一下感觉理解更深了。。。写博客还是好处很多的。。。

并查集的主要是建立一个类似于是的东西（个人感觉）然后寻根。。
不同的人可以有不同的根一个并查集里面可以有很多个根！！！这个很重要！！！！有很多根！！！！
他有好几个部分组成第一个find根

1
2
3

int find(int x) {
	return x == pa[x] ? x:pa[x] = find(pa[x]);
}

寻找他的这个数的根一便于后面判断。。。。
然后输unite合并个数，如果他们同根就不合并不同根就合并

void unite(int a,int b) {
	int x = find(a);
	int y = find(b);
	if(x != y) {
		if(ran[x] > ran[y]) pa[y] = x;
		else {
			pa[x] = y;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
}

这里其实有个优化机库是ran数组用来存储每个树的高度将低的树接到高的树上面可以很有效的减少数的高度，一遍减少find的时耗。

题目：
现在给你 N 个地点，和 M 条边，表示某两个地点相连( 即无向，可以互相通过 ) , 现在希望你判断是否每个地点都能到最后一个点 N 。

这里就可以用到并查集
以下是代码

#include<bits/stdc++.h>

using namespace std;

int par[10000];

int n,m;

int find(int x)
{
	return x == par[x] ? x : par[x] = find(par[x]);
}

void in(){
	int i = 1;
	for(i;i <= n;i++)
	{
		par[i] = i;
	}
}

void unite(int a,int b)
{
	find(a) == find(b) ?  : par[find(a)] = find(b);
}

int main()
{
	cin >> n >> m;
	int i;
	int a,b;
	in();
	for(i = 0;i < m;i++)
	{
		cin >> a >> b;
		unite(a,b);
	}
	for(i = 1;i < n;i++)
	{
		find(i) == find(n) ? cout<<"Yes":cout<<"No";
		cout<<endl;
	}
	return 0;
}

这里就是找两个数同不同根
题目2：
众所周知，在电影中总会出现如下的情景：在某个地方有n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

这个题目就是寻找有几个根的开始先把朋友合起来，再将敌人的敌人合起来
以下是代码

#include<iostream>
using namespace std;

int pa[1100];
int ran[1100];
int en[1100][1100];
bool mark[1100];

int find(int x) {
	return x == pa[x] ? x:pa[x] = find(pa[x]);
}

void unite(int a,int b) {
	int x = find(a);
	int y = find(b);
	if(x != y) {
		if(ran[x] > ran[y]) pa[y] = x;
		else {
			pa[x] = y;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
}

int main() {
	int n,m;
	cin >> n >> m;
	int num,num1;
	char judge;
	int i  = 0;
	for(i;i <= n;i++) pa[i] = i;
	for(i = 0; i < m; i++) {
		cin >> judge >> num >> num1;
		switch(judge) {
			case 'F':
				unite(num,num1);
				break;
			case 'E':
				en[num][++en[num][0]] = num1;
				en[num1][++en[num1][0]] = num;
				break;
		}
	}
	int j;
	for(i = 1; i <= n; i++) {
		num = en[i][0];
		for(j = 1; j <= num; j++) {
			int num1 = en[i][j];
			if(j > 1)
				unite(en[i][j],en[i][j - 1]);
			for(int k = 1; k <= en[num1][0]; k++)
				unite(i,en[num1][k]);
		}
	}
	int total = 0;
	for(i = 1; i <= n; i++) {
		num = find(i);
		if(!mark[num]) {
			mark[num] = true;
			total++;
		}
	}
	cout<<total;
	return 0;
}

背包问题；author：tc；

发表于 2019-05-22

ohohoh！这是tc的第一篇博客呢。nice
这回是背包，自己感觉总是忘记然后就哎，说多了都是泪。ok。
背包问题最主要的是状态转移方程。讲道理就最主要的是选和不选的问题。然后我个人觉得它就是优化版的贪心问题，其实他的状态转移方程就基本是贪心的思想。

0/1 背包。

这个是题大概就是每个物品只有一件，然后每个物品有他的价值和占用空间，然后就求最多价值可以试多少。
题目：0/1背包
这是他的状态转移方程
f[n] = max(f[n - w[i]] + v[i] , f[n])
这就是他的状态转移方程。
因为他的每个物品只能用一次，所以为了避免重复使用所以我们从后开始遍历。以下是代码

#include<iostream>
using namespace std;

int v[100000],w[100000],f[100000];

int main(){
	int n,t;
	cin>>n>>t;
	int i = 0;
	for(i;i < t;i++) cin>>w[i] >> v[i];
	i = 0;
	int j = 0;
	for(;i < t;i++)
		for(j = n;j >= w[i];j--)
			f[j] = max(f[j],f[j - w[i]] + v[i]); 
	cout<<f[n];
	return 0;
}

完全背包

题目：完全背包
完全背包和0/1最大的区别就是可以重复使用，所以他就从头开始遍历。
他们状态转移方程是一样的
f[n] = max(f[n - w[i]] + v[i] , f[n])
以下是代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<string>
using namespace std;
int v[10000],w[10000],f[100000];

int main() {
	int n,t;
	cin>>n >> t;
	int j ,i = 0;
	for(;i < t;i++) cin >> w[i] >> v[i];
	for(i = 0;i < t;i++)
		for(j = w[i];j <= n;j++)
			f[j] = max(f[j - w[i]] + v[i],f[j]);
	cout<<f[n];
	return 0;
}

未命名

发表于 2019-05-07

title:背包问题；author：tc；

0/1 背包。

#include<iostream>
using namespace std;

int v[100000],w[100000],f[100000];

int main(){
	int n,t;
	cin>>n>>t;
	int i = 0;
	for(i;i < t;i++) cin>>w[i] >> v[i];
	i = 0;
	int j = 0;
	for(;i < t;i++)
		for(j = n;j >= w[i];j--)
			f[j] = max(f[j],f[j - w[i]] + v[i]); 
	cout<<f[n];
	return 0;
}

完全背包

完全背包和0/1最大的区别就是可以重复使用，所以他就从头开始遍历。
他们状态转移方程是一样的
f[n] = max(f[n - w[i]] + v[i] , f[n])
以下是代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<string>
using namespace std;
int v[10000],w[10000],f[100000];

int main() {
	int n,t;
	cin>>n >> t;
	int j ,i = 0;
	for(;i < t;i++) cin >> w[i] >> v[i];
	for(i = 0;i < t;i++)
		for(j = w[i];j <= n;j++)
			f[j] = max(f[j - w[i]] + v[i],f[j]);
	cout<<f[n];
	return 0;
}