首页 / 更多教程 / [CSP-S模拟测试60]题解
[CSP-S模拟测试60]题解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[CSP-S模拟测试60]题解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3205字，纯文字阅读大概需要5分钟。
内容图文
回去要补一下命运石之门了……
A.嘟嘟噜
给定报数次数的约瑟夫，递推式为$ans=(ans+m)\% i$。
考虑优化，中间很多次$+m$后是不用取模的，这种情况就可以把加法变乘法了。问题在于如何找到下一次需要取模的位置。
解不等式$ans+km \ge i+k$即可，需要处理一下边界。
据说可以证明复杂度是$O(m \log n)$的，但我不是很会。
//考场代码 稍丑
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
int n,m,T,ans=1;
void qj()
{
for(int i=1;i<=n;i++)
ans=(ans+m)%i;
printf("%d\n",ans+1);
}
void work()
{
ans=1;
n=read();m=read();
if(m==1)
printf("%d\n",n);
else if(n<=m)qj();
else
{
ans=1;
for(int i=1;i<=n;i++)
{
if(ans+m<i)
{
ans+=m;
int times=(i-ans)/(m-1);
if(i+times>n)
times=n-i;
ans+=times*m;i+=times;
ans%=i;
}
else ans=(ans+m)%i;
}
printf("%d\n",ans+1);
}
return ;
}
int main()
{
T=read();
while(T--)work();
return 0;
}
B.天才绅士少女助手克里斯蒂娜
C.凤凰院凶真
经典的LCIS问题。设$dp[i][j]$为a串考虑到$i$，b串考虑到$j$且以$j$为结尾的LCIS长度。
限定一下条件，$O(n^3)$暴力dp就很好写了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
const int N=5005;
#define pa pair<int,int>
int n,m,a[N],b[N],dp[N][N],pre[N][N];
stack<int> s;
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m=read();
for(int i=1;i<=m;i++)
b[i]=read();
int ans1=-1,pos=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i]==b[j])
{
for(int k=0;k<j;k++)
if(b[k]<b[j])
if(dp[i][j]<dp[i-1][k]+1)
dp[i][j]=dp[i-1][k]+1,pre[i][j]=k;
}
}
for(int i=0;i<=m;i++)
if(ans1<dp[n][i])ans1=dp[n][i],pos=i;
int tim=n;
s.push(pos);
cout<<ans1<<endl;
while(tim&&pos)
{
if(pre[tim][pos])
{
pos=pre[tim][pos];
s.push(pos);
}
else tim--;
}
while(!s.empty())printf("%d ",b[s.top()]),s.pop();
putchar(‘\n‘);
return 0;
}
考虑优化。我们注意到，每次转移的条件是$a[i]=b[j] \ and\ b[j]<b[k]$，即$a[i]=b[j] \ and\ a[i]<b[k]$。j每次增加1，这个可选集合最多也只会增加1。所以可以直接去掉枚举k的循环，维护当前可选集合的最优解即可。
还有一个细节，记录前驱时要把两维的信息都记录，如果只记第二维的话各层状态会混用。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
const int N=5005;
#define pa pair<int,int>
int n,m,a[N],b[N],dp[N][N],pre[N][N];
stack<int> s;
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m=read();
for(int i=1;i<=m;i++)
b[i]=read();
int ans1=-1,pos=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i]==b[j])
{
for(int k=0;k<j;k++)
if(b[k]<b[j])
if(dp[i][j]<dp[i-1][k]+1)
dp[i][j]=dp[i-1][k]+1,pre[i][j]=k;
}
}
for(int i=0;i<=m;i++)
if(ans1<dp[n][i])ans1=dp[n][i],pos=i;
int tim=n;
s.push(pos);
cout<<ans1<<endl;
while(tim&&pos)
{
if(pre[tim][pos])
{
pos=pre[tim][pos];
s.push(pos);
}
else tim--;
}
while(!s.empty())printf("%d ",b[s.top()]),s.pop();
putchar(‘\n‘);
return 0;
}
原文：https://www.cnblogs.com/Rorschach-XR/p/11624745.html
内容总结
以上是互联网集市为您收集整理的[CSP-S模拟测试60]题解全部内容，希望文章能够帮你解决[CSP-S模拟测试60]题解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。