2023湖南省赛游记/题解

省赛拖了大哥们的后腿，感觉随便补个正常一队水平的人，我们一队肯定能AK。只能说自己真的菜，全程帮不上什么忙，还负贡献，真的想笑

B
暴力sg

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr int N=1e6;
int sg[N+5];
int vis[N+5];
void getsg(){for (int i=1;i<=N;i++){// vis[sg[i-1]]=i;int res=sqrt(1.0*i);if (i==res*res){for (int k=1;k<=res;k++){vis[sg[i-(i-res*res+k*res)]]=i;}}else{for (int k=0;k<=res;k++){vis[sg[i-(i-res*res+k*res)]]=i;}}while (vis[sg[i]]==i){sg[i]++;}}
}
void yrzr(){getsg();int n;std::cin>>n;int sum=0;for (int i=1;i<=n;i++){int x;std::cin>>x;sum^=sg[x];}if (sum){std::cout<<"First\n";}else{std::cout<<"Second\n";}
}

D
大哥赛后说是HN省选dp原题（见状压dp P3188 [HNOI2007] 梦幻岛宝珠），然后这个题比那个题范围还要大，看完题解发现是贪心题，但是还是按位分组的思想去解决问题
首先对于一个目标物品来说，它的需求可以表示为几个二进制位的组合，然后我们分解每一个目标物品到位上，然后将其按位合并，最后可以表示为一个二进制串（用数组表示）
然后对于每一件物品，重量小的物品可以合并成大物品，但大物品不能拆解成小物品，所以我们按位从小到大枚举目标物品数组，贪心地用小物品去满足当前位的数量，然后将剩下的物品贪心地两两合并成下一位的物品。

简要的说就是：目标物品总体可以表示为一个数组，然后拥有的物品贪心从小到大去填补目标重量

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr int inf=1e9;
std::priority_queue<int,std::vector<int>,std::greater<int>> q[5105];
void yrzr(){int n;std::cin>>n;for (int i=1;i<=n;i++){int x,y;std::cin>>x>>y;q[x].push(y);}int m;std::cin>>m;std::vector<int> sum(5105);while (m--){int t,h;std::cin>>t>>h;while (h){if (h&1) sum[t]++;h>>=1;t++;}}for (int i=0;i<=5100;i++){if (sum[i]>=2){int temp=sum[i],p=i;sum[i]=0;while (temp){if (temp&1) sum[p]++;temp>>=1;p++;}}}int ans=0;for (int i=0;i<=5100;i++){if (q[i].size()<sum[i]){std::cout<<"-1\n";return;}for (int j=1;j<=sum[i];j++){ans+=q[i].top();q[i].pop();}while (q[i].size()>=2){int temp=q[i].top();q[i].pop();temp+=q[i].top();q[i].pop();q[i+1].push(temp);}}std::cout<<ans;
}

F
图论题，首先Floyed求出一个字母变成另一个字母的最小花费，然后对于两个不同的字母，暴力预处理出他们变成同样字母的最小花费。最后A串不动，枚举B串位置，求最小即可

可能有重边，输入时$dis$取最小

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
constexpr int inf=1e16;
void yrzr(){int n,m;std::cin>>n>>m;std::vector<int> a(n),b(n);for (int i=0;i<n;i++){std::cin>>a[i];}for (int i=0;i<n;i++){std::cin>>b[i];}std::vector<std::vector<int>> dis(405,std::vector<int>(405,inf)),c(405,std::vector<int>(405,inf));for (int i=1;i<=m;i++){int x,y,z;std::cin>>x>>y>>z;dis[x][y]=std::min(dis[x][y],z);}for (int i=1;i<=400;i++){dis[i][i]=c[i][i]=0;}for (int k=1;k<=400;k++){for (int i=1;i<=400;i++){for (int j=1;j<=400;j++){dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);}}}for (int i=1;i<=400;i++){for (int j=1;j<=400;j++){for (int k=1;k<=400;k++){c[i][j]=std::min(c[i][j],dis[i][k]+dis[j][k]);}}}int ans=inf;for (int i=0;i<n;i++){int sum=0;bool ok=1;for (int j=0;j<n;j++){if (c[a[j]][b[(j+i)%n]]==inf){ok=0;break;}else{sum+=c[a[j]][b[(j+i)%n]];}}if (ok){ans=std::min(ans,sum);}}if (ans==inf){std::cout<<"-1\n";}else{std::cout<<ans<<"\n";}
}

