【牛客算法周周练4】

1. 这里着重要考虑的就是前向星的权值是什么？
2. 回顾已知条件：我们知道相邻的两个齿轮所相对转动的圈数，也就是齿轮相对转动比例。
3. 所以这个也就是我们的权值了。但是怎么用呢？
4. 根据这个权值，我们可以从上一个节点推导出下一个节点。所以我们假设比例为y/x（y为后一节点的相对转动圈数，x为前一节点的）。

1. 按照前向星的方法，将前向星初始化（前向星可以看专栏）。
2. 然后建立一个观测数组（visited数组），将所有节点遍历一遍（以第一个节点开始，并以第一个的相对转动圈数作为他的实际转动圈数）。
3. 如果有和要求互斥的（本题为我们推导出的下一节点的转动圈数）就直接输出No，正常扫完所有节点就可以输出Yes了。
4. 详情看我代码吧~

#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);
            }
    }
}
//函数区

• 但是能理解的是：这道题我先想到了前缀和，但是这里不可能用（因为这里是异或之和，而不是和的异或）。
• 然后从异或，我们一般会想到两个东西：<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;
}
//函数区

• 二分查找答案最重要的是什么呢？就是二分判断区间的条件。

1. 首先，二分是用来查找线性关系的方法：所以我们要知道他有个什么样的线性关系。
2. 那为什么这样做呢？首先我们确定一个概念：本题的线性关系就是素因子的数量。
3. 那我们回到最初的起点，在什么条件下n!会是p的倍数呢？从素因子的角度来看就是：n!的素因子集合包含p的素因子集合。
4. 所以首先，倍数的满足条件我们就知道了。那怎么才是最小的呢？要小，肯定就是素因子越少越小啦。
5. 所以，我们只要在n!的素因子满足p素因子集合的数量下，减少其他素因子数量就好了。
6. 我们这道题的判断条件就是：不满足p的条件就返回false，就找更大的数。满足就返回true，去找比她小的数。

1. 首先我们因为这是阶层，我们假设我们有一个数n，要求n!对每个素因子有多少个数。
2. 毫无疑问，我们可以先预处理一个数组用来放我们的素数集合。
3. 然后逐个访问。那最终要的来了，n!包括了比n小的所有整数。我们怎么数？
4. 我们取出最后一个数，也就是n。对某一个素数进行整除：举个栗子，n = 8对2整除。因为前面有2,4,6,8四个数，一除就知道前面有几个数是这个数的倍数了（在这里是8 / 2 = 4）。
5. 除完之后呢，我们的每个数也就减小了这个素数倍（这个例子就是变成了1,2,3,4）。再从这些数里面找出该素数（例子为2）的倍数。
6. 最后没有数了的时候（n = 0）把这些累加起来就是某一个素因子的个数。（这里简单来说就是：把1~n中的每一个数的该因子拿出来）

1. 首先就是预处理一个素数数组啦。
2. 第二就是二分查找答案。
3. 接下来就是按照我们上面的操作对项目进行二分操作。

#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;
}
//函数区

#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;
}

• 这道题不（wo）难（mei）发现是一道线性规划的题目。所以可以用我们高中的方法来求。

1. 根据题意，我们先得到他的线性方程组。（我们在这里假设第一种生产了m件，第二种生产了n件）。
   ---分割线---（横纵坐标为mOn）
2. 根据方程，我们可以得出右图的三种可能性，并可以依据此判断，分类讨论出我们的答案。
3. 首先两个单调曲线十分好求，由于我们求的是m+n的最大值。所以直接可以得到答案为截距向下取整。我们重点看相交的情况。
4. 相交时，我们相当于要求出交点的m和n值（不过m和n要取整，所以要考虑向上或向下取整哪个大）。
5. 所以我们就先求出该点的m值吧：此处因为求的是交点，所以可以直接将等式联立，就能得出：m = 1.0 * (4 * y - x) / 10。（此处m为浮点数）。
6. 然后就要对m的上取整数和下取整数求出对应的n值。（这里要考虑对应的是哪条直线：我们可以看图分辨m变大或变小时，哪条曲线在边界内）
7. 最后比较两种哪个大就好啦~（看代码）

1. 根据题目化简，还是假设第一种生产了m件，我们用换元法可以得到：ans = m + min((x - 2m) / 4, y - 3m)。
2. 根据三分法，我们就可以缩小该单峰区间的极值。然后缩小到一定范围之后，我们进行枚举，取出最大值就好了。

#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;
}
//函数区