NOIp 2014 Day2 题解

T1 无线网络发射器选址

先看数据范围，128*128？果断直接暴力模拟发射器的位置，但是在计算在(x-d,y-d)到(x+d,y+d)中的之和时要注意边界和范围。什么？代码呢？这么斯波的题自己去写。

T2 联合权值

这道题记得很早以前就做过。条件1如何解决是这道题的难点。如果直接对每个点进行判断能否抵达终点显然会超时的。那么既然我们要判断哪些点能到终点，为啥不从终点反着广搜一遍，看看终点能到哪些点呢？于是思路就显而易见了。将所有路径反向，从终点开始做一遍BFS标记出哪些点是可以作为合法路径，再做一遍spfa（其实貌似BFS也能过）就搞定了。

#include<bits/stdc++.h>
#define N 200005
#define inf 0x3f3f3f3f
using std::queue;

struct Edge{
    int v,nxt;
}e[N],E[N];

int n,m,s,t;
int head[N],tot;
int h[N],tol;

void AddEdge(int u,int v){
    e[++tot]=(Edge){v,head[u]};head[u]=tot;//正向边
    E[++tol]=(Edge){u,h[v]};h[v]=tol;//反向边
}

int vis[N];//表示这个点能直接到达终点
int be[N];//if be[i]== true 表示i没有被删除
int tt;

int dfs(int x,int f){//反向遍历
    vis[x]=true;
    for(int i=h[x];i;i=E[i].nxt){//反向边
        int to=E[i].v;
        if(to==f)continue;
        if(vis[to])continue;
        dfs(to,x);
    }
}

int init(){//删除不能存在于路径上的点
    for(int i=1;i<=n;++i){
        if(!vis[i])continue;bool flag=0;
        for(int j=head[i];j;j=e[j].nxt){
            int to=e[j].v;
            if(!vis[to])flag=true;
        }
        if(!flag)be[i]=true;
    }
}

int dis[N];

int spfa(int s,int t){// 从起点到终点的最短路
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    int top,to;
    dis[s]=0;queue<int>que;que.push(s);vis[s]=true;
    while(!que.empty()){
        top=que.front();
        que.pop();
        for(int i=head[top];i;i=e[i].nxt){
            to=e[i].v;
            if(!be[to])continue;           
            int l;
            if(dis[top]+1<dis[to]){
                dis[to]=dis[top]+1;
                if(!vis[to]){
                    vis[to]=true;
                    que.push(to);
                }
            }
        }
    }
    return dis[t];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    scanf("%d%d",&s,&t);
    dfs(t,0);
    init();
    int ans=spfa(s,t);
    if(ans==inf)ans=-1;
    printf("%d\n",ans);
    return 0;
}

T3 解方程

#include<bits/stdc++.h>
#define maxn 105
#define MOD1 23333
#define MOD2 19260817
using namespace std;
int n,m,a1[maxn],a2[maxn],vis[1000005];
vector<int>ans;
void read(int pos){
    char c=getchar();
    int x1=0,x2=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x1=(x1*10+c-'0')%MOD1;
        x2=(x2*10+c-'0')%MOD2;
        c=getchar();
    }
    a1[pos]=x1*f;
    a2[pos]=x2*f;
}
int check(int f[],int x,int mod) {
            int y=0;
            for(int i=n;i>=0;i--)
            y=((long long)y*x+f[i])%mod;                       
            return (!y)? 1:0;
}
int main(){
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)read(i);
    for(int i=1;i<=MOD1;i++)
       if(check(a1,i,MOD1))
           for(int j=i;j<=m;j+=MOD1)
             if(check(a2,j,MOD2))
                    vis[j]=1;
    for(int i=1;i<=m;i++)
         if(vis[i])ans.push_back(i);
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);
    return 0;
}