HDU 2018 Multi-University Training Contest 1

2018 Multi-University Training Contest 1

首先我先吐槽一下我的队友,打着打着睡着两个,只留下我这位蒟蒻一直刚到底,但是最后还是没有多刚出一题QAQ。

然后我们尽然拿了Rank294。

身为蒟蒻队中的蒟蒻队,只打出了4题,但是我还是不要脸的来写题解了。

首先我按照题目难易程度来写题解。

T11(6308)

这题是我写的,写了一个多小时:joy:

我认为最简单的是1011,完全不需要思维含量,直接求解就可以了,还有,如果对自己的答案没有信心,可以直接用windows调整时差来check答案,特别方便。

然后我就因为判错了导致出现24点,所以WA4,QAQ

#include<cstdio>
using namespace std;
int n,h,s;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&h,&s);
        char ch;int z,x;
        getchar();getchar();getchar();getchar();
        ch=getchar();scanf("%d",&z);
        if(getchar()=='.') scanf("%d",&x);else x=0;
        if(ch=='-') z=(12-z)+(12-8),x=-6*x;else z=z-8,x=6*x;
        h=((h+z)%24+24)%24;s+=x;
        while(s>=60) s-=60,h++;
        while(s<0) s+=60,h--;
        while(h>=24) h-=24;
        while(h<0) h+=24;
        printf("%02d:%02d\n",h,s);
    }
    return 0;
}

T1(6298)

这题是XZY打表,YPC找出规律的。

看上去十分难,但是你会发现很容易出现-1,所以不妨打表找规律,表一打出来就完事了,发现只有在n%4==0||n%3==0的情况下才有解,最大解是多少呢?

对于n%4==0的情况:MAX=2 * (\frac{n}{4})^3
对于n%3==0的情况:MAN=(\frac{n}{3})^3

所以说要勤打表,打表出省一。

#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%lld",&n);
        if (!(n%3)){
            long long tmp=n/3;
            printf("%lld\n",tmp*tmp*tmp);
        }else if (!(n%4)){
            long long tmp=n/4;
            printf("%lld\n",tmp*tmp*2*tmp);
        }else printf("-1\n");
    }
    return 0;
}

T3(6300)

这题需要一点思维,但是也是水题。

只要有一个三角形中出现点,那么肯定会出现相交的情况,那么我们必须选择相邻的点,那么不就出结论了。

对关键字排序,选择相邻的三个,肯定不会出现相交的情况。

然而这题是由YPC窃取到机密信息然后打掉的,当时我还在打T11:joy:

#include<bits/stdc++.h>
using namespace std;
struct ypc{
    int x,y,id;
    inline bool operator < (const ypc b)const{
        return (x<b.x)||(x==b.x&&y<b.y);
    }
}p[100005];
int n,T;
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        n*=3;
        for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
        sort(p+1,p+1+n);
        for (int i=1;i<=n;i+=3) printf("%d %d %d\n",p[i].id,p[i+1].id,p[i+2].id);
    }
    return 0;
}

T4(6301)

这题是因为实在没事干了,我就随意打了一下,结果就A掉了。

想法很简单,用堆维护在这个区间没有出现过最小数(因为我们要字典序最小,肯定要越高位越小,所以肯定先放小的数),我们可以将区间全部投射到一维的数组上,然后枚举这个位置,肯定选择最大的这个覆盖区间,放置这个区间中没有的最小的数。

