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;
}