NOIP2014复赛提高组day2（A：无线网络发射器选址 B：寻找道路 C：解方程）

时间：2022-12-16 15:55:02

今天是博主考的最差的一天，1、2两题全WA了。。。Orz。。。
A题：
这题完全可以 129×129×40×40 的复杂度暴力A掉
而我却认为暴力是 129×129×129×129 的复杂度
于是敲了一个二维前缀和
然后不知道为什么智障的没把所有坐标都加1，竟然用 0 ~ 128 的下标在那前缀和！！！！
还搞来搞去费力的维护当 l<=0 的情况，
结果费力不讨好。。成功的WA了( 70 分)
AC代码Orz。。。
//暴力O( n2⋅d2 )

#include<bits/stdc++.h>
using namespace std;
#define M 205
int mark[M][M];
int main(){
int d,cnt=0,ans=0;
scanf("%d",&d);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y,k;
scanf("%d %d %d",&x,&y,&k); 
        mark[x][y]=k;
    }for(int i=0;i<=128;i++)
for(int j=0;j<=128;j++){
int res=0;
for(int a=max(0,i-d);a<=min(128,i+d);a++)//暴力T。。(⊙﹏⊙)b。。
for(int b=max(0,j-d);b<=min(128,j+d);b++)//没什么好解释的。。。
                    res+=mark[a][b];
if(res>ans)ans=res,cnt=1;
else if(res==ans)cnt++;
        }
printf("%d %d\n",cnt,ans);
return 0;
}

B题：
这题WA的很冤。。。
因为有两个 mark 数组【一个 mark ，一个MARK】
一不小心把其中一个 mark 写成了MARK
自信AC没有对拍。。。
于是WA的只剩20分。。
好端端的就少了80分
首先这题其实还是比较容易的
这题我们肯定是要先找出那些点到达不了点 t ，这是显然的
但是如果一个个点 for 过去肯定是 TLE 没商量的
于是这个时候一个比较直观的思路就是
将所有的边反向
而后若点 t 不能到达某一个点，那么这一个点走正向边时就不能到达点 t
然后把能到达这个点的所有点及这个点从原图中抹去不再使用就行了，
最后再跑一遍 BFS 就行了
由于我们刚开始存的是反向边
为了节省一下内存，可以直接从点 t 跑回点 s
于是乎这道水题就解决了

#include<bits/stdc++.h>
using namespace std;
#define M 10005
void Rd(int &res){
char c;res=0;
while(c=getchar(),!isdigit(c));
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),isdigit(c));
}
vector<int>edge[M];
int mark[M],Q[M<<1],MARK[M];
void BFS(int s){//BFS遍历有向图
int l=0,r=0;
    Q[r++]=s;mark[s]=1;
while(l<r){
int x=Q[l++];
for(int i=0;i<edge[x].size();i++){
int y=edge[x][i];
if(mark[y])continue;
            mark[y]=1;
            Q[r++]=y;
        }
    }
}
struct node{
int x,step;
}QQ[M<<1];
int RBFS(int s,int t){//BFS寻找最短路
    node tmp;
    tmp.x=s;
    tmp.step=0;
int l=0,r=0;
    QQ[r++]=tmp;MARK[s]=1;
while(l<r){
        tmp=QQ[l++];int x=tmp.x;
for(int i=0;i<edge[x].size();i++){
int y=edge[x][i];
            node nxt;
            nxt.x=y;nxt.step=tmp.step+1;
if(!mark[y]||MARK[y])continue;
if(y==t)return nxt.step;
            MARK[y]=1;
            QQ[r++]=nxt;
        }
    }return -1;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
while(m--){
int x,y;
        Rd(x);Rd(y);
        edge[y].push_back(x);//将读入的边反向
    }int s,t;
scanf("%d %d",&s,&t);
    BFS(t);
for(int i=1;i<=n;i++)
if(!mark[i])//点i不能到达点t
for(int j=0;j<edge[i].size();j++)
                MARK[edge[i][j]]=1;//将所有能到达点i的点全部mark
for(int i=1;i<=n;i++)if(MARK[i])mark[i]=0;
memset(MARK,0,sizeof(MARK));
printf("%d\n",RBFS(t,s));
return 0;
}

