NOIP2017

D1T1:math(小凯的疑惑)

看到这道题当时还是很困惑的,这样简单的题面我不应当不会啊,然而(

30min之后用筛法水过去了:score=60;

标准解法是:拓展欧几里得(打表)

实际上知道【最大不可表数】的知识点以后,我们马上就可以知道答案是a*b-a-b;

代码如下:

#include<iostream>
#include<fstream>
using namespace std;
int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    long long a,b;
    cin>>a>>b;
    cout<<a*b-a-b<<endl;
    return 0;
}

 这里如果使用printf输出,要注意使用lld还是l64d。

D1T2:complexity(时间复杂度)

这道题很明显是一道大模拟。(拍了两个半小时)

要注意的点还是很多的,有很多人在读入部分就爆炸,因为个人的时间问题就不再多讲了。

第一个是t组数据,第二个是每组数据有L行,第三个是判断E/F。

很多人用getline读,最后导致爆零,其实直接cin就好了(才不会告诉你们我是没想到用getline)

似乎没有太多要讲的,直接上代码。

#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
using namespace std;
int s[101],t,l,top,maxn;
char h[101],k,b;
string x,y,a;
bool p,q;
int count1(){//提取复杂度数字
    int x=0;
    for (int i=4;i<a.length()-1;i++)
        x*=10,x+=int(a[i]-48);
    return x;
}
int count2(string a){//提取数值
    int num=int(a[0]-48);
    for (int i=1;i<a.length();i++)
        num*=10,num+=int(a[i]-48);
    return num;
}
bool work1(){
    cin>>k>>x>>y;
    h[++top]=k;
    if (x=="n"){
        if (y=="n") s[top]=1;
        else s[top]=0;
    }else{
        if (y=="n") s[top]=2;
        else{
            int sx=count2(x),sy=count2(y);
            s[top]=int(sx<=sy);
        }
    }
    for (int i=1;i<top;i++)
        if (k==h[i]) return false;
    return true;
}
bool work2(){
    if (top==0) return false;
    int sum=0;
    for (int i=1;i<=top;i++){
        if (s[i]==0) break;
        if (s[i]==2) sum++;
    }
    top--;
    maxn=max(sum,maxn);
    return true;
}
int main(){
    freopen("complexity.in","r",stdin);
    freopen("complexity.out","w",stdout);
    cin>>t;
    for (int m=1;m<=t;m++){
        top=0,maxn=0,q=true;
        cin>>l>>a;
        int kind=(a[2]=='n')?count1():0;
        for (int i=1;i<=l;i++){
            cin>>b;
            if (b=='F') p=work1();
            else p=work2();
            if (!p) q=false;
        }
        if (top!=0||!q) cout<<"ERR"<<endl;
        else{
            if (kind==maxn) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

核心思想是用栈模拟。

这里有一个栈顶指针的问题,我最后只拿了90分,因为没有判断E比F多的情况,所以有一个点里面top爆到负数了……

看了一下其他大佬的题解,添加一个注意点,就是中间判断出是ERR之后要继续读完。(这里我是用bool p,q;实现的)

D1T3 park(逛公园)

写完T2已经只剩最后半小时了。(我太水了)

至于解法……(咕咕咕)

D2T1 cheese(奶酪)

考场上三分钟出思路:宽搜

具体方法就是先把所有位于奶酪底层的点入队,然后维护这个队列,用遍历的方式搜索,直到搜到的点在顶层或者搜完为止。

要注意的几个点是精度,还有就是有的洞是既在底层又在顶层……

#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int x[1001],y[1001],z[1001],kind[1001],q[1001];
bool v[1001],p;
int n,t,h,r;
double d(int i,int j){
    double a=x[i]-x[j];
    double b=y[i]-y[j];
    double c=z[i]-z[j];
    return sqrt(a*a+b*b+c*c);
}
void work(int k){
    memset(kind,0,sizeof(kind));
    memset(v,false,sizeof(v));
    int l=1,rs=0;p=false;
    scanf("%d%d%d",&n,&h,&r);
    for (int i=1;i<=n;i++){
       scanf("%d%d%d",&x[i],&y[i],&z[i]);
       if (z[i]-r<=0) kind[i]+=2;
       if (z[i]+r>=h) kind[i]+=1;
       if (kind[i]>1) q[++rs]=i,v[i]=true;
    }
    while (l<=rs){
        int x=q[l++];
        if (kind[x]%2==1){
            p=true;
            break;
        }
        for (int i=1;i<=n;i++)
            if (!v[i])
                if (d(x,i)<=2*r) q[++rs]=i,v[i]=true;
    }
    if (p) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
}
int main()
{
    scanf("%d",&t);
    for (int it=1;it<=t;it++)
        work(it);
    return 0;
}

上面的是我考场上的源代码,现在一看真的丑得不行,于是我重写了一遍:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int q[1001],x[1001],y[1001],z[1001],k[1001];
int n,h,c;
bool v[1001];
double d(int i,int j){
    double a=x[i]-x[j],b=y[i]-y[j],c=z[i]-z[j];
    return sqrt(a*a+b*b+c*c);
}
int main(){
    int t;scanf("%d",&t);
    while (t--){
        memset(v,0,sizeof(v));
        memset(k,0,sizeof(k));
        scanf("%d%d%d",&n,&h,&c);
        int l=1,r=0;
        for (int i=1;i<=n;i++){
            scanf("%d%d%d",&x[i],&y[i],&z[i]);
            if (z[i]<=c) k[i]++,q[++r]=i;
            if (z[i]>=h-c) k[i]+=2;
        }
        bool flag=false;
        while (l<=r){
            if (k[q[l]]>1){flag=true;break;}
            for (int i=1;i<=n;i++)
                if (!v[i]&&d(q[l],i)<=2*c) q[++r]=i,v[i]=true;
            l++;
        }
        if (flag) printf("Yes\n");
            else printf("No\n");
    }
    return 0;
}

D2T2 treasure(宝藏)

考场上抓耳挠腮半天,最后居然瞎写了个树型DP就交上去了……最后莫名其妙25分(运气真好  

正解是状压DP

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=15;
int n,m,x,y,u;
long long g[MAXN][MAXN];
long long f[MAXN][1<<12],d[MAXN][1<<12],D[1<<12][1<<12];
long long ans=0x7f7f7f7f,l;
int main(){
    scanf("%d%d",&n,&m);u=(1<<n)-1;
    memset(g,0x7f,sizeof(g));
    memset(d,0x7f,sizeof(d));
    for (int i=1;i<=m;i++){
        scanf("%d%d%lld",&x,&y,&l);
        g[x][y]=g[y][x]=min(g[y][x],l);
    }
    for (int i=1;i<=n;i++)
        for (int s=0;s<(1<<n);s++)
            for (int j=1;j<=n;j++)
                if ((s>>(j-1))&1) d[i][s]=min(d[i][s],g[j][i]);
    for (int s=0;s<(1<<n);s++)
        for (int S=s^u;S;S=(S-1)&(s^u))
            for (int i=1;i<=n;i++)
                if ((S>>(i-1))&1){
                    if (d[i][s]==d[0][0]){D[s][S]=0;break;}
                    D[s][S]+=d[i][s];
                }
    for (int r=1;r<=n;r++){
        memset(f,0x7f,sizeof(f));
        f[1][1<<(r-1)]=0;
        for (int i=2;i<=n;i++)
            for (int s=0;s<(1<<n);s++)
                for (int S=s^u;S;S=(S-1)&(s^u))
                    if (f[i-1][s]!=f[0][0]&&D[s][S]) f[i][s|S]=min(f[i][s|S],f[i-1][s]+D[s][S]*(i-1));
            for (int i=1;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);
    }
    printf("%lld\n",ans);
    return 0;
}

D2T3 phalanx(列队)

考场上花了半个小时写了个模拟交上去,骗了30分(果然我超菜的  

正解可以线段树(但我喜欢树状数组,那就写个树状数组吧   

不难发现的是每一行是相对独立的,所以我们可以用一个vector存储加入的同学,同时对于最后一列,我们用树状数组维护。

发表评论

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