[数据结构与算法]2020icpc澳门（重温经典）

导语

三道额，以前没怎么用过fft和ntt导致A滑铁卢

涉及的知识点

思维，轻重链dp，位运算，字符串处理，fft/ntt，最小异或树

链接：The 2020 ICPC Asia Macau Regional Contest

题目

D

题目大意：略

思路：纯处理字符串，将字符串中所需要的数据都提取出来然后统一计算即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s[]= {"ATK Rate+","ATK+","Crit DMG Rate+","Crit Rate+"};//作为匹配字符串
double atk[6],Crate[6],Cdrate[6],atkr[6],sum;//分别记录需要的对应数据
double ATK=1500,cr=0.05,cdr=0.5;
double fe(double x,double y,double c,double cd) {//统计最后获得的E
    double a=ATK*(1+x)+y;
    return a*max(1-cr-c,0.0)+a*(1+cd+cdr)*min(cr+c,1.0);
}
signed main() {
    for(int i=1; i<=5; i++) {
        string str;
        for(int k=0; k<5; k++) {
            getline(cin,str);
            for(int j=0; j<4; j++) {
                int pos=str.find(s[j],0),len=s[j].length();
                //判断是否能找到对应的字符串
                if(pos==string ::npos)continue;//找不到就跳过
                if(j==1) {
                    double x=stod(str.substr(len));
                    atk[i]=x;//记录对应的值，也可以累和
                } else {
                    double x=stod(str.substr(len));
                    switch(j) {
                    case 0:
                        atkr[i]=x*0.01;//注意是比率
                        break;
                    case 2:
                        Cdrate[i]=x*0.01;
                        break;
                    case 3:
                        Crate[i]=x*0.01;
                        break;
                    }
                }
            }
        }
    }
    double x=0,y=0,c=0,cd=0;
    for(int i=1; i<=5; i++) {
        x+=atkr[i];
        y+=atk[i];
        c+=Crate[i];
        cd+=Cdrate[i];
    }
    printf("%.10f",fe(x,y,c,cd));
    return 0;
}

F

题目大意：给出三个整数$n,d,c$，需要构造出有$n$个点的图能够被分成$c$个连通块，每个连通块内有只有d条边

思路：分情况考虑，如果$d=0$，则分组数必须与点数相同，如果$d=1$，则代表两两分组，直接判断
当$d>1$时，对于一个连通块来说，至少需要$d+1$个点才能满足条件，那么把点分成多个$d+1$的小组，当然，最后一组可能不足$d+1$，那么 把倒数第二组单独拿出来和最后一组拼出来就行，假设这一部分的点为$p$个，首先这$p$个点首尾相连，然后再对每个点连完剩下的$d?2$条边，需要注意的是，每连一条边的贡献是-2，最后需要判断是否存在点无法连边，如果有则代表无解

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=3e5+5;
set<int> s[N];
queue<int> q;
void graph(int n,int start,int en) {
    int cnt=0;
    int ma=en-start;
    for(int i = start; i <= en; i ++) {
        if(i!=n) {
            cout << i;
            cnt++;
            if(cnt < ma) {
                cout << " ";
            }
        }
    }
    cout << endl;
}
void connect(int a,int b) {
    s[a].insert(b);
    s[b].insert(a);
}
bool graph2(int start,int en,int d) {
    connect(en,start);
    connect(en,en-1);
    connect(start,start+1);
    connect(start,en);
    for(int i = start+1; i <= en-1; i++) {
        connect(i,i+1);
        connect(i,i-1);
    }
    for(int i = start; i <= en; i++) {
        if(s[i].size()<d) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int a,b;
        a=q.front();
        q.pop();
        if(q.empty()) {//如果为空，代表不能构造出来
            return false;
        }
        while(s[a].size()<d) {
            b=q.front();
            q.pop();
            if(s[a].count(b)==0) {
                connect(a,b);
            }
            if(s[b].size()<d) {
                q.push(b);
            }
        }
    }
    return true;
}
void solve() {
    int n,d,c;
    scanf("%d%d%d",&n,&d,&c);
    if(d==0) {//特判d=0，d=0代表每个点都单独分组
        if(c!=n) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    } else if(d==1) {//特判d=1，如果不能两两分组
        if(n&1||c!=n/2) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
            for(int i = 1; i <= n; i++) {
                if(i&1) {
                    cout << i+1 << endl;
                } else {
                    cout << i-1 << endl;
                }
            }
        }
    } else if((d+1)*c>n) {//无法分组
        cout << "No" << endl;
    } else {
        if(!graph2((c-1)*(d+1)+1,n,d)) {//判断是否能够将最后一组单独处理
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
            for(int j = 1; j <= c-1; j++) {//把前c-1组直接构成完全图
                for(int i = j*(d+1)-d; i <= j*(d+1); i++) {
                    graph(i,j*(d+1)-d,j*(d+1));
                }
            }
            set<int>::iterator it;
            for(int i = (c-1)*(d+1)+1; i <= n; i++) {
                it = s[i].begin();
                for(; it!=s[i].end(); it++) {
                    cout << *it << " ";
                }
                cout << endl;
            }
        }
    }
}

