2019 ICPC Asia Yinchuan Regional（水题题解）

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.

样例输入
3
1 2 1
0 -1 0
0 1 0
样例输出
1

题意

  n×n的数值矩阵，初始数值全为 0，你可以对每一行或者每一列同时加某一正整数，得到最终矩阵，问你某一点的数值（输入是-1的点）

思路

• 找到 -1 点的位置(a_i,a_j)，记录，并把这个点重新赋值为 0
• 先进行行操作，找每一行的最小值，再每个数都减去这个最小值，注意的是最小值寻找时，要避开(a_i,a_j)点
• 同理进行列操作
• 输出 -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.

样例输入
16 2 FB
样例输出
11111011

题意

把一个 x 进制数 z 转化成 y 进制数，输出注意：0 ~ 9对应’0’ ~ 9’，10 ~ 35对应 ‘A’ ~ ‘Z’，36 ~ 61对应 ‘a’ ~ ‘z’。

思路

进制转换的模板题目：

#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!!

样例输入：
5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2
MULTIPLY 2 5 5
MAX 3 5
样例输出：
ANSWER 1
ANSWER 2

题意

给以一段 1~n 的区间(tree)，他们的初始值为 1，有两个操作：

• MULTIPLY l r x 操作：让[l,r] 内的每个数乘以 x (2<=x<=10)
• MAX l r 操作：输出[l,r]的最大 m，tree[i] % p^m = 0 && tree[i] % p^m+1 != 0，i∈[l,r]，p是任意素数。

思路

区间修改和查询问题很明显是线段树问题，这里的MAX操作像是一个质因分解操作。
打素数表，然后对每一个数质因分解？？
我们想一下，x的取值范围[2,10]，那么这些区间里的质因子一定是<=10的，那么就是 2 3 5 7 这四个数了
那么就线段树维护 2 3 5 7 这四个值得 mx，然后MAX是查询最大mx就行了。

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