补完一套月赛，此图为证
说明
题目链接
这套题其实没有特别难的，唯二两道难题是G和I。
G题是一道简单dp，式子很简单，难的地方在于怎么把图形存在数组里，而且还能利用这个数组动态规划。
I题是一道结论题，可能对科班出身的比较友好，考察的是出栈序列有多少种，如果知道卡特兰数，并且看出最想去的目的地不能首选的本质，就能秒杀此题。
A 简单题
知道e就是exp(1)，而且设置高位精度直接用C++的setprecision。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;cin>>T;
while(T--){
int a,b,y;
cin>>a>>b>>y;
cout<<fixed<<setprecision(y)<<b*exp(a)<<endl;
}
return 0;
}
B 简单题2
简化一下式子，注意式子精度要够。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;cin>>T;
while(T--){
int b,d,y;
cin>>b>>d>>y;
cout<<fixed<<setprecision(y)<<exp(exp(1)*log(b))/d<<endl;
}
return 0;
}
C 分元宵
注意快速幂里面的幂次不能取模，只能是底数取模，因为幂次取模是没有意义的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll a, ll b, ll m){
ll ans=1;
while(b){
if(b&1)ans=ans*a%m;
a=(a%m)*(a%m)%m;
b=b>>1;
}
return ans;
}
int main(){
ll a,b,c,d,mod;
cin>>a>>b>>c>>d>>mod;
ll p=c*d;
ll q=(a%mod)*(b%mod)%mod;
ll ans=ksm(q,p,mod);
if(a==0||b==0||c==0||d==0)ans=0;
cout<<ans<<endl;
return 0;
}
D 多项式乘法
看出来结构体排序，一遍过。
#include<bits/stdc++.h>
using namespace std;
struct node{
int cishu;
int xishu;
bool friend operator < (const node &A, const node &B){
return A.cishu<B.cishu;
}
}F[505],L[505],ans[505*505];
int shuchu[505*505];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++){
int x;cin>>x;
F[i].cishu=i,F[i].xishu=x;
}
for(int i=0;i<=m;i++){
int x;cin>>x;
L[i].cishu=i,L[i].xishu=x;
}
int cnt=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
ans[cnt].cishu=F[i].cishu+L[j].cishu;
ans[cnt++].xishu=F[i].xishu*L[j].xishu;
}
}
sort(ans,ans+cnt);
//for(int i=0;i<cnt;i++)cout<<ans[i].xishu<<" ";
int num=0,now=0;
for(int i=0;i<cnt-1;i++){
now+=ans[i].xishu;
if(ans[i].cishu!=ans[i+1].cishu){
shuchu[num]+=now;
num++;
now=0;
}
}
if(ans[cnt-2].cishu!=ans[cnt-1].cishu)shuchu[num++]=ans[cnt-1].xishu;
else shuchu[num]+=ans[cnt-1].xishu,num++;
for(int i=0;i<num;i++){
cout<<shuchu[i]<<" ";
}
return 0;
}
E 圆与三角形
输出流加fixed，就是四舍五入；不加fixed，就是保留几位小数。
#include<bits/stdc++.h>
using namespace std;
int main(){
double r;
cin>>r;
cout<<fixed<<setprecision(2)<<r+1<<endl;
return 0;
}
F 三视图
关键是怎么存坐标。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
char fr[maxn][maxn],le[maxn][maxn],to[maxn][maxn];
int main(){
int X,Y,Z,n;
cin>>X>>Y>>Z>>n;
for(int i=Y;i>=1;i--){
for(int j=1;j<=X;j++){
fr[j][i]='.';
}
for(int j=1;j<=Z;j++){
le[j][i]='.';
}
}
for(int i=1;i<=Z;i++){
for(int j=1;j<=X;j++){
to[i][j]='.';
}
}
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
//for(int j=1;j<=y;j++)fr[x][j]='x';
//for(int j=1;j<=y;j++)le[z][j]='x';
fr[x][y]='x';
le[z][y]='x';
to[z][x]='x';
}
for(int i=Y;i>=1;i--){
for(int j=1;j<=X;j++)cout<<fr[j][i];
cout<<" ";
for(int j=1;j<=Z;j++)cout<<le[j][i];
cout<<endl;
}
cout<<endl;
for(int i=1;i<=Z;i++){
for(int j=1;j<=X;j++){
cout<<to[i][j];
}
cout<<endl;
}
return 0;
}
G あなたの蛙は旅⽴っています
把六边形图压缩成正方形。压缩的过程纯模拟，一点一点写可以写出来，我用了一个多小时才写对。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 805;
int h[2*maxn][2*maxn];
int dp[2*maxn][2*maxn];
int main(){
memset(h,0,sizeof(h));
memset(dp,0,sizeof(dp));
int n;cin>>n;
int l=2*n-1;
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--)cin>>h[j][i-j+1];
}
for(int i=n+1,k=n+1;i<=3*n-2;i+=2,k++){
for(int j=k-1;j>k-n;j--)cin>>h[j][i-j+1];
for(int j=k;j>k-n;j--)cin>>h[j][i-j+2];
}
for(int i=1;i<=n-1;i++){
for(int j=l;j>l-n+i;j--)cin>>h[j][n+i+l-j];
}
/*
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
cout<<h[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1;i<=l;i++){
dp[i][1]=dp[i-1][1]+h[i][1];
dp[1][i]=dp[1][i-1]+h[1][i];
}
for(int i=2;i<=l;i++){
for(int j=2;j<=l;j++){
dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]))+h[i][j];
}
}
cout<<dp[l][l]<<endl;
return 0;
}
H 写真がとどいています
没学过五线谱的做这个题极不友好，实际上只需要看出高低音循环。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
char a[10][maxn];
int main(){
int N;
cin>>N;
for(int i=1;i<=9;i++){
for(int j=1;j<=N;j++){
scanf(" %c",&a[i][j]);
}
}
/*
for(int i=1;i<=9;i++){
for(int j=1;j<=N;j++){
printf("%c",a[i][j]);
}
cout<<endl;
}
*/
for(int i=1;i<=N;i++){
bool f=false;
for(int j=1;j<=9;j++){
if(a[j][i]=='o'){
switch(10-j){
case 1:cout<<"E";break;
case 2:cout<<"F";break;
case 3:cout<<"G";break;
case 4:cout<<"A";break;
case 5:cout<<"B";break;
case 6:cout<<"C";break;
case 7:cout<<"D";break;
case 8:cout<<"E";break;
case 9:cout<<"F";break;
default:break;
}
f=true;
}
else if(a[j][i]=='|'){
cout<<"|";
f=true;
break;
}
}
if(f==false)cout<<" ";
}
return 0;
}
I あなたの蛙が帰っています
逆向思维。一个长度为n的入栈序列的合法出栈序列数就是卡特兰数。如果第一个出栈的是A，那么合法出栈序列数就是长度为n-1时的卡特兰数。那么第一个出栈的不能是A的合法出栈序列数，就是长度为n时的卡特兰数-长度是n-1时的卡特兰数。 卡特兰数：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll maxn = 1e5+5;
ll jc[2*maxn];
void get_jc(){
jc[0]=jc[1]=1;
for(ll i=2;i<=2e5;i++){
jc[i]=(jc[i-1]%mod)*i%mod;
}
}
ll ksm(ll a, ll b, ll mod){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b=b>>1;
}
return ans;
}
ll inv(ll a, ll mod){
return ksm(a,mod-2,mod);
}
ll catalan(ll n){
return (((jc[2*n]%mod)*inv(jc[n+1],mod))%mod)*inv(jc[n],mod)%mod;
}
int main(){
get_jc();
ll t;cin>>t;
for(int i=1;i<=t;i++){
ll n;cin>>n;
ll ans=((catalan(n)%mod)+mod-(catalan(n-1)%mod))%mod;
cout<<"Case #"<<i<<": "<<ans%mod<<endl;
}
return 0;
}
J おみやげをまらいました
开一个map映射。
#include<bits/stdc++.h>
using namespace std;
map<string,string> mp;
int main(){
string s1,s2;
for(int i=1;i<=3;i++){
cin>>s1>>s2;
mp[s2]=s1;
}
int N;cin>>N;
for(int i=1;i<=N;i++){
string s;cin>>s;
if(mp[s]=="")puts("Fake");
else{
string ans=mp[s];
cout<<ans<<endl;
}
}
return 0;
}
小结
这套题中规中矩，但是3个小时AK难度很大，需要在读题这方面相当熟练。对于一个现在小白月赛稳定2-3题的蒟蒻的我，需要提高简单题的熟练度。
京公网安备 11010502036488号