# 2019 HDU多校第四场

## AND Minimum Spanning Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

You are given a complete graph with N vertices, numbered from 1 to N.
The weight of the edge between vertex x and vertex y (1<=x, y<=N, x!=y) is simply the bitwise AND of x and y. Now you are to find minimum spanning tree of this graph.
InputThe first line of the input contains an integer T (1<= T <=10), the number of test cases. Then T test cases follow. Each test case consists of one line containing an integer N (2<=N<=200000).
OutputFor each test case, you must output exactly 2 lines. You must print the weight of the minimum spanning tree in the 1st line. In the 2nd line, you must print N-1 space-separated integers f2, f3, … , fN, implying there is an edge between i and fi in your tree(2<=i<=N). If there are multiple solutions you must output the lexicographically smallest one. A tree T1 is lexicographically smaller than tree T2, if and only if the sequence f obtained by T1 is lexicographically smaller than the sequence obtained by T2.

Sample Input

2
3
2

Sample Output

1
1 1
0
1

Hint
In the 1st test case, w(1, 2) = w(2, 1) = 0, w(1, 3) = w(3, 1) = 1, w(2, 3) = w(3, 2) = 2. There is only one minimum spanning tree in this graph, i.e. {(1, 2), (1, 3)}.
For the 2nd test case, there is also unique minimum spanning tree.

#### 签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,a[maxn];
map<int,int> mp;
void solve(){
scanf("%d",&n);
if(mp[n]) printf("1\n");
else printf("0\n");
rep(i,2,n-1){
if(mp[i]) printf("%d ",i+1);
else{
int tmp=i,cnt=0;
while(tmp){
int last=tmp%2;
tmp/=2;
if(!last){
printf("%d ",1<<cnt);break;
}
cnt++;
}
}
}
if(mp[n]) printf("1\n");
else{
int tmp=n,cnt=0;
while(tmp){
int last=tmp%2;
tmp/=2;
if(!last){
printf("%d\n",1<<cnt);break;
}
cnt++;
}
}
}
int main(){
int op=2;
for(int i=1;op<=maxn-20;i++){
op*=2;
mp[op-1]=1;
}
int T;cin>>T;
while(T--) solve();
}


## Divide the Stones

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

There are n stones numbered from 1 to n.
The weight of the i-th stone is i kilograms. We divide the stones into k groups.
Each group consists of exactly stones.
We define the weight of each group is sum of the stones’ weights in the group.
Can we divide the stones so that the weights of all groups are same?
InputThe first line of input contains an integer T (1 <= T <= 100) denoting the number of test cases.
Each test case consists of one line containing two integers n (1 ≤ n ≤ 100000), k (k is divisor of n).
It is guaranteed that the sum of n overall test cases does not exceed 500000.
OutputFor each test case, if you can’t divide into k groups satisfying condition, print “no”.
Else if you can divide into k groups satisfying condition, print “yes” in one line and then print k lines.
The i-th line represent the indices of stones belonging to the i-th group.
If there are multiple solutions, you can print any of them.

Sample Input

1
4 2

Sample Output

yes
1 4
2 3

#### n/k为奇数时，可以先将前3k项分为相等的k份，然后剩下的再头+尾；贴一份女朋友的代码

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int maxn=1e5+7;
vector<int> ans[maxn];
int n,k;
void rua()
{
scanf("%d%d",&n,&k);
if(k==1)
{
printf("yes\n");
for (int i=1;i<n;i++) printf("%d ",i);
printf("%d\n",n);
return;
}
if(n==k) {printf("no\n");return;}
ll sum=1ll*n*(1+n)/2;
if(sum%k!=0) {printf("no\n");return;}
int tmp=n/k;
printf("yes\n");
if(tmp%2==0)
{
tmp/=2;//tmp组 头+尾
int res=1;
for (int i=1;i<=k;i++)
for (int j=1;j<=tmp;j++) {ans[i].pb(res);ans[i].pb(n-res+1);res++;}
}
else if(tmp%2==1)
{
ll num=1ll*3*(3*k+1)/2;
for (int i=1;i<=k;i++) ans[i].pb(i);
int tt=k+1;
for (int i=k;i>0;i-=2) ans[i].pb(tt),tt++;
for (int i=k-1;i>0;i-=2) ans[i].pb(tt),tt++;
for (int i=1;i<=k;i++) ans[i].pb(num-ans[i][0]-ans[i][1]);
int kk=(tmp-3)/2,res=1;
for (int i=1;i<=k;i++)
for (int j=1;j<=kk;j++) {ans[i].pb(3*k+res);ans[i].pb(n-res+1);res++;}
}
for (int i=1;i<=k;i++)
{
for (int j=0;j<ans[i].size()-1;j++) printf("%d ",ans[i][j]);
printf("%d\n",ans[i][ans[i].size()-1]);
}
for (int i=0;i<=k;i++) ans[i].clear();
return;
}
int main()
{
int t;scanf("%d",&t);
while (t--) rua();
return 0;
}