C题：
其实这题正解的代码只有30行
可以说是历届NOIP代码量最小第三题
xiaoC也说2014年的题出的不好
（除了飞扬的小鸟）
这题一样想到哈希之后随便哈希一个数就能有70分
高精敲的累死累活才50分(博主就是此类人)
先奉上暴力高精代码

//PS：高精代码，过于繁琐，博主都不想注释了，随便瞥两眼就好
#include<bits/stdc++.h> 
using namespace std;
#define M 3005
#define N 105
#define K 1000005 
#define P 10000
struct Bigint{
int f,len,val[M];
    Bigint(){
len=0;f=1;
        memset(val,0,sizeof(val));
    }
    void Input(){
        char str[M<<2];
        scanf("%s",str);
int LEN=strlen(str);int l=0;
if(str[0]=='-')l=1,f=-1;
else f=1;
for(int i=LEN-1;i>=l;i-=4){
len++;
for(int j=3;j>=0;j--)
if(i-j>=l)val[len-1]=(val[len-1]<<3)+(val[len-1]<<1)+(str[i-j]^48);
        }
    }
    void Output(){
if(f==-1)putchar('-');
        printf("%d",val[len-1]);
for(int i=len-2;i>=0;i--)printf("%04d",val[i]);puts("");
    }
bool operator <(const Bigint &A)const{
if(len!=A.len)return len<A.len;
for(int i=len-1;i>=0;i--)
if(val[i]!=A.val[i])return val[i]<A.val[i];
return false;
    } 
    Bigint operator -(const Bigint &A)const{
        Bigint tmp;
        tmp.len=len;tmp.f=f;
for(int i=0;i<len;i++)tmp.val[i]=val[i];
if(tmp<A){
            tmp=A-tmp;
            tmp.f=-1;
        }else{
for(int i=0;i<len;i++){
                tmp.val[i]-=A.val[i];
if(tmp.val[i]<0){
                    tmp.val[i]+=P;
                    tmp.val[i+1]--;
                }
            }while(tmp.len&&!tmp.val[tmp.len-1])tmp.len--;
if(!tmp.len){
                tmp.len++;
                tmp.val[0]=0;
            }tmp.f=1;
        }return tmp;
    }
    Bigint operator +(const Bigint &A)const{
        Bigint tmp;
if(f==A.f){ 
            tmp.len=len;tmp.f=f;
if(A.len>tmp.len)tmp.len=A.len;
for(int i=0;i<tmp.len;i++){
                tmp.val[i]+=val[i]+A.val[i];
if(tmp.val[i]>=P){
                    tmp.val[i+1]++;
                    tmp.val[i]-=P;
                }
            }if(tmp.val[tmp.len])tmp.len++;
return tmp;
        }else {
            Bigint tmp;
            tmp.len=len;tmp.f=f;
for(int i=0;i<len;i++)tmp.val[i]=val[i];
if(f==1)return tmp-A;
else return A-tmp;
        }
    }
    Bigint operator *(const Bigint &A)const{
        Bigint tmp;
        tmp.len=len+A.len-1;
        tmp.f=f*A.f;
for(int i=0;i<len;i++)
for(int j=0;j<A.len;j++)
                tmp.val[i+j]+=val[i]*A.val[j];
for(int i=0;i<tmp.len;i++)
if(tmp.val[i]>=P){
                tmp.val[i+1]+=tmp.val[i]/P;
                tmp.val[i]%=P;
            }
if(tmp.val[tmp.len])tmp.len++;
return tmp;
    }
}a[N];
int ans[K];
int main(){
int n,m,f=1,k=0;
    scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++){
        a[i].Input();
        Bigint tmp;
        tmp.len=1;tmp.f=1;
        tmp.val[0]=0;
if(a[i].f==-1)f=0;
    }if(f){
        puts("0");
return 0;
    }for(int i=1;i<=m;i++){
int x=i;
        Bigint res,tmp,T;
        while(x){
            T.val[T.len++]=x%P;
            x/=P;
        }tmp.len=1;tmp.val[0]=1;
        res=a[0];
for(int j=1;j<=n;j++){
            tmp=tmp*T;
            res=res+a[j]*tmp;
        }if(res.len==1&&!res.val[0])ans[++k]=i;
    }printf("%d\n",k);
