2018 Multi-University Training Contest 1 – WNJXYKのBlog
WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
2018 Multi-University Training Contest 1
2018 Multi-University Training Contest 1

HDU 6298 Maximum Multiple

因为x \mid n, y \mid n, z \mid n, x+y+z = n,所以我们可以知道1 = \frac{1}{a} + \frac{1}{b} + \frac{1}{c},其中a=\frac{n}{x}, b=\frac{n}{y}, c=\frac{n}{z}
我们又知道1 = \frac{1}{4}+\frac{1}{4}+\frac{1}{2} = \frac{1}{3}+\frac{3}{3} = \frac{1}{2} + \frac{1}{3} + \frac{1}{6},所以只需要简单的判断一下就可以了,否则输出-1。

#include <cstdio>
using namespace std;
int main(){
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++){
        int n; scanf("%d", &n);
        if (n%3==0) printf("%lld\n",1LL*n/3*n/3*n/3);
        else if (n%4==0) printf("%lld\n", 1LL*n/4*n/4*n/2);
        else printf("-1\n");
    }
    return 0;
}

HDU 6299 Balanced Sequence

给定了n个括号序列,我们可以用栈来计算出每一个序列的匹配情况,以及这个序列在拼接之后从可以与左边的left个右括号,以及右边的right个左括号进行匹配。

然后,根据每个序列的left,right这两个参数按照一定的顺序进行排序,之后线性计算一下最终的答案就行了。

至于怎么排序,按命排序即可。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1e5+50;

int n;
char str[MAXN];
struct Block{
    int l, r;
}blk[MAXN];

int cmp(const Block&a, const Block&b) {
    if (min(a.r, b.l) != min(a.l, b.r)) return min(a.r, b.l) > min(a.l, b.r);
    return a.r-a.l > b.r-b.l;
}

inline void solve(int T){
    int ans=0;

    scanf("%d", &n);
    for (int i=1; i<=n; i++){
        scanf("%s", str+1);
        int l=0, r=0, len=strlen(str+1);
        for (int j=1; j<=len; j++){
            if (str[j]=='(') ++l; else{
                if (l>0) ++ans, --l; else ++r;
            }
        }
        blk[i].l=l, blk[i].r=r;
    }

    sort(blk+1, blk+n+1, cmp);

    for (int i=1, now=0; i<=n; i++){
        ans+=min(now, blk[i].l);
        now=max(0, now-blk[i].l)+blk[i].r;
    }

    printf("%d\n", ans*2);
}

