持续雷击

比赛地址

牛客OJ

Pro : 3/5/11

Rank: 312/1159

[B] Boundary

题意

给出平面上n个点,找到一个过原点的圆,使得其能覆盖最多的点.

题解

因为已知原点在圆上,所以只需要枚举两个点就可以确定一个圆.枚举出所有的组合,算出共\frac{n(n-1)}{2}个圆心.找到其中出现次数最多的圆心,设出现了k次,则答案一定是C_{Ans}^{2}=k的解,这是显然的.总的时间复杂度为O(n^{2}logn).

本题卡精度,eps需要设到1e-10.

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>

#define IL inline
#define LL int
#define ULL unsigned LL
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;

#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FD(i,l,r) for(int i=(l);i<=(r);++i)

#define MIN(a, b) ((a)<(b)?(a):(b))
#define MAX(a, b) ((a)>(b)?(a):(b))

using D = double;

constexpr D eps(1e-10);
constexpr int MN(5e3);

constexpr int sign(D x)
{
    return x<-eps ? -1 : (x > eps ? 1 : 0);
}

struct Po
{
    D x, y;
    int hash() const
    {
        return 0;
    }
    bool operator <(const Po & o) const
    {
        return sign(x-o.x) < 0 || !sign(x-o.x) && sign(y-o.y) < 0;
    }
    bool operator ==(const Po & o) const
    {
        return !sign(x-o.x) && !sign(y-o.y);
    }
} v[2000005];
struct Poo
{
    int x, y;
    bool operator ==(const Poo & o) const
    {
        return x==o.x && y==o.y;
    }
};
using namespace std;


int main()
{
    unordered_map<int, int> findcn;

    Poo p[MN];
    int cnt[MN];
    _IO
    get(n)
    if (n <= 1)
        return printf("%d\n", n), 0;

    for (int i=1; i<=n; ++i)
        findcn[i*(i-1)/2] = i;

    for (int i=0; i<n; ++i)
    {
        sc(p[i].x)
        sc(p[i].y)
    }

    int vnt = 0;

    const int nn = n-1;
    for (int i=0; i<nn; ++i)
    {
        for (int j=i+1; j<n; ++j)
        {
            D a = -p[i].x;
            D b = -p[i].y;
            D c = -p[j].x;
            D d = -p[j].y;
            D e = (-p[i].x*p[i].x - p[i].y*p[i].y) / (D(2));
            D f = (-p[j].x*p[j].x - p[j].y*p[j].y) / (D(2));
            D fm = b*c-a*d;
            if (!sign(fm))
                continue;
            v[vnt].x = (b*f-d*e)/fm, v[vnt].y = (c*e-a*f)/fm, ++vnt;
//          v.emplace_back(std::move(Po( (b*f-d*e)/fm, (c*e-a*f)/fm )));
        }
    }

    std::sort(v, v+vnt);

    int ans = 0;
    for (int i=0; i<vnt; )
    {
        int j;
        for (j=i+1; j<vnt&&v[i]==v[j]; ++j);
        if (j-i > ans)
            ans = j-i;
        i = j;
    }

    printf("%d", findcn[ans]);
    return 0;
}

[C] Cover the Tree

题意

给出一棵树,求最少的路径数,使得树上的每条边至少被覆盖了一次.

题解

显然,每条选择的路径一定是以叶子节点为起止点的.如果叶子的数目是n的话,答案就是\frac{n+1}{2}.接下来是如何将这些叶子两两配对.先求出DFS序,设a_{i}表示第i个叶子.只需要让a_{i}与a_{\frac{n}{2}+i}配对即可.对于叶子数是奇数的情况单独判断下就好.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y,lsum=1,cnt,root,ans,tot;
int head[N],d[N],v[N],f[N],size[N],msize[N];

struct Edge{
    int t,next;
}e[N*8];

struct Data{
    int x,y;
}Ans[N];

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

inline void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

IL void Dfs(int x,int fa){
    reg int i=0;
    if (d[x]==1)    {
        v[++v[0]]=x;    return;
    }
    for (i=head[x];i;i=e[i].next)   if (e[i].t!=fa) Dfs(e[i].t,x);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    if (n==1){
        puts("0");  return 0;
    }
    if (n==2){
        puts("1");  puts("1 2");    return 0;
    }
    for (i=1;i<n;i++){
        x=read();   y=read();
        d[x]++; d[y]++;
        Add(x,y);   Add(y,x);
    }
    for (i=1;i<=n;i++)
    if (d[i]>1){
        Dfs(i,0);
        break;
    }
    x=v[0]/2;
    for (i=1;i<=x;i++){
        ans++;
        Ans[ans].x=v[i];    Ans[ans].y=v[i+x];
    }
    if (v[0]&1){
        ans++;
        Ans[ans].x=v[1];    Ans[ans].y=v[v[0]];
    }
    printf("%d\n",ans);
    for (i=1;i<=ans;i++)    printf("%d %d\n",Ans[i].x,Ans[i].y);
    return 0;
}

[D] Duration

题意&题解

签到题

代码

h1,m1,s1 = map(int, input().split(':'))
h2,m2,s2 = map(int, input().split(':'))

t1 = h1*60*60 + m1*60 + s1
t2 = h2*60*60 + m2*60 + s2

print(abs(t1-t2))

[F] Fake Maxpooling

题意

给出一个n\times m的方阵,a_{ij}=lcm(i,j).求这个方阵中,每一个k \times k子阵的最大值之和.

题解

预处理出方阵后拿单调队列直接计算即可.

据说算lcm时会卡常,用了一个神奇的gcd写法直接莽过去了.

代码

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

