赛后——2.18 寒假模拟11
\(\text{T1}\) 送分题
题意
省选开始了，\(\text{S}\) 省打算从 \(N\) 位选手中选择 \(K\) 名去参加 \(\text{NOI}\)。
已知 \(\text{NOI}\) 的题可能有 \(M\) 种，并且我们已知每位同学做每种题的得分会是多少。
已知每个同学在 \(\text{NOI}\) 上最多只能做对一个题（但是一个题可能会被多个同学做），求最大的得分和。
思路
直接求每个同学自己的最大值，再排序取前 \(K\) 个最大的即可
代码
点击查看代码
int n,m,k;
db a[105][105],maxx[105],ans;
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
int x=read();
db val;
scanf("%lf",&val);
a[x][i]=val;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
maxx[i]=max(maxx[i],a[i][j]);
}
}
sort(maxx+1,maxx+1+n);
for(int i=n;i>n-k;i--){
ans+=maxx[i];
}
printf("%.1lf\n",ans);
return 0;
}
\(\text{T2}\) 纸张题
题意
小 \(\text{S}\) 正在出题，题目的难度一共分为 \(N\) 阶，标号从 \(1\) 到 \(N\)。
有的题目的难度是已经确定为 \(x\) 的，有的可能是 \(x\)，也可能是 \(x+1\)，可以标任意一种。
现在，小 \(N\) 打算出每种难度的题各一道，求方案数（此时已经确定的所有题目的难度）。
思路
标准的计数dp，我们发现对于每一位要么是选确定的，要么是选当前或前一个不确定的，于是设 \(f_i,g_i,h_i\) 分别表示选第 \(i\) 个难度且确定的，选 \(i-1\) 或 \(i\) 难度且不确定的和选 \(i\) 和 \(i+1\) 难度且不确定的。因为第一、三种情况是直接由 \(i-1\) 的方案数乘上当前的选择数，十分简单，于是：
\[f_i=a_i\times (f_{i-1}+g_{i-1}+h_{i-1}) \]\[h_i=b_i\times (f_{i-1}+g_{i-1}+h_{i-1}) \]接着考虑到对于 \(g\) 来说是可能去前面的 \(h\) 有重复，于是实际选择数为 \(b_{i-1}-1\)，即：
\[g_i=b_{i-1}\times (f_{i-1}+g_{i-1})+(b_{i-1}-1)\times h_{i-1} \]不要忘记取模。
代码
点击查看代码
int n;
int a[maxn],b[maxn];
ll f[maxn],g[maxn],h[maxn];
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i\(\text{T3}\) 哈啤题
题意
定义一个长度为 \(2\times k\) 的序列是好的，当且仅当序列的前 \(k\) 个数之和与后 \(k\) 个数之和都小于等于 \(s\)。
给定一个 \(n\) 个数的序列，求以每个位置为开头的，最长的好的连续子序列
思路
我们发现，去直接二分答案是假的，于是考虑其他二分做法。
发现如果站在一个点 \(i\) 去看其左右能到达的最远距离，设为 \(l_i\) 与 \(r_i\)，于是 \(\min(l_i,r_{i+1})\) 即为站在 \(i\) 与 \(i+1\) 能达到的最大区间。
发现这个区间内的所有点都能以 \(i\) 与 \(i+1\) 为中间点，维护一下即可。
代码
点击查看代码
int n,s;
int a[maxn],sum[maxn];
int len[maxn][2];
inline int getlen(int x,bool pd){
if(!pd){
int l=1,r=x,ans;
if(a[x]>s) return 0;
while(l<=r){
int mid=(l+r)>>1;
if(sum[x]-sum[mid-1]<=s){
r=mid-1,ans=mid;
}
else l=mid+1;
}
return x-ans+1;
}
else{
int l=x,r=n,ans;
if(a[x]>s) return 0;
while(l<=r){
int mid=(l+r)>>1;
if(sum[mid]-sum[x-1]<=s){
l=mid+1,ans=mid;
}
else r=mid-1;
}
return ans-x+1;
}
}
vector g[maxn];
multiset st;
int main(){
n=read(),s=read();
for(int i=1;i<=n;i++){
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
len[i][0]=getlen(i,0),len[i][1]=getlen(i,1);
}
for(int i=1;i<=n;i++){
if(!len[i][0]||!len[i+1][1]) continue;
int lx=min(len[i][0],len[i+1][1]);
g[i-lx+1].push_back(i);
}
for(int i=1;i<=n;i++){
for(int j=0;j \(\text{T4}\) 简单题
题意
\(\text{Alice}\) 和 \(\text{Bob}\) 在玩游戏。
他们面前有一堆石子，共 \(n\) 个，\(\text{Alice}\) 先手，两人轮流拿石子。当某个人拿石子时，他最少拿一个石子，最多能拿上一次对方拿的石子个数的二倍。
\(\text{Alice}\) 第一次先手拿时可以拿任意个，不难发现，先手必胜，现在先手必胜的情况下，第一次最少要拿多少石头。
思路
斐波那契博弈，。
代码
点击查看代码
ll n;
ll fib[105]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657};
bool vis[105];
int main(){
n=read();
for(int i=74;i>=1;i--){
if(!vis[i+1]){
if(n