思路主要参考自官方题解，以及网友的博客分享，十分感谢~
A-巨木之森 #树的直径
题目链接
暂时咕咕咕，等我考完期末考
B-乐**对 #记忆化搜索 #线性DP
题目链接
分析：
比赛时我的思路是逆序贪心，但一直都过不了，赛后发现数据(n=12,a[]={6,6,6,6,6,6,6,1,1,1,1,1})，它的正确分组应该为：(6,6,6,6,6,6,6∣1∣1∣1∣1∣1)。
最保险的方法应该是DP，预先升序排序，然后状态转移方程为：
[dp[i] = egin{cases}
dp[i-1], \
dp[i - a[i]] + 1 （若i-a[i]+1存在）
end{cases}
]
但注意最终答案应该选择(dp[n] = dp[n - a[n]] +1)，这样是为了保证最后的人能够进队，比如 3 1 1 3。
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int dp[MAXN], a[MAXN], n;
int dfs(int cur){
if(cur <= 0) //抵达递归基
return 0;
else if(dp[cur] > -1)
return dp[cur];
else if(cur == n) //已保证前提
return dp[n] = 1 + dfs(cur - a[cur]); //因为最大值不能自成
else{
int mymax = -1;
if(cur - a[cur] >= 0) //[ (cur - a[cur]）, cur]自成一队
mymax = max(mymax, dfs(cur - a[cur]) + 1);
mymax = max(mymax, dfs(cur - 1)); //与cur-1属于同一队
return dp[cur] = mymax;
}
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
dp[i] = -1;
}
sort(a + 1, a + n + 1);
if(a[n] > n)
printf("-1
");
else
printf("%d
", dfs(n));
return 0;
}
C-光玉小镇 #搜索 #状态压缩DP
暂时咕咕咕，等我考完期末考
D-巅峰对决 #线段树
题目链接
分析：
本题卡的地方，在于如何用(O(logn))的时间复杂度，判断任意区间的每个值递增连续，判断区间长度 是否 等于最大值与最小值之差 即可。
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 1e5 + 5;
int n, q, mymax[MAXN << 2], mymin[MAXN << 2];
void PushUp(int rt){
mymax[rt] = max(mymax[rt << 1], mymax[rt << 1 | 1]);
mymin[rt] = min(mymin[rt << 1], mymin[rt << 1 | 1]);
}
void Build(int lo, int hi, int rt){
if(lo == hi){
int val;
scanf("%d", &val);
mymax[rt] = mymin[rt] = val;
return;
}
int mid = (lo + hi) >> 1;
Build(lo, mid, rt << 1);
Build(mid + 1, hi, rt << 1 | 1);
PushUp(rt);
}
void UpdateForDot(int idx, int X, int lo, int hi, int rt){
if(lo == hi) {
mymax[rt] = mymin[rt] = X;
return;
}
int mid = (lo + hi) >> 1;
if(idx <= mid)
UpdateForDot(idx, X, lo, mid, rt << 1);
else
UpdateForDot(idx, X, mid + 1, hi, rt << 1 | 1);
PushUp(rt);
}
pair<int, int> Query(int L, int R, int lo, int hi, int rt){
if(L <= lo && hi <= R)
return{mymax[rt], mymin[rt]};
int mid = (lo + hi) >> 1;
pair<int, int> ans{-1e9-5, 1e9+5}, tmp;
if(L <= mid) {
tmp = Query(L, R, lo, mid, rt << 1);
ans.first = max(ans.first, tmp.first);
ans.second = min(ans.second, tmp.second);
}
if(mid < R){
tmp = Query(L, R, mid + 1, hi, rt << 1 | 1);
ans.first = max(ans.first, tmp.first);
ans.second = min(ans.second, tmp.second);
}
return ans;
}
int main(){
scanf("%d%d", &n, &q);
Build(1, n, 1);
while(q--){
int opt, lo, hi;
scanf("%d%d%d", &opt, &lo, &hi);
if(opt == 1){
UpdateForDot(lo, hi, 1, n, 1);
}
else if(opt == 2){
pair<int, int> ans = Query(lo, hi, 1, n, 1);
if(ans.first - ans.second == hi - lo)
printf("YES
");
else
printf("NO
");
}
}
}
E-使徒袭来 #基本不等式
题目链接
分析
知道乘积，用pow函数就能出求和了$frac{a_1+a_2+...+a_n}{n} ge sqrt[n]{a_1a_2...a_n} $
F-核弹剑仙 #bitset #拓扑排序
题目链接
分析
题目要求偏序关系的计数，因而拓扑排序是本题的核心。如何计数呢？起初我以为直接用cnt[]存储次数，转移该节点时，对其所有上一节点的结果进行累加。然而，对于下图的情况，会将上一条路径重复累加，导致最终结果偏大
如何不遗漏分叉的路径，又不重复累加重合的路径呢？很明显这样的计数是取并集的过程，我们想到STL中bitset支持两个串的01进行按位或运算——即两串取并集。也就是说，我们为每一节点都定义个01串，这个01串的某个位若为1，记录该数位代表的顶点比当前节点先序。转移时，先将上一顶点的01串对当前顶点的01串进行按位或运算，然后再将上一顶点所代表的数位取1。最终，将每个节点的01串中含1的数量输出来即可。
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
#include <bitset>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
queue<int> myque;
bitset<MAXN> bitstr[MAXN];
int n, m, H[MAXN], tot = 0, InD[MAXN];
struct Edge{
int to, nextNbr;
} E[MAXN << 1];
int cnt[MAXN];
void AddEdge(int u, int v){
tot++;
E[tot].to = v; E[tot].nextNbr = H[u]; H[u] = tot;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) H[i] = -1;
for (int i = 1; i <= m; i++){
int tmpu, tmpv;
scanf("%d %d", &tmpu, &tmpv);
AddEdge(tmpu, tmpv);
InD[tmpv]++;
}
for (int i = 1; i <= n; i++)
if(InD[i] == 0)
myque.push(i);
while(!myque.empty()){
int u = myque.front();
myque.pop();
for (int i = H[u]; i >= 0; i = E[i].nextNbr){
int v = E[i].to;
InD[v]--;
if(InD[v] == 0){
myque.push(v);
}
bitstr[v] |= bitstr[u];
bitstr[v][u] = 1;
}
}
for (int i = 1; i <= n; i++)
printf("%d
", (int)bitstr[i].count());
}
H-社*游戏 #二维前缀和 #二分
题目链接
分析
注意题干中，是保证子正方形中所有字母都不超过k！
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
#include <bitset>
using namespace std;
typedef long long ll;
const int MAXN = 505;
int G[MAXN][MAXN], n, m, k;
int sum[29][MAXN][MAXN];
int ans[MAXN][MAXN];
string str[MAXN];
int Cal(int t, int x2, int y2, int x1, int y1) {
return sum[t][x2][y2] - sum[t][x2][y1 - 1] - sum[t][x1 - 1][y2] + sum[t][x1 - 1][y1 - 1];
}
bool Judge(int x2, int y2, int x1, int y1) {
for (int i = 1; i <= 27; i++) { //保证所有字母不超过!!!
if (Cal(i, x2, y2, x1, y1) > k) return 0;
}
return 1;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) cin >> str[i];
for (int t = 1; t <= 27; t++) {
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int cur = str[i][j] - 'a' + 1;
sum[t][i][j + 1] = (t == cur) + sum[t][i - 1][j + 1] + sum[t][i][j - 1 + 1] - sum[t][i - 1][j - 1 + 1];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int lo = 1, hi = min(n - i + 1, m - j + 1), len = 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (Judge(i + mid - 1, j + mid - 1, i, j)) {
lo = mid + 1;
len = mid;
}
else {
hi = mid - 1;
}
}
ans[i][j] = len;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
printf("%d%c", ans[i][j], (j == m) ? '
' : ' ');
}
I-名作之壁 #双指针 #单调队列
题目链接
分析
观察数据范围，我们不可能将任意区间枚举出来，一定需要观察题目性质。注意到，由于b,c均为正数，a[i]的值随i值递增。我们利用右指针（定义为i）尝试遍历整个数组。若a[lo, hi]的最值之差一旦大于k时，那么a[lo, hi+1]、a[lo, hi+2]、…的最值之差一定也满足大于k，因为最小值不变，最大值增大嘛。由此，我们一旦碰到条件满足，不需要继续枚举右端点i。此时，对于右端点为i且满足题意的区间有n-i+1
在当前右端点i下，我们又逐渐枚举左端点j，直到a[j, i]区间最值之差不满足题意时，我们再将i向前移动。
如何在(O(1))的时间复杂度内，得出一定区间的两个最值呢？使用两个单调队列，分别维护窗口最大值、最小值，代码中直接使用deque去模拟单调队列。
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;
const int MAXN = 1e7 + 5;
const int MOD = 1e9;
int n, k;
ll a[MAXN], c, b;
deque<int> mymax, mymin;
int main() {
scanf("%d%d", &n, &k);
scanf("%lld%lld%lld", &a[0], &b, &c);
for (int i = 1; i <= n; i++){
a[i] = (a[i - 1] * (ll)b + (ll)c) % MOD;
}
ll ans = 0;
for (int i = 1, j = 1; i <= n; i++){
//单调队列基本操作
while(!mymax.empty() && a[mymax.back()] <= a[i]) mymax.pop_back();
mymax.push_back(i);
while(!mymin.empty() && a[mymin.back()] >= a[i]) mymin.pop_back();
mymin.push_back(i);
while(!mymin.empty() && !mymin.empty() && a[mymax.front()] - a[mymin.front()] > k){ //对于特定的j，它们有相应的（可拓展的）右端点i
ans += (n - i + 1);
j++;
//保证单调队列维护[j, i]的最值
if(mymin.front() < j) mymin.pop_front();
if(mymax.front() < j) mymax.pop_front();
}
}
printf("%lld
", ans);
}