HDU 2018 Multi-University Training Contest 4

2018 Multi-University Training Contest 4

首先说一下我这次ACM的感想。

我们最早有想法的题是T2,因为这题学长前几天才讲过 :joy:。

接下来就是T11了,一道模拟,然后就一脸懵逼的看着T12那么多人A掉,我不会啊QAQ :scream:。

过了一会儿,这道SB题,我尽然没有一眼看出来,我该退役了。

然后我就要吐槽一下T4,我一开始题目理解错了,导致WA3,然后又因为脑袋嗯哼了,所以又WA1 :sweat:。

T5想法是有了,但是没时间了,所以GG。

T12(6343)

这题只要从1走到n就好了,所以答案就是sqrt(abs(w[1]-w[n]))。

是不是很懵啊,我们先假设没有sqrt,那么他的路径权值是俩数相减,所以从1走到n至少需要abs(w[1]-w[n])的代价,那么开根号也是这样啊。

被自己蠢到了。

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100005];
long long Ans=0;
int _abs(int x){return x<0?-x:x;}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);Ans=0;int Numn=0,Num1=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        Num1=a[1];Numn=a[n];
        printf("%lld\n",(long long)sqrt(_abs(Numn-Num1)));
    }
    return 0;
}

T11(6342)

这题也就跟题目模拟一下,如果是?那么都放1就可以了,但是有特殊情况,0?0,那么这个问号就需要变成符号,然后就AC了。

这题是队友打的,但是是我A的,所以码风有点奇怪。

#include<bits/stdc++.h>
using namespace std;
char s[505],cs[505];
inline bool check(int len){
    int i=0;
    while (i<len)
    if (!isdigit(cs[i])){
        if (i==0||i==len-1)return 0;
        i++;
        if (!isdigit(cs[i]))return 0;
        if(cs[i]=='0'){
            if(i+1>=len) return 1;
            if(s[i+1]=='?'){
                if(i+2>=len||!isdigit(cs[i+2])) return 0;
                cs[i+1]='+';
            }else 
            if(isdigit(cs[i+1])) return 0;
        }
        while (isdigit(cs[i])&&i<len)i++;
    }else{
        if(cs[i]=='0'){
            if(i+1>=len) return 1;
            if(s[i+1]=='?'){
                if(i+2>=len||!isdigit(cs[i+2])) return 0;
                cs[i+1]='+';
            }else 
            if(isdigit(cs[i+1])) return 0;
        }
        while (isdigit(cs[i])&&i<len)i++;
    }
    return 1;
}
int T,len;
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%s",s);
        len=strlen(s);s[len]=0;cs[len]=0;
        for (int i=0;i<len;i++)if (s[i]=='?')cs[i]='1';else cs[i]=s[i];
        if (check(len))cout<<cs<<endl;else cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}

T4(6335)

不管题目描述了,我到现在还没看懂,是队友告诉我过程的,然后我就跟过程写了。

其实这题样例验证出来就会做了。(队友就是解释样例的)

因为ai==1,所以我们可以知道哪些题目的正确率要高,从高的开始做,然后当前人数乘上正确的概率,因为是最坏情况,所以向下取整,直到人数为0时,过的题数就是答案。

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
int n,a[105];
LL Ans,m;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("T4.in","r",stdin);
    freopen("T4.out","w",stdout);
    #endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&m);Ans=0;
        for(int i=1;i<=n;i++) scanf("%*d%d",&a[i]);
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++) m=m/(a[i]+1),Ans+=(m>0);
        printf("%lld\n",Ans);
    }
    return 0;
}

T10(6341)

其实爆搜就可以了,加上剪枝就可以了,因为是数独所以剪枝的优化效果特别好,剪枝不用多说了吧。

