2022/7/22

C - Recover an RBS

At first, the idea seemed to be wrong , I've been from ？ Start with the number of , But there seem to be a lot of such considerations , I wrote it for a long time yesterday, but it was wrong , Today, after looking at the solution of the problem, I only need to fill in what should be filled in , Exchange the latest pair of parentheses to see if it is legal

Educational Codeforces Round 132 (Rated for Div. 2) A - E - You know (zhihu.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll t;
string s;
int main(){
    cin>>t;
    while(t--){
        cin>>s;
        ll l=0,r=0,n=s.size();
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') l++;
            else if(s[i]==')') r++;
        }
        if(l==n/2||r==n/2){printf("YES\n");continue;}
        ll maxl=0,minr=s.size(),left=n/2-l,sum=0;
        for(ll i=0;i<s.size();i++){
            if(s[i]=='?'){
                if(left) s[i]='(',left--,maxl=max(maxl,i);
                else s[i]=')',minr=min(minr,i);
            }
        }
        swap(s[maxl],s[minr]);
        bool flag=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') sum++;
            else sum--;
            if(sum<0){
                flag=1;break;
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    system("pause");
    return 0;
} 

1621B - Integers Shop 

This topic is so boring , I wrote it all morning and didn't transfer it out , The state of mind is exploding , The general idea is very good , But I didn't understand the idea of implementation , Too weak. ,,,

codeforces1621B Integers Shop( greedy ）_YounCGY The blog of -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll t,n;
ll c[100005],l[100005],r[100005];
int main(){
    cin>>t;
    while(t--){
      ll L=1e18,R=0,minl=1e18,minr=1e18,minlr=1e18;
      cin>>n;
      for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i]>>c[i];
        if(L>l[i]){L=l[i];minl=1e18;minlr=1e18;}
        if(R<r[i]){R=r[i];minr=1e18;minlr=1e18;}
        if(L==l[i]) minl=min(minl,c[i]);
        if(R==r[i]) minr=min(minr,c[i]);
        if(L==l[i]&&R==r[i]) minlr=min(minlr,c[i]);
        //cout<<L<<" "<<R<<" "<<minl<<" "<<minr<<" "<<minlr<<endl;
        printf("%lld\n",min(minlr,minl+minr));
      }
    }
    system("pause");
    return 0;
} 

1462E1 - Close Tuples (easy version)

Pay attention to six cases of choosing three numbers , Nothing else

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll t,n,a[200005],tx[200005],sum[200005];
int main(){
    cin>>t;
    sum[0]=sum[1]=sum[2]=0;
    for(ll i=3;i<200005;i++) sum[i]=sum[i-1]+(i-2LL)*(i-1LL)/2LL;
    //for(int i=3;i<=6;i++) cout<<i<<" "<<sum[i]<<endl;
    while(t--){
      scanf("%lld",&n);
      for(int i=1;i<=n+10;i++) tx[i]=0;
      for(int i=1;i<=n;i++) scanf("%lld",&a[i]),tx[a[i]]++;
      ll ans=0;  
      for(int i=1;i<=n;i++){
        ans+=sum[tx[i]]+
             ((tx[i]-1)*(tx[i])/2)*tx[i+1]+
             tx[i]*((tx[i+1]-1)*(tx[i+1])/2)+
             ((tx[i]-1)*(tx[i])/2)*tx[i+2]+
             tx[i]*((tx[i+2]-1)*(tx[i+2])/2)+
             tx[i]*tx[i+1]*tx[i+2];
      }
      printf("%lld\n",ans);
    }
    system("pause");
    return 0;
} 

P1265 Highway construction - Luogu prim

In fact, the second is useless , The title says that every city will choose a city close to itself , Second, that is to say, each city chooses cities close to itself to form a ring , But obviously this is wrong , Only equilateral polygons are suitable , But the problem has a unique solution , So there are no polygons , Removing this one is the minimum spanning tree , But there are too many sides , You should use prim

Prim Algorithm - EricWay1024 - Luogu blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll n,vis[5005];
double d[5005];
struct node{
    double x,y;
}c[5005];
double dis(node a,node b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
void prim(){
    ll x=0;
    for(int i=0;i<=n;i++) vis[i]=0,d[i]=1e18;
    d[1]=0;
    for(int i=1;i<=n-1;i++){
        x=0;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(!x||d[j]<d[x])) x=j;
        }
        vis[x]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]) d[j]=min(d[j],dis(c[x],c[j]));
        }
    }
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&c[i].x,&c[i].y);
    prim();
    double ans=0;
    //for(int i=1;i<=n;i++) cout<<d[i]<<" "<<i<<endl;
    for(int i=1;i<=n;i++) ans+=d[i];
    printf("%.2f\n",ans);
    system("pause");
    return 0;
} 

