寒假学习计划

比赛地址

牛客

[A] Alternative Accounts

题意

有一场比赛举办了k天,1\leq k\leq 3,每天有一些不同的账号参与.求这些账号最少属于多少人.

注:一个人在一天中只能使用一个账号

题解

不难发现,答案是出现了至少两次的账号和参赛人数最大值中最大的那个.证明显然.

代码

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int MN(1e5+7);


int main()
{
    unordered_set<int> hs[3];
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int m, n[3] = {}, k, x;
    cin >> m >> k;
    for (int i=0; i<k; ++i)
    {
        cin >> n[i];
        for (int j=0; j<n[i]; ++j)
            cin >> x, hs[i].insert(x);
    }

    if (k != 3)
        return cout << max(n[0], n[1]), 0;

    int c[3][3] = {}, cr = 0;
    int a[3] = {};
    for (int i=0; i<3; ++i)
        for (int j=i+1; j<3; ++j)
            for (int x : hs[i])
                c[i][j] += hs[j].count(x);

    for (int x : hs[2])
        cr += hs[1].count(x) && hs[0].count(x);

    cout << max(c[0][1] + c[0][2] + c[1][2] - 2 * cr, *max_element(n, n+3));
}

[E] Matching Problem

题意

给出一个长度为n的序列a和一个长度为4的序列b,求a中有多少子序列是和b相似的.相似的定义是,a_i=a_j \iff b_i=b_j,且两序列长度一样.

题解

枚举a序列前三位,根据b序列第四位和前三位的相等或不等情况,通过预处理好的前缀和实现O(1)统计.总的时间复杂度为O(n^3)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 310
using namespace std;

int n,i,j,k,flag;
LL Ans=0;
int a[N],b[50];
int s[N][N];

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    if (n<=3)   {puts("0"); return 0;}
    for (i=1;i<=n;i++)  a[i]=read(),s[i][a[i]]++;
    for (i=1;i<=4;i++)  b[i]=read();
    for (i=1;i<=n;i++)
        for (j=1;j<=300;j++)
            s[i][j]+=s[i-1][j];
    if (b[1]==b[4]) flag=1;
    if (b[2]==b[4]) flag=2;
    if (b[3]==b[4]) flag=3;
    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++){
            if (b[1]==b[2] && a[i]!=a[j])   continue;
            if (b[1]!=b[2] && a[i]==a[j])   continue;
            for (k=j+1;k<=n;k++){
                if (b[1]==b[3] && a[i]!=a[k])   continue;
                if (b[1]!=b[3] && a[i]==a[k])   continue;
                if (b[3]==b[2] && a[k]!=a[j])   continue;
                if (b[3]!=b[2] && a[k]==a[j])   continue;
                //cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<endl;
                if (flag){
                    if (flag==1)    Ans+=s[n][a[i]]-s[k][a[i]];
                    if (flag==2)    Ans+=s[n][a[j]]-s[k][a[j]];
                    if (flag==3)    Ans+=s[n][a[k]]-s[k][a[k]];
                }
                else {
                    Ans+=n-k-(s[n][a[i]]-s[k][a[i]]);
                    if (a[i]!=a[j]) Ans-=(s[n][a[j]]-s[k][a[j]]);
                    if (a[i]!=a[k] && a[j]!=a[k])   Ans-=(s[n][a[k]]-s[k][a[k]]);
                    //cout<<Ans<<endl;
                }
            }
        }
    cout<<Ans<<endl;
    return 0;
}

[G] Cryptographically Secure PRNG

题意

给出一个质数p,求所有满足模p意义下,x^{-1}=min_{i=2}^{x}i^{-1}的x

题解

题目保证了p是随机的,所以可以从头开始线性求逆元,统计可能符合题意的逆元对.因为p的随机性,保证了统计过程的时间复杂度期望为O(\sqrt{p}).(?不是很严谨,具体的推导回头补)

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int T;
long long int p, inv[1000000], mo;
long long int anstot, tot;

struct point {
    long long int a, b;
}ans[1000000], res[1000000];

bool cmp(point x, point y) {
    return x.a < y.a;
}

int main(){
    cin >> T;
    while(T--) {
        scanf("%lld", &p); mo = p;
        inv[1] = 1;
        anstot = tot = 0;
        long long int nowmin = p + 1;
        for (int i = 2; i < p; i++) {
            inv[i] = inv[mo % i] * (mo - mo/i) % mo;
            if (inv[i] > nowmin) continue;
            nowmin = min(nowmin, inv[i]);
            if (i > inv[i]) break;
            ans[++anstot].a = i; ans[anstot].b = inv[i];
            if (i == inv[i]) break;
            ans[++anstot].a = inv[i]; ans[anstot].b = i;
        }
        long long int now = inv[2];
        sort(ans + 1, ans + anstot + 1, cmp);
        for (int i = 1; i <= anstot; i++) {
            now = min(now, ans[i].b);
            if (ans[i].b == now) res[++tot].a = ans[i].a, res[tot].b = ans[i].b;
        }
        printf("%d\n", tot);
        for (int i = 1; i <= tot; i++) {
            printf("%lld %lld\n", res[i].a, res[i].b);
        }
    }
    return 0;
}

[H] Geometry PTSD

题意

提答题,要求给出单位球上的三个点,使得原点到这三个点构成平面的距离小于10^{-18},且要求三个点构成的三角形的最短边的变长大于1.7.

每个点的输出格式为x,y,z,表示\frac{x}{\sqrt{x^2+y^2+z^2}},\frac{y}{\sqrt{x^2+y^2+z^2}},\frac{z}{\sqrt{x^2+y^2+z^2}},其中,x,y,z均为整数

题解

1.7基本上明示了等边三角形.所以考虑球面上三点A(-1,0,0),B(\frac{1}{2},\frac{\sqrt{3}}{2},0),C(\frac{1}{2},-\frac{\sqrt{3}}{2},0),原点到其所在平面距离为0,符合题意,长度也满足要求.关键是B和C的坐标很难用题目中要求的方式表达出来.

于是使用Python暴力计算出比较接近的一对数,替代前两位坐标就好了.

代码

print("-1 0 0")
print("577350 1000000 0")
print("577350 -1000000 0")