1001.AND Minimum Spanning Tree
传送门：HDU6614
题意：给你一个又n个点的完全图，点编号从1~n，每条边的权值为被连接的两点编号按位与后的值。现在要你找到最小生成树，输出这个最小生成树的值 和 从2~n每个点相连的点（要求字典序最小）。
题解：因为是进行二进制操作，我们把数写成二进制形式可以发现，对于一个数x我们找到其从最低位开始第一个0位i，&上只有这一位是1其他位为0的数时与的结果为0。显然，只有n为2的次方-1时最小生成树的值为1，其他情况下每个点都能找到按位与后结果为0的点相连。
代码：
#include <cstdio>
using namespace std;
int a[]={};
int main() {
int T,n;
for (int i = ; i < ; i++)
a[i] = a[i-]*;
for (scanf("%d",&T);T--;) {
scanf("%d",&n);
int fg = ;
for (int i = ; i < ; i++)
if (n+ == a[i]) {
fg = ;
break;
}
printf("%d\n", fg);
for (int i = ; i <= n; i++) {
int x = i,cnt = ;
while(x) {
if (x% == ) break;
x>>=;
cnt<<=;
}
printf("%d%c",cnt>n?:cnt,i==n?'\n':' ');
}
}
return ;
}
1003.Divide the Stones
传送门：HDU6616
题意：有n个石子，编号和重量都是1~n，现在要把这n个石子分成k组，要求每组数量和总重量相同，判断是否能分成k组，可以的话输出每组有哪些石子。
题解：待补
代码：
1007.Just an Old Puzzle
传送门：HDU6620
题意：给你一个4*4的矩阵，问你120步内是否能复原。
题解：奇数码可达性问题。我们判断将空格移到最后之后前15个数逆序对个数是否为偶数个即可。
代码：
#include <cstdio>
using namespace std;
const int N = + ;
int a[][],b[N];
int main() {
int T,n;
for (scanf("%d",&T);T--;) {
int k=,x=;
for (int i = ; i <= ; i++)
for (int j = ; j <= ; j++)
scanf("%d",&a[i][j]);
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (i+j!=&&!a[i][j]) {
for (int yy = j; yy < ; yy++)
a[i][yy] = a[i][yy+];
for (int xx = i; xx < ; xx++)
a[xx][] = a[xx+][];
}
b[++k] = a[i][j];
}
}
for(int i=;i<;i++)
for(int j=;j<i;j++)
if(b[i]<b[j]) x++;
if (x%==) printf("Yes\n");
else printf("No\n");
}
return ;
}
1008.K-th Closest Distance
传送门：HDU6621
题意：你有一个长度为n的数组，有q次查询，每次询问[l,r]区间中p到ai第k大的距离是多少。
题解：区间第k大，第一反应是主席树。我们可以二分距离mid，当(p-mid,p+mid)中元素个数有k个时，mid为答案。注意边界。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + ;
const int M = 1e6;
struct node{
int l,r,val;
}T[N*];
int a[N],root[N],cnt;
void update(int l,int r,int &x,int y,int pos) {
T[++cnt] = T[y],T[cnt].val++,x = cnt;
if (l == r) return;
int mid = (l+r)>>;
if (mid >= pos) update(l,mid,T[x].l,T[y].l,pos);
else update(mid+,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int pl,int pr) {
if (pl <= l && pr >= r) return T[y].val - T[x].val;
int mid = (l+r)>>;
int ans = ;
if (pl <= mid) ans += query(l,mid,T[x].l,T[y].l,pl,pr);
if (pr > mid) ans += query(mid+,r,T[x].r,T[y].r,pl,pr);
return ans;
}
int main() {
int t,n,m;
for (scanf("%d",&t);t--;) {
scanf("%d%d",&n,&m);
cnt = ;
T[].l = ;
T[].r = ;
T[].val = ;
for (int i = ; i <= n; i++) {
scanf("%d",&a[i]);
update(,M,root[i],root[i-],a[i]);
}
int X = ;
while(m--) {
int l,r,p,k,L=,R=M;
scanf("%d%d%d%d",&l,&r,&p,&k);
l^=X,r^=X,p^=X,k^=X;
while(L<=R) {
int mid = (L+R) >> ;
if (query(,M,root[l-],root[r],max(,p-mid),min(M,p+mid))>=k){
X = mid;
R = mid - ;
}else L = mid + ;
}
printf("%d\n", X);
}
}
return ;
}
1010.Minimal Power of Prime
传送门：HDU6623
题意：给你一个大于一的正整数n，它可以写成不同质因子的幂的乘积的形式，现在问这些质因子的幂中，最小的幂是多少。
题解：先暴力打出一万以内的素数，算出这些素数中最小的幂是多少，如果得到最小的幂为1或者n为1了则表示找出了最小幂，否则的话分类讨论。因为我们打了一万以内的素数，那么剩下的数最大也只能是一个素数的4次方，我们依次判断是否为某个数的4次方，3次方，2次方，都不是的话n应该是个素数答案为1 。（看到有人说先判断4次方再判断2次方然后判断3次方，好像顺序关系不大~
代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e4 + ;
const int INF = 0x3f3f3f3f;
int prime[N];
bool vis[N];
int main(){
int cnt = ,T;
for (int i = ; i < N; i++) {
if (!vis[i]) prime[cnt++] = i;
for (int j = ; i * j < N; j++)
vis[i*j] = ;
}
for (scanf("%d",&T);T--;) {
ll n;
scanf("%lld",&n);
int ans = INF;
for (int i = ; i < cnt; i++) {
if(n%prime[i] == ) {
int num = ;
while(n%prime[i]==) {
num++;
n/=prime[i];
}
ans = min(ans,num);
if (ans == ) break;
}
}
if (ans == || n == ) {
printf("%d\n", ans);
continue;
}
ll x = pow(n,0.25);
if (pow(x,) == n)
ans = min(ans,);
else if (pow(x+,) == n) ans = min(ans,);
else {
x = pow(n,1.0/3.0);
if (pow(x,) == n) ans = min(ans,);
else if (pow(x+,) == n) ans = min(ans,);
else {
x = pow(n,0.5);
if (pow(x,) == n) ans = min(ans,);
else if (pow(x+,) == n) ans = min(ans,);
else ans = min(ans,);
}
}
printf("%d\n", ans);
}
return ;
}