禁止以任何形式转载此文
solution
| 主讲人 | IGL | ALBL |
|---|---|---|
| 试题 | T2 T3 | T1 T4 T5 |
现世，暗险
题意：给你一张有向图，距离为 ( ext{2}) 的正整数次幂的两点间可以重新连一条长为 ( ext{1}) 边，求在此情况下的从起点到终点最短路。
我们用 ( ext{f[i][j][o]}) 表示点 ( ext{i}) 到点 ( ext{j}) 之间是否存在长为 (large 2^o) 的边。有为真，否则为假。显然如果 ( ext{f[i][k][o - 1] = f[k][j][o - 1] = 1})，那 ( ext{f[i][j][o] = 1})。预处理原图中相连的点为 ( ext{f[i][j][0] = 1})。用 ( ext{dis[i][j]}) 表示两点间的最短距离，预处理原图中相连的点距离为 ( ext{1})，不相连的赋最大值。
然后倍增处理连新边，最后跑最短路即可。
数据这么小，( ext{Floyd}) 可以了。
#include <bits/stdc++.h>
#define N 100
using namespace std;
template <typename T>
inline void read (T &a) {
T x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
(ch == '-') and (f = 0);
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + (ch ^ '0');
ch = getchar ();
}
a = f ? x : -x;
}
template <typename T, typename ...A>
inline void read (T &t, A &...a) {
read (t), read (a...);
}
template <typename T>
inline void print (T x) {
if (x < 0) putchar ('-'), x = -x;
if (x > 9) print (x / 10);
putchar (x % 10 + '0');
}
int f[N][N][N];
int dis[N][N], n, m;
signed main () {
freopen ("Marionette.in", "r", stdin);
freopen ("Marionette.out", "w", stdout);
read (n, m);
memset (dis, 0x3f, sizeof dis);
for (int i = 1, x, y; i <= m; i++) {
read (x, y);
f[x][y][0] = 1;
dis[x][y] = 1;
}
for (int o = 1; o <= 64; o++) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (f[i][k][o - 1] and f[k][j][o - 1]) {
f[i][j][o] = 1;
dis[i][j] = 1;
}
}
}
}
} // 处理可以直接跳的
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
} // 最短路
print (dis[1][n]);
}
夜魇，如一
1.暴力
考虑暴力枚举，对于每一种情况都追杀一次。
2.正解
仔细观察，我们可以发现一些性质：我们设上帝的一次追杀事件为 ( ext{(0, x)})，我们可以得到一个小结论：
对于 ( ext{x} e ext{u}_ ext{i})，则这个事件插入在 ( ext{i}) 之前还是之后都是等价的，需要的话口胡证明。
因此，我们可以尝试在每一个事件前插入 ((0,u_i)) 之后直接暴力模拟，模拟一次的复杂度为 ( ext{O(n)})，这题还有一个点—— ( ext nge ext m)，所以很容易想到当追杀无效直接跳过，则至多进行 ( ext{3m-1}) 次，复杂度( ext{O(nm)})。
#include<bits/stdc++.h>
#define int long long
//#define rint register int
#define endl '
'
using namespace std;
const int maxn = 6e4 + 5,mod = 1e9 + 7;
inline int read() {
char c=getchar(),f=0;int t=0;
for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
return f?-t:t;
}
inline void write(int num) {
if(num < 0) {
putchar('-');
num = -num;
}
if(num > 9) write(num / 10);
putchar(num % 10 + '0');
}
int n, m;
int hp[2005], tem[2005], ans[2005];
int lastin[2005];
struct thea{
int u, v;
}Kill[maxn];
inline void as_one(int pos, int tar) {
for(int i = 1; i <= m; ++ i) tem[i] = hp[i];
tem[tar] --;
for(int i = pos; i <= n; ++ i) if(tem[Kill[i].u] && tem[Kill[i].v]) tem[Kill[i].v] --;
int t = 0;
for(int i = 1; i <= m; ++ i) if(tem[i]) t ++;
ans[t] += (pos - lastin[tar]);
lastin[tar] = pos;
}
signed main() {
freopen("Seele.in","r",stdin);
freopen("Seele.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= n; ++ i) Kill[i].u = read(), Kill[i].v = read();
for(int i = 1; i <= m; ++ i) hp[i] = 3;
for(int i = 1; i <= n; ++ i) {
int x = Kill[i].u, y = Kill[i].v;
if(hp[x] && hp[y]) {
as_one(i, x);
hp[y] --;
}
}
int t = 0;
for(int i = 1; i <= m; ++ i) if(hp[i]) t ++;
for(int i = 1; i <= m; ++ i) {
if(hp[i] == 1) ans[t - 1] += n + 1 - lastin[i];
else ans[t] += n + 1 - lastin[i];
}
for(int i = 0; i <= m; ++ i) {
printf("%lld ", ans[i]);
}
return 0;
fclose(stdin);fclose(stdout);
}
薪炎，燎原
这是一道恨不得拍到你脸上告诉你“这是四维偏序板子”的一道题，具体实现就是 ( ext{CDQ}) 套 ( ext{CDQ}) , 复杂度 ( ext{O(nlog}^3 ext{n)}),用( ext{KDT}) 的话会更快（但是我不会呵呵呵）
然后因为我自己的原因我的 ( ext{CDQ}) 跑了( ext{2.5s})（不会有暴力过了吧）
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define endl '
'
using namespace std;
const int maxn = 5e4 + 5,mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
inline int read() {
char c=getchar(),f=0;int t=0;
for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
return f?-t:t;
}
inline void write(int num) {
if(num < 0) {
putchar('-');
num = -num;
}
if(num > 9) write(num / 10);
putchar(num % 10 + '0');
}
int n, m, ans, M;
int b[maxn], poi_2D[maxn], poi_D[maxn];
struct node {
int a, b, c, d, val, ans, id, choed;
inline bool operator == (const node &x) const {
return a == x.a && b == x.b && c == x.c && d == x.d;
}
} poi[maxn], a[maxn];
inline int max(int a, int b) {
if(a > b) return a; else return b;
}
inline bool cmp1(node a, node b) {
if(a.a != b.a) return a.a < b.a;
if(a.b != b.b) return a.b < b.b;
if(a.c != b.c) return a.c < b.c;
return a.d < b.d;
}
inline bool cmp2(node a, node b) {
if(a.b != b.b) return a.b < b.b;
if(a.c != b.c) return a.c < b.c;
return a.d < b.d;
}
inline bool cmp3(node a, node b) {
if(a.c != b.c) return a.c < b.c;
return a.d < b.d;
}
struct AT {
int tr[maxn];
#define lowbit(x) (x & (-x))
inline void add(int poi, int x) {
for(int i = poi; i <= n; i += lowbit(i)) tr[i] = max(tr[i], x);
}
inline int ask(int poi) {
int ans = -inf;
for(int i = poi; i; i -= lowbit(i)) ans = max(tr[i], ans);
return ans % mod;
}
inline void clear(int poi) {
for(int i = poi; i <= n; i += lowbit(i)) {
tr[i] = 0;
}
}
} TA;
void CDQ_3D(int l ,int r) {
// cout << "FFGFFFF
";
if(l == r) return ;
int mid = (l + r) >> 1;
CDQ_3D(l, mid);
rint i = l, j = mid + 1;
sort(a + l, a + mid + 1, cmp3);
sort(a + mid + 1, a + r + 1, cmp3);
for(;j <= r; ++ j) {
while(i <= mid && a[i].c <= a[j].c) {
if(a[i].choed) TA.add(a[i].d, a[i].ans);
i++ ;
}
if(!a[j].choed) a[j].ans = max(a[j].ans, (TA.ask(a[j].d) + a[j].val) % mod);
}
for(i = l; i < j; ++ i) if(a[i].choed) TA.clear(a[i].d);
for(i = l; i <= r; ++ i) poi[poi_2D[a[i].id]] = a[i];
for(i = l; i <= r; ++ i) a[i] = poi[i];
CDQ_3D(mid + 1, r);
}
void CDQ_2D(int l, int r) {
// cout << "SDFASFDASFDADASDASDASD
";
if(l == r) return ;
int mid = (l + r) >> 1;
CDQ_2D(l, mid);
for(rint i = l; i <= mid; ++ i) a[i].choed = true;
for(rint i = mid + 1; i <= r; ++ i) a[i].choed = false;
sort(a + l, a + r + 1, cmp2);
for(rint i = l; i <= r; ++ i) {
poi_2D[a[i].id] = i;
}
CDQ_3D(l, r);
for(rint i = l; i <= r; ++ i) {
poi[poi_D[a[i].id]] = a[i];
}
for(rint i = l; i <= r; ++ i) a[i] = poi[i];
CDQ_2D(mid + 1, r);
}
signed main() {
freopen("Heavenlyfire.in","r",stdin);
freopen("Heavenlyfire.out","w",stdout);
n = read();
M = read();
for(rint i = 1; i <= n; ++ i) {
a[i].a = read(), a[i].b = read(), a[i].c = read(), a[i].d = read() % mod, a[i].val = read() % mod;
b[i] = a[i].d;
}
sort(b + 1, b + 1 + n);
int tot = unique(b + 1, b + 1 + n) - b - 1;
for(rint i = 1; i <= n; ++ i) {
a[i].d = lower_bound(b + 1, b + 1 + tot, a[i].d) - b;
}
sort(a + 1, a + 1 + n, cmp1);
for(rint i = 1; i <= n; ++ i) {
if(a[i] == a[i - 1]) {
a[m].val = (a[m].val + max(0LL, a[i].val)) % mod;
}
else a[++m] = a[i];
}
for(rint i = 1; i <= n; ++ i) a[i].ans = a[i].val, a[i].id = i, poi_D[a[i].id] = i;
CDQ_2D(1, n);
ans = -inf;
for(rint i = 1; i <= n; ++ i) ans = max(ans, a[i].ans);
printf("%lld
", ans % mod);
if(ans % mod < M) cout << "The Honkai befalled";
else cout << "May all the beauty be blessed";
fclose(stdin);fclose(stdout);
}
镜缘
一切开始之前，我们先推导一个引理：
[large{
f(n)=sum_{i=0}^ni^2,nge0\
f(n)=frac{n(n+1)(2n+1)}{6}
}
]
这里提供五种推导它的方法。
一、查找法
通过搜索引擎，题解，文献等，我们找到了这个公式：
[large f(n)=frac{n(n+1)(2n+1)}{6}
]
[doge]
二、归纳法
[large
egin{aligned}
&f(n)=frac{n(n+1)(2n+1)}{6}\
&=frac{n(n+1)(n+frac{1}{2})}{3}\
&\
&f(0)=0\
&f(n)=f(n-1)+n^2\
&3f(n)=(n-1)n(n-frac{1}{2})+3n^2\
&=(n^3-frac{3}{2}n+frac{1}{2}n)+3n^2\
&=n^3+frac{3}{2}n^2+frac{1}{2}n\
&=n(n+frac{1}{2})(n+1)\
& ext{故对于所有的}nge0,f(n)=frac{n(n+1)(2n+1)}{6}
end{aligned}
]
三、二重合式展开与收缩
[large
egin{aligned}
&f(n)=sum_{k=1}^nk^2\
&=sum_{j=1}^nsum_{k=j}^nk\
&=sum_{j=1}^nfrac{j+n}{2}(n-j+1)\
&=frac{1}{2}sum_{j=1}^n(n(n+1)+j-j^2)\
&=frac{1}{2}n^2(n+1)+frac{1}{4}n(n+1)-frac{1}{2}f(n)\
&=frac{1}{2}n(n+frac{1}{2})(n+1)-frac{1}{2}f(n)\
&\
&frac{3}{2}f(n)=frac{1}{2}n(n+frac{1}{2})(n+1)\
&f(n)=frac{n(n+1)(2n+1)}{6}
end{aligned}
]
对 (sum_{k=1}^nk^2=sum_{j=1}^nsum_{k=j}^nk) 的解释：
我们知道，一个数 (n) 加和 (n) 次，就是 (n^2)。
将右式展开：
1+2+3+4+5+6+...+n
2+3+4+5+6+...+n
3+4+5+6+...+n
4+5+6+...+n
5+6+...+n
6+...+n
...
...+n
刚好每个数 (k) 加 (k) 次，与原式等价。
四、瞎搞法
利用恒等式 (large(n+1)^3=n^3+3n^2+3n+1)，可以得到：
[large
egin{aligned}
&(n+1)^3-n^3=3n^2+3n+1\
&n^3-(n-1)^3=3(n-1)^2+3(n-1)+1\
&cdotscdots\
&2^3-1^3=3*(1^2)+3*1+1
end{aligned}
]
把这 (large n) 个等式两端分别相加，得：
[large(n+1)^3-1=3 imesfrac{n(n+1)}{2}+n+3sum_{i=1}^ni^2\
large n^3+3n^2+3n=3 imesfrac{n(n+1)}{2}+n+3sum_{i=1}^ni^2\
]
整理后得：
[largesum_{i=1}^ni^2=frac{n(n+1)(2n+1)}{6}
]
五、扰动法
这是最实用的方法。
对于 (f(n+1)) ，抽出 ((n+1)^2,0^2)。
[large
egin{aligned}
&f(n)+(n+1)^2\
&=sum_{k=0}^n(k+1)^2\
&=sum_{k=0}^n(k^2+2k+1)\
&=sum_{k=0}^nk^2+2sum_{k=0}^nk+sum_{k=0}^n1\
&=f(n)+2sum_{k=0}^nk+(n+1)\
&\
&sum_{k=0}^nk=frac{1}{2}((n+1)^2-(n+1))=frac{n(n+1)}{2}
end{aligned}
]
额。。。有个毛用？
等等，二次幂可以推出一次幂求和，那是不是三次幂可以推出二次幂求和？
设
[large g(n)=sum_{k=0}^nk^3
]
从 (g(n)) 中抽出 ((n+1)^3, 0^3)。
[large
egin{aligned}
&g(n)+(n+1)^3\
&=sum_{k=0}^n(k+1)^3\
&=sum_{k=0}^n(k^3+3k^2+3k+1)\
&=sum_{k=0}^nk^3+3sum_{k=0}^nk^2+3sum_{k=0}^nk+sum_{k=0}^n1\
&=g(n)+3f(n)+frac{3n(n+1)}{2}+(n+1)\
&\
&3f(n)=(n+1)^3-frac{3n(n+1)}{2}-(n+1)\
&=n^3+3n^2+3n+1-frac{3n^2+3n}{2}-n-1\
&=n^3+frac{3n^2}{2}+frac{n}{2}\
&=(n+1)(n+frac{1}{2})n\
&\
&f(n)=frac{n(n+1)(n+frac{1}{2})}{3}
end{aligned}
]
通过此方法，我们可以从 (n+1) 次幂推出 (n) 次幂！！！
好，接下来回归题目：
从 (1) 到 (sqrt{R}) 枚举 (x)，那 (y) 的最大值为 (sqrt{R-x^2})，因为再大会超出这个圆。
当然 (y) 向下取整。
(large x) 的贡献总和为 (large x^2y)，(large y) 的贡献总和为 (largefrac{y(y+1)(2y+1)}{6})。
相加即可。
#include <bits/stdc++.h>
#define int unsigned long long
#define le double
#define mod 1000000007
using namespace std;
inline int qpow (int a, int b) {
int res = 1;
while (b) {
(b & 1) and (res = res * a % mod);
a = a * a % mod;
b >>= 1;
}
return res;
}
int r, ans, k, inv;
signed main () {
freopen ("Mirror.in", "r", stdin);
freopen ("Mirror.out", "w", stdout);
inv = qpow (6, mod - 2);
cin >> r;
for (int x = 0, y; x * x <= r; x++) {
y = sqrt ((le) r - x * x);
k = (y * (y + 1) % mod * (y * 2 % mod + 1) % mod) * inv % mod + (x * x % mod * y % mod) % mod;
ans = (ans + k) % mod;
}
cout << ans * 4 % mod << endl;
// cout << "The run time is: " <<(double)clock() / CLOCKS_PER_SEC << "s" << endl;
}
廊中燥
话说这题是我自己口胡的，所以很水。
先给结论：
[large sum_{kin S(m,n)}varphi(k)=m imes n
]
首先思考判定条件 ( ext{n mod k + m mod k}ge ext{k}) 的等价判定式。
与 (mod) 有关的，除法？除法与向下取整结合，会有：
[largelfloorfrac{(n+m)}{k}
floor-lfloorfrac{n}{k}
floor-lfloorfrac{m}{k}
floor
]
这个式子与原判定式等价。
那么再看这个合式，既然有了新的判定式，那么这个式子也该找个等价式。
发现 (S(m,n)) 其实就是在 (1) 到 (m+n) 个数里筛掉一些数，
也就是：
[largesum_{k=1}^{m+n}varphi(k)lfloorfrac{m+n}{k}
floor-sum_{k=1}^nvarphi(k)lfloorfrac{n}{d}
floor-sum_{k=1}^mvarphi(k)lfloorfrac{m}{d}
floor
]
接下来考虑如何计算这个冗长的式子。
暴力枚举肯定不行。
发现这个长式子可以分成三截，算其中一截就行。
我们先从中拉出来一截转换一下：
[largelfloorfrac{n}{k}
floor=sum_{i=1}^n[dmid i]
]
带入其中那部分式子
[large
egin{aligned}
&sum_{k=1}^nvarphi(k)lfloorfrac{n}{d}
floor\
&=sum_{k=1}^nvarphi(k)sum_{j=1}^n[kmid j]\
&=sum_{j=1}^nsum_{k=1}^j[kmid j]varphi(k)\
&=sum_{j=1}^nsum_{kmid j}varphi(k)\
&=sum_{j=1}^nj\
&=frac{n(n+1)}{2}
end{aligned}
]
答案显而易见了，
[large
egin{aligned}
&frac{(m+n)(m+n+1)}{2}-frac{n(n+1)}{2}-frac{m(m+1)}{2}\
&=m imes n
end{aligned}
]
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n, m;
signed main () {
freopen ("Wzybqdp.in", "r", stdin);
freopen ("Wzybqdp.out", "w", stdout);
cin >> n >> m; cout << ((n % mod) * (m % mod)) % mod;
}