---恢复内容开始---
题目难度区分度很大,感觉题目出的很好,虽然只做出了5题,但是写下题解
a题其实是一个三数和的问题,就是在一个数列中找到三个数(可以重复选择)的和为k,由于数据规模比较大,数列长度小于3000,所以如果一个一个枚举三数的方法复杂度O(n^3)应该会超时,所以需要优化一下选择过程,即先对数列排序,然后对数组中设置两个指针一个指向头一个指向尾,从第一个元素开始求和,如果三数和大于k,则将尾指针向前指,小于k的话,就将头指针向后指,如果等于就break,虽然感觉没什么特别优化,但是复杂度降到了O(n^2)
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int main() { int n,m; int num[3000]; int t=0; cin>>n>>m; for(int i=0;i<n;i++) { cin>>num[i]; } sort(num,num+n); for(int x=0;x<n;x++){ int i=x; int j=n-1; t=0; while(j>x){ if(num[x]+num[i]+num[j]==m){ t=1; break; } else if(num[x]+num[i]+num[j]>m) j--; else i++; } if(t==1){ cout<<"o hu~"<<endl; break; } } if(t==0) cout<<"wo yo wo yo~"<<endl; return 0; }
b题看了下题面,感觉跟a题差不多,可能是a题的优化升级版,所以先放了,但是后面随便交了一发O(n^3)的竟然就过了,感觉太水了
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { int n,m; int num[100]; cin>>n>>m; int sum=0; for(int i=0;i<n;i++) cin>>num[i]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int t=0;t<n;t++) if(num[i]+num[j]+num[t]==m) sum++; if(sum==0) cout<<"0/1"<<endl; else { int s=n*n*n; int t=gcd(sum,s); sum/=t; s/=t; cout<<sum<<'/'<<s<<endl; } }
c题就是求多边形的面积
这个就是多边形的面积公式
然后附上代码就行了
#include <cstdio> int main() { double x[100],y[100],s=0; int n,i; scanf("%d",&n); for(i=1; i<=n; i++) scanf("%lf%lf",&x[i],&y[i]); for(i=1; i<n; i++) s+=x[i]*y[i+1]; s+=x[n]*y[1]; for(i=2; i<=n; i++) s-=x[i]*y[i-1]; s-=x[1]*y[n]; s/=2; s+=0.5f; int num=s; printf("%d ",num); return 0; }
e题wa了好多次,难受,主要就是忘记了期望的概念,其实就是求1/(1-q);
然后就是转化成分数形式,用的是字符串形式存的
#include <iostream> #include <cstdio> #include <cmath> #include <string> #define INF 1e-8 using namespace std; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { string s; cin>>s; if(s[0]=='1') cout<<"Sorrry,JuJu!"<<endl; else { int len=s.length(); int num=0; int t=1; for(int i=2;i<len;i++){ num+=s[i]-'0'; num*=10; t*=10; } num/=10; num=t-num; int g=gcd(num,t); cout<<t/g<<'/'<<num/g<<endl; } return 0; }
f题应该就是签到题,主要就是要注意有个坑,wa了几次,就是说的和实际的差是奇数的时候一定是错的
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main() { int a,b,n; cin>>a>>b>>n; int sum=abs(a)+abs(b); if(n<sum) cout<<"NO"<<endl; else { if((n-sum)%2!=0) cout<<"NO"<<endl; else cout<<"YES"<<endl; } }
---恢复内容结束---