layout: post
title: 2019 Multi-University Training Contest 4
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- ACM-ICPC
1001 AND Minimum Spanning Tree(位运算)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
set<int>mp;
int get(int x){
for(int i=0;i<30;i++){
if((x&(1<<i))==0)return (1<<i);
}
}
int main(){
std::ios::sync_with_stdio(false);
int t;
cin>>t;
int p=0;
for(int i=1;i<=2e5;i*=2){
p+=i;
mp.insert(p);
}
while(t--){
int n;
cin>>n;
int ans=0;
vector<int>oo;
for(int i=2;i<=n;i++){
if(i%2==0)oo.push_back(1);
else{
if(mp.count(i)&&(i+1)<=n){
oo.push_back(i+1);
}
else if(mp.count(i)){
oo.push_back(1);
ans++;
}
else{
int u=get(i);
oo.push_back(u);
}
}
}
cout<<ans<<endl;
for(int i=0;i<oo.size();i++){
if(i)cout<<" ";
cout<<oo[i];
}
cout<<endl;
}
return 0;
}1007 Just an Old Puzzle （结论）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int a[10][10];
int cal(int x,int y){
int p=a[x][y];
int cnt=0;
for(int i=1;i<=x;i++){
for(int j=1;j<=(i==x?y:4);j++){
if(p<a[i][j])cnt++;
}
}
return cnt;
}
int main(){
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int ix,iy;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>a[i][j];
if(a[i][j]==0)ix=i,iy=j;
}
}
int ans=ix;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
if(a[i][j]==0)continue;
ans+=cal(i,j);
}
}
// cout<<"ans="<<ans<<endl;
if(ans&1)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}1008 K-th Closest Distance （二分+主席树）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int e5=1e6;
int rt[maxn*40],num[maxn*40],ls[maxn*40],rs[maxn*40];
int cnt;
void update(int &o,int pre,int l,int r,int val){
o=++cnt;
ls[o]=ls[pre],rs[o]=rs[pre];
num[o]=num[pre]+1;
if(l==r)return ;
int mid=(l+r)/2;
if(val<=mid)update(ls[o],ls[pre],l,mid,val);
else update(rs[o],rs[pre],mid+1,r,val);
}
int query(int o,int l,int r,int val){///这个区间内小于等于这个数的个数
if(l==r){
return num[o];
}
int mid=(l+r)/2;
if(val<=mid)return query(ls[o],l,mid,val);
else return num[ls[o]]+query(rs[o],mid+1,r,val);
}
int n;
bool check(int mid,int K,int L,int R,int p){ ///K需要大于K个 值在P附近
int l1=max(p-mid,1),r1=min(e5,p+mid);
int numr1=query(rt[R],1,1e6,r1)-query(rt[L-1],1,1e6,r1);
int numl1=query(rt[R],1,1e6,l1-1)-query(rt[L-1],1,1e6,l1-1);
if(numr1-numl1>=K)return true;
else return false;
}
int a[maxn];
int main(){
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int m;
cin>>n>>m;
cnt=0;
for(int i=1;i<=n*40;i++){
num[i]=0;ls[i]=0;rs[i]=0;rt[i]=0;
}
for(int i=1;i<=n;i++){
cin>>a[i];
update(rt[i],rt[i-1],1,1e6,a[i]);
}
int x=0;
for(int i=1;i<=m;i++){
int L,R,p,K;
cin>>L>>R>>p>>K;
L^=x;R^=x;p^=x;K^=x;
if(L>R)swap(L,R);
int l=0,r=1e6,ans;
while(l<=r){
int mid=(l+r)/2;
if(check(mid,K,L,R,p)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans<<endl;
x=ans;
}
}
return 0;
}1010Minimal Power of Prime（分类讨论）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+50;
bool check[maxn];
ll prime[maxn],cnt;
void init(){
for(int i=2;i<maxn;i++){
if(!check[i]){
prime[++cnt]=i;
}
for(int j=1;j<=cnt;j++){
if(i*prime[j]>=maxn)break;
check[i*prime[j]]=true;
if(i%prime[j]==0)break;
}
}
}
int get(ll &x){
int ans=99999;
for(ll i=1;i<=cnt&&1LL*prime[i]*prime[i]<=x;i++){
if(x%prime[i]==0){
int oo=0;
while(x%prime[i]==0){
oo++;
x/=prime[i];
}
ans=min(oo,ans);
}
}
return ans;
}
int main(){
std::ios::sync_with_stdio(false);
int t;
init();
cin>>t;
while(t--){
ll n;
cin>>n;
int ans=99999;
if(n==1)ans=0;
ll u=n;
ans=get(u);
if(u==1){
cout<<ans<<endl;continue;
}
else{
ll o4=powl(u,0.25)+0.5,o2=powl(u,0.5)+0.5,o3=powl(u,1.0/3.0)+0.5;
if(o4*o4*o4*o4==u)ans=min(4,ans);
else if(o3*o3*o3==u)ans=min(3,ans);
else if(o2*o2==u)ans=min(2,ans);
else ans=min(1,ans);
cout<<ans<<endl;
}
}
return 0;
}