2019 ICPC Asia Yinchuan regional (water problem solution)

B. So Easy

Mr. G invents a new game whose rules are given as follows.

Firstly, he has a n \times nn×n matrix, all elements of which are 00 initially. Then, he follows up with some operations: in each time he chooses a row or a column, and adds an arbitrary positive integer to all the elements in the selected row or column. When all operations have been finished, he hides an element in the matrix and the element is modified to -1−1.

Now given the final matrix, you are asked to find out what the hidden element should be before the very last hiding operation.

Input

The first line contains a single integer n(2≤n≤1000).

Next nn lines represent the matrix after the operations. Each element in the matrix satisfies −1≤a _i,j​≤1000000, and exactly one element is -1.

Output
Output a single integer, the hidden element.

The sample input
3
1 2 1
0 -1 0
0 1 0
Sample output
1

The question

  n×n The numerical matrix of , The initial values are all 0, You can add a positive integer to each row or column at the same time , Get the final matrix , Ask you the value of a certain point （ Input is -1 The point of ）

Ideas

• find -1 Location of points (a_i,a_j), Record , And reassign this point to 0
• Operate first , Find the minimum value of each line , Subtract this minimum from each number , Note that when looking for the minimum , To avoid (a_i,a_j) spot
• Similarly, perform column operations
• Output -a[a_i][a_j]

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 1010;
int a[maxn][maxn];
int main(void)
{
    
    int n;
    int ai,aj;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=n;j++){
    
            scanf("%d",&a[i][j]);
            if(a[i][j]==-1){
    
                ai = i;aj = j;
                a[i][j] = 0;
            }
        }
    }
    int _min;
    for(int i=1;i<=n;i++){
    
        _min = INF;
        for(int j=1;j<=n;j++){
    
            if(i!=ai||j!=aj){
    
                _min = min(_min,a[i][j]);
            }
        }
        for(int j=1;j<=n;j++){
    
            a[i][j] -= _min;
        }
    }
    for(int j=1;j<=n;j++){
    
        _min = INF;
        for(int i=1;i<=n;i++){
    
            if(i!=ai||j!=aj)    _min = min(_min,a[i][j]);
        }
        for(int i=1;i<=n;i++){
    
            a[i][j] -= _min;
        }
    }
    printf("%d\n",-a[ai][aj]);
    return 0;
}

I Base 62

As we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of 2 to 62. The symbols ‘0’ – ‘9’ represent zero to nine, and ‘A’ – ‘Z’ represent ten to thirty-five, and ‘a’ – ‘z’ represent thirty-six to sixty-one. Now you need to convert some integer z in base xx into base y.

Input
The input contains three integers x, y (2≤x,y≤62) and z (0≤z<x¹²⁰), where the integer z is given in base x.

Output
Output the integer zz in base yy.

The sample input
16 2 FB
Sample output
11111011

The question

Put one x Hexadecimal number z Turn it into y Hexadecimal number , Output note ：0 ~ 9 Corresponding ’0’ ~ 9’,10 ~ 35 Corresponding ‘A’ ~ ‘Z’,36 ~ 61 Corresponding ‘a’ ~ ‘z’.

Ideas

Hexadecimal conversion template topic ：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 10000010;
char str[maxn],another[maxn];
int ten[maxn];
int switchToTen(int m)
{
    
    int i,j,len,k,c;
    len = strlen(str);
    k = 1;
    memset(ten,0,sizeof(ten));
    for(int i = 0;i<len;i++){
    
        for(int j=0;j<k;j++){
    
            ten[j] *= m;
        }
        if(str[i]>='0'&&str[i]<='9'){
    
            ten[0] += str[i]-'0';
        }
        else if(str[i]>='A'&&str[i]<='Z'){
    
            ten[0] += str[i]-'A'+10;
        }
        else if(str[i]>='a'&&str[i]<='z'){
    
            ten[0] += str[i]-'a'+36;
        }
        for(int j=c=0;j<k;j++){
    
            ten[j] += c;
            if(ten[j]>=10){
    
                c = ten[j] / 10;
                ten[j] %= 10;
            }
            else    c = 0;
        }
        while(c){
    
            ten[k++] = c % 10;
            c /= 10;
        }
    }
    int temp;
    for(int i=0,j=k-1;i<j;i++,j--){
    
        temp = ten[i];
        ten[i] = ten[j];
        ten[j] = temp;
    }
    return k;
}
void switchToAnother(int k,int n)
{
    
    int sum,r,t,d;
    sum = 1;
    r = 0;
    memset(another,0,sizeof(another));
    while(sum){
    
        sum = 0;
        for(int i=0;i<k;i++){
    
            d = ten[i] / n;
            sum += d;
            if(i==k-1){
    
                t = ten[i] % n;
                if(t>=0&&t<=9){
    
                    another[r] = t+'0';
                }
                else if(t>=10&&t<=35){
    
                    another[r] = t-10+'A';
                }
                else   another[r] = t-36+'a';
                r++;
            }
            else{
    
                ten[i+1] += ten[i]%n * 10;
            }
            ten[i] = d;
        }
    }
    for(int i=r-1;i>=0;i--){
    
        printf("%c",another[i]);
    }
    printf("\n");
}
int main()
{
    
    int m,n,k;
    cin>>m>>n>>str;
    k = switchToTen(m);
    switchToAnother(k,n);

    return 0;
}

G. Pot!!

The sample input ：
5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2
MULTIPLY 2 5 5
MAX 3 5
Sample output ：
ANSWER 1
ANSWER 2

