周赛_ABC291

C - LRUD Instructions 2

题面说了这样一句：(including the starting and ending points)
我不以为意捏，认为怎么会错过。结果WA了一发。

回头去找别人做的，似乎也只是把我用的set变成了map，本质都是一样的红黑树捏，怎么会是呢？
定睛一看，坐标(0,0)我并没有加入set。绷。

D - Flip Cards

维护两个数组（事实上是2个数）的递推，这种想法一下子就得到了捏。

自行对比为什么下面两个，前者不过样例，后者AC。

constexpr int N=2e5+2,md=998244353;
int a[N],b[N];
long long dp0[N]={1},dp1[N]={1};//dp0是这位不翻牌的方法
int main(){
	int n=read();
	for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
	for(int i=1;i<n;++i){
		if(a[i]!=a[i+1]){
			dp0[i]+=dp0[i-1];
		}
		if(a[i]!=b[i+1]){
			dp1[i]+=dp1[i-1];
		}
		if(b[i]!=a[i+1]){
			dp0[i]+=dp1[i-1];
		}
		if(b[i]!=b[i+1]){
			dp1[i]+=dp1[i-1];
		}
	}
	printf("%lld",dp0[n-1]+dp1[n-1]);
	return 0;
}

（没mod并不是问题，样例很小，所以一开始懒得先写上mod；不过后来因为printf忘记加mod而WA了一发，绷）

constexpr int N=2e5+2,md=998244353;
int a[N],b[N];
long long dp0[N]={1},dp1[N]={1};//dp0是这位不翻牌的方法
int main(){
	int n=read();
	for(int i=0;i<n;++i)a[i]=read(),b[i]=read();
	for(int i=1;i<n;++i){
		if(a[i]!=a[i-1]){
			dp0[i]+=dp0[i-1];
		}
		if(a[i]!=b[i-1]){
			dp0[i]+=dp1[i-1];
		}
		if(b[i]!=a[i-1]){
			dp1[i]+=dp0[i-1];
		}
		if(b[i]!=b[i-1]){
			dp1[i]+=dp1[i-1];
		}
		dp0[i]%=md;dp1[i]%=md;
	}
	printf("%lld",(dp0[n-1]+dp1[n-1])%md);
	return 0;
}

E - Find Permutation

拓扑排序没看出来，绷。搁那假做法DFS。
卡半天dfs之后，果断去Luogu复制了一个题解然后去VSCode格式化了一下

E - Find Permutation

想法正确！猜猜栽在哪里？

constexpr int N = 1e5 + 2, inf = 1e8;
char s[N][12];
bool from[N][11];
int dis[N], sid[N];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
        for (int k = 1; k <= m; ++k)
            if (s[i][k] == '1')
                from[i + k][k] = 1;
    }
    /////////////////////////////////////////////////
    fill_n(dis, n + 1, inf);
    dis[1] = 0;
    for (int i = 1; i < n; ++i)
    {
        for (int j = i + 1; j <= min(i + m, n); ++j)
            if (s[i][j - i] == '1')
                dis[j] = min(dis[j], dis[i] + 1);
    }
    // for (int i = 1; i <= n; ++i)
    //     printf("dis[%d]=%d\n", i, dis[i]);
    /////////////////////////////////////////////////
    fill_n(sid, n + 1, inf);
    sid[n] = 0;
    for (int j = n; j > 1; --j)
    {
        for (int i = j - 1; i >= max(j - m, 1); --i)
            if (from[j][j - i])
                sid[i] = min(sid[i], sid[j] + 1);
    }
    // for (int i = 1; i <= n; ++i)
    //     printf("sid[%d]=%d\n", i, sid[i]);
    /////////////////////////////////////////////////
    for (int k = 2; k < n; k++)
    {
        int t = inf;
        for (int i = max(k - m + 1, 1); i < k; ++i)
            for (int j = k + 1; j <= min(k + m - 1, n); ++j)
                if (j - i <= m && s[i][j - i]/*溜溜溜*/=='1'/*溜溜溜*/)
                {
                    t = min(t, dis[i] + sid[j] + 1);
                    //printf("skip %d, %d to %d is %d\n",k, i, j, dis[i] + sid[j] + 1);
                }
        printf("%d ", t < inf ? t : -1);
    }
    return 0;
}

mad 不要勉强自己区分不同的数据类型！以后二进制串的话char只用来读入！读入之后请转为bool数组！

Ex - Balanced Tree

一开始猜的是通过旋转(Rotate)变成SBT，保持第一性质不便而使得答案趋于第二性质。
@FFiber这么做WA了2次，随后通过1-2-3-4-5的链把自己hack掉。

后来去洛谷查题解看到点分治。然后去Atcoder学习了一下。赛后同级生老哥来给大家说是点分治板子。6。

后面再说吧。先走人了