前言
好久没考过试了，居然考这么挫qwq。。。T1 water
题目描述
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。
中位数是指把所有元素从小到大排列后，位于中间的数。（来源：[CQOI2009]中位数）
【数据规模】
对于30%的数据中，满足n≤100；
对于60%的数据中，满足n≤1000；
对于100%的数据中，满足n≤100000,1≤b≤n。
考试分析
emmm....不是说好第一题是水题吗？我觉得再怎么模拟也只有O(n^2)啊！
肯定TM又是一道找规律题..............推了1h居然没退出来，wc，果断60分滚粗
正解
（ps：思路来自lsq大佬）
1. 首先开一个sum[ ]数组、一个变量q，线性扫一遍，
如果a[i]>b，则++q；如果a[i]
2. 接着开一个f[ ][2]数组，并初始化f[0][0]=1;
从1扫到pos-1，
如果i是偶数，则++f[sum[i]][0]；否则++f[sum[i][1]；
然后从pos+1扫到n开始匹配
如果i是偶数，因为中间有个b，所以奇偶性要变，则ans+=f[sum[i]][1]；否则ans+=f[sum[i]][0]；
3. 最后输出ans即可
Code
#include<cstdio>
using namespace std;
template<typename TP>inline void read(TP & x)
{
x=0;int f=1;register char c=getchar();
while(c<'0'||c>'9') if(c=='-') f=-1;c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
template<typename TP>inline void print(TP x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,b,sum[1000005],ans,pos,qwq,a[1000005],f[1000005][2];
int main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
read(n),read(b);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i)
{
if(a[i]>b) ++qwq;
else if(a[i]<b) --qwq;
else if(a[i]==b) pos=i;
sum[i]=qwq;
}
f[0][0]=1;
for(int i=1;i<pos;++i)
{
if(i%2==0) ++f[sum[i]][0];
else ++f[sum[i]][1];
}
for(int i=pos;i<=n;++i)
{
if(i%2==0) ans+=f[sum[i]][1];
else ans+=f[sum[i]][0];
}
print(ans);
return 0;
}
T2 str
题目描述
已知有两个字串$A,B$及一组字串变换的规则（至多$6$个规则）:
$A_1$ ->$ B_1$
$A_2$ -> $B_2$
规则的含义为：在 $A$中的子串 $A_1$ 可以变换为$ B_1$，$A_2$ 可以变换为 $B_2$ …。
例如：$A$='$abcd$'$B$＝'$xyz$'
变换规则为：
‘$abc$’->‘$xu$’‘$ud$’->‘$y$’‘$y$’->‘$yz$’
则此时，$A$可以经过一系列的变换变为$B$，其变换的过程为：
‘$abcd$’->‘$xud$’->‘$xy$’->‘$xyz$’
共进行了$3$次变换，使得$A$变换为$B$。
所有字符串长度的上限为$20$。
若在$10$步（包含$10$步）以内能将$A$变换为$B$，则输出最少的变换步数；否则输出"NO ANSWER!"
（来源：NOIP2002 字符变换）
考试分析
正解
T3 tree
太弱了，不想更