2020第十一场暑期集训题解

• Marvolo • 0条评论 •

比赛地址

Codeforces Gym

[A] Bit String Reordering

题意&题解

签到题

代码

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

int a[20], s[20], b[20], c[20], A[20], B[20], C[20];
int tota, totb, totc;

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &s[i]);
    int k, tot;
    k = 0, tot = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= s[i]; j++) b[++tot] = k;
        k ^= 1;
    }
    k = 1, tot = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= s[i]; j++) c[++tot] = k;
        k ^= 1;
    }
    for (int i = 1; i <= n; i++) if (a[i]) A[++tota] = i;
    for (int i = 1; i <= n; i++) if (b[i]) B[++totb] = i;
    for (int i = 1; i <= n; i++) if (c[i]) C[++totc] = i;
    int ans = 999;
    if (tota == totb) {
        int now = 0;
        for (int i = 1; i <= tota; i++) now += abs(A[i]-B[i]);
        ans = min(ans, now);
    }
    if (tota == totc) {
        int now = 0;
        for (int i = 1; i <= tota; i++) now += abs(A[i]-C[i]);
        ans = min(ans, now);
    }
    cout << ans << endl;
}

[B] Miscalculation

题意&题解

签到题

代码

class LR:
    def __init__(self, v=0):
        self.v = v
    def __sub__(self, a):
        return LR(self.v*a.v)
    def __add__(self, a):
        return LR(self.v+a.v)

s = input()
tar = int(input())
val1 = eval(s)
ss = ''.join(list(map(
    lambda ch: f'LR({ch})' if ch not in "+*" else ch,
    list(s))))
ss = ss.replace('*', '-')
val2 = eval(ss).v

if val1 == tar and val2 == tar:
    print('U')
elif val1 != tar and val2 != tar:
    print('I')
elif val2 == tar:
    print('L')
else:
    print('M')

[C] Shopping

题意&题解

签到题

代码

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

struct point {
    int x, y;
}s[505];

int fa[505];
int find(int a) {
    if (fa[a] == a) return a;
    return fa[a] = find(fa[a]);
}

int main() {
    int n, m; cin >> n >> m;
    int ans = n + 1;
    for (int i = 1; i <= 500; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &s[i].x, &s[i].y);
        for (int j = 1; j < i; j++) {
            if (s[i].y > s[j].x && s[j].y > s[i].x) {
                int a = find(i), b = find(j);
                if (fa[a] != b) fa[a] = b;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int up = 0, down = 999999;
        for (int j = 1; j <= m; j++) if (find(j) == i) {
            up = max(up, s[j].y);
            down = min(down, s[j].x);
        }
        if (up) ans += 2*(up - down);
    }
    cout << ans << endl;
}

[D] Space Golf

题意

给出一个网球场,要从起点打出一颗网球,在地面上弹起不超过d次的情况下,落到终点.起点和终点之间有很多厚度为0,高度为h_{i}的障碍,问若使网球在不碰到障碍的前提下到达终点,最小的发射速度是多少.

理想物理模型,完全弹性碰撞,轨迹一定为抛物线.

题解

枚举弹起次数,则小球的落点一定.如果两个落点间有障碍,则计算下小球擦着障碍过去的最小速度.最后的答案一定是这些速度的最大值.同时,还有种情况要考虑,有一个物理结论是,从一点到另一点的最小抛物速度在发射角度为45度时取到,所以这些速度还要和45度的速度比较下.最后注意下精度就行了.

代码

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std; 
double eps = 1e-7;
double p[100], h[100];

bool equal(double a, double b) {
    if (a < b+eps && b < a+eps) return true;
    return false;
}

double fmax(double a, double b) {
    if (a < b) return b; return a;
}

double fmin(double a, double b) {
    if (a < b) return a; return b;
}

double speed(double d, double a, double b) {
    double k = b/(a-d)/a;
    double h = -1*k*d*d/4;
    if (h < d/4-eps) return 0;
    double t = sqrt(2*h);
    double vy = t;
    double vx = d/t/2;
    return sqrt(vx*vx+vy*vy);
    //else return 0;
}

int main() {
    int n, b; double s;
    cin >> s >> n >> b;
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i], &h[i]);
    double anss = 999999999;
    for (int i = 0; i <= b; i++) {
        double now = 0, d = s/(i+1);
        double ans = speed(d, d/2, d/4);
        for (int j = 0; j < i+1; j++) {
            double x = d*j; double y = x + d;
            for (int k = 1; k <= n; k++) {
                if (equal(p[k], x)||equal(p[k], y)) { ans = -1; break; }
                if (p[k] > x && p[k] < y) ans = fmax(ans, speed(d, p[k]-x, h[k]));
            }
            if (equal(ans, -1)) break;
        }
        if (equal(ans, -1)) continue;
        else anss = fmin(ans, anss);
    }
    printf("%.10lf\n", anss);
}

[F] There is No Alternative

题意

给出一个图,问哪些边一定在最小生成树里.

题解

