cf Round 594

2022-09-26 16:57:41

A.Warrior and Archer(思维)

战士一定会ban掉当前边缘的位置。而战士和射手就会选择剩下的最远的两点。
我们让剩下的最远的两点最近就达到了均衡。
于是我们枚举战士ban掉的边缘，ban的次数是一定的。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N];

int main ()

{

    int n;

    scanf("%d",&n);

    FOR(i,,n) scanf("%d",a+i);

    sort(a+,a+n+);

    int ans=INF;

    int k=n-(n-)/;

    FOR(i,,n+-k) ans=min(ans,a[i+k-]-a[i]);

    printf("%d\n",ans);

    return ;

}

B.Max and Bike(二分)

二分时间t，然后用控制精度check就行了。关键是这题的单调性不明显。

另外用fabs控制精度不行，浮点数误差。。。以后就控制二分次数吧。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int n;

double s, f, r, v;

bool check(double t)

{

    double S=v*t, l=*pi*r;

    double ss=S-floor(S/l)*l;

    double T=S+fabs(sin(ss//r))**r;

    return T>=f-s;

}

int main ()

{

    scanf("%d%lf%lf",&n,&r,&v);

    while (n--) {

        scanf("%lf%lf",&s,&f);

        double l=, r=1e12;

        int tot=;

        while (tot--) {

            double mid=(l+r)/;

            if (check(mid)) r=mid;

            else l=mid;

        }

        printf("%.7lf\n",l);

    }

    return ;

}

C.Edo and Magnets(贪心)

求平面n个点至多减少k个点后，用一个矩形覆盖它们，求这个矩形面积的最小值。(k<=10)

显然把边界的点先减掉最好，于是我们枚举四个边界上的点减少多少个后更新答案就ok了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct node{int x, y;}p[N];

bool cmp1(int a,int b){return p[a].x<p[b].x;}

bool cmp2(int a,int b){return p[a].x>p[b].x;}

bool cmp3(int a,int b){return p[a].y<p[b].y;}

bool cmp4(int a,int b){return p[a].y>p[b].y;}

int pos1[N], pos2[N], pos3[N], pos4[N], last[N];

int main()

{

    int n, k;

    scanf("%d%d",&n,&k);

    FO(i,,n) {

        int x1,y1,x2,y2;

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        p[i].x=(x1+x2); p[i].y=(y1+y2);

        pos1[i]=pos2[i]=pos3[i]=pos4[i]=i;

    }

    sort(pos1,pos1+n,cmp1); sort(pos2,pos2+n,cmp2);

    sort(pos3,pos3+n,cmp3); sort(pos4,pos4+n,cmp4);

    int now=;

    LL ans = 1LL<<;

    FOR(a,,k) FOR(b,,k) FOR(c,,k) FOR(d,,k) {

        now++;

        int cnt = ;

        FO(i,,a) if(last[pos1[i]]!=now) last[pos1[i]]=now,cnt++;

        FO(i,,b) if(last[pos2[i]]!=now) last[pos2[i]]=now,cnt++;

        FO(i,,c) if(last[pos3[i]]!=now) last[pos3[i]]=now,cnt++;

        FO(i,,d) if(last[pos4[i]]!=now) last[pos4[i]]=now,cnt++;

        if(cnt!=k) continue;

        LL Maxx=-1LL<<,Maxy=-1LL<<,Minx=1LL<<,Miny=1LL<<;

        FO(i,,n) {

            if(last[i]!=now) {

                Maxx=max(Maxx,p[i].x*1LL);

                Minx=min(Minx,p[i].x*1LL);

                Maxy=max(Maxy,p[i].y*1LL);

                Miny=min(Miny,p[i].y*1LL);

            }

        }

        LL x=Maxx-Minx, y=Maxy-Miny;

        x=max(x,2LL); y=max(y,2LL);

        ans=min(ans,x*y);

    }

    printf("%lld\n",ans/);

}

D.REQ(BIT+积性函数+逆元)

询问区间积[l,r]的欧拉函数。n,q<=2e5,ai<=1e6

因为欧拉函数是积性函数，我们化解一下式子，把不同的素因子拿出来维护一下就行了。
离散化后用树状数组离线处理区间[l,r]内的不同质因子，类似于HH的项链。
之后求答案的时候用逆元搞搞就行了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

typedef struct{int l, r, id;}Node;

Node qq[N];

int a[N], pri[N*], n;

LL sum[N], isum[N], mul[N], imul[N], tree[N], res[N];

queue<int> to[N];

map<int, int> vis;

VI vc[N];

void get_prim()

{

    FOR(i,,) {

        if (!pri[i]) pri[++pri[]]=i, vis[i]=pri[];

        for (int j=; j<=pri[]&&pri[j]<=/i; ++j) {

            pri[pri[j]*i]=;

            if (i%pri[j]==) break;

        }

    }

}

bool comp(Node a, Node b){return a.l<b.l;}

LL inv(LL a, LL m){

    if (a==) return ;

    return inv(m%a,m)*(m-m/a)%m;

}

void add(int x, LL val)

{

    while (x<=n) tree[x]=tree[x]*val%MOD, x+=lowbit(x);

}

LL query(int x)

{

    LL ans=;

    while (x) ans=ans*tree[x]%MOD, x-=lowbit(x);

    return ans;

}

int main ()

{

    get_prim();

    FO(i,,pri[]) mul[i]=(LL)(pri[i]-)*inv(pri[i],MOD)%MOD, imul[i]=(LL)pri[i]*inv(pri[i]-,MOD)%MOD;

    int q;

    n=Scan();

    FOR(i,,n) tree[i]=;

    sum[]=isum[]=;

    FOR(i,,n) {

        a[i]=Scan(), sum[i]=sum[i-]*a[i]%MOD, isum[i]=isum[i-]*inv(a[i],MOD)%MOD;

        int temp=a[i];

        for (int j=; pri[j]*pri[j]<=temp; ++j) {

            if (temp%pri[j]==) {

                to[j].push(i), vc[i].pb(j), temp/=pri[j];

                while (temp%pri[j]==) temp/=pri[j];

            }

        }

        if (temp>) to[vis[temp]].push(i), vc[i].pb(vis[temp]);

    }

    q=Scan();

    FOR(i,,q) qq[i].l=Scan(), qq[i].r=Scan(), qq[i].id=i;

    sort(qq+,qq+q+,comp);

    FO(i,,pri[]) if (!to[i].empty()) add(to[i].front(),mul[i]);

    int now=;

    FOR(i,,q) {

        while (now<qq[i].l) {

            int size=vc[now].size();

            for (int j=; j<size; ++j) {

                int k=vc[now][j];

                add(to[k].front(),imul[k]), to[k].pop();

                if (!to[k].empty()) add(to[k].front(),mul[k]);

            }

            now++;

        }

        res[qq[i].id]=sum[qq[i].r]*isum[qq[i].l-]%MOD*query(qq[i].r)%MOD;

    }

    FOR(i,,q) printf("%lld\n",res[i]);

    return ;

}

E.Cutting the Line(待填坑)

上一篇：Hyperledger Fabric Endorsement policies——背书策略


下一篇：深入浅出mongoose