您的位置: 首页  >  IT文章  >  $NOIP2014$ 题解报告

$NOIP2014$ 题解报告

分类: IT文章 • 2025-01-22 12:01:07

目录

$Luogu P1328$ 生活大爆炸版石头剪刀布$( √ )$

$Luogu P1351$ 联合权值$( √ )$

$Luogu P1941$ 飞扬的小鸟$( √ )$

$Luogu P2038$ 无线网络发射器选址$( √ )$

$Luogu P2296$ 寻找道路$( √ )$

$Luogu P2312$ 解方程$( √ )$

$Luogu P1328$ 生活大爆炸版石头剪刀布

题目传送门

模拟大水题

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define g() getchar()
 7 #define rg register
 8 #define go(i,a,b) for(rg int i=a;i<=b;i++)
 9 #define back(i,a,b) for(rg int i=a;i>=b;i--)
10 #define db double
11 #define ll long long
12 #define il inline
13 #define pf printf
14 using namespace std;
15 int fr(){
16     int w=0,q=1;
17     char ch=g();
18     while(ch<'0'||ch>'9'){
19         if(ch=='-') q=-1;
20         ch=g();
21     }
22     while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g();
23     return w*q;
24 }
25 const int N=1e4+2;
26 int n1,n2,a[N],b[N];
27 ll n,ans1,ans2,s1,s2;
28 int main(){
29     //freopen("","r",stdin);
30     //freopen("","w",stdout);
31     scanf("%lld%d%d",&n,&n1,&n2);
32     go(i,1,n1) a[i]=fr();a[0]=a[n1];
33     go(i,1,n2) b[i]=fr();b[0]=b[n2];
34     rg int n3=n1*n2,x=n%n3;
35     rg ll y=n/n3;
36     go(i,1,n3){
37         rg int A=a[i%n1],B=b[i%n2];
38         if(A==0){
39             if(B==1||B==4) ans2++;
40             if(B==2||B==3) ans1++;
41         }
42         if(A==1){
43             if(B==2||B==4) ans2++;
44             if(B==0||B==3) ans1++;
45         }
46         if(A==2){
47             if(B==0||B==3) ans2++;
48             if(B==1||B==4) ans1++;
49         }
50         if(A==3){
51             if(B==0||B==1) ans2++;
52             if(B==2||B==4) ans1++;
53         }
54         if(A==4){
55             if(B==2||B==3) ans2++;
56             if(B==0||B==1) ans1++;
57         }
58         if(i==x) s1=ans1,s2=ans2;
59     }
60     ans1=ans1*y+s1;ans2=ans2*y+s2;
61     pf("%lld %lld
",ans1,ans2);
62     return 0;
63 }
代码戳这里

$Luogu P1351$ 联合权值

题目传送门

与每个点组合会对答案造成贡献的显然是当前节点的祖父、兄弟和孙子。根据乘法分配律，我们利用每个点的儿子的权值之和求出当前节点与其兄弟对答案的贡献。每一组祖父和孙子的贡献可以在深度较大的点处$*2$算出。要求最大值，主要难点在兄弟之间，这里可以贪心找每个节点的儿子中最大的两个

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 #define E(i,x) for(ri i=hd[x];i;i=e[i].nxt)
12 #define t(i) e[i].to
13 using namespace std;
14 il int fr(){
15     ri w=0,q=1;char ch=g();
16     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
17     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
18     return w*q;
19 }
20 const int mod=10007;
21 const int N=200002;
22 int n,w[N],hd[N],ed,son[N],f[N],ans,mx;
23 struct edge{
24     int nxt,to;
25 }e[N<<1];
26 il void build(ri x,ri y){e[++ed]=(edge){hd[x],y};hd[x]=ed;return;}
27 il void Tree(ri x,ri fa){
28     f[x]=fa;ri mx1=0,mx2=0;
29     E(i,x){
30         if(t(i)==fa)continue;
31         Tree(t(i),x);son[x]+=w[t(i)];
32         if(son[x]>=mod)son[x]-=mod;
33         if(w[t(i)]>=mx1)mx2=mx1,mx1=w[t(i)];
34         else if(w[t(i)]>mx2)mx2=w[t(i)];
35     }
36     mx=max(mx,mx1*mx2);
37     return;
38 }
39 int main(){
40     //freopen(".in","r",stdin);
41     //freopen(".out","w",stdout);
42     n=fr();
43     go(i,1,n-1){
44         ri x=fr(),y=fr();
45         build(x,y);build(y,x);
46     }
47     go(i,1,n)w[i]=fr();
48     Tree(1,0);
49     go(i,1,n){
50         if(f[f[i]])ans=(ans+2*(w[i]*w[f[f[i]]]%mod)%mod)%mod,mx=max(mx,w[i]*w[f[f[i]]]);
51         if(f[i])ans=(ans+w[i]*(son[f[i]]-w[i])%mod)%mod;
52     }
53     pf("%d %d
",mx,ans);
54     return 0;
55 }
代码戳这里

$Luogu P1941$ 飞扬的小鸟

题目传送门

今日玄学，重构代码即可$AC$

$DP$，设$f[i][j]$表示横坐标为$i$，纵坐标为$j$时的最小点击次数。把点击上升当作完全背包来做，下降当作$0/1$背包来做

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 const int N=10002,M=1002;
19 int n,m,k,vis[N],x[N],y[N];
20 int f[N][M<<1],ans;
21 struct pipe{
22     int pos,l,h;
23 }p[N];
24 int main(){
25     //freopen(".in","r",stdin);
26     //freopen(".out","w",stdout);
27     n=fr();m=fr();k=fr();
28     go(i,1,n)x[i]=fr(),y[i]=fr();
29     go(i,1,k){
30         p[i]=(pipe){fr(),fr(),fr()};
31         vis[p[i].pos]=i;
32     }
33     mem(f,0x3f);go(i,1,m)f[0][i]=0;
34     go(i,1,n){
35         go(j,1,m+x[i])f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
36         go(j,m+1,m+x[i])f[i][m]=min(f[i][m],f[i][j]);
37         go(j,1,m-y[i])f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
38         if(vis[i]){
39             go(j,1,p[vis[i]].l)f[i][j]=f[0][0];
40             go(j,p[vis[i]].h,m)f[i][j]=f[0][0];
41         }
42     }
43     ans=f[0][0];
44     go(j,1,m)ans=min(ans,f[n][j]);
45     if(ans<f[0][0]){puts("1");pf("%d
",ans);return 0;}
46     ri i,j;ans=0;
47     for(i=n;i>=1;i--){
48         for(j=1;j<=m;j++)if(f[i][j]<f[0][0])break;
49         if(j<=m)break;
50     }
51     go(k,1,i)if(vis[k])ans++;
52     puts("0");pf("%d
",ans);
53     return 0;
54 }
55 /*
56   f[i][j]表示位置i高度为j的最小点击次数
57 */
代码戳这里

$Luogu P2038$ 无线网络发射器选址

题目传送门

暴力枚举即正解

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 const int N=130;
19 int d,n,num[N][N],s[N][N],sum[N][N],ans,mx;
20 int main(){
21     //freopen(".in","r",stdin);
22     //freopen(".out","w",stdout);
23     d=fr();n=fr();
24     go(i,1,n)num[fr()][fr()]=fr();
25     /*s[0][0]=num[0][0];go(i,0,128)s[0][i]=num[0][i],s[i][0]=num[i][0];
26     go(i,1,128)go(j,1,128)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+num[i][j];
27     go(i,0,128)go(j,0,128){
28         ri x1=max(0,i-d),y1=max(0,j-d),x2=min(128,i+d),y2=min(128,j+d);
29         ri as=s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1];
30         if(as>mx)mx=as,ans=1;
31         else if(as==mx)ans++;
32     }*/
33     go(i,0,128)go(j,0,128){
34         ri as=0;
35         go(x,max(0,i-d),min(128,i+d))go(y,max(0,j-d),min(128,j+d))
36             as+=num[x][y];
37         if(as>mx)ans=1,mx=as;
38         else if(as==mx)ans++;
39     }
40     pf("%d %d
",ans,mx);
41     return 0;
42 }
代码戳这里

$Luogu P2296$ 寻找道路

题目传送门

$bfs+dijkstra$

建反图，$bfs$求出与终点相连的所有点，然后枚举每个点，如果某个点不与终点相连但是它的出边所指的某个点与终点相连，那么这个出边所指的点也是不合法的。因为题目要求路径上的所有点的出边所指的点都能到达终点。

然后在保证路径上的点合法的情况下跑$dijkstra$求单源最短路

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 #define P pair<int,int>
12 #define mp make_pair
13 #define E(i,x) for(ri i=hd[x];i;i=e[i].nxt)
14 #define t(i) e[i].to
15 using namespace std;
16 il int fr(){
17     ri w=0,q=1;char ch=g();
18     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
19     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
20     return w*q;
21 }
22 const int N=10002;
23 const int M=200002;
24 int n,m,ed,hd[N],s,t,dis[N];
25 bool vis1[N],vis2[N],v[N];
26 priority_queue<P> q;
27 queue<int> Q;
28 struct edge{
29     int nxt,to;
30 }e[M];
31 il void build(ri x,ri y){e[++ed]=(edge){hd[y],x};hd[y]=ed;return;}
32 int main(){
33     freopen("2296.in","r",stdin);
34     freopen("2296.out","w",stdout);
35     n=fr();m=fr();
36     go(i,1,m){
37         ri x=fr(),y=fr();
38         if(x==y)continue;
39         build(x,y);
40     }
41     s=fr();t=fr();Q.push(t);
42     while(!Q.empty()){
43         ri p=Q.front();Q.pop();
44         if(vis1[p])continue;vis1[p]=1;
45         E(i,p)Q.push(t(i));
46     }
47     if(!vis1[s]){puts("-1");return 0;}
48     go(i,1,n)vis2[i]=vis1[i];
49     go(i,1,n){
50         if(vis1[i])continue;
51         E(j,i)if(vis2[t(j)])vis2[t(j)]=0;
52     }
53     if(!vis2[s]){puts("-1");return 0;}
54     mem(dis,0x3f);//mem(vis,0);
55     dis[t]=0;q.push(mp(0,t));
56     while(!q.empty()){
57         ri p=q.top().second;q.pop();
58         if(v[p])continue;v[p]=1;
59         E(i,p){
60             if(!vis2[t(i)])continue;
61             dis[t(i)]=min(dis[t(i)],dis[p]+1);
62             q.push(mp(-dis[t(i)],t(i)));
63         }
64     }
65     pf("%d
",dis[s]);
66     return 0;
67 }
代码戳这里

$Luogu P2312$ 解方程

题目传送门

数学课上讲过的秦九韶算法$QAQ$

暴力枚举可能的解，然后$check$一下

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 const int mod=1e9+7;
13 il ll fr(){
14     rl w=0,q=1;char ch=g();
15     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
16     while(ch>='0'&&ch<='9')w=(w*10%mod+ch-'0')%mod,ch=g();
17     return w*q;
18 }
19 const int N=102;
20 const int M=1e6+2;
21 ll n,m,a[N],ans[M],num;
22 il bool check(ri x){
23     //cout<<"x="<<x<<endl;
24     rl as=a[n];
25     back(i,n-1,0)as=(as*x%mod+a[i]+mod)%mod;
26     //cout<<"as="<<as<<endl;
27     return as==0;
28 }
29 int main(){
30     //freopen(".in","r",stdin);
31     //freopen(".out","w",stdout);
32     n=fr();m=fr();
33     go(i,0,n)a[i]=fr();
34     go(i,1,m)if(check(i))ans[++num]=i;
35     pf("%lld
",num);
36     go(i,1,num)pf("%lld
",ans[i]);
37     return 0;
38 }
代码戳这里

相关推荐