Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

银联高校极客挑战赛 初赛 第一场

congmingyige 2019-07-20 16:30:00 阅读数:131 评论数:0 点赞数:0 收藏数:0

 

文章发表于比赛之后。。。

(之前是没有选发表,然后比赛后再按了发表)

 

 

A. 码队女朋友的王者之路

不满足打满全场的情况

判断前2个赛季(第2个赛季开始,值为负数;若还有第3个赛季,它的值比第2个赛季开始的时候更小)

 

满足打满全场的情况

最后部分场次可以不打

 

所以都要考虑两个赛季的情况

 

 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <string>
 #include <algorithm>
 #include <iostream>
 using namespace std;
 #define ll long long
 
 const double eps=1e-;
 const ll inf=1e9;
 const ll mod=1e9+;
 const int maxn=3e2+;
 
 ll a[maxn];
 
 int main()
 {
     ll n,m,k,g,t,i,j,r,x,y,z,win;
     char c;
     scanf("%lld",&t);
     while (t--)
     {
         scanf("%lld%lld%lld\n",&n,&k,&m);
         g=;
         for (i=;i<=n;i++)
         {
             scanf("%c",&c);
             if (c=='')
             {
                 g++;
                 a[i]=;
             }
             else
                 a[i]=;
         }
         for (i=n+;i<=n*;i++)
             a[i]=a[i-n];
         for (i=*n+;i<=n*;i++)
             a[i]=a[i-n*];
         if (g==)
             printf("0\n");
         else
         {
             win=,j=,r=;
             for (i=;i<=min(2ll,m)*n;i++)
             {
                 if (i%n==)
                     j+=k;
 
                 if (a[i])
                     win++;
                 else if (j>)
                     j--;
                 else
                     win--;
                 r=max(r,win);
             }
             if (m<= || g<(n-g)-k)
                 printf("%lld\n",r);
             else
                 printf("%lld\n",(m-)*( g - max((n-g)-k,0ll)  ) +  r);
 
         }
     }
     return ;
 }
 /**
  5 2 5
 11000
 
 7 2 5
 1100000
 
 7 2 5
 0000011
 **/

 

B. 自学图论的码队弟弟

判断环

dfs 记录路径&是否访问过

环:position x~position y

 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <string>
 #include <algorithm>
 #include <iostream>
 using namespace std;
 #define ll long long
 
 const double eps=1e-;
 const ll inf=1e9;
 const ll mod=1e9+;
 const int maxn=1e5+;
 
 struct node
 {
     int d,len;
     node *to;
 }*e[maxn],*findlen[maxn];
 
 int a[maxn],b[maxn],ind[maxn],v[maxn],root,fa[maxn];
 bool ifok,vis[maxn];
 
 void dfs(int d,int index)
 {
     if (ifok)
         return;
     vis[d]=;
     b[index]=d;
     ind[d]=index;
     node *p=e[d];
     while (p)
     {
         if (ifok)
             return;
         findlen[index]=p;
         if (!vis[p->d])
         {
             fa[p->d]=d;
             dfs(p->d,index+);
         }
         else if (p->d!=fa[d])
         {
             int i,j=ind[p->d];
             ll tot=,tot1=;
             for (i=j;i<=index;i++)
             {
                 p=findlen[i];
                 tot+=p->len;
                 if ((i-j)%==)
                     tot1+=p->len;
             }
 
             root=p->d;
             v[p->d]=tot/-tot1;
             ifok=;
             return;
         }
         p=p->to;
     }
 }
 
 void work(int d)
 {
     vis[d]=;
     node *p=e[d];
     while (p)
     {
         if (!vis[p->d])
         {
             v[p->d]=p->len-v[d];
             work(p->d);
         }
         p=p->to;
     }
 }
 
 int main()
 {
     node *p;
     int n,i,x,y,z;
     scanf("%d",&n);
     for (i=;i<=n;i++)
     {
         scanf("%d%d%d",&x,&y,&z);
         p=new node();
         p->d=y;
         p->len=z;
         p->to=e[x];
         e[x]=p;
 
         p=new node();
         p->d=x;
         p->len=z;
         p->to=e[y];
         e[y]=p;
     }
     dfs(,);
 
     memset(vis,,sizeof(vis));
     work(root);
 
     for (i=;i<=n;i++)
         printf("%d\n",v[i]);
     return ;
 }
 /*
  1 2 2
 2 3 2
 3 4 2
 4 5 2
 5 1 2
 
  1 2 1
 2 3 3
 3 4 4
 4 2 5
 5 3 100
 6 4 2
 */

 

 

C. 折扇染色

对于x-1,x扇形:

分成1~x-2,x+1~n两部分

 

对于下一个扇形x,x+1

分成

1-~x-2 到它

 

x+1到它

x+2~n到它

 

而x+1~n这部分,对于任意的数字,它们的情况都是一样的(在这之前,没有约束)

 

 

 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <string>
 #include <algorithm>
 #include <iostream>
 using namespace std;
 #define ll long long
 
 const double eps=1e-;
 const ll inf=1e9;
 const ll mod=1e9+;
 const int maxn=5e5+;
 
 ll ch[maxn],fan_ch[maxn],rev[maxn];
 
 ll mul(ll a,ll b)
 {
     ll y=;
     while (b)
     {
         if (b&)
             y=y*a%mod;
         a=a*a%mod;
         b>>=;
     }
     return y;
 }
 
 int maxv=5e5;
 
 int main()
 {
     int t;
     ll n,m,i,a,b,aa,bb,c,d,x;
     ch[]=;
     for (i=;i<=maxv;i++)
         ch[i]=ch[i-]*i%mod;
     fan_ch[maxv]=mul(ch[maxv],mod-);
     for (i=maxv;i>=;i--)
     {
         fan_ch[i-]=fan_ch[i]*i%mod;
         rev[i]=fan_ch[i]*ch[i-]%mod;
     }
     rev[]=;
 
     scanf("%d",&t);
     while (t--)
     {
         scanf("%lld%lld",&n,&m);
 
         ///x=1
         a=;
         b=m-+;
         for (x=;x<n;x++)
         {
             c=b*rev[m-(x+)+]%mod;
             d=c*(m-(x+)+-)%mod;
             aa=(a*(x--)       + c*(x-) + d*(x-))%mod;
             bb=(a*(m-(x+)+) + c*(m-(x+)+) + d*(m-(x+)+-))%mod;
 
             a=aa;
             b=bb;
         }
 
         ///P(m,n)
         printf("%lld\n",(a+b)%mod*ch[m]%mod*fan_ch[m-n]%mod);
     }
     return ;
 }

 

版权声明
本文为[congmingyige]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/cmyg/p/11218195.html