| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 8/13 | O | . | Ø | O | . | . | O | O | O | . | Ø | . | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A Rikka with Minimum Spanning Trees
题目描述
给一个随机数生成器生成一张图，问最小生成树乘上最小生成树的个数是多少。
解题思路
因为随机的是$64$位的边权，有两个最小生成树的可能极小，故直接$kruskal$即可。
AC代码
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
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
using namespace std;
int f[N];
ull k1, k2;
ull xorShift128Plus(){
ull k3=k1,k4=k2;
k1=k4;
k3^=k3<<23;
k2=k3^k4^(k3>>17)^(k4>>26);
return k2+k4;
}
int n,m,tot;
struct Edge{
int u,v;ull w;
bool operator<(const Edge&e)const{return w<e.w;}
}e[N<<2];
void gen(){
int i,u,v;ull w;
scanf("%d%d%llu%llu",&n,&m,&k1,&k2);
for(i=1;i<=m;i++){
u=xorShift128Plus()%n+1;
v=xorShift128Plus()%n+1;
w=xorShift128Plus();
if(u!=v)e[tot++]=(Edge){u,v,w};
}
}
int find(int x){
return x==f[x]?f[x]:f[x]=find(f[x]);
}
int main(){
int i,T;
scanf("%d",&T);
while(T--){
int cnt=0;tot=0;
ull ans=0,mod=1000000007;
gen();
sort(e,e+tot);
for(i=1;i<=n;i++)f[i]=i;
for(i=0;i<tot;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x!=y){
f[x]=y;cnt++;
ans=(ans+e[i].w%mod)%mod;
}
}
if(cnt==n-1)printf("%llu\n",ans);
else printf("0\n");
}
return 0;
}
B Rikka with Line Graphs
题目描述
解题思路
AC代码
2
C Rikka with Consistency
题目描述
给定一个折线段（共$n$段，$n\leq 50$），左端点在$(0,0)$，右端点在$(n,0)$，中间第$i$个点在$(n,hi)$。所有高度在$0-50$之间整数。
一开始，一个人$A$在左端点，一个人$B$在右端点。$A$要走到右端点，$B$要走到左端点，要求时时刻刻两个人的高度总保持一致。求最小总路程和。
解题思路
用一个三元组$(x,y,h)$保存第一个人位于$[x,x+1]$，第二个人位于$[y,y+1]$，两个人高度均为$h$时的最小总路程和，如果$[x,x+1]$区间线段高度相等，定义位于左端点。于是可以跑一边最短路。
AC代码
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
typedef long long ll;
using namespace std;
double dis[52][52][52],unit[52];
int h[52],vis[52][52][52];
struct Point{
double ds;
int x,y,z;
bool operator<(const Point&p)const{
return ds>p.ds;
}
};
Point Get(double a,int x,int y,int z){return (Point){a,x,y,z};}
priority_queue<Point>Q;
void get(double ds,int x,int y,int z){
if(dis[x][y][z]>ds){
dis[x][y][z]=ds;
Q.push(Get(ds,x,y,z));
}
}
int in(int h,int h1,int h2){
return h>=min(h1,h2)&&h<=max(h1,h2);
}
int main(){
int i,j,k,T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=50;k++)dis[i][j][k]=1e9;
for(i=0;i<=n;i++)scanf("%d",&h[i]);
for(i=1;i<=n;i++)
unit[i-1]=h[i]==h[i-1]?1:sqrt((h[i]-h[i-1])*(h[i]-h[i-1])+1.0)/fabs(h[i]-h[i-1]);
h[n+1]=-1e9;
dis[0][n][0]=0;
Q.push(Get(0,0,n,0));
while(!Q.empty()){
Point tmp=Q.top();Q.pop();
double ds=tmp.ds;
int x=tmp.x;
int y=tmp.y;
int z=tmp.z;
if(vis[x][y][z])continue;
vis[x][y][z]=1;
if(z==h[x]&&x>0)get(ds+(h[x]==h[x-1]),x-1,y,z);
if(z==h[x+1]&&x+1<=n)get(ds+(h[x+1]==h[x]),x+1,y,z);
if(z==h[y+1]&&y+1<=n)get(ds+(h[y+1]==h[y]),x,y+1,z);
if(z==h[y]&&y>0)get(ds+(h[y]==h[y-1]),x,y-1,z);
if(in(z-1,h[x],h[x+1])&&in(z-1,h[y],h[y+1]))get(ds+unit[x]+unit[y],x,y,z-1);
if(in(z+1,h[x],h[x+1])&&in(z+1,h[y],h[y+1]))get(ds+unit[x]+unit[y],x,y,z+1);
}
printf("%.15f\n",dis[n][0][0]);
}
return 0;
}
D Rikka with Subsequences
题目描述
给了一个$n\times n$的$01$矩阵$M$，还给了一个长度为$n$的序列$a_i$，$a_i\in [1,n]$。其中任意一个子序列，如果满足相邻的元素$a_i,a_j$满足$M_{a_ia_j}=1$，则被称作$Yuta$序列。
对于给定序列的每一个$Yuta$序列，统计出现的总数$cnt$，然后求$cnt^3$的和。
解题思路
先将$cnt^3$拆为计算三个完全相同的$Yuta$序列的选择个数。
设$f[j][k]$表示第一个序列选到$i$，第二个序列选到$j$，第三个序列选到$k$的、三个序列为相同的$Yuta$序列的种数。用前缀和优化，设$s[j][k]$代表选到$i$，且之前能完全对应匹配某个$l<i$，且能够与$i$匹配的二元组$(j,k)$个数，这里不需要考虑重复，因为$f[j][k]$会选择性地匹配。于是有$f[j][k]=s[j][k]+1$， $s[j][k]=s[j][k-1]+s[j-1][k]-s[j-1][k-1]+(M_{a[j-1]a[i]}==1?f[j-1][k-1]:0)$
AC代码
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
typedef long long ll;
using namespace std;
char m[210][210];
int a[210];
ll s[210][210],f[210][210],mod=1000000007;
int main(){
int i,j,k,T,n;
scanf("%d",&T);
while(T--){
ll ans=0;
memset(f,0,sizeof(f));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%s",m[i]+1);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
for(k=1;k<=n;k++){
if(m[a[j]][a[i]]=='1')s[j+1][k+1]=f[j][k];
else s[j+1][k+1]=0;
(s[j+1][k+1]+=s[j+1][k]+s[j][k+1]-s[j][k])%=mod;
}
}
for(j=1;j<=n;j++){
for(k=1;k<=n;k++){
if(a[i]==a[k]&&a[j]==a[k]){
(ans+=s[j][k]+1)%=mod;
(f[j][k]+=s[j][k]+1)%=mod;
}
}
}
}
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
E Rikka with Data Structures
题目描述
解题思路
AC代码
2
F Rikka with Nice Counting Striking Back
题目描述
解题思路
AC代码
2
G Rikka with Intersections of Paths
题目描述
给定一个$n$个节点的树和$m$个简单路，求有多少个选择$k$个给定简单路并使得这$k$个简单路交于同一点的方案。答案对$1e9+7$取模。
解题思路
AC代码
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
typedef long long ll;
using namespace std;
const int mod=1000000007;
int n,m;
struct Edge{
int e,n;
}e[N<<1];
int cnt;
int d[N],fa[22][N],lg[N],hd[N];
void add(int a,int b){
e[++cnt].e=b;
e[cnt].n=hd[a];
hd[a]=cnt;
}
void dfs(int now,int f){
d[now]=d[f]+1;
fa[0][now]=f;
int i;
for(i=1;(1<<i)<=d[now];i++)fa[i][now]=fa[i-1][fa[i-1][now]];
for(;i<22;i++)fa[i][now]=0;
for(i=hd[now];i;i=e[i].n){
int p=e[i].e;
if(p!=f)dfs(p,now);
}
}
int lca(int x,int y){
int i;
if(d[x]<d[y]){int t=x;x=y;y=t;}
while(d[x]>d[y])
x=fa[lg[d[x]-d[y]]][x];
if(x==y)return x;
for(i=lg[d[x]];~i;i--)
if(fa[i][x]!=fa[i][y])
x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
int lcanum[N],x[N],y[N];
int edges[N],k;
ll res;
ll fac[N],inv[N];
int qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int c(int n,int m){
if(n<m||m<0)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void getans(int p,int f){
int i,q;
for(i=hd[p];i;i=e[i].n){
q=e[i].e;
if(q!=f){
getans(q,p);
edges[p]+=edges[q];
}
}
res=(res+c(edges[p],k)-c(edges[p]-lcanum[p],k)+mod)%mod;
}
int main(){
int i,x,y,T;
fac[0]=inv[0]=1;
for(i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
scanf("%d",&T);
while(T--){
res=0;
memset(hd,0,sizeof(int)*(n+1));cnt=0;
memset(lcanum,0,sizeof(int)*(n+1));
memset(edges,0,sizeof(int)*(n+1));
scanf("%d%d%d",&n,&m,&k);
int rt=1;
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
d[rt]=0;
dfs(rt,0);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);int lc=lca(x,y);
lcanum[lc]++;
edges[x]++;edges[y]++;
edges[lc]--;edges[fa[0][lc]]--;
}
getans(rt,0);
printf("%lld\n",res);
}
return 0;
}
H Rikka with A Long Colour Palette
题目描述
数轴上有$n$条线段，对每条线段染色$[1,k]$，问最多有多少个区间包含了所有颜色，并输出染色方案。
解题思路
贪心地维护一个未染色集合和待定染色集合即可。
将线段分为左端点右端点两种，如果当前到达左端点，未染色集合如果空那么将这个线段加入待定染色集合，否则拿出未染色集合任意一个元素进行染色；如果当前是右端点， 将颜色加回未染色集合，从待定集合中依次拿出线段，如果线段右端点比当前右端点还小，说明可以任意染色，否则拿出未染色集合进行染色。不必要用集合，用一个队列即可。
AC代码
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
typedef long long ll;
using namespace std;
queue<int>S,col;
int tot;
struct Point{
int sign,id,x;
bool operator<(const Point&a)const{
return x<a.x||(x==a.x&&(sign>a.sign||sign==a.sign&&x<a.x));
}
}p[N<<1];
int c[N];
int main(){
int i,T,n,k,l,r;
scanf("%d",&T);
while(T--){
ll ans=0;
while(!S.empty())S.pop();
while(!col.empty())col.pop();
memset(c,0,sizeof(c));
scanf("%d%d",&n,&k);
tot=0;
for(i=1;i<=n;i++)
scanf("%d%d",&l,&r),
p[++tot]=(Point){1,i,l},p[++tot]=(Point){-1,i,r};
sort(p+1,p+1+tot);
for(i=1;i<=k;i++)col.push(i);
for(i=1;i<=tot;i++){
if(col.empty())ans+=p[i].x-p[i-1].x;
if(p[i].sign==1){
if(col.empty())S.push(p[i].id);
else{
c[p[i].id]=col.front();
col.pop();
}
}else{
if(c[p[i].id])col.push(c[p[i].id]);
else c[p[i].id]=1;
while(!col.empty()&&!S.empty()){
int now=S.front();S.pop();
int cl=col.front();
if(c[now])continue;
c[now]=cl;
col.pop();
}
}
}
printf("%lld\n",ans);
for(i=1;i<=n;i++)printf("%d%c",c[i],i==n?'\n':' ');
}
return 0;
}
I Rikka with Sorting Networks
题目描述
对于一个长度为$n$（$n<=50$）的数列，尝试最多$10$次指定的比较（比较某$2$个指定的位置），如果比较的结果是”$>$”，就交换着两个位置的权值。
问有多少$1-n$的排列，满足经过这个处理后，会形成一个”最长上升子序列长度是$n-1$”的序列。
解题思路
由于$almost\space sorted\space array$只有$(n-1)^2+1$种（枚举每一个长度为$n-1$的数列，有$n-1$个空可以插，再加一种$1-n$的排列），故可以枚举这个东西回推。
AC代码
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
typedef long long ll;
using namespace std;
int mod;
vector<int>v;
set<vector<int>>S;
struct Query{
int u,v;
}q[52];
int ans;
void dfs(int d){
if(!d){ans++;return;}
if(v[q[d].u]<v[q[d].v]){
swap(v[q[d].u],v[q[d].v]);dfs(d-1);
swap(v[q[d].u],v[q[d].v]);dfs(d-1);
}
}
int main(){
int i,j,l,T;
scanf("%d",&T);
while(T--){
int n,k;
S.clear();v.clear();
ans=0;
scanf("%d%d%d",&n,&k,&mod);
for(i=1;i<=k;i++)scanf("%d%d",&q[i].u,&q[i].v),q[i].u--,q[i].v--;
for(i=1;i<=n;i++)v.push_back(i);
S.insert(v);dfs(k);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
int now=0;
v.clear();
for(l=1;l<j;l++){
if(++now==i)now++;
v.push_back(now);
}
v.push_back(i);
for(l=j+1;l<=n;l++){
if(++now==i)now++;
v.push_back(now);
}
if(S.find(v)==S.end()){
S.insert(v);
//for(auto m:v)printf("%d ",m);
dfs(k);
//puts("");
}
}
}
printf("%d\n",ans);
}
return 0;
}
J Rikka with An Unnamed Temple
题目描述
解题思路
AC代码
2
K Rikka with Ants
题目描述
有一个环，每个边有边权。两只蚂蚁，一只要从$u_0$走到$v_0$，另一只要从$u_1$走到$v_1$，如果两只蚂蚁都经过某个边，这边的边权变为三倍。边权总和越小越好，问两只蚂蚁都采取最优策略的情况下，走过的权值和期望。
解题思路
先计算出蚂蚁分别顺时针、逆时针走的路程，判断出必然利己的决策。
然后假设蚂蚁$0$走逆时针的概率为$p_1$，蚂蚁$1$走逆时针的概率为$p_2$。那么能求出蚂蚁$0$的期望$E_0$，用$p_1,p_2$表示。假设$E_0=c+x\times p_1+y\times p_2+z\times p_1p_2$，现在要求$p_1,p_2$。
- 采取最利己策略，令$p_2=0,p_2=1$的期望相等，求出$p_1=-\frac yz$，同理根据$E_1$求出$p_2$；
- 采取使对方不存在纯策略，最优策略是概率分布：$p_2=-\frac xz$，同理根据$E_0$求出$p_1$。
这两种情况求出的$p_1,p_2$不相同，但期望总是相同的。很玄学，但都能过。
AC代码
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
typedef long long ll;
using namespace std;
int u[2],v[2],a[52],ans[2][2][2];
int state[52],n;
void calc(int f1,int t1,int f2,int t2,int* ans){
int i,d1=0,d2=0;
memset(state,0,sizeof(state));
for(i=f1;i!=t1;i=(i+1)%n)state[i]+=1;
for(i=f2;i!=t2;i=(i+1)%n)state[i]+=2;
for(i=0;i<n;i++){
if(state[i]==1)d1+=a[i];
else if(state[i]==2)d2+=a[i];
else if(state[i])d1+=a[i]*3,d2+=a[i]*3;
}
ans[0]=d1;ans[1]=d2;
}
int main(){
int i,T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
scanf("%d%d%d%d",&u[0],&v[0],&u[1],&v[1]);
u[0]--;u[1]--;v[0]--;v[1]--;
calc(u[0],v[0],u[1],v[1],ans[0][0]);
calc(u[0],v[0],v[1],u[1],ans[0][1]);
calc(v[0],u[0],u[1],v[1],ans[1][0]);
calc(v[0],u[0],v[1],u[1],ans[1][1]);
if(ans[0][0][1]<=ans[0][1][1]&&ans[1][0][1]<=ans[1][1][1]){//0怎么选 1选0都是优的
if(ans[1][0][0]<=ans[0][0][0])printf("%d %d\n",ans[1][0][0],ans[1][0][1]);
else printf("%d %d\n",ans[0][0][0],ans[0][0][1]);
}else if(ans[0][0][1]>=ans[0][1][1]&&ans[1][0][1]>=ans[1][1][1]){//0怎么选 1选1都是优的
if(ans[1][1][0]<=ans[0][1][0])printf("%d %d\n",ans[1][1][0],ans[1][1][1]);
else printf("%d %d\n",ans[0][1][0],ans[0][1][1]);
}else if(ans[0][0][0]<=ans[1][0][0]&&ans[0][1][0]<=ans[1][1][0]){//1怎么选 0选0都是优的
if(ans[0][1][1]<=ans[0][0][1])printf("%d %d\n",ans[0][1][0],ans[0][1][1]);
else printf("%d %d\n",ans[0][0][0],ans[0][0][1]);
}else if(ans[0][0][0]>=ans[1][0][0]&&ans[0][1][0]>=ans[1][1][0]){//1怎么选 0选1都是优的
if(ans[1][1][1]<=ans[1][0][1])printf("%d %d\n",ans[1][1][0],ans[1][1][1]);
else printf("%d %d\n",ans[1][0][0],ans[1][0][1]);
}else{
double p1,p2;
int c[2],x[2],y[2],z[2];
c[0]=ans[0][0][0];
x[0]=-ans[0][0][0]+ans[1][0][0];
y[0]=-ans[0][0][0]+ans[0][1][0];
z[0]=ans[0][0][0]+ans[1][1][0]-ans[0][1][0]-ans[1][0][0];
c[1]=ans[0][0][1];
x[1]=-ans[0][0][1]+ans[1][0][1];
y[1]=-ans[0][0][1]+ans[0][1][1];
z[1]=ans[0][0][1]+ans[1][1][1]-ans[0][1][1]-ans[1][0][1];
p1=-1.0*y[0]/z[0];//改变的p1
p2=-1.0*x[1]/z[1];//改变的p2
/*p2=-1.0*x[0]/z[0];//改变的p1
p1=-1.0*y[1]/z[1];//改变的p2*/
//printf("%f %f\n",p1,p2);
printf("%.12f ",c[0]+x[0]*p1+y[0]*p2+z[0]*p1*p2);
printf("%.12f\n",c[1]+x[1]*p1+y[1]*p2+z[1]*p1*p2);
}
}
return 0;
}
L Rikka with Grid Graphs
题目描述
解题思路
AC代码
2
M Rikka with Illuminations
题目描述
给一个凸包，外面有多个点光源，问最少使用多少个点光源才能照亮所有边。保证不存在三点共线。
解题思路
暴力枚举起点，贪心求解即可。
AC代码
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
typedef long long ll;
using namespace std;
struct Point{
int x,y;
}p[N],t[N];
Point operator-(Point a,Point b){
return (Point){a.x-b.x,a.y-b.y};
}
ll cross(Point a,Point b){return 1LL*a.x*b.y-1LL*a.y*b.x;}
int id[N],ext[N];
int main(){
int i,j,T,n,m;
scanf("%d",&T);
while(T--){
memset(ext,0,sizeof(ext));
memset(id,0,sizeof(id));
scanf("%d%d",&n,&m);
int ans=n+1,start=0,flag=0;
for(i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(i=0;i<m;i++)scanf("%d%d",&t[i].x,&t[i].y);
for(i=0;i<m;i++){
int l=0,r=0;
for(j=1;j<n;j++){
if(cross(p[j]-t[i],p[l]-t[i])<0)l=j;
if(cross(p[j]-t[i],p[r]-t[i])>0)r=j;
}
for(j=l;j!=r;j=(j+1)%n){
j%=n;
if(ext[j]<(r-j+n)%n)ext[j]=(r-j+n)%n,id[j]=i;
}
}
for(i=0;i<n;i++)if(ext[i]<1)flag=1;
if(flag){
printf("-1\n");
continue;
}
for(i=0;i<n;i++){
j=i;int cnt=0;
while(j<(i+n))
j+=ext[j%n],cnt++;
if(ans>cnt)ans=cnt,start=i;
}
printf("%d\n",ans);
while(ans--)printf("%d%c",id[start]+1,!ans?'\n':' '),(start+=ext[start])%=n;
}
return 0;
}