Preface

这几天里打的最好的一场了，虽然后面写I唐的不行浪费了好多时间

但好在最后都改出来了并且最后Rush出了L题，4h57min绝杀，9题收场

只能说恰好在祁神缺席的这场没有几何，没有被腐乳

而且这场打完发现只有韩文题解没有英文题解，这下直接不用补题了爽歪歪

A. Autonomous Vehicle

大力模拟题，但被徐神1h斩于马下

由于数据范围不大，直接干就完事，但要注意可能会多次走回起点因此需要对循环走的部分取个模

#include <bits/stdc++.h>

struct Line {
    int bx, by, ex, ey;
    std::vector<std::pair<int, int> > crs;
};

std::vector<Line> lines;

bool crs(const Line &a, const Line &b) {
    int abx = std::min(a.bx, a.ex), aex = std::max(a.bx, a.ex);
    int aby = std::min(a.by, a.ey), aey = std::max(a.by, a.ey);

    int bbx = std::min(b.bx, b.ex), bex = std::max(b.bx, b.ex);
    int bby = std::min(b.by, b.ey), bey = std::max(b.by, b.ey);
    return
        abx == aex && bbx < abx && aex < bex && aby < bby && bey < aey ||
        aby == aey && bby < aby && aey < bey && abx < bbx && bex < aex;
}

int main(void) {
    std::ios::sync_with_stdio(false);
    int n, t;
    std::cin >> n >> t;
    lines.resize(n);
    for(auto &[bx, by, ex, ey, crs]: lines)
        std::cin >> bx >> by >> ex >> ey;
    
    for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) {
        Line &a = lines[i], &b = lines[j];
        if(a.bx == a.ex && b.bx == b.ex) continue;
        if(a.by == a.ey && b.by == b.ey) continue;
        if(!crs(a, b)) continue;
        if(a.bx == a.ex) a.crs.push_back({b.by, j});
        else             a.crs.push_back({b.bx, j});
    }

    for(int i = 0; i < n; ++i) std::sort(lines[i].crs.begin(), lines[i].crs.end());

    int vx, vy, sta = 0, cx = lines[0].bx, cy = lines[0].by;
    if(lines[0].bx == lines[0].ex) vx = 0, vy = (lines[0].by < lines[0].ey ? 1 : -1);
    else                           vy = 0, vx = (lines[0].bx < lines[0].ex ? 1 : -1);

    int T = t, ch = 0;

    int *vc, *cc, be, ed;
    for(;;) {
        if(sta == 0 && cx == lines[0].bx && cy == lines[0].by) {
            ch += 1;
            if(ch == 2) t %= T - t;
        }
        // std::cerr << "current: " << cx << ' ' << cy << ' ' << vx << ' ' << vy << ' ' << t << char(10);
        auto [bx, by, ex, ey, crs] = lines[sta];
        if(vx) vc = &vx, cc = &cx, be = std::min(bx, ex), ed = std::max(bx, ex);
        else   vc = &vy, cc = &cy, be = std::min(by, ey), ed = std::max(by, ey);
        if(*vc > 0) {
            int l = 0, r = crs.size(), mid;
            while(l < r) {
                mid = (l + r) >> 1;
                if(crs[mid].first > *cc) r = mid;
                else                     l = mid + 1;
            }
            if(l == crs.size()) {
                int ts = ed - *cc;
                if(t > ts) {
                    *cc += ts;
                    t -= ts;
                    *vc = -*vc;
                } else {
                    *cc += t;
                    break;
                }
            } else {
                int ts = crs[l].first - *cc;
                if(t > ts) {
                    *cc += ts;
                    t -= ts;
                    int temp = vx;
                    vx = -vy;
                    vy = temp;
                    sta = crs[l].second;
                } else {
                    *cc += t;
                    break;
                }
            }
        } else {
            int l = -1, r = crs.size() -1, mid;
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                if(crs[mid].first < *cc) l = mid;
                else                     r = mid - 1;
            }
            if(l == -1) {
                int ts = *cc - be;
                if(t > ts) {
                    *cc -= ts;
                    t -= ts;
                    *vc = -*vc;
                } else {
                    *cc -= t;
                    break;
                }
            } else {
                int ts = *cc - crs[l].first;
                if(t > ts) {
                    *cc -= ts;
                    t -= ts;
                    int temp = vx;
                    vx = -vy;
                    vy = temp;
                    sta = crs[l].second;
                } else {
                    *cc -= t;
                    break;
                }
            }
        }
    }
    std::cout << cx << ' ' << cy << std::endl;
    return 0;
}

