木有闲话qwq

A.[SDOI2016]齿轮

看到名字，发现是2016省选题，于是先放着打后面去了，然而，后来发现贼简单？？？

只需要判断下各个边给出的约束条件是否有矛盾就行。我们可以考虑下稍微简化的版本:

给出m个约束条件，每个条件是u比v小x，求是否有矛盾。

对于这个题，我们可以直接令一个点为0，然后，根据这个点和其他点的关系推出其他点的值就行了，中途判断是否矛盾即可。

而这个题，仅仅是给的条件变成了u是v的x倍而已。

于是，我们另一个点为1(因为要转动，不能是0嘛)，然后跟上面一样的做法即可

不过，有可能有些点不在同一个连通块，对于不同连通块我们分别判断即可~

#include<bits/stdc++.h>
using namespace std;
const int N=1001,M=1e4+1;
const double eps=1e-3;
struct node{
    int v,x,y,nex;
}t[M<<1];
int len,las[N];
double dis[N];
bool vis[N];
inline void add(int u,int v,int x,int y){
    t[++len]=(node){v,x,y,las[u]},las[u]=len;
}
inline bool check(double x,double y){
    return fabs(x-y)<=eps;
}
inline bool dfs(int x){
    vis[x]=1;
    for(int i=las[x];i;i=t[i].nex){
        int v=t[i].v;double a=t[i].x,b=t[i].y;
        double res=(dis[x]/a)*b;
        if(!vis[v]){
            dis[v]=res;
            if(!dfs(v)){
                return false;
            }
        }else{
            if(!check(res,dis[v])){
                return false;
            }
        }
    }
    return true;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ti=1;ti<=T;++ti){
        int n,m;memset(las,0,sizeof(las)),len=0;
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            int u,v,x,y;
            scanf("%d%d%d%d",&u,&v,&x,&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: ",ti);
        if(!flag){
            puts("No");
        }else{
            puts("Yes");
        }
    }
    return 0;
}

B.Rinne Loves Xor

发现前面一节其实就是个常数，我们先不管它，我们着重看后面那个求和

因为后面两个是个等价的问题，我们只考虑其中一个怎么做

其实就是等价于求:

(两个问题是等价的，只是表示方法不同罢了)

对于这个问题，第一反应是搞个前缀和，然而，异或之和并不等于和的异或，所以，是错的

这样的话，我们就可以考虑另一个套路——按位计算

我们计算每一位的贡献即可。

对于二进制的第k位，如果的第k位为0,那么，对于前面所有的第k位为1的，都会给答案提供一个的贡献，而这个是可加的，同理，如果的第k位为1，我们只需统计第k为0的个数即可，计算完贡献后再统计一下就可以了

会算这个后，我们就可以等价的计算题目的式子了~

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,mod=1e9+7;
int a[N],b[N],c[N];
int A[30][2],B[30][2];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    c[0]=0;
    for(int i=1;i<=n;++i){
        c[i]=(c[i-1]+(a[i]^b[i]))%mod;
        for(int j=29;~j;--j){
            c[i]=(c[i]+(1LL*B[j][((a[i]>>j)&1)^1]*(1<<j))%mod)%mod;
            c[i]=(c[i]+(1LL*A[j][((b[i]>>j)&1)^1]*(1<<j))%mod)%mod;
            ++A[j][((a[i]>>j)&1)];++B[j][((b[i]>>j)&1)];
        }
        printf("%d ",c[i]);
    }
    return 0;
}

C.阶乘

这题有两种解法，不过都需要对p进行质因数分解

对于质因数分解，一般我们有两种做法:

1.

2.

当然还有其他很多的比如Pollard Rho，但这并不在我们讨论之中

考虑到数据范围

如果,我们使用预处理的话，则会超时，所以，我们考虑使用第2种也是最简朴的那种算法——枚举质因子

由于太简单了，就不再说明，不会的可以看代码qwq

我们假设分解完后（这里使用的是一般的表示方法,指的一个质数和前面的p不同）

那么，我们对于每一组的我们计算出最小的一个Ki使得Ki的阶乘是的倍数，答案取最大的即可（因为每组质因数之间没有关联）

那么，现在就是如何求这个了。

方法一——二分

注意到，明显满足二分性，那么，我们只需要求出二分的一个数字x的阶乘可以分解为多少个相乘即可，结论是:

这里就不再推导，不清楚的童鞋可以自行推导下，挺简单的

然后，我们算出了有多少个后，和比较下大小即可

方法二——暴力枚举

因为对的个数有影响的只有的倍数，所以我们可以暴力枚举的倍数，直到枚举出的的所有倍数分解出的的个数大于等于即可

但是，复杂度为啥是对的？

我们分析下:

因为是指数,而至少为2，所以，的大小是log级别的

所以，我们每次最多枚举log个倍数即可算出答案了

代码:

方法一:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int sav[N],tot[N],e;
inline bool check(int x){
    for(int i=1;i<=e;++i){
        int y=x,res=0;
        while(y){
            res+=(y/sav[i]);
            y/=sav[i];
        }
        if(res<tot[i]){
            return false;
        }
    }
    return true;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int p;e=0;
        scanf("%d",&p);
        for(int i=2;i<=sqrt(p);++i){
            if(p%i==0){
                sav[++e]=i;tot[e]=0;
                while(p%i==0){
                    ++tot[e];p/=i;
                }
            }
        }
        if(p>1){
            sav[++e]=p;tot[e]=1;
        }
        int l=1,r=1e9,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                r=mid-1;ans=mid;
            }else{
                l=mid+1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

方法二:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int sav[N],tot[N],e;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int p;e=0;
        scanf("%d",&p);
        for(int i=2;i<=sqrt(p);++i){
            if(p%i==0){
                sav[++e]=i;tot[e]=0;
                while(p%i==0){
                    ++tot[e];p/=i;
                }
            }
        }
        if(p>1){
            sav[++e]=p;tot[e]=1;
        }
        int ans=1;
        for(int i=1;i<=e;++i){
            int rep=0;
            for(int j=sav[i];;j+=sav[i]){
                int now=j;
                while(now%sav[i]==0){
                    ++rep;now/=sav[i];
                }
                if(rep>=tot[i]){
                    ans=max(ans,j);
                    break;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D.小石的签到题

咋看之下不可做，写个暴力规律过。。。

找规律发现只有n=1时Yang才会胜利，然后。。。就没然后了

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if(n==1){
        puts("Yang");
    }else{
        puts("Shi");
    }
    return 0;
}

E.装备合成

显然满足三分(感觉/x)，于是直接打个三分枚举用第一个方法造几次装备即可

（左端点记得为0，我因为这个挂了好久qwq）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
inline int calc(int x){
    int L=n-x*2,R=m-x*3;
    return x+min(L/4,R);
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        int l=0,r=min(n/2,m/3),ans=0;
        while(l<=r){
            int lc=l+(r-l)/3,rc=r-(r-l)/3;
            int res1=calc(lc),res2=calc(rc);
            ans=max(ans,max(res1,res2));
            if(res2<res1){
                r=rc-1;
            }else{
                l=lc+1;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}