带分数
#include<bits/stdc++.h> #define rep(i,l,r) for(int i=l;i<=r;++i) using namespace std; int a[15]; int main() { for(int i=0; i<10; ++i)a[i]=i; int n,ans=0; scanf("%d",&n); do { for(int p=1; p<8; ++p) { // 整数到 i for(int d=p+1; d<=8; ++d) { // 分数到j int num=0,up=0,down=0; for(int i=1;i<=p;++i)num=num*10+a[i]; for(int i=p+1;i<=d;++i)up=up*10+a[i]; for(int i=d+1;i<=9;++i)down=down*10+a[i]; if(up%down==0){ if(num+up/down==n){ ++ans; } } } } } while (next_permutation(a+1,a+10)); printf("%d",ans); return 0; }
不会T。
>>> from math import factorial as f >>> f(9)*8*8 23224320
数字三角形
暴力代码:
#include<bits/stdc++.h> #define rep(i,l,r) for(int i=l;i<=r;++i) using namespace std; int a[105][105]; const int N=105; int ans=0,n,m; void dfs(int val,int i,int j,int L,int R) { if(i==n+1 and abs(L-R)<=1) { ans=max(val,ans); return ; } if(L>m or R>m )return ; dfs(val+a[i][j],i+1,j,L+1,R);// left dfs(val+a[i][j],i+1,j+1,L,R+1);// right } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; m=(n-1)/2+(n-1)%2; for(int i=1; i<=n; ++i) for(int j=1; j<=i; ++j) cin>>a[i][j]; dfs(0,1,1,0,0); cout<<ans<<'\n'; return 0; }
其实在写暴力的时候我们就发现了对于状态空间的遍历,其实保证L,R不越出上限即可。
而这个搜索的可行域就如下图所示。
于是可以dp
#include<bits/stdc++.h> using namespace std; int a[105][105]; const int N=105; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) cin>>a[i][j]; int mid = n / 2 + 1; /* for(int i=1,L,R; i<=n; ++i) { if(i<=mid)L=1,R=i; else L=1+i-mid,R=i-(i-mid); for(int j=1; j<L; ++j)putchar(' '); for(int j=L; j<=R; ++j)putchar('*'); for(int j=R+1; j<=i; ++j)putchar(' '); putchar('\n'); } */ for(int i=1,L,R; i<=n; ++i) { if(i<=mid)L=1,R=i; else L=1+i-mid,R=i-(i-mid); for(int j=1; j<L; ++j) a[i][j]=0; for(int j=R+1; j<=i; ++j) a[i][j]=0; } for(int i=n-1; i; --i)for(int j=1; j<=i; ++j) a[i][j]+=max(a[i+1][j],a[i+1][j+1]); cout<<a[1][1]; return 0; }
荒岛探测
求一个椭圆和三角的公共面积
蒙特卡洛:
#include <bits/stdc++.h> using namespace std; class Vector3 { public: Vector3(double fx, double fy, double fz) : x(fx), y(fy), z(fz) {} // Subtract Vector3 operator-(const Vector3& v) const { return Vector3(x - v.x, y - v.y, z - v.z); } // Dot product double Dot(const Vector3& v) const { return x * v.x + y * v.y + z * v.z; } // Cross product Vector3 Cross(const Vector3& v) const { return Vector3(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x); } public: double x, y, z; }; // Determine whether two vectors v1 and v2 point to the same direction // v1 = Cross(AB, AC) // v2 = Cross(AB, AP) bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P) { Vector3 AB = B - A; Vector3 AC = C - A; Vector3 AP = P - A; Vector3 v1 = AB.Cross(AC); Vector3 v2 = AB.Cross(AP); // v1 and v2 should point to the same direction return v1.Dot(v2) >= 0; } // Same side method // Determine whether point P in triangle ABC bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P) { return SameSide(A, B, C, P) && SameSide(B, C, A, P) && SameSide(C, A, B, P); } inline double cro(Vector3 A, Vector3 B) { return A.x * B.y - A.y * B.x; } double S(Vector3 A, Vector3 B, Vector3 C) { double ans = cro(B - A, C - A); return ans / 2; } #define point(x, y) Vector3(x, y, 0) #define x first #define y second mt19937 rd(time(0)); typedef pair<double, double> pii; pii a[5]; double L; pii s, t; inline bool in(double xx, double yy) { double dis1 = sqrt((xx - s.x) * (xx - s.x) + (yy - s.y) * (yy - s.y)); double dis2 = sqrt((xx - t.x) * (xx - t.x) + (yy - t.y) * (yy - t.y)); return dis1 + dis2 <= L; } const int N = 4e6; int main() {//srand(time(0)); cin >> s.x >> s.y >> t.x >> t.y >> L; double maxx = -1000, minx = 1000; double maxy = -1000, miny = 1000; for (int i = 1; i <= 3; ++i) { cin >> a[i].x >> a[i].y; maxx = max(maxx, a[i].x); minx = min(minx, a[i].x); maxy = max(maxy, a[i].y); miny = min(miny, a[i].y); } sort(a + 1, a + 4); Vector3 A = point(a[1].x, a[1].y); Vector3 B = point(a[2].x, a[2].y); Vector3 C = point(a[3].x, a[3].y); int xRange = (maxx - minx) * 1000; int yRange = (maxy - miny) * 1000; int valid = 0, tot = 0; for (int i = 0; i < N; ++i) { double xx = minx + 0.001 * (rd() % xRange); double yy = miny + 0.001 * (rd() % yRange); Vector3 P = point(xx, yy); if (PointinTriangle(A, B, C, P)) { ++tot; if (in(xx, yy)) ++valid; } } double ans = S(A, B, C) / tot * valid; printf("%.2lf\n", ans); return 0; } /* 10 6 4 12 12 0 2 13 2 13 15 39.9 */
格点法(30%)
#include <bits/stdc++.h> using namespace std; typedef double db; class Vector3 { public: Vector3(db fx, db fy, db fz) : x(fx), y(fy), z(fz) {} // Subtract Vector3 operator-(const Vector3& v) const { return Vector3(x - v.x, y - v.y, z - v.z); } // Dot product db Dot(const Vector3& v) const { return x * v.x + y * v.y + z * v.z; } // Cross product Vector3 Cross(const Vector3& v) const { return Vector3(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x); } public: db x, y, z; }; // Determine whether two vectors v1 and v2 point to the same direction // v1 = Cross(AB, AC) // v2 = Cross(AB, AP) bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P) { Vector3 AB = B - A; Vector3 AC = C - A; Vector3 AP = P - A; Vector3 v1 = AB.Cross(AC); Vector3 v2 = AB.Cross(AP); // v1 and v2 should point to the same direction return v1.Dot(v2) >= 0; } // Same side method // Determine whether point P in triangle ABC bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P) { return SameSide(A, B, C, P) && SameSide(B, C, A, P) && SameSide(C, A, B, P); } inline db cro(Vector3 A, Vector3 B) { return A.x * B.y - A.y * B.x; } db S(Vector3 A, Vector3 B, Vector3 C) { db ans = cro(B - A, C - A); return ans / 2; } #define point(x, y) Vector3(x, y, 0) #define x first #define y second typedef pair<db, db> pii; pii a[5]; db L; pii s, t; inline bool in(db xx, db yy) { db dis1 = sqrt((xx - s.x) * (xx - s.x) + (yy - s.y) * (yy - s.y)); db dis2 = sqrt((xx - t.x) * (xx - t.x) + (yy - t.y) * (yy - t.y)); return dis1 + dis2 <= L; } const int N = 5000; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> s.x >> s.y >> t.x >> t.y >> L; db maxx = -1000, minx = 1000; db maxy = -1000, miny = 1000; for (int i = 1; i <= 3; ++i) { cin >> a[i].x >> a[i].y; maxx = max(maxx, a[i].x); minx = min(minx, a[i].x); maxy = max(maxy, a[i].y); miny = min(miny, a[i].y); } Vector3 A = point(a[1].x, a[1].y); Vector3 B = point(a[2].x, a[2].y); Vector3 C = point(a[3].x, a[3].y); db xDeata = (maxx - minx) * 0.0002; db yDelta = (maxy - miny) * 0.0002; int valid = 0, tot = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { db xx = minx + i * xDeata; db yy = miny + j * yDelta; if (PointinTriangle(A, B, C, point(xx, yy))) { ++tot; if (in(xx, yy)) ++valid; } } } db ans = S(A, B, C) / tot * valid; cout << fixed << setprecision(4) << ans << endl; return 0; } /* 10 6 4 12 12 0 2 13 2 13 15 39.9 */
正解:
https://blog.csdn.net/m0_48960163/article/details/115124027
# https://blog.csdn.net/qq_48081868/article/details/115298527?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-7.control&dist_request_id=1329187.12801.16178920724796009&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-7.control import math class Line: def __init__(self,a,b,start,end): self.a=a self.b=b self.start=start self.end=end class Solution: #输入:输入第第一行包含五个整数,分别为XA,YA,XB,YB,L # 第二行包含六个整数:分别为x1,y1,x2,y2,x3,y3 #输出: # 输出一行,包含一个实数,四舍五入保留2位小数,表示答案 def desertIsland(self,tance,triangle): #1.求出椭圆方程的a,b,c。并且知道x*2/a*2+y*2/b*2=1 a=tance[4]/2 c=math.sqrt((tance[0]-tance[2])**2+(tance[1]-tance[3])**2)/2 b=math.sqrt(a**2-c**2) #2.进行坐标轴的变换,先进行坐标轴的平移,然后进行坐标轴的旋转 #坐标轴逆时针旋转a°,则新的坐标位x=Xcosa+Ysina,y=Ycosa-Xsina horn=math.atan((tance[3]-tance[1])/(tance[2]-tance[0])) O_offset=((tance[0]+tance[2])/2,(tance[1]+tance[3])/2) p1_temp=(triangle[0]-O_offset[0],triangle[1]-O_offset[1]) p2_temp=(triangle[2]-O_offset[0],triangle[3]-O_offset[1]) p3_temp=(triangle[4]-O_offset[0],triangle[5]-O_offset[1]) p1_new=(p1_temp[0]*math.cos(horn)+p1_temp[1]*math.sin(horn),-p1_temp[0]*math.sin(horn)+p1_temp[1]*math.cos(horn)) p2_new=(p2_temp[0]*math.cos(horn)+p2_temp[1]*math.sin(horn),-p2_temp[0]*math.sin(horn)+p2_temp[1]*math.cos(horn)) p3_new=(p3_temp[0]*math.cos(horn)+p3_temp[1]*math.sin(horn),-p3_temp[0]*math.sin(horn)+p3_temp[1]*math.cos(horn)) #3.x从-a到a,计算每一个小矩形的面积。然后累加得到答案 #3.1计算x_start,x_end #3.2计算出三条直线的方程,并且存储 #3.3将积分计算出答案 x_start=max(-a,min(p1_new[0],p2_new[0],p3_new[0])) x_end=min(a,max(p1_new[0],p2_new[0],p3_new[0])) lines=list() #求a1,b1 a1_parent=(p2_new[0]-p1_new[0]) if a1_parent: a1=(p2_new[1]-p1_new[1])/a1_parent b1=p1_new[1]-a1*p1_new[0] start1=min(p1_new[0],p2_new[0]) end1=max(p1_new[0],p2_new[0]) line1=Line(a=a1,b=b1,start=start1,end=end1) lines.append(line1) #求a2,b2 a2_parent=(p3_new[0]-p2_new[0]) if a2_parent: a2=(p3_new[1]-p2_new[1])/a2_parent b2=p2_new[1]-a2*p2_new[0] start2=min(p2_new[0],p3_new[0]) end2=max(p2_new[0],p3_new[0]) line2=Line(a=a2,b=b2,start=start2,end=end2) lines.append(line2) #a3,b3 a3_parent=(p1_new[0]-p3_new[0]) if a3_parent: a3=(p1_new[1]-p3_new[1])/a3_parent b3=p3_new[1]-a3*p3_new[0] start3=min(p1_new[0],p3_new[0]) end3=max(p1_new[0],p3_new[0]) line3=Line(a=a3,b=b3,start=start3,end=end3) lines.append(line3) x=x_start res=0 step=0.001 while x<=x_end: temp=[] for i,line in enumerate(lines): if line.start<=x and line.end>=x: temp.append(x*line.a+line.b) temp_big=max(temp[0],temp[1]) temp_little=min(temp[0],temp[1]) tuoyuan_temp=math.sqrt((1-(x**2)/(a**2))*(b**2)) y_big=min(temp_big,tuoyuan_temp) y_little=max(temp_little,-tuoyuan_temp) if y_big>=y_little: res+=step*(y_big-y_little) x+=step return round(res,2) if __name__=='__main__': solution=Solution tance=list(map(int,input().split())) triangle=list(map(int,input().split())) result=solution.desertIsland(solution,tance,triangle) print(result)
日期问题
http://lx.lanqiao.cn/problem.page?gpid=T443
#include<bits/stdc++.h> using namespace std; int s[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; struct date { int y, m, d; bool operator < (const date& a) const { if (y != a.y) return y < a.y; if (m != a.m) return m < a.m; return d < a.d; } }; set<date>st; void chk (int y, int m, int d) { if (y >= 60) y += 1900; else y += 2000; date now; now.y = y, now.m = m, now.d = d; bool r = 0; if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0) r = 1; if (m > 12 || m < 1) return ; if (m == 2) { if (d >= 1 && d <= s[m] + r) st.insert (now); return ; } if (d >= 1 && d <= s[m]) st.insert (now); } int main() { // for (int i = 1; i <= 12; ++i) cout << i << ' ' << s[i] << endl; int a, b, c; scanf ("%d/%d/%d", &a, &b, &c); //1960年1月1日至2059年12月31日 //年/月/日 月/日/年 日/月/年 chk (a, b, c); chk (c, a, b); chk (c, b, a); set<date>::iterator it = st.begin(); for (; it != st.end(); ++it) { date p = *it; printf ("%d-%02d-%02d\n", p.y, p.m, p.d); } return 0; }
错误票据
#include<bits/stdc++.h> using namespace std; int main() { int n,x; int ans1,ans2; set<int>st; scanf ("%d", &n); for(int i=0;i<n;++i){ scanf("%d",&x); if(st.count(x))ans2=x;else st.insert(x); } for(int l=*st.begin(),i=l;i<l+n;++i){ if(!st.count(i)){ ans1=i;break; } }printf("%d %d\n",ans1,ans2); return 0; }