B. Commemorative Dice

签到，直接枚举即可

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int a[10],b[10],wins;
int main()
{
    RI i,j; for (i=1;i<=6;++i) scanf("%d",&a[i]);
    for (i=1;i<=6;++i) scanf("%d",&b[i]);
    for (i=1;i<=6;++i) for (j=1;j<=6;++j)
    if (a[i]>b[j]) ++wins; int g=__gcd(wins,36);
    return printf("%d/%d",wins/g,36/g),0;
}

C. Dessert Café

不难发现边权是没有意义的，最后good的点一定在所有关键点之间的路径上

而维护这些路径可以类似于虚树，每次拿出两个关键点然后把它们之间的路径标记，并且将LCA也标为关键点

但由于这题只要统计一次所以可以直接暴力往上跳，同时标记经过的点，最后复杂度还是对的

注意特判\(k=1\)的情形

#include <bits/stdc++.h>

constexpr int $n = 100000 + 10;

std::vector<int> out[$n];

int dep[$n], isRed[$n], fa[$n];

std::priority_queue<std::pair<int, int> > pq;

void dfs(int now) {
    dep[now] = dep[fa[now]] + 1;
    for(auto ch: out[now]) if(ch != fa[now]) fa[ch] = now, dfs(ch);
}

int main() {
    std::ios::sync_with_stdio(false);
    int n, k;
    std::cin >> n >> k;
    for(int i = 1, f, t, v; i < n; ++i) {
        std::cin >> f >> t >> v;
        out[f].push_back(t);
        out[t].push_back(f);
    }
    dfs(1);
    for(int i = 1, a; i <= k; ++i) {
        std::cin >> a;
        pq.push({dep[a], a});
    }
    while(pq.size() > 1) {
        auto[curDep, cur] = pq.top(); pq.pop();
        if(isRed[cur]) continue;
        isRed[cur] = 1;
        if(cur != 1) pq.push({dep[fa[cur]], fa[cur]});
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans += isRed[i];
    std::cout << ans + (k == 1) << std::endl;
    return 0;
}

D. Electric Vehicle

不可做题，弃疗

E. Imprecise Computer

Easy题，不难发现对于某个\(i\)，只有它和\(i-1,i+1\)的比赛状况是不确定的

而我们从\(1\)的情况开始，就可以顺推出所有数的胜负情况，最后检验下\(n\)的情况是否合法即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,a[N],b[N],d[N];
int main()
{
    RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&d[i]);
    bool flag=1; for (i=1;i<n&&flag;++i)
    {
        bool sign=0;
        for (RI p=0;p<2&&!sign;++p) for (RI q=0;q<2&&!sign;++q)
        if (abs((a[i]+p)-(b[i]+q))==d[i]) sign=1,a[i+1]=p,b[i+1]=q;
        if (!sign) flag=0;
    }
    if (abs(a[n]-b[n])!=d[n]) flag=0;
    return puts(flag?"YES":"NO"),0;
}

F. Ink Mix

题目都没看，弃疗

G. Mobile Robot

被徐神一眼秒了

不妨设一号点最后的位置为\(x\)，则答案为\(\max |x-[a_i+d\times (i-1)]|\)

不妨令\(b_i=a_i+d\times (i-1)\)，那么最优的\(x\)一定取在\(\{b_i\}\)两个极值的中点处

