2019 杭电多校（第四场）

本文主要是介绍2019 杭电多校（第四场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1001 AND Minimum Spanning Tree （思维 二进制运算）

http://acm.hdu.edu.cn/showproblem.php?pid=6614

题意

给你1-n个数 让你建最小生成树 边的权值为两点按位与 求最小权值和 和 建发（最小字典序）

思路

字典序最小 那就连最小按位与为0的点 找的最小的0 该为1即可 对于全为1的点连在100..0上（如果不等于n，等于n的话连在1上 权值即为1）

代码

#include<bits/stdc++.h>using namespace std;
int a[50];
int n;
int f[200005*2];
int ok(int x)
{int qw;int qwe = x;for(int i = 1;i <= 18;i++){a[i] = x % 2;x /= 2;if(a[i] == 1) qw = i;}int ans = 0;x = 1;for(int i = 1;i <= qw;i++){if(a[i] == 0) {ans += x;break;}x *= 2;}if(f[ans]) return 1;if(ans == 0&&qwe + 1 <= n) return qwe+1;else if(ans == 0) return 1;return ans;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);int x = 2;int ans = 0;for(int i = 1;;i++){x *= 2;if(x - 1 == n){ans = 1;break;}else if(x - 1 > n) break;f[x-1] = 1;}printf("%d\n",ans);printf("1");for(int i = 3;i <= n;i++){ans = ok(i);printf(" %d",ans);}printf("\n");}return 0;
}

1003 Divide the Stones （思维）

http://acm.hdu.edu.cn/showproblem.php?pid=6616

题意

给你n个数1-n  让你分成k组 使每组数字和相等 输出分法

思路

If the total number of stones is a multiple of k, we can always divide the stones. Otherwise, we can’t.

If n/k is even, you can find solution quite easily.

If n/k is an odd number, we divide first 3k stones into k groups with exactly 3 stones and equal weight.

After that, you can divide remaining stones by the way you did when n/k is even.

Time complexity is O(n).

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
vector<int> ans[maxn];int main()
{int T;scanf("%d",&T);while(T--){ll n,k;scanf("%lld%lld",&n,&k);ll sum = n*(n+1)/2;if(k == 1){printf("yes\n");for(int i = 1;i <= n;i++){printf("%d ",i);}continue;}if(sum % k != 0){printf("no\n");continue;}ll qw = n / k;printf("yes\n");for(int i = 1;i <= k;i++) ans[i].clear();if(qw % 2 == 0){int id = 1;for(int i = 1;i <= n/2;i++){ans[id].push_back(i);id++;if(id > k) id = 1;}id = 1;for(int i = n;i > n/2;i--){ans[id].push_back(i);id++;if(id > k) id = 1;}}else{for(int i = 1; i <= k; i++){ans[i].push_back(i);ans[i].push_back(k + (i + k / 2 - 1) % k + 1);ans[i].push_back(2 * k + (1 + k) / 2 * 3 - i - ((i + k / 2 - 1) % k + 1));}int len = (n-3*k) / 2;int id = 1;for(int i = 3*k+1;i <= 3*k+len;i++){ans[id].push_back(i);id++;if(id > k) id = 1;}id = 1;for(int i = n;i > 3*k+len;i--){ans[id].push_back(i);id++;if(id > k) id = 1;}}for(int i = 1;i <= k;i++){for(int j = 0;j < ans[i].size();j++){printf("%d ",ans[i][j]);}printf("\n");}}return 0;
}

1007 Just an Old Puzzle （定理）

http://acm.hdu.edu.cn/showproblem.php?pid=6620

题意 

给你一个4*4的图 问你能不能在120步内移动到初始状态

思路

定理 

• 格子列数为奇数，怎么移动，都不会改变原始的逆序数。因为奇数加减偶数还是奇数，偶数加减偶数还是偶数。所以，只要保证逆序数是偶数即可，不必关心空格的位置。
• 格子列数为偶数，那么进行奇数次上下移动，会改变其逆序数的奇偶性。所以，如果当前逆序数是偶数，要想有解，就要保证实际上下移动会进行偶数次，也就是说空格所在行与初始空格所在行的差为偶数。
• 同理，若当前逆序数是奇数，要想有解，要进行奇数次的移动，才能保证最终逆序数是偶数。

代码

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
int a[20];
int main()
{int T;scanf("%d",&T);int p = 1;while(T--){p = 1;for(int i = 1;i <= 4;i++){for(int j = 1;j <= 4;j++){int x;scanf("%d",&x);a[p++] = x;}}if(a[16] != 0){while(1){for(int i = 1;i <= 16;i++){if(a[i] == 0){if(i + 4 <= 16){swap(a[i],a[i+4]);}else{swap(a[i],a[i+1]);}}}if(a[16] == 0) break;}}int num = 0;for(int i = 1;i <= 15;i++){for(int j = i + 1;j <= 15;j++){if(a[i] > a[j]) num++;}}if(num%2 == 0) printf("Yes\n");else printf("No\n");}return 0;
}

