NOIP模拟赛-2018.11.6

74 阅读 0 评论 49 点赞

我是靠谱客的博主优秀方盒，最近开发中收集的这篇文章主要介绍NOIP模拟赛-2018.11.6，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

NOIP模拟赛

　　今天想着反正高一高二都要考试，那么干脆跟着高二考吧，因为高二的比赛更有技术含量(我自己带的键盘放在这里).

　　今天考了一套英文题?发现阅读理解还是有一些困难的.

　　T1:有$n$个点,$m$天,第$[1,m]$天每天会把最大公约数是$m-i+1$的数连边,给出$q$组询问,询问给出的两点最早被连接起来是什么时候.$n,m,q<=10^5$

　　一开始以为是一道求$gcd$的签到题...后来发现还可以这样:$3->6,6->8$，所以不用等到最后一天$3,8$就连通了.

　　首先可以想到枚举每一天,把$gcd$为这个数的数对两两连边合并并查集,但是查询的时候就不知道是哪天连起来的了,所以可以用$Kruscal$重构树,每次合并时加一个新的点来中转.但是枚举数对的复杂度非常高,有一种思路是枚举质数对并乘上$gcd$,可是打表发现这个范围内的质数有点多...

　　这时可以发现一个很奇妙的性质:如果两个数同时是$d$的倍数,那么它们被连接起来不会晚于$d$的出现时间,为什么?依旧采取最大公约数的表示形式:

　　$$a=xd,b=yd,(x,y)不保证互质$$ $$a=xd,b=yd$$ $$a=x_1qd,b=y_1qd quad (x_1,y_1)=1$$ $$(x_1d,y_1d)=d$$ $$(a,x_1d)=x_1d,(b,y_1d)=y_1d$$ $$minleft { d,x_1d,x_2dright }=d$$

　　既然$d$的倍数都会被连起来,我们又是每次建立新点来连接,就可以直接把所有倍数都连接到新点上,不用枚举数对了.

　　树建好之后每次询问在树上倍增找$LCA$即可.


1 # include <cstdio>

2 # include <iostream>

3 # include <cstring>

4 # include <string>

5 # include <algorithm>

6 # include <cmath>

7 # define R register int

8 # define ll long long

9
 10 using namespace std;
 11
 12 const int maxn=200005;
 13 int x,n,m,q,h,firs[maxn],f[maxn][21];
 14 int dep[maxn],v[maxn],nod,F[maxn];
 15 struct edge
 16 {
 17
int too,nex;
 18 }g[maxn*2+5];
 19
 20 int read ()
 21 {
 22
int x=0,f=1;
 23
char c=getchar();
 24
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
 25
while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
 26
return x*f;
 27 }
 28
 29 void add (int x,int y)
 30 {
 31
g[++h].nex=firs[x];
 32
g[h].too=y;
 33
firs[x]=h;
 34 }
 35
 36 int father (int x)
 37 {
 38
if(x!=F[x]) return F[x]=father(F[x]);
 39
return x;
 40 }
 41
 42 void dfs (int x)
 43 {
 44
int j;
 45
for (R i=firs[x];i;i=g[i].nex)
 46 
{
 47
j=g[i].too;
 48
if(dep[j]) continue;
 49
f[j][0]=x;
 50
dep[j]=dep[x]+1;
 51
for (R k=1;k<=20;++k)
 52
f[j][k]=f[ f[j][k-1] ][k-1];
 53 
dfs(j);
 54 
}
 55 }
 56
 57 int lca (int x,int y)
 58 {
 59
if(dep[x]>dep[y]) swap(x,y);
 60
for (R i=20;i>=0;--i)
 61
if(dep[y]-(1<<i)>=dep[x]) y=f[y][i];
 62
if(x==y) return x;
 63
for (R i=20;i>=0;--i)
 64 
{
 65
if(f[x][i]==f[y][i]) continue;
 66
x=f[x][i];
 67
y=f[y][i];
 68 
}
 69
return f[x][0];
 70 }
 71
 72 int main()
 73 {
 74
scanf("%d%d%d",&n,&m,&q);
 75
for (R i=1;i<=n;++i)
 76
F[i]=i;
 77
nod=n;
 78
for (R i=m;i>=1;--i)
 79 
{
 80
nod++;
 81
F[nod]=nod;
 82
v[nod]=m-i+1;
 83
for (R j=1;j*i<=n;++j)
 84 
{
 85
x=father(i*j);
 86
if(x==nod) continue;
 87 
add(nod,x);
 88 
add(x,nod);
 89
F[x]=nod;
 90 
}
 91 
}
 92
dep[nod]=1;
 93 
dfs(nod);
 94
for (R i=1;i<=q;++i)
 95 
{
 96
int x,y;
 97
x=read(),y=read();
 98
printf("%dn",v[ lca(x,y) ]);
 99 
}
100 
fclose(stdin);
101 
fclose(stdout);
102
return 0;
103 }

