今天的题目难度比昨天小一些，但是太菜的我还是啥也不会。
今天的出题大佬是Heaplex，他的题目中倒是出现了ZZQ，不知道是否是本人？
T1.a
期望得分30，实际得分30
这道题开场发现好像有什么小小的规律，而且既然数据范围都到2*10^6了，这基本就是明示你要是用O（n）的算法了。
一开始我想了暴力30，就是n^2的算法，这样肯定不行。考虑一下当前每个s[i] > i的数，它在下一次旋转之后的贡献是当前的值-1，而s[i] < i的数，它在下一次旋转之后的贡献是当前值+1. 而当前第一个元素不大一样，他的贡献可以直接每次计算出来。
然后我就卡壳了，卡在怎么维护每次旋转之后s[i] > i的个数。
后来听了Dukelv的讲解才知道，其实无需维护！我们把答案看成一长序列，我们完全可以记录在旋转第i次的时候有多少值会从小变大！这个只要一开始的时候预处理一下，维护s[i]-i = -x的数，那么在旋转x次之后就会变正。之后直接线性计算就可以了！（我自己咋就想不出来我太菜了）
然后还有一种做法（题解），其实一个数对于答案序列的贡献是好几段不连续的等差数列，这个可以用二阶差分维护，但是代码长不想写……
看一下老詹的正解代码。
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define rg register typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 2e6 + 5; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } void MYFILE() { #ifndef mrclr freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif } int n, a[maxn]; int big = 0, sma = 0, num[maxn << 1]; ll ans, Min = 0; int main() { MYFILE(); n = read(); for(int i = 1; i <= n; ++i) { a[i] = read(); int x = a[i] - i; if(x >= 0) ++big, Min += x; else ++sma, Min -= x, num[-x]++; } ans = Min; for(int i = 1; i <= n; ++i) { int x = a[i] - 1, y = n - a[i]; big--; Min -= x; sma++; Min += y; num[i + y]++; Min += big - sma + 1; if(num[i]) big += num[i], sma -= num[i]; ans = min(ans, Min); } write(ans); enter; return 0; }
T2.maze
期望得分30，实际得分10.
这题一开始没啥思路，直接暴力bfs。然后还有一种神奇的起点不合法的情况没有特判，卡了我20.
之后据说正解是线段树……反正这个矩阵它非常的窄，我们可以把它看成一个序列。对于一个区间[l,r]，我们直接维护第l列所有点到第r列所有点的最短距离。
用线段树上的每一个点代表一个邻接矩阵，直接维护距离。
在修改的时候直接单点修改，然后暴力重构所有涉及到的矩阵，查询的时候合并直接用floyd合并，返回一个结构体（借鉴了老詹的代码，老詹重载了运算符）
我们看一下mrclr大神的代码。
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define rg register typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxm = 2e5 + 5; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } void MYFILE() { #ifndef mrclr freopen("maze.in", "r", stdin); freopen("maze.out", "w", stdout); #endif } int n, m, q, a[6][maxm]; struct Tree { int l, r; int dis[6][6]; Tree operator + (const Tree &oth)const { Tree ret; Mem(ret.dis, 0x3f); ret.l = l; ret.r = oth.r; for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) ret.dis[i][j] = min(ret.dis[i][j], dis[i][k] + 1 + oth.dis[k][j]); return ret; } }t[maxm << 2]; void build(int L, int R, int now) { t[now].l = L; t[now].r = R; if(L == R) { Mem(t[now].dis, 0x3f); for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) if(a[j][L]) t[now].dis[i][j] = t[now].dis[j][i] = j - i; else break; return; } int mid = (L + R) >> 1; build(L, mid, now << 1); build(mid + 1, R, now << 1 | 1); t[now] = t[now << 1] + t[now << 1 | 1]; } void update(int now, int d) { if(t[now].l == t[now].r) { Mem(t[now].dis, 0x3f); for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) if(a[j][t[now].l]) t[now].dis[i][j] = t[now].dis[j][i] = j - i; else break; return; } int mid = (t[now].l + t[now].r) >> 1; if(d <= mid) update(now << 1, d); else update(now << 1 | 1, d); t[now] = t[now << 1] + t[now << 1 | 1]; } Tree query(int L, int R, int now) { if(L == t[now].l && R == t[now].r) return t[now]; int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) return query(L, R, now << 1); else if(L > mid) return query(L, R, now << 1 | 1); else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1); } int main() { MYFILE(); n = read(); m = read(); q = read(); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) a[i][j] = read(); build(1, m, 1); for(int i = 1; i <= q; ++i) { int op = read(); if(op == 1) { int x = read(), y = read(); a[x][y] ^= 1; update(1, y); } else { int sx = read(), sy = read(), ex = read(), ey = read(); int ans = query(sy, ey, 1).dis[sx][ex]; write(ans == INF ? -1 : ans); enter; } } return 0; }
T3.point
期望得分60，实际得分95.
本题一开场最暴力思路想到30分。然后发现这个k必然是区间最小值，可以用st表维护，然后又发现这样无法解决判断的问题……还是O（n^3）。又发现，我们反正要求最大的区间，那不如直接从每个点往两边暴力拓展，维护与之最近的不是其倍数的点，然后这样再扫一遍，复杂度是O（n^2）的，但是实际上因为数据特别随机它卡过了95pts，而且比正解跑的快。大哥用暴力+特判直接把这题A了。
正解是，我们可以先预处理每个区间的最小值和区间gcd，如果二者相等说明此区间合法。（这个就是我没想到的了）
这样我们可以O（1）判断一个区间，预处理是O（nlog^2n），然后又因为我们要求最大区间长，所以可以直接二分答案，那么计算的复杂度就是O（nlogn），直接A题。
题外话，其实这题暴力跑的贼快，比正解快5倍，除了那个被卡掉的点。
不上95分代码啦……直接看一下老詹的A题代码（%%%%%）
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define rg register typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 5e5 + 5; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } void MYFILE() { #ifndef mrclr freopen("point.in", "r", stdin); freopen("point.out", "w", stdout); #endif } int n; inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; } int dp[maxn][21][2], ha[maxn]; void rmq() { for(rg int i = 1; i <= n; ++i) dp[i][0][0] = dp[i][0][1] = read(); for(rg int j = 1; (1 << j) <= n; ++j) for(rg int i = 1; i + (1 << j) - 1 <= n; ++i) { dp[i][j][0] = min(dp[i][j - 1][0], dp[i + (1 << (j - 1))][j - 1][0]); dp[i][j][1] = gcd(dp[i][j - 1][1], dp[i + (1 << (j - 1))][j - 1][1]); } int x = 0; for(rg int i = 1; i <= n; ++i) { ha[i] = x; if((1 << (x + 1)) <= i + 1) x++; } } inline int query_Min(const int &L, const int &R) //卡常…… { int k = ha[R - L + 1]; return min(dp[L][k][0], dp[R - (1 << k) + 1][k][0]); } inline int query_Gcd(const int &L, const int &R) { int k = ha[R - L + 1]; return gcd(dp[L][k][1], dp[R - (1 << k) + 1][k][1]); } bool judge(const int &len) { for(rg int i = 1; i + len - 1 <= n; ++i) { int L = i, R = i + len - 1; int Min = query_Min(L, R), Gcd = query_Gcd(L, R); if(!(Gcd % Min)) return true; } return false; } int num = 0; vector<int> ans; int main() { MYFILE(); n = read(); rmq(); int L = 0, R = n; while(L < R) { int mid = (L + R + 1) >> 1; if(judge(mid)) L = mid; else R = mid - 1; } for(rg int i = 1; i + L - 1 <= n; ++i) { int l = i, r = i + L - 1; int Min = query_Min(l, r), Gcd = query_Gcd(l, r); if(!(Gcd % Min)) num++, ans.push_back(i); } write(num); space; write(L - 1); enter; for(rg int i = 0; i < (int)ans.size(); ++i) write(ans[i]), space; enter; return 0; }
两天分数合计215可还行……菜到连本省省一线都没到。
还是撸起袖子继续干吧orz。