2019 国际大学生程序设计竞赛（ICPC）亚洲区域赛（银川） 7题

补题链接：https://codeforces.com/gym/104021
难得VP打出这么好的成绩，虽然是有争议的西部枢纽银川站，虽然没能早生几年。。。。

N.Fibonacci Sequence

题意：

• 输出斐波那契数列的前5项

思路：

• 输入没有，输出是前五项，直接样例复制粘贴输出就过了。

#include
using namespace std;

int main(){
    cout<<"1 1 2 3 5\n";
    return 0;
}
1
2
3
4
5
6
7

B.So Easy

题意：

• 给出一个n*n的矩阵，初始全为0。每次可以选择任意行或任意列，给整行+1。
• 若干次操作后得到一个全新的矩阵。
• 将该矩阵的某个位置藏起来（设为-1），并把该矩阵作为输入给你，求那个藏起来的值是多少。

思路：

• 不难发现任意二元子矩阵的对角线和是相等的。 将4个点分成两组，不管加哪一行还是哪一列，刚好每组都会恰好有1个点被加到1次。
• 所以答案就是找个包含-1的随便矩阵，然后a[x,y] = a[x+1,y]+a[x,y+1]-a[x+1,y+1]。
• 考虑到4个顶点的位置，所以分一下类。开始没关流同步，TLE5了一发。

#include
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>a[i][j];
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            if (a[i][j] == -1) {
                if (i > 1 && j > 1) {
                    a[i][j] = a[i - 1][j] + (a[i][j - 1] - a[i - 1][j - 1]);
                } else if (i > 1 && j < n) {
                    a[i][j] = a[i - 1][j] + (a[i][j + 1] - a[i - 1][j + 1]);
                } else if (i < n && j > 1) {
                    a[i][j] = a[i + 1][j] + (a[i][j - 1] - a[i + 1][j - 1]);
                } else {
                    a[i][j] = a[i + 1][j] + (a[i][j + 1] - a[i + 1][j + 1]);
                }
                cout << a[i][j] << '\n';
                return 0;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

I.Base62

题意：

• 给出一个x进制下的数z，将它转为y进制输出。（0-9，大写，小写字母依次表示到62进制）

思路：

• 先转10进制，再转y进制，直接输出即可。
• 120次方需要手写高精度，直接python大整数即可。
• 开始0没特判，WA12了一发。

x, y, z = input().split()
x = int(x); y = int(y)
tmp = 0
for i in z :
    if i >= '0' and i <= '9':
        tmp = tmp * x +  int(i)
    elif i >= 'A' and i <= 'Z' :
        tmp = tmp * x + 10 + ord(i) - 65
    else :
        tmp = tmp * x + ord(i) + 36 - 97
res = ""
while tmp > 0 :
    tp = tmp % y
    tmp = tmp // y
    if (tp <= 9) : res = str(tp) + res
    elif (tp < 36) : res = chr(tp - 10 + 65) + res
    else : res = chr(tp - 36 + 97) + res
if res == "" : print(0)
else : print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

G.Pot!!

题意：

• 定义函数pop_p(n) = m，其中p为n的因数，m表示该因数的个数。
• 题目有两种操作。
  操作1：给区间[l, r]都乘上一个x（x<10）
  操作2：求区间内任意一个数的因数个数最大的个数。例如对于ai的所有因数出现次数分别为b1, b2, b3, ,bn， 取max{b1。。。。bn}。 然后再取max{al。。。。ar}。
• n<1e5, 操作q<1e5

思路：

• 发现乘的数x属于1到10， 而1-10内的质因数只有2,3,5,7四种情况。加上数组初始值为1，相当于最后任意情况下的数组，每个值都只有2357这四个质因数。
• 区间操作和区间查询不难想到线段树，加上查询的时候查的只有质因数个数的最大值，我们不难想到维护4个线段树，分别表示2,3，5,7的区间最大值。 修改的时候对于输入的x质因数分解，然后给对应的线段树做区间加即可。

#include 
using namespace std;
#define int long long 
const int N = 1000010;
int n, m, k;

int tree[5][N];
int lazy[5][N];
void push_down(int id, int l, int r, int u) {
    int mid = (l + r) >> 1;
    tree[id][u << 1] += lazy[id][u];
    lazy[id][u << 1] += lazy[id][u];
    tree[id][u << 1 | 1] += lazy[id][u];
    lazy[id][u << 1 | 1] += lazy[id][u];
    lazy[id][u] = 0;
}
void update(int id , int l, int r, int u, int L, int R, int v) {
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        tree[id][u] += v;
        lazy[id][u] += v;
        return;
    }
    if (lazy[id][u]) {
        push_down(id, l, r, u);
    }
    int mid = (l + r) >> 1;
    update(id, l, mid, u << 1, L, R, v);
    update(id, mid + 1, r, u << 1 | 1, L, R, v);
    tree[id][u] = max(tree[id][u << 1], tree[id][u << 1 | 1]);
}
int query(int id, int l, int r, int u, int L, int R) {
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) {
        return tree[id][u];
    }
    if (lazy[id][u]) {
        push_down(id, l ,r , u);
    }
    int mid = (l + r) >> 1;
    return max(query(id, l, mid, u << 1, L, R), query(id, mid + 1, r, u << 1 | 1, L, R));
}
void solved() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        string opr;
        int l, r;
        cin >>opr >> l >> r;
        if (opr == "MULTIPLY") {
            int x;
            cin >> x;
            while (x % 2 == 0) update(0, 1, n, 1, l, r, 1), x /= 2;
            while (x % 3 == 0) update(1, 1, n, 1, l, r, 1), x /= 3;
            while (x % 5 == 0) update(2, 1, n, 1, l, r, 1), x /= 5;
            while (x % 7 == 0) update(3, 1, n, 1, l, r, 1), x /= 7;
        } else {
            int maxn = 0;
            for (int i = 0; i <= 3; i ++ ) {
                maxn = max(maxn, query(i, 1, n, 1, l, r));
            }
            cout <<"ANSWER " <<  maxn << '\n';
        }
    }
}

