holiday

解题思路

这一题显然可以直接暴力把每个点走$k$条边以内所能到达的点判断出来，那么暴力的思路在bfs完之后就是从起点开始dfs。

考虑一下优化，显然，我们要从家开始，再从家结束，所以走的这四个景点与家肯定能构成一个环。那么显然，我们找第一二点与找三四点是等效的。所以我们可以以家为起点，将从家开始的向后所有两个点所能构成的路线提前存下来，然后再从这所有的路线中挑出一二和三四即可，关于点与点之间是否联通可以在bfs是就求出来。（考场$75$分）

再优化一下，众所周知，人类的智慧是无穷的。既然是类似搜索了，又是要找最大值，那么我们接下来需要做的就是贪心或者剪枝了。由于我们要找最大值，所以我们可以将上述的从家开始往后的两个点的路线的值降序排序，再走一遍双指针，当遇到可行的方案时，一但找到符合条件的三四点指针就可以进行剪枝，这是显然的。

#include <bits/stdc++.h>

using namespace std;

const int N=2e4+10;
int n,m,k;
int e[N],ne[N],h[N],idx;
bool va[2510][2510];
long long ans;
bool v[N];
long long a[N];
vector<int> ve[2510];
vector<pair<long long,pair<int,int> > > vec; 
void add(int x,int y){
    e[++idx]=y;
    ne[idx]=h[x];
    h[x]=idx;
}

void bfs(){
    queue<int> q,q1;
    for(int i=1;i<=n;i++){
        q.push(i);
    }
    while(q.size()){
        int x=q.front();
//        cout<<x<<'\n';
        q.pop();
        while(q1.size())q1.pop();
        q1.push(x);
        v[x]=1;
        for(int i=0;i<=k;i++){
            int q=q1.size();
            if(q1.empty()) break;
            for(int w=1;w<=q;w++){
                int y=q1.front();
//              cout<<y<<'\n';
                q1.pop();
                for(int j=h[y];j;j=ne[j]){
                    int l=e[j];
                    if(v[l]) continue;
                    v[l]=1;
                    va[x][l]=va[l][x]=1;
                    ve[x].push_back(l);
                    q1.push(l);
                }
            }

        }
        for(int i=1;i<=n;i++){
            v[i]=0;
        }
    }
}

long long query(int s,int e){
    long long res=0;
    for(int i=0;i<ve[s].size();i++){
        int x1=ve[s][i];
        if(x1==e) continue;
        for(int j=0;j<ve[e].size();j++){
            int x2=ve[e][j];
            if(x2==s||x2==x1) continue;
            if(va[x2][x1]) res=max(res,a[x2]+a[x1]);
        }
    }
    return res;
}

