题意：给定一个长度为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< 题意：建立一棵树，树上的结点分黑白，黑节点的所有子节点全为黑，白结点的子节点可为黑可为白。建树，数的情况恰好有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
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）