int main() {
//	freopen("in.txt","r",stdin);
    int t = 1;
//	scanf("%d",&t);
    while(t--) {
        solve();
    }
    return 0;
}

G

题目大意：给出n个非负整数的序列$A$，遵循下列规则两人博弈：

1. 博弈的每一步是以当前节点移动到下一位置，初始的位置为$k$
2. G为先手，然后两人策略性博弈
3. 每一步移动，假设当前位置为$i$，那么下一步的位置$j$满足$j>i$且$A_j$和$A_i$只有至多一位二进制不同
4. 不能继续移动的人判输

现在给出初始序列$A$，执行$m$次操作，每次操作要么在序列后添加一个值要么询问从给定的位置开始谁赢，输出每次询问的结果

思路：如图，如果存在一个位置$pos$，假设其对应$a_i$值为$x$，其之后不存在后继位置可以到达，那么这个位置必然是先手必败态，即先手从这个位置开始出发一定会败，那么，能够到达这个位置的其余所有位置都是先手必胜态，如图，假设能到达该位置的位置为$k$，如果先手从$k$出发，就可以选择直接到达$pos$，这样后手无路可走，先手必胜态，那么，有哪些位置能够到达$pos$？答案是所有$x$的其他位置以及能够通过变换1位到达值$x$的其余值$y$的位置

因此，可以推得，对于每个值来说，最重要的是其下标最大的那一个位置$p_{max}$，如果$p_{max}$不存在后继可到达的状态，那么一定是先手必败态，那么，如果存在后继可到达的状态呢？

如图，如果存在后继可到达的状态，可到达状态包括先手必败态的话，显然该位置就是先手必胜态，无需讨论，但是，如果后继全是先手必胜态，那么当前状态就是先手必胜态，因为先手从这一状态向后转移，那么此时到达的都是先手必胜态，但是此时作决定的是后手，后手可以直接走到必败态，让先手无路可走

在想清楚状态间关系后，根据先前得到的结论，每次插入一个新值后需要更新状态关系，重要的就是记录每个值的最大下标，然后从下标最大者向前更新，由于值相同的位置可相互抵达，所以可将其视为一个集合，详见代码