I
数位dp，不知道省赛脑子犯了什么抽，受前几天一道数位dp，直接把状态数组压入map暴力记忆化的影响，想当然的觉得这题也是这么做，大哥直接提出时间复杂度是不够的。后面大哥们说是数位dp加个容斥。

补题的时候也一直在想数位dp+容斥，发现自己容斥不出来（容斥见识的得太少了），看了题解后发现只要一个数位dp就可以了

突然发现这题的思想其实跟前几天做的数位dp是一样的，甚至状态更简单，我们最重要的状态其实就只有当前位第几位，然后还要知道现在有多少个不同的数，这就足够了。因为对于这10个数字来说，后面的数字它只有两种身份，之前选了/没选，所以当前位相同，之前不同的数字个数相同，剩下的方案数就相同，就可以用记忆化。（赛时真的蠢傻了，这种套路思想学数位dp的时候见过很多了）

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr ll mod=1e9+7;
ll f[200005][12][2][2];
int now[12];
void yrzr(){int n;std::cin>>n;std::vector<int> a(n+1),b(n+1);for (int i=1;i<=n;i++){char ch;std::cin>>ch;a[i]=ch-'0';}for (int i=1;i<=n;i++){char ch;std::cin>>ch;b[i]=ch-'0';}reverse(a.begin()+1,a.end());reverse(b.begin()+1,b.end());int A;std::cin>>A;std::function<ll(int,int,int,int)> dfs=[&](int len,int sum,int dif1,int dif2){if (len==0){return 1LL*(sum==A);}if (sum>A){return 0LL;}if (dif1&&dif2&&f[len][sum][dif1][dif2]){return f[len][sum][dif1][dif2];}int x=(dif1?0:a[len]),y=(dif2?9:b[len]);ll res=0;for (int i=x;i<=y;i++){if (now[i]){now[i]++;res=(res+dfs(len-1,sum,dif1|(a[len]!=i),dif2|(b[len]!=i)))%mod;now[i]--;}else{now[i]++;res=(res+dfs(len-1,sum+1,dif1|(a[len]!=i),dif2|(b[len]!=i)))%mod;now[i]--;}}if (dif1&&dif2) f[len][sum][dif1][dif2]=res;return res;};std::cout<<dfs(n,0,0,0);}

J
分别枚举圆心在三个坐标轴，然后二分圆的半径，接下来考虑怎么check，对于一个点来说，我们去计算出它在球内时，圆心所在的区间,存下区间左右端点和权值（表示是左端点还是右端点），遍历一遍看是否有点满足题意即可

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr int N=1e5+5;
int n;
ll x[N],y[N],z[N];
struct node{double pos;int val;
}a[N<<1];
bool check(double r){int cnt=0;for (int i=1;i<=n;i++){double res=r*r-y[i]*y[i]-z[i]*z[i];if (res<0) continue;res=sqrt(res);a[++cnt]={x[i]-res,1};a[++cnt]={x[i]+res,-1};}std::sort(a+1,a+1+cnt,[&](node i,node j){return i.pos<j.pos;});int sum=0;for (int i=1;i<=cnt;i++){sum+=a[i].val;if (sum>=n/2){return 1;}}cnt=0;for (int i=1;i<=n;i++){double res=r*r-x[i]*x[i]-z[i]*z[i];if (res<0) continue;res=sqrt(res);a[++cnt]={y[i]-res,1};a[++cnt]={y[i]+res,-1};}std::sort(a+1,a+1+cnt,[&](node i,node j){return i.pos<j.pos;});sum=0;for (int i=1;i<=cnt;i++){sum+=a[i].val;if (sum>=n/2){return 1;}}cnt=0;for (int i=1;i<=n;i++){double res=r*r-x[i]*x[i]-y[i]*y[i];if (res<0) continue;res=sqrt(res);a[++cnt]={z[i]-res,1};a[++cnt]={z[i]+res,-1};}std::sort(a+1,a+1+cnt,[&](node i,node j){return i.pos<j.pos;});sum=0;for (int i=1;i<=cnt;i++){sum+=a[i].val;if (sum>=n/2){return 1;}}return 0;
}
void yrzr(){std::cin>>n;for (int i=1;i<=n;i++){std::cin>>x[i]>>y[i]>>z[i];}double l=0,r=1e6;for (int i=0;i<=50;i++){double mid=(l+r)/2;if (check(mid)){r=mid;}else{l=mid;}}std::cout<<std::fixed<<std::setprecision(7)<<l;
}