signed main() {
    int t = 1;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> t;
    for (int i = 1; i <= t; i ++ ) {
        solved();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

F.Function!

题意：

• 定义fa(x)=a^x，f-1a(x)为fa(x)的反函数。
• 求${\sum }_{a=2}^n(a{\sum }_{b=a}^n\lfloor f_a^{-1}(b)\rfloor \lceil f_b^{-1}(a)\rceil )$ % 998244353 的结果。

思路：

• 输入一个数，输出一个数，n的范围是1e12，盲猜结论题，打了波表，发现样例都打不出来。
• fa(x)的反函数就是log(a)b， 且a<=b对原式必成立，所以log(b)a肯定是介于0与1之间的，向上取整后必然等于1。
  此时去掉这部分修改后的打表成功了，虽然还是没找到什么规律，但是发现做两次差分后，后面的值都是成段出现的，意识到左边的部分，loga(b)他其实是可以用数论分块做的，因为b在一段区间内，log(a)b的值都是相同的。
• 但是复杂度还是不够，进一步推式子，发现当a>1e6的时候，log1e6(1e12)也才等于2，意味着左边的式子log(a)b也恒等于1了，此时就变成了一个等差数列求和公式，即可求出来。
• 而对于<1e6（或者说根号n）的部分，第二层循环跑分块的复杂度只有十几，乘上外面的1e6，是可以通过的。

#include 
using namespace std;
#define int long long 
const int N = 1000010;
int n, m, k;
const int mod = 998244353;
int Qpow(int x, int k) {
    int res = 1;
    while (k) {
        if (k % 2) res = (res * x) % mod;
        x = (x * x) % mod;
        k >>= 1; 
    } 
    return res;
}
int get_presum(int x) {
    x = x % mod;
    int len = n % mod;
    int part1 = len % mod * (1 + x) % mod * x % mod * Qpow(2, mod - 2) % mod;
    int part2 = (2 * x % mod + 1) * (x + 1) % mod * x % mod * Qpow(6, mod - 2) % mod;
    int part3 = (1 + x) % mod * x % mod * Qpow(2, mod - 2) % mod;
    // cout << part1 << " " << part2 << ' ' << part3 << '\n';
    return (part1 - part2 + part3) % mod; 
}
void solved() {
    cin >> n;
    int res = 0;
    for (int i = 2; i * i <= n; i ++ ) {
        int tmp = 1;
        int sum = 0;
        for (int j = i; j <= n; j *= i) {
            sum = (tmp * (min(n + 1, j * i) - j) % mod + sum) % mod;
            tmp ++;
        }
        res = (res + i * sum % mod) % mod;
    }
    int r = sqrt(n);
    res = (res + get_presum(n) - get_presum(r) + mod) % mod;
    cout << res << '\n';
}

signed main() {
    int t = 1;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> t;
    for (int i = 1; i <= t; i ++ ) {
        solved();
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

K.Largest Common Submatrix

题意：

• 给出两个n*m的矩阵A和B，矩阵的值由1-nm的排列打乱后组成（不重复）。
• 求矩阵A和矩阵B的最大公共子矩阵。
• n,m<1000

思路：

• 类比全为排列的最长公共子串的复杂度最优的做法为， 将序列A映射到序列B，然后对序列B做最长上升子序列。本题也可以将矩阵A映射到矩阵B，（不难证明在A和B中同时交换任意两个数字的位置时， 新的两个矩阵的LCS对结果是不会产生影响的。），即将矩阵A修改为123456.。。。。nm的形式，然后B对应的修改为某个新的随机矩阵。
• 考虑映射后的矩阵B，要找他和A的最大公共子矩阵，只需要满足某个值向上延伸都是-m的情况，向左延伸都是-1的情况。按照这种方法向四个方向蔓延出去，能取到的矩阵面积最大即可。此时枚举点和方向的复杂度为O(n^4）。
• 不难递推预处理出top[i][j]表示第i行第j个从当前往上蔓延能走到的最远的距离，对于某一行，这样的top[i]这一行数组就形成了一个柱状图求最大面积的情况，发现白书里做过，是POJ2559原题，可以单调栈做。
  参考：https://gwj1314.blog.csdn.net/article/details/81513728
• 然后写完没过样例，发现有点不一样的地方是，直接按没列跑单调栈，没有考虑到行的情况，所以在行上再做一个递推，对行上的各个区间，分别跑单调栈求最大面积（相当于遇到断掉的时候就清空栈一次），然后就AC了。

#include 
using namespace std;
#define int long long 
const int N = 1000010;
int n, m, k;
const int mod = 998244353;
pair<int, int> pos[N];
int mrxa[1002][1992], mrxb[1002][1090];
int top[1010][1010];
int vis[N];
void solved() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> mrxa[i][j];
            vis[mrxa[i][j]] = (i - 1) * m + j;
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> mrxb[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            mrxb[i][j] = vis[mrxb[i][j]];
        }
    }
    int maxn = 0;
    stack<int> st;
    for (int i = 1; i <= n; i ++ ) {
        st.push(0);
        int last[1002];
        for (int i = 1; i <= m; i ++ ) last[i] = m + 1; 
        for (int j = 1; j <= m; j ++ ) {
            if(mrxb[i-1][j]+m==mrxb[i][j]){
                top[i][j] = top[i-1][j]+1;
            }else{
                top[i][j] = 1;
            }
            if (mrxb[i][j - 1] + 1 != mrxb[i][j]) {
                while (st.top() != 0) {
                    maxn = max(maxn, (j - last[st.top()]) * top[i][st.top()]);
                    st.pop();
                }
            }
            last[j] = j;
            while (top[i][j] <= top[i][st.top()]) {
                maxn = max(maxn, (j - last[st.top()]) * top[i][st.top()]);
                last[j] = min(last[st.top()], last[j]);
                st.pop();
            }
            st.push(j);
        }
        while (st.top() != 0) {
            maxn = max(maxn, (m + 1 - last[st.top()]) * top[i][st.top()]);
            st.pop();
        }
    }
    cout << maxn << '\n'; 
}

signed main() {
    int t = 1;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> t;
    for (int i = 1; i <= t; i ++ ) {
        solved();
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73