Codeforces Round #453 (Div. 2)(A-E題解)

A：pig站在傳送帶上隻能在傳送帶上移動的情況下判斷是否能夠到達m初始位置0

題解:用dp[i]表示pig能不能到達接着轉移方程就是在傳送在dp[i] = max(dp[i-1],dp[i])即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define root 1,1,n
#define ls 2*rt
#define rs 2*rt+1
#define mid (L+R)/2
#define lson ls,L,mid
#define rson rs,mid+1,R
const int mx = 1e5+5;
int l[mx];
int r[mx];
int dp[mx];
int main(){
    int n,m;
    memset(dp,0,sizeof(dp));
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d%d",&l[i],&r[i]);
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = l[i]+1; j <= r[i]; j++)
            dp[j] = max(dp[j-1],dp[j]);
    if(dp[m])
        puts("YES");
    else
        puts("NO");
    return 0;
}
           

B：讓你塗一棵樹的顔色，塗完改結點後其所有子樹都會變成該顔色，要求你塗成特定的顔色需要塗多少步

題解:直接從上往下塗判斷是否為想要的顔色即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define root 1,1,n
#define ls 2*rt
#define rs 2*rt+1
#define mid (L+R)/2
#define lson ls,L,mid
#define rson rs,mid+1,R
const int mx = 1e5+5;
vector<int>g[mx];
int col[mx];
int ans;
void dfs(int u,int fa,int s){
    if(s!=col[u])
        ans++;
    for(auto v: g[u]){
        if(v!=fa){
            dfs(v,u,col[u]);
        }
    }
}
int main(){
    int n,m;
    int a;
    ans = 0;
    scanf("%d",&n);
    for(int i = 2; i <= n; i++){
        scanf("%d",&a);
        g[a].push_back(i);
    }
    for(int i = 1; i <= n; i++)
        scanf("%d",&col[i]);
    dfs(1,0,0);
    printf("%d\n",ans);
    return 0;
}
           

C:：給你一課樹，深度0-n,深度為然後是0-n的樹判斷是否能構造出不同構的樹

題解：如果有兩個以上高度連續且個數都為2以上的話肯定能構造出不同構的樹，接着讓同一高度的結點一個指向開始結點一個指向末尾結點即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define root 1,1,n
#define ls 2*rt
#define rs 2*rt+1
#define mid (L+R)/2
#define lson ls,L,mid
#define rson rs,mid+1,R
const int mx = 1e5+5;
int a[mx];
int main(){
    int n,m;
    scanf("%d",&n);
    int ok = 1;
    int sum = 0;
    for(int i = 0; i <= n; i++){
        scanf("%d",&a[i]);
        sum += a[i];
    }
    for(int i = 1; i <= n; i++)
        if(a[i]>=2&&a[i-1]>=2)
            ok = 0;
    if(ok)
        puts("perfect");
    else{
        puts("ambiguous");
        int pre = 0;
        int len = 1;
        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= a[i]; j++){
                printf("%d%c",pre,len==sum?'\n':' ');
                len++;
            }
            pre = len-1;
        }
        pre = 0;
        len = 1;
        int s = 0;
        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= a[i]; j++){
                printf("%d%c",j%2==0?s:pre,len==sum?'\n':' ');
                len++;
            }
            pre = len-1;
            s = len-a[i];
        }
    }
    return 0;
}
           

D：給你一個公式然後判斷多項式到達B等于0需要多少步

題解：設p1 = 1, p2 = x

p（n） = x*p（n-1） + p（n-2）即可

因為限制了系數隻能為-1,0,1是以我們求得時候取膜2即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mx = 1e5+5;
int a[300],b[300],c[300];
	int n;
void calc(){
	int *x,*y,*z;
	x = a;
	y = b;
	z = c;
	for(int i = 1; i < n; i++){
		memset(z,0,sizeof(c));
		for(int j = 0; j <= i; j++){
			z[j+1] = x[j];
			
		}
		for(int j = 0; j < i; j++){
			z[j] = (z[j]+y[j])%2;
		//	printf("%d",y[j]);
		}
		swap(x,z);
		swap(z,y);
	}
	printf("%d\n",n);
	for(int i = 0; i <= n; i++)
		printf("%d%c",x[i],i==n?'\n':' ');
	n--;
	printf("%d\n",n);
	for(int i = 0; i <= n; i++)
		printf("%d%c",y[i],i==n?'\n':' ');
}
int main(){
	scanf("%d",&n);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0] = 0;
	a[1] = 1;
	b[0] = 1;
	calc();	
	return 0;
}
           

E：給你n個點的無向圖，保證沒有偶數點的環，有q個查詢，每次給l,r問隻保留l,r編号的點，問有多少對區間内的點構成二分圖

題解:如果都沒有環的情況是(n+1)*n/2那麼考慮一下有環的化我如果是這個環内編号的最小的或者比他小的點那麼我隻能延伸到環的最大點-1接着當給你l，r的時候我隻要找出最右邊的那個有環的最小點加1即可,這樣分成兩部分就是sum[l]-sum[x]+(r-x+2)*(r-x+1)/2,這些我們可以預處理一下在r位置的最右邊的環的點是哪一個，接着就是求環我們當碰到已經周遊過的點那麼我們可以用一個棧存一下一直後退直到棧頂的元素是我們周遊到的點即可.最後我這個點可能不在環内用另外一個數字标記一下即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long int ll;
const int mx = 3e5+5;
stack<int>s;
int front[mx];
vector<int>g[mx];
int pre[mx];
int Max[mx],Min[mx];
ll sum[mx];
void dfs(int u,int fa){
    pre[u] = 1;
    s.push(u);
    for(auto v: g[u]){
        if(v!=fa){
            if(pre[v]==0) dfs(v,u);
            else if(pre[v]==1){
                int x = u,y = u;
                while(!s.empty()){
                    int z = s.top();
                    s.pop();
                    x = min(z,x);
                    y = max(z,y);
                    if(z==v)    break;
                }
                Max[y] = x;
                Min[x] = y;
            }
        }
    }
    if(!s.empty()&&s.top()==u) s.pop();
    pre[u] = 2;
}
int main(){
    int n,m,q;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0; i <= n+1; i++)
            Max[i] = 0,Min[i] = n+1;
    for(int i = 1; i <= n; i++)
        if(!pre[i])
            dfs(i,i);
    int x,y;
    for(int i = n; i >= 1; i--){
        Min[i] = min(Min[i+1],Min[i]);
        sum[i] = sum[i+1] + Min[i]-i;
    }
    for(int i = 1; i <= n; i++){
        Max[i] = max(Max[i-1],Max[i]);
        cout<<Max[i]<<endl;
    }
    scanf("%d",&q);
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        x = max(l,Max[r]+1);
        //cout<<x<<endl;
        ll ans = sum[l]-sum[x];
        //cout<<ans<<endl;
        ans  += 1ll*(r-x+2)*(r-x+1)/2;
        printf("%I64d\n",ans);
    }
    return 0;
}
           

給你