Cydiater

CS Academy Round #61 Solution

首先庆祝一下 CSA 红名啦!

Strictly Increasing Array

a[i]a[i] - i,求个 LIS 就完了。

Unstable Merge Sort

由于数据量非常小,我们枚举每个位置上的数,然后考虑每个位置上的数重新分配到其他位置上的概率。因为我们可以通过提前排序一次知道每个数值的位置范围,所以我们可以只求每个位置上的数排序完后前面有多少个相同数值的数。

我们考虑预处理一个 DP 数组g[i][j][0/1][0/1]表示对于相同的数值来说。左边的块有$i$个数,右边的块有$j$个数,同时左右块后面是否还有相同的数的概率,这个很好预处理出来。

接着我们模拟一次归并排序的过程。首先当递归到我们枚举到的位置时,令f[0] = 1即这个数前面有 0 个数的概率是 1,然后考虑当合并两个块时,我们假设这个数在右边的块中,这时候我们枚举这个数在块的第几个位置上,然后我们考虑他在左边第几个数弹出之后弹出,利用之前预处理的 DP 数组转移即可。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 605;
const db eps = 1e-10;

int N, a[MAXN], b[MAXN];
db g[MAXN][MAXN][2][2], f[MAXN], h[MAXN];

void DFS(int le, int ri, int o){
    if (le == ri) {
        f[0] = 1;
        return;
    }
    int mi = (le + ri) >> 1;
    if (o <= mi) {
        DFS(le, mi, o);
        up (i, 0, N) h[i] = 0;
        int cl = 0, cr = 0;
        up (i, le, mi)         cl += (a[i] == a[o]);
        up (i, mi + 1, ri)     cr += (a[i] == a[o]);
        up (i, 1, cl) up (j, 0, cr) {
            if (j < cr) h[i + j - 1] += f[i - 1] * g[i - 1][j][1][1] / 2;
            else        h[i + j - 1] += f[i - 1] * g[i - 1][j][1][0];
        }
        up (i, 0, N) f[i] = h[i];
    }else {
        DFS(mi + 1, ri, o);
        up (i, 0, N) h[i] = 0;
        int cl = 0, cr = 0;
        up (i, le, mi)         cl += (a[i] == a[o]);
        up (i, mi + 1, ri)     cr += (a[i] == a[o]);
        up (i, 1, cr) up (j, 0, cl) {
            if (j < cl) h[i + j - 1] += f[i - 1] * g[j][i - 1][1][1] / 2;
            else        h[i + j - 1] += f[i - 1] * g[j][i - 1][0][1];
        }
        up (i, 0, N) f[i] = h[i];
    }
}

int main(){
    scanf("%d", &N);
    up (i, 1, N) scanf("%d", &a[i]);
    up (i, 0, 1) up (j, 0, 1) g[0][0][i][j] = 1;
    up (i, 0, N) up (j, 0, N) {
        g[i][j + 1][0][0] += g[i][j][0][1];
        g[i][j + 1][0][1] += g[i][j][0][1];
        g[i + 1][j][0][0] += g[i][j][1][0];
        g[i + 1][j][1][0] += g[i][j][1][0];
        g[i + 1][j][0][1] += g[i][j][1][1] / 2;
        g[i + 1][j][1][1] += g[i][j][1][1] / 2;
        g[i][j + 1][1][0] += g[i][j][1][1] / 2;
        g[i][j + 1][1][1] += g[i][j][1][1] / 2;
    }
    up (i, 1, N) b[i] = a[i];
    sort(b + 1, b + N + 1);
    up (i, 1, N) {
        int st;
        down (j, N, 1) if (b[j] == a[i]) st = j;
        up (j, 0, N) f[j] = 0;
        DFS(1, N, i);
        db ans = 0;
        up (j, 0, N - 1) ans += (st + j) * f[j];
        printf("%.10lf\n", ans);
    }
    return 0;
}

Xor the Graph

比赛的时候 yy 了半天解异或方程组什么的..然后看到数据范围就放弃梦想去养老了..

看题解,这题解题思路也挺无脑的。首先,我们考虑一个连通图中,如果全是黑边,那么显然我们需要只走一个欧拉路,但是原图不一定存在欧拉路,我们考虑强行把原图补成一个可以走欧拉回路的图,因为原图中度数是奇数的点一定是偶数个,所以奇数度数的点两两之间连一条边就好了。然后我们可以构造出一个欧拉回路,然后把强行加的边给删掉,把欧拉回路给拆成若干条路径,这个时候就是对应的答案了..但是我不理解为什么这样构造一定是最优的,希望那个神犇理解可以在评论里指点一下。

之后考虑有白边的,这个就很简单了,我们把白边给乘二加到原图中就行了。

然后需要注意,普通的 DFS 求欧拉回路的算法是可以被菊花图卡到 $n^2$的,具体的参考我的代码吧。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 4e5 + 5;

int N, M;

struct edge {
    int x, y, next, rev;
}e[MAXN << 2];
int LINK[MAXN], tmp, len = 0, deg[MAXN], nodes[MAXN], cnt = 0, odd[MAXN], oddcnt = 0, ans = 0;
bool vis[MAXN], one[MAXN], isone, play[MAXN << 1], key[MAXN << 1];
vector<int> S[MAXN];
inline void ins(int x, int y, int rev){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].x = x; e[len].rev = len + rev;
}
inline void Ins(int x, int y){
    ins(x, y, 1);
    ins(y, x, -1);
    deg[x]++; deg[y]++;
}

