欢迎来到起遇信息学
起遇信息学正处于上线筹建阶段，以下功能已全部开放免费体验： ✅ 完整题库浏览与代码提交评测（C / C++ / Python / Java 等） ✅ 入门到进阶的系列课程试读、作业与考试 ✅ AI 提示、AI 作业分析等智能助教功能 ✅ 赛事模拟与个人能力报告 ✅ 邮箱注册开放 ⏳ 付费课程订阅与微信/支付宝支付通道 ⏳ 手机号登录，微信扫码登录、微信公众号绑定 使用中如遇任何问题，欢迎通过页面底部 **"联系我们"** 与我们沟通。
A.假期
https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF698A?lang=zh 动态规划 题意：在每一天，Vasya 可以选择休息，或者参加比赛（如果这一天有比赛），或者锻炼（如果这一天健身房开放），输出一行，包含一个整数，表示 Vasya 至少需要休息多少天，限制：不能连续两天都锻炼，不能连续两天都参加比赛。 思路：dp[i][j]表示第i天做活动j时，前i天最多能活动多少天，状态转移公式：如果休息（dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])），如果健身（dp[i][2] = max(dp[i-1][0],dp[i-1][1])+1），如果比赛（dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 1）；
#include<bits/stdc++.h>
using namespace std;
int n,a[105],dp[105][3];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
if(a[i]==1||a[i]==3){
dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
}
if(a[i]==2||a[i]==3){
dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
}
}
cout<<min(dp[n][0],min(dp[n][1],dp[n][2]));
}
B.数字之和
题意：你的任务是找出长度为m，各位数字之和为，s的最小和最大数，若不存在满足条件的数，输出“-1 -1”。 思路：贪心，先特判-1 -1，策略最大数：高位尽可能大，最小数：最高位为1，然后从低位到高位尽可能大。
#include<bits/stdc++.h>
using namespace std;
int main(){
int m,s,x;
cin>>m>>s;
x=s;
if(s>9*m){
cout<<"-1 -1";
return 0;
}
if(s==0&&m>1){
cout<<"-1 -1";
return 0;
}
if(s==0&&m==1){
cout<<"0 0";
return 0;
}
string a="";
for(int i=1;i<=9;i++){
if(i<=x&&x-i<=(m-1)*9){
a+=char('0'+i);
x-=i;
break;
}
}
for(int i=2;i<=m;i++){
for(int j=0;j<=9;j++){
if(j<=x&&x-j<=(m-i)*9){
a+=char('0'+j);
x-=j;
break;
}
}
}
x=s;
string b="";
for(int i=1;i<=m;i++){
for(int j=9;j>=0;j--){
if(i==1&&j==0&&m>1)continue;
if(j<=x&&x-j<=(m-i)*9){
b+=char('0'+j);
x-=j;
break;
}
}
}
cout<<a<<" "<<b;
}
C.美丽序列
题意：每次操作，你可以删除序列中的任意一个元素。请问最少需要多少次操作才能使给定序列变为美丽序列（定义：如果一个序列可以被分成若干个区块，每个区块的第一个元素表示该区块的长度，接下来是该区块的元素，则称该序列为美丽序列） 思路：我们需要找到最长的美丽子序列，答案=n-最长美丽子序列的长度，dp[i] 表示以位置i作为区块起点时，从i到n能形成的最大美丽序列长度转移：如果选择x作为区块长度，那么这个区块的长度为 x+1，下一个位置从i+x+1开始，公式：如果i+a[i]<=n,dp[i]=a[i]+1+ dp[i+a[i]+1否则：dp[i]=0（无法形成完整区块）要点：倒着用dp
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],dp[200005];
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n+1;i++)dp[i]=0;
for(int i=1;i<=n;i++){
dp[i]=max(dp[i],dp[i-1]);
if(i+a[i]<=n){
dp[i+a[i]]=max(dp[i+a[i]],dp[i-1]+a[i]+1);
}
}
cout<<n-dp[n]<<"\n";
}
return 0;
}
D.小高的生日卡
https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF766C
题意：一条长度为n的信息s，分成若干个非空的子串，不允许英文字母中第i个字母在长度超过ai的字符串中出现，有多少种方法可以将字符串拆分成若干个子串，使得每个子串都满足魔法纸的条件，子串长度之和为n,且互不重叠？请计算方案数对1e9+7取模,在所有合法拆分中，可能出现的最长子串的最大长度是多少？在所有合法拆分方式中，最少需要分成多少个子串？ 思路：dp1[i]：前i个字符的分割方案数，状态转移公式：x[i]=sum(dp1[j-1])，初始化x[0]=1，(j到i是合法子串),y[i]：前i个字符最少需要多少个子串,状态转移公式：y[i]=min(y[j-1]+1)，(j到i是合法子串)，初始化：y[0]=0,最大值：搜索合法子串时找max(···)。
#include<bits/stdc++.h>
using namespace std;
int n,a[30],x[1005],y[1005];
string s;
int main(){
cin>>n>>s;
for(int i=0;i<26;i++)cin>>a[i];
int ans=0;
for(int i=0;i<=n;i++)y[i]=1e9;
x[0]=1;
y[0]=0;
for(int i=0;i<n;i++){
int len=1e9;
for(int j=i;j<n;j++){
len=min(len,a[s[j]-'a']);
if(j-i+1>len)break;
x[j+1]=(x[j+1]+x[i])%1000000007;
ans=max(ans,j-i+1);
y[j+1]=min(y[j+1],y[i]+1);
}
}
cout<<x[n]<<"\n"<<ans<<"\n"<<y[n]<<"\n";
}
E.棋盘游戏
https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF1033C
题意：游戏棋盘由n个格子组成，排成一行，编号从1到n，每个格子内包含一个1到n之间的数字ai。此外，任意两个格子内的数字都不相同。一个棋子被放在某个格子上。他们轮流移动棋子，Alice 先手。当前玩家可以将棋子从第i个格子移动到第j个格子，要求：aj>ai，|i−j∣mod ai=0，无法进行移动的一方判负，对于每一个可能的初始位置，若双方都采取最优策略，判断谁能获胜，输出一个长度为n的字符串s，其中第i个字符表示若棋子初始放在第i个格子时的游戏结果。如果Alice能获胜，则si等于"A"；否则，si等于"B"。 思路：没地方走的地方必败，走到必败地方的地方必胜，走到必胜地方的地方必败，走到必败地方(^o^)/和必胜地方的地方必胜；
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],f[100005];
int dfs(int x){
if(f[x]!=-1)return f[x];
int w=0;
for(int i=a[x];i<=n;i+=a[x]){
if(x+i<=n&&a[x+i]>a[x]){
if(dfs(x+i)==0)w=1;
}
if(x-i>=1&&a[x-i]>a[x]){
if(dfs(x-i)==0)w=1;
}
if(w)break;
}
return f[x]=w;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++){
if(dfs(i))cout<<"A";
else cout<<"B";
}
}
F.高雅数
https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF1036C
题意：给定一个区间[L,R]，请统计有多少个“高雅数”（它的十进制表示中存在不超过3个的非零数字）整数x满足L≤x≤R 思路：数位DP：dfs(p,c,l) 表示从高位到低位处理到第p位，已经用了c个非零数字，l表示是否贴着上限，统计0到n中非零数字<=3的数字个数。 转移与剪枝：枚举当前位0-9，非零则c+1，若c≤3继续递归，p=0时返回1（所有合法数字都算1个）。 区间答案：sq(n)统计0到n的个数并减去0，最终答案=sq(R)-sq(L-1)。
#include<bits/stdc++.h>
using namespace std;
long long f[20][5][2],x,y;
int t,d[20];
long long dfs(int p,int c,int l){
if(!p)return 1;
if(!l&&f[p][c][l]!=-1)return f[p][c][l];
long long zx=0;
int u=9;
if(l)u=d[p];
for(int i=0;i<=u;i++){
int v=c+(i!=0);
if(v<4)zx+=dfs(p-1,v,l&&i==u);
}
if(!l)f[p][c][l]=zx;
return zx;
}
long long sq(long long n){
if(n<=0)return 0;
int p=0;
while(n){
d[++p]=n%10;
n/=10;
}
memset(f,-1,sizeof(f));
return dfs(p,0,1)-1;
}
int main(){
cin>>t;
while(t--){
cin>>x>>y;
cout<<sq(y)-sq(x-1)<<"\n";
}
}
0 条评论
目前还没有评论...
Be the first to comment!
