2022/7/15

P6121 [USACO16OPEN]Closing the Farm G - Luogu | New ecology of computer science education (luogu.com.cn) Union checking set

I've done this problem before , Not now ,,, The key is to think about the opposite , Turn positive closing into negative opening , from n-1 Start recording how many edges are added , If the number of sides added is points -1, Then it is connected

2022/1/29_killer_queen4804 The blog of -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,m,s[200005],ans[200005],vis[200005],t[200005];
ll head[500005],cnt;
struct Edge{
    ll next,from,to;
}edge[500005];
void addedge(ll from,ll to){
    edge[++cnt].from=from;
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}
ll findd(ll x){
    return x==s[x]?x:s[x]=findd(s[x]);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
    for(int i=1;i<=n;i++) s[i]=i;
    vis[t[n]]=1;
    ans[n]=1;
    ll k=0;
    for(int i=n-1;i>=1;i--){
        vis[t[i]]=1;
        for(int j=head[t[i]];j;j=edge[j].next){
            if(vis[edge[j].to]){
                ll x=findd(t[i]),y=findd(edge[j].to);
                if(x!=y){
                    k++;
                    s[x]=y;
                }
            }
        }
        if(k==n-i) ans[i]=1;
        else ans[i]=0;
    }
    for(int i=1;i<=n;i++)
        if(ans[i]) printf("YES\n");
    else printf("NO\n");
    return 0;
}

Palindromic Numbers  structure

The number output must be the same as the number given , That is to say, it has to be n position , Consider taking 99 Come on , You can consider 111 This palindrome number , So the answer is 12, And then you can see that 999 The answer is 112,9999 The answer is 1112, The number of digits is the same , And most of the scores can be one more 111... Subtract the given number to get the answer , But compared to 1..2 A small number is not enough , So you can use that 1000..01 The answer is obtained by subtracting the given number from the number in this form

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n;
char s[100005],c[100005],ans[100005],ch[100005];
bool pd(){
    for(int i=1;i<=n;i++){
        if(s[i]<ch[i]) return 0;
        if(s[i]>ch[i]) return 1;
    }
    return 1;
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        scanf("%s",s+1);
        for(int i=1;i<n;i++) ch[i]='1';ch[n]='2';
        if(pd()){
            for(int i=1;i<=n+1;i++) c[i]='1';
        }
        else{
            for(int i=2;i<=n;i++) c[i]='0';c[1]=c[n+1]='1';
        }
        for(int i=n;i>=1;i--){
            if(c[i+1]<s[i]){
                    c[i+1]+=10;
                    ll cnt=i;c[cnt]--;
                    while(cnt>0&&c[cnt]<0){
                        c[cnt]+=10;
                        c[--cnt]--;
                    }
            }
            //cout<<c[i+1]<<" "<<s[i]<<" "<<(c[i+1]-'0')-(s[i]-'0')<<endl;
            ans[i]=(c[i+1]-'0')-(s[i]-'0')+'0';
        }
        for(int i=1;i<=n;i++) cout<<ans[i];cout<<'\n';
    }
    return 0;
}

Helping the Nature  Difference

After reading the title, I have no way to start , But find out a difference group and you can find , The three operations previously pressed have become

b[1]-1,b[i]+1;b[1]+1;b[i]-1; These three operations , In this way, we try to use the 1 Kind of operation , Because you can change two at the same time , Then use the other two , Our goal is to change the difference array into 0, So sometimes b[i](i>1) It will be less than 0 And the first operation alone cannot make b[i]=0, So we should use the second operation to make b[1] increase ,b[i] Greater than or equal to 0 Then you can use the third operation to eliminate it in turn , The code is directly simplified into oneortwo formulas , But it all means the same

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n,a[200005],b[200005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ll sum=0,ans=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
            if(i>1){
                sum+=b[i]<0?abs(b[i]):0;
                ans+=abs(b[i]);
            }
        }
        ans+=abs(b[1]-sum);
        printf("%lld\n",ans);
    }
    return 0;
}