然后我们考虑区间转移,比如说当前区间结束了,那么当前区间的左边界到下一区间的左边界上的点肯定不会对当前造成影响,所以完全可以选择这段区间里的数。放到小根堆中就可以了。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int T,n,m,Len,hep_Num[100005],Len_Num,Len_L,que[100005];
bool hsh[100005];
struct xcw{
    int x,id;bool f;
    bool operator <(const xcw b)const{return x<b.x;}
}a[200005],hep_L[200005];
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
void put_Num(int x){
    hep_Num[++Len_Num]=-x;
    push_heap(hep_Num+1,hep_Num+1+Len_Num);
}
int get_Num(){
    pop_heap(hep_Num+1,hep_Num+1+Len_Num);
    return -hep_Num[Len_Num--];
}
void put_L(xcw x){
    hep_L[++Len_L]=x;
    push_heap(hep_L+1,hep_L+1+Len_L);
}
xcw get_L(){
    pop_heap(hep_L+1,hep_L+1+Len_L);
    return hep_L[Len_L--];
}
int main(){
    for(T=read();T;T--){
        memset(hsh,0,sizeof(hsh));
        while(Len_Num) get_Num();
        while(Len_L) get_L();
        n=read();m=read();
        for(int i=1;i<=m;i++) a[(i<<1)-1]=(xcw){read(),i,1},a[i<<1]=(xcw){read()+1,i,0};
        sort(a+1,a+1+(m<<=1));
        for(int i=1;i<=n;i++) put_Num(i);
        for(int i=1,j=1;i<=n;i++){
            while(a[j].x==i&&j<=m){
                if(a[j].f) hsh[a[j].id]=1,put_L((xcw){-a[j].x,a[j].id,0});
                else hsh[a[j].id]=0;
                j++;
            }
            if(Len_L==0) printf("1"),que[i]=1;
            else{
                xcw Now=get_L();int P=-Now.x;
                while(!hsh[Now.id]&&Len_L) Now=get_L();
                if(hsh[Now.id]){
                    put_L(Now);
                    for(int j=P;j<-Now.x;j++) put_Num(que[j]);
                    que[i]=get_Num();
                }else{
                    for(int j=P;j<i;j++) put_Num(que[j]);
                    que[i]=1;
                }
                printf("%d",que[i]);
            }
            printf(i==n?"\n":" ");
        }
    }
    return 0;
}

T2(6299)

这道毒瘤贪心题,反正我打了2个多小时没有调出来,机房里的dalao直接大力猜结论,直接A了此题,Orz。

然而这题我没有写掉。考完后才发现,我的贪心完全反了。

先讲一下贪心的做法,对每个字符串的左右括号个数进行分类讨论。
1. 如果左括号多,那么就将这个放到序列后半段,然后让右括号数量少的放后面,这样能使右括号没匹配上的少。
2. 如果右括号多,那么就将这个放到序列前半段,然后让左括号数量少的放前面,同样的意思。
但是我写的时候不是让没匹配上的越少越好,而是让匹配上的越多越好。

但是这就会反例了,我是这么理解的,不知是否有误:不一定你想匹配的全匹配上,如果有一个左括号特别多,但是还是少于右括号的,这种可能会被放在最后,但是放在较中间的位置更好一些。换种说法,尽量让右半段自己匹配最多与左半段自己匹配最多,然后剩下左右两端匹配起来。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int T,n,que[100005],Len1,Len2,Len3;
char s[100005];
struct xcw{int Q,H,Z;}a[100005],a1[100005],a2[100005];
bool cmp1(xcw x,xcw y){return x.H>y.H||(x.H==y.H&&x.Q<y.Q);}
bool cmp2(xcw x,xcw y){return x.Q<y.Q||(x.Q==y.Q&&x.H>y.H);}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("T2.in","r",stdin);
    freopen("T2.out","w",stdout);
    #endif 
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);Len1=Len2=0;
        for(int i=1;i<=n;i++){
            s[0]=0;gets(s);
            while(!s[0]) gets(s);
            int Len=strlen(s);
            a[i]=(xcw){0,0,0};
            int Now=0;
            for(int j=0;j<Len;j++){
                if(Now>-a[i].Q&&s[j]==')') a[i].Z++;
                Now+=((s[j]=='(')?1:-1);
                a[i].Q=max(a[i].Q,-Now);
            }
            Now=0;
            for(int j=Len-1;j>=0;j--){
                Now+=((s[j]=='(')?1:-1);
                a[i].H=max(a[i].H,Now);
            }
        }
        for(int i=1;i<=n;i++){
            if(a[i].Q-a[i].H<=0) a2[++Len2]=a[i];
            else a1[++Len1]=a[i];
        } 
        sort(a1+1,a1+1+Len1,cmp1);sort(a2+1,a2+1+Len2,cmp2);
        for(int i=1;i<=Len2;i++) a[i]=a2[i];
        for(int i=1;i<=Len1;i++) a[i+Len2]=a1[i];
        int Ans=a[1].Z*2,Now=a[1].H;
        for(int i=2;i<=n;i++){
            Ans+=a[i].Z*2;
            if(a[i].Q>Now) Ans+=Now*2,Now=0;
            else Ans+=a[i].Q*2,Now-=a[i].Q;
            Now+=a[i].H;
        }
        printf("%d\n",Ans);
    }
    return 0;
}

T7(1007)

这题多亏了省队dalao LowestJN的帮助,机房才有人能A掉,当然不是我们队,但是貌似十分可做。
先让我请教一下dalao哈。

一个回复在 “HDU 2018 Multi-University Training Contest 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部