西南民族大学 校赛Day2

传送门

写在最前面,这题目名字起的,我给满分!!!真的棒!!!

题目思路

A人生如戏–Const

二分答案,拆点做最大流
每个人拆成两个点,一个点用来连合作过的所有人,另一个点连没有合作过的所有人
源点向所有男生“合作过的点”引边,女生“合作过的点”向汇点引边,流量为当前的答案值即场次
男生“合作过的点”向“未合作过的点”引边,女生“未合作过的点”向“合作过的点”引边,流量为限制K
对于所给矩阵,若$Dij=Y$则i男向j女“合作过的点”引容量为1的边,反之在“未合作过的点”之间引边
最后得到最大流为场次乘以人数即存在可行解

B回忆如糖

稍微研究一下,我们发现弟弟的不进位加法本质是xor(异或 ^)

P.S.一开始看成or了死活不会我真的是。。。

下面有一些关于异或的有趣性质,主要有两个

x^x=0,(x^y)^x=y

于是我们观察到,如果存在题目要求的分组,那么所有糖果的值的xor和必然是0!!!

这个作为有无解的判据就好了~

然后其实所有糖都给哥哥好像也满足条件,不过看题目我们出于人道主义考虑,好像要至少给弟弟一块糖

那么给弟弟最小的值就好了,坏哥哥!

C战功如雨

主要是看在前一个时辰是否存在某种射箭方案,使得命中率刚好为pd

这个算一下满足条件的最小值看看是否小于等于前一小时的射箭数即可

然后pd和pg为0和100的时候需要特判,就酱

D江山如画

这题好像当时没人过,然后我的正确代码被卡了常数QAQ,预处理之后AC

一眼看出正解(害羞,捂脸)

这是一个板题+结论题

由于树已经给定不会改变,同时查询仅需要查询任意两点间距离

因此我们使用LCA中最快的ST表方案

同时还有一个结论,比较不可描述

我第一次见到是在2016北京的网络赛->传送门

我们需要查询树上某些点之间的最大距离,可以进行如下做法

设x,y为这些点中最长距离的两个端点

首先任取两个点作为x,y

对于剩下的点,每一次取一个z,比较dis(x,y),dis(x,z) ,dis(y,z)

取这三个值的最大值,用对应的端点更新x和y即可

E料事如神

我们将1-n分为几部分来考虑

第一部分:质数,显然要全取,不然验不出来

第二部分:质数的幂,也需要全取,不然同样验不出来

第三部分:剩余合数,考虑任意合数的唯一分解定理,均可以被验出来,所以不用取

自此,本题思考就结束了

我的做法很黄很暴力QAQ

用欧拉筛暴力筛取1e7以内的质数,并暴力添加了所有质数不超过1e7的幂

然后暴力排序

然后对于每个询问,暴力二分,使得$a_k<=n<a_{k+1}$,那么$k$即为答案

F风雨如磐

一个比较好的概率dp

假设$a_{i,j,0}$表示在剩余$i$张雨牌$j$张风牌时当前人取到风牌的概率,$a_{i,j,1}$表示取到雨牌的概率

分情况讨论,递推即可

G湖光如镜

我认为是本场最水的题,可以算是签到题

暴力维护每个1的横纵坐标最大最小值

然后在这个区间内检查是不是所有的数都是1即可

AC代码(不写头文件)

A人生如戏–Const

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 205
#define maxm 200005
#define rever(x) (mem+((x-mem)^1))
struct edge
{
int s,t,v;
edge* next;
}mem[maxm*2],*head[maxn];
int cnt=-1;
void add_edge(int s,int t,int v)
{
mem[++cnt].s=s;mem[cnt].t=t;mem[cnt].v=v;mem[cnt].next=head[s];head[s]=mem+cnt;
mem[++cnt].s=t;mem[cnt].t=s;mem[cnt].v=0;mem[cnt].next=head[t];head[t]=mem+cnt;
}
int n,m;

int S,T;
int numbs[maxn];
int d[maxn];
edge* cur[maxn],*revpath[maxn];

void bfs()
{
queue<int> q;
while(!q.empty()) q.pop();
for (int i=0;i<=n;i++) d[i]=maxn-1;
d[T]=0;q.push(T);
while(!q.empty())
{
int u=q.front();
q.pop();
for (edge* it=head[u];it;it=it->next)
{
edge *now=rever(it);
if (now->v==0||d[now->s]<n) continue;
d[now->s]=d[u]+1;
q.push(now->s);
}
}
memset(numbs,0,sizeof(numbs));
for (int i=0;i<=n;i++) numbs[d[i]]++;
}