但这题还有个坑点就是最后的顺序除了\(1\sim n\)，还可以是\(n\sim 1\)，因此需要把所有坐标取反再跑一次

#include <bits/stdc++.h>
#define Tp template <typename T>
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
        }
}F;

int64_t solve(std::vector<int64_t> a, int64_t d) {
    for(int i = 0; i < a.size(); ++i) a[i] -= int64_t(i) * d;
    std::sort(a.begin(), a.end());
    return a.back() - a[0];
}
int main(void) {
    int64_t n, d; F.read(n); F.read(d);
    std::vector<int64_t> a(n);
    for(int i = 0; i < n; ++i) F.read(a[i]);
    int64_t ans = solve(a, d);
    for(int i = 0; i < n; ++i) a[i] = -a[i];
    ans = std::min(ans, solve(a, d));
    std::cout << (ans >> 1ll);
    std::cout << ((ans & 1ll) ? ".5" : ".0");
    std::cout << std::endl;
    return 0;
}

H. Needle

这题题意我没看，徐神告诉我就是给三个数组\(\{a_i\},\{b_i\},\{c_i\}\)，然后求满足\(a_i+c_k=2\times b_j\)的三元组\((i,j,k)\)个数

做法也很简单，注意到数的值域很小，因此直接把每个数有多少个记下来，大力FFT对\(\{a_i\},\{c_i\}\)卷积即可

#include<cstdio>
#include<iostream>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
typedef long double LDB;
const int N=1<<20;
namespace Poly
{
    const LDB PI=acosl(-1);
    struct Complex
    {
        LDB x,y;
        inline Complex (const LDB& X=0,const LDB& Y=0)
        {
            x=X; y=Y;
        }
        inline Complex conj(void)
        {
            return Complex(x,-y);
        }
        friend inline Complex operator + (const Complex& A,const Complex& B)
        {
            return Complex(A.x+B.x,A.y+B.y);
        }
        friend inline Complex operator - (const Complex& A,const Complex& B)
        {
            return Complex(A.x-B.x,A.y-B.y);
        }
        friend inline Complex operator * (const Complex& A,const Complex& B)
        {
            return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
        }
    }; int lim,p,rev[N];
    inline void init(CI n)
    {
        for (lim=1,p=0;lim<=n;lim<<=1,++p);
        for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
    }
    inline void FFT(Complex *f,CI opt)
    {
        RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
        for (i=1;i<lim;i<<=1)
        {
            Complex D(cosl(PI/i),opt*sinl(PI/i));
            for (j=0;j<lim;j+=(i<<1))
            {
                Complex W(1,0);
                for (k=0;k<i;++k,W=W*D)
                {
                    Complex x=f[j+k],y=W*f[i+j+k];
                    f[j+k]=x+y; f[i+j+k]=x-y;
                }
            }
        }
        if (!~opt)
        {
            for (i=0;i<lim;++i) f[i].x/=lim,f[i].y/=lim;
        }
    }
}
using namespace Poly;
const int S=30000;
int la,lb,lc,x,B[N]; long long ans; Complex A[N],C[N];
int main()
{
    RI i; for (scanf("%d",&la),i=1;i<=la;++i)
    scanf("%d",&x),A[x+S].x+=1;
    for (scanf("%d",&lb),i=1;i<=lb;++i)
    scanf("%d",&x),++B[2*(x+S)];
    for (scanf("%d",&lc),i=1;i<=lc;++i)
    scanf("%d",&x),C[x+S].x+=1;
    for (init(60001*2),FFT(A,1),FFT(C,1),i=0;i<lim;++i) A[i]=A[i]*C[i];
    for (FFT(A,-1),i=0;i<=4*S;++i) ans+=(long long)(A[i].x+0.5)*B[i];
    return printf("%lld",ans),0;
}

I. Stock Analysis

很有趣味的一个题，又卡时间又卡空间，最后被徐神的智慧之作线段树套分块给干过去了