void DFS(int node){
    vis[node] = 1;
    nodes[++cnt] = node;
    isone |= one[node];
    Auto (i, node) if (!vis[e[i].y]) DFS(e[i].y);
}

void Go(int node){
    int pre = 0;
    for (int i = LINK[node]; i; i = e[i].next) if (!play[i]) {
        play[i] = play[e[i].rev] = 1;
        Go(e[i].y);
        if (key[i]) ans++;
        else S[ans].push_back(i);
    }else LINK[node] = e[i].next;
}

void Work(){
    oddcnt = 0;
    up (i, 1, cnt) if (deg[nodes[i]] & 1) odd[++oddcnt] = nodes[i];
    for (int i = 1; i <= oddcnt; i += 2) {
        Ins(odd[i], odd[i + 1]);
        key[len] = key[len - 1] = 1;
    }
    ans++;
    Go(oddcnt > 0 ? odd[1] : nodes[1]);
    while (ans && S[ans].empty()) ans--;
}

int main(){
    scanf("%d%d", &N, &M);
    up (i, 1, M) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        Ins(x, y);
        if (!v) Ins(x, y);
        if (v) {
            one[x] = 1;
            one[y] = 1;
        }
    } 
    up (i, 1, N) if (!vis[i]) {
        isone = 0;
        cnt = 0;
        DFS(i);
        if (isone) Work();
    }
    printf("%d\n", ans);
    up (i, 1, ans) {
        printf("%d ", SZ(S[i]) + 1);
        printf("%d ", e[S[i][0]].y);
        up (j, 0, SZ(S[i]) - 1) printf("%d ", e[S[i][j]].x);
        puts("");
    }
    return 0;
}

Find the Matrix

第一次在比赛的时候碰到了差分约束的题..

首先,如果题目中没有对于$A$矩阵取值的限制,我们对$A$矩阵的第一行和第一列取随机值,然后令

$$a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1]$$

即可。但是考虑到对于$A$的取值有范围的限制,我们考虑能否挖掘更多的性质。

接着,我们发现如果对于一行或一列交错加上/减去一个相同的数,那么是不影响$B$矩阵的取值的,因为$B$的取值总是有同一行相邻列的相加和同一列相邻行的相加,这一点非常重要。

然后我们把$A$矩阵进行二分图染色,颜色不同的格子,每次调整的正负形是不同的,我们考虑把行列和相同的元素$a[i][j]$变为$K - a[i][j]$,这个并不影响对于取值范围的约束,我们只需要在处理后再做一遍相同的操作即可。

这个时候对于一行和一列的调整操作的正负就可以取相同的了,我们令$R[i]$为第$i$行的调整值,令$C[i]$为第$i$列的调整值,这个时候新的$a[i][j]$就是$a[i][j] + R[i] - C[j]$,根据这个式子的取值范围,很容易转化成差分约束的形式。

然后就做完了!

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 405;
const ll oo = 1LL << 60;

int N, M, K, S, R[MAXN], C[MAXN], cnt = 0;
ll a[MAXN][MAXN], b[MAXN][MAXN];

struct edge {
    int y, next;
    ll v;
}e[MAXN * MAXN << 1];
int LINK[MAXN], len = 0, mark[MAXN];
ll dis[MAXN];
bool vis[MAXN];
deque<int> q;
inline void ins(int x, int y, ll v){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].v = v;
}

int main(){
    scanf("%d%d%d", &N, &M, &K);
    up (i, 1, N - 1) up (j, 1, M - 1) scanf("%d", &b[i][j]);
    up (i, 2, N) up (j, 2, M) a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1];
    up (i, 1, N) up (j, 1, M) if ((i + j) & 1) a[i][j] = K - a[i][j];
    up (i, 1, N) R[i] = ++cnt; 
    up (i, 1, M) C[i] = ++cnt;
    S = ++cnt;
    up (i, 1, N) ins(S, R[i], 0);
    up (i, 1, M) ins(S, C[i], 0);
    up (i, 1, N) up (j, 1, M) ins(R[i], C[j], a[i][j]);
    up (i, 1, M) up (j, 1, N) ins(C[i], R[j], K - a[j][i]);
    up (i, 1, cnt) dis[i] = oo;
    q.push_back(S); dis[S] = 0; vis[S] = 1;
    while (!q.empty()) {
        int node = q.front(); q.pop_front();
        Auto (i, node) if (dis[e[i].y] > dis[node] + e[i].v) {
            dis[e[i].y] = dis[node] + e[i].v;
            if (!vis[e[i].y]) {
                if (++mark[e[i].y] >= cnt) {
                    puts("-1");
                    return 0;
                }
                q.push_back(e[i].y);
                vis[e[i].y] = 1;
            }
        }
        vis[node] = 0;
    }
    up (i, 1, N) up (j, 1, M) a[i][j] += dis[R[i]] - dis[C[j]];
    up (i, 1, N) up (j, 1, M) if ((i + j) & 1) a[i][j] = K - a[i][j];
    up (i, 1, N) up (j, 1, M) printf("%lld%c", a[i][j], (j == M ? '\n' : ' '));
    return 0;
}