for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
return 0;
}

而后我们来思考正解
显而易见的是，如果res=0，那么res%P=0
于是我们很容易想到哈希
但是哈希明显会产生冲突
于是就搞好几个数哈希就行了
然而那些用 1e9+7 和 1e9+9 这两个孪生素数哈希的人我也就不做评价了。。
简直作死好么
好不容易把高精的数字变小，你还搞这么大， no zuo no die 啊，孩纸！！
多弄几个小一点的数哈希不好么。。。。Orz！！！
还有那些用高精的人
。。。
读入一个Bigint，然后搞高精模。。。我也是醉了
这样复杂度好高的啊
为什么不在读入的时候直接模呢？？
然后模好之后我们就可以计算表达式的值了
但是计算表达式值得时候直接算可能系数比较大
然后我们根据秦九昭算术的公式(其实这是显然的，什么 low 公式)
a0+a1x+a2x2+…+an−1xn−1+anxn=a0+x(a1+x(a2+x(……)))
于是乎计算表达式值得伪代码是这样的
for i = n−>1
　 res=res∗x+ai
于是乎，巨短的正解代码就出炉了。。(虽然有缩行的嫌疑。。。)

//PS：开这么一个二维数组程序速度回变慢，但是写着不繁琐，自己看着办吧、
/*
你也可以用这一个黑科技
#define f(x,y) x##y //这代表将x、y连在一起
然后数组可以这样定义：
int a0[M]，a1[M]，a2[M],a3[M];
这样就可以用for，既省时间，又简洁
比如读入的时候：
for(int i=0;i<4;i++)
    f(a,i)[id]=((f(a,i)[id]<<3)+(f(a,i)[id]<<1)+(c^48))%P[i];
*/
#include<bits/stdc++.h> 
using namespace std;
#define N 105
#define M 10005
short a[4][N],P[4]={9941,9949,9967,9973},res[4][M];
//P数组中存的是10000以下最大的4个素数
//a[i][x]代表读入的第x个数模P[i]的结果
//这几个数组中的数都在10000以下，用short省内存
int ans[M];
void Rd(int id){
    char c;int k=1;
while(c=getchar(),!isdigit(c)&&c!='-');
if(c=='-')k=-1,c=getchar();
do {
for(int i=0;i<4;i++)
            a[i][id]=((a[i][id]<<3)+(a[i][id]<<1)+(c^48))%P[i];//读入的时候针对每一个P[i]取模
    }while(c=getchar(),isdigit(c));
if(k==-1)
for(int i=0;i<4;i++)
            a[i][id]=(-a[i][id]+P[i])%P[i];
}
int main(){
int n,m,k=0;
    scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++)Rd(i);
for(int k=0;k<4;k++)
for(int i=0;i<P[k];i++)//哈希，计算出对于每一个人P[i]每个数的小于p[i]的数作为x的情况的值
for(int j=n;j>=0;j--)
                res[k][i]=(res[k][i]*i+a[k][j])%P[k];
for(int i=1;i<=m;i++)
if(!res[0][i%P[0]]&&!res[1][i%P[1]]&&!res[2][i%P[2]]&&!res[3[i%P[3]])ans[++k]=i;
//使用每一个P都满足res%P=0，那么我们就可以认为res=0了
printf("%d\n",k);
for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
return 0;
}

140 分爆炸了55555！！！！Orz。。。
标签：

相关文章