#include<cstdio>
using namespace std;
char ch[10][10][10][10],s[20][20];
int T,Num[10][10],hsh[255],Ans;
bool t;
void Rotate(int x,int y){
    char ss[10][10];
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++) ss[i][j]=ch[x][y][4-j-1][i];
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++) ch[x][y][i][j]=ss[i][j];
}
bool check(int x,int y){
    for(int k=0;k<4;k++){
        for(int i=0;i<10;i++) hsh[i+'0']=0;
        for(int i=0;i<=5;i++) hsh[i+'A']=0;
        for(int j=1;j<=y;j++)
        for(int p=0;p<4;p++) if(hsh[ch[x][j][k][p]]) return 0;else hsh[ch[x][j][k][p]]=1;
    }
    for(int p=0;p<4;p++){
        for(int i=0;i<10;i++) hsh[i+'0']=0;
        for(int i=0;i<=5;i++) hsh[i+'A']=0;
        for(int i=1;i<=x;i++)
        for(int k=0;k<4;k++) if(hsh[ch[i][y][k][p]]) return 0;else hsh[ch[i][y][k][p]]=1;
    }
    return 1;
}
void DFS(int x,int y){
    if(x>4){int Now=0;for(int i=1;i<=4;i++)for(int j=1;j<=4;j++) Now+=Num[i][j]/*,printf(j==4?"%d\n":"%d ",Num[i][j])*/;Ans=(Ans>Now?Now:Ans);return;}
    for(int t=0;t<4;t++){
        if(check(x,y)) DFS(x+(y==4),y%4+1);
        Num[x][y]++;Rotate(x,y);
    }
    Num[x][y]=0;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("T10.in","r",stdin);
    freopen("T10.out","w",stdout);
    #endif
    scanf("%d",&T);
    while(T--){
//        for(int i=1;i<=4;i++)
//        for(int j=1;j<=4;j++) Num[i][j]=0;
        for(int i=0;i<16;i++) scanf("%s",s[i]);Ans=1e9;
        for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        for(int k=0;k<4;k++)
        for(int p=0;p<4;p++) ch[i][j][k][p]=s[k+(i-1)*4][p+(j-1)*4];
        DFS(1,1);printf("%d\n",Ans);
    }
    return 0;
}

T2(6333)

这题虽然是第三个A掉的题,但是还是有点难度的。

定义Sum(n,m)=\sum^m_{i=0} C(n,i)

不难发现Sum(n,m)=Sum(n,m-1)+C(n,m)

然后稍微推一下,就可以退出Sum(n,m)=2 * Sum(n-1,m)-C(n-1,m)

然后用莫队维护就可以了。

这题是队友打的,但我不知道为什么打的这么长。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=1e5+6,tt=1e9+7;
int id[maxn],cnt,n,MAXN,ans[maxn],L,R,f[maxn],ni[maxn];
int rad()
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
struct js{
    int L,R,ic;
    void rd(int i){R=rad();L=rad();ic=i;if(R>MAXN)MAXN=R;}
    bool operator <(const js&b)const{return id[L]<id[b.L]||(id[L]==id[b.L]&&((id[L]&1)^(R<b.R)));}
}a[maxn];
LL sum;
void exgcd(int a,int b,int &x,int &y){if (b==0){x=a;y=0;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
int C(int n,int m){return 1ll*f[n]*ni[m]%tt*ni[n-m]%tt;}
int main()
{
    sum=1;f[0]=1;
    for (int i=1;i<=100000;++i) f[i]=1ll*f[i-1]*i%tt;
    int x,y;exgcd(f[100000],tt,x,y);if (x<0) x+=tt;ni[100000]=x;
    for (int i=99999;i>=1;--i) ni[i]=1ll*ni[i+1]*(i+1)%tt;ni[0]=1;
//    for (int i=1;i<=100000;++i) if (1ll*f[i]*ni[i]%tt!=1) printf("ERROR\n");
    MAXN=0;
    n=rad();L=1,R=1;sum=1;
    for (int i=1;i<=n;++i) a[i].rd(i);
    cnt=sqrt(MAXN);
    for (int i=1;i<=MAXN;++i) id[i]=id[i-1]+(i%cnt==1);
    sort(a+1,a+n+1);
    for (int i=1;i<=n;++i)
    {
        if (a[i].R<L)
        {
            while (L<a[i].L) {sum=(sum+C(R,++L))%tt;}
            while (L>a[i].L) {sum=(sum-C(R,L--)+tt)%tt;}
            while (R<a[i].R) {sum=((sum<<1|1)-C(R++,L)+tt)%tt;}
            while (R>a[i].R) {sum=(sum-1+C(--R,L))%tt*ni[2]%tt;}
        }else{
            while (R<a[i].R) {sum=((sum<<1|1)-C(R++,L)+tt)%tt;}
            while (R>a[i].R) {sum=(sum-1+C(--R,L))%tt*ni[2]%tt;}
            while (L<a[i].L) {sum=(sum+C(R,++L))%tt;}
            while (L>a[i].L) {sum=(sum-C(R,L--)+tt)%tt;}
        }
        ans[a[i].ic]=(sum+1)%tt;
    }
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

T5(6336)

讲一下这题想法吧,画出矩阵后,会发现这个矩阵是循环的,所以我们可以把大矩阵分割,割成四个角、四条边和中心一块,然后注意一下细节就可以了,然而,就是因为细节,导致来不及了,因为最后半个小时才开始打QAQ。

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

发表评论

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

返回顶部