原网站：http://phoenix-zh.cn/2020/09/05/CodeForces-1409/

A.题目名称:

Yet Another Two Integers Problem

题目大意：

每次选择一个k∈[1,10]，a可以a-=k或者a+=k，问需要的最小次数使得a变成b。

思路：

尽量选大，则D=abs(a-b)，D=ceil(D/10)

代码：

#include
using namespace std;
typedef long long ll;
ll T,a,b;
int main(){cin>>T;while(T--){cin>>a>>b;ll d=abs(a-b);ll ans=ceil(d*1.0/10.0);cout<<ans<<endl;}return 0;
}

B.题目名称：

Minimum Product

题目大意：

每次可以对a-=1，或者b-=1，最多操作n次，并且保证a>=x,b>=y.求a * b的最小值。

思路：

先将a变成最小，若有剩余再将b变小，求得minn1；先将b变成最小，若有剩余再将a变小，求得minn2。ans=min(minn1,minn2）。

代码：

#include
using namespace std;
typedef long long ll;
ll T,a,b,x,y,n;
int main(){cin>>T;while(T--){cin>>a>>b>>x>>y>>n;ll d1=min(a-x,n);ll resn=n-d1;ll d2=min(b-y,resn);ll ans1=(a-d1)*(b-d2);d2=min(b-y,n);resn=n-d2;d1=min(a-x,resn);ll ans2=(a-d1)*(b-d2);cout<<min(ans1,ans2)<<endl;}return 0;
}

C.题目名称：

Yet Another Array Restoration

题目大意：

一组数组有n个数，一定包含x，y，求得这组数组使得其中最大的尽量小。

思路：

枚举x与y之间得数字个数，进而得到差值，尽量让y作为最大值，如果中间不够填充，则先向左边扩展，再向右扩展。

特判：n==2，直接输出x，y。

代码：

#include
using namespace std;
typedef long long ll;
ll T,x,y,n;
int main(){cin>>T;while(T--){cin>>n>>x>>y;ll d=y-x,tot=0;if(n==2){cout<<x<<' '<<y<<endl;continue;}for(int i=n-1;i;i--){if(d%i==0){ll D=d/i;ll now=x;while(now<=y&&tot<n){cout<<now<<' ';tot++;now+=D;}now=x-D;while(now>0&&tot<n){cout<<now<<' ';tot++;now-=D;}now=y+D;while(tot<n){cout<<now<<' ';now+=D;tot++;}break;}}cout<<endl;}return 0;
}

D.题目名称:

Decrease the Sum of Digits

题目大意:

给一个数n,每次可以让n+=1,使得n的各个位的数字之和<=s.

思路:

先分解出各个位上的数字,并求和得到sum,若sum<=s则直接输出答案(0),然后从从左到右(从高位到低位)开始判断该位上的数字是否需要变化.如果s-a[opt]>=1,则这一位不会变化,往下一位走.最后走到某一位opt发现s-a[opt]<1,则从opt-1到个位都是要变化的,最小的变化次数是(a[opt-1]+1)*(10^(n-opt+1))-(opt-1位作为最高位的数字)

代码:

#include
using namespace std;
typedef long long ll;
const ll maxn=100+50;
ll T,n,s,a[maxn],p[maxn];char t[maxn];
int main(){cin>>T;while(T--){p[0]=1;for(ll i=1;i<=19;i++)p[i]=p[i-1]*10ll;cin>>t+1>>s;ll sum=0,len=strlen(t+1);for(ll i=1;i<=len;i++)sum=sum+t[i]-'0',a[i]=t[i]-'0';if(sum<=s){cout<<"0"<<endl;continue;}ll opt=1;while(opt<=len&&s>a[opt])s-=a[opt],opt++;ll res=p[len-opt+1]*(a[opt-1]+1);ll tot=0;for(ll i=opt-1;i<=len;i++)tot=tot*10+a[i];ll ans=res-tot;cout<<ans<<endl;}return 0;
}

E.题目名称:

Two Platforms

题目大意:

有n个左边点,两块长度为k的木板条,只要球下降掉在木板范围以内,表示木板可以借住小球,求木板可以接住的最大数量.

思路:

先将球按照x轴的坐标从小到大排序,另开一个数组b来存在所有球的x轴坐标,对他进行去重.然后用map存每一个对应的x轴的值所对应的最大的下标值.然后对一个点求当前点作为木板的左边界可以接住的球的数量:有当前球的x轴坐标t[i].x可以求得木板的右边界t[i].x+k,如果这个有边界>=t[i].n,则sum[i]=n-i+1;否则在b数组中二分求得第一个比t[i].x+k大的数字b[t],则b[t-1]就是木板所接住的最右边的球,由map反解出b[t-1]对应的x的值对应的最大的小标mp[b[t-1]],sum[i]=mp[b[t-1]]-i+1.这样求出每一个点作为左边界可以接住的球的数量,但是这只是针对一根木板,还需要在这基础上从右到左求得M数组,M[i]表示i之后的点(包括i)一根木板可以接到的最大的球的数量.这样每一次枚举最左边的木板的左边界点i,由此得到木板的右边第一个不在该木板范围内的点i+sum[i],则第二个木板可以接到的最大数量是M[i+sum[i]],这样得到的数量就是sum[i]+M[i+sum[i]],然后每次取最大即可.

代码:

#include
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int T,n,k,sum[maxn],b[maxn],M[maxn];
struct Point{int x,y;
}t[maxn];
int cmp(Point a,Point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;
}
int main(){cin>>T;while(T--){memset(M,0,sizeof(M));map<int,int>mp;cin>>n>>k;for(int i=1;i<=n;i++)cin>>t[i].x,b[i]=t[i].x;for(int i=1;i<=n;i++)cin>>t[i].y;sort(t+1,t+1+n,cmp);sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){mp[t[i].x]=i;}for(int i=1;i<=n;i++){int maxx=t[i].x+k;if(maxx>=t[n].x){sum[i]=n-i+1;}else{int t=upper_bound(b+1,b+1+n,maxx)-b;int re=mp[b[t-1]];sum[i]=re-i+1;}}for(int i=n;i>=1;i--){M[i]=max(M[i+1],sum[i]);}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,sum[i]+M[i+sum[i]]);}cout<<ans<<endl;}return 0;
}