int main(){
    // freopen("2.in","r",stdin);
    // freopen("holiday.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    bfs();
    for(int i=0;i<ve[1].size();i++){
        for(int j=0;j<ve[ve[1][i]].size();j++){
            if(ve[ve[1][i]][j]==1) continue;
            vec.push_back({a[ve[1][i]]+a[ve[ve[1][i]][j]],{ve[1][i],ve[ve[1][i]][j]}});
        }
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    // for(int i=0;i<vec.size();i++){
    //     cout<<vec[i].second.first<<' '<<vec[i].second.second<<' '<<vec[i].first<<'\n';
    // }
    for(int i=0;i<vec.size();i++){
        int x=vec[i].second.first,y=vec[i].second.second;
        for(int j=i+1;j<vec.size();j++){
            int q=vec[j].second.first,w=vec[j].second.second;
            if(x==y||x==q||x==w||y==q||y==w||q==w||!va[y][w]) continue;
            else{
                // cout<<vec[i].first<<' '<<vec[i].second.first<<' '<<vec[i].second.second<<'\n';
                // cout<<vec[j].first<<' '<<vec[j].second.first<<' '<<vec[j].second.second<<'\n';
                ans=max(ans,vec[i].first+vec[j].first);
                break;
            }
        }
    }
    cout<<ans<<'\n';
//    for(int i=1;i<=n;i++){
//      for(int j=0;j<ve[i].size();j++){
//          cout<<ve[i][j]<<' ';
//      }
//      cout<<'\n';
//  }
    return 0;
}

game

解题思路

在赛场上第一眼看到这一题的时候还以为是博弈论，看了几眼就看出来这道题只不过是个线段树的板子题（或者说ST表的板子题）。赛场上很不幸打错了一个字母，这会只能看CCF会怎么造数据了。（幸运的是CCF确实是用脚造的数据）

从简单的情况开始思考，假设全部都是正数，首先我们可以发现小A想要让答案的值最大，而小B想让答案的值最小，小A先手。那么当小A选完后，小B肯定会竭尽自己的全力来让答案尽可能的小。例如，小A选了最大的数，那么小B一定会挑选出自己最小的数。

那么如果存在负数呢，情况会变成什么样子？显然，如果小A只有正数，而小B有负数，那么如果小A选了最大的正数，那么小B一定会去选绝对值最大的那一个负数去反制小A，这样的话小A就不是最聪明的了。所以小A会去选最小的正数而小B还是一样。

那么接下来就是类似于上面这些过程的分类讨论了，在考场上的时候由于担心写挂，所以没有简写，直接按照每边正，负，正负的情况分了九种情况去讨论，这里留给读者自己思考。

#include <bits/stdc++.h>
#define pl tr<<1
#define pr tr<<1|1
using namespace std;

const int N=1e5+10;
const int INF=1000000001;
int n,m,q;
long long a[N],b[N];
int l1,r1,l2,r2;
long long ans;


struct Seg{
    struct node{
        int l,r;
        long long maxn1=-INF,maxn2=INF,minn1=INF,minn2=-INF;
    }t[N<<2];
    void pushup1(int tr){
        t[tr].maxn1=max(t[pl].maxn1,t[pr].maxn1);
        t[tr].minn1=min(t[pl].minn1,t[pr].minn1);
    }
    void pushup2(int tr){
        t[tr].maxn2=min(t[pl].maxn2,t[pr].maxn2);
        t[tr].minn2=max(t[pl].minn2,t[pr].minn2);
    }
    void build(int l,int r,int tr,long long a[]){
        t[tr].l=l,t[tr].r=r;
        if(l==r){
            if(a[l]>0) t[tr].maxn1=a[l],t[tr].minn1=a[l];
            else if(a[l]<0)t[tr].maxn2=a[l],t[tr].minn2=a[l];
            else{
                t[tr].maxn1=a[l],t[tr].minn1=a[l];
                t[tr].maxn2=a[l],t[tr].maxn2=a[l];
            }
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,pl,a);
        build(mid+1,r,pr,a);
        pushup1(tr);
        pushup2(tr);
    }
    long long query1(int l,int r,int tr){
        if(l<=t[tr].l&&t[tr].r<=r){
            return t[tr].maxn1;
        }
        // pushdown(tr);
        long long res=-INF;
        int mid=(t[tr].l+t[tr].r)>>1;
        if(l<=mid) res=query1(l,r,pl);
        if(mid<r) res=max(query1(l,r,pr),res);
        return res;
    }
    long long query2(int l,int r,int tr){
        if(l<=t[tr].l&&t[tr].r<=r){
            return t[tr].minn1;
        }
        // pushdown(tr);
        long long res=INF;
        int mid=(t[tr].l+t[tr].r)>>1;
        if(l<=mid) res=query2(l,r,pl);
        if(mid<r) res=min(query2(l,r,pr),res);
        return res;
    }
    long long query3(int l,int r,int tr){
        if(l<=t[tr].l&&t[tr].r<=r){
            return t[tr].maxn2;
        }
        // pushdown(tr);
        long long res=INF;
        int mid=(t[tr].l+t[tr].r)>>1;
        if(l<=mid) res=query3(l,r,pl);
        if(mid<r) res=min(query3(l,r,pr),res);
        return res;
    }
    long long query4(int l,int r,int tr){
        if(l<=t[tr].l&&t[tr].r<=r){
            return t[tr].minn2;
        }
        // pushdown(tr);
        long long res=-INF;
        int mid=(t[tr].l+t[tr].r)>>1;
        if(l<=mid) res=query4(l,r,pl);
        if(mid<r) res=max(query4(l,r,pr),res);
        return res;
    }
}t1,t2;

int main(){
//    freopen("game4.in","r",stdin);
//    freopen("4.out","w",stdout);
//    freopen("game.in","r",stdin);
//    freopen("game.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    t1.build(1,n,1,a);
    t2.build(1,m,1,b);//考场上就是这里把m打成n了
    for(int i=1;i<=q;i++){
        cin>>l1>>r1>>l2>>r2;
        long long res;
        long long maxn1=t1.query1(l1,r1,1),minn1=t1.query2(l1,r1,1);
        long long maxn2=t1.query3(l1,r1,1),minn2=t1.query4(l1,r1,1);
        long long maxn3=t2.query1(l2,r2,1),minn3=t2.query2(l2,r2,1);
        long long maxn4=t2.query3(l2,r2,1),minn4=t2.query4(l2,r2,1); 
        bool f1=(maxn1==-INF),f2=(maxn2==INF);
        bool f3=(maxn3==-INF),f4=(maxn4==INF);
        if(f2&&f4){
            res=maxn1*minn3;
        }
        else if(f2&&f3){
            res=minn1*maxn4;
        }
        else if(f1&&f4){
            res=minn2*maxn3;
        }
        else if(f1&&f3){
            res=maxn2*minn4;
        }
        else if(f2){
            res=minn1*maxn4;
        }
        else if(f4){
            res=maxn1*minn3;
        }
        else if(f1){
            res=minn2*maxn3;
        }
        else if(f3){
            res=maxn2*minn4;
        }
        else{
//            cout<<f1<<' '<<f2<<' '<<f3<<' '<<f4<<'\n';
            res=max(minn2*maxn3,minn1*maxn4);
        }
        cout<<res<<'\n';
    }
    //250 272 508 513
//    l1=250,r1=272,l2=508,r2=513;
//    long long maxn1=t1.query1(l1,r1,1),minn1=t1.query2(l1,r1,1);
//        long long maxn2=t1.query3(l1,r1,1),minn2=t1.query4(l1,r1,1);
//        long long maxn3=t2.query1(l2,r2,1),minn3=t2.query2(l2,r2,1);
//        long long maxn4=t2.query3(l2,r2,1),minn4=t2.query4(l2,r2,1); 
//        bool f1=(maxn1==-INF),f2=(maxn2==INF);
//        bool f3=(maxn3==-INF),f4=(maxn4==INF);
//        cout<<res<<'\n';
//        cout<<f1<<' '<<f2<<' '<<f3<<' '<<f4<<'\n';
    return 0;
}

galaxy

解题思路

这一题的话主要是题目比较长，把题目意思完全理解之后其实就是当且仅当所有点的出度均为$1$时才输出YES，其他情况下都输出NO。

赛场上打了个暴力，爆砍$60$分，可惜如果加一个卡时大样例全部输出NO的话应该能拿到全部的分数（所以说CCF是拿脚再造数据）。注意到我们要判断每个点的出度是否都为$1$，这种判断类似于判断每个数是否均出现$1$次，有一个算法叫做XOR Hashing，大致思路就是将每个数都随机化一个权值，用一个变量来存储当前出现的数的权值的异或和，当该变量的值等于全部数的异或和时，则说明每个数只出现一次，差不多是这个意思，如果我有时间的话再好好的钻一下这个算法吧。

这一题有很多人用了类似于XOR Hashing的算法，只不过处理的不是异或和而是和，类似上面的做法，具体过程与下文中异或哈希差不多。

如果是异或和的话要怎么做呢？首先我们可以观察到一个性质，每个点的出度都为$1$时，图中的边数一定为$n$，那么每个点的度数如果都为奇数的话只有度数为$1$这种唯一的可能性,不存在度数为$3$或者更大的可能性。

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+10;

int n,m,q;
int u,v,x,y;

int ru[N],du[N],sum[N],a[N];
int val[N];
int chu[N];
int cnt;
int rd(){
    return rand()*rand();
}
long long res;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    srand(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=rd();
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        chu[x]++;
        ru[y]++;
        du[y]++;
        sum[y]^=a[x];
        val[y]^=a[x];
        cnt++;
    }
    for(int i=1;i<=n;i++){
        if(!(chu[i]&1)) res^=a[i];
    }
    cin>>q;
    while(q--){
        int op;
        cin>>op>>x;
        if(op==1){
            cin>>y;
            cnt--;
            ru[y]--;
            res^=a[x];
            val[y]^=a[x];
        }
        else if(op==2){
            cnt-=ru[x];
            res^=(val[x]);
            val[x]=0;
            ru[x]=0;
        }
        else if(op==3){
            cin>>y;
            cnt++;
            ru[y]++;
            res^=a[x];
            val[y]^=a[x];
        }
        else{
            cnt+=(du[x]-ru[x]);
            res^=(sum[x]^val[x]);
            val[x]=sum[x];
            ru[x]=du[x];
        }
        if(cnt==n&&!res) cout<<"YES\n";
        else cout<<"NO\n";
    }
}