K
补的时候相成状压了，然后状压+矩阵加速？？？，发现不会写
然后看了题解知道是容斥了，所以以后对于这种小数据除了状压也有可能是容斥

想到容斥就很好做了，每次直接暴力二进制枚举哪些城市不去，在转移的矩阵和答案矩阵上去掉那些转移点，然后dp矩阵加速即可

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
constexpr ll mod=1e9+9;
constexpr int N=25;
struct Matrix{int lenn,lenm;ll a[N][N];Matrix() {memset(a,0,sizeof(a));}Matrix operator*(const Matrix &b)const{if (lenm==b.lenn){Matrix res;res.lenn=lenn;res.lenm=b.lenm;for (int i=1;i<=lenn;i++){for (int j=1;j<=b.lenm;j++){for (int l=1;l<=lenm;l++){res.a[i][j]=(res.a[i][j]+a[i][l]*b.a[l][j]%mod)%mod;}}}return res;}}Matrix operator+(const Matrix &b)const{if (lenn==b.lenn&&lenm==b.lenm){Matrix res;res.lenn=lenn;res.lenm=lenm;for (int i=1;i<=lenn;i++){for (int j=1;j<=lenm;j++){res.a[i][j]=a[i][j]+b.a[i][j];}}return res;}}Matrix operator-(const Matrix &b)const{if (lenn==b.lenn&&lenm==b.lenm){Matrix res;res.lenn=lenn;res.lenm=lenm;for (int i=1;i<=lenn;i++){for (int j=1;j<=lenm;j++){res.a[i][j]=a[i][j]-b.a[i][j];}}return res;}}};
int s[10],n,m,k,d;
int a[25][25];
ll solve(int mask){Matrix e,f,ans;ans.lenn=1;ans.lenm=f.lenn=f.lenm=e.lenn=e.lenm=n;std::vector<int> vis(n+1);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){e.a[i][j]=a[i][j];}f.a[i][i]=1;ans.a[1][i]=1;}for (int i=1;i<=k;i++){if (mask&(1<<(i-1))){int x=s[i];for (int j=1;j<=n;j++){e.a[x][j]=e.a[j][x]=0;}vis[x]=1;ans.a[1][x]=0;}}int temp=d;while (temp){if (temp&1) f=f*e;e=e*e;temp>>=1;}ans=ans*f;ll sum=0;for (int i=1;i<=n;i++){if (vis[i]) continue;sum=(sum+ans.a[1][i])%mod;}return sum;
}
void yrzr(){std::cin>>n>>m>>k>>d;d--;for (int i=1;i<=k;i++){std::cin>>s[i];}for (int i=1;i<=m;i++){int x,y;std::cin>>x>>y;a[x][y]=a[y][x]=1;}ll ans=0;for (int i=0;i<(1<<k);i++){if (__builtin_popcount(i)&1){ans=(ans-solve(i)+mod)%mod;}else{ans=(ans+solve(i))%mod;}}std::cout<<ans;
}