【NOIP模拟赛】总结

时间:2022-04-06 16:35:54

题目描述

【NOIP模拟赛】总结

输入

第一行是5个正整数,n,m,k,S,T,分别代表无向图点数,边数,蝙蝠的数量,二小姐所在起点的编号,目标点的编号。
第二行是k个正整数,分别代表大小姐每个蝙蝠所在的起点的编号。接下来有m行,每行有4个正整数,u,v,q,p,分别是该边的起点、终点,蝙蝠通过该
路花费的代价,二小姐通过该路花费的代价。

输出

一行,一个整数,所有人物达到终点所需要的代价的和的最小值。

样例输入

5 5 2 3 4 1 5 1 2 3 5 3 2 3 5 2 4 4 9 3 4 9 6 5 4 1 1

样例输出

13

提示

1号蝙蝠从1到2,花费3

二小姐从3到2,花费5,遇见蝙蝠,之后不计算费用1号蝙蝠从2到4,花费4

2号蝙蝠从5到4,花费1

总计13
 
其中30%:n<=200。另有20%:保证S=T。

另有20%:保证k<=5,n<=1000,m<=10000。100%:n<=10000,m<=100000,k<=10000,1<=S、T、u、v<=n,1<=p、q<=1000,不保证

蝙蝠起点互不相等,数据中可能有重边和自环,保证所有点均能走到T点(即不存在无解情况)。
 
