noip2014题解-白红宇

noip2014题解

阅读量：5030 次

发布时间：2019-06-12

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

没有正解都是我的暴力

T1生活大爆炸版石头剪刀布

把得分要求存进C数组里

c[i][j]表示i对j的得分情况

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define LL long long#define N 202using namespace std;int n,na,nb;int a[N],b[N],c[10][10];int A,B;void rule_(){ /* 0--剪刀 1--石头 2--布 3--蜥蜴人 4--斯波克 */ for(int i=0;i<=4;i++) c[i][i]=0; c[0][1]=0;c[0][2]=1;c[0][3]=1;c[0][4]=0; c[1][0]=1;c[1][2]=0;c[1][3]=1;c[1][4]=0; c[2][0]=0;c[2][1]=1;c[2][3]=0;c[2][4]=1; c[3][0]=0;c[3][1]=0;c[3][2]=1;c[3][4]=1; c[4][0]=1;c[4][1]=1;c[4][2]=0;c[4][3]=0;}void play_(){ for(int i=1;i<=n;i++) { int xa,xb; xa=i%na;if(!xa) xa=na; xb=i%nb;if(!xb) xb=nb; A=A+c[a[xa]][b[xb]]; B=B+c[b[xb]][a[xa]]; }}int main(){/// freopen("rps.in","r",stdin);/// freopen("rps.out","w",stdout); scanf("%d%d%d",&n,&na,&nb); for(int i=1;i<=na;i++) scanf("%d",&a[i]); for(int i=1;i<=nb;i++) scanf("%d",&b[i]); rule_(); play_(); printf("%d %d\n",A,B);// fclose(stdin);// fclose(stdout); return 0;}/*10 5 60 1 2 3 40 3 4 2 1 09 5 50 1 2 3 41 0 3 2 4*/

100

T2联合权值

30% O(n^3)floyed求两点距离+n^2枚举

60% LCA求两点距离+n^2枚举

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define LL long long#define N 2020#define M 10007using namespace std;int n;int sumedge;int head[N],w[N];int size[N],deep[N],dad[N],top[N];int dis[103][103];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct Edge{ int x,y,nxt; Edge(int x=0,int y=0,int nxt=0): x(x),y(y),nxt(nxt){}}edge[N<<1];void add(int x,int y){ edge[++sumedge]=Edge(x,y,head[x]); head[x]=sumedge;}void slove1(){ int max_,res;max_=res=0; memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;i++) dis[i][i]=0; for(int i=1;i
             
              size[s]) s=v; } if(s) { top[s]=top[x]; dfs_(s); } for(int i=head[x];i;i=edge[i].nxt) { int v=edge[i].y; if(v!=dad[x]&&v!=s)dfs_(v); }}int LCA(int x,int y){ if(deep[x]>deep[y]) swap(x,y); for(;top[x]!=top[y];) { if(deep[top[x]]>deep[top[y]]) swap(x,y); y=dad[top[y]]; } if(deep[x]>deep[y]) swap(x,y); return x; }void slove2(){ int max_,res;max_=res=0; for(int i=1;i

T3飞扬的小鸟

加卡时35不加30....

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define LL long long#define N 10005using namespace std;int n,m,k,js;int ans_z,ans_c;int X[N],Y[N];bool bo[N]; struct A{ int x,l,r;}a[N];struct B{ int l,r;}b[N];bool cmp(A a,A b){ return a.x
             
              400000) { if(ans_c==k) { printf("1\n"); printf("%d\n",ans_z); }else { printf("0\n"); printf("%d\n",ans_c); } // fclose(stdin);fclose(stdout); exit(0); }*/ ans_c=max(ans_c,c);//更新通过的最多的管子数 if(x==n) //已经到达终点 { ans_z=min(ans_z,z); return ; } if(bo[x+1]) { int nxty;nxty=y-Y[x]; if(nxty>b[x+1].l&&nxty
              
               b[x+1].l&&nxty
               
                0) dfs(x+1,nxty,c,z); for(int i=1;i<=3;i++) { int nxty;nxty=y+X[x]*i; dfs(x+1,min(nxty,m),c,z+i); } } return ;}int main(){// freopen("birda.in","r",stdin);// freopen("birda.out","w",stdout); scanf("%d%d%d",&n,&m,&k);/*长、高、水管数量 */ for(int i=0;i