题解：

D1T1 生活大爆炸版石头剪刀布

水题送温暖~

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

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

 int n,n1,n2,ans1,ans2,a[],b[];

 int main(){

     scanf("%d%d%d",&n,&n1,&n2);

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

         scanf("%d",&a[i]);

     }

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

         scanf("%d",&b[i]);

     }

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

         ans1+=ch[a[(i-)%n1]][b[(i-)%n2]];

         ans2+=ch[b[(i-)%n2]][a[(i-)%n1]];

     }

     printf("%d %d",ans1,ans2);

     return ;

 }

D1T2 联合权值

题面

和一个同点相连的两个点一定会产生联合权值；

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 #define mod 10007

 using namespace std;

 typedef long long ll;

 struct edge{

     int v,next;

 }a[];

 int n,u,v,tot=,ans=-inf,anss=,top,s[],num[],head[];

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void work(int u){

     int sum=,mx=-inf,mmx=-inf;

     top=;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         s[++top]=v;

         sum+=num[v];

         if(num[v]>mx){

             mmx=mx;

             mx=num[v];

         }else mmx=max(mmx,num[v]);

     }

     if(top<)return;

     ans=max(ans,mx*mmx);

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

         anss=(anss+(ll)num[s[i]]*(sum-num[s[i]]))%mod;

     }

 }

 int main(){

     memset(head,-,sizeof(head));

     scanf("%d",&n);

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

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     for(int i=;i<=n;i++)scanf("%d",&num[i]);

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

         work(i);

     }

     printf("%d %d",ans,anss);

     return ;

 }

D1T3 飞扬的小鸟

题面

唯一可能有点思维难度的题？70分显然，正解就向上向下分两种背包（01和完全）转移即可；

（1A爽爽）

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 0x7f7f7f7f

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 int n,m,k,p,L,H,tmp,ans=inf,x[],y[],l[],h[],f[][];

 bool isp[];

 int main(){

     memset(f,0x7f,sizeof(f));

     memset(isp,,sizeof(isp));

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

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

         scanf("%d%d",&x[i],&y[i]);

         l[i]=;

         h[i]=m+;

     }

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

         scanf("%d%d%d",&p,&L,&H);

         isp[p]=true;

         l[p]=L;

         h[p]=H;

     }

     for(int i=;i<=m;i++)f[][i]=;

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

         for(int j=x[i]+;j<=m;j++){

             f[i][j]=min(f[i][j],f[i-][j-x[i]]+);

             f[i][j]=min(f[i][j],f[i][j-x[i]]+);

         }

         for(int j=m-x[i];j<=m;j++){

             f[i][m]=min(f[i][m],min(f[i][j]+,f[i-][j]+));

         }

         for(int j=l[i]+;j<h[i];j++){

             if(j+y[i]<=m){

                 f[i][j]=min(f[i][j],f[i-][j+y[i]]);

             }

         }

         for(int j=;j<=l[i];j++)f[i][j]=inf;

         for(int j=h[i];j<=m;j++)f[i][j]=inf;

     }

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

         ans=min(ans,f[n][i]);

     }

     if(ans==inf){

         ans=;

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

             tmp=inf;

             for(int j=;j<=m;j++)tmp=min(tmp,f[i][j]);

             if(tmp==inf)break;

             if(isp[i])ans++;

         }

         printf("0\n%d",ans);

     }else printf("1\n%d",ans);

     return ;

 }

D2T1 无线网络发射器选址

题面

水题送温暖~

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 int n,d,x,y,k,ans=,tmp,anss=,mp[][];

 int main(){

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

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

         scanf("%d%d%d",&x,&y,&k);

         mp[x][y]=k;

     }

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

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

             tmp=;

             for(int x=max(i-d,);x<=min(i+d,);x++){

                 for(int y=max(j-d,);y<=min(j+d,);y++){

                     tmp+=mp[x][y];

                 }

             }

             if(tmp>ans){

                 ans=tmp;

                 anss=;

             }else if(tmp==ans)anss++;

         }

     }

     printf("%d %d",anss,ans);

     return ;

 }

D2T2 寻找道路

题面

什么时候裸的最短路可以上D2T2了？？显然建反向边把不能到达的点判掉，然后裸的最短路；

（并没有卡SPFA好评）

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 struct edge{

     int v,next;

 }a[],_a[];

 int n,m,u,v,vs,vt,tot=,_tot=,head[],_head[],sp[];

 bool isin[],used[],vis[];

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void _add(int u,int v){

     _a[++_tot].v=v;

     _a[_tot].next=_head[u];

     _head[u]=_tot;

 }

 void bfs(int s){

     queue<int>q;

     q.push(s);

     used[s]=true;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for(int tmp=_head[u];tmp!=-;tmp=_a[tmp].next){

             int v=_a[tmp].v;

             if(!used[v]){

                 used[v]=true;

                 q.push(v);

             }

         }

     }

 }

 void spfa(int s){

     memset(isin,,sizeof(isin));

     memset(sp,0x3f,sizeof(sp));

     queue<int>q;

     q.push(s);

     isin[s]=true;

     sp[s]=;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         isin[u]=false;

         for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

             int v=a[tmp].v;

             if(vis[v]&&sp[v]>sp[u]+){

                 sp[v]=sp[u]+;

                 if(!isin[v]){

                     isin[v]=true;

                     q.push(v);

                 }

             }

         }

     }

 }

 int main(){

     memset(used,,sizeof(used));

     memset(head,-,sizeof(head));

     memset(_head,-,sizeof(_head));

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

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

         scanf("%d%d",&u,&v);

         if(u==v)continue;

         add(u,v);

         _add(v,u);

     }

     scanf("%d%d",&vs,&vt);

     bfs(vt);

     if(!used[vs])return printf("-1"),;

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

         vis[i]=true;

         for(int tmp=head[i];tmp!=-;tmp=a[tmp].next){

             int v=a[tmp].v;

             vis[i]&=used[v];

         }

     }

     spfa(vs);

     printf("%d",sp[vt]);

     return ;

 }

D2T3 解方程

题面

无力吐槽了……一道跟D1T1一样水的题放在D2T3是想考我们读题能力吗……还是考字符串转化成数字的处理？？

枚举解，把所有系数膜一个大质数即可；

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 #define mod 998244353

 using namespace std;

 typedef long long ll;

 int rd(){

     int x=,f=;

     char ch;

     do{

         ch=getchar();

         if(ch=='-')f=-;

     }while(!isdigit(ch));

     do{

         x=((ll)x*+ch-'')%mod;

         ch=getchar();

     }while(isdigit(ch));

     if(f==-)x=mod-x;

     return x;

 }

 int n,m,ans=,anss[],num[];

 void work(int x){

     ll nw=,ret=;

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

         ret=(ret+(ll)nw*num[i]%mod+mod)%mod;

         nw=(nw*x)%mod;

     }

     if(ret==)anss[++ans]=x;

 }

 int main(){

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

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

         num[i]=rd();

     }

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

         work(i);

     }

     printf("%d\n",ans);

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

         printf("%d\n",anss[i]);

     }

     return ;

 }

总结：

早就听说很水，没想到这么水……晚上无聊写写一个半小时不到写完了……“当你走进提高组考场考了六道普及组题目是怎样一种体验”

巴特西

[NOIP补坑计划]NOIP2014 题解&做题心得

题解：