9 Training Simulation Match 12 (another day for brother Hu)

A. A crafty businessman

Title Description

Diao Cai receives a task to investigate a businessman's account book for the tax department to see if it is forged. The revenue of N months is recorded in the account book, and the revenue of the ith month is Ai(i=1,2,3...n-1,n). When Ai is greater than 0, it means a profit of Ai yuan this month. When Ai is less than 0, it means a loss of Ai yuan this month. The so-called total income over a period of time is the sum of the monthly income during that period.

Diao Cai's task was carried out in secret. In order to investigate the merchant's account books, she had to go to the merchant to work. She peeps into the account book while the merchant is away, but she can't steal it out. Every time she peeps into the account book, she can only see the income recorded in the account book for a certain period of time, and she can only remember the total income during that period. Now Diao Cha has peeked at the ledger for m times in total. Of course, she has remembered the total income in the period of M. your task is to judge whether the ledger is false according to the information she has remembered.

Input format

The first line is a positive integer W, where w < 100 indicates that there are w groups of data, i.e. w ledgers, which need your judgment.

The first row of each group of data is two positive integers n and m, where n < 100 and m < 1000 respectively represent the number of months of income recorded in the corresponding ledger and the number of times the ledger has been peeked.

The next line M represents the M pieces of information that Diao Qian remembered after peeking at the ledger for m times. Each information occupies one line, and there are three integers s, t and V, indicating that the total income from month s to month t (including month T) is v. here, it is assumed that s is always less than or equal to t.

Output format

Contains w rows, each of which is true or false.

Where the ith line is true if and only if the ith group of data, that is, the ith ledger is not false; The ith row is false if and only if the ith group of data, that is, the ith ledger is false.

Example

sample input

2 
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

sample output

true
false

analysis

This problem is called weighted union search set. It gives the interval sum of [l,r], which is equivalent to s[r] - s[l]. Once we know s[a]-a[b],s[b]-s[c], it is obvious that we can judge the "true or false bill" after making a [a,c]. Put each such information into a set, and maintain it with union search set, and maintain cha[l] = s[root]-s[l],char[r] = s[root] - s[r]. If l, If R is already in a set, you can directly query whether cha[l]-cha[r] is equal to w.

#include<bits/stdc++.h>
int fa[105],cha[105];  
int find(int x)
{  
    if(x!=fa[x])
    {
        int t=find(fa[x]);
        cha[x]+=cha[fa[x]];
        fa[x]=t;  
    }  
    return fa[x];  
}  
int main()  
{  
    int T,n,m,i,x,y,z,flag;  
    scanf("%d",&T);  
    while (T--) 
    {  
        flag=0;  
        scanf("%d%d",&n,&m);  
        for(i=0;i<=n;i++)
        {  
            fa[i]=i;  
            cha[i]=0;  
        }  
        for(i=1;i<=m;i++)  
        {  
            scanf("%d%d%d",&x,&y,&z);  
            x--;  
            if(find(x)!=find(y))  
            {  
                cha[fa[y]]=cha[x]-cha[y]-z;  
                fa[fa[y]]=fa[x];
            }  
            else  
            if(cha[x]-cha[y]!=z) flag=1;  
        }  
        if(flag==0) printf("true\n"); else printf("false\n");  
    }  
    return 0;  
}

B. Elephant and mouse

Title Description

The zoo in S country is an N*M grid diagram. The coordinates of the upper left corner are (1,1) and the coordinates of the lower right corner are (N,M). The little elephant is in the upper left corner of the zoo. He wants to go back to his home in the lower right corner to sleep, but there are some mice in the zoo, and the little elephant is afraid of mice. The mice in the zoo are different from each other. The fear value of a baby elephant is defined as the number of different mice he can see on his way home. If the current position of the little elephant is (x1,y1), the little elephant can see the mouse if and only if the position of the mouse (x2,y2) satisfies | x1-x2 | + | y1-y2 | < =1. Because the baby elephant is very sleepy, the baby elephant will only take the shortest way home, that is, the baby elephant will only go down or right. Now you need to help the little elephant determine a way home to minimize the fear of the little elephant.

Input format

The first line contains two integers separated by spaces, N and M.

Next, an N*M matrix represents the map of the zoo. Where A[i][j] refers to the number of rats in row I, column J. If A[i][j]=0, it means that there are no mice in the current position (mice may also exist in the elephant's home).

Output format

Output an integer indicating the minimum fear value of the route.

Example

sample input

3 9 
0 0 1 0 0 0 0 0 1 
1 1 1 1 1 1 0 1 0 
1 0 0 1 0 0 1 0 0

sample output

9

Data range and tips

For 10% data, 1<=n, m<=5.

For 100% data, 1<=n, m<=1000, 0<=aij<=100.

analysis

This is a dp question. Obviously, we can define the least mice we see in row i and column j, but what the elephant sees cannot be the same mouse, that is, the mouse in the same position only counts once. Since the elephant can only go down or to the right, we add it to indicate whether the elephant moves from the top or the left.

f[i][j][0] represents the least visible mouse that reaches row I and column J and is transferred from above.

f[i][j][1] indicates the least visible mouse that reaches row I and column J and is transferred from the left.

f[i][j][0]:

The status of f[i-1][j] is unknown, so there are classifications. If f[i][j][0], the rats (if any) on the lower left and right of a[i][j] should be included.

If f[i][j][1], the mouse on the right below a[i][j] should be included.

f[i][j][1]:

If f[i][j-1][0], the lower right side of a[i][j] shall be included.

If f[i][j-1][1], the lower left side and the right side of a[i][j] shall be included.

Then initialize it.

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int a[N][N];
int f[N][N][2];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    memset(f,0x3f,sizeof(f));
    f[1][1][1] = f[1][1][0] =  a[1][1] + a[1][2] + a[2][1];
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            f[i][j][0] = min(f[i][j][0],f[i-1][j][0]+a[i+1][j]+a[i][j-1]+a[i][j+1]);
            f[i][j][0] = min(f[i][j][0],f[i-1][j][1]+a[i+1][j]+a[i][j+1]);
            f[i][j][1] = min(f[i][j][1],f[i][j-1][1]+a[i-1][j]+a[i+1][j]+a[i][j+1]);
            f[i][j][1] = min(f[i][j][1],f[i][j-1][0]+a[i][j+1]+a[i+1][j]);
        }
    }
    printf("%d\n",min(f[n][m][1],f[n][m][0]));
    return 0;
}

