24.9.1（康托展开）
上星期三:
补 24牛客多校 二 C 牛客传送门
思路: 赛时写模拟写的很臭,如果用dp写就很方便
代码如下:
const int N=2e6+10;
const int mod=1e9+7;
ll n;
char s[N][2];
int dp[N][2];
void solve(){
cin >> n;
for(int i=1;i<=n;i++) cin >> s[i][0];
for(int i=1;i<=n;i++) cin >> s[i][1];
if(s[1][0]=='R') dp[1][0]=(s[1][0]=='R')+(s[1][1]=='R');
if(s[1][1]=='R') dp[1][1]=(s[1][1]=='R')+(s[1][0]=='R');
int ans=max(dp[1][0],dp[1][1]);
for(int i=2;i<=n;i++){
dp[i][0]=(s[i][0]=='R');
dp[i][1]=(s[i][1]=='R');
ans=max(dp[i][0]+dp[i][1],ans);
if(s[i][0]=='R' && s[i-1][0]=='R')
dp[i][0]=max(dp[i-1][0]+1,dp[i][0]),ans=max(dp[i][0],ans);
if(s[i][1]=='R' && s[i-1][1]=='R')
dp[i][1]=max(dp[i-1][1]+1,dp[i][1]),ans=max(dp[i][1],ans);
int dp0=dp[i][0],dp1=dp[i][1];
// if(s[i][1]=='R' && s[i-1][0]=='R' && s[i][0]=='R')
// dp[i][1]=max(dp0+1,dp[i][1]),ans=max(dp[i][1],ans);
// if(s[i][0]=='R' && s[i-1][1]=='R' && s[i][1]=='R')
// dp[i][0]=max(dp1+1,dp[i][0]),ans=max(dp[i][0],ans); //不该判上一列
if(s[i][0]=='R' && s[i][1]=='R'){
dp[i][0]=max(dp1+1,dp[i][0]);
dp[i][1]=max(dp0+1,dp[i][1]);
ans=max({dp[i][0],dp[i][1],ans});
}
}
if(ans) cout << ans-1 << "\n";
else cout << 0;
}因为上星期的题量太少，没咋写周记，就给并掉了
星期二：
补 24牛客多校二 B 牛客传送门
题意：给一图和q次询问，每次询问给一图内点集，问子图的最小生成树
题解pdf
思路：最小生成树用kk算法处理，如何取边采用根号分治，若 k <= ，双重循环枚举点集，取出存在的边，若 k >
，枚举 m取出有效边
然后跑克鲁斯卡尔。因为 k的sum是有限制的，所以采用对应的枚举方法可有效降低总体复杂度
代码如下：
const int N=2e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
struct edge{
int u,v,w;
bool operator <(const edge &b)const{
return w<b.w;
}
}e[N];
map<PII,int>mp;
int fa[N];
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void solve(){
int m,q; cin >> n >> m >> q;
int sq=sqrt(n);
for(int i=1;i<=m;i++){
int u,v,w; cin >> u >> v >> w;
e[i]={u,v,w};
mp[{u,v}]=w;
mp[{v,u}]=w;
}
sort(e+1,e+m+1);
while(q--){
int k; cin >> k;
vector<int>ve;
vector<edge>ed;
unordered_map<int,bool>vi;
for(int i=1;i<=k;i++){
int s; cin >> s;
ve.push_back(s);
vi[s]=1;
fa[s]=s;
}
if(k<=sq){
for(int i=0;i<k;i++){
for(int j=i+1;j<k;j++) if(mp.count({ve[i],ve[j]}))
ed.push_back({ve[i],ve[j],mp[{ve[i],ve[j]}]});
}
sort(ed.begin(),ed.end());
ll cnt=0,sum=0;
for(auto t:ed){
int u=fnd(t.u),v=fnd(t.v);
if(u==v) continue;
fa[u]=v;
sum+=t.w;
if(++cnt==k-1) break;
}
if(cnt==k-1) cout << sum << "\n";
else cout << "-1\n";
}else{
ll cnt=0,sum=0;
for(int i=1;i<=m;i++) if(vi.count(e[i].u) && vi.count(e[i].v)){
int u=fnd(e[i].u),v=fnd(e[i].v);
if(u==v) continue;
fa[u]=v;
sum+=e[i].w;
if(++cnt==k-1) break;
}
if(cnt==k-1) cout << sum << "\n";
else cout << "-1\n";
}
}
}补 24牛客多校 二 I 牛客传送门
思路：p【num】【0/1】表示数字 num的左右区间下标
dp【num】【i】表示数字为num，考虑到第 i个数的最大贡献（i <= p【num】【1】
处理大区间时，需考虑其间的小区间贡献，将区间按长度从小到大排序，对每个区间进行遍历，若遇到包含在内的小区间，对是否转移取max，O(n^2)的复杂度
代码如下：
const int N=2e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
int a[3030*2],p[3030][2];
int id[3030];
ll dp[3030][3030*2];
void solve(){
cin >> n;
for(int i=0;i<=n;i++) id[i]=i;
a[1]=0,p[0][0]=1;
for(int i=2;i<=n*2+1;i++){
cin >> a[i];
!p[a[i]][0]?p[a[i]][0]=i:p[a[i]][1]=i;
}
a[n*2+2]=0,p[0][1]=n*2+2;
n++;
sort(id,id+n,[&](int a,int b){
return p[a][1]-p[a][0]<p[b][1]-p[b][0];
});
// for(int i=1;i<=n;i++) cout << a[i] << " \n"[i==n]; //注意下标是到n*2
for(int num=0;num<n;num++){
int x=id[num];
dp[x][p[x][0]]=x;
for(int i=p[x][0]+1;i<=p[x][1];i++){
dp[x][i]=dp[x][i-1]+x; //默认贡献为x
if(p[a[i]][0]>p[x][0] && i==p[a[i]][1])
dp[x][i]=max(dp[x][p[a[i]][0]-1]+dp[a[i]][i],dp[x][i]);
}
}
cout << dp[0][n*2];
}星期三：
学了下康托展开，可用来求全排列的编号，树状数组优化后复杂度为O(nlogn)
逆康托可以把编号转为全排列（编号的数据范围需在 20！内，21！会爆 ull
学这个的目的主要是掌握逆康托，如果遇到了可暴力全排列的题且不知正解，可以试着用随机数加上逆康托，生成一个随机的全排列，然后开始暴力枚举一定次数，有极小概率撞上答案，不过此为走投无路之举，且有很大的局限性，慎用
贴个n^2板子：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
ull fac[N];
ll kt(vector<int> ve){
ll res=0;
int sz=ve.size();
unordered_map<int,bool>vi;
for(int i=0;i<sz;i++){
int cnt=0;
for(int j=1;j<ve[i];j++) if(!vi.count(j)) cnt++; //可用树状数组优化
(res+=1ll*cnt*fac[sz-i-1]%mod)%=mod;
vi[ve[i]]=1;
}
return ++res%mod;
}
vector<int> rev_kt(ull k,int len){ //编号和排列长度
vector<int>ans;
k--;
vector<int>ve;
for(int i=1;i<=len;i++) ve.push_back(i);
for(int i=1;i<=len;i++){
int t=k/fac[len-i];
ans.push_back(ve[t]);
ve.erase(ve.begin()+t);
k%=fac[len-i];
}
return ans;
}
void solve(){
cin >> n;
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
vector<int>ve;
for(int i=1;i<=n;i++){
int x; cin >> x;
ve.push_back(x);
}
cout << kt(ve);
}星期四：
补 24牛客多校 二 G 牛客传送门
题意：定义一集合为好集合，需满足元素乘积为平方数即 x^2，此集合权值即为 x。给一数集，问所有为好集合的子集的权值和是多少
贴个dalao题解：2024牛客暑期多校训练营2 - Luckyblock - 博客园 (cnblogs.com)
思路：由平方数考虑到质因子分解，值域1000以内，若存在大于31的质因子，则必定只有一个，且31以内的质数也只有11个，可以状压处理，将所有数分解，若不存在大质数则分解后为1，若存在即为大质数，按此分组，对每组进行转移
如何分解：对于每个数，我们要知道它的小质数的奇偶状态，但除此之外，还要处理出它的偶数个质因子对答案的贡献，即处理为pair值，再分组处理
dp【i】【mask】【0/1】表示考虑到每组第 i个数，小质数奇偶状态为mask，选了 偶/奇个大质数
对于不存在大质数的数，只需关注小质数奇偶状态，第三维暂时用不上，对于每个【ma，v】， 枚举状态进行转移，注意答案除了需乘v外，还需乘上两状态同奇的质数
对于存在大质数的数，按大质数 p分组进行转移，因为答案不断累加，到了下一组后，之前的答案仍保留，不过需要清除选了奇数个p‘（p’<p 的状态的值。接下来仍是枚举状态转移，注意每当 p选了偶数个，dp【now^1】【mask】【0】就需乘上 p
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll dp[2][1<<11][2];
vector<PII>ve[1010];
int p[11]={2,3,5,7,11,13,17,19,23,29,31};
ll cal(int ma1,int ma2){
ll res=1;
for(int i=0;i<11;i++) if((ma1&ma2)&1<<i) (res*=p[i])%=mod;
return res;
}
void solve(){
cin >> n;
for(int i=1;i<=n;i++){
int x; cin >> x;
ll xma=0,v=1;
for(int j=0;j<11;j++){
while(x%p[j]==0){
if(xma&1<<j) v*=p[j];
xma^=(1<<j);
x/=p[j];
}
}
ve[x].push_back({xma,v});
}
int now=0;
dp[0][0][0]=1;
for(auto [ma,v]:ve[1]){
for(int mask=0;mask<1<<11;mask++) dp[now^1][mask][0]=dp[now][mask][0];
for(int mask=0;mask<1<<11;mask++){
int nmask=mask^ma;
(dp[now^1][nmask][0]+=dp[now][mask][0]*v%mod*cal(mask,ma)%mod)%=mod;
}
now^=1;
}
for(int val=32;val<=1000;val++) if(!ve[val].empty()){
for(int mask=0;mask<1<<11;mask++) dp[now][mask][1]=0;
for(auto [ma,v]:ve[val]){
for(int mask=0;mask<1<<11;mask++)
dp[now^1][mask][1]=dp[now][mask][1],dp[now^1][mask][0]=dp[now][mask][0];
for(int mask=0;mask<1<<11;mask++){
int nmask=mask^ma;
(dp[now^1][nmask][0]+=dp[now][mask][1]*v%mod*cal(mask,ma)%mod*val%mod)%=mod;
(dp[now^1][nmask][1]+=dp[now][mask][0]*v%mod*cal(mask,ma)%mod)%=mod;
}
now^=1;
}
}
cout << (dp[now][0][0]-1+mod)%mod;
}星期五：
补 24牛客多校 三 A 牛客传送门
思路：最少的需要从右往左的趟数为 s= ( n-r ) / ( r-l )向上取整，最后一趟载 r个人，每个来回能有 r-l个人过河。把每个人的体力数处理为能趟一来回的次数 a即a = ( h-1 )/2。
最少要往回趟 s次，每次载 l个人，在贪心即每次运输体力最高的人的前提下，所有人 a的总和最少需要 s*l，若一个人的 a大于 s，那么超出的部分没有意义，所以计算总和时 a需要和 s取min，再和 s*l进行比较
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll a[N];
void solve(){
int l,r; cin >> n >> l >> r;
ll s=(n-r+r-l-1)/(r-l),cp=0;
for(int i=1;i<=n;i++){
int h; cin >> h;
a[i]=(h-1)/2;
cp+=min(a[i],s);
}
if(cp>=s*l) cout << "YES";
else cout << "NO";
}恐怖故事，摸了两天半鱼，发现已经星期一了