模拟赛小结：2019-2020 ICPC, Asia Jakarta Regional Contest

比赛链接：传送门

离金最近的一次？，lh大佬carry场。

Problem A. Copying Homework 00：17（+） Solved by Dancepted

签到，读题有点慢了。而且配置vscode花了点时间。

#include <bits/stdc++.h>

using namespace std;

int a[];

int main() {

    int n;

    cin >> n;

    for (int i = ; i <= n; i++) {

        scanf("%d", &a[i]);

    }

    for (int i = ; i <= n; i++) {

        printf("%d%c", n +  - a[i], " \n"[i==n]);

    }

    return ;

}

Problem C. Even Path 00：44（+） Solved by Dancepted

每个格子通过even path能到达的区域是一个矩形，预处理这个矩形的边界就ok。签到。

“NO”写成了“No”，WA1不算罚时开心死了。

#include <bits/stdc++.h>

#define N 100005

using namespace std;

int R[N], C[N];

int l[N], r[N], u[N], d[N];

int main() {

    int n, q;

    cin >> n >> q;

    for (int i = ; i <= n; i++)

        scanf("%d", &R[i]);

    for (int i = ; i <= n; i++)

        scanf("%d", &C[i]);

    l[] = u[] = ;

    for (int i = ; i <= n; i++) {

        if (R[i]% == R[i-]%)

            u[i] = u[i - ];

        else

            u[i] = i;

        if (C[i]% == C[i-]%)

            l[i] = l[i - ];

        else

            l[i] = i;

    }

    r[n] = d[n] = n;

    for (int i = n - ; i >= ; i--) {

        if (R[i]% == R[i+]%)

            d[i] = d[i + ];

        else

            d[i] = i;

        if (C[i]% == C[i+]%)

            r[i] = r[i + ];

        else

            r[i] = i;

    }

    while (q--) {

        int ra, ca, rb, cb;

        scanf("%d%d%d%d", &ra, &ca, &rb, &cb);

        if (u[ra] <= rb && rb <= d[ra] && l[ca] <= cb && cb <= r[ca])

            puts("YES");

        else

            puts("NO");

    }

    return ;

}

Problem H. Twin Buildings 01：03（-1） Solved by xk

xk说是sb题。。。qwq。

#include<bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < (n); i++)

#define forab(i, a, b) for(int i = (a); i <= (b); i++)

#define forba(i, b, a) for(int i = (b); i >= (a); i--)

#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))

#define mp(x, y) make_pair(x, y)

#define fi first

#define se second

typedef long long ll;

typedef double db;

typedef pair<int, int> pii;

const int maxn = 1e5 + ;

pii a[maxn];

int mxh[maxn];

int main()

{

    int n;

    ios::sync_with_stdio(), cin.tie();

    cin >> n;

    ll ans = ;

    forn(i, n)

    {

        cin >> a[i].fi >> a[i].se;

        if(a[i].fi > a[i].se)

            swap(a[i].fi, a[i].se);

        ans = max(ans, (ll)a[i].fi * a[i].se);

    }

    sort(a, a + n);

    forba(i, n - , )

    {

        mxh[i - ] = max(mxh[i], a[i].se);

        ans = max(ans, (ll)a[i - ].fi * min(a[i - ].se, mxh[i - ]) * );

    }

    cout << ans /  << (ans %  ? ".5" : ".0") << endl;

}

Problem K. Addition Robot 01：28（+） Solved by lh

lh一拍脑袋说这个tm好像可以区间合并，那不是线段树随便搞？于是K就被秒了。

具体地：

若左子树对应区间的A和B是：

$\begin{bmatrix}A_{l}&B_{l}\end{bmatrix} = \begin{bmatrix}A&B\end{bmatrix} * \begin{bmatrix}f_{AtoAl} & f_{AtoBl}\\ f_{BtoAl} & f_{BtoBl}\end{bmatrix}$

而右子树对应区间的A和B是：

$\begin{bmatrix}A_{r}&B_{r}\end{bmatrix} = \begin{bmatrix}A&B\end{bmatrix} * \begin{bmatrix}f_{AtoAr} & f_{AtoBr}\\ f_{BtoAr} & f_{BtoBr}\end{bmatrix}$

则合并后的区间对应的A和B是：

$\begin{bmatrix}A_{o}&B_{o}\end{bmatrix} = \begin{bmatrix}A&B\end{bmatrix} * \begin{bmatrix}f_{AtoAl} & f_{AtoBl}\\ f_{BtoAl} & f_{BtoBl}\end{bmatrix} * \begin{bmatrix}f_{AtoAr} & f_{AtoBr}\\ f_{BtoAr} & f_{BtoBr}\end{bmatrix}$