C. Roads and routes

Title Description

Farmer John is investigating his milk sales plan in a new sales area. He wants to send the milk to T towns, numbered 1 to T. These towns are connected by R roads (numbered 1 to R) and routes (numbered 1 to P). Each road i or route i connects the town Ai to Bi at a cost of Ci.

For the road 0<=ci<=104, however, the cost of the route is magical, and the cost of CI may be negative. The road is two-way, from Ai to Bi, or from Bi to Ai. The call fee is Ci. However, different from the route, it can only be Ai to bi.

In fact, due to the recent rampant terrorism, some policies have been issued to ensure social harmony: if there is a route from Ai to Bi, it is impossible to return from Bi to Ai through some roads and routes. As FJ'S cows are recognized as awesome in the world, he needs to transport cows to every town. He wanted to find the cheapest way to send cows from the central town S to each town, or knew it was impossible.

Input format

The first line is an integer separated by four spaces: T, R, P, S;

Lines 2 to R+1: three spaces separated integers (representing a road): Ai, Bi and Ci;

Lines R+2 to R+P+1: integer separated by three spaces (representing a route): Ai, Bi and Ci.

Output format

Output line T, and line i represents the minimum cost to reach town i. if NO PATH is output.

Example

sample input

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10 

sample output

NO PATH 
NO PATH 
5 
0 
-95 
-100 

Data range and tips

For all data, 1<=t<=2.5 × 104,1<=r, p<=5 × 104,1<=ai, Bi, s<=t, ensure that for all roads, 0<=ci<=104, and for all routes, -104<=ci<=104

analysis

This is a simple shortest path, right? But we can use spfa to perform TLE, so we use a double ended queue for optimization (it will be stuck for more than 900 milliseconds).

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int t,r,p,s;
int x,y,w;
int dis[N],head[N],cnt;
bool vis[N];
deque<int>q;

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

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

void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    q.push_back(s);
    vis[s] = 1;
    dis[s] = 0;
    while(!q.empty()){
        int f = q.front();
        q.pop_front();
        vis[f] = 0;
        for(int i = head[f];i;i = e[i].ne){
            int v = e[i].to;
            if(dis[v] > dis[f] + e[i].w){
                dis[v] = dis[f] + e[i].w;
                if(!vis[v]){
                    if(!q.empty()&&dis[v]>=dis[q.front()])q.push_back(v);
                    else q.push_front(v);
                    vis[v] = 1;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d",&t,&r,&p,&s);
    for(int i = 1;i <= r;i++){
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    for(int i = 1;i <= p;i++){
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
    }
    spfa(s);
    for(int i = 1;i <= t;i++){
        if(dis[i] == 0x3f3f3f3f)printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
    return 0;
}

D. Sequence operation

Title Description

There is a sequence with length n on the paper, and the value of item i is ai.

Now little A wants to add A plus or multiplier between these numbers. Ask for different

Options,

What is the sum of all the answers?

Since the data range is large, the module of 1000000007 is output.

Input format

Enter an integer n in the first row to indicate the length of the sequence.

The next line contains n integers, and the nth integer represents the i-th item ai of the sequence.

Output format

One line, the answer is the result of modulo 1000000007.

Example

sample input

3
1 2 4

sample output

30

Data range and tips

At 30% of the data, 1 ≤ n ≤ 10,1 ≤ ai ≤ 10^5

For the other 30% of the data, 1 ≤ n ≤ 1000,ai=1

For 90% of data, 1 ≤ n ≤ 1000,1 ≤ ai ≤ 10^5

For 100% data, 1 ≤ 100000,1 ≤ ai ≤ 10^9

analysis

According to the preliminary judgment, this problem is to make trouble.

xiu

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
const ll mod =  1000000007;
ll n;
ll a[maxn],f[maxn],sum[maxn],s[maxn];
ll pai[maxn];
ll quickpow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1)ans = ans%mod*a%mod%mod;
        a=a%mod*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int main(){
    scanf("%lld",&n);
    scanf("%lld",&a[1]);
    pai[0]=1;
    pai[1]=a[1];
    for(int i=2;i<=n;++i){
        scanf("%lld",&a[i]);
        pai[i] = pai[i-1]%mod*a[i]%mod;
        s[i] = s[i-1]%mod*a[i]%mod+a[i]%mod*quickpow(2,i-2)%mod;
    }
    f[1]=a[1];
    sum[1]=f[1];
    for(int i=1;i<=n;++i){
        f[i] = sum[i-1]%mod+pai[i]%mod+s[i]%mod;
        sum[i] = sum[i-1]%mod+f[i]%mod;
    }
    printf("%lld\n",f[n]%mod);
    return 0;
}

 

Tags: shortest path dp

Posted by DirtySnipe on Thu, 02 Jun 2022 03:35:46 +0530