首页 › 试卷 › 信息学奥赛 › 信息学奥赛-入门级 › 2022年CCF非专业级别软件能力认证第二轮 (CSP-J)入门级C++语言试题

2022年CCF非专业级别软件能力认证第二轮 (CSP-J)入门级C++语言试题 VIP

信息学奥赛-入门级 共 4 题 2022 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

乘方(pow)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int main() {     long long ans, a, b;     ans = 1;     cin &gt;&gt; a &gt;&gt; b;     if (a == 1) { // 特判a=1,避免超时         cout &lt;&lt; ans;     } else {         for (int i = 1; i &lt;= b; ++i) {             ans *= a; // b个a相乘             if (ans &gt; 1e9) { // 若乘积超过10^9,直接输出-1并终止程序                 cout &lt;&lt; -1;                 return 0;             }         }         cout &lt;&lt; ans; // 输出b个a相乘的结果     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

解密(decode)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; int k; int main(){ scanf("%d",&amp;k); for(int i=1;i&lt;=k;i++){ long long n,d,e; scanf("%lld %lld %lld",&amp;n,&amp;d,&amp;e); long long s=n-d*e+2; long long r=(n-d*e+2)/2,l=1; while(l&lt;r){ int mid=(l+r)/2; if(mid*(s-mid)&gt;=n){ r=mid; }else{ l=mid+1; } } if(l*(s-l)==n){ printf("%lld %lld\n",l,(s-l)); }else{ printf("NO\n"); } } return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

逻辑表达式(expr)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; using namespace std; inline void fio(string name) { freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } inline long long read() { long long s=0,w=1,ch=getchar(); while(ch&lt;'0'||ch&gt;'9') ch=='-'?w=-1,ch=getchar():ch=getchar(); while(ch&gt;='0'&amp;&amp;ch&lt;='9') s=(s&lt;&lt;1)+(s&lt;&lt;3)+(ch^48),ch=getchar(); return s*w; } const int S=1000005; int n; char a[S]; int top,sta[S]; int rb[S],val[S]; int mlog[S],mn[S][25]; int cnt1,cnt2; inline int que(int l,int r) { int k=mlog[r-l+1]; int x=mn[l][k],y=mn[r-(1&lt;&lt;k)+1][k]; return val[x]&lt;val[y]?x:y; } int slove(int l,int r) { if(rb[l]==r) l++,r--; if(l==r) return a[l]-'0'; int pos=que(l,r); int lft=slove(l,pos-1); if(lft==0&amp;&amp;a[pos]=='&amp;') { cnt1++; return 0; } if(lft==1&amp;&amp;a[pos]=='|') { cnt2++; return 1; } int rig=slove(pos+1,r); if(a[pos]=='&amp;') return lft&amp;rig; else return lft|rig; } int main() { fio("expr"); scanf("%s",a+1); n=strlen(a+1); for(int i=1;i&lt;=n;i++) { if(a[i]=='(') sta[++top]=i; else if(a[i]==')') rb[sta[top--]]=i; else if(a[i]!='0'&amp;&amp;a[i]!='1') val[i]=sta[top]*2+(a[i]=='&amp;'); if(a[i]!='&amp;'&amp;&amp;a[i]!='|') val[i]=1e8; } mlog[0]=-1; for(int i=1;i&lt;=n;i++) mlog[i]=mlog[i&gt;&gt;1]+1,mn[i][0]=i; for(int j=1;j&lt;=mlog[n];j++) { for(int i=1;i&lt;=n-(1&lt;&lt;j)+1;i++) { int x=mn[i][j-1],y=mn[i+(1&lt;&lt;j-1)][j-1]; mn[i][j]=val[x]&lt;val[y]?x:y; } } printf("%d\n",slove(1,n)); printf("%d %d\n",cnt1,cnt2); return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt; #define N 3000005 using namespace std; int n,m,top,ans1,ans2; int to[N],to2[N],stk[N],cl[N],cr[N]; char str[N],s[N]; void build(int l,int r){ if(l==r) return; if(str[l]=='('&amp;&amp;str[r]==')'&amp;&amp;to[l]==r){build(l+1,r-1);return;} build(l,to[l]); for(int i=to[l]+1;i&lt;=r;i=to[i+1]+1){ build(i+1,to[i+1]); if(str[i]=='&amp;'){ cl[to2[i-1]]++;cr[to2[i+1]]++; to2[to2[i+1]]=to2[i-1]; } } } int solve(int l,int r){ if(l==r) return s[l]-'0'; if(s[l]=='('&amp;&amp;s[r]==')'&amp;&amp;to[l]==r) return solve(l+1,r-1); int val=solve(l,to[l]); for(int i=to[l]+1;i&lt;=r;i=to[i+1]+1){ if(s[i]=='&amp;'){ if(!val) ans1++; else val&amp;=solve(i+1,to[i+1]); }else{ if(val) ans2++; else val|=solve(i+1,to[i+1]); } } return val; } signed main(){ freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); scanf("%s",str+1);n=strlen(str+1); for(int i=1;i&lt;=n;i++){ if(str[i]=='0'||str[i]=='1') to[i]=i; if(str[i]=='(') stk[++top]=i; if(str[i]==')') to[stk[top]]=i,to[i]=stk[top],top--; } memcpy(to2,to,sizeof(to)); build(1,n); for(int i=1;i&lt;=n;i++){ while(cl[i]--) s[++m]='('; s[++m]=str[i]; while(cr[i]--) s[++m]=')'; } memset(to,0,sizeof(to)); top=0; for(int i=1;i&lt;=m;i++){ if(s[i]=='0'||s[i]=='1') to[i]=i; if(s[i]=='(') stk[++top]=i; if(s[i]==')') to[stk[top]]=i,to[i]=stk[top],top--; } printf("%d\n",solve(1,m)); printf("%d %d\n",ans1,ans2); return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include&lt;bits/stdc++.h&gt; using namespace std; typedef long long LL; const int N=1e6+5; string s; int sum,sun,to[N],stk[N],stkid,now; char la; stack&lt;int&gt;r[N/2]; int main() { freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); cin&gt;&gt;s; int n=s.size(); for(int i=n-1;i&gt;=0;i--) s[i+1]=s[i]; for(int i=1;i&lt;=n;i++) to[i]=i+1; for(int i=1;i&lt;=n;i++){ if(s[i]=='(') stk[++stkid]=i-1; if(s[i]==')') to[stk[stkid--]]=i; } for(int i=1;i&lt;=n;i++){ if(s[i]=='|'){ if(r[now].size()){ int TOP=r[now].top(); r[now].pop();      to[TOP]=i-1;      }      r[now].push(i);      } if(s[i]=='(') now++; if(s[i]==')'){ if(r[now].size()){ int TOP=r[now].top(); r[now].pop();      to[TOP]=i;      } now--; } } if(r[now].size()) to[r[now].top()]=n+1; //for(int i=1;i&lt;=n;i++) cout&lt;&lt;to[i]&lt;&lt;' ';cout&lt;&lt;endl; for(int i=1;i&lt;=n;i++){ if(s[i]=='('||s[i]==')') continue; if(s[i]=='|'){     if(la=='1') {sun++;i=to[i];} } else if(s[i]=='&amp;'){ if(la=='0') {sum++;i=to[i];} } else{     la=s[i]; } } cout&lt;&lt;la&lt;&lt;endl&lt;&lt;sum&lt;&lt;' '&lt;&lt;sun; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码4 #include&lt;bits/stdc++.h&gt; #define REP(i,a,n) for(int i=(a);i&lt;(int)(n);++i) #define pb push_back using namespace std; string s; int tp1,tp2; int main(){ freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); cin&gt;&gt;s; int cnt1=0,cnt2=0,ans=0; REP(i,0,s.size()){ if(s[i]=='1'||s[i]=='0')ans=s[i]-'0'; else if(s[i]=='&amp;'){ if(ans==0){ ++cnt1; int res=0; for(int j=i+1;j&lt;(int)(s.size());++j){ if(s[j]=='(')++res; else if(s[j]==')')--res; if((!res)&amp;&amp;s[j]!='&amp;'&amp;&amp;s[j]!='|'){ i=j; break; } } } }else if(s[i]=='|'){ if(ans==1){ ++cnt2; int res=0; for(int j=i+1;j&lt;(int)(s.size());++j){ if(s[j]=='(')++res; else if(s[j]==')')--res; if(j!=(int)(s.size()-1)&amp;&amp;s[j+1]=='&amp;')continue; if((!res)&amp;&amp;s[j]!='&amp;'&amp;&amp;s[j]!='|'){ i=j; break; } } } } } cout&lt;&lt;ans&lt;&lt;endl; cout&lt;&lt;cnt1&lt;&lt;' '&lt;&lt;cnt2&lt;&lt;endl; return 0; }</pre><p></p>
这道题暂未补解析。
4. 简答题

上升点列(point)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;bits/stdc++.h&gt; using namespace std; struct node{ int x,y; //重载运算符,按x从小到大排序,x相同,则按y从小到大排序 friend bool operator&lt;(const node &amp;a1,const node &amp;a2){ if(a1.x!=a2.x)return a1.x&lt;a2.x; return a1.y&lt;a2.y; } }a[505];//记录500个点 int f[505][105],n,m,ans; int main(){ cin&gt;&gt;n&gt;&gt;m; for(int i=1;i&lt;=n;i++)cin&gt;&gt;a[i].x&gt;&gt;a[i].y; sort(a+1,a+1+n);//排序 for(int k=0;k&lt;=m;k++){//枚举使用0到K个点的情况 for(int i=1;i&lt;=n;i++){//枚举每一个点 f[i][k]=k+1;//初始化第i个点用掉K个添加点后的最长距离 for(int j=1;j&lt;i;j++){//循环这个点之前的点 if(a[j].y&gt;a[i].y)continue;//如果之前的点Y坐标大,则忽略 int dist=a[i].x-a[j].x+a[i].y-a[j].y;//计算距离 if(dist-1&gt;k)continue;//如果距离大,添加的点不够用,则忽略 f[i][k]=max(f[i][k],f[j][k-dist+1]+dist);//看下现在的大还是换成之前的点大 } ans=max(ans,f[i][k]+m-k);//跟最大值比较 } } cout&lt;&lt;ans; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt;  using namespace std; int n,k; struct points {     int x,y; } p[510];   bool cmp(const points a,const points b)  {     if(a.x==b.x) return a.y&lt;b.y;     else return a.x&lt;b.x; } int f[510][110];//以i点为终点,再添加上j个点的情况下最大序列长度 int main()  { //打开输入文件,输出文件 freopen("point.in","r",stdin); freopen("point.out","w",stdout);     scanf("%d %d",&amp;n,&amp;k);     for(int i=1; i&lt;=n; i++)  {         scanf("%d %d",&amp;p[i].x,&amp;p[i].y);     }     sort(p+1,p+1+n,cmp);     int ans=0;     for(int i=1; i&lt;=n; i++)  {//以i为终点         for(int j=0; j&lt;=k; j++)  {//添加j个点             f[i][j]=j+1;//以i为终点,后续添加j个点最短的长度             for(int l=1; l&lt;i; l++)  { //l为i的前一个点                 if(p[l].x&lt;=p[i].x&amp;&amp;p[l].y&lt;=p[i].y)  {//横坐标、纵坐标值均单调不减                     int t=p[i].x-p[l].x+p[i].y-p[l].y-1;//需要添加的点数量                     if(j&gt;=t) f[i][j]=max(f[i][j],f[l][j-t]+t+1);                     //cout&lt;&lt;p[i].x&lt;&lt;p[l].x&lt;&lt;p[i].y&lt;&lt;p[l].y&lt;&lt;t&lt;&lt;endl;                 }                 //cout&lt;&lt;"i="&lt;&lt;i&lt;&lt;" j="&lt;&lt;j&lt;&lt;" l="&lt;&lt;l&lt;&lt;" f="&lt;&lt;f[i][j]&lt;&lt;endl;             }               ans=max(ans,f[i][j]);         }     }     printf("%d",ans);     //关闭输入文件输出文件 fclose(stdin); fclose(stdout);     return 0; }</pre><p><br/></p>
这道题暂未补解析。