代码

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn=4e5+500;
int t,n,m,a[maxn],last[300];
bool dp[300];
bool cmp(const int &a,const int &b) {
    return last[a]>last[b];
}
void Adjust() {
    memset(dp,1,sizeof(dp));//初始都为1，也代表最远下标没有后继
    vector<int>num;
    for(int i=0; i<=255; i++)if(last[i])num.push_back(i);//如果存在最远元素
    sort(num.begin(),num.end(),cmp);//按照最远位置排序，位置最大的在第一个
    for(auto i:num) {
        bool f=0;//判断是否为必败态
        for(int j=0; j<8; j++)
            if(!dp[i^(1<<j)]) {//如果存在一个邻接必败态
                f=1;//标记
                break;
            }
        f?dp[i]=1:dp[i]=0;
        //存在一个邻接必败态，代表当前为必胜态，否则为必败态
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    for(int i=1; i<=n; i++) {
        cin >>a[i];
        last[a[i]]=i;//记录最后出现的位置
    }
    Adjust();//需要预处理一下，防止直接询问
    while(m--) {
        int op,k;
        cin >>op>>k;//录入操作
        if(op==1) {
            a[++n]=k;//记录值
            last[a[n]]=n;//更新最远距离
            Adjust();//调整必胜态和必败态
        } else {
            if(last[a[k]]==k) {
                if(dp[a[k]])cout <<"Grammy\n";
                else cout <<"Alice\n";
            } else
                cout <<"Grammy\n";
        }
    }
    return 0;
}

I

题目大意：题目内存很小，只有8M
两人进行尼姆博弈，有几堆石子，每一堆可能包含多块石子，两人轮流决策性拿，不能拿的就输了，每一次操作选择一堆石子然后拿走正数个，每次都是A先拿
接下来在n天进行n次博弈，初始时没有石子，每一天博弈前，A从下列操作中选择一个执行

1. $ADD$ $a[i]$ $b[i]:$ A在最右边增加一堆石子，数量为$a[i]$，将会花费B$b[i]$的费用移除它
2. $DEL:$ A删去最右的一推

在A操作之后，B可以选择花费费用暂时删除多堆石子（这一次博弈之后会还原）确保B一定会胜利

现在询问每次博弈的最小使得B获胜的最小花费

思路：首先，从A操作的次序可以看出，次序之间存在拓扑关系，更确切的来说是树形关系，那么可以尝试离线处理，先构造出操作间的树形关系，再从上到下处理

首先考虑单个情况，即不考虑修改，尼姆博弈后手赢的条件是石子堆对应个数异或和为0，那么，对于给出的多堆石子，假设异或和为$sum$，那么就需要拿走异或和为$sum$的$p$堆石子，这样$sum$ $xor$ $sum=0$，因此，对于给定的情况，所拿的石子异或和是固定的，那么问题就转换成，如何用最小的花费使得所取元素异或和为$sum$，显然，这是个背包问题了

分析清楚了单个情况后，就需要考虑如何在树形结构上实现它，由于数值很小而且是异或运算，可以进行暴力更新，对于每次遍历到的节点，尝试用其更新所有的元素异或和的最小花费，那么显然每一个节点就需要开一个数组来存储当前节点不同异或和下的最小花费，显然会超空间

对于树形结构，考虑启发式合并的思路，对于整棵树来说，最消耗时间复杂度的是对重子的处理，与其保存所有节点的处理结果，不如只保存重子的处理结果，这样就可以使得重子中的结果不需要重新计算，最大化利用空间

那么，具体做法就出来了：根据给定的操作次序建树，树刨，建树之后根据DFS序离线处理节点的结果，对轻子动态开点存储操作结果，处理完所有轻子之后处理重子，并保留重子结果，以此类推，详见代码

代码

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e4+10;
const int N=16385;
int cur,n,val[maxn],cost[maxn],fa[maxn],cnt,dp[N],res[maxn];
vector<int>tree[maxn];
bool son[maxn];
int DFS(int u) {//树刨
    int acc=1,mx=0,h=-1;
    for(auto i:tree[u]) {
        int large=DFS(i);
        if(large>mx) {
            h=i;
            mx=large;
        }
        acc+=large;'
    }
    if(h>=0)son[h]=1;//标记该点为重子
    return acc;
}
void solve(int u,int sum) {
    int*tmp;
    if(!son[u]) {//不是重子，复制父节点的结果
        tmp=new int[N];
        for(int i=0; i<N; i++)tmp[i]=dp[i];//tmp作为暂时存储没有轻子的结果
    }
    for(int i=0; i<N; i++)
        dp[i^val[u]]=min(dp[i^val[u]],dp[i]+cost[u]);
    //以该点数量更新各异或和下的花费最小值
    res[u]=dp[sum^val[u]];//记录从当前链中去掉与对应链异或和相等的最小花费
    int h=-1;
    for(auto i:tree[u]) {//先处理完轻子
        if(son[i]) {
            h=i;
            continue;
        }
        solve(i,sum^val[u]);
    }
    if(h>=0)solve(h,sum^val[u]);//再处理重子
    if(!son[u]) {
        for(int i=0; i<N; i++)dp[i]=tmp[i];//数值回溯
        delete []tmp;
    }
}
void Print(int u) {
    if(!n)return ;
    if(u) {
        cout <<res[u]<<endl;
        n--;
    }
    for(auto i:tree[u]) {
        if(!n)return ;
        Print(i);
        if(!n)return ;
        cout <<res[u]<<endl;
        n--;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++) {
        string op;
        cin >>op;
        if(op=="ADD") {
            cnt++;
            cin >>val[cnt]>>cost[cnt];//记录数量与费用
            tree[cur].push_back(cnt);//建树
            fa[cnt]=cur;//记录父节点
            cur=cnt;//动态开点
        } else
            cur=fa[cur];//回溯
    }
    memset(dp,inf,sizeof(dp));
    dp[0]=0;//需要初始化，因为目标是0
    DFS(0);//树刨出重子
    solve(0,0);
    Print(0);
    return 0;
}

参考文献

1. The 2020 ICPC Asia Macau Regional Contest G.Game on Sequence 博弈+思维
2. 训练赛-2020icpc澳门
3. The 2020 ICPC Asia Macau Regional Contest I Nim Cheater