写在前面
\(Day1\)，这场考试难度适中，我觉得海星
T1 有理树(SBT)
Idea
\(Stern-Brocot\ Tree \to SBT\)
容易发现在每一行都存在\(\displaystyle \frac{m}{n} \lt \frac{m+m'}{n+n'} \lt \frac{m'}{n'}\)
根据图还发现，当\(\displaystyle\frac{a}{b}\)小于当前节点时，向左走\((L)\)；大于当前节点时，向右走\((R)\)
并且发现题目中不存在向下走的情况，去掉多余点后，发现这是一颗完全二叉树(然而并没有什么卵用，请忽略这行话
设当前节点为\(\displaystyle \frac{m}{n}\),则
当\(\displaystyle \frac{a}{b} \gt \frac{m}{n}\)时，\(a \times n>b \times m\);
当\(\displaystyle \frac{a}{b}<\frac{m}{n}\)时，\(a \times n<b \times m\)；
根据这个条件进行判断
什么时候结束呢？
当\(a \times n=b \times m\)时。原因很简单
结束时\(\displaystyle \frac{m}{n} = \frac{\frac{a}{gcd(a,b)}}{\frac{b}{gcd(a,b)}}\),所以\(a \times n=b \times m=\displaystyle \frac{a \times b}{gcd(a,b)}\)，(应该没错。。。吧。。。
再仔细分析一波，\(a \times b\)好像爆\(int\)了，所以要开\(long\ long\)。
Code
signed main(){
// freopen(File".in","r",stdin);
// freopen(File".out","w",stdout);
int a=read(),b=read();
int x=0,y=1;
int m=1,n=1;
int m1=1,n1=0;
while(a*n!=b*m){
if(a*n<b*m){
putchar('L');
m1=m; n1=n;
}
else{
putchar('R');
x=m;y=n;
}
m=x+m1; n=y+n1;//按规则计算下一行的分子分母。
}
return 0;
}T2 字符串问题(string)
Idea
\(20\ pts\)：搜索，预计复杂度\(O(T \ast k!)\)
\(50\ pts\)：建图，跑最长路，用\(Bellman-Ford/SPFA\)判断负环，复杂度\(O(T \ast k^4)\)
\(100\ pts\)：新建一个节点，向所有点连边权为0的边，或者直接让所有点距离为0开始跑最长路。复杂度\(O(T \ast k^3)\)
Code
int w[maxn][maxn];
int ans,dis[maxn];
signed main(){
// freopen(File".in","r",stdin);
// freopen(File".out","w",stdout);
int T=read();
while(T--){
mem(dis,0); ans=0; //初始化很重要
int k=read();
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
w[i][j]=read();
for(int l=1;l<=k;l++)
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
dis[j]=max(dis[j],dis[i]+w[i][j]);
bool flag=1;
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
if(dis[j]<dis[i]+w[i][j]) flag=0;
if(flag){
for(int i=1;i<=k;i++)
ans=max(ans,dis[i]);
printf("%d\n",ans);
}
else puts("-1");
}
return 0;
}T3 序列(sequence)
Idea
考场上自然是暴力做了，暴力自然不难
对于\(50\ pts\)，使用\(ST\)表，复杂度\(O(n^2)\)
对于\(100\ pts\)，使用二分+分治思想；
找到全局最小值，处理跨过最小值的区间，然后分裂为两块。
最小值和一个端点确定后，满足条件的另一个端点处的值是确定的，于是只需统计该权值在对应区间的出现次数。
对每个权值，记录下其出现的全部位置，然后二分就可以知道其在某个区间出现了多少次。
枚举端点时选择枚举较短的一边可以保证复杂度，因为每次被计算代表大小至少减半，于是一个位置最多计算\(\log n\)次
复杂度\(O(n \log^2 n)\)
我们有三种策略:
- \(O(n^3)\)枚举\(l,r\)，再枚举\(\displaystyle \min_{l \le k \le r}a_k\)
我们的式子是\(a_l \oplus a_r \oplus a_{\min}=D\)，我们相当于知三求一
已知\(a_l,a_{\min},D\),求\(a_r\)；
已知\(a_r,a_{\min},D\),求\(a_l\)
以上两个式子等效
Code
//暴力，根据题意的暴力T_T
int a[maxn],ans;
inline int find(int l,int r){
int res=inf;
for(int i=l;i<=r;i++)
res=min(res,a[i]);
return res;
}
signed main(){
// freopen(File".in","r",stdin);
// freopen(File".out","w",stdout);
int n=read(),D=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
if((a[i]^a[j]^find(i,j))==D)
ans++;
}
printf("%d",ans);
return 0;
}
//该暴力复杂度O(n^3)，预计20 pts,开O2可以有50pts。。。。const int N=100005,M=1<<20;
int T,n,D;
int a[N];
int lc[N],rc[N];
int stk[N],tp;
vi bac[M];
LL ans;
void solve(int w,int l,int r){
if(w-l<r-w){
for(int i=l;i<=w;++i){
int v=D^a[i]^a[w];
ans+=lower_bound(bac[v].begin(),bac[v].end(),r+1)-lower_bound(bac[v].begin(),bac[v].end(),w);
}
}else{
for(int i=w;i<=r;++i){
int v=D^a[i]^a[w];
ans+=lower_bound(bac[v].begin(),bac[v].end(),w+1)-lower_bound(bac[v].begin(),bac[v].end(),l);
}
}
if(lc[w])solve(lc[w],l,w-1);
if(rc[w])solve(rc[w],w+1,r);
}
int main(){
freopen(File".in","r",stdin);
freopen(File".out","w",stdout);
n=read();D=read();ans=0;
for(int i=0;i<N;++i)bac[i].clear();
for(int i=1;i<=n;++i){
a[i]=read();bac[a[i]].push_back(i);
if(!tp||a[i]>=a[stk[tp]])stk[++tp]=i;
else{
for(;tp&&a[i]<a[stk[tp]];--tp)rc[stk[tp-1]]=stk[tp];
lc[i]=stk[tp+1];stk[++tp]=i;
}
}
for(;tp;--tp)rc[stk[tp-1]]=stk[tp];
solve(rc[0],1,n);
printf("%lld\n",ans);
fclose(stdin);fclose(stdout);
return 0;
}\[ The \quad End \]
\[ \text{她渐渐忘了我，但是她并不晓得；遍体鳞伤的我，一天也在没爱过。-《那女孩对我说》} \]