A、点对最大值
题意：给一棵树，有点权也有边权，求最长点对价值，最长点对价值指的是这两点的路径的边权和加上这两个点的权值
dp[v] 表示一个端点为 v，另一个节点是在以 v 为根的子树中 的最大点对价值，考虑 u 是 v 的父节点，转移到 dp[u] 时，我们只需要考虑，以 v 为另一个端点和以 其他点为另一个端点并且加上 dp[u]（即除了这个子链的其他链的最大值），然后在遍历玩了这个点为根节点的子树之后，将 dp[u] 加上 u 的点权，这时，dp[u] 就表示一个端点为 u ，另一个节点是在以 u 为根的子树中 的最大点对价值，即完成了状态转移。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 5;
struct edge
{
int to;
ll w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
ll dp[MAXN], val[MAXN];
ll ans = 0;
void init(int n)
{
for (int i = 1; i <= n; i++)
{
head[i] = -1;
dp[i] = -1e18 - 7;
}
tot = 1;
ans = -1e18 - 7;
}
void add(int a, int b, ll w)
{
e[tot] = edge{ b,w,head[a] };
head[a] = tot++;
}
void dfs(int u, int fa)
{
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
ll w = e[i].w;
if (v == fa)
continue;
dfs(v, u);
ans = max(ans, dp[u] + dp[v] + w - val[v]);
ans = max(ans, dp[u] + w + val[v]);
dp[u] = max(dp[u], dp[v] + w - val[v]);
dp[u] = max(dp[u], w + val[v]);
}
dp[u] += val[u];
ans = max(ans, dp[u]);
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
init(n);
for (int i = 1; i < n; i++)
{
int to; ll w;
sc("%d%lld", &to, &w);
add(i + 1, to, w);
add(to, i + 1, w);
}
for (int i = 1; i <= n; i++)
sc("%lld", &val[i]);
dfs(1, 0);
pr("%lld\n", ans);
}
} B、减成一
题意：n个数，每次选择一个区间是的区间内所有数字减一，求将所有数变成 1 的最小次数。
和上周中北大学的一个题类似，将这个序列看成若干个不下降的序列，然后序列内通过若干次区间减一，变成这些区间的最小值，并且由于前一个区间的最大值肯定小于下一个区间的最小值，所以不需要额外的代价，可以将所有数字变成第一个区间的最小值，即第一个数字，所以我们只需要在进行 a[1] - 1 次，即可将所有数字变成 1
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
ll a[MAXN];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
ll ans = 0;
a[0] = 1;
for (int i = 1; i <= n; i++)
{
sc("%lld", &a[i]);
if (a[i - 1] < a[i])
ans += a[i] - a[i - 1];
}
pr("%lld\n", ans);
}
} C、面积
题意：输出面积
x * x + (x / 2) ^ 2 * PI * 2
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll n;
sc("%lld", &n);
double ans = n * n + 2 * (n / 2.0) * (n / 2.0) * 3.14;
pr("%.2lf\n", ans);
}
} D、扔硬币
题意：有n个硬币，每个硬币正面反面概率都是50%，投出n个硬币，求至少有m个硬币是反面的前提下，有k个硬币是正面的概率
显然是一个概率论问题，就用 有k个硬币是正面的概率 / 至少有m个硬币是反面 即可，并且由于数据库较小，每次暴力求前缀和也能过
注意特判 0 的情况
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
const ll mod = 1e9 + 7;
ll invi[MAXN], fac[MAXN], inv[MAXN];
void init()
{
invi[0] = invi[1] = 1;
fac[0] = 1;
inv[0] = 1;
for (int i = 2; i < MAXN; i++)
invi[i] = invi[mod % i] * (ll)(mod - mod / i) % mod;
for (int i = 1; i < MAXN; i++)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = invi[i] * inv[i - 1] % mod;
}
}
ll C(ll n, ll m)
{
ll ans = fac[n] * inv[m] % mod * inv[n - m] % mod;
return ans;
}
ll power(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll a[MAXN];
int main()
{
init();
int T;
sc("%d", &T);
while (T--)
{
ll n, m, k;
sc("%lld%lld%lld", &n, &m, &k);
if (m + k > n)
pr("0\n");
else
{
ll ans1 = C(n, k) % mod;
ll ans2 = 0;
for (int i = 0; i <= n - m; i++)
ans2 = (ans2 + C(n, i)) % mod;
pr("%lld\n", ans1 * power(ans2, mod - 2) % mod);
}
}
} E、赛马
题意：每个人有n个马，每个马一个战力值，求第一个人最多能赢多少场。
先将第一个人的马的战力值存在multiset中，然后对于每一个别人的马，找一匹比这个马战斗力大的战斗力最小的马，然后删掉即可，如果没有比他大的就选一匹战斗力最小的马和它打
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int a[MAXN];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
multiset<int>s;
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
sc("%d", &a[i]);
s.insert(a[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
int t;
sc("%d", &t);
auto it = s.upper_bound(t);
if (it == s.end())
continue;
else
{
ans++;
s.erase(it);
}
}
pr("%d\n", ans);
}
} F、三角形
题意：将长度为 a 的木棒分成若干段，要求不能组成三角形，最多能被分成几段
显然按照斐波那契数列来分是最优的，如果剩下的值不足以构成下一个斐波那契数，那么我们将剩下的数全部放在上一个数。
由于题目给的范围比较大，直接上JAVA，真香
import java.math.BigInteger;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
BigInteger zero = new BigInteger("0");
BigInteger[] fib = new BigInteger[100];
fib[1] = new BigInteger("1");
fib[2] = new BigInteger("1");
for (int i=3;i<100;i++)
fib[i] = fib[i-1].add(fib[i-2]);
for (int i=2;i<100;i++){
fib[i]=fib[i].add(fib[i-1]);
}
for (int i=0;i<T;i++){
BigInteger n = sc.nextBigInteger();
for (int j=1;j<100;j++) {
if (n.subtract(fib[j]).compareTo(zero) < 0) {
System.out.println(j-1);
break;
}
}
}
}
} H、直线
题意：一个平面，n 条直线，最多有多少个交点
在纸上模拟，很容易得到答案是 1 到 n 的等差数列，由于数据较大，直接上JAVA，真香
import java.math.BigInteger;
import java.util.*;
public class Main{
public static void main(String[] args){
BigInteger one = new BigInteger("1");
BigInteger two = new BigInteger("2");
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i=0;i<T;i++){
BigInteger n = sc.nextBigInteger();
n = n.multiply(n.subtract(one)).divide(two);
System.out.println(n);
}
}
} J、最大值
题意：对于字符串中一个非前缀子串 它与字符串的前缀相等的最大长度
这个定义就是KMP的next数组的定义，所以直接跑一遍next数组即可
（字符串哈希+二分应该也可以通过此题）
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
char s[MAXN];
int len, nex[MAXN], n, m;
void getnex()
{
memset(nex, 0, sizeof(nex));
int i = 0, j = -1;
nex[0] = -1;
while (i < len)
{
if (j == -1 || s[i] == s[j])
{
i++, j++;
nex[i] = j;
}
else
j = nex[j];
}
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
sc("%s", s);
len = strlen(s);
getnex();
int ans = 0;
for (int i = 1; i <= len; i++)
{
ans = max(ans, nex[i]);
}
pr("%d\n", ans);
}
} 
京公网安备 11010502036488号