#define T int
T gcd(T __a, T __b) {
    T __tp;
    while (__b) {
        __tp = __a % __b;
        __a = __b;
        __b = __tp;
    }
    return __a;
}

struct node{ int x, y; } v[5050];
int mn1[5050][5050], s[5050][5050], n, m, k;
void getmin() {
    for (int t = 1; t <= n; t++) {
        int i, head = 1, tail = 0;
        for (i = 1; i <= 5000; i++) v[i].x = v[i].y = 0;
        for (i = 1; i < k; i++) {
            while(head <= tail && v[tail].x <= s[t][i]) tail--;
            v[++tail].x = s[t][i], v[tail].y = i;
        }
        for (; i <= m; i++) {
            while (head <= tail && v[tail].x <= s[t][i]) tail--;
            v[++tail].x = s[t][i], v[tail].y = i;
            while (v[head].y < i-k+1) head++;
            mn1[t][i-k+1] = v[head].x;
        }
    }
    for (int t = 1; t <= (m-k+1); t++) {
        int i, head = 1, tail = 0;
        for (i = 1; i <= 5000; i++) v[i].x = v[i].y = 0;
        for (i = 1; i < k; i++) {
            while(head <= tail && v[tail].x <= mn1[i][t]) tail--;
            v[++tail].x = mn1[i][t], v[tail].y = i;
        }
        for (; i <= n; i++) {
            while(head <= tail && v[tail].x <= mn1[i][t]) tail--;
            v[++tail].x = mn1[i][t], v[tail].y = i;
            while(v[head].y < i-k+1) head++;
            s[i-k+1][t] = v[head].x;
        }
    }
}

int main() {
    for (int i = 1; i <= 5000; i++) for (int j = i; j <= 5000; j++) s[i][j] = i*j/gcd(j, i);
    for (int i = 1; i <= 5000; i++) for (int j = 1; j < i; j++) s[i][j] = s[j][i];
    scanf("%d%d%d", &n, &m, &k);
    getmin();
    long long int ans = 0;
    for (int i = 1; i <= n-k+1; i++) for (int j = 1; j <= m-k+1; j++)
        ans += s[i][j];
    cout << ans << endl;
    return 0;
}

[G] Greater and Greater

题意

给出一个长度为n的序列和一个长度为m的序列,m<n.求将第二个序列放到原序列的哪些位置,可以让第一个序列的值大于等于第二个序列的值.

题解

bitset的奇妙用法.

预处理出第二个序列中,每个位置可以放在哪里,然后与到一起,再统计一下1的数目就行了.时间复杂度是O(\frac{nm}{64}).

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 150010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,cnt,Ans;
int a[N],b[N],l[N*2];

bitset <N> c,v,ans;

struct Data{
    int x,y,id;
}p[N*2];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

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

IL bool cmp(Data x,Data y){return (x.x==y.x)?x.y<y.y:x.x<y.x;}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    for (i=1;i<=n;i++)  a[i]=read(),l[++l[0]]=a[i];
    for (i=1;i<=m;i++)  b[i]=read(),l[++l[0]]=b[i];
    sort(l+1,l+1+l[0]);
    for (i=1;i<=n;i++)  a[i]=lower_bound(l+1,l+1+l[0],a[i])-l;
    for (i=1;i<=m;i++)  b[i]=lower_bound(l+1,l+1+l[0],b[i])-l;
    cnt=0;
    for (i=1;i<=n;i++){
        ++cnt;
        p[cnt].x=a[i];  p[cnt].y=1; p[cnt].id=i;
    }
    for (i=1;i<=m;i++){
        ++cnt;
        p[cnt].x=b[i];  p[cnt].y=0; p[cnt].id=i;
    }
    sort(p+1,p+1+cnt,cmp);
    for (i=1;i<=n-m+1;i++)  ans[i]=1;
    for (i=cnt;i;i--){
        if (p[i].y==1){
            v[p[i].id]=1;   continue;
        }
        c=v>>(p[i].id-1);   ans&=c;
    //  for (int j=1;j<=n;j++)  cout<<c[j];
    //  cout<<endl;
    }
    cout<<ans.count()<<endl;
    return 0;
}

[H] Happy Triangle

题意

有三种操作,第一种是往一个集合里加入一个数,第二种是删除一个数.第三种是询问操作,给出一个数,问能否从集合中取出两个数,使得这三个数构成一个合法的三角形.

题解

对于给出的数,分最大边和不是最大边讨论.

对于不是最大边的情况,只需要求两个前驱;对于最大边的情况,只需要考虑所有相邻的数就行.证明是显然的.

官方题解需要写一个平衡树,其实可以通过两个set+线段树解决.

代码

待填

[K] Keyboard Free

题意

已知三个同心圆的半径,求在这三个圆上各随机取一个点所构成的三角形的面积的期望.

题解

首先可以固定一个点.当第二个点也固定之后,和第一个点连线,先算出第三个点到该直线的距离的期望,再算面积的期望.因为精度要求不是很高,第二个点可以随机取足够多次.

实际测试发现卡常卡精度QAQ

代码

待填

总结

开题策略大失败.

C题一开始没什么思路,就一直在写B.结果因为没注意看条件,以为会有点重合的情况,自己给自己加了一堆限制条件,代码也改了好几版.发现只需要交初版代码的时候又被卡了精度莫名WA,最后凭直觉改了eps才过去.

因为在B题上浪费了太多时间,后期又一直在死磕C题和K题,导致有些题根本就没有读,错失了过G题和H题的机会.K题思路已经是正确的了,但是剩的时间太短来不及推式子,后期节奏彻底崩塌.

望之后引以为戒QAQ.