首先注意到\(n\)的范围很小，因此不妨先大力找出所有的区间，求出其贡献后记为三元组\((l,r,val)\)

同时对于某个询问也记作三元组\((S,E,U)\)，然后将所有三元组一起按第三维从小到大排序，并依次处理

这样的好处就是保证了对于某个询问，我们查询出的结果一定满足其贡献\(\le U\)

因此这题只需要维护一个支持单点赋值，矩形求\(\max\)的数据结构即可，一眼可以二维线段树

好家伙但写完发现刚好爆空间，同时这题由于是求\(\max\)也不好用树状数组来解决

危难之际徐神提出不妨将内层的数据结构改成分块，对应的就是一维的单点赋值和区间求\(\max\)，这样可以把空间变成原来的\(\frac{1}{4}\)

同时我在写的时候还发现这种写法还完美的利用了分块\(O(1)\)修改\(O(\sqrt n)\)查询的性质，因为这题修改次数远多于询问次数，因此恰好取得了复杂度的完美平衡

最终也是极限的1248ms卡过

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=2005,S=50;
const LL INF=1e18;
struct ifo
{
    int x,y,id; LL val;
    friend inline bool operator < (const ifo& A,const ifo& B)
    {
        return A.val!=B.val?A.val<B.val:A.id<B.id;
    }
}o[4200005]; int n,m,a[N],cnt,blk[N]; LL pfx[N],ans[200005];
class Segment_Tree_X
{
    private:
        struct BLOCKS
        {
            LL val[N],tag[S];
            inline void updata(CI pos,const LL& mv)
            {
                val[pos]=mv; tag[blk[pos]]=max(tag[blk[pos]],mv);
            }
            inline LL query(CI l,CI r,LL ret=-INF)
            {
                if (blk[l]==blk[r])
                {
                    for (RI i=l;i<=r;++i) ret=max(ret,val[i]); return ret;
                }
                RI i; for (i=l;i<=blk[l]*S;++i) ret=max(ret,val[i]);
                for (i=(blk[r]-1)*S+1;i<=r;++i) ret=max(ret,val[i]);
                for (i=blk[l]+1;i<blk[r];++i) ret=max(ret,tag[i]);
                return ret;
            }
        }T[N<<2];
    public:
        #define TN CI now=1,CI l=1,CI r=n
        #define LS now<<1,l,mid
        #define RS now<<1|1,mid+1,r
        inline void init(CI n)
        {
            RI i,j; for (i=1;i<=n;++i) blk[i]=(i-1)/S+1;
            for (i=0;i<=(n<<2);++i)
            {
                for (j=1;j<=blk[n];++j) T[i].tag[j]=-INF;
                for (j=1;j<=n;++j) T[i].val[j]=-INF;
            }
        }
        inline void updata(CI x,CI y,const LL& mv,TN)
        {
            T[now].updata(y,mv); if (l==r) return; int mid=l+r>>1;
            if (x<=mid) updata(x,y,mv,LS); else updata(x,y,mv,RS);
        }
        inline LL query(CI beg,CI end,TN)
        {
            if (beg<=l&&r<=end) return T[now].query(beg,end); int mid=l+r>>1; LL ret=-INF;
            if (beg<=mid) ret=max(ret,query(beg,end,LS)); if (end>mid) ret=max(ret,query(beg,end,RS)); return ret;
        }
        #undef TN
        #undef LS
        #undef RS
}SEG;
int main()
{
    RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
    scanf("%d",&a[i]),pfx[i]=pfx[i-1]+a[i];
    for (i=1;i<=m;++i)
    scanf("%d%d%lld",&o[i].x,&o[i].y,&o[i].val),o[i].id=i;
    for (cnt=m,i=1;i<=n;++i) for (j=i;j<=n;++j)
    o[++cnt]=(ifo){i,j,-1,pfx[j]-pfx[i-1]};
    sort(o+1,o+cnt+1); SEG.init(n);
    for (i=1;i<=cnt;++i)
    if (o[i].id==-1) SEG.updata(o[i].x,o[i].y,o[i].val);
    else ans[o[i].id]=SEG.query(o[i].x,o[i].y);
    for (i=1;i<=m;++i) if (ans[i]==-INF) puts("NONE"); else printf("%lld\n",ans[i]);
    return 0;
}