The question

Give a paragraph 1~n The range of (tree), Their initial value is 1, There are two operations ：

• MULTIPLY l r x operation ： Give Way [l,r] Multiply each number in by x (2<=x<=10)
• MAX l r operation ： Output [l,r] Maximum m,tree[i] % p^m = 0 && tree[i] % p^m+1 != 0,i∈[l,r],p Is any prime number .

Ideas

The problem of interval modification and query is obviously the problem of segment tree , there MAX Operation is like a factorization operation .
Prime table , Then decompose each number prime factor ？？
Let's think about ,x Value range of [2,10], Then the prime factor in these intervals must be <=10 Of , So that is 2 3 5 7 These four numbers
Then maintain the line segment tree 2 3 5 7 These four are worth mx, then MAX Is the largest query mx That's it .

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 100010;
int p[maxn];
int n,m;
char cmd[10];
int x,y,z;
struct node{
    
    int l,r,mx;
    int mx2,la2;
    int mx3,la3;
    int mx5,la5;
    int mx7,la7;
}a[maxn<<2];
void update(int k)
{
    
    a[k].mx2 = max(a[k<<1].mx2,a[k<<1|1].mx2);
    a[k].mx3 = max(a[k<<1].mx3,a[k<<1|1].mx3);
    a[k].mx5 = max(a[k<<1].mx5,a[k<<1|1].mx5);
    a[k].mx7 = max(a[k<<1].mx7,a[k<<1|1].mx7);
    a[k].mx = max(a[k<<1].mx,a[k<<1|1].mx);
}
void pushdown(int k)
{
    
    if(a[k].la2){
    
        a[k<<1].la2 += a[k].la2;
        a[k<<1|1].la2 += a[k].la2;
        a[k<<1].mx2 += a[k].la2;
        a[k<<1|1].mx2 += a[k].la2;
        a[k].la2 = 0;
    }
    if(a[k].la3){
    
        a[k<<1].la3 += a[k].la3;
        a[k<<1|1].la3 += a[k].la3;
        a[k<<1].mx3 += a[k].la3;
        a[k<<1|1].mx3 += a[k].la3;
        a[k].la3 = 0;
    }
    if(a[k].la5){
    
        a[k<<1].la5 += a[k].la5;
        a[k<<1|1].la5 += a[k].la5;
        a[k<<1].mx5 += a[k].la5;
        a[k<<1|1].mx5 += a[k].la5;
        a[k].la5 = 0;
    }
    if(a[k].la7){
    
        a[k<<1].la7 += a[k].la7;
        a[k<<1|1].la7 += a[k].la7;
        a[k<<1].mx7 += a[k].la7;
        a[k<<1|1].mx7 += a[k].la7;
        a[k].la7 = 0;
    }
    a[k<<1].mx = max(max(a[k<<1].mx2,a[k<<1].mx3),max(a[k<<1].mx5,a[k<<1].mx7));
    a[k<<1|1].mx = max(max(a[k<<1|1].mx2,a[k<<1|1].mx3),max(a[k<<1|1].mx5,a[k<<1|1].mx7));
}
void build(int k,int l,int r)
{
    
	a[k].l = l;a[k].r = r;
	a[k].la2 = a[k].la3 = 0;
	a[k].la5 = a[k].la7 = 0;
	a[k].mx2 = a[k].mx3 = 0;
	a[k].mx5 = a[k].mx7 = 0;
	if(l==r)    return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	update(k);
}
void changeSegment(int k,int l,int r,int x2,int x3,int x5,int x7)
{
    
	if(a[k].l>=l&&a[k].r<=r){
    
        a[k].la2 += x2;a[k].la3 += x3;
        a[k].la5 += x5;a[k].la7 += x7;
        a[k].mx2 += x2;a[k].mx3 += x3;
        a[k].mx5 += x5;a[k].mx7 += x7;
        a[k].mx = max(max(a[k].mx2,a[k].mx3),max(a[k].mx5,a[k].mx7));
		return;
	}
	pushdown(k);
	int mid=(a[k].l+a[k].r)>>1;
	if(r>mid) changeSegment(k<<1|1,l,r,x2,x3,x5,x7);
	if(l<=mid) changeSegment(k<<1,l,r,x2,x3,x5,x7);
	update(k);
}
int query(int k,int l,int r)
{
    
	if(a[k].l>=l&&a[k].r<=r) return a[k].mx;
    pushdown(k);
	int x = 0;
	int mid=(a[k].l+a[k].r)>>1;
	if(r>mid) x = max(x,query(k<<1|1,l,r));
	if(l<=mid) x = max(x,query(k<<1,l,r));

	return x;
}
int main(void)
{
    
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++){
    
        scanf("%s",cmd);
        if(cmd[1]=='U'){
    
            scanf("%d%d%d",&x,&y,&z);
            int x2,x3,x5,x7;
            x2 = x3 = x5 = x7 = 0;
            if(z==2) x2++;
            else if(z==3)   x3++;
            else if(z==4)   x2 += 2;
            else if(z==5)   x5++;
            else if(z==6)   x2++,x3++;
            else if(z==7)   x7++;
            else if(z==8)   x2 += 3;
            else if(z==9)   x3 += 2;
            else if(z==10)  x2++,x5++;
            changeSegment(1,x,y,x2,x3,x5,x7);
        }
        else{
    
            scanf("%d%d",&x,&y);
            printf("ANSWER %d\n",query(1,x,y));
        }
    }
    return 0;
}