24.9.1（康托展开）

2024-09-02 22:04
文章标签 展开 康托 24.9

本文主要是介绍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 <= \sqrt{n}，双重循环枚举点集，取出存在的边，若 k > \sqrt{n}，枚举 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*2for(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;        //默认贡献为xif(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";
}

恐怖故事，摸了两天半鱼，发现已经星期一了

这篇关于24.9.1（康托展开）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1131186。

相关文章

3174. 清除数字（24.9.5）

3174. 清除数字（24.9.5）

题目 给你一个字符串s。你的任务是重复以下操作删除所有数字字符：删除第一个数字字符以及它左边最近的非数字字符。请你返回删除所有数字字符以后剩下的字符串。 示例 1： 输入：s="abc" 输出："abc" 解释：字符串中没有数字。 示例 2： 输入：s="cb34" 输出："" 解释：一开始，我们对s[2]执行操作，s变为"c4"。然后对s[1]执行操作，s变为空字符串。 提示： 1 <
阅读更多...
通知Notification（可展开的大布局）使用，适配android8.0

通知Notification（可展开的大布局）使用，适配android8.0

补充修正： 2018-11-07 问题：Notification PendingIntent失效，每个通知都响应第一个PendingIntent https://blog.csdn.net/u013370255/article/details/83791750 2018-08-16 问题：app版本更新，通知形式显示安装包下载进度 https://blog.csdn.net/u01337025
阅读更多...
vue3 行点击事件 table 树 点击行展开

vue3 行点击事件 table 树 点击行展开

需求：每次需要点击左侧小按钮才可以展开不方便，提出点击行就展开 el-table 添加 ref="tableDeptRef"@row-click="handleRowClick" 方法 const tableDeptRef = ref()/**行点击事件 */const handleRowClick=(row)=> {tableDeptRef.value.toggleRowExpa
阅读更多...
zm-tree-org 数据量过大时，全部展开后，根节点点击收缩，树形消失

zm-tree-org 数据量过大时，全部展开后，根节点点击收缩，树形消失

zm-tree-org 数据量过大时，全部展开后，根节点点击收缩，树形消失 <zm-tree-orgref="tree"@on-expand="onExpand"</zm-tree-org>export default {methods: {onExpand(e, data) {<!-- 当为根节点,且根节点为闭合时 -->if (data.root === true && data.expa
阅读更多...
Servelet学习-24.9.3

Servelet学习-24.9.3

文章目录 前言一、Servelet概述1.1 简单入门：2.2 生命周期 二、HttpServletRequest对象2.1 常用方法 三、HttpServeletResponse对象 前言 九月，加油 一、Servelet概述 Servelet： server applet  servelet就是一个接口,定义了Java类被浏览器访问到的规则，内部一共包含了五个抽
阅读更多...
二叉树展开为列表（LeetCode）

二叉树展开为列表（LeetCode）

题目 给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 解题 class TreeNode:def __init__(self, val=0, left=None, right=None):self.va
阅读更多...
周报 | 24.8.26-24.9.1文章汇总

周报 | 24.8.26-24.9.1文章汇总

为了更好地整理文章和发表接下来的文章，以后每周都汇总一份周报。 周报 | 24.8.19-24.8.25文章汇总-CSDN博客 python | 提升代码迭代速度的Python重载方法-CSDN博客 机器学习算法与Python学习 | 黑匣子被打开了？能玩的Transformer可视化解释工具！_研究别人的黑盒算法 机器学习 python-CSDN博客 极市平台 | 语言图像模型大一统！M
阅读更多...
leetcode 114:二叉树展开为链表

leetcode 114:二叉树展开为链表

二叉树的题，使用递归的方式 TreeNode *last(TreeNode*root){while(root->right!=NULL){root=root->right;}return root;}TreeNode *fla(TreeNode *root){if(root==NULL)return NULL;if(root->left==NULL&&root->right==NULL)re
阅读更多...
24.9.1学习心得

24.9.1学习心得

VGG（Visual Geometry Group）网络是由牛津大学视觉几何小组提出的一种卷积神经网络模型，该模型因其在ImageNet大规模视觉识别挑战赛（ILSVRC 2014）中的优异表现而闻名。VGG模型的特点在于其架构的简单性和一致性，以及对参数数量的大量使用，这使得它成为了深度学习领域中一个非常受欢迎的基础模型。 VGG架构的主要特点包括： 堆叠的3x3卷积层：VGG网络使用了多
阅读更多...
求幂级数展开的部分和 / 求分数序列前N项和 / 特殊a串数列求和

求幂级数展开的部分和 / 求分数序列前N项和 / 特殊a串数列求和

习题4-2 求幂级数展开的部分和   (20分) 已知函数e^xe​x​​可以展开为幂级数1+x+x^2 /2! + x^3 /3! + \cdots + x^k /k! + \cdots1+x+x​2​​/2!+x​3​​/3!+⋯+x​k​​/k!+⋯。现给定一个实数xx，要求利用此幂级数部分和求e^xe​x​​的近似值，求和一直继续到最后一项的绝对值小于0.00001。 输入格式:
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2