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$$ $$min\left \{ d,x_1d,x_2d\right \}=d$$
既然$d$的倍数都会被连起来,我们又是每次建立新点来连接,就可以直接把所有倍数都连接到新点上,不用枚举数对了.
树建好之后每次询问在树上倍增找$LCA$即可.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# include <algorithm>
# include <cmath>
# define R register int
# define ll long long using namespace std; const int maxn=;
int x,n,m,q,h,firs[maxn],f[maxn][];
int dep[maxn],v[maxn],nod,F[maxn];
struct edge
{
int too,nex;
}g[maxn*+]; int read ()
{
int x=,f=;
char c=getchar();
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
} void add (int x,int y)
{
g[++h].nex=firs[x];
g[h].too=y;
firs[x]=h;
} int father (int x)
{
if(x!=F[x]) return F[x]=father(F[x]);
return x;
} void dfs (int x)
{
int j;
for (R i=firs[x];i;i=g[i].nex)
{
j=g[i].too;
if(dep[j]) continue;
f[j][]=x;
dep[j]=dep[x]+;
for (R k=;k<=;++k)
f[j][k]=f[ f[j][k-] ][k-];
dfs(j);
}
} int lca (int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
for (R i=;i>=;--i)
if(dep[y]-(<<i)>=dep[x]) y=f[y][i];
if(x==y) return x;
for (R i=;i>=;--i)
{
if(f[x][i]==f[y][i]) continue;
x=f[x][i];
y=f[y][i];
}
return f[x][];
} int main()
{
scanf("%d%d%d",&n,&m,&q);
for (R i=;i<=n;++i)
F[i]=i;
nod=n;
for (R i=m;i>=;--i)
{
nod++;
F[nod]=nod;
v[nod]=m-i+;
for (R j=;j*i<=n;++j)
{
x=father(i*j);
if(x==nod) continue;
add(nod,x);
add(x,nod);
F[x]=nod;
}
}
dep[nod]=;
dfs(nod);
for (R i=;i<=q;++i)
{
int x,y;
x=read(),y=read();
printf("%d\n",v[ lca(x,y) ]);
}
fclose(stdin);
fclose(stdout);
return ;
}
pictionary
T2:有$n$座楼,每座有一个高度和金币数,可以从任意楼开始跳,每次只能跳到右边不低于当前楼高的楼上,可以在任意楼停下,问获得的总金币数大于等于$k$的方案数.$n<=40$
考场写了搜索,还有一种奇怪的用$map$做$dp$的做法,正解是折半搜索,分别找到前后两部分的答案数,然后记录前半部分以高度$i$结尾,收益是$j$的方案数以及后半部分以高度$i$开始,收益是$j$的方案数,排序后对于前者找到后者的匹配区间,好像很快啊.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# include <algorithm>
# include <cmath>
# include <vector>
# include <map>
# define R register int
# define ll long long using namespace std; const int maxn=;
int n;
ll ans,k,h[maxn],g[maxn],f[maxn];
vector <ll> v[maxn];
map <ll,int> m[maxn]; int read ()
{
int x=,f=;
char c=getchar();
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
} int main()
{
freopen("san.in","r",stdin);
freopen("san.out","w",stdout); scanf("%d%lld",&n,&k);
for (R i=;i<=n;++i)
scanf("%lld%lld",&h[i],&g[i]);
for (R i=;i<=n;++i)
{
if(m[i][ g[i] ]==)
v[i].push_back(g[i]);
m[i][ g[i] ]++;
for (R j=i+;j<=n;++j)
{
if(h[j]<h[i]) continue;
int s=v[i].size();
for (R k=;k<s;++k)
{
ll x=v[i][k]+g[j];
if(m[j][x]==)
v[j].push_back(x);
m[j][x]+=m[i][ v[i][k] ];
}
}
}
for (R i=;i<=n;++i)
{
int siz=v[i].size();
for (R j=;j<siz;++j)
if(v[i][j]>=k) ans+=m[i][ v[i][j] ];
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
} /*
4 6
2 1
6 3
7 2
5 6 */
san-40
T3:https://www.luogu.org/problemnew/show/P4441
$Cena$不能编译$string$类型...?直接全$T$了...
可以尝试带着$string$一起$dp$,保存目前在哪个点,有多少个未匹配的左括号的最长长度,$string$中保存这个答案,显然这样是比较慢的...在洛谷上也没过。题解是$dp$时只求长度,最终拿最长长度倒推回去找答案,听起来很有道理的样子.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# include <algorithm>
# include <cmath>
# define R register int
# define ll long long using namespace std; int read ()
{
int x=,f=;
char c=getchar();
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
} const int dir[]={-,,};
int a[][],pos,x;
int dp[][][];
string s[][][],c;
string ans;
int len; string tr (string a,string b)
{
if(a.length()>b.length()) return a;
else if(a.length()<b.length()) return b;
return min(a,b);
} int main()
{
int n,m;
cin>>n>>m;
for (R i=n;i>=;--i)
{
cin>>c;
while(c.length()==) cin>>c;
c=' '+c;
for (R j=;j<=m;++j)
{
if(c[j]=='.') a[i][j]=;
else if(c[j]=='(') a[i][j]=;
else if(c[j]==')') a[i][j]=-;
else if(c[j]=='*') a[i][j]=;
else pos=j;
}
}
for (R i=;i<=m+;++i)
a[n+][i]=;
memset(dp[],,sizeof(dp[]));
dp[][][pos]=;
for (R i=;i<=n+;++i)
{
int no=i&;
int las=no^;
memset(dp[no],,sizeof(dp[no]));
for (R j=;j<=m;++j)
for (R k=;k<=m;++k)
s[no][j][k]="";
for (R j=;j<=m;++j)
for (R k=;k<=m;++k)
{
if(dp[las][j][k]<) continue;
for (R d=;d<;++d)
{
x=k+dir[d];
if(x<=||x>m) continue;
if(a[i][x]==)
{
if(j==) ans=tr(ans,s[las][j][k]);
continue;
}
if(a[i][x]==)
{
if(dp[no][j][x]<dp[las][j][k])
{
dp[no][j][x]=dp[las][j][k];
s[no][j][x]=s[las][j][k];
}
if(dp[no][j][x]==dp[las][j][k]) s[no][j][x]=tr(s[no][j][x],s[las][j][k]);
}
if(a[i][x]==-)
{
if(j==) continue;
if(dp[no][j-][x]<dp[las][j][k]+)
{
dp[no][j-][x]=dp[las][j][k]+;
s[no][j-][x]=s[las][j][k]+")";
}
if(dp[no][j-][x]==dp[las][j][k]+) s[no][j-][x]=tr(s[no][j-][x],s[las][j][k]+")");
}
if(a[i][x]==)
{
if(dp[no][j+][x]<dp[las][j][k]+)
{
dp[no][j+][x]=dp[las][j][k]+;
s[no][j+][x]=s[las][j][k]+"(";
}
if(dp[no][j+][x]==dp[las][j][k]+) s[no][j+][x]=tr(s[no][j+][x],s[las][j][k]+"(");
}
}
}
}
cout<<ans.length()<<endl<<ans;
return ;
}
Retro
---shzr