CCF CSP 2020年06月认证真题及详细答案解析

CCFCSP2020年06月认证真题及详细答案解析本次整理为CCFCSP2020年6月完整五题真题，包含题目描述、解题思路、完整C++满分代码、分步解析、易错点总结，完全贴合考场答题规范，逻辑通俗，无冗余话术。第一题线性分类器（100分）一、题目描述给定一个二维平面，有若干A、B两类样本点，再给出若干条直线作为分类器。对于每条直线，判断是否能完美分割两类点：所有A类点在直线一侧，所有B类点在另一侧。直线通用公式：ax+by+c=0。点代入公式得到数值，正数、负数代表直线两侧，0代表点在直线上（判定为分割失败）。输入格式：第一行两个整数n,m，n为样本点数量，m为分类直线数量。接下来n行，每行两个整数x,y和一个字符t（A/B），代表点坐标和类别。接下来m行，每行三个整数a,b,c，代表直线参数。输出格式：对每条直线，能够完美分割输出Yes，否则输出No。数据范围：1≤n,m≤1000，坐标绝对值不超过10000。二、解题思路1、遍历每条直线，逐个代入所有样本点计算val=a∗x+b∗y+c；2、若存在任意点val=0，直接判定分割失败；3、记录第一个A类点的正负符号，后续所有A类点必须和它符号一致，所有B类点必须符号相反；4、满足上述所有条件则输出Yes，否则No。核心要点：无需几何推导，纯数值符号判断即可，避免浮点运算误差，全程整数计算。三、满分代码cpp

#include<iostream>

#include<vector>

usingnamespacestd;

structPoint{

intx,y;

chartype;

};

vector<Point>p;

intmain(){

intn,m;

cin>>n>>m;

for(inti=0;i<n;i++){

intx,y;chart;

cin>>x>>y>>t;

p.push_back({x,y,t});

}

while(m--){

inta,b,c;

cin>>a>>b>>c;

boolok=true;

intflag=0;//记录A类点符号

for(auto&pt:p){

intres=a*pt.x+b*pt.y+c;

if(res==0){

ok=false;

break;

}

if(pt.type=='A'){

if(flag==0)flag=res>0?1:-1;

else{

intnow=res>0?1:-1;

if(now!=flag){

ok=false;

break;

}

}

}else{

intnow=res>0?1:-1;

if(now==flag){

ok=false;

break;

}

}

}

cout<<(ok?"Yes":"No")<<endl;

}

return0;

}四、易错点解析1、不能忽略点在直线上的情况，只要有一个点落在直线上，直接不满足分割条件；2、必须统一A类点符号，不能只判断AB符号不同，避免A类点分居直线两侧的错误情况；3、全程使用整数运算，杜绝浮点数精度丢失问题。第二题稀疏向量（100分）一、题目描述稀疏向量指大部分元素为0的向量，存储时仅存储非零元素的下标和数值。给定两个n维稀疏向量u、v，计算二者的内积。向量内积规则：对应下标元素相乘后累加，下标不存在非零元素则该项为0。输入格式：第一行三个整数n,a,b，n为向量维度，a为u的非零元素个数，b为v的非零元素个数。接下来a行，每行两个整数idx,val，代表u中下标idx的元素值为val。接下来b行，每行两个整数idx,val，代表v中下标idx的元素值为val。输出格式：输出一个整数，为两个向量的内积。数据范围：1≤n≤1e9，1≤a,b≤1e5，下标互不重复，数值绝对值≤1000。二、解题思路1、n维度极大，无法开数组存储完整向量，只能存储非零元素；2、用哈希表存储第一个向量的下标和对应数值；3、遍历第二个向量的所有非零元素，若下标在哈希表中存在，累加二者乘积；4、最终累加结果即为内积。时间复杂度O(a+b)，可以完全通过数据范围限制。三、满分代码cpp

#include<iostream>

#include<unordered_map>

usingnamespacestd;

typedeflonglongll;

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

lln;

inta,b;

cin>>n>>a>>b;

unordered_map<int,int>mp;

for(inti=0;i<a;i++){

intidx,val;

cin>>idx>>val;

mp[idx]=val;

}

llans=0;

for(inti=0;i<b;i++){

intidx,val;

cin>>idx>>val;

if(mp.count(idx)){

ans+=1LL*mp[idx]*val;

}

}

cout<<ans<<endl;

return0;

}四、易错点解析1、结果必须用longlong存储，多组乘积累加会超出int范围，导致溢出失分；2、关闭cin同步加速，处理1e5级别的数据，避免输入超时；3、无需存储零元素，仅匹配共同非零下标即可，节省空间和时间。第三题化学方程式（100分）一、题目描述输入一条化学方程式，格式为左边化学式=右边化学式，判断方程式是否配平（左右各元素原子总数相等）。化学式规则：包含大写字母开头的元素、括号、数字下标、整体系数。输入：多组数据，每组一行方程式。输出：配平输出Y，否则输出N。二、解题思路1、以等号分割字符串，分别处理左右两侧；2、以加号分割每个化学式，逐个统计元素数量；3、先读取化学式整体前置系数，再遍历字符，处理括号嵌套、元素下标；4、用栈处理括号，括号内所有元素数量乘以括号后的下标数字；5、统计完左右两侧元素总数后，对比哈希表，完全一致则配平。三、满分代码cpp

