周周练4

直接上题解
A:本题题意其实就是判断某个点走过一个环后该点的初始值和再一次访问的时候的值是否相同。

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define db double
const int MAXN = 1015;
const int MAXM = 10010;
const db eps = 1e-7;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

int e[MAXM<<1],ne[MAXM<<1],h[MAXN],idx; 
db cur[MAXN],C[MAXM<<1];

int N,M; bool vis[MAXN+1],flag;
inline void add(int u,int v,db w){
    e[++idx]=v; C[idx]=w; ne[idx]=h[u]; h[u]=idx;
}
inline void dfs(int k,double now){
    vis[k]=1,cur[k]=now; 
    for(int x=h[k];~x;x=ne[x]){
        int v=e[x]; db w=now*C[x];
        if(vis[v]){ 
            if(fabs(w-cur[v])>eps) flag=0; 
        }
        else dfs(v,w);
    }
}

int main(){
    int T=read();
    for(int Ca=1;Ca<=T;Ca++){
        memset(h,-1,sizeof(h)),idx=0;
        memset(vis,0,sizeof(vis));
        N=read(),M=read();
        for(int i=1;i<=M;i++){
            int x=read(),y=read(),xx=read(),yy=read();
            add(x,y,(db)yy/xx); add(y,x,(db)xx/yy);
        } 
        flag=1;
        for(int i=1;i<=N;i++) if(!vis[i]) dfs(i,1);
        printf("Case #%d: ",Ca);
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

B:
B题一开始没什么思路，暴力n2肯定会炸，所以不妨考虑每一位的贡献。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int MAXN=1e5+50,mod=1e9+7;
ll a[MAXN],b[MAXN],c[MAXN];
ll ca[35][2], cb[35][2];
int main(){
    int n; n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++){
        for(int j=0;j<=30;j++){
            ++ca[j][(a[i]>>j)&1];
            ++cb[j][(b[i]>>j)&1];
            c[i]+=(ca[j][1]*cb[j][0]+ca[j][0]*cb[j][1])<<j;  //
            c[i]%=mod;
        }
    }
    for(int i=1;i<=n;i++) cout<<c[i]<<" ";
}

C:c比较简单，找到每个素因子q，然后暴力找满足条件的n，使得n！能被q^k整除（q^k|p)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
int main(){
    int T; T=read();
    while(T--){
        int p; p=read();
        int ans=1;
        for(int i=2;i*i<=p;i++)
            if((p%i)==0) {
                int cnt=0;
                while((p%i)==0){
                    p/=i;cnt++;
                }
                int j=i;
                while(cnt>0){
                    int t=j;
                    while((t%i)==0){
                        t/=i; cnt--;
                    }
                    j+=i;
                }
                ans=max(ans, j-i);
            }
        if(p!=1) ans = max(ans, p);
        printf("%d\n", ans);
    }
    return 0;
}

D.具体证明不会。 打表发现 >1 的时候先手总能胜利（代码简单略）
E.满足三分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
const int Maxn=5e5+10;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int x,y;
int check(int n){
    return n+min((x-2*n)/4,y-3*n);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        int l=0,r=min(x/2,y/3);
        while(l<r){
            int mid1=l+(r-l)/3;
            int mid2=r-(r-l)/3;
            if(check(mid1)>check(mid2))r=mid2-1;
            else l=mid1+1;
        }
        printf("%d\n",check(l));
    }
    return 0;
}