int isap()
{
int flow=0;
for (int i=0;i<=n;i++) cur[i]=head[i];
int u=S;
while(d[S]<n)
{
if (u==T)
{
int augflow=2147483647;
for (int i=S;i!=T;i=cur[i]->t)
augflow=min(augflow,cur[i]->v);
for (int i=S;i!=T;i=cur[i]->t)
{
cur[i]->v-=augflow;
rever(cur[i])->v+=augflow;
}
flow+=augflow;u=S;
}
edge *e;
for (e=cur[u];e;e=e->next)
if (e->v&&d[u]==(d[e->t]+1)) break;
if (e)
{
cur[u]=e;
revpath[e->t]=rever(e);
u=e->t;
}
else
{
numbs[d[u]]--;
if (numbs[d[u]]==0) break;
cur[u]=head[u];
int mindist=n;
for (edge* it=head[u];it;it=it->next)
if (it->v) mindist=min(mindist,d[it->t]);
d[u]=mindist+1;
numbs[d[u]]++;
if (u!=S) u=revpath[u]->t;
}
}
return flow;
}
int N,K;
char dat[60][60];
bool check(int now)
{
cnt=-1;memset(head,0,sizeof(head));
for (int i=1;i<=N;i++) {add_edge(S,i,now);add_edge(i+2*N,T,now);}
for (int i=1;i<=N;i++) {add_edge(i,i+N,K);add_edge(i+3*N,i+2*N,K);}
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
if (dat[i][j]=='Y') add_edge(i,j+2*N,1);
else add_edge(i+N,j+3*N,1);
bfs(); return isap()==N*now;
}
int main()
{
scanf("%d%d",&N,&K);
for (int i=1;i<=N;i++) scanf("%s",dat[i]+1);
S=0;T=4*N+1;n=T;
int L=0,R=50;
while(R-L>1)
{
int M=(L+R)>>1;
if (check(M)) L=M;
else R=M;
}
if (check(L)) printf("%d",L);
else printf("%d",R);
return 0;
}

B回忆如糖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int i,n,T,t,mi,sum,x,tot;

int main()
{
scanf("%d",&T);
for(t=1;t<=T;t++)
{
tot=sum=0;mi=10000005;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
if(x<mi)mi=x;
tot^=x;sum+=x;
}
printf("Case #%d: ",t);
if(tot!=0)printf("NO\n");else printf("%d\n",sum-mi);
}
return 0;
}

C战功如雨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long LL;

int T,t;
LL n,pd,pg;

LL gcd(LL x,LL y)
{
if(y==0)return x;else return gcd(y,x%y);
}

int main()
{
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%lld %lld %lld",&n,&pd,&pg);
printf("Case #%d: ",t);
if(100/gcd(100,pd)>n){printf("Broken\n");continue;}
if(pg==100 && pd!=100){printf("Broken\n");continue;}
if(pd>0 && pg==0){printf("Broken\n");continue;}
printf("Possible\n");
}
return 0;
}

D江山如画

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
const int maxn=200005;

vector<int> mz[maxn/2];
struct node
{
int dep,fat;
vector<int> son;
}tr[maxn];

int dfn[2*maxn],a[maxn];
int st[2*maxn][20];
int i,j,k,l,m,n,u;
int loo[1000005];

void dfs(int x)
{
a[++u]=x;
int temp=u;
st[++l][0]=temp;
dfn[x]=l;
tr[x].dep=tr[tr[x].fat].dep+1;
for(unsigned int t=0;t<tr[x].son.size();t++)
{
dfs(tr[x].son[t]);
st[++l][0]=temp;
}
}

