【NOIP2014】DAY2题解+代码

傻逼题……不想写贴昨年代码了。

总之随便怎么搞都能过、

15年的DAY2T1怎么那么毒瘤真是越活越倒退】

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <cstring>

#include <cmath>

using namespace std;

ifstream fin("wireless.in");

ofstream fout("wireless.out");

struct lk

{

 int x;

 int y;

 int gs;

};

lk citys[];

int fw=,lks=;

int search(int xc,int yc);//查找当前范围有多少个公共设施被覆盖

int main(void)

{

 fin>>fw>>lks;

 int a=,b=,sl=;

 for(int i=;i<=lks;i++)

    {

     fin>>a>>b>>sl;

     citys[i].x=a;

     citys[i].y=b;

     citys[i].gs=sl;

    }

 int ans=,tot=,fas=;

 for(int i=;i<=;i++)

    {

     for(int j=;j<=;j++)

        {

         tot=search(i,j);

         if(ans==tot)fas++;

         if(ans<tot)fas=;

         ans=max(tot,ans);

        }

    }

 fout<<fas<<" "<<ans;

 return ;

}

int search(int xc,int yc)

{

 int pdx=,pdy=,zgs=;

 for(int i=;i<=lks;i++)

    {

     pdx=abs(citys[i].x-xc);

     pdy=abs(citys[i].y-yc);

     if(pdx<=fw&&pdy<=fw)zgs+=citys[i].gs;

    }

 return zgs;

}

先反边，求一遍终点能到的点。再预处理一下判定那些点可以出现在路径上、

最后随便搜一下。

这题最后一个数据专卡DFS。卡得飞起，换成了BFS之后快得飞起、】

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

struct lb

{

    int nw;

    int to;

};

lb line[],anti[];

int n=,m=,head[]={},anth[]={};

int cnt1=,cnt2=,st=,ed=,dis[]={};

int check[]={};

void add(int f,int t);

void a_add(int f,int t);

void fid(int nw);

void solve();

int main(void)

{

    freopen("road.in","r",stdin);

    freopen("road.out","w",stdout);

    memset(dis,0x7f/,sizeof(dis));

    const int INF=dis[];

    scanf("%d%d",&n,&m);

    int a=,b=;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d",&a,&b);

        add(a,b);

        a_add(b,a);

    }

    scanf("%d%d",&st,&ed);

    check[ed]=;

    fid(ed);

    int next=;

    for(int i=;i<=n;i++)

    {

        if(check[i])

        {

            for(int j=head[i];j>;j=line[j].to)

            {

                next=line[j].nw;

                if(check[next]==)

                {

                    check[i]=-;

                    break;

                }

            }

        }

    }

    dis[st]=;

    solve();

    if(dis[ed]!=INF)printf("%d",dis[ed]);

    else printf("-1\n");

    return ;

}

void add(int f,int t)

{

    line[++cnt1].nw=t;

    line[cnt1].to=head[f];

    head[f]=cnt1;

    return;

}

void a_add(int f,int t)

{

    anti[++cnt2].nw=t;

    anti[cnt2].to=anth[f];

    anth[f]=cnt2;

    return;

}

void fid(int nw)

{

    if(nw>n)return;

    int next=;

    for(int i=anth[nw];i>;i=anti[i].to)

    {

        next=anti[i].nw;

        if(check[next])continue;

        check[next]=;

        fid(next);

    }

    return;

}

void solve()

{

    int dl[]={},tou=,wei=,next=;

    dl[]=st;

    do

    {

        tou++;

        if(tou>)tou=;

        for(int i=head[dl[tou]];i>;i=line[i].to)

        {

            next=line[i].nw;

            if(dis[next]<=dis[dl[tou]]+||check[next]!=)continue;

            wei++;

            if(wei>)wei=;

            dl[wei]=next;

            dis[next]=dis[dl[tou]]+;

        }

    }while(tou!=wei);

    return;

}

我不会搞啊真的不会搞啊

但是我A过QAQ昨年AC过这题QAQ

代码贴上来好了……

#include <algorithm>

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <cstring>

#include <string>

#include <cmath>

using namespace std;

ifstream fin("equation.in");

ofstream fout("equation.out");

long long int xs[][]={};//系数

const int mo[]={,,,,,};

long long int pd[][]={};

int N=,M=,ans[]={},gs=;

void dr(int bh);

long long int ycl(int sum,int mox);//传说中的预处理

int main(void)

{

 fin>>N>>M;

 for(int i=;i<=N+;i++)dr(i);

// for(int i=1;i<=N+1;i++)cout<<xs[i][1]<<"\n";

 for(int i=;i<=;i++)

    {

    for(int j=;j<=mo[i];j++)

       {

        pd[j][i]=ycl(j,i);

       }

    }

 bool fg=false;

 for(int i=;i<=M;i++)

    {

     fg=false;

     for(int j=;j<=;j++)

        {

        if(pd[i%mo[j]][j])

          {

           fg=true;

           break;

          }

        }

     if(fg==false)ans[++gs]=i;

    }

 fout<<gs<<"\n";

 for(int i=;i<=gs;i++)fout<<ans[i]<<"\n";

 return ;

}

void dr(int bh)

{

 string s;

 bool jl=false;

 fin>>s;

 for(int i=;i<s.size();i++)

    {

     if(s[i]=='-')jl=true;

     else

       {

        for(int j=;j<=;j++)

           {

            xs[bh][j]=(xs[bh][j]*+s[i]-'')%mo[j];

           }

       }

    }

 if(jl)

    for(int i=;i<=;i++)xs[bh][i]=mo[i]-xs[bh][i];

}

long long int ycl(int sum,int mox)

{

 long long int tot=0ll;

 for(int i=N+;i>;i--)

    {

     tot=(tot*sum+xs[i][mox])%mo[mox];

     //if(sum==1)cout<<tot<<"\n";

    }

 return tot;

}

巴特西

【NOIP2014】DAY2题解+代码

最新文章

热门文章