越考越烂，感觉药丸
感觉考试策略和心态出了大问题
Problem A:辣鸡
这是一道以我的名字命名的题目，我很自豪。
看了题没啥思路，开始看数据点。
第一个数据点只有一个矩形，看出来了单矩形内的式子(2 (x_2 - x_1) (y_2 - y_1)).5pts get
继续读题，还是没啥思路，去上厕所（
回来后继续想，只能想出(O(N^2))的暴力，因为我想不到什么方法去处理不同矩形间的关系。
码码码，昨天写插头DP的后遗症显现出来了，写了一堆IF。。。。
晚上没睡好没关空调被冻醒，调试进度缓慢，写完T1考试过了一半了。。。
考完看题解，我×，真是(O(N^2))的大暴力？？？？
不过加了一个优化：把矩形按照左下角坐标排序，这样，只要两个矩形相离就可以直接break掉。
这个我在考试的时候其实写了，但是脑抽在提交时注释掉了。。。。
这分丢的真实丢人
#include <bits/stdc++.h>
#define ll long long
ll n, x_1, x_2, y_1, y_2, ans;
struct Node {
ll x_1, y_1, x_2, y_2;
friend bool operator <(Node a, Node b) {
if (a.x_1 == b.x_1) return a.y_1 < b.y_1;
return a.x_1 < b.x_1;
}
} nd[100005];
bool In(ll x, ll y, Node a) {
return a.x_1 <= x && a.x_2 >= x && a.y_1 <= y && a.y_2 >= y;
}
namespace case5 {
signed QAQ() {
for (int i = 1; i <= n; i++)
scanf("%lld%lld%lld%lld", &x_1, &y_1, &x_2, &y_2), nd[i] = {x_1, y_1, x_2, y_2}, ans += (x_2 - x_1) * (y_2 - y_1) * 2;
std::sort(nd + 1, nd + 1 + n);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (nd[j].x_1 > nd[i].x_2 + 1) break;
if ((nd[j].x_1 == nd[i].x_2 + 1 || nd[j].x_2 == nd[i].x_1 - 1)
&& (nd[j].y_1 == nd[i].y_2 + 1 || nd[j].y_2 == nd[i].y_1 - 1)) ++ans;
else if (nd[j].x_1 == nd[i].x_2 + 1 || nd[j].x_2 == nd[i].x_1 - 1) {
ll x = std::min(nd[i].y_2, nd[j].y_2), y = std::max(nd[i].y_1, nd[j].y_1);
if (x >= y) {
ans += 2ll * (x - y);
if (nd[i].y_2 != nd[j].y_2) ++ans;
if (nd[i].y_1 != nd[j].y_1) ++ans;
}
} else if (nd[j].y_1 == nd[i].y_2 + 1 || nd[j].y_2 == nd[i].y_1 - 1) {
ll x = std::min(nd[i].x_2, nd[j].x_2), y = std::max(nd[i].x_1, nd[j].x_1);
if (x >= y) {
ans += 2ll * (x - y);
if (nd[i].x_2 != nd[j].x_2) ++ans;
if (nd[i].x_1 != nd[j].x_1) ++ans;
}
}
}
}
return !printf("%lld
", ans);
}
}
signed main() {
scanf("%lld", &n);
return case5::QAQ();
}
Problem B:模板
wdnmd真模板啊都
第一眼读错题以为树上差分，再仔细看，应该是每个节点开个动态开点线段树，然后线段树合并。
问题来了，这玩意我都不会啊。。。
跳了
现在想想真的后悔，线段树合并和平衡树什么的一直咕咕咕没有学，欠下的早晚要还的Orz
这题太好了，独立博文了：https://www.cnblogs.com/gekoo/p/11267848.html
Problem C:大佬
这是一道以我的同桌的名字命名的题目，我的同桌很自豪。
读完题感觉这是假期望（这是错误的万恶之源）
然而其实我此时读错题了（这是fa[万恶之源]）
总方案数不就是(m^n)嘛，求出所有方案和不就行了嘛！
DP不能！别问！问就是DFS！干就完事了！
干个头啊，cwy你分没了（哭
区间的长度是k不是n，总方案数是(m^k)不是(m^n)（错误1）
题目要求的是算t较大的w，不是最大w的t（错误2）（终极弱智错误）
DFS不能后我开始尝试DP。我设计f[i][j]表示第i天最大难度j的方案数。（错误3）
首先基于错误2我的转移方程全是错的。其次，这么设置状态有后效性，DP不能。
官方题解看不懂，邓鸽鸽方法跑得快还好懂。
我们先求出来每个区间最大难度值为i的劳累期望。
所有区间的概率的分母：(frac{1}{m^k}).正确认识是k不是n是你AC的重要基础（捂脸，因为区间长度是k。
在看分子部分，也就是有多少情况的i是有贡献的，也就是区间的最大值。从1-k中选数，区间能产生(i^k)种序列，刨掉最大值不是i的序列，有((i - 1) ^ k)种。
所以每个区间的劳累期望为(sum limits _{i = 1} ^ m ( i^k - (i - 1) ^k ) m^{-k} w_i).
然后激动的cwy输入了样例，挂掉了。
这是一个区间，别忘了乘个区间数。。。
最终答案((n - k + 1) sum limits _{i = 1} ^ m (i^k - (i - 1) ^k) m^{-k} w_i).
这题很坑，数据有k > n的，要特判掉。
#include <bits/stdc++.h>
#define ll long long
const int MOD = 1000000007;
ll n, m, k, ans, w;
ll qpow(ll x, ll b) {
ll ret = 1;
for (; b; b >>= 1, x = x * x % MOD)
if (b & 1) ret = ret * x % MOD;
return ret;
}
signed main() {
scanf("%lld%lld%lld", &n, &m, &k);
if (n < k) return !printf("0
");
for (int i = 1; i <= m; i++)
scanf("%lld", &w), ans = (ans + w * (qpow(i, k) - qpow(i - 1, k)) % MOD * qpow(m, k * (MOD - 2)) % MOD) % MOD;
printf("%lld
", ans * (n - k + 1) % MOD);
return 0;
}