线段树每个节点维护4个系数。对于交换一个区间内的A和B，就是把系数AtoA和BtoA交换，AtoB和BtoB交换。合并的时候两个子区间的系数矩阵乘一下就行。

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LLINF 0x3f3f3f3f3f3f3f3f

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

#define ffor(i, d, u) for (int i = (d); i <= (u); ++i)

#define _ffor(i, u, d) for (int i = (u); i >= (d); --i)

#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))

#define mp(x, y) make_pair(x, y)

#define fi first

#define se second

#define N 100005

#define M 1000005

typedef long long ll;

typedef double db;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef pair<db, db> pdd;

const db PI = acos(-);

const ll MO = 1e9 + ;

const ll Inv2 = (MO + ) / ;

const bool debug = true;

template <typename T>

inline void read(T &x)

{

    x=;char c;T t=;while(((c=getchar())<''||c>'')&&c!='-');

    if(c=='-'){t=-;c=getchar();}do(x*=)+=(c-'');while((c=getchar())>=''&&c<='');x*=t;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args)

{

    read(x), read(args...);

}

template <typename T>

inline void write(T x)

{

    int len=;char c[];if(x<)putchar('-'),x*=(-);

    do{++len;c[len]=(x%)+'';}while(x/=);_ffor(i,len,)putchar(c[i]);

}

int n, q;

char s[N];

struct node

{

    ll a, b, x, y;

    bool lazy;

    node operator * (const node &other)

    {

        node ans;

        ans.lazy = false;

        ans.a = (a * other.a % MO + x * other.b % MO) % MO;

        ans.b = (b * other.a % MO + y * other.b % MO) % MO;

        ans.x = (a * other.x % MO + x * other.y % MO) % MO;

        ans.y = (b * other.x % MO + y * other.y % MO) % MO;

        return ans;

    }

} t[N << ];

inline void pushup(int o)

{

    int lo = o << , ro = o <<  | ;

    t[o] = t[lo] * t[ro];

}

void build(int o = , int l = , int r = n)

{

    t[o].lazy = false;

    if (l == r)

    {

        if (s[l] == 'A')

            t[o].a = , t[o].b = , t[o].x = , t[o].y = ;

        else

            t[o].a = , t[o].b = , t[o].x = , t[o].y = ;

        return;

    }

    int mid = (l + r) >> ;

    build(o << , l, mid), build(o <<  | , mid + , r);

    pushup(o);

}

inline void modify(int o)

{

    t[o].lazy = !t[o].lazy;

    swap(t[o].a, t[o].b), swap(t[o].x, t[o].y);

    swap(t[o].a, t[o].x), swap(t[o].b, t[o].y);

}

inline void pushdown(int o)

{

    if (t[o].lazy == false)

        return;

    int lo = o << , ro = o <<  | ;

    modify(lo), modify(ro), t[o].lazy = false;

}

void change(int cl, int cr, int o = , int l = , int r = n)

{

    if (cl == l && cr == r)

    {

        modify(o);

        return;

    }

    pushdown(o);

    int mid = (l + r) >> ;

    if (mid >= cr)

        change(cl, cr, o << , l, mid);

    else if (mid < cl)

        change(cl, cr, o <<  | , mid + , r);

    else

        change(cl, mid, o << , l, mid), change(mid + , cr, o <<  | , mid + , r);

    pushup(o);

}

node query(int ql, int qr, int o = , int l = , int r = n)

{

    if (ql == l && qr == r)

        return t[o];

    pushdown(o);

    int mid = (l + r) >> ;

    if (mid >= qr)

        return query(ql, qr, o << , l, mid);

    else if (mid < ql)

        return query(ql, qr, o <<  | , mid + , r);

    else

        return query(ql, mid, o << , l, mid) * query(mid + , qr, o <<  | , mid + , r);

}

inline int ac()

{

    read(n, q);

    scanf("%s", s + );

    build();

    while (q--)

    {

        int op, l, r, a, b;

        read(op, l, r);

        if (op == )

        {

            read(a, b);

            node ans = query(l, r);

            write((a * ans.a % MO + b * ans.b % MO) % MO), putchar(' '), write((a * ans.x % MO + b * ans.y % MO) % MO), putchar('\n');

        }

        else

            change(l, r);

    }

    return ;

}

int main()

{

    ac();

    return ;

}

Problem G. Performance Review 02：44（+） Solved by lh

据说是个线段树之类的题，lh分分钟就秒了，我和xk站在一边人都看傻了。

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

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

#define ffor(i, d, u) for (int i = (d); i <= (u); ++i)

#define _ffor(i, u, d) for (int i = (u); i >= (d); --i)

#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))

#define mp(x, y) make_pair(x, y)

#define fi first

#define se second

#define N 100005

#define M 3000005

typedef long long ll;