P1340 Animal trail management - Luogu | Minimum spanning tree in reverse order  

This problem feels like running will be overtime , But many of the solutions are running , Maybe my complexity estimation is wrong ,,, But running in reverse order is more stable , Another green question is running too much ,,, Run him backwards , If this side is for the next few days, it cannot be used , You need to run the minimum spanning tree again , Otherwise, you can not run again , This reduces the number of spanning tree runs , Reduce the time complexity ,used Marked are the edges that participate in the minimum spanning tree ,vis Marked is an unusable edge

Answer key P1340 【 Animal trail management 】 - SovietPower The blog of - Luogu blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll n,w,s[205],vis[6005],used[6006];
struct node{
    ll u,v,w,id;
    bool operator<(const node& a)const { return w<a.w; }
}ed[6005],e[6005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
ll kruscal(){
    ll ans=0;
    ll cnt=0;
    for(int i=1;i<=n;i++) s[i]=i;
    for(int i=1;i<=w;i++) used[i]=0;
    for(int i=1;i<=w;i++){
        if(vis[ed[i].id]) continue;
        ll xx=findd(ed[i].u),yy=findd(ed[i].v);
        if(xx==yy) continue;
        s[xx]=yy;used[ed[i].id]=1;
        ans+=ed[i].w;cnt++;
        if(cnt>=n-1) return ans;
    }
    return -1;
}
ll ans[6005];
int main(){
    scanf("%lld%lld",&n,&w);
    //cout<<n<<" "<<w<<endl;
    for(int i=1;i<=w;i++){
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        ed[i].u=u;ed[i].v=v;ed[i].w=w;ed[i].id=i;
    }
    sort(ed+1,ed+w+1);
    ll flag=1;
    ans[w]=kruscal();
    vis[w]=1;
    for(int i=w-1;i>=1;i--){
       // cout<<i<<" "<<used[i+1]<<endl;
        if(flag==0){
            ans[i]=-1;continue;
        }
        if(used[i+1]){
            //cout<<"ssssss "<<i<<endl;
            ans[i]=kruscal();if(ans[i]==-1) flag=0;
        }
        else ans[i]=ans[i+1];
        vis[i]=1;
    }
    for(int i=1;i<=w;i++) printf("%lld\n",ans[i]);
    system("pause");
    return 0;
} 

P1351 [NOIP2014 Improvement group ] Joint weights - Luogu | dfs​​​​​​

The label says lca, But I use dfs Made it out ,,, A distance of 2 There is only joint weight for a point, that is, only with its own grandfather and brother can there be joint weight , Then grandpa's joint weight is easy to find , Just need an array of fathers f Can , Brothers can also o(n) Find out , The joint weight of a point and its brother is equal to the weight of the point *( The next brother until the last brother's and ), Just find a prefix sum , The maximum value is the product of the weights of the two largest siblings , It should be noted that it must be in dfs Then perform the operations of finding prefix and brother , Otherwise enter dfs After that, everything was in a mess  

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll n,f[200005],c[200005],vsu[200005];
vector<ll>v[200005];
ll maxx=0,sum=0;
void dfs(ll u,ll fa){
    f[u]=fa;
    if(f[fa]){
        maxx=max(maxx,c[f[fa]]*c[u]);
        sum=(sum+c[u]*c[f[fa]]*2LL%mod)%mod;
    }
    for(int i=0;i<v[u].size();i++){
        ll j=v[u][i];
        if(j==fa) continue;
        dfs(j,u);
    }
    for(int i=1;i<=v[u].size()+10;i++) vsu[i]=0;
    for(int i=0;i<v[u].size();i++){
        vsu[i+1]=vsu[i];
        ll j=v[u][i];
        if(j==fa) continue;
         vsu[i+1]+=c[j];
    }
    ll max1=0,max2=0;
    for(int i=0;i<v[u].size();i++){
        ll j=v[u][i];
        if(j==fa) continue; 
        if(c[j]>max1){
            max2=max1;max1=c[j];
        }
        else if(c[j]<=max1&&c[j]>max2){max2=c[j];}
        //cout<<u<<" "<<i<<" "<<vsu[v[u].size()]<<" "<<vsu[i+1]<<" "<<(vsu[v[u].size()]-vsu[i])<<endl;
        sum=(sum+c[j]*(vsu[v[u].size()]-vsu[i+1])*2LL%mod)%mod;
    }
    //cout<<u<<" "<<max1<<" "<<max2<<endl;
    maxx=max(maxx,max1*max2);
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        ll u,vv;
        scanf("%lld%lld",&u,&vv);
        v[u].push_back(vv);
        v[vv].push_back(u);
    }
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    dfs(1,0);
    printf("%lld %lld\n",maxx,sum);
    system("pause");
    return 0;
}