目录
A - Running Routes题意解题思路代码
B - Research Productivity Index题意解题思路代码
C - Interesting Subset题意解题思路代码
D - Tell Your World题意解题思路代码
E - Stop Counting!题意解题思路代码
F - Dasha and Very Difficult Problem题意解题思路代码
A - Running Routes
题意
链接：A - Running Routes
输入输出：
3
0 1 1
1 0 1
1 1 0
1
6
0 0 0 1 0 0
0 0 0 0 1 1
0 0 0 0 1 1
1 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
2
给你一个正n边形，和一个n*n矩阵a[i][j]表示端点i，j间可以连一条线，问最多能连多少条不相交的线
解题思路
区间dp把正n边形的端点按顺序从1到n编号一圈，对于每一个区间(l,r)，若中间有一点k与l相连则区间(l+1,k-1)中的点不能再连线了。记dp[l][r]表示区间(l,r)最多能连的线数，则状态转移方程为dp[l][r]=max(dp[l][r],dp[l +1][k-1]+ dp[k+1][r]+ a[l][k]）
代码
#include<stdio.h>
#include<algorithm>
using namespace std
;
int a
[505][505],dp
[505][505];
int main()
{
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
scanf("%d",&a
[i
][j
]);
for(int i
=1;i
<n
;i
++)
for(int j
=1;j
<=n
-i
;j
++)
for(int k
=j
;k
<=j
+i
;k
++)
dp
[j
][j
+i
]=max(dp
[j
][j
+i
],dp
[j
+1][k
-1]+dp
[k
+1][j
+i
]+a
[j
][k
]);
printf("%d\n",dp
[1][n
]);
return 0;
}
B - Research Productivity Index
题意
链接：B - Research Productivity Index
输入输出：
5
30 50 70 60 90
2.220889579
6
30 90 30 90 30 90
2.599738456
4
10 10 10 10
0.368937005
Angela提交了n篇论文，每篇论文提交通过的概率为ai,记F=
j
j
i
j^{\frac{j}{i}}
jij(i为总提交论文数，j为通过的论文数)，问F的最大期望
解题思路
概率dpFi的期望=Fi的概率*Fi ans为Fi的期望的最大记dp[i][j]表示提交前i篇论文，其中有j篇通过的概率，则状态转移方程为：dp[i][j]=dp[i-1][j]*(1-a[i])+dp[i-1][j-1]a[i] 边界dp[0][0]=1 dp[i][0]=dp[i-1][0](1-a[i])应该优先取通过概率大的论文所以要先把ai从大到小排序
代码
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std
;
double a
[105];
double dp
[105][105];
bool cmp(double x
,double y
)
{
return x
>y
;
}
int main()
{
int n
,x
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)
{
scanf("%d",&x
);
a
[i
]=x
*0.01;
}
sort(a
+1,a
+1+n
,cmp
);
dp
[0][0]=1;
double ans
=0;
for(int i
=1;i
<=n
;i
++)
{
double e
=0;
dp
[i
][0]=dp
[i
-1][0]*(1-a
[i
]);
for(int j
=1;j
<=i
;j
++)
{
dp
[i
][j
]=dp
[i
-1][j
]*(1-a
[i
])+dp
[i
-1][j
-1]*a
[i
];
e
+=dp
[i
][j
]*pow(j
,1.0*j
/i
);
}
ans
=max(e
,ans
);
}
printf("%.9lf\n",ans
);
return 0;
}
C - Interesting Subset
题意
链接：C - Interesting Subset 输入：
3
1
2
3
输出：
Case
1: 1
Case
2: 9
Case
3: 47
一个集合是有趣的定义：该集合中至少存在一个数是该集合中最小的数的倍数 现给你一个集合x={1，2，3，……，2n},问有多少个子集是有趣的
解题思路
枚举每个有趣的子集的最小的数i（1<=i<=n） 对于每个i，集合x中（除i外）有a=
2
n
i
−
1
\frac{2n}{i}-1
i2n−1个数是i的倍数,每个数字都有选或不选两种情况共
2
a
−
1
2^{a-1}
2a−1;剩下的不是i的倍数的数有b=2n-i-a，每个数字都有选或不选两种情况共
2
b
2^b
2b 所以每个i有
2
a
−
1
∗
2
b
2^{a-1}*2^b
2a−1∗2b个子集是有趣的快速幂，数学，注意ll与mod的处理
代码
#include<stdio.h>
using namespace std
;
typedef long long ll
;
const ll mod
=1000000007;
ll
power(ll aa
,ll bb
)
{
ll res
=1;
while(bb
)
{
if(bb
&1)res
=1ll*res
*aa
%mod
;
aa
=1ll*aa
*aa
%mod
;
bb
>>=1;
}
return res
;
}
int main()
{
ll t
,n
;
scanf("%lld",&t
);
for(ll T
=1;T
<=t
;T
++)
{
scanf("%lld",&n
);
ll ans
=0;
for(ll i
=1;i
<=n
;i
++)
{
ll a
=2*n
/i
-1,b
=2*n
-a
-i
;
ans
=(ans
+(power(2,a
)-1)*power(2,b
))%mod
;
}
printf("Case %lld: %lld\n",T
,ans
);
}
return 0;
}
D - Tell Your World
题意
链接：D - Tell Your World输入输出：
5
7 5 8 6 9
Yes
5
-1 -2 0 0 -5
No
5
5 4 3 2 1
No
5
1000000000 0 0 0 0
Yes
给你n个点的纵坐标y1,y2,……,yn, 则点i的坐标为(i，yi) ，问你能不能用两条不重合的平行线经过这个n个点（每条平行线上至少有1个点在上面）
解题思路
参考：传送门
思路：对于大问题，先缩小为小问题 考虑只有两个点的时候可以任意画出两条不重合的平行线分别过这两个点 当有三个点数，可以取其中两个点确定一条直线L1，再根据另一个点和L1的斜率确定出另一条直线L2，而L1的斜率有三种取值 然后每增加一个点我们就判断一下它能否在前三个点确定出的两条直线上，如果三种情况不行就为no 判断剩余的点能否在前三个点确定出的两条直线上的方法：前两个点确认出的斜率kt,枚举每个点的坐标(i,yi),根据直线方程y=kx+b可得出纵截距bi=yi-kt*i，统计bi的值不同的个数是否为2map.count(b)代表元素b在map中的个数 关于map的用法可看传送门
代码
#include<stdio.h>
#include<map>
using namespace std
;
typedef long long ll
;
const ll maxn
=1003;
double k
[4];
int y
[maxn
];
int main()
{
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&y
[i
]);
k
[1]=(y
[1]*1.0-y
[2]*1.0)/(1.0-2.0);
k
[2]=(y
[1]*1.0-y
[3]*1.0)/(1.0-3.0);
k
[3]=(y
[2]*1.0-y
[3]*1.0)/(2.0-3.0);
int fff
=0;
for(int t
=1;t
<=3;t
++)
{
int cnt
=0;
map
<double,int>m
;
for(int i
=1;i
<=n
;i
++)
{
double b
=y
[i
]*1.0-k
[t
]*i
*1.0;
if(!m
.count(b
))
{
m
[b
]=1;cnt
++;
}else m
[b
]++;
}
if(cnt
==2)
{
fff
=1;break;
}
}
if(fff
)printf("yes\n");
else printf("no\n");
return 0;
}
E - Stop Counting!
题意
链接：E - Stop Counting! 输入输出：
5
10 10 -10 -4 10
10.000000000
4
-3 -1 -4 -1
0.000000000
有一个n张牌，每张牌有一个面值ai，牌的顺序固定，让你在n个数中间插入两个隔板分成三部分，支出为前后两部分牌的面值之和除以这两部分的总牌数，问最大的支出是多少
解题思路
设前x张牌的平均值为a，后y张牌的平均值为b，则支出为ax+by / x+y 当a>=b时，
a
x
+
b
y
x
+
y
<
=
a
x
+
a
y
x
+
y
=
a
\frac{ax+by}{x+y } <= \frac{ax+ay}{x+y } = a
x+yax+by<=x+yax+ay=a 则最大支出为a 当a<=b时，同理得最大支出为b所以可以得出结论：最大支出为前缀平均值或后缀平均值的最大
代码
#include<stdio.h>
#include<algorithm>
using namespace std
;
typedef long long ll
;
const int maxn
=1e6+5;
double a
[maxn
],q
[maxn
],h
[maxn
];
int main()
{
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)scanf("%lf",&a
[i
]);
for(int i
=1;i
<=n
;i
++)
{
q
[i
]=q
[i
-1]+a
[i
];
h
[n
-i
+1]=h
[n
-i
+2]+a
[n
-i
+1];
}
double ans
=0;
for(int i
=1;i
<=n
;i
++)
{
q
[i
]/=i
;
h
[n
-i
+1]/=i
;
ans
=max(ans
,max(q
[i
],h
[n
-i
+1]));
}
printf("%.9lf\n",ans
);
return 0;
}
F - Dasha and Very Difficult Problem
题意
链接：F - Dasha and Very Difficult Problem
输入输出：
5 1 5
1 1 1 1 1
3 1 5 4 2
3 1 5 4 2
4 2 9
3 4 8 9
3 2 1 4
2 2 2 9
6 1 5
1 1 1 1 1 1
2 3 5 4 1 6
-1
序列a b c之间存在关系c[i]=b[i]-a[i]。现给出n，l，r和两个长为n的序列a和p，其中l r 表示序列a和b的取值范围，pi表示ci在序列c中是第pi小的，让你构造出任意一个满足条件的序列b，若不行则输出-1
解题思路
因为b[i]=c[i]+a[i] 我们构造一个满足此条件的最小的序列b则c也是最小的，所以c[i]=p[i]，
接下来判断满不满足第二个条件，序列b的取值落在l r里：找出这个序列的最大和最小，看看这个序列b的取值有多少个即maxb-minb+1<=r-l+1若不满足则不存在输出-1,否则就把b的取值范围移动到区间l,r里
代码
#include<stdio.h>
#include<algorithm>
using namespace std
;
typedef long long ll
;
const int maxn
=1e5+5;
int a
[maxn
],b
[maxn
];
int main()
{
int n
,l
,r
,p
;
scanf("%d%d%d",&n
,&l
,&r
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
]);
int maxb
=-1,minb
=0x3f3f3f3f;
for(int i
=1;i
<=n
;i
++)
{
scanf("%d",&p
);
b
[i
]=p
+a
[i
];
maxb
=max(maxb
,b
[i
]);
minb
=min(minb
,b
[i
]);
}
if(maxb
-minb
+1>r
-l
+1)printf("-1\n");
else{
int dis
=0;
if(minb
<l
)dis
=l
-minb
;
else if(maxb
>r
)dis
=r
-maxb
;
for(int i
=1;i
<=n
;i
++)
{
b
[i
]+=dis
;printf("%d",b
[i
]);
if(i
==n
)printf("\n");
else printf(" ");
}
}
return 0;
}