typedef double db;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef pair<db, db> pdd;

const db PI = acos(-);

const ll MO = 1e9 + ;

const ll Inv2 = (MO + ) / ;

const bool debug = true;

template <typename T>

inline void read(T &x)

{

    x=;char c;T t=;while(((c=getchar())<''||c>'')&&c!='-');

    if(c=='-'){t=-;c=getchar();}do(x*=)+=(c-'');while((c=getchar())>=''&&c<='');x*=t;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args)

{

    read(x), read(args...);

}

template <typename T>

inline void write(T x)

{

    int len=;char c[];if(x<)putchar('-'),x*=(-);

    do{++len;c[len]=(x%)+'';}while(x/=);_ffor(i,len,)putchar(c[i]);

}

int n, m, q, a = ;

vector<int> b[N];

int minx[N << ], lazy[N << ];

void build(int o = , int l = , int r = m)

{

    minx[o] = a, lazy[o] = ;

    if (l == r)

        return;

    int mid = (l + r) >> ;

    build(o << , l, mid), build(o <<  | , mid + , r);

}

inline void pushdown(int o)

{

    if (lazy[o] == )

        return;

    int lo = o << , ro = o <<  | ;

    minx[lo] += lazy[o], minx[ro] += lazy[o];

    lazy[lo] += lazy[o], lazy[ro] += lazy[o];

    lazy[o] = ;

}

void change(int ql, int qr, int x, int o = , int l = , int r = m)

{

    if (l == ql && r == qr)

    {

        lazy[o] += x, minx[o] += x;

        return;

    }

    pushdown(o);

    int mid = (l + r) >> ;

    if (mid >= qr)

        change(ql, qr, x, o << , l, mid);

    else if (mid < ql)

        change(ql, qr, x, o <<  | , mid + , r);

    else

        change(ql, mid, x, o << , l, mid), change(mid + , qr, x, o <<  | , mid + , r);

    minx[o] = min(minx[o << ], minx[o <<  | ]);

}

inline int ac()

{

    int r, x, y, z;

    read(n, m, q, x);

    ffor(i, , n) read(y), a += (y < x ?  : );

    build(), a = ;

    ffor(i, , m)

    {

        read(r);

        if (a)

            change(i, m, a);

        a = ;

        ffor(j, , r)

        {

            read(y), b[i].emplace_back(y);

            a += (y < x ?  : );

        }

        change(i, m, -r);

    }

    int mu = x;

    while (q--)

    {

        read(x, y, z);

        if ((b[x][y - ] > mu) == (z > mu) || x == m)

        {

            b[x][y - ] = z;

            puts(minx[] >=  ? "" : "");

            continue;

        }

        if (z > mu)

            change(x + , m, -);

        else

            change(x + , m, );

        b[x][y - ] = z;

        puts(minx[] >=  ? "" : "");

    }

    return ;

}

int main()

{

    ac();

    return ;

}

后面我和xk去开了E，我想了个贪心，但是有些细节没理清楚，而xk怎么看怎么像差分约束，对着板子敲了一下，但是后面发现不太会改板子的样子。后面还尝试写F和L。

F我看了一眼割出来的点必须是树的重心，但是不知道怎么判子树同构，瞎猜了一个做法，但是bug有点多没来得及调完。（赛后调完交上去WA17，应该是个假做法，明早补）

L大概是个图论，但是xk最后没来得及写。

总结：

这场其实有点不太认真，因为各种原因过了10分钟左右才开始看题。中间我还接到了移动的电话骗我去改套餐（结果是兼职的同学找人代打电话，细节没交代好，害我白跑一趟），还顺路买了个晚饭。。。

我后面上厕所也上了挺久的，浪费了不少时间。

最后手上还有三道疑似可做的题，时间多一点说不定能再过一题，这周六要认真点打了QAQ。

还有个人感觉xk看E的时候的：“这肯定是个差分约束，但是我不会差分约束”，这种做法不太好，我感觉这样很容易看成假算法。我有一场CF就是死脑筋，那场的D我就说：“这肯定是个马拉车，但是我不会马拉车，我去看一下我的板子”，但是实际上D是个思维题，我还因此掉了不少分。

不过xk和我切水题又快起来了的样子qwq。然后lh一眼一道线段树，分分钟过掉真的nb没话说。

赛后想想，F题的判树的同构的算法是猜出来的，而xk的L应该是证明过的比较严谨，下次碰到的时候应该优先让这种题先敲。

其他的。。。和某位肾结石的好基友讨论了一下，才发现我们俩从初中开始就熬夜成瘾了，身体真的吃不消，以后还是早睡早起吧QWQ。

巴特西

模拟赛小结：2019-2020 ICPC, Asia Jakarta Regional Contest

最新文章

热门文章