2019年杭电多校第四场

1001 AND Minimum Spanning Tree(HDU6614)

题意

要你构造一棵最小生成树，边权是两顶点的编号的与值。

思路

对于\(2^i-1\)看\(2^i\)是否小于等于\(n\)，如果是则与\(2^i\)连边，其他的数则看其二进制下最后一个\(0\)在哪，假设是在\(x\)，那么就与\(2^x\)连边。

代码实现如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< vec;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int ans = 0;
        vec.clear();
        for(int i = 2; i <= n; ++i) {
            int num = 0;
            for(int j = 0; j <= 20; ++j) {
                if(i <= (1<

1003 Divide the Stones(HDU6616)

题意

要你把个石子分成\(k\)堆，每堆有\(\frac{n}{k}\)个石子，使得这\(k\)堆石子重量相同，每个石子的重量为\(i\)。

思路

对于\(\frac{n}{k}\)偶数我们发现蛇形填数是可以使得其相等的，那么对于奇数我们只需要拿出前\(3k\)个来填，剩余的按照偶数的进行处理即可。

奇数的时候我们首先确定第一列分别为\(1\)~\(k\)，第二列肯定要错位填数，通过计算可以得到第\(\frac{k}{2}+1\)填\(2k\)，然后\(\frac{k}{2}+2\)填\(1\)，以此类推。第三列则用\(\frac{3(3*k+1)}{3}\)来减即可。

代码实现如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<

1007 Just an Old Puzzle(HDU6620+华容道+逆序对)

思路

把\(0\)变成\(16\)然后矩阵合并成一列求出逆序对，加上\(0\)的初始位置如果是偶数则可以构造，否则就不能构造。

代码实现如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< a[i]) ++ans;
            }
        }
        if(ans & 1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

1008 K-th Closest Distance(6621+主席树+二分)

题意

对于一个数组\(a\)查询\(q\)次，每次问区间\([L,R]\)中距离\(p\)是第\(k\)大的是多少(第\(i\)个数与\(p\)的距离为\(|a_i-p|\))。

思路

二分答案然后看\([p-ans,p+ans]\)内有没有\(k\)个数。

代码实现如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    if(mid >= pos) update(l, mid, tree[x].l, tree[y].l, pos);
    else update(mid + 1, r, tree[x].r, tree[y].r, pos);
}

int query(int l, int r, int x, int y, int L, int R) {
    if(l >= L && r <= R) return tree[y].sum - tree[x].sum;
    if(l == r) return 0;
    int mid = (l + r) >> 1;
    if(R <= mid) return query(l, mid, tree[x].l, tree[y].l, L, R);
    else if(L > mid) return query(mid + 1, r, tree[x].r, tree[y].r, L, R);
    else return query(l, mid, tree[x].l, tree[y].l, L, mid) + query(mid + 1, r, tree[x].r, tree[y].r, mid + 1, R);
}

int main() {
#ifndef ONLINE_JUDGE
FIN;
time_t s = clock();
#endif // ONLINE_JUDGE
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &q);
        int mx = 0;
        cnt = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        }
        for(int i = 1; i <= n; ++i) {
            update(1, mx, root[i], root[i-1], a[i]);
        }
        int las = 0;
        while(q--) {
            scanf("%d%d%d%d", &l, &r, &p, &k);
            l = l ^ las, r = r ^ las, p = p ^ las, k = k ^ las;
            int ub = mx, lb = 0, mid, ans = mx;
            while(ub >= lb) {
                mid = (ub + lb) >> 1;
                if(query(1, mx, root[l-1], root[r], p - mid, p + mid) >= k) {
                    ans = mid;
                    ub = mid - 1;
                } else {
                    lb = mid + 1;
                }
            }
            las = ans;
            printf("%d\n", ans);
        }
    }
    return 0;
}

1010 Minimal Power of Prime(HDU6623+素数筛)

题意

给你\(n\)，问你\(n\)的素因子中最小的次数是多少。

思路

我们首先把\(4000\)内的素数筛出来，如果\(n\)还有剩余那么可以发现除了\(p^4,p^3,p^2,(p_1p_2)^2\)外其他情况指数最小都是\(1\)，对于这几种情况分别开方就行，最后与小于\(4000\)的素数的最小次数取\(min\)就行。

本题与HDU5447()很像，想清楚就会发现其实很简单，根本就不用把\(n\)完全唯一分解出来。

代码实现如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<
迷之二分迷之数论比赛题解感想迷之主席树

相关

标签

一品网 冀ICP备14022925号-6