游记
DAY 0
因为这次不评奖也不干啥的所以也就没准备什么,颓了一天。
DAY 1
其实也就一天上午
8:00起床,吃个早饭就准备开始比赛了。
这次登陆得很顺利,没怎么卡。
先开T1,范围那么大,感觉是道结论题,不会。
在看T2,感觉以前好像做过类似的题,先不管。
最后看T3,题面写的很迷,手算一遍样例好像不太对。看了下数据范围发现有20pts的链,就随手写了一个。
这时9:00。
回头看T1,往结论上面想,简单推了一下式子,过了样例。(吐槽一下没有大样例,我暴力都不会写)
预计得分:100?
这时9:30。
再去看T2,以前好像真的做过类似的题,感觉就是线段树维护一下,一顿乱写过了样例,对拍了一下好像也没问题。
预计得分:100?
此时10:30。
再看T3,突然发现题面好像和之前的不太一样/jk。
按新题面手算了一下样例,发现过了。
然后我就看到了公告:10:10左右改了T3题面(垃圾CCF)
发现有20pts的非多项式复杂度暴搜珂写,就随手写了个暴力。(此时11:00)
然后开始想正解,感觉可能是个dp(毕竟不太可能一场比赛没有dp题),然后到最后也没推出来。
预计得分:40?
考试结束后
发现T1好像是道CF原题,CCF这锅得背。
对了一下发现我前两道题都是正解,大概能过。
然后突然发现我T1被hack了,我没判k=1,感觉要凉(毒瘤CCF可以把我卡成0pts)
感觉要凉。
然后又发现T3链的情况1节点不一定是链头,20pts又没了/kk。
最坏得分:0+100+20=120
最好得分:100+100+40=240
出分数
CCF偷偷出分数,我刚开始都不知道。
良心CCF T1还是给了我80pts,T2 100pts没问题,T3就只有20pts了/kk
最终得分:80+100+20=200(终于上了两百
感觉T1没特判还是挺可惜的,要不然就有220pts了。
好多AK的神仙鸭(%%%)
游记就讲到这吧。。。
题解
T1
这道题就不讲每一档部分分怎么拿了,因为我考试的时候也没想。
我们发现如果\(k=1\)直接输出No就行了,先特判一下。
我们先不妨设\((p_1,p_2)=1\),因为如果\((p_1, p_2) \neq 1\),同时对\(p_1, p_2\)除以\((p_1, p_2)\)效果不变。
再不妨设\(p_1<p_2\),最坏情况就是在\([qp_2 + 1, (q+1)p_2 - 1]\)里大于等于\(k\)个\(p_1\)。
而最坏情况就是\(qp_2+1\)是\(p_1\)的倍数,即\(rp_1=qp_2+1\)。
而如果要输出No,则\((r+k-1)p_1 \leq (q+1)p_2 - 1\),化简的\((k-1)p_1+1<p_2\)。
所以若上述式子满足,则输出No,否则输出Yes。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll t, p1, p2, k;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll read() {
ll ret = 0, f = 1;
char ch = getchar();
while ('0' > ch || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9') {
ret = (ret << 1) + (ret << 3) + ch - '0';
ch = getchar();
}
return ret * f;
}
int main() {
t = read();
while (t--) {
p1 = read();
p2 = read();
k = read();
if (k == 1) {
puts("No");
continue;
}
ll g = gcd(p1, p2);
p1 /= g;
p2 /= g;
if (p1 > p2) swap(p1, p2);
if (p1 * (k - 1) + 1 < p2) puts("No");
else puts("Yes");
}
return 0;
}
T2
显然可以想到 \(n^3\) 的暴力,就是枚举端点,然后计算区间内不同的颜色的数量。
考虑用set维护这个区间,然后增量插入,可以把复杂度降到 \(n^2\log{n}\),但还是太慢。
枚举右端点 r,考虑在log的复杂度内计算出 \(f(l,r),l \in [1,r]\)。
我们记pos=右端点的颜色上一次出现的位置+1,如果没有出现过则记为1,这一点可以通过链表O(n)求出来。
然后我们发现只有[pos,r]这个区间内的l的f(l,r)会较f(l,r-1)加一,区间维护一下平方再区间修改区间查询,这就是线段树裸题了。
注意要离散化否则无法开桶。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
const ll mod = 1e9 + 7;
struct Segment{
ll sum, sq, add;
}tr[N << 2];
ll head[N], pre[N];
ll n, a[N], b[N], nn;
ll ans;
ll read() {
ll ret = 0, f = 1;
char ch = getchar();
while ('0' > ch || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9') {
ret = (ret << 1) + (ret << 3) + ch - '0';
ch = getchar();
}
return ret * f;
}
void push_up(ll p) {
tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
tr[p].sq = tr[p << 1].sq + tr[p << 1 | 1].sq;
}
void push_down(ll p, ll l, ll r) {
ll mid = (l + r) >> 1;
if (tr[p].add) {
tr[p << 1].add += tr[p].add;
tr[p << 1].sq += tr[p].add * tr[p].add * (mid - l + 1) + 2 * tr[p << 1].sum * tr[p].add;
tr[p << 1].sum += (mid - l + 1) * tr[p].add;
tr[p << 1 | 1].add += tr[p].add;
tr[p << 1 | 1].sq += tr[p].add * tr[p].add * (r - mid) + 2 * tr[p << 1 | 1].sum * tr[p].add;
tr[p << 1 | 1].sum += (r - mid) * tr[p].add;
tr[p].add = 0;
}
}
void change(ll p, ll l, ll r, ll x, ll y) {
if (r < x || l > y) return;
if (x <= l && r <= y) {
tr[p].add++;
tr[p].sq += r - l + 1 + 2 * tr[p].sum;
tr[p].sum += r - l + 1;
return;
}
push_down(p, l, r);
ll mid = (l + r) >> 1;
change(p << 1, l, mid, x, y);
change(p << 1 | 1, mid + 1, r, x, y);
push_up(p);
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
b[++nn] = a[i];
}
sort(b + 1, b + 1 + nn);
nn = unique(b + 1, b + 1 + nn) - b - 1;
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b + 1, b + 1 + nn, a[i]) - b;
}
for (int i = 1; i <= n; i++) {
pre[i] = head[a[i]];
head[a[i]] = i;
}
for (int i = 1; i <= n; i++) {
ll pos = pre[i] + 1;
change(1, 1, n, pos, i);
ans = (ans + tr[1].sq) % mod;
}
cout << ans;
return 0;
}
T3
设 \(f_k\) 代表恰好为 \(k\) 的方案数,\(g_k\) 代表钦定 \(k\) 场平局的方案数。显然有 \(g_n=\sum_{k\ge n} \binom{k}{n}f_k\),根据二项式反演有 \(f_n=\sum_{k\ge n}(-1)^{k-n}\binom{k}{n}g_k\)。于是只需算 \(g\) 即可。显然可以树形背包。