周三

M. Rock-Paper-Scissors Pyramid（思维）

斜着看，每次复制一遍加一个

用一个栈维护，如果当前可以打败栈顶的，就出栈，如果相同，入不入栈都可以，如果打不过也要入栈，因为它可以阻挡后面的。

最后栈底就是留下来的。

#include
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
char s[N];
int top;int main()
{map mp;mp['S'] = 0; mp['P'] = 1; mp['R'] = 2;int T; scanf("%d", &T);while(T--){string str; cin >> str;int len = str.size();top = 0;rep(i, 0, len){while(top && (mp[str[i]] + 1) % 3 == mp[s[top]]) top--;s[++top] = str[i];}printf("%c\n", s[1]);}return 0;
}

P3396 哈希冲突（根号分治）

用根号为分界线，一部分暴力，一部分预处理

对于这道题，模数小于等于根号n时，直接预处理

模数大于等于根号n时，直接暴力

#include
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1.5e5 + 10;
const int M = 400;
int s[M][M], a[N], n, m;int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d", &a[i]);int block = sqrt(n);_for(i, 1, n)_for(j, 1, block)s[j][i % j] += a[i];while(m--){char op[10]; int x, y;scanf("%s%d%d", op, &x, &y);if(op[0] == 'A'){if(x <= block) printf("%d\n", s[x][y]);else{int res = 0;for(int i = y; i <= n; i += x) res += a[i];printf("%d\n", res);}}else{_for(j, 1, block) s[j][x % j] += y - a[x];a[x] = y;}}return 0;
}

Array Queries（根号分治）

1e5左右的数据范围要很敏感，很可能是n根号n的算法

这题而言，每次p最少会增加k

那么当k大于根号n时，最多跳根号n次

当k小于根号n时，可以用dp直接求出，倒着求一遍

#include
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
const int M = 350;
int dp[N][M], a[N], n, m;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);int block = sqrt(n);for(int i = n; i >= 1; i--)_for(k, 1, block){int j = i + a[i] + k;if(j > n) dp[i][k] = 1;else dp[i][k] = dp[j][k] + 1;}scanf("%d", &m);while(m--){int p, k;scanf("%d%d", &p, &k);if(k <= block) printf("%d\n", dp[p][k]);else{int res = 0;while(p <= n){p = p + a[p] + k;res++;}printf("%d\n", res);}}return 0;
}