牛客算法周周练4

闲话
A、B看了这位大佬的博客看懂的 $图片说明$ 传送门，B题我想化简，结果出了问题求助这位大佬，然后同学发现我多算了一个 $图片说明$ ，大佬也很快发现了，我自己找了半天，QAQ。
戳我传送

[SDOI2016]齿轮

题意：

n个齿轮m条链，链上两点u、v的转述比为x：y，若不同链条的传动比不相容，则有些齿轮无法转动，就输出no，反之yes。
图片说明
思路：

若不同链条的传动比不相容，则有些齿轮无法转动，意思是确定一个点后沿着链，根据题目输入的转速比确定其它点，当形成环时，会再次推到起点，若有矛盾就是不相容。真的题意后，就会想到以前的每日一题边的染色 （我的博客）和它的思路非常相似。
1.链式向前星存图。
2.对于任一连通块，假定一个点为1，通过这个点和其它点的关系退出其它点的值，推回来后判断是否矛盾就可以了。
3.因为可能有多个连通块，所以可能要多走几次。
Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1001,maxm=1e4+7;
const double eps=1e-3;
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 head[maxn],Next[maxm<<1],to[maxm<<1],x[maxm<<1],y[maxm<<1],tot;
void add(int u,int v,int a,int b) {
    to[++tot]=v;
    Next[tot]=head[u];
    x[tot]=a;
    y[tot]=b;
    head[u]=tot;
}
double dis[maxn];
bool vis[maxn];
bool dfs(int u) {
    vis[u]=1;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i]; double a=x[i],b=y[i];
        double res=(dis[u]/a)*b;
        if(!vis[v]) {
            dis[v]=res;
            if(!dfs(v)) return false;
        }
        else {
            if(fabs(res-dis[v])>eps) return false;
        }
    }
    return true;
}
int t,n,m,j;
int main() {
    read(t);
    while(t--) {
        read(n),read(m);
        memset(head,0,sizeof head);tot=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;++i){
            int u,v,x,y;
               read(u),read(v),read(x),read(y);
            add(u,v,x,y),add(v,u,y,x);
        }
        bool flag=1;
        for(int i=1;i<=n;++i){
            if(!vis[i]){
                dis[i]=1;
                if(!dfs(i)){
                    flag=0;
                    break;
                }
            }
        }
        printf("Case #%d: ",++j);
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

Rinne Loves Xor

题意：

求出图片说明

思路：

题目的式子可以化简，等价于求：
$图片说明$
1.对于这个问题，第一反应是用前缀和去做，但是异或之和并不等于和的异或，所以不可行。
2.其次经常想到的就是二进制---按位运算。
3. $图片说明$ 表示B数组从1遍历到 $图片说明$ 为止，第k位出现0的次数； $图片说明$ 表示B数组从1遍历到 $图片说明$ 为止，第k位出现1的次数。 $图片说明$ 也是类似的意思。
4. $图片说明$ 表示 $图片说明$ 二进制第k位的数字。
5.化简后的式子 $图片说明$ 和 $图片说明$ 的贡献是一样的， $图片说明$ 二进制第 $图片说明$ 位（假设这一位是0）的贡献就是 $图片说明$ 。
6.之后就不难了，输出不要"\n"。
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+1,mod=1e9+7;
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;
}
ll a[maxn],b[maxn],c[maxn],n;
ll A[30][2],B[30][2];
int main() {
    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) {
            ++A[j][(a[i]>>j)&1];
            ++B[j][(b[i]>>j)&1];
            c[i]+=(A[j][0]*B[j][1]+A[j][1]*B[j][0])<<j;
            c[i]%=mod;
        }
        printf("%lld ",c[i]);
    }
    return 0;
}

阶乘

思路：因为 p 高达 1e9 ，可以考虑唯一分解定理，分解之后我们单独讨论每个质因子。对于某个质因子 p[ i ] ，记录其在 p 中的出现次数 num[ i ] ，我们现在只需要找到一个最小的 k ，使得 k! 内含有大于等于 num[ i ] 个质因子p[ i ] 即可，然后每次维护一下 k 的最大值就是答案了。
那么怎么求k？
1.第一种思路是直接二分，因为这里的k明显具有单调性，对于每个二分答案只要计算[1,k]内p[i]的个数就行了。（还不会）
2.直接枚举，如果p的质因数全是2，那么最多也就30多个，所以所有的质因数的个数不会超过30多个，我们只要枚举j * p[i]，当j * p[i]中质因数p[i]的数量大于等于num[i]时就是一个答案，然后每次维护一下 k 的最大值就是最后的结果。
原理：（第二种思路）
1.分解出质因数比如2 * 3 * 3 * 3 * 5 * 5，枚举出来的答案是2、3 * 3，2 * 5，最终的结果显然是10，因为10！包括2！和9！，也就是满足质因数p[2]、p[3]的数量大于等于num[2]、num[3]。
2.上面的10怎么来的，因为只要质因数p[5]的倍数有质因数5，所有我们只要枚举i * p[5]，分离出每个i * p[5]中质因数5的个数temp，直到temp累加大于等于num[5]，这时的i * p[5]就是k，显然k!中一定含有num[5]个质因数5。
Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main() {
    int t,n,i,j,ans=0;
    js;
    cin>>t;
    while(t--) {
        cin>>n;
        ans=0;
        for(i=2;i*i<=n;++i) if(n%i==0) {
            int cnt=0;
            while(n%i==0) {
                n/=i;
                ++cnt;
            }
            int tmp=0;
            for(j=i;;j+=i) {
                for(int p=j;p%i==0;p/=i,++tmp);
                if(tmp>=cnt)    break;
            }
            ans=max(ans,j);
        }
        cout<<max(ans,n)<<endl;
    }
}

小石的签到题

思路：每个人必须要拿走一个数及其半数关系，只要数不为1就意味着拿的人都可以为对方制造拿的机会，每个人都会想方设法给对方制造拿的机会，这样也就是说先拿的人优势非常大，也就是说只要n!=1，先拿的人有决定输赢的机会。
Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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 n;
int main() {
    read(n);
    if(n!=1) printf("Shi\n");
    else printf("Yang\n");
}

装备合成

思路：
1.a特别多时，合成一件装备尽可能的多用a，也就是4a加b，因为假设a特别多，所以a>4 * b。
2.b特别多时，合成一件装备尽可能的多用b，也就是2
a加3b，因为假设b特别多，所以3 * a<2 * b。
3.a、b差不多时，发现总共要拿5个材料，且a要是偶数，所以假设可以和成的材料是（a+b）/5，这样是有可能多算一个的，就是当a不为偶数个且a+b恰好是5的倍数（比如1 4，3 2）。（前面都失配才考虑这个）
4.记得开ll，不然数据会溢出。a、b都是1e9的。
Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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 t;
ll a,b;
int main() {
    read(t);
    while(t--) {
        read(a),read(b);
        if(a>(b<<2)) printf("%lld\n",b);
        else if(a*3<(b<<1)) printf("%lld\n",(a>>1));
        else {
            ll sum=(a+b)/5;
            if(a&1&&(a+b)%5==0) --sum;
            printf("%lld\n",sum);
        }
    }
}