随便构建一个最小生成树,然后枚举不在树上的边.每条边一定连接了树上的两个顶点,用这条边的边权去覆盖树上的这条链,维护一下每条边被覆盖的所有边权的最小值.如果最小值等于边权,则这条边可以被覆盖,否则不能.可以在树剖后用线段树维护下最值.

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <limits>

using std::vector;
using std::sort;

#define FED(src) for(Ed *p=head[src]; p; p=p->next)

#define OPER1(T,x1,b1) inline bool operator<(const T&_o)const{return x1 b1 _o.x1;}
#define OPER2(T,x1,b1,x2,b2) inline bool operator<(const T&_o)const{return x1 b1 _o.x1||x1==_o.x1&&x2 b2 _o.x2;}

#define IL inline

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

constexpr int MV(2e5+7), ME(MV<<1);

using dint = int;
constexpr dint SINT_MAX = std::numeric_limits<dint>::max(), SINT_MIN = std::numeric_limits<dint>::min();

int uf[MV];
int find(const int x)
{
    return uf[x] ? uf[x]=find(uf[x]) : x;
}
bool merge(int x, int y)
{
    if ((x=find(x)) == (y=find(y)))
        return false;
    return uf[x] = y, true;
}



struct Ed
{
    Ed *next;
    int u, v, son;
    dint d;
} *head[MV], ed[ME];
int tot;
#define edd(uu, vv, dd) ed[++tot].next=head[uu], ed[tot].u=uu, ed[tot].v=vv, ed[tot].d=dd, head[uu]=ed+tot
struct OEd
{
    int u, v, id;
    dint d;
    bool picked;
    OPER1(OEd, d, <)
};
vector<OEd> edges;


void kruskal()
{
    sort(edges.begin(), edges.end());
    for (auto &e : edges)
        if (merge(e.u, e.v))
            e.picked = true, edd(e.u, e.v, e.d), edd(e.v, e.u, e.d);
}


template <typename vint, typename xint = int>
class STree
{
private:

    static constexpr xint ROOT = 1;
    struct Node
    {
        xint l, r;
        vint min, lzm;
    } t[MV << 2];

    vint *a, vv;
    xint ll, rr, pos;

#define glr xint li=i<<1, ri=i<<1|1
#define t_mid ((t[i].l+t[i].r)>>1)

#define ini_v(i, v) \
    ({ \
        t[i].min = SINT_MAX; \
    })
#define set_min_v(i, m) \
    ({ \
        t[i].min = MIN(t[i].min, m); \
        t[i].lzm = MIN(t[i].lzm, m); \
    })
#define pu(i) \
    ({ \
        t[i].min = MIN(t[li].min, t[ri].min); \
    })
#define pd(i) \
    ({ \
        if (t[i].lzm != SINT_MAX) \
        { \
            set_min_v(li, t[i].lzm); \
            set_min_v(ri, t[i].lzm); \
            t[i].lzm = SINT_MAX; \
        } \
    })

    void build(const xint i, const xint l, const xint r)
    {
        t[i].l = l, t[i].r = r, t[i].lzm = SINT_MAX;
        if (l == r)
            ini_v(i, a[r]);
        else
        {
            glr;
            build(li, l, t_mid);
            build(ri, t_mid+1, r);
            pu(i);
        }
    }

    void set_min(const xint i)
    {
        if (ll <= t[i].l && t[i].r <= rr)
            set_min_v(i, vv);
        else
        {
            glr;
            pd(i);
            if (ll <= t_mid)
                set_min(li);
            if (rr > t_mid)
                set_min(ri);
            pu(i);
        }
    }
    vint _min(const xint i)
    {
        if (t[i].l == t[i].r)
            return t[i].min;
        else
        {
            glr;
            pd(i);
            if (pos <= t_mid)
                return _min(li);
            else
                return _min(ri);
        }
    }

public:
    void build(vint *arr, const xint l, const xint r) {a = arr, build(ROOT, l, r);}
    void set_min(const xint l, const xint r, const vint v) {ll = l, rr = r, vv = v,set_min(ROOT);}
    vint min(const xint p) {pos=p; return _min(ROOT);}
};



namespace HLD
{
STree<dint> st;


dint a0[MV];
int de[MV], fa[MV], sz[MV], son[MV];
void dfs1(const int u, const int f)
{
    de[u] = de[fa[u]=f] + (sz[u]=1), son[u] = 0;
    FED(u)
    {
        const int v = p->v;
        if (v != f)
        {
            a0[p->son=v] = p->d;
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]])
                son[u] = v;
        }
        else
            p->son = u;
    }
}

dint a1[MV];
int top[MV], id[MV], dnt;
void dfs2(const int u)
{
    top[u] = son[fa[u]]==u ? top[fa[u]] : u;
    a1[id[u]=++dnt] = a0[u];

    if (son[u])
    {
        dfs2(son[u]);
        FED(u)
            if (p->v == p->son && p->v != son[u])
                dfs2(p->v);
    }
}

void decom()
{
    dfs1(1, 0), dfs2(1);
    st.build(a1, 2, dnt);
}

