Problem A. TreeScript

简单树 dp。

const int N = int(1e6) + 9;
VI adj[N]; int dp[N];
int n, z;

void dfs(int u) {
    dp[u] = 0;
    for (auto v: adj[u]) {
        dfs(v);
        checkMax(dp[u], dp[v] + 1);
    }

    int c = 0;
    for (auto v: adj[u]) {
        if (dp[u] == dp[v] + 1) ++c;
    }
    if (c == 1) dp[u] -= 1;

}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n);
        REP_1(i, n) adj[i].clear();
        REP_1(i, n)  adj[RD()].PB(i);
        dfs(1); cout << dp[1] + 1 << endl;
    }
}

Problem B. Big Picture

第一反应是每个格点独立染色。。。。卧槽这能做？
然后发现是每一行和每一列都独立染色。。。哦。。。那样黑色一定只有一个连通块，且每个白色块都是矩形。。有且仅有一个右下角。。
那么还是可以利用期望的线性性。。考察每个点成为白色区域的右下角的概率即可。。。

Problem E. Goose, goose, DUCK?

不知为何，让我想到了 dQuery。先考虑对答案取反，那么显然就是维护区间并的测度，线段树即可。

做法也类似，对每种数字，开个 queue 记录前面出现的位置。
然后找到插入新数字前后变化的区间，操作线段树即可。

const int N = int(1e6) + 9;
int n;

struct rec{
    int cov, cnt;
} T[8*N];


#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r


void upd(int x, int l, int r) {
    if (T[x].cnt > 0) T[x].cov = r - l + 1;
    else T[x].cov = T[lx].cov + T[rx].cov;
}

void inc(int x, int d) {
    T[x].cnt += d;
}


/*int Query(int x, int l, int r, const int a, const int b) {
    if (b < l || r < a) return 0;
    if (a <= l && r <= b) {
        return T[x];
    } else {
        return min(Query(lc, a, b), Query(rc, a, b), cmp);
    }
}*/

void Add(int x, int l, int r, int a, int b, int d) {
    if (b < l || r < a) return;
    if (a <= l && r <= b) {
        inc(x, d);
    } else {
        Add(lc, a, b, d);
        Add(rc, a, b, d);
    }
    upd(x,l,r);
}

map<int, VI> H;
int m;

void gao(int x, int d) {

#define t H[x]

    if (SZ(t) < m) return;
    if (SZ(t) == m) {
        int l = 1, r = t[0];
        Add(1, 1, n, l ,r ,d);  // m-1
    } else { // 0..m ,
        int l = t[SZ(t)-(m+1)]+1, r = t[SZ(t)-m];
        Add(1, 1, n, l ,r ,d);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    RD(n, m);
    LL z = 0;
    REP_1(i, n) {
        int x; RD(x);

        gao(x, -1);
        H[x].PB(i);
        gao(x, 1);

        z += i - T[1].cov;
    }
    cout << z <<endl;
}

Problem F. Sum of Numbers

看起来人畜无害的签到题。。。但是不知为何非常卡时。。。难道是因为高精度太慢？
看了一下其它人的代码。。。貌似 dp 和 搜索都可以过？
– dp
– 搜索

Problem H.

签到题。

int main()
{
//	freopen("A.in","r",stdin);
//	freopen(".out","w",stdout);
//	int p=read();
//	For(i,p)if(p%i!=0) cout<<p%i<<endl;
	ll l,r,b,k;
	cin>>l>>r>>b>>k;
	cout<<((l+b-1)/b)*b*k;
	return 0;
}

Problem K.

签到题。

int main() {
	
	int n=read();
	For(i,n) a[i]=read();
	
	sort(a+1,a+1+n);
	n=unique(a+1,a+1+n)-a-1;
	if(n==1) cout<<a[1]<<endl;	
	else if(a[1]*2<=a[2]) cout<<a[1]<<endl;
	else cout<<min(a[1]/2,a[2]/2)<<endl;
	return 0;
}

Posted by xiaodao
Category: 日常