终于又回到熟悉的Round了
设个未知数，解方程，还好没有hack点
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5;
const double PI = acos (-1.0); int main() {
double d, h, v, e; scanf ("%lf%lf%lf%lf", &d, &h, &v, &e);
double V = PI * (d / 2.0) * (d / 2.0) * h;
double addv = PI * (d / 2.0) * (d / 2.0) * e;
if (addv > v) {
puts ("NO");
} else {
double t = -V / (addv - v);
puts ("YES");
printf ("%.8f\n", t);
}
return 0;
}
题意：求增加最小长度的一根木棍，使得构成一个多边形。
分析：那么构成三角形，原来n条木棍分成A，B两边，A和B接近(A<=B)，那么另一条边满足A + C > B，即C = B +１ - A
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5;
int a[N]; int main() {
int n; scanf ("%d", &n);
ll sum = 0;
for (int i=0; i<n; ++i) {
scanf ("%d", a+i);
sum += a[i];
}
std::sort (a, a+n);
ll del = 1000001000;
ll A, B, presum = 0;
for (int i=0; i<n; ++i) {
presum += a[i];
ll res = sum - presum;
ll tmp = presum - res;
if (abs (tmp) < del) {
if (tmp < 0) {
del = -tmp;
A = presum;
B = res;
} else {
del = tmp;
A = res;
B = presum;
}
}
}
ll C = B + 1 - A;
printf ("%I64d\n", C); return 0;
}
题意：问后缀由若干个长度为2或3的子串构成，且相邻的子串不能相同。
分析：The only restriction — it is not allowed to append the same string twice in a row! 英语太渣不知道这是连续，相邻的意思。那么dp[i][0]表示i开始长度为2的子串能否可行，如果可行，那么dp[i-3][1]一定可行，因为长度不相等；还有如果长度相等的判断一下，即dp[i-2][0]。
#include <bits/stdc++.h> const int N = 1e4 + 5;
bool dp[N][2]; int main() {
std::string str;
std::cin >> str;
int n = str.length ();
dp[n-2][0] = dp[n-3][1] = true;
std::set<std::string> ans;
for (int i=n-1; i>=5; --i) {
if (dp[i][0]) {
ans.insert (str.substr (i, 2));
dp[i-3][1] = true;
if (str.substr (i-2, 2) != str.substr (i, 2)) {
dp[i-2][0] = true;
}
}
if (dp[i][1]) {
ans.insert (str.substr (i, 3));
dp[i-2][0] = true;
if (str.substr (i-3, 3) != str.substr (i, 3)) {
dp[i-3][1] = true;
}
}
}
std::cout << ans.size () << '\n';
for (auto s: ans) {
std::cout << s << '\n';
}
return 0;
}
题意：找4个点按照顺序走，a->b->c->d，每次点到下一个点走的是最短路，问走的长度总和最大是多少。
分析：先计算dis(u, v)，枚举b和c，对于b来说在反向图中找距离最远的点，因为a!=b a!=c，所以存最优的前3个点；对于c来说在原图中找距离最远的点，存最优的前4个点。
#include <bits/stdc++.h> const int N = 3e3 + 5;
const int M = 5e3 + 5;
const int INF = 0x3f3f3f3f;
int dis[N][N];
std::vector<int> G[N], rG[N];
std::vector<std::pair<int, int> > bin[N], bout[N];
bool vis[N];
int n, m; void BFS() {
memset (dis, INF, sizeof (dis));
for (int i=1; i<=n; ++i) {
std::queue<int> que;
dis[i][i] = 0;
que.push (i);
while (!que.empty ()) {
int u = que.front (); que.pop ();
for (auto v: G[u]) {
if (dis[i][v] > dis[i][u] + 1) {
dis[i][v] = dis[i][u] + 1;
que.push (v);
}
}
}
}
} void sort_out() {
for (int i=1; i<=n; ++i) {
memset (vis, false, sizeof (vis));
vis[i] = true;
bout[i].push_back (std::make_pair (0, i));
std::queue<std::pair<int, int> > que;
que.push (std::make_pair (0, i));
while (!que.empty ()) {
std::pair<int, int> pu = que.front (); que.pop ();
for (auto v: G[pu.second]) {
if (!vis[v]) {
vis[v] = true;
bout[i].push_back (std::make_pair (pu.first + 1, v));
que.push (std::make_pair (pu.first + 1, v));
}
}
}
std::sort (bout[i].begin (), bout[i].end (), std::greater<std::pair<int, int> > ()); //dis[i][v], v
if (bout[i].size () > 4) {
bout[i].resize (4);
}
}
} void sort_in() {
for (int i=1; i<=n; ++i) {
memset (vis, false, sizeof (vis));
vis[i] = true;
bin[i].push_back (std::make_pair (0, i));
std::queue<std::pair<int, int> > que;
que.push (std::make_pair (0, i));
while (!que.empty ()) {
std::pair<int, int> pu = que.front (); que.pop ();
for (auto v: rG[pu.second]) {
if (!vis[v]) {
vis[v] = true;
bin[i].push_back (std::make_pair (pu.first + 1, v));
que.push (std::make_pair (pu.first + 1, v));
}
}
}
std::sort (bin[i].begin (), bin[i].end (), std::greater<std::pair<int, int> > ()); //dis[v][i], v
if (bin[i].size () > 3) {
bin[i].resize (3);
}
}
} int main() {
scanf ("%d%d", &n, &m);
for (int u, v, i=0; i<m; ++i) {
scanf ("%d%d", &u, &v);
G[u].push_back (v);
rG[v].push_back (u);
}
BFS ();
sort_in ();
sort_out ();
int a, b, c, d;
int best = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=n; ++j) {
if (i == j || dis[i][j] == INF) {
continue;
}
int k, l;
for (int ii=bin[i].size ()-1; ii>=0; --ii) {
int tot = dis[i][j];
std::pair<int, int> &x = bin[i][ii];
if (x.second != i && x.second != j) {
k = x.second;
tot += x.first;
for (int jj=bout[j].size ()-1; jj>=0; --jj) {
std::pair<int, int> &y = bout[j][jj];
if (y.second != i && y.second != j && y.second != k) {
l = y.second;
tot += y.first;
if (best < tot) {
best = tot;
a = k; b = i; c = j; d = l;
}
tot -= y.first;
}
}
}
}
}
}
printf ("%d %d %d %d\n", a, b, c, d); return 0;
}
组合数学 C - Codeword(div 1)
题意：给一个串，长度为 l，问它扩展成长度n的串有多少个（其中长度l的原串相当于变成长度n的子序列）
分析：对于长度为 l 的子序列，n 的答案是
因为 l 的总和不超过 10^5，所以 l 不同的取值只有最多 2 sqrt(10^5) 种。对于每个 l，前缀和预处理所有 n 的答案。
令，则
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int fac[N], inv_fac[N];
char s[N];
int ans[N];
std::vector<std::pair<int, int> > query[N]; //len, n int pow_mod(int x, int n) {
int ret = 1;
while (n) {
if (n & 1) {
ret = (ll) ret * x % MOD;
}
x = (ll) x * x % MOD;
n >>= 1;
}
return ret;
} int binom(int n, int m) {
if (m > n) {
return 0;
} else {
return (ll) fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD;
}
} void prepare(int len, int maxn) {
int base = 1;
//g(n)
for (int i=0; i<=maxn; ++i) {
ans[i] = i < len ? 0 : (ll) binom (i - 1, len - 1) * base % MOD;
if (i >= len) {
base = (ll) base * 25 % MOD;
}
}
//f(n+1) = g(n+1) + f(n+1) * 26
for (int i=0; i<maxn; ++i) {
if (ans[i] >= MOD) {
ans[i] -= MOD;
}
ans[i+1] += (ll) ans[i] * 26 % MOD;
}
if (ans[maxn] >= MOD) {
ans[maxn] -= MOD;
}
} int main() {
fac[0] = 1;
for (int i=1; i<N; ++i) {
fac[i] = (ll) fac[i-1] * i % MOD;
}
inv_fac[N-1] = pow_mod (fac[N-1], MOD-2);
for (int i=N-2; i>=0; --i) {
inv_fac[i] = (ll) inv_fac[i+1] * (i + 1) % MOD;
}
std::vector<int> query;
int m; scanf ("%d", &m);
scanf ("%s", s);
int len = strlen (s);
int maxn = -1;
for (int i=0; i<m; ++i) {
int op; scanf ("%d", &op);
if (op == 1) {
prepare (len, maxn);
for (int j=0; j<query.size (); ++j) {
printf ("%d\n", ans[query[j]]);
}
query.clear ();
maxn = -1;
scanf ("%s", s);
len = strlen (s);
} else {
int n; scanf ("%d", &n);
if (maxn < n) {
maxn = n;
}
query.push_back (n);
}
}
prepare (len, maxn);
for (int j=0; j<query.size (); ++j) {
printf ("%d\n", ans[query[j]]);
}
return 0;
}