int main(){
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6300 Triangle Partition

按照X轴的排序,因为不存在三点共线,所以每相邻的三个点组成一个三角形就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=1e3+50;

int n;
int x[3*MAXN], y[3*MAXN], idx[3*MAXN];

inline bool cmp(int a, int b){
    if (x[a]!=x[b]) return x[a]<x[b];
    return y[a]<y[b];
}

inline void solve(int T){
    scanf("%d", &n);
    for (int i=1; i<=3*n; i++)
        scanf("%d%d", &x[i], &y[i]);
    for (int i=1; i<=3*n; i++) idx[i]=i;
    sort(idx+1, idx+3*n+1, cmp);
    for (int i=1; i<=n; i++)
        printf("%d %d %d\n", idx[i*3-2], idx[i*3-1], idx[i*3]);
}

int main(){
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDH 6301 Distinct Values

因为要求字典序最小,所以前面的数字越小越好。我们只需要通过贪心的取满足前面条件的时候,当前最小的数字即可。
我们可以用一个优先队列维护当前这个位置能取的数字集合,然后动态维护更新。一旦一个限制区间结束,我们就可以释放这个限制区间中与还存在的限制区间无关的那部分数字。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN=1e5+50;

int n, M, m;
struct Seg{int l, r;}seg0[MAXN], seg[MAXN];
int ans[MAXN];
priority_queue<int> que;

inline bool cmp(const Seg &a, const Seg &b){
    if (a.l!=b.l) return a.l<b.l;
    return a.r>b.r;
}

inline void solve(int T){
    scanf("%d%d", &n, &M);
    for (int i=1; i<=M; i++) scanf("%d%d", &seg0[i].l, &seg0[i].r);
    while(!que.empty()) que.pop();
    for (int i=1; i<=n; i++) que.push(-i);

    // Delete
    sort(seg0+1, seg0+M+1, cmp);
    m=0;
    for (int i=1, mx=-1; i<=M; i++){
        if (seg0[i].r>mx){
            seg[++m]=seg0[i];
            mx=seg0[i].r;
        }
    }
    //printf("%d\n", m);for (int i=1; i<=m; i++) printf("%d %d\n", seg[i].l, seg[i].r);

    // Set
    int l=1, r=0;
    for (int i=1; i<=n; i++){
        // Ins
        while(r+1<=m && seg[r+1].l<=i && i<=seg[r+1].r) r++;
        // Delete
        while(l<=m &&i>seg[l].r) {
            //printf("D#%d(%d)\n", l, i);
            for (int j=seg[l].l; j<=seg[l].r && j<i && (l+1>m || j<seg[l+1].l); j++) que.push(-ans[j]);//, printf("Delete %d\n", j);
            l++;
        }
        ans[i]=-que.top(); que.pop();
        if (l>r) que.push(-ans[i]);
    }

    for (int i=1; i<n; i++) printf("%d ", ans[i]); printf("%d\n", ans[n]);
}

int main(){
    //freopen("in.txt", "r", stdin);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6304 Chiaki Sequence Revisited

打表找规律之后,我们可以发现这个序列是这个样子的:1,1,2,2,3,4,4,4,5,6,6,7,8,8,8,8,\cdots
把第一个1去掉时候,我们可以发现这个序列遵从一种分形的生成方式:如果要从1\cdots 2^{i}生成1\cdots 2^{i+1}i+1,我们只需要将1\cdots 2^{i}这个序列每个数字加上2^i拼接在1\cdots 2^{i}序列的后面,然后再添加上一个2^{i+1}即可。
如此,我们可以使用线性递推计算出以2^i结尾的答案,利用之前计算出来的结果,再加上后边半段的整体位移贡献。
对于任意一个n,它一定可以表示成若干个经过位移之后的1\cdots 2^k的序列之和。我们找到这些序列,然后累和即可。

#include <cstdio>
#define LL long long
using namespace std;

const LL MOD=1e9+7;

const int len=16;
const int seq[20]={0, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9};
int suffix_seq[20]={0};

const LL MAXN=1e18;
const LL MAXS=1e6;
LL bin[65], lin[65], ans[65]; int tot;

int main(){
    //freopen("in.txt", "r", stdin);
    for (int i=1; i<=len; i++) suffix_seq[i]=suffix_seq[i-1]+seq[i];
    bin[tot=0]=lin[0]=1; while(bin[tot]*2LL<=MAXN) ++tot, bin[tot]=bin[tot-1]*2LL, lin[tot]=bin[tot]*2LL-1LL;
    ans[0]=1; for (int i=1; i<=tot; i++) ans[i]=(ans[i-1]*2LL%MOD + (bin[i-1]%MOD)*(lin[i-1]%MOD) + bin[i]%MOD)%MOD;

    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++){
        LL n; scanf("%lld", &n); n--;
        LL ptr=1LL;
        while(n>len){
            for (int i=tot; i>=0; i--) if (lin[i]<=n){
                n-=lin[i];
                ptr= ptr + ans[i] + (bin[i]%MOD)*(n%MOD); ptr%=MOD;
                break;
            }
        }
        ptr=(suffix_seq[n] + ptr)%MOD;
        printf("%lld\n", ptr);
    }
    return 0;
}


HDU 6305 RMQ Similar Sequence

因为在实数范围内生成两个相同的数字的概率等于0,所以我们可以默认所有数字不相同。那么随机生成一个满足条件的序列的概率应该等于随机生成一个满足条件的排列的概率。接下来观察这个排列,排列满足条件只需要排列的笛卡尔树与原序列的笛卡尔树同构即可,所以我们建立原序列的笛卡尔树,通过排列组合算一算符合的排列的方案数即可。
又因为我们需要求序列的期望的和,每一个数字的期望为\frac{1}{2},所以长度为n的序列的期望为\frac{n}{2}。在概率上乘一下序列期望即是答案。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define mp(x,y) make_pair(x,y)
#define LL long long
using namespace std;

const LL MOD=1e9+7;

const int Maxn=1e6;
int n;
int num[Maxn+5];

LL fac[Maxn+5];
LL ifac[Maxn+5];
LL inv[Maxn+5];
void init_rev(int n,LL P){
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=P-1LL*(P/i)*inv[P%i]%P;
}

inline void init(){
    init_rev(Maxn,MOD);
    for (int i=1;i<=Maxn;i++) fac[i]=i;
    ifac[1]=inv[1]=1;
    ifac[0]=inv[0]=1;
    for (int i=2;i<=Maxn;i++){
        fac[i]=fac[i]*fac[i-1]%MOD;
        ifac[i]=inv[i]*ifac[i-1]%MOD;
    }
}

inline int mergeTree(int a,int b){
    if (num[a]>=num[b]) return a; else return b;
}

int pos[Maxn*4+5];
void build(int x,int left,int right){
    if(left==right){
        pos[x]=left;
    }else{
        int mid=(left+right)/2;
        build(x*2,left,mid);
        build(x*2+1,mid+1,right);
        pos[x]=mergeTree(pos[x*2],pos[x*2+1]);
    }
}

int query(int x,int l,int r,int left,int right){
    if (left<=l && r<=right){
        return pos[x];
    }else{
        int mid=(l+r)/2;
        if (right<=mid) return query(x*2,l,mid,left,right);
        if (left>=mid+1) return query(x*2+1,mid+1,r,left,right);
        return mergeTree(query(x*2,l,mid,left,right),query(x*2+1,mid+1,r,left,right));
    }
}

LL ans=1;
void dfs(int left, int right){
    if (right-left+1<=2) return;
    int mid=query(1, 1, n, left, right);
    ans=ans*fac[right-left]%MOD*ifac[mid-left]%MOD*ifac[right-mid]%MOD;
    dfs(left, mid-1); dfs(mid+1, right);
}

queue<pair<int,int> > que;

inline void solve(int T){
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", &num[i]);
    build(1, 1, n);

    ans=ifac[n]*n%MOD*ifac[2]%MOD;

    while(!que.empty()) que.pop();
    if (n>=2) que.push(mp(1, n));
    while(!que.empty()){
        int left=que.front().first, right=que.front().second; que.pop();
        int mid=query(1, 1, n, left, right);
        ans=ans*fac[right-left]%MOD*ifac[mid-left]%MOD*ifac[right-mid]%MOD;
        if (mid-left>2) que.push(mp(left, mid-1));
        if (right-mid>2) que.push(mp(mid+1, right));
    }

    printf("%lld\n",ans);
}

int main(){
    //freopen("in.txt","r",stdin);
    init();
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 1011 Time Zone

时区转换问题,所以我们只需要全部都转换成为分钟。然后在分钟的基础上在进行时区转换即可。
注意浮点数的精度问题。

#include <cstdio>
#include <cmath>
using namespace std;
int main(){
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++){
        int a, b, t; double f; scanf("%d %d UTC%lf", &a, &b, &f);
        t=a*60+b+round((f-8.0)*60.0);
        t=(t%1440+1440)%1440;
        a=t/60; b=t%60;
        printf("%02d:%02d\n", a, b);
    }
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

2018 Multi-University Training Contest 1
HDU 6298 Maximum Multiple 因为$$x \mid n, y \mid n, z \mid n, x+y+z = n$$,所以我们可以知道$$1 = \frac{1}{a} + \frac{1}{b} + \frac{1}{c}$$,其中$$a=&…
扫描二维码继续阅读
2018-07-24
<--! http2https -->