NAIPC 2019
题意：从(n)个点中选择(k)个点构成多边形，问期望面积。
题解：如果能够确定两个点，那么可以从这两个点之间选择(k-2)个点来构成一个(k)边形。所以可以枚举两个点，计算这两个点被选入构成凸包的概率和对凸包贡献的面积。
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef long double ld;
const int maxn = 2500 + 10;
struct Point {
ld x, y;
}a[maxn];
ld C[maxn][maxn];
void getC(int n) {
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
ld Cross(Point a, Point b) {
return a.x*b.y - a.y*b.x;
}
int n, k;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
getC(n);
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
ld ans = 0;
for (int i = 1; i <= n; i++)
for (int j = k-1; j <= n-1; j++) {
int t = i+j;
if (t > n) t -= n;
ans += Cross(a[i], a[t]) * C[j-1][k-2] / C[n][k];
}
printf("%.7Lf
", ans/2);
}
D - It's a Mod, Mod, Mod, Mod World
题意：给定(n,p,q)，求(sum_{i=1}^n[(p⋅i)mod q])
题解：参考自原博客。我也不会证，应该是把前面的等差数列求和，然后再减去模掉的部分。拿来留作等差数列取模的模板。
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
LL count(LL a, LL b, LL c, LL n) {
if (n <= 0) return 0;
if (n == 1) return b/c;
LL tmp = 0;
tmp += (a/c) * ((n-1)*n / 2);
tmp += (b/c) * n;
a %= c, b %= c;
if (a == 0) return tmp;
return tmp + count(c, (a*n+b)%c, a, (a*n+b)/c);
}
int T;
LL p, q, n;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%lld %lld %lld", &p, &q, &n);
LL sum = p*n*(n+1) / 2ll, tmp = count(p, p, q, n) * q;
printf("%lld
", sum - tmp);
}
}
题意：给定n个顶点坐标值不重复的矩形，问是否有矩形相交（不包括内含）。
题解：线段树扫描线。将每个矩形拆成上下两条线，下边的线对两端点+1，上边的线对两端点-1。如果扫到某条线发现区间和不为0，则说明相交。坐标需要离散化。
#include <vector>
#include <cstdio>
#include <algorithm>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef long double ld;
const int maxn = 2e5 + 10;
struct Seg{
int l, r, h, id;
bool operator < (const Seg& rhs) {
return h < rhs.h;
}
};
vector<Seg> S;
vector<int> V;
struct SegTree {
struct Node {
int l, r, sum;
}t[maxn*4];
void build(int id, int l, int r) {
t[id].l = l, t[id].r = r;
if (l == r) return;
int mid = (l+r) / 2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
}
void update(int id, int x, int val) {
if (t[id].l == t[id].r) { t[id].sum += val; return;}
int mid = (t[id].l + t[id].r) / 2;
if (x <= mid) update(id*2, x, val);
else update(id*2+1, x, val);
t[id].sum = t[id*2].sum + t[id*2+1].sum;
}
int query(int id, int l, int r) {
if (t[id].l == l && t[id].r == r) return t[id].sum;
int mid = (t[id].l + t[id].r) / 2;
if (r <= mid) return query(id*2, l, r);
else if (l > mid) return query(id*2+1, l, r);
else return query(id*2, l, mid) + query(id*2+1, mid+1, r);
}
}ST;
bool cmp(Seg a, Seg b) {
return a.h < b.h;
}
int n, x1, y1, x2, y2;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
S.push_back({x1, x2, y1, 1});
S.push_back({x1, x2, y2, -1});
V.push_back(x1), V.push_back(x2);
}
n *= 2;
ST.build(1, 1, n);
sort(S.begin(), S.end(), cmp);
sort(V.begin(), V.end());
int ans = 0;
for (auto s : S) {
int x = lower_bound(V.begin(), V.end(), s.l) - V.begin() + 1,
y = lower_bound(V.begin(), V.end(), s.r) - V.begin() + 1;
if (s.id == 1) ans |= ST.query(1, x, y) != 0;
ST.update(1, x, s.id);
ST.update(1, y, s.id);
if (s.id == -1) ans |= ST.query(1, x, y) != 0;
}
printf("%d
", ans != 0);
}
J - Subsequences in Substrings
题意：给定两个字符串，求第一个字符串中有多少子串包含第二个字符串构成的子序列。
题解：对于每个位置，预处理26个字母下一次出现的位置。然后枚举左端点，暴力跑完第二个字符串的子序列，就可以得到最小的右端点。把所有右端点到字符串结尾的长度累加就是答案。因为第二个字符串长度为100，所以不会超时。
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 100;
char s[maxn], t[maxn];
int main() {
scanf("%s%s", s, t);
int len = strlen(s);
vector<vector<int> >Next (len+2, vector<int>(27, len));
for (int i = len-1; i >= 0; i--) {
for (int j = 0; j < 26; j++)
Next[i][j] = Next[i+1][j];
Next[i][s[i]-'a'] = i;
}
LL ans = 0;
for (int i = 0; i < len; i++) {
int l = i;
for (int j = 0; t[j]; l = Next[l][t[j++]-'a']+1) ;
ans += len-l+1;
}
printf("%lld
", ans);
}