第十一届山东省大学生程序设计竞赛

题意：给定一个长度为n的序列，构建一个无向图，无相图边长为 g c d ( a [ i ] , a [ j ] ) gcd(a[i],a[j]) gcd(a[i],a[j])，为从区间 [L,R]中的随机数。但是n最大为2e5，L和R为2e5，不能直接考虑最小生成树算法，需找规律，当 L = = R L==R L==R时，所有的 g c d ( a [ i ] , a [ j ] ) gcd(a[i],a[j]) gcd(a[i],a[j])全部为L，所以图的总长度为 L ∗ ( n − 1 ) L*(n-1) L∗(n−1)。还有一条件，若这n个数中出现 质数，则所有点和他的gcd都为1，所以结果就为 n − 1 n-1 n−1，int范围内，相邻质数的距离不超过1000，所以当 ( n > 1000 & & L ! = R ) (n>1000&& L!=R) (n>1000&&L!=R)时，结果就为n-1。当n<1000时，直接kruskal最小生成树即可。

#include 
#include 
#include 
using namespace std;
int n,L,R,a[200001];
unsigned long long seed;
unsigned long long xorshift64() {
	unsigned long long x=seed;
	x^=x<<13;
	x^=x>>7;
	x^=x<<17;
	return seed=x;
}
class node{
	public:
		int i,j;
		int wast;
};
bool operator<(const node &a,const node &b){
	return a.wastve;
int find(int x){
	if(fa[x]!=x){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
void Krusal() {
	for(int i=0; i1000) {
		cout< 
C.Cat Virus 
题意：建立一棵树，树上的结点分黑白，黑节点的所有子节点全为黑，白结点的子节点可为黑可为白。建树，数的情况恰好有k种
 
考点：思维+构造
 
题解：总结规律可得，某节点原来没有子节点，加一个子节点，总可能数=原数量+1，若已有子节点，则加一个子节点，总可能数=1+原来子节点的总数*2。所以，当k可以被2整除时，只需在当前节点下加新的结点即可，若不可以，则需要格外加一个子节点，然后在该子节点下继续加新的节点。
 
注意：数据范围需要long long
 
#include 
#include 
using namespace std;
typedef long long int ll;
vector a[1005];
ll n=1;
void to(ll i,ll k){
	a[0].push_back(i);
	ll tmp=k-1;
	while(tmp%2==0){
		a[i].push_back(++n);
		tmp/=2;
	}
	if(tmp==1)return;
	a[i].push_back(++n);
	to(n,tmp);
}
int main(){
	ll k;
	cin>>k;
	to(1,k);
	cout< 
M.Matrix Problem 
题意：给一个01矩阵C，说该矩阵是由AB矩阵同为1的点，C矩阵中才为1，否则为0，让你求，AB矩阵，并且要求，AB矩阵要将C矩阵中的1连接起来。注意：题目给出了，矩阵的最外围全为0。
 
考点：思维+构造
 
题解：C中为1的点，AB都必为1，可以将奇数行都给A变为1，偶数行都给B变为1，并且最左侧一列给A全为1，最右侧一列全给B全为1，即可。
 
#include 
#include 
using namespace std;
const int mx=505;
int a[mx][mx];
bool ff[mx][mx];
int main(){
	int n,m;
	cin>>n>>m;
	bool f[mx];
	memset(ff,0,sizeof(ff));
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	getchar();
	for(int i=0;i