pictionary

　　T2:有$n$座楼,每座有一个高度和金币数,可以从任意楼开始跳,每次只能跳到右边不低于当前楼高的楼上,可以在任意楼停下,问获得的总金币数大于等于$k$的方案数.$n<=40$

　　考场写了搜索,还有一种奇怪的用$map$做$dp$的做法,正解是折半搜索,分别找到前后两部分的答案数,然后记录前半部分以高度$i$结尾,收益是$j$的方案数以及后半部分以高度$i$开始,收益是$j$的方案数,排序后对于前者找到后者的匹配区间,好像很快啊.

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # include <algorithm>
 6 # include <cmath>
 7 # include <vector>
 8 # include <map>
 9 # define R register int
10 # define ll long long
11
12 using namespace std;
13
14 const int maxn=41;
15 int n;
16 ll ans,k,h[maxn],g[maxn],f[maxn];
17 vector <ll> v[maxn];
18 map <ll,int> m[maxn];
19
20 int read ()
21 {
22
int x=0,f=1;
23
char c=getchar();
24
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
25
while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
26
return x*f;
27 }
28
29 int main()
30 {
31
freopen("san.in","r",stdin);
32
freopen("san.out","w",stdout);
33
34
scanf("%d%lld",&n,&k);
35
for (R i=1;i<=n;++i)
36
scanf("%lld%lld",&h[i],&g[i]);
37
for (R i=1;i<=n;++i)
38 
{
39
if(m[i][ g[i] ]==0)
40 
v[i].push_back(g[i]);
41
m[i][ g[i] ]++;
42
for (R j=i+1;j<=n;++j)
43 
{
44
if(h[j]<h[i]) continue;
45
int s=v[i].size();
46
for (R k=0;k<s;++k)
47 
{
48
ll x=v[i][k]+g[j];
49
if(m[j][x]==0)
50 
v[j].push_back(x);
51
m[j][x]+=m[i][ v[i][k] ];
52 
}
53 
}
54 
}
55
for (R i=1;i<=n;++i)
56 
{
57
int siz=v[i].size();
58
for (R j=0;j<siz;++j)
59
if(v[i][j]>=k) ans+=m[i][ v[i][j] ];
60 
}
61
printf("%lld",ans);
62 
fclose(stdin);
63 
fclose(stdout);
64
return 0;
65 }
66
67 /*
68 4 6
69 2 1
70 6 3
71 7 2
72 5 6
73
74 */

san-40

　　T3:https://www.luogu.org/problemnew/show/P4441

　　$Cena$不能编译$string$类型...?直接全$T$了...

　　可以尝试带着$string$一起$dp$,保存目前在哪个点,有多少个未匹配的左括号的最长长度,$string$中保存这个答案,显然这样是比较慢的...在洛谷上也没过。题解是$dp$时只求长度,最终拿最长长度倒推回去找答案,听起来很有道理的样子.


