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

2024年CCF非专业级别软件能力认证第二轮 (CSP-S)提高级C++语言试题 VIP

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

一、简答题

1. 简答题

T1、决斗(duel)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e6+10; int n, x; struct bj { int num; bool flag, gjf; }; vector&lt;bj&gt; v; int bs(int k) { int r = n - 1, l = 0, res = -1; while (l &lt;= r) { int mid = l + (r - l) / 2; if (v[mid].num &gt; k &amp;&amp; v[mid].flag == true &amp;&amp; v[mid].gjf == true) { res = mid; r = mid - 1; } else l = mid + 1; } return res; } bool cmp(bj a, bj b) { return a.num &lt; b.num; } int main() { cin &gt;&gt; n; for (int i = 0; i &lt; n; i++) { cin &gt;&gt; x; v.push_back({x, true, true}); } sort(v.begin(), v.end(), cmp); for (int i = 0; i &lt; n - 1; i++) { int re = bs(v[i].num); if (re == -1) continue; else { v[i].flag = false; v[re].gjf = false; } } int ans = 0; for (int i = 0; i &lt; n; i++) if (v[i].flag == true) ans++; cout &lt;&lt; ans; return 0; }</pre>
这道题暂未补解析。
2. 简答题

T2、超速检测(detect)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; bool Mbegin; void File_Work(){ freopen("detect.in","r",stdin); freopen("detect.out","w",stdout); } const int N=1e5+8; int n,m,L,V,p[N],d[N],v[N],a[N]; struct Interval{ int l,r; void init(){ l=r=0; } friend bool operator &lt;(Interval a,Interval b){ if(a.r!=b.r) return a.r&lt;b.r; return a.l&lt;b.l; } }itv[N]; bool check(int pos,int i){ int x=p[pos]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2) return 1; return 0; } void MAIN(){ for(int i=1;i&lt;=n;i++) p[i]=0,itv[i].init(); cin&gt;&gt;n&gt;&gt;m&gt;&gt;L&gt;&gt;V; for(int i=1;i&lt;=n;i++) cin&gt;&gt;d[i]&gt;&gt;v[i]&gt;&gt;a[i]; for(int i=1;i&lt;=m;i++) cin&gt;&gt;p[i]; sort(p+1,p+m+1); int ans1=0; for(int i=1;i&lt;=n;i++){ if(p[m]&lt;d[i]) continue; int pos=lower_bound(p+1,p+m+1,d[i])-p; if(a[i]==0&amp;&amp;v[i]&gt;V) itv[++ans1]={pos,m}; else if(a[i]&lt;0){ int x=p[pos]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2){ int l=pos,r=m,res=0; while(l&lt;=r){ int mid=(l+r)/2; if(check(mid,i)==1){ res=mid; l=mid+1; } else r=mid-1; } itv[++ans1]={pos,res}; } } else if(a[i]&gt;0){ int x=p[m]-d[i]; int v2=v[i]*v[i]+2*a[i]*x; if(V*V&lt;v2){ int l=pos,r=m,res=0; while(l&lt;=r){ int mid=(l+r)/2; if(check(mid,i)==1){ res=mid; r=mid-1; } else l=mid+1; } itv[++ans1]={res,m}; } } } cout&lt;&lt;ans1&lt;&lt;' '; sort(itv+1,itv+ans1+1); int ans2=0,cur; for(int i=1;i&lt;=ans1;i++){ if(itv[i].l&lt;=cur&amp;&amp;cur&lt;=itv[i].r) continue; ans2++; cur=itv[i].r; } cout&lt;&lt;m-ans2&lt;&lt;'\n'; } bool Mend; int main(){ // File_Work(); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cerr&lt;&lt;fixed&lt;&lt;setprecision(3)&lt;&lt;(&amp;Mbegin-&amp;Mend)/1048576.0&lt;&lt;" MB\n\n\n"; int testid=0,testnum=1; // cin&gt;&gt;testid; cin&gt;&gt;testnum; while(testnum--) MAIN(); cerr&lt;&lt;"\n\n\n"&lt;&lt;fixed&lt;&lt;setprecision(0)&lt;&lt;1e3*clock()/CLOCKS_PER_SEC&lt;&lt;" ms"; return 0; }</pre>
这道题暂未补解析。
3. 简答题

T3、染色(color)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; #define ll long long using namespace std;   ll t,anstmp; ll dp[2000005][2]; ll lst[2000005];   struct num{     ll n,last; }a[2000005];   int main(){     ll t;     scanf("%lld",&amp;t);     while (t--){         ll n;         scanf("%lld",&amp;n);         memset(dp,0,sizeof(dp));         memset(lst,0,sizeof(lst));         anstmp=0;         for (ll i=1;i&lt;=n;i++){             scanf("%lld",&amp;a[i].n);             if (lst[a[i].n]) a[i].last=lst[a[i].n];             else a[i].last=0;             lst[a[i].n]=i;             if (a[i-1].n==a[i].n) anstmp=anstmp+a[i].n;         }         for (ll i=1;i&lt;=n;i++){             if (a[i].n==a[i-1].n){                 dp[i][0]=max(dp[i-1][0],dp[i-1][1]);                 dp[i][1]=dp[i-1][1];                 continue;             }             else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);             if (a[i].last) dp[i][1]=max(max(dp[a[i].last][0],dp[a[i].last][1]),max(dp[a[i].last+1][0],dp[a[i].last+1][1]))+a[i].n;         }         printf("%lld\n",max(dp[n][0],dp[n][1])+anstmp);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt; using namespace std; #define int long long int rd() { int x = 0, w = 1; char ch = 0; while (ch &lt; '0' || ch &gt; '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch &gt;= '0' &amp;&amp; ch &lt;= '9') { x = x * 10 + (ch - '0'); ch = getchar(); } return x * w; } void wt(int x) { static int sta[35]; int f = 1; if(x &lt; 0) f = -1,x *= f; int top = 0; do { sta[top++] = x % 10, x /= 10; } while (x); if(f == -1) putchar('-'); while (top) putchar(sta[--top] + 48); } namespace work{ const int N = 2e5+5,M = 1e6 + 5; int n,a[M],s[M],f[M],t[M]; void solve() { memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); memset(f,0,sizeof(f)); n = rd(); for(int i = 1;i&lt;=n;i++) a[i] = rd(); for(int i = 2;i&lt;=n;i++) s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i]; for(int i = 1;i&lt;=n;i++) { f[i] = f[i - 1]; if(t[a[i]]) f[i] = max(f[i],f[t[a[i]] + 1] + a[i] + s[i] - s[t[a[i]] + 1]); t[a[i]] = i; } wt(f[n]);putchar('\n'); } } signed main() { int T = rd(); while(T--) work::solve(); return 0; }</pre>
这道题暂未补解析。
4. 简答题

T4、擂台游戏(arena)

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;bits/stdc++.h&gt; #define INF 0x3f3f3f3f #define ll long long #define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d)) #define FOR(i,a,b) for(int i(a);i&lt;=(int)(b);++i) #define DOR(i,a,b) for(int i(a);i&gt;=(int)(b);--i) using namespace std; constexpr int N((1&lt;&lt;17)+10); namespace IOstream { #define getc() getchar() #define putc(ch) putchar(ch) #define isdigit(ch) ('0'&lt;=(ch)&amp;&amp;(ch)&lt;='9') template&lt;class T&gt;void rd(T &amp;x) { static char ch(0); for(x=0,ch=getc(); !isdigit(ch); ch=getc()); for(; isdigit(ch); x=(x&lt;&lt;1)+(x&lt;&lt;3)+(ch^'0'),ch=getc()); } template&lt;class T&gt;void wr(T x,const char End='\n') { static int top(0); static int st[50]; do st[++top]=x%10,x/=10; while(x); while(top)putc(st[top]^'0'),--top; putc(End); } } using namespace IOstream; bool d[N]; char s[N]; int n,m,k,Q; int a_[N],a[N],c[N],wt[N&lt;&lt;1],wn[N&lt;&lt;1]; ll sum[N]; #define v (u&lt;&lt;1) void dfs0(int u,int h) { if(!h)return wn[u]=a[wt[u]=u-(1&lt;&lt;k)+1],void(); dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]&lt;h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]&lt;h))]; } void dfs1(int u,int hmx,int h,int L,int R) { if(L&gt;R)return; if(!h) { int x(u-(1&lt;&lt;k)+1); if(L&lt;min(R,x))sum[L]+=x,sum[min(R,x)]-=x; if(a[x]&gt;=hmx&amp;&amp;max(L,x)&lt;R)sum[max(L,x)]+=x,sum[R]-=x; return; } dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]&gt;=h?min(wt[v|d[u]],R):R); } #undef v signed main() { rd(n),rd(m); while((1&lt;&lt;k)&lt;n)++k; FOR(i,1,n)rd(a_[i]); FOR(i,1,m)rd(c[i]); DOR(i,k-1,0) { scanf("%s",s); DOR(j,(1&lt;&lt;i)-1,0)d[j|1&lt;&lt;i]=s[j]^48; } rd(Q); while(Q--) { static int X[4]; rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]); FOR(i,1,n)a[i]=a_[i]^X[i&amp;3]; dfs0(1,k),RCL(sum+1,0,ll,n); FOR(i,0,k)dfs1(1&lt;&lt;(k-i),0,i,!i?1:(1&lt;&lt;(i-1))+1,(1&lt;&lt;i)+1); FOR(i,1,n)sum[i]+=sum[i-1]; ll ans(0); FOR(i,1,m)ans^=i*sum[c[i]]; wr(ans); } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt; #define INF 0x3f3f3f3f #define ll long long #define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d)) #define FOR(i,a,b) for(int i(a);i&lt;=(int)(b);++i) #define DOR(i,a,b) for(int i(a);i&gt;=(int)(b);--i) using namespace std; constexpr int N((1&lt;&lt;17)+10); namespace IOstream { #define getc() getchar() #define putc(ch) putchar(ch) #define isdigit(ch) ('0'&lt;=(ch)&amp;&amp;(ch)&lt;='9') template&lt;class T&gt;void rd(T &amp;x) { static char ch(0); for(x=0,ch=getc(); !isdigit(ch); ch=getc()); for(; isdigit(ch); x=(x&lt;&lt;1)+(x&lt;&lt;3)+(ch^'0'),ch=getc()); } template&lt;class T&gt;void wr(T x,const char End='\n') { static int top(0); static int st[50]; do st[++top]=x%10,x/=10; while(x); while(top)putc(st[top]^'0'),--top; putc(End); } } using namespace IOstream; bool d[N]; char s[N]; int n,m,k,Q; int a_[N],a[N],c[N],wt[N&lt;&lt;1],wn[N&lt;&lt;1]; ll sum[N]; #define v (u&lt;&lt;1) void dfs0(int u,int h) { if(!h)return wn[u]=a[wt[u]=u-(1&lt;&lt;k)+1],void(); dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]&lt;h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]&lt;h))]; } void dfs1(int u,int hmx,int h,int L,int R) { if(L&gt;R)return; if(!h) { int x(u-(1&lt;&lt;k)+1); if(L&lt;min(R,x))sum[L]+=x,sum[min(R,x)]-=x; if(a[x]&gt;=hmx&amp;&amp;max(L,x)&lt;R)sum[max(L,x)]+=x,sum[R]-=x; return; } dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]&gt;=h?min(wt[v|d[u]],R):R); } #undef v signed main() { rd(n),rd(m); while((1&lt;&lt;k)&lt;n)++k; FOR(i,1,n)rd(a_[i]); FOR(i,1,m)rd(c[i]); DOR(i,k-1,0) { scanf("%s",s); DOR(j,(1&lt;&lt;i)-1,0)d[j|1&lt;&lt;i]=s[j]^48; } rd(Q); while(Q--) { static int X[4]; rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]); FOR(i,1,n)a[i]=a_[i]^X[i&amp;3]; dfs0(1,k),RCL(sum+1,0,ll,n); FOR(i,0,k)dfs1(1&lt;&lt;(k-i),0,i,!i?1:(1&lt;&lt;(i-1))+1,(1&lt;&lt;i)+1); FOR(i,1,n)sum[i]+=sum[i-1]; ll ans(0); FOR(i,1,m)ans^=i*sum[c[i]]; wr(ans); } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #define ls x&lt;&lt;1 #define rs x&lt;&lt;1|1 #define lson x&lt;&lt;1,l,mid #define rson x&lt;&lt;1|1,mid+1,r #define ll long long using namespace std; const int N = (1 &lt;&lt; 17) + 5; int mx[20][N &lt;&lt; 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1; bool vis[N]; ll ans[N], sum; struct node { ll sum; int x; bool tp, d; } t[N &lt;&lt; 2]; inline void build(int x, int l, int r) { if (l == r) { t[x].x = l; return ; } int mid = l + r &gt;&gt; 1, k = lg[r - l + 1], d = t[x].d; build(lson); build(rson); int win = a[t[x &lt;&lt; 1 | d].x] &gt;= k; t[x].x = t[x &lt;&lt; 1 | (d ^ !win)].x; if (!d &amp;&amp; win)t[x].tp = 1, ok[r]++, ok[mid]--; else t[x].tp = 0; } inline void build2(int x, int l, int r, int *mx) { t[x].sum = (l + r) * (r - l + 1ll) / 2; if (l == r)return ; int mid = l + r &gt;&gt; 1, k = lg[r - l + 1], d = t[x].d; if (~mx[x])mx[ls] = mx[rs] = mx[x]; else mx[x &lt;&lt; 1 | d] = k; build2(lson, mx); build2(rson, mx); } inline void up(int x) { sum += !vis[x] * x; vis[x] = 1; } inline int rd() { char c; int f = 1; while (!isdigit(c = getchar()))if (c == '-')f = -1; int x = c - '0'; while (isdigit(c = getchar()))x = x * 10 + (c ^ 48); return x * f; } inline char gc() { char c; while ((c = getchar()) &lt;= ' '); return c; } int main() { // freopen("arena.in","r",stdin); // freopen("arena.out","w",stdout); n = rd(); m = rd(); for (int i = 1; i &lt;= n; i++)aa[i] = rd(); for (int i = 1; i &lt;= m; i++)c[i] = rd(); while (nn &lt; n)nn &lt;&lt;= 1; for (int i = 2; i &lt;= nn; i++)lg[i] = lg[i &gt;&gt; 1] + 1; for (int i = nn / 2; i; i &gt;&gt;= 1) for (int j = i; j &lt; i * 2; j++) t[j].d = gc() - '0'; memset(mx, -1, sizeof mx); for (int s = 0; (1 &lt;&lt; s) &lt;= nn; s++) build2(1 &lt;&lt; s, 1, nn&gt;&gt;s, mx[s]); for (int T = rd(); T--;) { int yh[4] = {rd(), rd(), rd(), rd()}; for (int i = 1; i &lt;= n; i++)a[i] = aa[i] ^ yh[i &amp; 3]; memset(ok, 0, sizeof ok); build(1, 1, nn); for (int i = nn, rt = 1, s = 0; i; i--) { if ((1 &lt;&lt; lg[i]) == i) { if (i != nn)rt &lt;&lt;= 1, s++; for (int j = 1; j &lt;= i; j++)vis[j] = 0; sum = 0; up(t[rt].x); } ans[i] = sum; if (ok[i] += ok[i + 1])continue; up(i); int x = i + nn - 1; while (x != rt) { int d = x &amp; 1; x &gt;&gt;= 1; if (!d) if (t[x].tp)sum += t[rs].sum; else break; else if (a[t[ls].x] &gt;= mx[s][ls])up(t[ls].x); } } ll num = 0; for (int i = 1; i &lt;= m; i++)num ^= i * ans[c[i]]; printf("%lld\n", num); } return 0; }</pre>
这道题暂未补解析。