void mkST()
{
for(int i=1;(1<<i)<=l;i++)
for(j=1;j<=l-(1<<i)+1;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}

int find(int x,int y)
{
if(x>y){int temp=x;x=y;y=temp;}
int j=loo[y-x+1];
return min(st[x][j],st[y-(1<<j)+1][j]);
}

int search(int x,int y)
{
int z=find(dfn[x],dfn[y]);
return tr[x].dep+tr[y].dep-2*tr[a[z]].dep;
}

int main()
{
loo[1]=0;loo[2]=1;
for(i=3;i<=1000000;i++)loo[i]=loo[i/2]+1;
scan2(n,m);
for(i=1;i<=n;i++)
{
scan2(j,k);
tr[i].fat=k;
tr[k].son.push_back(i);
mz[j].push_back(i);
}
l=0;
for(i=1;i<=n;i++)if(tr[i].fat==0){dfs(i);break;}
mkST();
for(i=1;i<=m;i++)
{
int p=mz[i][0];
int q=mz[i][1];
for(unsigned int t=2;t<mz[i].size();t++)
{
int e=mz[i][t];
int s1=search(p,e);
int s2=search(q,e);
int s=search(p,q);
if(s1<=s && s2<=s)continue;
if(s1>s2)q=e;else p=e;
}
printf("%d\n",search(p,q));
}
return 0;
}

E料事如神

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#define MAXN 10000001
int minFactor[MAXN];
int prime[2000000], primeNum;
void calPrime()
{
for (int i = 2; i < MAXN; i++){
if (!minFactor[i]){
prime[primeNum++] = i;
minFactor[i] = primeNum;
}
for (int j = 1; j <= minFactor[i]; j++){
int t = i * prime[j - 1];
if (t >= MAXN)break;
minFactor[t] = j;
}
}
}

int a[MAXN/2];
int i,j,k,m,n;

int main()
{
primeNum=0;m=0;
calPrime();
for(i=0;i<primeNum;i++)
{
LL t=prime[i];
while(t<MAXN)
{
a[++m]=t;
t=(LL)t*prime[i];
}
}
sort(a+1,a+m+1);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&k);
int l=1,r=m;
while(r-l>1)
{
int mid=(l+r)>>1;
if(a[mid]<=k)l=mid;else r=mid;
}
if(a[l+1]<=k)l++;
if(a[l]>k)l--;
printf("Case #%d: %d\n",i,l);
}
return 0;
}

F风雨如磐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
double a[1005][1005][2];
int i,j,k,l,m,n;
double sum=1,ans=0,tot=0;

int main()
{
scan2(n,m);
memset(a,0,sizeof(a));
if(n==0){printf("0.00000000");return 0;}
if(m==0){printf("1.00000000");return 0;}
a[n][m][1]=(double)(n)/(double)(n+m);
a[n][m][0]=1.0-a[n][m][1];
ans+=a[n][m][1];
for(k=n+m-1;k>=1;k--)
{
//sum-=tot;tot=0;
for(i=min(n,k);i>=1;i--)
{
j=k-i;
if(j>m)break;
double kk=k,ii=i;
if((n+m-k)%3==0)
{
if(i+1<=n)
a[i][j][1]+=a[i+1][j][1]*(ii/kk),a[i][j][0]+=a[i+1][j][1];
if(j+1<=m)
a[i][j][1]+=a[i][j+1][0]*(ii/kk),a[i][j][0]+=a[i][j+1][0];
}else
{
if(j+1<=m)
a[i][j][1]+=a[i][j+1][0]*(ii/kk),a[i][j][0]+=a[i][j+1][0];
}
a[i][j][0]-=a[i][j][1];
if((n+m-k)%3==0)ans+=a[i][j][1];
if((n+m-k)%3==1)tot+=a[i][j][1];
}
}
//for(i=1;i<=n;i++)
// for(j=0;j<=m;j++)
// if((n+m-i-j)%3==0)ans+=a[i][j];
printf("%.8lf",ans);
//printf("\n%.8lf",tot);
return 0;
}

G湖光如镜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int a[55][55];
int i,j,u,d,l,r,n;
int t,T;

void read(int &x)
{
char c;
while(scanf("%c",&c)==1 && !(c=='0' || c=='1'));
x=c-48;
}

int main()
{
scan(T);
for(t=1;t<=T;t++)
{
u=l=100;d=r=0;
scan(n);
bool f=true;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
read(a[i][j]);
if(a[i][j]>0)
{
u=min(i,u);d=max(i,d);
l=min(j,l);r=max(j,r);
}
}
for(i=u;i<=d && f;i++)
for(j=l;j<=r;j++)
if(a[i][j]==0){f=false;break;}
prr(t);
if(f)printf("Yes\n");else printf("No\n");
}
return 0;
}