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_2d ight }=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("%d
",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 }

Retro

---shzr