8 intensive training simulation (forgetting the board)

A. Ticketing system

Title Description

Input format

Output format

Example

sample input

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

sample output

YES
YES
NO
NO 

analysis

This problem is a segment tree interval modification and interval query, but this problem n2 can pass!!!! Because I am extremely lazy, I will not write the line segment tree, but directly post the violent code. This code is too dangerous, and it is easy to TLE. I still find time to play the line segment tree

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 6e4+10;
int c,s,r;
int o,d,n;
int tree[N];

int main(){
    scanf("%d%d%d",&c,&s,&r);
    for(int i = 1;i <= r;i++){
        scanf("%d%d%d",&o,&d,&n);
        int maxn = -10;
        for(int j = o;j <= d-1;j++){
            maxn = max(maxn,tree[j]);
            if(s - maxn < n)break;
        }
        if(s - maxn >= n){
            printf("YES\n");
            for(int j = o;j <= d-1;j++){
                tree[j] += n;
            }
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

B. Queue up

Title Description

Input format

Output format

Example

sample input

5 3

sample output

15

Data range and tips

analysis

Xiaohua, hehe, my English teacher was called "Xiaohua" before my class was divided. Alas, it's far away.

What surprised me was that the problem was recursion. I thought it was a sort of merge, reverse order, tree array.

In the sequence composed of 1 ~ n, if it is in ascending order, then the reverse pair is 0. If it is in descending order, then the reverse pair is 1+2+3+4++ N-1.

Add a number, then the maximum number of newly generated reverse pairs is i-1.

Therefore, we define f[i][j], which represents the number of schemes when the number of I inverse pairs of 1~i is J.

So f[i][j] = f[i-1][j]+f[i-1][j-1]+f[i-1][j-1]++ F[i-1][j-i+1] (1)

Similarly: f[i][j-1] = f[i-1][j-1]+f[i-1][j-2]+f[i-1][j-3]++ F[i-1][j-i] (2)

From (1) - (2), f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1].

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
const int mod = 1799999;
long long f[N][N*N];
int n,k;
int sum;

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++){
        f[i][0] = 1;
    }
    for(int i = 1;i <= n;i++){
        sum += (i-1);
        for(int j = 1;j <= k;j++){
            if(j > sum)break;
            f[i][j] = (f[i-1][j] + f[i][j-1])%mod;
            if(i <= j){//Judgment, not yes j-i Less than zero
                f[i][j] = (f[i][j] - f[i-1][j-i] + mod)%mod;//Take mold everywhere
            }
        }
    }
    printf("%lld\n",f[n][k]%mod);
    return 0;
}

C. Graceful value

Title Description

Input format

Output format

Example

sample input

8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8

sample output

7
3
1
3
5
3
7
3

Data range and tips

analysis

In fact, I think this question is more metaphysical. I really understand it, but I don't know how to say it very clearly. Then try to say it.

If the i-th number ai can become the median, the number larger than it must be the same as the number smaller than it in its range, so we scan from ai to the left and right, encounter sum++ larger than it, sum--smallerthan it, and then record with the number as the coordinate.

After that, if there are sum on the left than him, then there are -sum on the right than him, so we'll find the largest one

Code

