考试过程：开考后读3个题，觉得T1可做，就回来想T1，结果不到5分钟整个机房的人都开始打题了，我还是没有什么思路，我当时慌zhan了，但是我及时调整了心态，又换了几种思路想了想，最后想到一种\(o(nk)\)的做法，理论可以获得57分，然后，就去实现了，但是因为思路不够严谨，有个边界条件没有想到，导致挂分了。剩下的题就是打了个暴搜，没什么思路。总结一下收获就是考试时不要受外界环境影响，及时调整心态，题还是可以做出来的，做题时注意边界条件。
T1 Reverse
思路：我在考场上打的一个bfs，以每个点为起点向外扩展。但是正解和我的思路不太一样，先说一个性质：若以一个点为起点，设移动一次到达的点为点p，那么还可以到达的点为 p+2 的，这个手模一下，所以我们初始化钦定net[i]=i+2,表示相邻的可以到达的点，在我们更新过一边后将已经遍历过的点的net数组进行更改，就可以做到\(o(n)\)的复杂度，代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"YES"<<endl
using namespace std;
const int N=1e5+10;
const int INF=1e9+10;
int n,k,m,s,tot,t2;
int a[N],q[N],net[N];
ii read()
{
int x=0;
char ch=getchar();
bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
signed main()
{
int cnt=0;
n=read(),k=read(),m=read(),s=read();
for(re i=1;i<=n;i++) a[i]=INF,net[i]=i+2;
for(re i=1;i<=m;i++)
{
int x=read();
a[x]=-1;
}
a[s]=0;
q[++q[0]]=s;
int t1,l,r,p,now=1;
while(now<=q[0])
{
p=q[now],++now;
t1=max(1,p-k+1),l=t1+t1+k-1-p;
t1=min(n-k+1,p),r=t1+t1+k-1-p;
for(re i=l;i<=r;i=net[i]) if(a[i]>a[p]+1) a[i]=a[p]+1,q[++q[0]]=i;
for(re i=l;i<=r;)
{
int R=net[i];
net[i]=max(net[i],r);
i=R;
}
}
for(re i=1;i<=n;i++)
if(a[i]!=INF) printf("%d ",a[i]);
else printf("-1 ");
return 0;
}
T2 Silhouette
思路：
解释一下中间那个式子，首先是组合数，\(c^{a}_{i}\)表示在a行中选出i行不合法，\(s^i\)表有i个数有s种取值，那么\((s+1)^(a-i)\)表示有（a-i）个数有s+1种取值，最后要减去一个\(s^(a-i)\)为了保证有一行一定合法。那么我们在来考虑一般情况，式子为\(f[i]=C_a^i\times (S^i\times ((S+1)^{a+c-i}-S^{a+c-i}))^b\times (S^i\times (S+1)^{a-i})^d\),具体证明可以看这里，最后注意取模问题，代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"YES"<<endl
#define mod mo
using namespace std;
const int N=1e5+10;
const int mo=1e9+7;
int n,ma,mb,ans=1;
int A[N],B[N],s[N<<1];
int jc[N],inv[N];
ii read()
{
int x=0;
char ch=getchar();
bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii ksm(int d,int z)
{
int out=1;
while(z)
{
if(z&1) out=out*d%mo;
z>>=1;
d=d*d%mo;
}
return out;
}
ii suan(int n,int m)
{
return jc[n]%mo*inv[m]%mo*inv[n-m]%mo;
}
ii C(int n,int m)
{
if(m==0 or n==0) return 1;
return C(n/mo,m/mo)%mo*suan(n%mo,m%mo)%mo;
}
ii solve(int a,int b,int c,int d,int S)
{
int res=0,now;
for(re i=0;i<=a;i++)
{
now=C(a,i)%mo*ksm(ksm(S,i)%mo*((ksm(S+1,a+c-i)-ksm(S,a+c-i)+mo)%mo)%mo,b)%mo*(ksm((ksm(S,i)%mo*ksm(S+1,a-i)%mo),d)%mo)%mo;
if(i&1) res=(res-now+mo)%mo;
else res=(res+now)%mo;
}
return res%mo;
}
signed main()
{
n=read();
for(re i=1;i<=n;i++) A[i]=read(),s[i]=A[i],ma=max(ma,A[i]);
for(re i=1;i<=n;i++) B[i]=read(),s[i+n]=B[i],mb=max(mb,B[i]);
jc[0]=1;
for(re i=1;i<N;i++) jc[i]=jc[i-1]*i%mo;
inv[N-1]=ksm(jc[N-1],mo-2);
for(re i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mo;
if(ma!=mb)
{
printf("0\n");
return 0;
}
sort(A+1,A+n+1);
sort(B+1,B+n+1);
sort(s+1,s+n*2+1);
s[0]=unique(s+1,s+n*2+1)-s-1;
int p1=n,p2=n,las1=n+1,las2=n+1;
for(re i=s[0];i;i--)
{
while(p1>1 and A[p1-1]==s[i]) --p1;
while(p2>1 and B[p2-1]==s[i]) --p2;
ans=ans*(solve(las1-p1,las2-p2,n-las1+1,n-las2+1,s[i]))%mo;
las1=p1,las2=p2;
}
printf("%lld\n",(ans%mo+mo)%mo);
return 0;
}
T3 Seat
留坑