#include<iostream>

#include<string>

#include<unordered_map>

#include<stack>

usingnamespacestd;

typedefunordered_map<string,int>ump;

//截取数字

intgetNum(string&s,int&p){

intres=0;

while(p<s.size()&&isdigit(s[p])){

res=res*10+s[p]-'0';

p++;

}

returnres==0?1:res;

}

//解析单个化学式

umpparse(strings){

umpcnt;

intpos=0;

intpre=getNum(s,pos);

stack<ump>st;

st.push(cnt);

while(pos<s.size()){

if(s[pos]=='('){

st.push(cnt);

pos++;

}elseif(s[pos]==')'){

pos++;

intnum=getNum(s,pos);

umpnow=st.top();st.pop();

for(auto&p:now){

st.top()[p.first]+=p.second*num;

}

}else{

//读取元素名

stringname;

name+=s[pos];

pos++;

if(pos<s.size()&&islower(s[pos])){

name+=s[pos];

pos++;

}

intnum=getNum(s,pos);

st.top()[name]+=num;

}

}

umpres=st.top();

for(auto&p:res)p.second*=pre;

returnres;

}

//处理一侧所有化学式

umpcalc(strings){

umpres;

intl=0;

for(inti=0;i<s.size();i++){

if(s[i]=='+'){

umpnow=parse(s.substr(l,i-l));

for(auto&p:now)res[p.first]+=p.second;

l=i+1;

}

}

umpnow=parse(s.substr(l));

for(auto&p:now)res[p.first]+=p.second;

returnres;

}

boolcheck(strings){

intpos=s.find('=');

stringleft=s.substr(0,pos);

stringright=s.substr(pos+1);

returncalc(left)==calc(right);

}

intmain(){

intT;

cin>>T;

while(T--){

strings;

cin>>s;

cout<<(check(s)?"Y":"N")<<endl;

}

return0;

}四、核心解析与易错点1、难点为括号嵌套处理，栈是最优解法，每层括号独立统计，出栈时统一乘下标；2、无下标时默认数量为1，无前置系数时默认系数为1；3、元素名可能为两位（大写+小写），不能只读取单个字符；4、左右两侧必须元素种类、数量完全一致，缺一不可。第四题星际旅行（100分）一、题目描述有n个星球，m条双向时空隧道，每条隧道有通行时长。玩家可以使用至多k次瞬移技能，每次瞬移可将单次隧道通行时长减半（向下取整）。求1号星球到n号星球的最短通行时间。输入格式：第一行n,m,k，代表星球数、隧道数、最大瞬移次数。后续m行，每行u,v,w，代表u、v双向隧道，时长w。输出：1到n的最短时间。数据范围：n≤1000，m≤5000，k≤10。二、解题思路本题为分层最短路经典模板题。1、定义dp[i][j]：到达i号点，使用j次瞬移的最短时间；2、对于每条边，有两种选择：不使用瞬移，耗时w；使用瞬移（j<k），耗时w/2；3、用堆优化Dijkstra算法跑最短路，最后取dp[n][0~k]的最小值即为答案。分层思想：将状态扩充为「节点+使用技能次数」，彻底解决有限次技能的最短路问题。三、满分代码cpp

#include<iostream>

#include<vector>

#include<queue>

#include<cstring>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

typedefpair<ll,pair<int,int>>pli;

constintN=1005;

constintK=15;

constllINF=1e18;

vector<pair<int,int>>g[N];

lldis[N][K];

intn,m,k;

voiddijkstra(){

for(inti=1;i<=n;i++)

for(intj=0;j<=k;j++)

dis[i][j]=INF;

priority_queue<pli,vector<pli>,greater<pli>>q;

dis[1][0]=0;

q.push({0,{1,0}});

while(!q.empty()){

autonow=q.top();q.pop();

lld=now.first;

intu=now.second.first;

intcnt=now.second.second;

if(d>dis[u][cnt])continue;

for(auto&e:g[u]){

intv=e.first;

intw=e.second;

//不使用瞬移

if(dis[v][cnt]>d+w){

dis[v][cnt]=d+w;

q.push({dis[v][cnt],{v,cnt}});

}

//使用瞬移

if(cnt<k&&dis[v][cnt+1]>d+w/2){

dis[v][cnt+1]=d+w/2;

q.push({dis[v][cnt+1],{v,cnt+1}});

}

}

}

}

intmain(){

cin>>n>>m>>k;

for(inti=0;i<m;i++){

intu,v,w;

cin>>u>>v>>w;

g[u].emplace_back(v,w);

g[v].emplace_back(u,w);

}

dijkstra();

llans=INF;

for(inti=0;i<=k;i++)ans