## Just an Old Puzzle

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given a 4 × 4 grid, which consists of 15 number cells and an empty cell.
All numbers are unique and ranged from 1 to 15.
In this board, the cells which are adjacent with the empty cell can move to the empty cell.
Your task is to make the input grid to the target grid shown in the figure below.
In the following example (sample input), you can get the target grid in two moves.

InputThe first line contains an integer T (1 <= T <= 10^5) denoting the number of test cases.
Each test case consists of four lines each containing four space-separated integers, denoting the input grid. 0 indicates the empty cell.
OutputFor each test case, you have to print the answer in one line.
If you can’t get the target grid within 120 moves, then print 'No', else print 'Yes'.

Sample Input

2
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Sample Output

Yes
No

#### 可以证明若有解则80步内必可以实现，判断可行性只要判断逆序对数量的奇偶性就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,mp[110];
void solve(){
int ans=0;
rep(i,0,3) rep(j,0,3){
int x;scanf("%d",&x);
mp[4*i+j]=x;
if(!x){ans+=(i+j);mp[4*i+j]=16;}
}
rep(i,0,15) rep(j,i+1,15) if(mp[i]>mp[j]) ++ans;
puts(ans%2==0?"Yes":"No");
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## K-th Closest Distance

Time Limit: 20000/15000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

You have an array: a1, a2, , an and you must answer for some queries.
For each query, you are given an interval [L, R] and two numbers p and K. Your goal is to find the Kth closest distance between p and aL, aL+1, ..., aR.
The distance between p and ai is equal to |p - ai|.
For example:
A = {31, 2, 5, 45, 4 } and L = 2, R = 5, p = 3, K = 2.
|p - a2| = 1, |p - a3| = 2, |p - a4| = 42, |p - a5| = 1.
Sorted distance is {1, 1, 2, 42}. Thus, the 2nd closest distance is 1.
InputThe first line of the input contains an integer T (1 <= T <= 3) denoting the number of test cases.
For each test case:

The second line contains n space-separated integers a1, a2, ..., an (1 <= ai <= 10^6). Each value of array is unique.
Each of the next m lines contains four integers L', R', p' and K'.
From these 4 numbers, you must get a real query L, R, p, K like this:
L = L' xor X, R = R' xor X, p = p' xor X, K = K' xor X, where X is just previous answer and at the beginning, X = 0.
(1 <= L < R <= n, 1 <= p <= 10^6, 1 <= K <= 169, R - L + 1 >= K).
OutputFor each query print a single line containing the Kth closest distance between p and aL, aL+1, ..., aR.

Sample Input

1
5 2
31 2 5 45 4
1 5 5 1
2 5 3 2

Sample Output

0
1

#### 主席树二分答案

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,q,a[maxn],last,maxx;
struct tree{int l,r,sum;}t[maxn*300];
int root[maxn],sz;
void update(int l,int r,int &x,int y,int val){
t[++sz]=t[y],t[sz].sum++,x=sz;
if(l==r) return;
int mid=(l+r)>>1;
if(val<=mid) update(l,mid,t[x].l,t[y].l,val);
else update(mid+1,r,t[x].r,t[y].r,val);
}
int query(int cl,int cr,int l,int r,int x,int y){
if(cl<=l&&r<=cr) return t[y].sum-t[x].sum;
int mid=(l+r)>>1,ans=0;
if(cl<=mid) ans+=query(cl,cr,l,mid,t[x].l,t[y].l);
if(cr>mid) ans+=query(cl,cr,mid+1,r,t[x].r,t[y].r);
return ans;
}
void solve(){
scanf("%d%d",&n,&q);
sz=last=maxx=0;
rep(i,1,n) scanf("%d",&a[i]),maxx=max(maxx,a[i]);
rep(i,1,n) update(1,maxx,root[i],root[i-1],a[i]);
while(q--){
int L,R,p,k; scanf("%d%d%d%d",&L,&R,&p,&k);
L^=last;R^=last;p^=last;k^=last;
int l=0,r=1e6,mid;
while(l<=r){
mid=(l+r)>>1;
if(query(max(1,p-mid),min(maxx,p+mid),1,maxx,root[L-1],root[R])>=k) r=mid-1;
else l=mid+1;
}
printf("%d\n",last=l);
}
}
int main(){
int QAQ;cin>>QAQ;
while(QAQ--) solve();
}


## Minimal Power of Prime

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

You are given a positive integer n > 1. Consider all the different prime divisors of n. Each of them is included in the expansion n into prime factors in some degree. Required to find among the indicators of these powers is minimal.
InputThe first line of the input file is given a positive integer T ≤ 50000, number of positive integers n in the file. In the next T line sets these numbers themselves. It is guaranteed that each of them does not exceed 10^18.
OutputFor each positive integer n from an input file output in a separate line a minimum degree of occurrence of a prime in the decomposition of n into simple factors.

Sample Input

5
2
12
108
36
65536

Sample Output

1
1
2
2
16

#### 数论题

1）如果m1/4是整数，我们可以知道m=p4。使用4更新答案并返回。

2）如果m1/3是整数，我们可以知道m=p3。使用3更新答案并返回。

3）如果m1/2是整数，我们可以知道m=p2或m=p2q2。无论哪种情况，我们都可以使用2更新答案并返回。
4）如果（1）（2）（3）是错误的，我们可以知道答案=1。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200],b[200];
int pt;
ll pri[4010];
bool mk[4010];
void mobi(){
for(int i=2;i<=4000;i++){
if(!mk[i]){
pri[++pri[0]]=i;
}
for(int j=1;j<=pri[0] && pri[j]*i<=4000;j++){
mk[i*pri[j]]=1;
if(i%pri[j]==0){
break;
}
}
}
return;
}
ll calc(ll x){
pt=1;
for(ll i=1;pri[i]*pri[i]<=x && i<=pri[0];i++){
if(x%pri[i]==0){
a[pt]=pri[i];
b[pt]=0;
while(x%pri[i]==0){
x/=pri[i];
b[pt]++;
}
pt++;
}
}
return x;
}
int main(){
int T;
scanf("%d",&T);
mobi();
while(T--){
ll n;
scanf("%lld",&n);
ll x=calc(n);
ll res=99999999;
for(int i=1;i<pt;i++){
res=min(res,b[i]);
}
if(x==1){
printf("%lld\n",res);
}
else{
ll ub=(ll)1e9,lb=1,ans;
while(ub>=lb){
ll md=(ub+lb)/2;
if(md*md<=x){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
if(ans*ans==x){
x=ans;
ll ub=(ll)1e6,lb=1,ans;
while(ub>=lb){
ll md=(ub+lb)/2;
if(md*md<=x){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
if(ans*ans==x){
printf("%lld\n",min(4ll,res));
}
else{
printf("%lld\n",min(2ll,res));
}
}
else{
ll ub=(ll)1e6;
ll lb=1,ans;
while(ub>=lb){
ll md=(lb+ub)/2;
if(md*md*md<=x){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
if(ans*ans*ans==x){
printf("%lld\n",min(3ll,res));
}
else{
printf("1\n");
}
}
}
}
return 0;
}


0 评论