做网站推广公司,当涂县微网站开发,网络推广服务公司外包,北京高端网站建设案例很幸运拿了辽宁赛区的省一,进入6月1号的国赛啦... 这篇文章主要对第十五届省赛大学B组(C)进行一次完整的复盘,这次省赛2道填空题6道编程题:
A.握手问题 把握手情景看成矩阵:
粉色部分是7个不能互相捂手的情况
由于每个人只能和其他人捂手, 所以黑色情况是不算的
1和2握手2和…很幸运拿了辽宁赛区的省一,进入6月1号的国赛啦... 这篇文章主要对第十五届省赛大学B组(C)进行一次完整的复盘,这次省赛2道填空题6道编程题:
A.握手问题 把握手情景看成矩阵:
粉色部分是7个不能互相捂手的情况
由于每个人只能和其他人捂手, 所以黑色情况是不算的
1和2握手2和1握手,就是只用算一半的对角矩阵
#includeiostream
using namespace std;
int main(){int a0;for(int i49;i;i--) ai;int b0;for(int i6;i;i--) bi;int ansa-b;coutansendl;//最后求得答案为1204 return 0;
}
B.小球反弹
这题考试的时候我是直接跳过的,到最后也没来得及看,看了估计也算不对,haha
整体思路是:
最终返回左上角时,小球走过的水平路程和垂直路程一定是343720和233333的偶数倍
并且水平路程与垂直路程之比一定为15:17
#includeiostream
#includecmath
using namespace std;
typedef long long ll;
const int N1e4;
const ll X343720;
const ll Y233333;
int main(){for(ll x2;xN;x2){for(ll y2;yN;y2){if (15*Y*y17*X*x){printf(%lf,sqrt((X*x)*(X*x)(Y*y)*(Y*y)));//结果是1100325199.770395return 0;}}}
}
C.好数
这题暴力枚举就能AC,数据不大,haha
#includeiostream
using namespace std;
typedef long long ll;
const int N1e75;
ll ans;
bool check(int x){int flag0;while(x0){int tx%10;if(!flag){if(t%20) return false;else flag1;}else{if(t%2!0) return false;else flag0;}x/10;}return true;
}
int main(){int n;cinn;for(int i1;in;i) if(check(i)) ans;coutansendl;return 0;
} D.R格式
考试时候的代码:
#includeiostream
#includecmath
using namespace std;
typedef long long ll;
int main(){int n;double d;cinnd;ll a(ll)pow(2,n);double ansa*d;double res(ll)ans0.5;if(ansres) cout(ll)ans1endl;else cout(ll)ansendl;return 0;
}
混了一半的分数: 高精度优化(AC):
#includeiostream
#includealgorithm//reverse函数:前后翻转
#includecstring//to_string函数:数字常量转化为字符串
using namespace std;
typedef long long ll;
int n;string d;
string ans1;
string add(string a,string b){string res;int laa.size(),lbb.size();int ila-1,jlb-1,jw0;while(i0||j0){int sumjw;if(i0) suma[i--]-0;if(j0) sumb[j--]-0;jwsum/10;resto_string(sum%10);}if(jw) resto_string(jw);reverse(res.begin(),res.end());return res;
}
string mul(string a,string b){string res0;int laa.size(),lbb.size();for(int ila-1;i0;i--){int jw0;string temp;for(int jlb-1;j0;j--){int sum(a[i]-0)*(b[j]-0)jw;jwsum/10;tempto_string(sum%10);}if(jw) tempto_string(jw);reverse(temp.begin(),temp.end());for(int k0;kla-1-i;k) temp0;resadd(res,temp);}return res;
}
int main(){cinnd;while(n--) ansmul(ans,2);string newd;int flag;for(int i0;id.size();i){if(d[i]!.) newdd[i];else flagd.size()-i-1;}ansmul(newd,ans);int keyans.size()-flag;string s;for(int i0;ikey;i) sans[i];if(ans[key]5) sadd(s,1);couts;return 0;
}
E.宝石组合
整体思路(当然考试时候我肯定是没想出来):
由最小公倍数和最大公约数的性质
我们可以推出S的值就等于三个数的最大公约数gcd(h[a],h[b],h[c])
当三个数的最大公约数最大时,s最大,然后把包含此因子的三个最小数输出即可
//最大公约数
int gcd(int a,int b){return b0?a:gcd(b,a%b);
}
//最小公倍数
int lcm(int a,int b){return a*b/gcd(a,b);
}
暴力:
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N1e55;
int n,h[N],ans[5],res[5],temp0;
int gcd(int a,int b){return b0?a:gcd(b,a%b);
}
int gcd3(int a,int b,int c){return gcd(gcd(a,b),c);
}
void dfs(int x,int startt) {if(x3){int ygcd3(h[ans[1]],h[ans[2]],h[ans[3]]);if(ytemp){res[1]ans[1],res[2]ans[2],res[3]ans[3];tempy;}return ;}for(int istartt;in;i){ans[x]i;dfs(x1,i1);ans[x]0;}
}
int main(){cinn;for(int i1;in;i) cinh[i];dfs(1,1);h[1]h[res[1]],h[2]h[res[2]],h[3]h[res[3]];sort(h1,h4);couth[1] h[2] h[3]endl;return 0;
} 优化思路(AC):
#includeiostream
#includealgorithm
#includevector
#includecmath
using namespace std;
const int N1e55;
int n,h[N];
vectorintans[N];
int main(){cinn;for(int i0;in;i) cinh[i];sort(h,hn);//遍历一遍把数放入其因子中for(int i0;in;i){for(int j1;jsqrt(h[i]);j){if(h[i]%j0){ans[j].push_back(h[i]);if(h[i]/j!j) ans[h[i]/j].push_back(h[i]);}}}//从最大的因子开始遍历,个数不低于3就可以输出for(int iN-1;i0;i--){if(ans[i].size()3){coutans[i][0];for(int j1;j3;j){cout ans[i][j];}break;}}return 0;
}
F.数字接龙
这题考试时候没想明白如何判断路径是否交叉,就只会dfs出所有答案可能的情况,折腾将近一个小时还没解决,最后无奈提交了样例还有-1这个情况...
实际上对于斜方向进行判断时,只需判断对于斜边的两个坐标是否被选中(AC):
#includeiostream
#includestring
using namespace std;
int n,k,a[15][15],endd0;
bool flag[15][15];
int dx[8]{-1,-1,0,1,1,1,0,-1};
int dy[8]{0,1,1,1,0,-1,-1,-1};
string ans;
//寻找方向函数
int direction(int x,int y){if(a[x][y]k-1) return 0;else return a[x][y]1;
}
//回溯字符串函数
string delete_last(string s){if(s.size()1) return ;//注意:大小为1时返回空string temp;for(int i0;is.size()-2;i) temps[i];return temp;
}
//核心函数dfs
void dfs(int x,int y){flag[x][y]true;if(xnynans.size()n*n-1){coutansendl;//只要找到字典序最小的,找到后标记enddendd;return ;}int dirdirection(x,y);for(int i0;i7;i){int xxxdx[i],yyydy[i];if(xx1xxnyy1yyna[xx][yy]dirflag[xx][yy]false){//判断斜方向情况,i才是真正的方向,direction只是方向的值if(i1flag[x-1][y]flag[x][y1]) continue;else if(i3flag[x][y1]flag[x1][y]) continue;else if(i5flag[x1][y]flag[x][y-1]) continue;else if(i7flag[x-1][y]flag[x][y-1]) continue;else{flag[xx][yy]true;ansto_string(i);dfs(xx,yy);//在回溯时,特判一下已经找到答案的情况if(endd) return ;//回溯flag[xx][yy]false;ansdelete_last(ans);}}}return ;
}
int main(){cinnk;//注意:k的值不可能大于pow(n,2)if(kn*n){puts(-1);return 0;}for(int i1;in;i) for(int j1;jn;j) cina[i][j];dfs(1,1);//利用endd标记是否成功dfsif(!endd) puts(-1);return 0;
}
G.爬山
这题利用STL的优先队列进行模拟,考试时候魔法一和魔法二相同时候的情况没完善明确,因此下面这段代码肯定会有问题,但考完试我隐约记得while(m--)好像被我写成了while(n--),我真是个**:
#includeiostream
#includecmath
#includequeue
using namespace std;
typedef long long ll;
const int N1e55;
int n,p,q,h[N];
ll ans;
priority_queueint,vectorint,lessintpq;
int magic(int x){int asqrt(x);int bx/2;if(ab) return 2;else if(ab) return 1;else return 0;
}
int main(){cinnpq;for(int i1;in;i){int x;cinx;pq.push(x);}int mpq;while(m--){int tpq.top();pq.pop();if(p0q0){int ttmagic(t);if(tt0){if(qp) pq.push(t/2),q--;else pq.push((int)sqrt(t)),p--;}else if(tt1){pq.push((int)sqrt(t));p--;}else{pq.push(t/2);q--;}}else if(p0q0){pq.push((int)sqrt(t)),p--;}else if(q0p0){pq.push(t/2),q--;}else{break;}}while(pq.size()){anspq.top();pq.pop();}coutansendl;return 0;
} HACK数据:
2 1 1
49 48
H.拔河
这题考试时候直接理解错题目了(哭),以为每一人都要参加拔河,估计直接零蛋了haha
所以做题时一定要认真把题目读清楚...
暴力枚举两个连续区间的左右端点:
#includeiostream
using namespace std;
typedef long long ll;
const int N1e35;
ll n,a[N],l1,r1,l2,r2,ans1e18;//不开浪浪见祖宗...
int main(){cinn;for(int i1;in;i){//前缀和cina[i];a[i]a[i-1];}for(int l11;l1n;l1){for(int r11;r1n;r1){for(int l21;l2n;l2){for(int r21;r2n;r2){if(l1r1r1l2l2r2){ll sum1a[r1]-a[l1-1];ll sum2a[r2]-a[l2-1];ansmin(ans,abs(sum2-sum1));}}}}}coutansendl;return 0;
} 前缀和multiset(AC):
#includeiostream
#includeset
using namespace std;
typedef long long ll;
const int N1e35;
ll n,a[N],ans1e18;
multisetlls;
int main(){cinn;for(int i1;in;i){cina[i];a[i]a[i-1];}//利用multiset(有序并且可以重复)记录所有可能的区间for(int l1;ln;l) for(int r1;rn;r) if(rl) s.insert(a[r]-a[l-1]);//枚举左区域的右端点for(int r1;rn;r){//删除以r为左端点的所有区间,因为接下来右区间是从r1开始选择//如果保留之前的以r为左端点的右区间之和,会影响答案for(int ir;in;i) s.erase(s.find(a[i]-a[r-1]));//枚举左区间的左端点for(int l1;lr;l){//计算左区间ll tempa[r]-a[l-1];auto xs.lower_bound(temp);//multiset.lower_bound(key)函数返回一个迭代器//返回第一个key的元素//如果key容器max,则返回当前容器中最后一个元素的位置if(x!s.end()){ansmin(ans,abs(*x-temp));//和temp右侧的*x更新ans}if(x!s.begin()){x--;//先向左移动xansmin(ans,abs(*x-temp));//和temp左侧的*x更新ans}}}coutansendl;return 0;
}