xiu

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
int n;
int a[N];
int l[N],r[N],sum;
int maxn[N];
int Q;
int L,R;
void pre(){
    for(int i = 1;i <= n;i++){
        memset(l,-1,sizeof(l));
        memset(r,-1,sizeof(r));
        l[n] = 0,r[n] = 0;
        sum = 0;
        for(int j = i-1;j >= 1;j--){
            if(a[j] > a[i])sum++;
            if(a[j] <= a[i])sum--;
            l[sum+n] = i - j;
        }
        sum = 0;
        for(int j = i+1;j <= n;j++){
            if(a[j] >= a[i])sum++;
            if(a[j] < a[i])sum--;
            r[sum+n] = j - i;
        }
        for(int j = 1-i;j <= i-1;j++){
            if(l[j+n]>=0&&r[n-j]>=0)
                maxn[i] = max(maxn[i],l[j+n]+r[n-j]+1);
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    pre();
    scanf("%d",&Q);
    for(int i = 1;i <= Q;i++){
        scanf("%d%d",&L,&R);
        int ans = -10;
        for(int j = L;j <= R;j++){
            ans = max(ans , maxn[j]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

D. Shortest path

Title Description

 

 

Input format

Output format

Example

sample input

4 4
1 2 1
2 3 2
1 3 2
3 4 1
2
2 4
1 3

sample output

3
2

Data range and tips

analysis

This is an annoying thing. The source of this problem is Luogu P5236 , a lot of problem solutions, then go and see. I don't know yet.

Code

#include <bits/stdc++.h>
const int maxn=100005+100,maxm=300005;//Because there are new edges, the maximum new edge is n,A big ring
struct Node{
    int to,w,next;
}e[maxm];
int len=1,head[maxn],vis[maxn],dis[maxn],dep[maxn],f[maxn][14];
int n,m,Time,dfn[maxn];
int cnt,Circle[maxm],st[maxn],rd[maxn],belong[maxn],Girth[maxn];
void Insert(int x,int y,int z){//The number of edges starts from 2    
    e[++len].to=y;e[len].w=z;e[len].next=head[x];head[x]=len;
}
void spfa(int x) {
    memset(dis,0x3f,sizeof dis);
    std::queue<int> q; q.push(x);dis[x]=0;
    while(!q.empty()) {
        int u=q.front(); q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v])
                    vis[v]=1,q.push(v);
            }
        }
    }
}
void Circ(int x,int y) {//y Is the earliest access node on the ring
    if(x==y) return;
    belong[x]=cnt;//Record node x Which ring does it belong to
    Insert(y,x,0);//Just build y reach x Because lca Hour y Hour x Parent node of
    Circle[st[x]]=Circle[st[x]^1]=1;//Upper left mark of edge on ring
    Girth[cnt]+=e[st[x]].w;//Record the length of the ring
    Circ(e[st[x]^1].to,y); 
}
void dfs(int x) {
    dfn[x]=++Time;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(i!=(st[x]^1)&&i<=m*2+1){//Number greater than 2*m+1 The edge of is the edge on the new ring
            if(!dfn[v]){
                rd[v]=rd[x]+e[i].w;//Record in search order v Distance to root node 1
                st[v]=i;//Record with v Number of end branch edges
                dfs(v);
            } 
            else if(dfn[v]<dfn[x]){//Simple ring appears
                Girth[++cnt]=e[i].w;//cnt Record ring number
                Circ(x,v);//Processing ring,v Is the earliest access point on the ring
            } 
        }
    }
}
void dfs2(int u) {
    for(int i=1;(1<<i)<=dep[u];++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!Circle[i] && !dep[v]){//edge i Not on ring v Not accessed
            f[v][0]=u;//Multiply initialization
            dep[v]=dep[u]+1;
            dfs2(v);
        }
    }
}
int Query(int u,int v) {
    if(dep[u]<dep[v])std::swap(u,v);
    int a=u,b=v,len=dep[u]-dep[v],k=0;
    while(len){
        if(len & 1) u=f[u][k];
        ++k;len>>=1;
    }
    if(u==v)return dis[a]-dis[b];
    for(int i=13;i>=0;i--)
        if(f[u][i]!=f[v][i]){
            u=f[u][i];v=f[v][i];
        }
    if(belong[u] && belong[u]==belong[v]) {
        int r=abs(rd[u]-rd[v]);//u and v Distance in the ring in search order
        return dis[a]-dis[u]+dis[b]-dis[v]+std::min(r,Girth[belong[u]]-r);
    }
    return dis[a]+dis[b]-2*dis[f[u][0]];
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);Insert(y,x,z);
    }
    spfa(1),dfs(1),dep[1]=1,dfs2(1);
    int q;scanf("%d",&q);
    while(q--){
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",Query(x,y));
    }
    return 0;
}

 

Posted by Wolfsoap on Mon, 30 May 2022 06:21:49 +0530