Preface

新年第一训，直接被干出shi来

开局经典梦游2h2题不知道在干啥，后面抄个网络流板子也能抄错卡个半天

后面2h祁神来救场几何，结果因为一个特判地方没加绝对值WA到结束都没看出来

鉴定为全队太久没摸键盘导致的，寒假有时间得再多练练的说

A. Attendance

开场就开到的不可做题

B. Ball Passing

不难发现男女生独立，因此只要求给一个凸包上的点配对得到的最大贡献

手玩一下会发现我们把凸包上的点按极角序排好后，每个点和其对面的点配对一定是最优的

证明的话就考虑如果有两条配对的线不相交那么交换一下让它们相交一定是最优的，而上面的配对方法可以保证任意两条配对线均相交

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
struct Point
{
    int x,y;
    inline Point(CI X=0,CI Y=0) { x=X; y=Y; }
    int quad(void)
    {
        if (x>0&&y>=0) return 1; if (x<=0&&y>0) return 2;
        if (x<0&&y<=0) return 3; if (x>=0&&y<0) return 4;
        return 0;
    }
    inline int Cross(const Point& ots)
    {
        return x*ots.y-y*ots.x;
    }
    friend inline bool operator < (Point A,Point B)
    {
        if (A.quad()!=B.quad()) return A.quad()<B.quad();
        return A.Cross(B)<0;
    }
};
inline double dist(const Point& A,const Point& B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int n,x,y; char s[N]; vector <Point> P[2];
inline double solve(vector <Point> pnt)
{
    if (pnt.empty()) return 0; Point s=pnt[0];
    for (auto [x,y]:pnt) if (x<s.x||(x==s.x&&y<s.y)) s=Point(x,y);
    for (auto& [x,y]:pnt) x-=s.x,y-=s.y;
    sort(pnt.begin(),pnt.end());
    int m=pnt.size()/2; double ret=0;
    for (RI i=0;i+m<pnt.size();++i) ret+=dist(pnt[i],pnt[i+m]);
    return ret;
}
int main()
{
    RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
    scanf("%d%d",&x,&y),P[s[i]=='B'].push_back(Point(x,y));
    return printf("%.9lf",solve(P[0])+solve(P[1])),0;
}

C. Cakes

小清新网络流，感觉是最经典的那种模型了

首先不难发现由于原料不能重复利用，我们可以直接从蛋糕的收益中扣除成本以得到净收益\(c'_i\)

考虑用最小割模型处理，从源点向每个蛋糕连容量为\(c'_i\)的边，每个工具向汇点连容量为\(t_j\)的边，然后每个蛋糕向其需要的工具连容量为\(\infty\)的边

用\(\sum c'_i\)减去最小割就是最大利润了，意义也很明显，割源点出去的边就是放弃做这个蛋糕，割到汇点的边就是买工具

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=405,INF=1e18;
int G,C,T,c[N],g[N],tc[N],x,y,sum;
namespace NetWork_Flow
{
    const int MM=1e6+5;
    struct edge
    {
        int to,nxt,v;
    }e[MM<<1]; int cnt=1,head[N],cur[N],dep[N],s,t; queue <int> q;
    inline void addedge(CI x,CI y,CI z)
    {
        //printf("%lld -> %lld (%lld)\n",x,y,z);
        e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
        e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
    }
    #define to e[i].to
    inline bool BFS(void)
    {
        memset(dep,0,(t+1)*sizeof(int)); dep[s]=1; q=queue <int>(); q.push(s);
        while (!q.empty())
        {
            int now=q.front(); q.pop();
            for (RI i=head[now];i;i=e[i].nxt)
            if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
        }
        return dep[t];
    }
    inline int DFS(CI now,CI tar,int dis)
    {
        if (now==tar) return dis; int ret=0;
        for (RI& i=cur[now];i&&dis;i=e[i].nxt)
        if (e[i].v&&dep[to]==dep[now]+1)
        {
            int dist=DFS(to,tar,min(dis,e[i].v));
            if (!dist) dep[to]=INF;
            dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
            if (!dis) return ret;
        }
        if (!ret) dep[now]=0; return ret;
    }
    #undef to
    inline int Dinic(int ret=0)
    {
        while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
    }
};
using namespace NetWork_Flow;
signed main()
{
    RI i,j; scanf("%lld%lld%lld",&G,&C,&T);
    for (i=1;i<=C;++i) scanf("%lld",&c[i]);
    for (i=1;i<=G;++i) scanf("%lld",&g[i]);
    for (i=1;i<=T;++i) scanf("%lld",&tc[i]);
    for (i=1;i<=C;++i) for (j=1;j<=G;++j) scanf("%lld",&x),c[i]-=x*g[j];
    for (s=C+T+1,t=s+1,i=1;i<=C;++i) if (c[i]>0) addedge(s,i,c[i]),sum+=c[i];
    for (i=1;i<=T;++i) addedge(C+i,t,tc[i]);
    for (i=1;i<=C;++i) for (scanf("%lld",&x),j=1;j<=x;++j)
    scanf("%lld",&y),addedge(i,C+y,INF);
    return printf("%lld",sum-Dinic()),0;
}

D. Drying Laundry

徐神秒了此题，我只是代为爬上去实现了一下

考虑从另一个方向来考虑问题，当\(t\)确定时，怎样计算所需的最小长度\(l\)

不难发现可以把衣物分成两类，对于\(t^{slow}\le t\)的衣物可以考虑把它们尽可能平均的分成两份，而剩下的就只能占用两根来放，并且还要满足其中最大的\(t^{fast}\le t\)

因此不难得到以下做法，先将所有衣物按照\(t^{slow}\)从小到大排序，然后从前往后把衣物取出扔进一个集合中

现在难点在于动态维护集合中尽可能平均分配，这个直接上bitset优化背包即可

值得一提的是在找最优的值的时候直接写了个暴力跳也能跑过，由于std::bitset不支持诸如找从高位/低位开始的第一个\(0/1\)之类的操作，如果出题人有意卡的话可能要手写bitset了

最后由于\((t,l)\)是单调变化的，询问的话在维护出的信息上二分一下即可

#include<cstdio>
#include<iostream>
#include<bitset>
#include<algorithm>
#include<map>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
struct ifo
{
    int d,s,f;
    friend inline bool operator < (const ifo& A,const ifo& B)
    {
        return A.s<B.s;
    }
}a[N]; int n,q,x,suf[N],sum[N],tot,t[N],l[N],cnt; map <int,int> rst; bitset <N> f;
inline void Upt(CI x,CI y)
{
    //cout<<'('<<x<<' '<<y<<')'<<endl;
    if (!rst.count(x)) rst[x]=y; else rst[x]=min(rst[x],y);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    RI i; for (cin>>n>>q,i=1;i<=n;++i) cin>>a[i].d>>a[i].f>>a[i].s;
    for (sort(a+1,a+n+1),i=n;i>=1;--i)
    suf[i]=max(suf[i+1],a[i].f),sum[i]=sum[i+1]+a[i].d;
    Upt(suf[1],sum[1]); f.set(0);
    for (i=1;i<=n;++i)
    {
        tot+=a[i].d; f|=(f<<a[i].d);
        int st=(tot+1)/2; while (!f.test(st)) ++st;
        Upt(max(suf[i+1],a[i].s),st+sum[i+1]);
    }
    for (auto [_t,_l]:rst) ++cnt,t[cnt]=_t,l[cnt]=_l;
    //for (i=1;i<=cnt;++i) cout<<t[i]<<' '<<l[i]<<endl;
    for (i=1;i<=q;++i)
    {
        cin>>x; int L=1,R=cnt,mid,ret=-1;
        while (L<=R) if (l[mid=L+R>>1]<=x) ret=t[mid],R=mid-1; else L=mid+1;
        cout<<ret<<endl;
    }
    return 0;
}

E. Equal Schedules

徐神开场写的一个签，我题目都没看

#include <bits/stdc++.h>

int main(void) {
    std::string line;
    int b, e;
    std::string name;
    std::map<std::string, int> c;
    for(;;) {
        std::getline(std::cin, line);
        if(line == "------") break;
        std::stringstream ss;
        ss << line;
        ss >> b >> e >> name;
        c[name] -= e - b;
    }
    for(;;) {
        std::getline(std::cin, line);
        if(line == "======") break;
        std::stringstream ss;
        ss << line;
        ss >> b >> e >> name;
        c[name] += e - b;
    }
    bool f = false;
    for(auto [name, delta]: c) {
        if(delta) f = true;
        if(delta > 0)
            std::cout << name << " +" << delta << char(10);
        if(delta< 0)
            std::cout << name << " " << delta << char(10);
    }
    if(!f) std::cout << "No differences found.\n";
    return 0;
}

F. Phylogenetics

貌似是本场最难的一题，现在CF上还没有一个人过

G. Going to the Moon

本来完全被徐神和祁神秒了的题，但因为一个求点到直线距离的时候叉积没加绝对值WA飞了

首先考虑特判掉答案直接就是\(AB\)连线的情况，比如\(A,B\)其中一个点在圆内或者两点连线和圆有交（这部分容易写错）

否则当两点都在圆外时，不难发现其实就是求以\(A,B\)为焦点的椭圆与圆相切的切点\(P\)

根据椭圆的光学性质，可以得到这个切点\(P\)和圆心的连线\(CP\)是\(\angle APB\)的角平分线

因此接下来有两种思路，一种是直接在\(AB\)上三分，代价函数就是\(AP+BP\)的值

另一种就是我们队比赛时候写的，设\(CP\)与\(AB\)交于\(D\)，根据角平分线的性质\(\frac{AP}{AD}=\frac{BP}{BD}\)，可知随着\(D\)在\(AB\)上的移动，\(\frac{AP\times BD}{AD\times BP}\)的值是单调的

这里扔的代码是二分的写法

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LD long double
const LD eps = 1e-11L;

int sgn(LD x){return (fabs(x)<=eps ? 0 : (x>eps ? 1 : -1));}
struct Pt{ 
    LD x, y;
    Pt operator*(LD b)const{return Pt{x*b, y*b};}
    Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
    Pt operator+(Pt b)const{return Pt{x+b.x, y+b.y};}
    LD crs(Pt b)const{return x*b.y-y*b.x;}
    LD dot(Pt b)const{return x*b.x+y*b.y;}
    LD len()const{return sqrtl(x*x+y*y);}
};
LD cross(Pt p, Pt a, Pt b){return (a-p).crs(b-p);}

int t;
LD d_l(Pt p, Pt a, Pt b){
    return fabs(cross(a, b, p))/(a-b).len();
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(10);
    cin >> t;
    while (t--){
        Pt A, B, C;
        int R;
        cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> R;

        if (sgn(A.x-B.x)==0 && sgn(A.y-B.y)==0){
            if (sgn((C-A).len()-R)<=0) cout << 0.0L << '\n';
            else cout << 2*((A-C).len()-R) << '\n';
            continue;
        }
        
        if (0==R){
            cout << (A-C).len()+(B-C).len() << '\n';
            continue;
        }
        // continue;
        // printf("AC=%Lf BC=%Lf\n", (A-C).len(), (B-C).len());
        if (sgn((A-C).len()-R)<=0 || sgn((B-C).len()-R)<=0){
            // printf("fuck\n");
            cout << (A-B).len() << '\n'; 
            continue;
        }

        if (sgn(d_l(C, A, B)-R)<=0){
            if (sgn((B-A).dot(C-A))>=0 && sgn((A-B).dot(C-B))>=0){
                cout << (A-B).len() << '\n'; continue;
            }
        }

        LD LL=0.0L, RR=1.0L;
        while (RR-LL>eps){
            // printf("LL=%.10Lf RR=%.10Lf RR-LL=%.10Lf\n", LL, RR, RR-LL);
            LD M = (LL+RR)*0.5L;
            Pt E = A + (B-A)*M;
            Pt D = C + (E-C)*(R/(C-E).len());
            if (sgn((D-A).len()*(B-E).len() - (D-B).len()*(A-E).len()) >= 0) LL=M;
            else RR=M;
        }
        Pt E = A + (B-A)*LL;
        Pt D = C + (E-C)*(R/(C-E).len());
        LD ans = (D-A).len() + (D-B).len();
        cout << ans << '\n';
    }
    return 0;
}

H. Human Resources

很有意思的通信题，虽然做法不难但颇有趣味

不难发现问题的本质就是给一棵树进行编码，由于这里的树不一定是二叉树，因此不能用前/中/后序的方法

但考虑到怎么利用多余的那个\(01\)串，很容易想到用括号序列

即我们先求出树的DFS序，然后将其输出，同时再输出一串长为\(2n\)的\(0/1\)串表示DFS过程中的行为，\(0\)表示回溯，\(1\)表示向下

手玩一下会发现这样就可以实现加密解密了，同时字符数也符合要求

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=605;
string Type,Name[N],bits; map <string,int> rst; vector <int> v[N],order; int idx,hasfa[N],fa[N];
inline int getID(const string& name)
{
    if (rst.count(name)) return rst[name];
    return rst[name]=++idx;
}
inline void DFS(CI now)
{
    order.push_back(now); for (auto to:v[now]) bits+="1",DFS(to),bits+="0";
}
int main()
{
    RI i; getline(cin,Type);
    if (Type=="ENCODE")
    {
        string s; while (getline(cin,s))
        {
            int pos; string boss; vector <int> space;
            for (i=0;i<s.size();++i)
            {
                if (s[i]==':') boss=s.substr(0,i);
                if (s[i]==' ') space.push_back(i);
            }
            //cout<<"boss="<<boss<<endl; 
            int now=getID(boss);
            for (i=0;i<space.size();++i)
            {
                string employ=s.substr(space[i]+1,(i+1<space.size()?space[i+1]:s.size())-space[i]-1);
                //cout<<"employ="<<employ<<endl;
                int nxt=getID(employ); v[now].push_back(nxt); hasfa[nxt]=1;
            }
        }
        for (auto [name,id]:rst) Name[id]=name;
        int rt; for (i=1;i<=idx;++i) if (!hasfa[i]) { rt=i; break; }
        DFS(rt); for (auto x:order) cout<<Name[x]<<endl;
        cout<<bits<<endl;
    } else
    {
        string s; int n=0;
        while (cin>>s)
        {
            if (s[0]=='0'||s[0]=='1') break;
            Name[++n]=s;
        }
        int cur=1,now=1; for (i=0;i<s.size();++i)
        if (s[i]=='1') ++cur,v[now].push_back(cur),fa[cur]=now,now=cur; else now=fa[now];
        for (i=1;i<=n;++i) if (!v[i].empty())
        {
            cout<<Name[i]<<":";
            for (auto j:v[i]) cout<<" "<<Name[j];
            cout<<endl;
        }
    }
    return 0;
}

I. Interactive Reconstruction

ORZ徐神秒了此题

首先有个很trivial的思路就是先问一遍\(111\cdots 111\)，得到每个点的度数

然后对于度数为\(1\)的点（即为叶子节点），对它们进行询问以找出对应的父亲节点，然后将这些叶子删除再逐步处理

很显然这样会有一个问题就是询问次数爆炸，但徐神提出可以用经典的二进制分组来优化

即我们枚举二进制下每一位\(j\)，当某个点的编号在第\(j\)位上为\(1\)时就将其置为\(1\)，以此来对得到一些信息

手玩一下可以发现不论是找父亲还是删除节点都可以利用这些来完成，具体实现看代码

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    int n; std::cin >> n;
    std::vector<std::vector<int> > v(16, std::vector<int>(n + 1));
    std::cout << "QUERY ";
    for(int i = 1; i <= n; ++i) std::cout << 1;
    std::cout << std::endl;
    for(int i = 1; i <= n; ++i) std::cin >> v[0][i];
    for(int t = 0; t < 15; ++t) {
        std::cout << "QUERY ";
        for(int i = 1; i <= n; ++i) std::cout << (i >> t & 1);
        std::cout << std::endl;
        for(int i = 1; i <= n; ++i) std::cin >> v[t + 1][i];
    }
    std::queue<int> q;
    for(int i = 1; i <= n; ++i) if(v[0][i] == 1) q.push(i);
    int T = n - 1;
    std::cout << "ANSWER" << std::endl;
    while(T--) {
        int lf = q.front(); q.pop();
        int pa = 0;
        for(int i = 1; i <= 15; ++i) if(v[i][lf]) pa |= 1 << (i - 1);
        std::cout << lf << ' ' << pa << char(10);
        for(int i = 0; i < 16; ++i) v[i][lf] = 0;
        for(int i = 0; i < 16; ++i) if(i == 0 || (lf >> (i - 1) & 1)) {
            v[i][pa] -= 1;
            if(i == 0 && v[i][pa] == 1) q.push(pa);
        }
    }
    std::cout << std::flush;
    return 0;
}