2022杭电多校第二场

C++ to Python（模拟 思维）

题意
将C++代码std::make_tuple转化为Python代码并输出。

分析
将输入中所有的std::make_tuple删除，直接模拟即可。

AC代码

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        string t="std::make_tuple";
        for(int i=0;i<s.size();i++)
        {
            bool flag=true;
            for(int j=0;j<t.size();j++)
            {
                if(s[i]==t[j])
                {
                    flag=false;
                    break;
                }
            }
            if(flag) cout<<s[i];
        }
        cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Keychains（计算几何）

题意
给定三维空间中的两个圆，判断这两个圆是否相扣。题目给定两个圆的圆心、半径和法向量，保证两个圆上的两个点之间的距离不小于$0.1$

题解
首先求两个圆所在平面的交线，由一点和一个法向量可以确定一个平面。得到交线后，再求出交线和圆A的交点，交线和圆A的交点其实就是交线和球A的交点。然后判断交点是否都在圆B内，通过交点和圆心的距离和半径的大小可以判断点是否在圆内。求两个平面的交线以及直线与球的交点要确定模板的正确性。

AC代码

typedef double lf;

struct vec {
    lf x, y, z;
    vec(){} vec(lf x, lf y, lf z): x(x), y(y), z(z) {}
    vec operator-(vec b) { return vec(x - b.x, y - b.y, z - b.z); }
    vec operator+(vec b) { return vec(x + b.x, y + b.y, z + b.z); }
    vec operator*(lf k) { return vec(k * x, k * y, k * z); }
    lf sqr() { return x * x + y * y + z * z; }
    lf len() { return sqrt(x * x + y * y + z * z); }
    vec trunc(lf k = 1) { return *this * (k / len()); }
    friend vec cross(vec a, vec b) {
        return vec(
            a.y * b.z - a.z * b.y,
            a.z * b.x - a.x * b.z,
            a.x * b.y - a.y * b.x
        );
    }
    friend lf dot(vec a, vec b) {
        return a.x * b.x + a.y * b.y + a.z * b.z;
    }
    void scan() {
        scanf("%lf%lf%lf", &x, &y, &z);
    }
};

void inter_ff(vec p1, vec dir1, vec p2, vec dir2, vec &res1, vec &res2) {
	vec e = cross(dir1, dir2), v = cross(dir1, e);
	lf d = dot(dir2, v); if (abs(d) < 1e-9) return;
	vec q = p1 + v * (dot(dir2, p2 - p1) / d);
    res1 = q;
    res2 = q + e;
}

lf dist_pp(vec p1, vec p2) {
    return (p2 - p1).len();
}

lf dist_pl(vec p, vec l1, vec l2) {
    return cross(l2 - l1, p - l1).len() / (l2 - l1).len();
}

vec perpendicular_pl(vec p, vec l1, vec l2) {
    return l1 + (l2 - l1) * (dot(l2 - l1, p - l1) / (l2 - l1).sqr());
}

void solve() {
    vec p1, d1, p2, d2;
    lf r1, r2;

    p1.scan();
    d1.scan();
    scanf("%lf", &r1);
    p2.scan();
    d2.scan();
    scanf("%lf", &r2);

    vec dir = cross(d1, d2);
    if (dir.sqr() < 0.1) {
        puts("No");
        return;
    }

    vec l1, l2;
    inter_ff(p1, d1, p2, d2, l1, l2); //求平面交线 
    lf dis = dist_pl(p2, l1, l2);
    if (dis > r2) {
        puts("No");
        return;
    }
    vec delta = (l2 - l1).trunc(sqrt(r2 * r2 - dis * dis));
    vec mid = perpendicular_pl(p2, l1, l2);
    //a,b是直线与圆的交点 
    vec a = mid + delta;
    vec b = mid - delta;
    if ((dist_pp(a, p1) < r1) ^ (dist_pp(b, p1) < r1)) {
        puts("Yes");
    } else {
        puts("No");
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

Snatch Groceries（贪心 思维）

题意
给定$n$个置信区间，求在两个置信区间重叠(包括端点)前，有多少个置信区间互不重叠。题面TL;DR:意为 Too Long; Didn’t Read，Problem Description中只需读后两段。

题解
按$earliest$升序排序，检查相邻两个区间是否重叠。对于第$i$个置信区间，最有可能和它重叠的一定是$earliest$最小的。

AC代码

const int N=1e5+10;
struct node {
    int l,r;
    bool operator<(const node &a) {
        return l<a.l;
    }
}p[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>p[i].l>>p[i].r;
        sort(p+1,p+n+1);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(i<n&&p[i].r>=p[i+1].l) break;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

ShuanQ（数论 枚举）

题意
给定一个质数模数$M$，设私钥为$P$，对于公钥$Q$满足$P\times Q\equiv 1(modM)$，即$Q$是$P$模$M$意义下的逆元。
加密公式：
$encrypted\_data=raw\_data\times PmodM$
解密公式：
$raw\_data=encrypted\_data\times QmodM$
给出 $P$、$Q$ 和 $encrypted\_data$ $(P,Q,encrypted\_data<M)$，问是否可以求出$raw\_data$，如果可以确定 $raw\_data$，输出 $raw\_data$，否则输出shuanQ

题解
由$P\times Q\equiv 1(modM)$可得 $kM=P\times Q-1$，这说明$M$是$P\times Q-1$的一个比$P$和$Q$大的质因子，时间复杂度$sqrt(P\times Q-1)$

AC代码

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        ll n=a*b-1;
        ll ans;
        int cnt=0;
        for(ll i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                while(n%i==0) n/=i;
                if(i>a&&i>b&&a*b%i==1)
                {
                    ans=i;
                    cnt++;
                }
            }
        }
        if(n>1&&n>a&&n>b&&a*b%n==1)
        {
            ans=n;
            cnt++;
        }
        if(cnt>1||!cnt) cout<<"shuanQ"<<endl;
        else cout<<b*c%ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Luxury cruise ship（贪心 DP）

题意
Kayzin有7、31、365三种面值的硬币，给定一个费用，问是否可以用这三种硬币凑出这个费用，如果不存在输出$-1$，否则输出最少需要的硬币数量。

题解
对于$N$较小的询问，用背包预处理出答案。如果$N$较大，先用$365$将$N$减小到背包预处理的范围内，再算出答案。在下面的代码中预处理了$7\times 31\times 365$以内的最小值，如果不确定预处理的范围，可以在空间和时间允许的范围内尽可能多预处理。

AC代码

typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=7*31*366;
const int M=7*31*365;
ll f[N];

int main()
{
    int t;
    cin>>t;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=M;i++)
    {
        if(i>=7) f[i]=min(f[i],f[i-7]+1);
        if(i>=31) f[i]=min(f[i],f[i-31]+1);
        if(i>=365) f[i]=min(f[i],f[i-365]+1);
    }
    while(t--)
    {
        ll n;
        cin>>n;
        if(n<=M)
        {
            if(f[n]<inf) cout<<f[n]<<endl;
            else cout<<-1<<endl;
        }
        else
        {
            ll x=n-M;
            ll ans=(x+364)/365;
            ll y=n-365*ans;
            ans+=f[y];
            if(ans>=inf) cout<<-1<<endl;
            else cout<<ans<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39