void set_min(int u, int v, const dint d)
{
    while (top[u] != top[v])
    {
        if (de[top[u]] > de[top[v]])
        {
            auto tp = u;
            u = v;
            v = tp;
        }
        st.set_min(id[top[v]], id[v], d);
        v = fa[top[v]];
    }

    if (u == v)
        return;
    if (de[u] > de[v])
    {
        auto tp = u;
        u = v;
        v = tp;
    }
    st.set_min(id[son[u]], id[v], d);
}
dint min(const int u, const int v)
{
    return st.min(id[de[u]>de[v] ? u:v]);
}
}   // namespace HLD



dint ans[MV];
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);

    OEd ee;
    ee.picked = false;
    for (int i=0; i<E; ++i)
    {
        scanf("%d %d %d", &ee.u, &ee.v, &ee.d);
        ee.id = i;
        edges.emplace_back(ee);
    }

    kruskal();
    HLD::decom();

    for (auto &e : edges)
    {
        if (not e.picked)
        {
            HLD::set_min(e.u, e.v, e.d);
        }
    }

    int acnt = 0;
    long long sum = 0;
    for (auto &e : edges)
    {
        if (e.picked)
        {
            dint min_d = HLD::min(e.u, e.v);
            if (min_d > e.d)
                ++acnt, sum += e.d;
        }
    }

    std::cout << acnt << ' ' << sum;

    return 0;
}

[G] Flipping Parentheses

题意

给出一个合法的括号序列,有一些操作,每次操作会对某个位置进行一次修改操作,也就是左括号变右括号,右括号变左括号.问在修改操作后,再进行一次修改的话,将哪里的括号翻转可以使得括号序列重新变得合法.输出最左边的答案.

题解

分两种情况考虑.

左边右:显然,将第一个右括号变成左括号即可.右括号的位置可以用set来维护.

右变左:将括号序列转化为一个1,-1构成的序列,用一棵线段树维护其前缀和.右变左相当于在某个位置后区间+2,接下来要进行区间-2使得最后一个位置的前缀和等于0.为了保证区间-2后的最小值不会小于0,就要找最后一个前缀和为1的位置的后面的那个位置.也就是该位置到最后的区间最小值大于等于2.线段树上二分下即可.

代码

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 300010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,x;
char c[N];
int a[N],s[N];

set <int> S;

struct Tree{
    int l,r,d,p;
}t[N*4];

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

inline void Maketree(int x,int low,int high){
    int mid=(low+high)>>1;
    t[x].l=low; t[x].r=high;
    if (low==high){
        t[x].d=s[low];  return;
    }
    Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
    t[x].d=Min(t[l(x)].d,t[r(x)].d);
    return;
}

inline void Push(int x){
    int p=t[x].p;
    t[l(x)].d+=p;   t[r(x)].d+=p;
    t[l(x)].p+=p;   t[r(x)].p+=p;
    t[x].p=0;
    return;
}

inline void Add(int x,int low,int high,int val){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].l==low&&t[x].r==high){
        t[x].d+=val;    t[x].p+=val;    return;
    }
    if (t[x].p) Push(x);
    if (high<=mid)  Add(l(x),low,high,val);
    else    if (low>mid)    Add(r(x),low,high,val);
    else    Add(l(x),low,mid,val),Add(r(x),mid+1,high,val);
    t[x].d=Min(t[l(x)].d,t[r(x)].d);
}

inline int Query(int x,int low,int high){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].l==low&&t[x].r==high)  return t[x].d;
    if (t[x].p) Push(x);
    if (high<=mid)  return Query(l(x),low,high);
    else if (low>mid)   return Query(r(x),low,high);
    else return Min(Query(l(x),low,mid),Query(r(x),mid+1,high));
}

IL void LR(int x){
    if (x==1){
        puts("1");  return;
    }
    a[x]=2;
    Add(1,x,n,-2);
    S.insert(x);
    auto i=S.begin();
    a[*i]=1;
    printf("%d\n",*i);
    Add(1,*i,n,2);
    S.erase(*i);
}

IL bool Check(int x){
    return Query(1,x,n)>=2;
}

IL void RL(int x){
    reg int low=1,high=n,mid=0,ans=0;
    Add(1,x,n,2);
    a[x]=1;
    S.erase(x);
//  cout<<Query(1,2,6)<<endl;
    while (low<=high){
        mid=(low+high)>>1;
        if (Check(mid)){
            ans=mid;    high=mid-1;
        }
        else low=mid+1;
    }
    printf("%d\n",ans);
    a[ans]=2;
    S.insert(ans);
    Add(1,ans,n,-2);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    scanf("%s",c+1);
    for (i=1;i<=n;i++)  a[i]=c[i]=='('?1:2;
    for (i=1;i<=n;i++)  s[i]=s[i-1]+((a[i]==1)?1:-1);

    for (i=1;i<=n;i++)  
        if (a[i]==2)    S.insert(i);
    Maketree(1,1,n);

    for (i=1;i<=m;i++){
        x=read();
        if (a[x]==1)    LR(x);
        else RL(x);
    }
    return 0;
}

总结

天胡六题开局,卒于一道大模拟.

声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: 2020第十一场暑期集训题解
最小生成树 树链剖分 线段树 计算几何
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...