F.题目名称:

Subsequences of Length Two

题目大意:

对于字符串s可以将一个字母改成任意一个小写字母,可以操作不超过k次,求s中出现串t的最大数量.

思路:

设置dp[i][j][cnt0]表示枚举到i时改变了j次其中右cnt0个t[0]时出现的t的最大数量.则对于i+1来讲有三种状态:

ps:e0=s[i]==t[0];e1=s[i]==t[1];e01=t[0]==t[1].

第一种:直接不改变,则dp[i+1][j][l+e0]=max(dp[i+1][j][l+e0],dp[i][j][l]+(e1?l:0);

第二种:将它变成t[0],则dp[i+1][j+1][l+1]=max(dp[i+1][j+1][l+1],dp[i][j][l]+(e01?l:0));

第三种:将它变成t[1].则dp[i+1][j+1][l+e01]=max(dp[i+1][j+1][l+e01],dp[i][j][l]+l).

其中第二种和第三种状态中要保证j+1<=k;三种情况都要保证dp[i][j][l]!=-0x3f3f3f3f

最后枚举改变次数和cnt0的数量,求max(dp[n][i][cnt0]);

代码:

#include
using namespace std;
const int maxn=200+50;
int n,k,dp[maxn][maxn][maxn];char s[maxn],t[maxn];
int main(){cin>>n>>k;cin>>s>>t;memset(dp,-0x3f3f3f3f,sizeof(dp));dp[0][0][0]=0;for(int i=0;i<n;i++){for(int j=0;j<=k;j++){for(int l=0;l<=n;l++){if(dp[i][j][l]==-0x3f3f3f3f)continue;int e0=s[i]==t[0];int e1=s[i]==t[1];int e01=t[0]==t[1];dp[i+1][j][l+e0]=max(dp[i+1][j][l+e0],dp[i][j][l]+(e1?l:0));if(j+1<=k){dp[i+1][j+1][l+1]=max(dp[i+1][j+1][l+1],dp[i][j][l]+(e01?l:0));dp[i+1][j+1][l+e01]=max(dp[i+1][j+1][l+e01],dp[i][j][l]+l);	}}}}int ans=0;for(int i=0;i<=k;i++){for(int j=0;j<=n;j++){ans=max(ans,dp[n][i][j]);}}cout<<ans<<endl;return 0;
}

{% aplayer “那年” “枯木逢春” “https://cdn.jsdelivr.net/gh/Phoenix-ZH/CDN/1.mp3” “autoplay” %}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！