4 Training sim 7 (a day of losing 100 points, WTF)

A. Reconnaissance (tarjan abbreviation)

Topic description

input format

output format

Sample

sample input

12 11
10 11 2 3 4 5 1 1 1 1 1 1
1 2
2 3
1 3
4 5
5 6
6 7
8 9
9 12
11 12
10 11
8 10 

Sample output

8 9 10 11 12
1 2 3

  analyze

I hate this question, (so easy, but...), a break is written outside the parentheses, but the second question has no output, ~~~~~~~~

This is a simple tarjan shrink point, then record the number of bases and the number of enemies in the SCC, and then take the max, while traversing each point to find the output, it is ok, break, don't write the wrong position ah ah ah ah ah ah ah! ! !

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1100;
int n,m;
int a[N];
int sum[N],summ[N],dfn[N],low[N];
int Time,tot,cnt,top;
int x,y,g[N],head[N];
bool vis[N];
int sta[N];

struct edge{
    int to;
    int ne;
}e[N<<2];

void add(int u,int v){
    e[++cnt].to = v;
    //e[cnt].w = w;
    e[cnt].ne = head[u];
    head[u] = cnt;
}

void tarjan(int u){
    dfn[u]=low[u]=++Time;
    vis[u]=1;sta[++top]=u;
    for(int i=head[u];i;i=e[i].ne){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u] , low[v]);
        }
        if(vis[v]){
            low[u] = min(low[u] , dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        tot++;
        //sum[tot]+=a[u];
        while(sta[top+1]!=u){
            int v = sta[top--];
            vis[v] = 0;
            sum[tot]+=a[v];
            summ[tot]++;
            g[v] = tot;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    int jidi=-10,diren=-10;
    for(int i=1;i<=tot;i++){
        jidi = max(jidi,summ[i]);
        diren = max(diren,sum[i]);
    }
    //printf("%d  %d\n",jidi,diren);
    for(int i=1;i<=n;i++){
        if(summ[g[i]]==jidi){
            for(int j=1;j<=n;j++){
                if(g[j]==g[i]){
                    printf("%d ",j);
                }
            }
            break;
        }
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        if(sum[g[i]]==diren){
            for(int j=1;j<=n;j++){
                if(g[j]==g[i]){
                    printf("%d ",j);
                }
            }
            break;
        }
    }
    return 0;
}

B. Borrowing books (two-point answer)

Topic description

 

input format

 

output format

 

Sample

sample input

6 3 
5
7
1
17
13
10

Sample output

 7

Data range and hints

  analyze

It is a two-point answer. In fact, this is a question model, the minimum value is maximized, and the maximum value is minimized (already implied to be a two-point answer),

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N];
int maxn;
int gd[N];
int aa;
int cnt;


bool cheak(int x){
    aa=0,cnt=0;
    for(int i=1;i<n;i++){
        aa+=gd[i];
        if(aa>=x){
            cnt++;
            aa=0;
        }
    }
    if(cnt+1>=m){
        return true;
    } else return false;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        maxn = max(maxn,a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++){
        gd[i] = a[i+1]-a[i];
    }
    int l=0,r=maxn;
    while(l<=r){
        if(r-l==1){
            if(cheak(r)){
                l=r;
            }
            break;
        }
        int mid = (l+r)/2;
        if(cheak(mid)){
            l=mid;
        } else {
            r=mid;
        }
    }
    printf("%d",l);
}

C. Searching for treasures in the city (tree...tree dp?)

Topic description

 

input format

 

output format

 

Sample

sample input

8 4 
1 2 
1 3 
2 4 
2 5 
3 6 
3 7 
6 8 
2 5 1 4 6 1 1 10 

Sample output

27

Data range and hints

  analyze

Eh... This question is a tree dp, but we have to consider the problem of the portal, what should I do! ! ! tsk tsk tsk! ! ! ! We build a virtual point, which is n+1. Because the situation is uncertain, we can enumerate each point, let each point do a right subtree that requires point n+1, and then search hard with dfs. xiu, but pay attention to the return of a point after the virtual point.

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 50;
int ls[N],rs[N],fa[N];//left and right son, and father array
int n,key,a[N];
int x,y,ans;

int dfs(int x,int k){
    if(x==0)return 0;
    if(k==1)return a[x];
    int now = 0;
    for(int i=0;i<k;i++){//The keys are enumerated from one, thinking that they may be used to open the left subtree and the right subtree
        now = max(dfs(ls[x],i)+dfs(rs[x],k-i-1)+a[x],now);
    }
    return now;
}

int main(){
    scanf("%d%d",&n,&key);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&x,&y);
        if(!ls[x])ls[x] = y;
        else rs[x] = y;
        fa[y]=x;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ls[n+1] = 1;
    for(int i=2;i<=n;i++){
        rs[n+1] = i;
        if(ls[fa[i]]==i){//if left son
            ls[fa[i]]=0;
            ans = max(ans,dfs(n+1,key+2));
            ls[fa[i]] = i;
        }
        else {//right son
            rs[fa[i]] = 0;
            ans = max(ans,dfs(n+1,key+2));
            rs[fa[i]] = i;        
        }
    }
    printf("%d\n",ans);
    return 0;
}

D. MM does not cry (dp)

Topic description

 

input format

 

output format

 

Sample

sample input

4
3
2 2
5 8
6 1
8 7

Sample output

56

  analyze

Saw this and thought...

This is similar to turning off the street lights in Luogu. We define the array f[ i ][ j ][ 1(0) ] as the minimum cost to stop at i(0) or stop at j(1) after processing i to j, then

 

 

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,v,x;
int f[N][N][2];
int sum[N];
struct node{
    int x;
    int w;
}e[N];

bool cmp(node a,node b){
    return a.x<b.x;
}

int main(){
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&e[i].x,&e[i].w);
    }
    /*v = e[v].x;//Adding or not is the same here
    //printf("%d",x);//Because the data in the question is incremental
    sort(e+1,e+1+n,cmp);//Although not saying
    for(int i=1;i<=n;i++){//Don't ask how I know
        if(v==e[i].x){//Asking is a crooked hit
            v=i;
        }
    }*/
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1]+e[i].w;
    }
    memset(f,0x3f,sizeof(f));
    f[v][v][1]=f[v][v][0] = 0;
    for(int l = 2;l <= n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j = i+l-1;
            if(i < x-l+1)continue;
            //if(j>n)break;
            int n1=sum[i]+sum[n]-sum[j];
            int n2=sum[i]+sum[n]-sum[j];
            int n3=sum[i-1]+sum[n]-sum[j-1];
            int n4=sum[i-1]+sum[n]-sum[j-1];
            f[i][j][0] = min(f[i+1][j][0]+n1*(e[i+1].x-e[i].x),f[i+1][j][1]+n2*(e[j].x-e[i].x));
            f[i][j][1] = min(f[i][j-1][0]+n3*(e[j].x-e[i].x),f[i][j-1][1]+n4*(e[j].x-e[j-1].x));
        }
    }
    printf("%d\n",min(f[1][n][0],f[1][n][1]));
    return 0;
}

Congratulations on finding a pig that is taking a bath, wait a moment, the analysis will come soon

Since this is a daily blog, there may not be too much analysis (mainly because of lack of time), so paste it Coach Blog

It's a bit of a visit.

Posted by david4ie on Tue, 31 May 2022 10:59:34 +0530