1 # include <cstdio>

2 # include <iostream>

3 # include <cstring>

4 # include <string>

5 # include <algorithm>

6 # include <cmath>

7 # define R register int

8 # define ll long long

9
 10 using namespace std;
 11
 12 int read ()
 13 {
 14
int x=0,f=1;
 15
char c=getchar();
 16
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
 17
while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
 18
return x*f;
 19 }
 20
 21 const int dir[]={-1,0,1};
 22 int a[305][305],pos,x;
 23 int dp[2][305][305];
 24 string s[2][305][305],c;
 25 string ans;
 26 int len;
 27
 28 string tr (string a,string b)
 29 {
 30
if(a.length()>b.length()) return a;
 31
else if(a.length()<b.length()) return b;
 32
return min(a,b);
 33 }
 34
 35 int main()
 36 {
 37
int n,m;
 38
cin>>n>>m;
 39
for (R i=n;i>=1;--i)
 40 
{
 41
cin>>c;
 42
while(c.length()==0) cin>>c;
 43
c=' '+c;
 44
for (R j=1;j<=m;++j)
 45 
{
 46
if(c[j]=='.') a[i][j]=0;
 47
else if(c[j]=='(') a[i][j]=1;
 48
else if(c[j]==')') a[i][j]=-1;
 49
else if(c[j]=='*') a[i][j]=100;
 50
else pos=j;
 51 
}
 52 
}
 53
for (R i=0;i<=m+1;++i)
 54
a[n+1][i]=100;
 55
memset(dp[1],128,sizeof(dp[1]));
 56
dp[1][0][pos]=0;
 57
for (R i=2;i<=n+1;++i)
 58 
{
 59
int no=i&1;
 60
int las=no^1;
 61
memset(dp[no],128,sizeof(dp[no]));
 62
for (R j=1;j<=m;++j)
 63
for (R k=1;k<=m;++k)
 64
s[no][j][k]="";
 65
for (R j=0;j<=m;++j)
 66
for (R k=1;k<=m;++k)
 67 
{
 68
if(dp[las][j][k]<0) continue;
 69
for (R d=0;d<3;++d)
 70 
{
 71
x=k+dir[d];
 72
if(x<=0||x>m) continue;
 73
if(a[i][x]==100)
 74 
{
 75
if(j==0) ans=tr(ans,s[las][j][k]);
 76
continue;
 77 
}
 78
if(a[i][x]==0)
 79 
{
 80
if(dp[no][j][x]<dp[las][j][k])
 81 
{
 82
dp[no][j][x]=dp[las][j][k];
 83
s[no][j][x]=s[las][j][k];
 84 
}
 85
if(dp[no][j][x]==dp[las][j][k]) s[no][j][x]=tr(s[no][j][x],s[las][j][k]);
 86 
}
 87
if(a[i][x]==-1)
 88 
{
 89
if(j==0) continue;
 90
if(dp[no][j-1][x]<dp[las][j][k]+1)
 91 
{
 92
dp[no][j-1][x]=dp[las][j][k]+1;
 93
s[no][j-1][x]=s[las][j][k]+")";
 94 
}
 95
if(dp[no][j-1][x]==dp[las][j][k]+1) s[no][j-1][x]=tr(s[no][j-1][x],s[las][j][k]+")");
 96 
}
 97
if(a[i][x]==1)
 98 
{
 99
if(dp[no][j+1][x]<dp[las][j][k]+1)
100 
{
101
dp[no][j+1][x]=dp[las][j][k]+1;
102
s[no][j+1][x]=s[las][j][k]+"(";
103 
}
104
if(dp[no][j+1][x]==dp[las][j][k]+1) s[no][j+1][x]=tr(s[no][j+1][x],s[las][j][k]+"(");
105 
}
106 
}
107 
}
108 
}
109
cout<<ans.length()<<endl<<ans;
110
return 0;
111 }