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 阅读数:208 评论数: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