题解:
很容易想到枚举每一个个点作为蝙蝠和二小姐的交点
但是时间内存不允许,于是我们优化,我们可以虚拟一个S' S'到每一个蝙蝠的起点有一条,长度为 -dist ki-T
然后答案就是sum(F[ki][T])+min(F[s'][i]+F[S][i]+F[i][T])
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=10005,M=100005,INF=1999999999,MOD=100050;
 7 int head[N],num=0;
 8 struct Lin{
 9     int next,to,dis[2];
10 }a[M<<1];
11 void init(int x,int y,int z1,int z2){
12     a[++num].next=head[x];a[num].to=y;a[num].dis[0]=z1;a[num].dis[1]=z2;head[x]=num;
13     if(!x)return ;a[++num].next=head[y];a[num].to=x;a[num].dis[0]=z1;a[num].dis[1]=z2;head[y]=num;
14 }
15 int gi(){
16     int str=0;char ch=getchar();
17     while(ch>'9' || ch<'0')ch=getchar();
18     while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar();
19     return str;
20 }
21 int n,m,k,S,T;int f[5][N],q[N*10],s[N];bool vis[N];
22 void spfa(int sta,bool tt)
23 {
24     for(int i=1;i<=n;i++)vis[i]=false,f[sta][i]=INF;
25     int t=0,sum=1,x,u;
26     int from=0;
27     if(sta==1)from=S;if(sta==2)from=T;if(sta==3)from=0;
28     q[1]=from;vis[from]=true;f[sta][from]=0;
29     while(t!=sum)
30     {
31         t++;t%=MOD;
32         x=q[t];
33         for(int i=head[x];i;i=a[i].next)
34         {
35             u=a[i].to;
36             if(a[i].dis[tt]+f[sta][x]<f[sta][u])
37             { 
38                 f[sta][u]=f[sta][x]+a[i].dis[tt];
39                 if(!vis[u])vis[u]=true,sum++,sum%=MOD,q[sum]=u;
40             }
41         }
42         vis[x]=false;
43     }
44 }
45 int main()
46 {
47     n=gi();m=gi();k=gi();S=gi();T=gi();
48     for(int i=1;i<=k;i++)s[i]=gi();
49     int x,y,z1,z2;
50     for(int i=1;i<=m;i++)
51     {
52         x=gi();y=gi();z1=gi();z2=gi();
53         if(x==y)continue;
54         init(x,y,z1,z2);
55     }
56     spfa(1,1);spfa(2,0);
57     long long sum=0;
58     for(int i=1;i<=k;i++)init(0,s[i],-f[2][s[i]],0),sum+=f[2][s[i]];
59     spfa(3,0);
60     long long ans=INF,tmp;
61     long long pp=0;
62     for(int i=1;i<=n;i++)
63     {
64         tmp=f[1][i]+f[3][i]+f[2][i];
65         if(tmp<ans)ans=tmp,pp=i;
66     }
67     printf("%lld",ans+sum);
68     return 0;
69 }

 

题目描述

【NOIP模拟赛】总结

 

输入

第一行是一个正整数n,表示上式中的p的个数。
 

 

接下来有n行,每一行两个正整数 p i  e i  

 

输出

【NOIP模拟赛】总结

 

样例输入

2 2 2 3 2

样例输出

2 2 3 1

提示

 

样例解释

N=2*2*3*3=36

phi(N)=36*(1-1/2)*(1-1/3)=12 12=2*2*3

样例输入二

4

37 1

3 4

37 1

333667 2

样例输出二

2 4

3 8

37 2

167 1 333667 1


【NOIP模拟赛】总结

 题解:

水的数论,分解每一个pi-1即可

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const int N=500002,M=1000000,T=1000055;
 9 int gi(){
10     int str=0;char ch=getchar();
11     while(ch>'9' || ch<'0')ch=getchar();
12     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
13     return str;
14 }
15 bool d[M];int mark[T];bool cf[T];
16 ll qm(ll x,int k)
17 {
18     if(x==0)return 0;
19     if(k==0)return 1;
20     ll sum=1;
21     while(k)
22     {
23         if(k&1)sum*=x;
24         k>>=1;x*=x;
25     }
26     return sum;
27 }
28 int a[T],num=0;int z[N],t=0;
29 void qd(int p)
30 {
31     int lim;int c;
32     num=0;
33     for(int i=1;i<=t;i++){if(p%z[i]==0)a[++num]=z[i];}
34     for(int i=1;i<=num;i++)
35     {
36         int k=0,tmp=p;
37         while(tmp)
38         {
39             if(tmp%a[i])break;
40             k++;tmp/=a[i];
41         }
42         mark[a[i]]+=k;
43     }
44 }
45 int main()
46 {
47     //freopen("pp.in","r",stdin);
48     int n,x,y;
49     scanf("%d",&n);
50     memset(mark,0,sizeof(mark));
51     for(int i=1;i<=n;i++)
52     {
53         x=gi();y=gi();
54         mark[x]+=y;
55         cf[x]=true;
56     }
57     int m=1e6;
58     d[2]=false;
59     for(int i=2;i<=m;i++)
60     {
61         if(d[i])continue;
62         z[++t]=i;
63         for(int j=2*i;j<=m;j+=i)d[j]=true;
64     }
65     int to=1e6;
66     for(int i=1;i<=to;i++)
67     {
68         if(cf[i])
69         qd(i-1),mark[i]--;
70     }
71     for(int i=1;i<=to;i++)
72     {
73         if(mark[i])printf("%d %d\n",i,mark[i]);
74     }
75     return 0;
76 }

 

题目描述

【NOIP模拟赛】总结

 

输入

第一行一个正整数n,代表积木的个数。 接下来有n行,每行两个数li,ri,分别代表第i块积木左端点和右端点。

 

输出

输出一行两个整数,用一个空格隔开,分别代表最底层最多有多少积木和积木最少有多 少层。

 

样例输入

6 1 2 2 3 4 5 5 6 1 4 3 6

样例输出

4 2

提示

 


第 1、2、3、4 块放在最底层,第 5 块第二层,第 6块第三层。此时底层共 4块积木。


第 1、2、6块放在最底层,第 3、4、5块第二层。此时高度为 2。


【NOIP模拟赛】总结

30%:n<=10,0<=l,r<=20

另 20%: n<=100,0<=l<=50,r=l+2,即每块积木长均为 2

100%:n<=100000,-2*10^8<=l,r<=2*10^8

题解:

贪心,第一问线段覆盖,按右端点排序,然后以此判断 l>=last 满足就加入

第二问将每一条线段拆成两个点 再将每个点排序,线性扫描一边,遇l h++遇r h-- 意为能塞入底层就塞入

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=100005;
 7 int gi(){
 8     int str=0,f=1;char ch=getchar();
 9     while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar();
11     return str*f;
12 }
13 struct Point{
14     int l,r;
15 }a[N];
16 bool comp(const Point &p,const Point &q){return p.r<q.r;}
17 struct Pointed{
18     int x;bool t;
19 }p[N<<1];
20 bool cmp(const Pointed &p,const Pointed &q){if(p.x!=q.x)return p.x<q.x;return p.t>q.t;}
21 int main()
22 {
23     int n=gi();
24     for(int i=1;i<=n;i++)
25     {
26         a[i].l=gi();a[i].r=gi();
27         p[(i<<1)-1].x=a[i].l;p[(i<<1)-1].t=0;
28         p[i<<1].x=a[i].r;p[i<<1].t=1;
29     }
30     sort(a+1,a+n+1,comp);
31     int from=-2e9,ans1=0;
32     for(int i=1;i<=n;i++)
33     {
34         if(a[i].l>=from)
35         {
36             ans1++;
37             from=a[i].r;
38         }
39     }
40     printf("%d ",ans1);
41     sort(p+1,p+(n<<1)+1,cmp);
42     int top=0,ans2=0,ppap=(n<<1);
43     for(int i=1;i<=ppap;i++)
44     {
45         if(!p[i].t)top++;
46         else top--;
47         if(top>ans2)ans2=top;
48     }
49     printf("%d",ans2);
50     return 0;
51 }

 

 

题目描述

【NOIP模拟赛】总结 

擦弹(graze)

输入

第一行是1个正整数n,代表道路长度。
接下来有4n-4行,每行n个整数,第i行第j个数代表在i时刻(开始为0时刻)在第j格内受到的伤害。

输出

两个整数,用空格隔开,分别代表最小的miss数,和在miss数最小的情况下最大的graze 数。

样例输入

2 1 2 2 2 3 2 4 2

样例输出

30 10

提示

只有一种走法。

第一回合:第一格3分身,第二格1分身,miss5,graze1。

第二回合:第一格2分身,第二格2分身,miss8,graze2。

第三回合:第一格1分身,第二格3分身,miss9,graze3。

第四回合:第一格0分身,第二格4分身,miss8,graze4。


其中30%数据:n<=3其中50%数据:n<=10其中70%数据:n<=30

100%数据:n<=100,每时刻每格中弹幕数均为正数且小于  1000

 

题解:
简单的高维dp 注意高维常数 F[i][j][k][g]表示i时刻,第一个分身走的步数为j,第二个为k,第三个为g,第四个为l-i-j-k的最小miss值
然后以miss为最高优先级,每一次miss更新 graze就更新,miss相等则取较大者
第一维明显可以滚动掉 注意边界条件
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int N=105,M=455;
 8 int F[2][N][N][N],p[2][N][N][N];int a[N];
 9 int gi(){
10     int str=0;char ch=getchar();
11     while(ch>'9' || ch<'0')ch=getchar();
12     while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar();
13     return str;
14 }
15 int main()
16 {
17     int n;
18     scanf("%d",&n);
19     int m=4*n-4;
20     int tmp=0,l=0,pc=0;
21     memset(F,127/3,sizeof(F));
22     F[0][0][0][0]=0;
23     int c=0,cc=1;
24     for(int i=1;i<=m;i++)
25     {
26         for(int j=1;j<=n;j++)
27         {
28             a[j]=gi();
29         }
30         for(int j=0;j<n;j++)
31         {
32             if(j>i)break;
33             for(int k=j;k<n;k++)
34             {
35                 if(k+j>i)break;
36                 pc=k>i-j-k-n?k:i-j-k-n;
37                 for(int g=pc;g<n;g++)
38                 {
39                     if(g+j+k>i)break;
40                     l=i-j-k-g;
41                     if(l<g-33)break;
42                     int *pp=&F[cc][j][k][g];
43                     int *qq=&p[cc][j][k][g];
44                     *pp=2e8;
45                     *qq=0;
46                     tmp=a[j+1]+a[k+1]+a[g+1]+a[l+1];
47                     if(tmp+F[c][j-1][k][g]<=*pp&& j)
48                     {
49                         int t=F[c][j-1][k][g];
50                         if(tmp+t<*pp)
51                         *qq=p[c][j-1][k][g]+a[j];
52                         else if(p[c][j-1][k][g]+a[j]>*qq)*qq=p[c][j-1][k][g]+a[j];
53                         *pp=tmp+t;
54                     }
55                     if(tmp+F[c][j][k-1][g]<=*pp&& k)
56                     {
57                         int t=F[c][j][k-1][g];
58                         if(tmp+t<*pp)
59                         *qq=p[c][j][k-1][g]+a[k];
60                         else if(p[c][j][k-1][g]+a[k]>*qq)*qq=p[c][j][k-1][g]+a[k];
61                         *pp=tmp+t;
62                     }
63                     if(tmp+F[c][j][k][g-1]<=*pp&& g)
64                     {
65                        int t=F[c][j][k][g-1];
66                         if(tmp+t<*pp)
67                         *qq=p[c][j][k][g-1]+a[g];
68                         else if(p[c][j][k][g-1]+a[j]>*qq)*qq=p[c][j][k][g-1]+a[g];
69                         *pp=tmp+t;
70                     }
71                     if(tmp+F[c][j][k][g]<=*pp)
72                     {
73                         int t=F[c][j][k][g];
74                         if(tmp+t<*pp)
75                         *qq=p[c][j][k][g]+a[l];
76                         else if(p[c][j][k][g]+a[l]>*qq)*qq=p[c][j][k][g]+a[l];
77                         *pp=tmp+t;
78                     }
79                 }
80             }
81         }
82         c^=1;cc^=1;
83     }
84     cout<<F[c][n-1][n-1][n-1]<<" "<<p[c][n-1][n-1][n-1];
85     return 0;
86 }