超级菜的我一道题都没写出来，来补题了
A [SDOI2106]齿轮
前向星（专栏）+遍历的简单题（我没看出来的简单题）
这道题重点是在齿轮匹配的转化上面，我们该怎么定位呢？
- 这里着重要考虑的就是前向星的权值是什么？
- 回顾已知条件：我们知道相邻的两个齿轮所相对转动的圈数，也就是齿轮相对转动比例。
- 所以这个也就是我们的权值了。但是怎么用呢？
- 根据这个权值，我们可以从上一个节点推导出下一个节点。所以我们假设比例为y/x（y为后一节点的相对转动圈数，x为前一节点的）。
然后就是写代码：
- 按照前向星的方法，将前向星初始化（前向星可以看专栏）。
- 然后建立一个观测数组（visited数组），将所有节点遍历一遍（以第一个节点开始，并以第一个的相对转动圈数作为他的实际转动圈数）。
- 如果有和要求互斥的（本题为我们推导出的下一节点的转动圈数）就直接输出No，正常扫完所有节点就可以输出Yes了。
- 详情看我代码吧~
代码
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
//代码预处理区
const int MAX = 1e4 + 7;
int head[MAX], total = 0;
struct node {
int v, next;
double w;
} edge[MAX << 1];
double weight[MAX];
int visited[MAX], flag = 1;
//全局变量区
template<class T>inline void read(T& res);//整型快读函数
void add_edge(int u, int v, double w);
void dfs(int u, int fa);
//函数预定义区
int main() {
int T; read(T);
for (int cnt = 1; cnt <= T; cnt++) {
int N, M; read(N); read(M);
total = 0;
memset(head, 0, sizeof head);
for (int i = 1; i <= M; i++) {
int u, v, x, y; read(u); read(v); read(x); read(y);
add_edge(u, v, 1.0 * x / y);
add_edge(v, u, 1.0 * y / x);
}
flag = 1;
memset(visited, 0, sizeof visited);
for (int i = 1; i <= N && flag; i++)
if (!visited[i]) {
weight[i] = 1.0;
dfs(i, 0);
}
if (flag) printf("Case #%d: Yes\n", cnt);
else printf("Case #%d: No\n", cnt);
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
void add_edge(int u, int v, double w) {
total++;
edge[total].v = v;
edge[total].w = w;
edge[total].next = head[u];
head[u] = total;
}
void dfs(int u, int fa) {
visited[u] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v != fa)
if (visited[v])
if (abs(weight[v] - weight[u] * edge[i].w) <= 1e-3);
else {
flag = 0;
return;
}
else {
weight[v] = weight[u] * edge[i].w;
dfs(v, u);
}
}
}
//函数区
B Rinne Loves Xor
这道题我其实不是很懂，有点懵，看了几个小时没有起色（好难受）
- 但是能理解的是：这道题我先想到了前缀和，但是这里不可能用（因为这里是异或之和，而不是和的异或）。
- 然后从异或，我们一般会想到两个东西：<1>递推。<2>二进制。
- 说到二进制我们当然就会想到数位的贡献（但也就是这里我最不能理解）。我们可以计算并递推每一位的贡献。
- 详情看代码吧。。
代码
#include <iostream>
using namespace std;
typedef long long ll;
//代码预处理区
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 7;
ll A[MAX], B[MAX], C[MAX];
ll dpa[37][2], dpb[37][2];
//全局变量区
template<class T>inline void read(T& res);//整型快读函数
//函数预定义区
int main() {
int N; read(N);
for (int i = 1; i <= N; i++) read(A[i]);
for (int i = 1; i <= N; i++) read(B[i]);
for (int i = 1; i <= N; i++)
for (int j = 0; j <= 30; j++) {
dpa[j][(A[i] >> j) & 1]++;
dpb[j][(B[i] >> j) & 1]++;
C[i] += (dpa[j][0] * dpb[j][1] + dpa[j][1] * dpb[j][0]) << j;
C[i] %= MOD;
}
for (int i = 1; i <= N; i++)
printf("%lld ", C[i]);
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
//函数区
C 阶乘
要说明显呢也明显，说不明显呢，也不明显。这道题我们可以用二分来查找答案。
- 二分查找答案最重要的是什么呢？就是二分判断区间的条件。
所以话不多说我们就来讲一下怎么区分：
- 首先，二分是用来查找线性关系的方法：所以我们要知道他有个什么样的线性关系。
- 那为什么这样做呢？首先我们确定一个概念：本题的线性关系就是素因子的数量。
- 那我们回到最初的起点，在什么条件下n!会是p的倍数呢？从素因子的角度来看就是：n!的素因子集合包含p的素因子集合。
- 所以首先，倍数的满足条件我们就知道了。那怎么才是最小的呢？要小，肯定就是素因子越少越小啦。
- 所以，我们只要在n!的素因子满足p素因子集合的数量下，减少其他素因子数量就好了。
- 我们这道题的判断条件就是：不满足p的条件就返回false，就找更大的数。满足就返回true，去找比她小的数。
但是写到这里，你可能会说：憨憨，你讲了这么多，我还是不知道怎么算每个的数量啊！这可是n!啊！
不要紧，我这不是要说呢吗：
- 首先我们因为这是阶层，我们假设我们有一个数n，要求n!对每个素因子有多少个数。
- 毫无疑问，我们可以先预处理一个数组用来放我们的素数集合。
- 然后逐个访问。那最终要的来了，n!包括了比n小的所有整数。我们怎么数？
- 我们取出最后一个数，也就是n。对某一个素数进行整除：举个栗子，n = 8对2整除。因为前面有2,4,6,8四个数，一除就知道前面有几个数是这个数的倍数了（在这里是8 / 2 = 4）。
- 除完之后呢，我们的每个数也就减小了这个素数倍（这个例子就是变成了1,2,3,4）。再从这些数里面找出该素数（例子为2）的倍数。
- 最后没有数了的时候（n = 0）把这些累加起来就是某一个素因子的个数。（这里简单来说就是：把1~n中的每一个数的该因子拿出来）
最后当然还是写代码了：
- 首先就是预处理一个素数数组啦。
- 第二就是二分查找答案。
- 接下来就是按照我们上面的操作对项目进行二分操作。
代码
#include <iostream>
#include <cstring>
using namespace std;
//代码预处理区
const int MAX = 1e5 + 7;
int prime[MAX], cnt[MAX], len = 0;//素因子，素因子的个数，数组长度
//全局变量区
template<class T>inline void read(T& res);//整型快读函数
int judge(int mid);//二分判断函数
//函数预定义区
int main() {
int T; read(T);
while (T--) {
int p; read(p);
len = 0;
memset(cnt, 0, sizeof cnt);
for (int i = 2; i * i <= p; i++)
if (0 == p % i) {
prime[++len] = i;
while (0 == p % i) {
cnt[len]++;
p /= i;
}
}
if (p > 1) {
prime[++len] = p;
cnt[len]++;
}
//求出素因子及其个数
int left = 1, right = 1e9, ans = 0;
while (left <= right) {
int mid = left + right >> 1;
if (judge(mid)) {
right = mid - 1;
ans = mid;
}
else left = mid + 1;
}
//二分查找
printf("%d\n", ans);
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int judge(int mid) {
for (int i = 1; i <= len; i++) {
int n = mid, sum = 0;
while (n) {
sum += n / prime[i];
n /= prime[i];
}
if (sum < cnt[i]) return false;
}
return true;
}
//函数区
D 小石的签到题
分析可得，小石永远可以一次性拿的只剩一个。除非我想让他输。。。
代码
#include <iostream>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
int main() {
js;
int n; cin >> n;
if (n == 1) cout << "Yang" << endl;
else cout << "Shi" << endl;
return 0;
}
E 装备合成
这道题有两种写法：<1>数学题。<2>三分法。
<1>数学题：
- 这道题不（wo）难（mei）发现是一道线性规划的题目。所以可以用我们高中的方法来求。
所以怎么写呢？
- 根据题意，我们先得到他的线性方程组。（我们在这里假设第一种生产了m件，第二种生产了n件）。
---分割线---
（横纵坐标为mOn）
- 根据方程，我们可以得出右图的三种可能性，并可以依据此判断，分类讨论出我们的答案。
- 首先两个单调曲线十分好求，由于我们求的是m+n的最大值。所以直接可以得到答案为截距向下取整。我们重点看相交的情况。
- 相交时，我们相当于要求出交点的m和n值（不过m和n要取整，所以要考虑向上或向下取整哪个大）。
- 所以我们就先求出该点的m值吧：此处因为求的是交点，所以可以直接将等式联立，就能得出：m = 1.0 * (4 * y - x) / 10。（此处m为浮点数）。
- 然后就要对m的上取整数和下取整数求出对应的n值。（这里要考虑对应的是哪条直线：我们可以看图分辨m变大或变小时，哪条曲线在边界内）
- 最后比较两种哪个大就好啦~（看代码）
<2>三分法：
- 根据题目化简，还是假设第一种生产了m件，我们用换元法可以得到：ans = m + min((x - 2m) / 4, y - 3m)。
- 根据三分法，我们就可以缩小该单峰区间的极值。然后缩小到一定范围之后，我们进行枚举，取出最大值就好了。
代码
线性规划法#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
//代码预处理区
template<class T>inline void read(T& res);//整型快读函数
//函数预定义区
int main() {
int T; read(T);
while (T--) {
ll x, y; read(x); read(y);
ll x1 = y, y1 = y / 3, x2 = x / 4, y2 = x / 2;
//分别为两条直线在x，y轴上的截距
if (x1 <= x2) printf("%lld\n", x1);
else if (y1 >= y2) printf("%lld\n", y2);
//两种不相交的情况
else {
double maxm = 1.0 * (4 * y - x) / 10;//实数的最大m
ll m1 = floor(maxm), m2 = ceil(maxm);
ll n1 = (x - m1 * 2) / 4, n2 = y - 3 * m2;
//整数的最大m，和对应的最大n
printf("%lld\n", max(m1 + n1, m2 + n2));//输出较大方案
}
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
//函数区 三分法#include <iostream>
using namespace std;
//代码预处理区
int x, y;
//全局变量区
template<class T>inline void read(T& res);//整型快读函数
int F(int n) { return n + min((x - 2 * n) / 4, y - 3 * n); }
//函数预定义区
int main() {
int T; read(T);
while (T--) {
read(x); read(y);
int left = 0, right = min(x / 2, y / 3);
while (left + 7 < right) {
//debug(left);debug(right);
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (F(mid1) < F(mid2)) left = mid1;
else right = mid2;
}
int ans = 0;
for (int i = left; i <= right; i++)
ans = max(ans, F(i));
printf("%d\n", ans);
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
//函数区 
京公网安备 11010502036488号