首页
关于
Search
1
Codeforces Round 930 (Div. 2)
14 阅读
2
Codeforces Round 931 (Div. 2)
9 阅读
3
测试页面
6 阅读
4
Codeforces Round 922 (Div. 2)
6 阅读
5
Codeforces Round 926 (Div. 2)
6 阅读
默认分类
codeforces
登录
Search
算法小何
累计撰写
87
篇文章
累计收到
1
条评论
首页
栏目
默认分类
codeforces
页面
关于
搜索到
86
篇与
的结果
2024-08-26
Educational Codeforces Round 153 (Rated for Div. 2)
Yet Another Permutation Problem算法本质思维题目大意需要玩家构建长度n的循环排列,定义其美丽值:相邻元素的gcd值的不同个数输出最大化的构建方案。思路推演稍加模拟:对于1而言,其跟和相邻,gcd值都是1,对于2而言,其与2的倍数相邻gcd值才是2,考虑其与4相邻是最优解(因为其他元素可能有更好的解法)。同理,2的右边放4,左边没什么用了,就放1吧。对于4而言,右侧应该放4的倍数,8是最优解,以此类推,我们找到了gcd值的1 2 4 8 ...,当大小不够时,回身找3,同理即可。最终构建出的数组形如:[1, 2, 4, 8, 16, ...., 3, 6, 12, 24, ...., 5, 10, 20, ....]Trees and Segments算法本质思维题目大意给定01串,设置l0表示串中连续0的最大长度,l1表示串中连续1的最大长度。现在至多可以执行k次操作:反转某位有式子:f(x) = x*l0 + l1独立地回答,当x属于[1~n],输出操作后最大化的f(x)。n <= 3e3思路推演稍加模拟可以发现,首先完全贪心思路是无法解决的,所以寻求dp解决。这里会有个经常的问题是,大概率不会是O(n)求一个f(x),若需要如此,完全可以将n修改为1e6,然后随机赋予一个x值求解。所以一定会有用到n^2^的算法的:预处理O(n^2^),所有x都能受益x之间存在关系,可以借用操作完后,肯定是存在2个无交集区间,分别是全0的最长区间和全1的最长区间,暂且默认全0区间在左。dp处理同时维护全0区间和全1区间不行(其权重未知,没有同一标准),但是维护单个信息还是可行的。比如dp[i][j]表示[1~i]中用j次操作后,最长的0区间长度。一个想法是,区间之间一定存在分界线,枚举分界线,然后枚举左边的操作次数和右边的操作次数,就能得到两个区间的长度。但是,对于每种区间长度,还需要枚举x的n个取值,这总体的复杂度达到了O(n^3^)。一个朴素的优化方式是:这里有n^2^种两个区间的长度,其存在部分单调性,用0区间长度作为key来记录,1区间的长度就具备了单调性,情况可以优化至n种。然后再对这相对优解枚举其x值,就可以O(n^2^)解决。回过头来,再来看dp[][]的设置,其实是存在一些小问题的。之前的状态设置完全转移困难,所以重新设计dp[i][j]表示操作j次以i结尾的最长0区间长度。这样转移十分好写:if s[i]==0: dp[i][j] = dp[i-1][j] + 1 # 不需要额外操作 else: dp[i][j] = dp[i-1][j-1] + 1 # 需要额外操作,注意i j边界然后再建立一个状态:$pre[i][j] = \max_{t=1}^idp[t][j]$来表示以1~i中,使用j次操作后的最长连续0区间。这样就拿到了所需要的东西,但是这仅仅是某一个,其实有4个东西需要拿到:1~i中,使用j次操作后的最长连续0区间长度i~n中,使用j次操作后的最长连续0区间长度1~i中,使用j次操作后的最长连续1区间长度i~n中,使用j次操作后的最长连续1区间长度建议使用函数优化。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<vector<int>> f(string s, char c) { s = " " + s; vector<vector<int>> dp(n+5, vector<int>(k+5)), pre(n+5, vector<int>(k+5)); for (int i=1; i<=n; i++) { for (int j=0; j<=min(k, i); j++) // 注意操作数可能为0,要从0开始 { if (s[i]==c) dp[i][j] = dp[i-1][j] + 1; else if (j>0) // 注意别越界 dp[i][j] = dp[i-1][j-1] + 1; pre[i][j] = max(pre[i-1][j], dp[i][j]); } } return pre; } inline void solve() { string s; cin>>n>>k>>s; vector<vector<int>> pre0, suf0, pre1, suf1; pre0 = f(s, '0'); pre1 = f(s, '1'); reverse(s.begin(), s.end()); // 倒过来就是suf了 suf0 = f(s, '0'); suf1 = f(s, '1'); vector<int> to(n+5, -1); // to[0区间长度] = 最大的1区间长度 for (int i=0; i<=n; i++) // 枚举分界点 { for (int l=0; l<=k; l++) /// 枚举左右方的操作数 { int r=k-l; int len0=pre0[i][l]; // 假设0区间在左,1区间在右的情况 int len1=suf1[n-i][r]; to[len0] = max(to[len0], len1); len0=suf0[i][r]; // 假设0区间在右,1区间在左的情况 len1=pre1[n-i][l]; to[len0] = max(to[len0], len1); } } vector<int> ans(n+5, -1); for (int len0=0; len0<=n; len0++) // 存在n个相对优解 { if (to[len0]==-1) continue; for (int x=1; x<=n; x++) ans[x] = max(ans[x], x*len0 + to[len0]); } for (int i=1; i<=n; i++) // 输出 cout<<ans[i]<<" \n"[i==n]; return; }Rollbacks (Easy Version)算法本质思维题目大意初始存在一个空数组,接下来有q次操作:+ x数组末尾增加值x的元素- x数组末尾减去x个元素!回溯上一个操作(类似于栈,无法回溯回溯的操作)?询问目前数组不同元素的个数Hard版本强制要求在线全部值 <= 1e6思路推演Eszy版本并不要求在线,这点提醒了我们。稍加模拟可以发现,减法的形态,有点类似于树的一个分支。例如当[1, 3, 2, 5, 3, 6]遇到减去3个元素后,数组末尾的[5, 3, 6]就可以视作树的一个分支。同时当前点需要跳转至2,这样的大幅度跳转需要优化至log级别,在线倍增符合我们的要求。还需要注意的一个点是回溯操作,其实其本质很简单,回溯到上一次操作的点,我们仅需要每次操作的时候,都记录一下之前的点即可。遇到问好,就在树上做个标记:第x个问号在次询问。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> g[maxn]; int up[maxn][20]; int a[maxn]; vector<int> cod[maxn]; int swim(int x, int step) // 向上移动step步的基础函数 { for (int wei=0; step>0; wei++) { if (step&1) x=up[x][wei]; step /= 2; } return x; } int ans[maxn]; int mp[maxn]; // 这里用map会爆内存(题目卡的比较死) int siz=0; void dfs(int u=0) { if (u < 0) return; if (u!=0) { mp[ a[u] ]++; if (mp[a[u]]==1) siz++; } for (int pos:cod[u]) ans[pos] = siz; for (int v:g[u]) dfs(v); mp[ a[u] ]--; if (mp[a[u]]==0) siz--; } inline void solve() { int q=in(); int y=q; int cnt=0, p=0, wen=0; // cnt记录出现的点数,p记录当前点的id,wen记录?出现的次数 vector<int> lastp; // 记录操作前的id,方便回溯 while (q--) // 维护树结构,然后记录有的节点需要答案 { string op; cin>>op; if (op=="+") { lastp.push_back(p); int num=in(); int u = ++cnt; // 新增点 g[p].push_back(u); // 记录其父亲多了一个子节点,方便之后访问 a[u] = num; // 记录点的值 up[u][0] = p; for (int i=1; i<=19; i++) // 更新一下树上倍增 up[u][i] = up[ up[u][i-1] ][i-1]; p = u; // 更新当前点 } else if (op=="-") { lastp.push_back(p); int num=in(); int u = swim(p, num); // 利用倍增log级别查询 p = u; // 更新当前点 } else if (op=="?") cod[p].push_back(++wen); // 记录问号 else if (op=="!") p=lastp.back(), lastp.pop_back(); } dfs(); for (int i=1; i<=wen; i++) cout<<ans[i]<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 152 (Rated for Div. 2)
Max to the Right of Min算法本质思维++、单调栈题目大意给定排列p[],定义[l, r]为合法区间:p[l~r]的最大值下标 > p[l~r]的最小值下标输出合法区间数。n <= 1e6思路推演这样的题,朴素思想一来有两种:固定区间左端点,枚举右端点固定区间最大值,枚举最小值至于具体固定左还是右,大还是小,本质上是一样的第一种方式,区间内的最值变化严重,无规律可言,直接放弃。相比而言,第二种方式可以把合法区间有条理分类去找。假设找以p[i]为最大值的合法区间,然后这天然就存在的限制是:区间内不能有>p[i]的值,这个由p[i]最大值引起的限制可以用单调栈来搞定。随后枚举<i的下标,找合法区间的最小值。通过数次模拟可以发现,左边可行的合法区间最小值,是一个单调递减的形式,其下标用j表示。用lmin[] lmax[] rmin[] rmax[]表示某个元素左右方向第一个大于、小于其的值的下标。每个合法区间,将其范围缩减至区间最值暴露于左右两端,用[j, i]表示——即对于a[j]为最小值、a[i]为最大值的合法区间的数目为:$(j-\max(lmin[j], lmax[i]))*(min(rmin[j], rmax[i])-i)$不过显然,最坏情况这样的复杂度为O(n^2^),复杂度不支持,思考优化。可以发现的是,如果枚举最大值下标i是从左往右枚举时,由于最小值在左的规则,i+1作为最大值下标找的合法区间最小值下标与i相同的地方许多,也许可以做些预处理来。而且由于这些最小值下标j从左往右是递增的,所以其rmin[]值也是递减的,而在上面可以公式可以看到,这个公式最大的问题就是max min值的分割处理(才能进行整体特征合并优化),而rmin值递增为公式右侧部分提供了分割处理的基础。公式左侧部分,可以通过lmin[j]的值来寻找可行的最小值下标。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; ddz(a, n); vector<int> s, sum; int ans=0; for (int i=1; i<=n; i++) { while (s.size() && a[s.back()]>a[i]) // s[]维护的是一个递增、且全部<a[i]的下标数组 { s.pop_back(); sum.pop_back(); } // 保证a[i]为最大值的合法区间中,s[l]是最靠左的合法区间最小值下标!(这里比较重要,画图理解) int l=upper_bound(s.begin(), s.end(), lmax[i]) - s.begin(); if (l < s.size()) // 存在这样的值 { int j=s[l]; // j为合法区间最小值下标(以a[i]为最大值、最左边的下标) ans += (j-lmax[i]) * (min(rmin[j], rmax[i]) - i); // 按照公式计算[j,i]的可达合法区间数 l++; // 接下来的s[l]不再是最左边的最小值下标,所以公式的左侧取`lmin[j]`而不是`lmax[i]`,同时lmin[j]可以很好的合并 // 上面这几步代码,实际上已经将公式左侧的情况分开讨论了,随后也讨论右侧的情况 int r=partition_point(s.begin()+l, s.end(), [&](int x) { return rmin[x] > rmax[i]; }) - s.begin(); // 找到s[]中第一个rmin[?]<=rmax[i]的下标 ans += (s[r-1] - s[l-1]) * rmax[i]; // 这部分区间,公式左侧取`lmin[j]`,公式右侧取`rmax[i]` ans += sum.back() - sum[r-1]; // 这部分用前缀和处理,具体看sum那的处理 ans -= (s.back() - s[l-1]) * i; } int pre = sum.size() ? sum.back() : 0; int last = s.size() ? s.back() : 0; sum.push_back(pre + (i-last) * rmin[i]); // 预处理一部分,画图理解 s.push_back(i); } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
Prefix Purchase算法本质思维题目大意给定长度n的数组c[],初始拥有长度n的全0数组a[]和k元。可以进行任意次操作:花费c[i]元,使得a[1~i]元素都+1输出操作后最大化的a[](字典序)。思路推演稍加模拟可知:价格相同,下标大的优下标相同,价格低的优可以选择不同价格的,但是要保证次数不减少这说明了,可以用贪心的思路去遍历可能的点,其符合:下标递增价格递增首个点是价格最低中,最靠右的点根据此模拟即可。(详细看代码)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { cin>>n; map<int, int> mp; for (int i=1; i<=n; i++) mp[in()]=i; cin>>k; vector<int> ans(n+5); int max_ci=1e9, lastid=0, bo=0; // max_ci表示选择次数上限、lastid记录上次访问id(排序保证价格递增,lastid维护id递增)、bo表示价格底部 for (auto [w, id]:mp) { if (id < lastid) continue; // 维护id递增 int ci=k/(w-bo); ci = max(ci, 0ll); // 范围在[0~max_ci]之前 ci = min(ci, max_ci); k -= ci*(w-bo); // 计算“剩余的钱” ans[id] = ci; // 记录选择 max_ci = ci; // 更大最大值限制 bo = w; lastid = id; } for (int i=n; i>=1; i--) // 因为是选取了一部分点,没有覆盖全部,手动覆盖 ans[i] = max(ans[i], ans[i+1]); for (int i=1; i<=n; i++) cout<<ans[i]<<" \n"[i==n]; return ; }Another MEX Problem算法本质思维、dp题目大意给定长度n数组a[],元素值为[0~n]。玩家可以选择若干个互不相交的子数组,输出最大化的每个子数组的mex值的异或和。n <= 5e3思路推演显然需要用到dp,在不考虑复杂度的情况下,构建dp解决(这个过程很可能领悟题目的特性)。首先来说表示一个范围的精确值十分好计算,但是这显然不合适题意来dp——因为可以空许多地方,意味分割线的数目会很多。所以自然而然的,使用dp[l][r][x] = 0/1来表示区间a[l~r]是否可以制造出x值。同时考虑转移方程,发现并不需要精确的左右端点范围,所以修改为:dp[r][x] = 0/1表示区间a[1~r]是否可以制造出x值。转移方程也相对简单:1~r可以视作由完全自己构成dp[r][ mex(a[1~r]) ] = 1看作由2个区间异或而成dp[r][ dp[mid][x] ^ mex(a[mid+1~r]) ] = 1通过设计dp状态,目前空间复杂度n^2^、时间复杂度n^3^,寻找特征继续优化。考虑mex的特征,当一个区间向外延申时,其mex值可能不变。定义不可替代区间:当区间长度为1 或者 不存在真子区间也可以获得相等的mex值通过继承方式,我们可以只用在不可替代区间上更新。证明:不可替代区间的数目是O(n)量级 区间长度为1的都是不可替代:有n个 考虑区间长度>1的情况: 对于任意长度>1的不可替代区间,其左右端点元素一定不相同,则先假定左端点值>右端点值 反证法: 对于每个左端点l,若存在多个r端点可以组成不可替代区间,先取2个为r1 r2,其r1<r2 首先可以知道mex(l, r1)>l(不可替代区间特点),r2<l<mex(l,r1),所以r2显然无贡献,删除r2不会对mex值产生影响。 所以可得,对于每个左端点l,至多有1个r端点可以组成不可替代区间(长度>1) 然后反过来,不可替代区间的数目是3n (也可以修改定义使其求为2n,但是这种方式不改变数量级,无所谓)所以,对于每个左端点,转移复杂度降低至O(n)。另外有担心异或导致值超出n,实际上没有这种数据,手动模拟,应该是存在什么数学式子约束。但是没有题解做出回答,所以目前无法解答。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { cin>>n; vector<int> a(n+5); vector<vector<int>> dp(n+5, vector<int>(n+5)), mex(n+5, vector<int>(n+5)), cod(n+5); for (int i=1; i<=n; i++) cin>>a[i]; // 初始化mex[][] for (int i=1; i<=n; i++) { vector<bool> zhi(n+5); int val=0; for (int j=i; j<=n; j++) { zhi[ a[j] ] = 1; while (zhi[val]) val++; mex[i][j] = val; } } // 维护cod,cod[l]记录了所有以l为左端点的**不可替代区间** for (int l=1; l<=n; l++) { cod[l].push_back(l); for (int r=l+1; r<=n; r++) { if (mex[l][r]!=mex[l+1][r] && mex[l][r]!=mex[l][r-1]) cod[l].push_back(r); } } dp[0][0] = 1; for (int l=0; l<=n; l++) { if (l>0) // 继承,表示中间有部分没有选择 { for (int x=0; x<=n+1; x++) if (dp[l-1][x]) dp[l][x] = 1; } for (int r:cod[l+1]) { for (int x=0; x<=n; x++) { if (dp[l][x]==0) continue; dp[r][ x^mex[l+1][r] ] = 1; } } } int ans=0; for (int i=0; i<=n; i++) if (dp[n][i]) ans = i; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
Tenzing and Balls算法本质思维、dp题目大意存在n个小球排成一列,给定数组a[]表示每个小球颜色,玩家可以执行任意次操作:选择2个相同颜色的小球,删除两球中间包括其在内所有小球输出最大化删除的小球个数。思路推演稍加模拟可以发现,核心在于不同颜色小球的交错。相同颜色小球可以用连续区间来表示,问题在于如何处理不同颜色区间的交。再次模拟思考,发现没有特定规律,于是考虑dp:dp[x]=y表示在区间1~x中最多可以删除y个小球。转移的方式有二:不删除当前小球dp[i] = dp[i-1]当前小球作为区间右端点删除dp[i] = max(dp[x] + i-x)其中a[x+1] = a[i]复杂度在于第二个转移方程,朴素去做的话复杂度达到O(n^2^),既然是向前寻找,能否维护一个极值:dp[x]-x即可。当然也可以转换dp定义,这样看起来更直观:dp[x]=y表示区间1~x中最少剩余y个小球:不删除当前小球dp[i] = dp[i-1] + 1删除当前小球dp[i] = min(dp[x])其中a[x+1] = a[i],这里开个数组记录一下即可ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> dp(n+5, 1e9), cod(n+5, 1e9); // dp[x]表示下标1~x中,保留的最少球数 dp[0] = 0; // cod[x]表示,当前小球颜色为x,之前状态的最少小球数 for (int i=1; i<=n; i++) { int x=in(); dp[i] = min(dp[i-1]+1, cod[x]); // 直接继承和跳跃继承 cod[x] = min(cod[x], dp[i-1]); // 维护 } int ans = n-dp[n]; cout<<ans<<endl; return; }Tenzing and His Animal Friend算法本质思维题目大意(抽象)给定无向有权图,玩家可以进行任意次操作:将点设置为白点或黑点(1必须是白点、n必须是黑点),任意边两侧点颜色不一致,则边权-1在保证边权不出现负数情况下,输出玩家至多可以进行的操作次数,并且输出每次操作的信息(用01表示点的黑白)。若可以无限次输出inf。n <= 1e2思路推演稍加模拟可以发现,若1 n两点不连通,则可以进行无限次操作。题目核心在于固定1是白点、n是黑点,那一定有中间点受伤。若画出1 n的任意一条路径,可以发现,每次操作至少路径上某边的边权会-1。这不难推出,理论上最多操作次数即其最短路,带着这个思路去模拟发现:若某点与n的最短路径是0,则其必须是黑点。随后以最短路的思维,从n出发,除开必须黑点的点,其余点每次操作都取白点。随着操作数的增加,可以视作黑点的面积不断扩大——正是最短路的模型。随后代码模拟即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 省略DSU板子 inline void solve() { cin>>n>>m; vector<vector<int>> g(n+5, vector<int>(n+5, 1e18)); // 两点的初始距离 DSU dsu(n); while (m--) { int u, v, w; cin>>u>>v>>w; dsu.merge(u, v); g[u][v] = g[v][u] = w; } if (dsu.same(1, n)==0) // 检查是否联通 { cout<<"inf"<<endl; return; } string now(n+1, '1'); // 初始情况:除了n点全选白点 now[n] = '0'; vector<int> cod(n+5); for (int i=1; i<=n-1; i++) cod[i] = g[i][n]; int tim=0, ci=0; vector<pair<string, int>> ans; while (1) { int minw=1e18, id=-1; for (int i=1; i<=n; i++) if (now[i]=='1' && cod[i]<minw) minw=cod[i], id=i; if (minw > 0) // 需要记录 { ans.push_back({now.substr(1, n), minw}); tim += minw; ci++; } for (int i=1; i<=n; i++) if (now[i]=='1') cod[i]-=minw; now[id] = '0'; for (int i=1; i<=n; i++) if (now[i]=='1') cod[i] = min(cod[i], g[id][i]); if (id==1) // 当1必须是黑点时,就无法继续操作了 break; } cout<<tim<<" "<<ci<<endl; for (auto [s, t] : ans) cout<<s<<" "<<t<<endl; return; }Tenzing and Triangle算法本质思维、线段树题目大意存在一个区间由3条直线围成:y=0x=0x+y=k思路推演一个重要的特性是,三角形之间不存在交集。观察x+y=k线,我们需要在这选择若干不相交区间。在一维坐标上,我们需要选择若干区间(不同选择有不同成本),最后完全覆盖整个区间。这是一个经典的dp[]做法:dp[x]=y表示覆盖区间[1~x]的最小成本是y。先假设所有点都是单独消除,整体成本目前是sum,设f(l,r)表示x轴l~r三角形覆盖点的成本和 - A*(r-l)。这样就可以把题目转为sum减去若干个不相交的f(l,r)——求若干个不相交的f(l,r)的最大值。dp[x]=y表示处理完所有1~xac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 899 (Div. 2)
Card Game算法本质思维题目大意给定长度n序列,玩家初始金额0元,可以进行若干次以下操作之一:删除奇下标元素,并加+对应元素的金额删除偶下标元素结束游戏输出最大化最终金额。思路推演先贪心的想,所有>0的元素我们都希望得到,能否实现。奇下标元素当然容易实现,只需要从后往前拿即可。偶下标稍微困难一些,其核心在于,若前面有被拿掉的元素,则一定可以实现。考虑首个>0的元素下标是偶下标,我们也可以尝试删除下标2的元素,来实现前面拿到元素这个条件。所以可以知道,下标>2的元素,可以任取。然后再考虑下标1和下标2的元素情况即可。Tree XOR算法本质思维题目大意给定一棵树,每个点有初始值a[i],希望最终使得所有点的值相等。玩家可以进行以下操作:选择某个节点u和正整数x,其含自己的所有子节点都异或x,成本是子树(含自己)节点数 * x对于这棵树的根是[1 ~ n]的情况,分别计算其最小成本。思路推演首先拆位是肯定的,拆位之后可以把图看成黑白双色的图。因为题目的要求对所有点都当根节点的情况,这十分贴合换根dp的特性,所以优先考虑换根dp。然后其实这就是一个相对基础的换根dp做法,推一下递推公式即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> g[maxn]; int c[maxn], a[maxn]; int wast[maxn], num[maxn], wast2[maxn]; // 有方向情况:num[x]表示包括其本身的子节点数目,wast[x]表示将其子树都变成和自己同一颜色的操作节点数 // 无方向情况(或者所有方向情况):wast2[x]其作为根节点,需要操作的节点数 void dfs(int u, int fr=0) { wast[u] = 0; num[u] = 1; for (int v:g[u]) { if (v==fr) continue; dfs(v, u); num[u] += num[v]; wast[u] += wast[v]; if (c[v] != c[u]) wast[u] += num[v]; } } void dfs2(int u, int fr=0) { wast2[u] = wast[u]; if (fr!=0) { int wfu = wast2[fr] - wast[u]; if (c[u]!=c[fr]) wfu -= num[u]; wast2[u] += wfu; if (c[u]!=c[fr]) wast2[u] += n-num[u]; } for (int v:g[u]) { if (v==fr) continue; dfs2(v, u); } } inline void solve() { cin>>n; for (int i=1; i<=n; i++) cin>>a[i]; m = n-1; while (m--) { int u, v; cin>>u>>v; g[u].push_back({v}); g[v].push_back({u}); } vector<int> ans(n+5); for (int val=1, t=0; t<20; val*=2, t++) { for (int i=1; i<=n; i++) { if (a[i] & val) c[i] = 1; else c[i] = 0; } dfs(1); dfs2(1); for (int i=1; i<=n; i++) ans[i] += wast2[i]*val; } for (int i=1; i<=n; i++) { cout<<ans[i]<<" \n"[i==n]; g[i].clear(); } return; }Two Permutations (Hard Version)算法本质思维题目大意给定长度分别是n和m的排列a[] b[],现在玩家可以进行若干次操作:选择i ja[i]左右两侧的元素交换,同时其内部顺序不变b[j]左右两侧的元素交换,同时其内部顺序不变目的是最终使得a[]和b[]同时有序。(不可行输出-1)简单版本1e4次操作内完成困难版本最少操作次数完成n m <= 2500思路推演 - 简单版本首先思考简单版本,显然是需要一个必胜法。朴素的想法是,维护有序区间,然后依次增长,说白了就是先找1,然后找1 2,然后找1 2 3。模拟的时候就可以发现,因为中间仅有一个元素位置不变,例如已经有了1 2 3,现在希望加入4,则4要成为这个被操作的元素。我们希望当时的情况类似于:x x x 4 x x x 1 2 3,这样通过一次操作就可以凑成1 2 3 4了。想要使得1 2 3出现在末尾,其实也比较简单,x x 1 2 3 p x x,操作p元素即可。至此我们就得到了一个简单的必胜法,每次至多2次操作即可使得维护的有序区间+1。接下来要解决的问题是同时有序。稍加模拟可以发现,对同一元素重复操作2次数组不变,意味如果其操作数之差是偶数,则两者可行。模拟过程中可以发现,对于长度n的序列,一定存在操作n次后不变的情况。所以考虑一下奇偶同步的情况即可。这个结论可以说是模拟后猜的,结合简单版本的限制,困难版本会证明思路推演 - 困难版本到这一步,需要抽象成一个全新的模型才能求解最小操作——每次操作的核心。每次操作会移动n-1个元素,这太复杂了,能否看作移动操作元素。至此需要引入循环数组。对于1 2 3 4 5,如果对3操作,理论上应该是4 5 3 1 2,如果我们只考虑移动3,则可以视作移动至开头的循环数组3 1 2 4 5。但是显然,下次移动就并非移动至开头,而是移动至上次3存在的地方。我们引入一个虚拟的0,每次操作可以视作选择某个非0元素与0的位置交换。最后保证有序的循环数组即可。(未完)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
1
...
6
7
8
...
18