本文共 6260 字，大约阅读时间需要 20 分钟。

差8秒AK啊  气人

A-[SDOI2016]齿轮

题意：

做法：设1节点是1/1  然后按照比例算出其他节点，保存分子、分母节点即可。当遇到之前遍历过的点，就用当前转换一下，能否得到这点的fz/fm

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}const int N=1e3+10;int vis[N];int n,m,flag;struct node{    ll fz,fm;}dfn[N];struct edge{    int v;    ll x,y;};vector
     
      G[N];pair
      
       p1,p2;void dfs(int u,int fa){    //printf("u:%d fa:%d\n",u,fa);    if(!flag) return;    for(auto now:G[u]){        if(now.v==fa) continue;        if(vis[now.v]){            pair
       
        p1,p2;            p1=make_pair(dfn[u].fz,dfn[u].fm);            p2=make_pair(dfn[now.v].fz,dfn[now.v].fm);            p1.first*=now.y;            p2.first*=now.x;            ll gc=gcd(p1.first,p1.second); p1.first/=gc;p1.second/=gc;               gc=gcd(p2.first,p2.second); p2.first/=gc;p2.second/=gc;//            if(p1.second<0) p1.second=-p1.second,p1.first=-p1.first;            if(p2.second<0) p2.second=-p2.second,p2.first=-p2.first;            //printf("v:%d 重复拜访 p1.f :%lld p1.se:%lld\n",now.v,p1.first,p1.second);            //printf("u:%d 重复拜访 p2.f :%lld p2.se:%lld\n",u,p2.first,p2.second);            if(p1!=p2){                //printf("u:%d v:%d\n",u,now.v);                flag=0;                return ;            }            continue;        }        vis[now.v]=1;        pair
        
         p1=make_pair(dfn[u].fz*now.y,dfn[u].fm*now.x); //printf("fz:%lld y:%lld fm:%lld x:%lld\n",dfn[u].fz,now.y,dfn[u].fm,now.x); ll gc=gcd(p1.first,p1.second); p1.first/=gc;p1.second/=gc; if(p1.second<0) p1.second=-p1.second,p1.first=-p1.first; //printf("v:%d p1.f:%lld p1.se:%lld\n",now.v,p1.first,p1.second); dfn[now.v]={p1.first,p1.second}; dfs(now.v,u); }}void solve(int cas){ scanf("%d%d",&n,&m); rep(i,1,n) { G[i].clear();vis[i]=0; } for(int i=1;i<=m;++i){ int u,v; ll x,y; scanf("%d%d%lld%lld",&u,&v,&x,&y); G[u].push_back({v,x,y}); G[v].push_back({u,y,x}); } printf("Case #%d: ",cas); flag=1; vis[1]=1; dfn[1]={1,1}; dfs(1,-1);// for(int i=1;i<=n;++i){// printf("i:%d fz:%lld fm:%lld\n",i,dfn[i].fz,dfn[i].fm);// } if(flag) puts("Yes"); else puts("No");}int main(){ int cas=0; int _;cin>>_;while(_--){ solve(++cas); }}/*103 31 2 3 52 3 5 -71 3 3 7*/
        
       
      
     
    
   

B-Rinne Loves Xor

题意：

做法：

经典的异或题了，保存前面每个位置 0  或是 1 的个数，然后当前a[i] 就去  j<i 的32 位中找与当前a[i] 某一个二进制下相反的位数 的个数

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}const int N=1e5+10;const ll mod=1e9+7;ll a[N],b[N],c[N],pa[40][2],pb[40][2];int n;void add(ll &x,ll y){    x=(x+y)%mod;}ll print(ll x){    stack
     
      sta;    while(x)sta.push(x%2),x=x/2;while(sta.size()<30) sta.push(0);    while(sta.size()) printf("%d",sta.top()),sta.pop();    puts("");}void solve(){    cin>>n;    rep(i,1,n) scanf("%lld",&a[i]);    rep(i,1,n) scanf("%lld",&b[i]);    c[1]=a[1]^b[1];    ll v;    v=a[1];for(int j=0;j<=30;++j) pa[j][v&1]++,v=v/2;    v=b[1];for(int j=0;j<=30;++j) pb[j][v&1]++,v=v/2;    //print(a[1]);    //print(b[2]);    rep(i,2,n)    {        c[i]=c[i-1];        add(c[i],(a[i]^b[i]));        ll v=a[i],now=1,ans=0;        for(int j=0;j<=30;++j){            add(ans,pb[j][1-(v&1)]*now%mod);            now=now*2;            v=v/2;        }        //printf("ans:%lld\n",ans);        v=b[i];now=1;ll res=0;        for(int j=0;j<=30;++j){            add(res,pa[j][1-(v&1)]*now%mod);            now=now*2;            v=v/2;        }        //printf("res:%lld\n",res);        v=a[i];for(int j=0;j<=30;++j) pa[j][v&1]++,v=v/2;        v=b[i];for(int j=0;j<=30;++j) pb[j][v&1]++,v=v/2;        add(c[i],ans);        add(c[i],res);    }    rep(i,1,n) printf("%lld ",c[i]);}int main(){	solve();}
     
    
   

C-阶乘

下面的p是某个素数

把p中唯一分解一下，求得 某个素数prime 和 num

相当于是求这个：

那我对于每一个素数二分得到合法的p  然后p中选取最大值即可。

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef int ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}ll powmod(ll a,ll b) {ll res=1;for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}ll n;ll getcnt(ll n,ll p){	ll ans=0;	ll base=p;	while(n>=p){		ans+=n/p;		p=p*base;	}	return ans;}int main(){	int _;cin>>_;while(_--)	{	    scanf("%lld",&n);	    if(n==1){printf("1\n");continue;}	    ll ans=0;	    for(ll i=2;i*i<=n;++i){            if(n%i==0){                ll num=0;                while(n%i==0) ++num,n=n/i;                ll l=1,r=1e9;                ll ans1=0;                while(l<=r){                	ll mid=l+r>>1;                	ll t=getcnt(mid,i);                	if(t>=num)  ans1=mid,r=mid-1;                	else l=mid+1;				}				ans=max(ans,ans1);            }	    }	    if(n!=1) ans=max(ans,n);	    printf("%lld\n",ans);	}	return 0;}
    
   

D-小石的签到题

博弈

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_backusing namespace std;typedef long long ll;const int N=1e5+10;int main(){    int x;    cin>>x;    int f=x%2;         if(x==1) printf("Yang\n");    else printf("Shi\n");}
   

E-装备合成

三分水题，三分 第一种方案的数量，然后随便搞搞

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}const int N=2e5+10;int x,y,mi,ans; int cal(int num,int x,int y){    return num+min((x-2*num)/4,y-3*num); }int main(){    int _;cin>>_;while(_--)    {        scanf("%d%d",&x,&y);         int l=0,r=min(x/2,y/3),ans;        while(l+10<=r)        {            int m1=l+r>>1,m2=m1+r>>1;            if(cal(m1,x,y)>=cal(m2,x,y)) r=m2-1,ans=m1;            else l=m1+1;        }        int m1=ans;         //printf("m1:%d\n",m1+min(x-2*mi,y-3*mi));         int res=0;        for(int i=l;i<=r;i++)        res=max(res,i+min((x-2*i)/4,y-3*i));         printf("%d\n",res);    }}
    
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/105824793 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！