J. Switches

经典没看题就被徐神秒了

好像就是对原01矩阵求个逆就完事，可以直接上bitset高斯消元会好写很多

#include <bits/stdc++.h>

std::bitset<1000> a[500];

int main() {
    int n; std::cin >> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0, t; j < n; ++j)
            std::cin >> t, a[i][j] = t;
        a[i][i + n] = 1;
    }
    for(int i = 0; i < n; ++i) {
        int t;
        for(t = i; t < n; ++t) if(a[t][i]) break;
        if(t == n) return std::cout << "-1\n", 0;
        std::swap(a[i], a[t]);
        for(int j = i + 1; j < n; ++j) if(a[j][i]) a[j] ^= a[i];
    }
    for(int i = n - 1; i >= 0; --i)
        for(int j = i - 1; j >= 0; --j)
            if(a[j][i]) a[j] ^= a[i];
    for(int i = 0; i < n; ++i) {
        std::vector<int> ans;
        for(int j = n; j < 2 * n; ++j) if(a[i][j]) ans.push_back(j - n + 1);
        for(size_t j = 0; j < ans.size(); ++j)
            std::cout << ans[j] << char(j == ans.size() - 1 ? 10 : 32);
    }
    return 0;
}

K. Tiling Polyomino

做不来捏

L. Two Buildings

最刺激的一集，灵光一现证出决策单调性然后手速Rush完最后卡点通过

首先常规的做法都不好处理，我们考虑分治求解，考虑怎么快速计算跨过中点的区间的贡献

有个trivial的想法就是从中点向两端维护单调栈，保证从\(l\sim mid\)中选出的元素单调递增，从\(mid+1\sim r\)中选出的元素单调递减，显然答案只能在这些元素间产生

但只是这样的话还是不好处理，后面一直隐隐觉得在求出的两个数组中会不会有决策单调性，后面发现果然可以证明

（PS：这题的证明比较巧妙，但由于篇幅原因不便说明，如关心证明方法者可以私聊我）

而决策单调性的题目一旦证出来后就很套路了，这题的话直接上整体二分即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,a[N],ans;
#define Tp template <typename T>
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        Tp inline void read(T& x)
        {
            x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
        }
}F;
inline void devide(vector <int>& L,CI l,CI r,vector <int>& R,CI ll,CI rr)
{
    if (l>r) return; int mid=l+r>>1,mx=0,pos=0;
    for (RI i=ll;i<=rr;++i)
    {
        int tmp=(a[L[mid]]+a[R[i]])*(R[i]-L[mid]);
        if (tmp>mx) mx=tmp,pos=i;
    }
    ans=max(ans,mx); devide(L,l,mid-1,R,ll,pos); devide(L,mid+1,r,R,pos,rr);
}
inline void solve(CI l,CI r)
{
    if (l>=r) return; int mid=l+r>>1;
    solve(l,mid); solve(mid+1,r);
    vector <int> L,R; RI i;
    for (i=mid;i>=l;--i)
    {
        while (!L.empty()&&a[i]>=a[L.back()]) L.pop_back();
        L.push_back(i);
    }
    for (i=mid+1;i<=r;++i)
    {
        while (!R.empty()&&a[i]>=a[R.back()]) R.pop_back();
        R.push_back(i);
    }
    reverse(L.begin(),L.end());
    devide(L,0,L.size()-1,R,0,R.size()-1);
}
signed main()
{
    RI i; for (F.read(n),i=1;i<=n;++i) F.read(a[i]);
    return solve(1,n),printf("%lld",ans),0;
}

PS：写完后看同校其它队伍的代码才发现其实不需要分治套整体二分的，先求出两个方向的单调栈后直接上整体二分就行