切蛋糕的贝贝
题意：
将多边形一个蛋糕切成6份，使得面积之比为1:1:4:5:1:4（顺序可以打乱），只有两种切法，一种是将过外
接圆的多边形的对角线，第二种是从多边形的中心和顶点的连线，先给你一个n边形，问是否可以完成这个目标
思路：
虽然有两种切法，但是实际的没什么太大的差距，可以很容易的看出
1、若n是16的倍数，此时完成这个操作只需要5步
2、若n不是16的倍数，此时是根本无法完成这种操作的
时间复杂度：O（1）
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if(n % 16 == 0) cout << 5 << endl;
else {
cout << -1 << endl;
}
return 0;
}
抱歉，这没有集美
题意：
将1~n随意排列，每一种排列代表一种方案，当一种方案中存在一个位置满足gcd （i，p[i]）则，说明Tenshi成为集
美的概率就不为0，问在给定的n的情况下，有多少中这种方案（答案对1e9 + 7取余）
思路：
满足i和p[i]的值是偶数情况时，i和p[i]的值需要都是偶数，所以在n个数中一共存在n / 2（下取整）个偶数，枚举
所有的方案显然很复杂，所以这里可以采用容斥原理，计算方案中不存在这种条件的方案数，对于所以的方案数哟共有n！种方案，互补方案的特点是：
奇数可以放在奇数位上，偶数必须放在奇数位上（在给定的一个n中，偶数的数量 <= 奇数的数量恒成立）
1、当n是奇数时：对于偶数位上一共 （n + 1） / 2 （向下取整）中选法，奇数位上一共有 n / 2 (向下取整)种
选法，这里注意可以存在奇数放在奇数位上的情况出现，
所以此时的方案数是：（n + 1）/ 2）！* (n / 2) ！（除法向下取整）
2、当n时偶数是，同理得到方案数为：(n / 2) ! * (n / 2) ! (除法向下取整)
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL solve(int n) {
LL ans = 1;
for (int i = 1; i <= n; i ++ ) {
ans = (ans * i) % mod;
}
return ans % mod;
}
LL cal(int n) {
int temp = n / 2;
LL ans = 1;
for (int i = 1; i <= temp; i ++ ) {
ans = (ans * i) % mod;
ans = (ans * i) % mod;
}
return ans % mod;
}
int main() {
int n;
cin >> n;
LL sum = solve(n);
if (n % 2 == 1) n ++ ;
LL temp = cal(n);
// cout << sum << " " << temp << endl;
cout << (sum - temp + mod) % mod << endl;
return 0;
}
打牌的贝贝
题意：
贝贝和宁宁玩扑克牌，里一共有2 * n张牌，规则是：
问贝贝和宁宁各自获胜的数量
思路：
官方的题解中提到了卡特兰常数（不太了解），不如直接用直白的解释
贝贝要是想赢的话，必须手中有一个张大于宁宁手中所有牌的卡牌，所以此时先给贝贝n - 1张牌，然后在剩余的卡牌
种拿一个最大值，就可以满足贝贝赢（而且这个最大值具有唯一性），所以贝贝赢的方案是：C（n - 1， 2 * n）
总方案数是C(n, 2 * n) ，所以宁宁获胜的方案数目是: C(n, 2 * n) - C(n - 1, 2 * n)
时间复杂度：O（3 * n）
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5;
const LL mod = 1e9 + 7;
LL num[N];
LL ans[N];
//快速幂
LL qpow(LL a, LL b) {
LL res = 1;
while (b) {
if(b & 1) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
void init() {
num[1] = 1;
for (int i = 2; i <= 2000000; i ++ ) {
num[i] = (num[i - 1] * i) % mod;
}
ans[2000000] = qpow(num[2000000], mod - 2) % mod;
for (int i = 2000000; i >= 1; i -- ) {
ans[i - 1] = ans[i] * i % mod;
}
}
LL solve(LL m, LL n) {
return num[n] * ans[m] % mod * ans[n - m] % mod;
}
int main() {
int t;
cin >> t;
//将n的阶乘和x ^ mod - 2(1 <= x <= 2000000)都初始化出来，节省时间
init();
while (t -- ) {
int n;
scanf("%d", &n);
if(n == 1) {
cout << "1 1" << endl;
continue;
}
printf("%lld %lld\n", solve(n - 1, 2 * n), (solve(n, 2 * n) - solve(n - 1, 2 * n) + mod) % mod);
//这里不要使用endl会爆时间
}
return 0;
}
点分治分点
题意：给定一个n个点，m条边的图，定义一条简单路径上的low值为其路径上的边权的最小值，（简单路径不能包含两
个相同的点），d(u, v) 为从 u 到 v 所有简单路径的最大 low 值，对于给定的s，u从1到n输出d(s, u)，若是
不存在则输出-1
思路：
在图论结题方法中一般都是先完成建图，然后再在图上进行操作，但是这个题，可以在建图的过程中解决问题
将所有路径按照权值从大到小排序，然后每次将边加到图中，这样每次选出的权值，对于能达到的点而言，都一样是最
小值中的最大值
时间复杂度：不是很清楚，望有大佬解惑（多谢-）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct node {
int x, y, w;
}s[N];
bool vis[N];
vector<int> e[N];
int ans[N];
bool cmp(node a, node b) {
return a.w > b.w;
}
void dfs(int x, int w) {
vis[x] = 1;
ans[x] = w;
for (auto i : e[x]) {
if(!vis[i]) {
dfs(i, w);
}
}
}
int main() {
int n, m, st;
scanf("%d%d%d", &n, &m, &st);
for (int i = 1; i <= n; i ++ ) ans[i] = -1;
for (int i = 1; i <= m; i ++ ) {
cin >> s[i].x >> s[i].y >> s[i].w;
}
sort(s + 1, s + 1 + m, cmp);
vis[st] = 1;
for (int i = 1; i <= m; i ++ ) {
int xx = s[i].x, yy = s[i].y;
e[xx].push_back(yy);
if(vis[xx] && !vis[yy]) {
dfs(yy, s[i].w);
}
}
for (int i = 1; i <= n; i ++ ) {
printf("%d ", ans[i]);
}
return 0;
}
参考：https://www.cnblogs.com/hhzp/p/16864121.html
标签：方案,练习赛,int,LL,牛客,贝贝,ans,105,mod From： https://www.cnblogs.com/luoyefenglin/p/16874990.html