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. 码队女朋友的王者之路

``` #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 记录路径&是否访问过

``` #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. 折扇染色

1-~x-2 到它

x+1到它

x+2~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 ;
}```

https://www.cnblogs.com/cmyg/p/11218195.html