1008 K-th Closest Distance （主席树）

http://acm.hdu.edu.cn/showproblem.php?pid=6621

题意

给你n个数 若干次询问 每次给你一个区间 问你第k接近q的数和q差多少

思路

强制在线 区间问题 主席树 二分答案 查询p-ans 到 p+ans范围内个数是否大于k

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAX = 1e5+100;struct Node {int sum, l, r;
} tree[MAX * 40];int root[MAX], cnt;
int data[MAX];int n,m;//离散化获得ID
//int get_id(int x) {
//    return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
//}void init() {cnt = 0;root[0] = 0;
}//根据旧版本的线段树创建新线段树的节点
int create_node(int po) {int idx = ++cnt;tree[idx].sum = tree[po].sum + 1;tree[idx].l = tree[po].l;tree[idx].r = tree[po].r;return idx;
}void updata(int &o, int po, int l, int r, int pos) {o = create_node(po);if (l == r) return;int m = (l + r) >> 1;if (pos <= m) updata(tree[o].l, tree[po].l, l, m, pos);else updata(tree[o].r, tree[po].r, m + 1, r, pos);
}//二分查询
//int query(int s, int e, int l, int r, int k) {
//    if (l == r) return l;
//    int m = (l + r) >> 1;
//    int sum = tree[tree[e].l].sum - tree[tree[s].l].sum;
//    if (k <= sum) return query(tree[s].l, tree[e].l, l, m, k);
//    else return query(tree[s].r, tree[e].r, m + 1, r, k - sum);
//}
int query(int s,int e,int l,int r,int x,int y)
{if(l == x&&r == y)return tree[e].sum - tree[s].sum;int mid = (l + r) / 2;if(y <= mid) return query(tree[s].l,tree[e].l,l,mid,x,y);else if(x > mid) return query(tree[s].r,tree[e].r,mid+1,r,x,y);else return query(tree[s].l,tree[e].l,l,mid,x,mid) +  query(tree[s].r,tree[e].r,mid+1,r,mid+1,y);
}
int main() {int T;scanf("%d",&T);while(T--){n = read(),m = read();for(int i = 1;i <= n;i++){scanf("%d",&data[i]);
//            sorted.push_back(data[i]);}
//        sort(sorted.begin(),sorted.end());
//        sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
//        int num = sorted.size();init();for(int i = 1;i <= n;i++){updata(root[i],root[i-1],1,1e6,data[i]);}int qw = 0;while(m--){int l,r,p,k;scanf("%d%d%d%d",&l,&r,&p,&k);l ^= qw,r ^= qw,p ^= qw,k ^= qw;if(l > r) swap(l,r);int ll = 0,rr = max(p,(int)1e6-p);while(ll + 1 < rr){int mid = (ll + rr) / 2;int num = query(root[l-1],root[r],1,1e6,max(p-mid,(int)1),min(p+mid,(int)1e6));if(num >= k){rr = mid;}else ll = mid;}int num = query(root[l-1],root[r],1,1e6,max(p-ll,(int)1),min(p+ll,(int)1e6));if(num >= k){printf("%d\n",ll);qw = ll;}else{printf("%d\n",rr);qw = rr;}}}return 0;
}

1010 Minimal Power of Prime （思维）

http://acm.hdu.edu.cn/showproblem.php?pid=6623

题意

给你一个数n  问你因式分解后 素数的所有幂中最小的是多少

思路

暴力计算到n的（1/5）次方 剩下的最大不会超过5次方 枚举计算即可

代码

 

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 4000;
ll pri[N],top=0;
int vis[N];
ll po(ll a,int b)
{ll ret=1;while(b--)ret*=a;return ret;
}
int check(ll n,int k)
{ll t=pow(n,1.0/k);t-=5;if(t<1)t=1;while(po(t+1,k)<=n)t++;return po(t,k)==n;
}void solve(ll n)
{int mi = 100000;for(int i = 0;i < top&&pri[i] <= n;i++){if(n % pri[i] == 0){int num = 0;while(n % pri[i] == 0){num++;n /= pri[i];}mi = min(mi,num);}}if(n == 1) {printf("%d\n",mi);return ;}for(int i = 4;i >= 2;i--){if(check(n,i)){printf("%d\n",i);return ;}}printf("1\n");
}int main()
{for(int i = 2;i <= N;i++){if(vis[i] == 0){pri[top++] = i;for(int j = i+i;j <= N;j+=i){vis[j] = 1;}}}int T;scanf("%d",&T);while(T--){ll n;scanf("%lld",&n);solve(n);}return 0;
}

 

这篇关于2019 杭电多校（第四场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---