蓝桥杯官网往届试题

带分数

#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;
}

算法竞赛之路文章被收录于专栏

整理、记录算法竞赛的好题