文章目录

• • • N.Fibonacci Sequence
    • B.So Easy
    • I.Base62
    • G.Pot!!
    • F.Function!
    • K.Largest Common Submatrix

补题链接：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;
}

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

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) - 65else :tmp = tmp * x + ord(i) + 36 - 97
res = ""
while tmp > 0 :tp = tmp % ytmp = tmp // yif (tp <= 9) : res = str(tp) + reselif (tp < 36) : res = chr(tp - 10 + 65) + reselse : res = chr(tp - 36 + 97) + res
if res == "" : print(0)
else : print(res)

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

F.Function!

题意：

• 定义fa(x)=a^x，f-1a(x)为fa(x)的反函数。
• 求∑a=2n(a∑b=an⌊fa−1(b)⌋⌈fb−1(a)⌉)\sum_{a=2}^n(a\sum_{b=a}^n⌊f_a^{−1}(b)⌋⌈f_b^{−1}(a)⌉)∑a=2n​(a∑b=an​⌊fa−1​(b)⌋⌈fb−1​(a)⌉) % 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();}
}

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