首页
关于
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
Codeforces Round 905 (Div. 2)
一剑,一念。You Are So Beautiful算法本质思维题目大意定义数组a[]中美丽子数组:a[]有且仅有一个子序列与其相等给定长度n的数组a[],计数其美丽子数组。思路推演模拟:3 2 1 2 3 1比如其中3 2 1是一种显然不美丽的情况,因为1之后存在1。考虑是否所有数字都要满足身后没有重复的数字。进一步思考,发现对于3 2 1来说,需要保证1是最后一次出现、3是第一次出现。遍历拿下。Dances (Hard Version)算法本质思维题目大意给定长度n的数组a[] b[],会进行m轮游戏,输出每轮游戏得到值的和。其中仅a[1]在第i轮游戏的值为i,其他信息每轮游戏不会改变。每轮游戏规则:玩家希望顺序执行以下操作,使得最后对于任意i来说都满足a[i]<b[i]:玩家删除k个a[]的元素和k个b[]的元素玩家改变a[]或者b[]元素顺序每轮游戏得到的值是最小化的k。n m <= 2e5 k <= n 元素值 <= 1e9思路推演首先思考每轮游戏如何处理。(即easy版本)显然在排序后,每个删除都会是删除a[]最大值、b[]最小值(最优删除)。那什么时候才算合法,举例:a[]: 1 2 3 4 5 6 7 b[]: 1 1 2 2 3 3 4按照最优删除处理,至少也得删除两次,使得b[1]>a[1],如此一来,其实我们可以用连线来表示两者的关系。对于a[i]来说,其连线对象是b[]中大于a[i]且没有被占用的最小值。k显然是没有相连的元素个数。接着思考多轮游戏会如何变化。如果我们仅改变一个值,实际上对游戏的影响并不大。首先时候a[2~n]和b[]制作连线图,然后观察b[]未被连线的最大元素,若a[1]的值小于这个最大元素,则可以视作两者相连,反之则可以记作没有相连的元素。这里是一个贪心思路,可能需要仔细思考一下ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<int> a, b; a.push_back(2e9); // 这里可以给一个无限大或者不给 for (int i=2; i<=n; i++) a.push_back(in()); for (int i=1; i<=n; i++) b.push_back(in()); sort(a.begin(), a.end()); sort(b.begin(), b.end()); // 排序后将其放入双端队列中,需要其取前、取后的功能 for (int x:a) dqa.push_back(x); for (int x:b) dqb.push_back(x); vector<int> sheng; // 记录b[]中没有被占线的元素 int res=0; // 记录删除元素个数 while (1) { int x=dqa.front(); while (dqa.size() && dqb.front()<=dqa.front()) // 如果不合法,则需要删除元素,使用最优删除操作 { sheng.push_back(dqb.front()); dqa.pop_back(), dqb.pop_front(), res++; } if (dqa.size()==0) // 说明已经合法了 break; dqa.pop_front(); dqb.pop_front(); } int top = sheng.back(); // 找到b[]中没有占线元素的最大值 int ans=0; int p=min(top-1, m); ans += p * (res-1); // a[1] = 1~p,其k值是res-1 ans += (m-p) * res; // a[1] = p+1~m,其k值是res cout<<ans<<endl; return; }Time Travel算法本质思维、模拟题目大意(抽象)存在n个点m条无向边,但是m条边分布在t张图中。在这场旅行中一共有k天,玩家希望从点1走至点n,当玩家处于第i天时,仅能使用第a[i]张图的边进行移动。为了方便理解,我们可以视作玩家仅能在白天行动,在第0天的傍晚玩家处于点1处、接着休息了一晚上,第1天清晨仍然处于点1且准备行动。玩家每天行动至多一条边(可以不动)。输出抵达点n的天数(通常来说是傍晚抵达的),或者告知k天内无法抵达。n m k <= 2e5思路推演刚开始看,觉得像传说中的分层图,但是转念一想,cf不会这样出的最短路思想,用dj即可解决。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<pair<int,int>> g[maxn]; // {w, v} inline void solve() { int t; cin>>n>>t; for (int i=1; i<=t; i++) { cin>>m; while (m--) { int u, v; cin>>u>>v; g[u].push_back({i, v}); // i表示第i张图的边 g[v].push_back({i, u}); } } cin>>k; vector<vector<int>> cod(t+5); // cod[x] = {a, b, c}表示第x张图会在第a、b、c天出现 for (int i=1; i<=k; i++) cod[in()].push_back(i); vector<int> dis(n+5, 1e18), vis(n+5); // 最短路结构 priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> q; q.push({0, 1}); // 第0天傍晚抵达点1 dis[1] = 0; while (q.size()) { auto [t, u] = q.top(); q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [w, v]:g[u]) { auto it = lower_bound(cod[w].begin(), cod[w].end(), t+1); // 第二天清晨,需要w>=t+1 if (it==cod[w].end()) continue; int nt = *it; // 在nt的傍晚抵达点v if (nt < dis[v]) { dis[v] = nt; q.push({dis[v], v}); } } } int ans = (dis[n]<=k ? dis[n] : -1); cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 904 (Div. 2)
Counting Rhyme算法本质思维题目大意给定n个数字,定义美丽数字对a b:若x满足a%x==0 && b%x==0则x必然不等同于n个数字的某个计数美丽数字对。n <= 1e6 元素 <= n思路推演显然,其实就是gcd(a,b)不能被任意一个存在的数字整除,比如设其为g这里每次运算其实存在3个元素:a b g,我们希望找到gcd(a,b) % g等于0或者不等于0的情况。显然,从a入手是不可行的,题目讲元素大小限制在n,这些行为都在告诉我们,要从g入手。从g入手也面临一些问题,其中最大的问题是重复。观察某个例子:4 2 3 12 4这个例子中,需要考虑g为2 3 4的情况。笔者在赛时对于重复的做法,采取容斥解决(因为其复杂度不会特别高),赛时没写完,赛后发现会T这里实际是巧妙利用了调和级数的复杂度,g也是处于这个限制内的,这点是容易思考错过的。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int f(vector<int> &cnt, vector<int> &dp, int idx) { if (dp[idx]!=-1) return dp[idx]; int num=0; for (int i=idx; i<=n; i+=idx) num += cnt[i]; int res = num*(num-1)/2; for (int i=idx*2; i<=n; i+=idx) res -= f(cnt, dp, i); return dp[idx] = res; } inline void solve() { cin>>n; // cnt[x]=y:值为x的元素个数是y // dp[x]=y:有x对元素的gcd值是y // vis[x]=1:元素对的gcd值为x时是不合法的,反之是合法的 vector<int> cnt(n+5), dp(n+5, -1), vis(n+5); for (int i=1; i<=n; i++) cnt[in()]++; f(cnt, dp, 1); // 记忆化搜索处理dp[] int ans=n*(n-1)/2; for (int val=1; val<=n; val++) { if (cnt[val]>0) for (int w=val; w<=n; w+=val) vis[w] = 1; ans -= dp[val] * vis[val]; } 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
Codeforces Round 902 (Div. 2)
Autosynthesis算法本质思维、图题目大意给定数组a[],玩家可以顺序圈出任意元素(可以重复圈出某一元素),在某个操作后停止,根据当前局面得到2个数组:v1[]:由a[]没有圈中的元素值顺序构成v2[]:由玩家圈元素的下标顺序构成玩家能否使得上面两个数组相等,如果可以输出相等数组信息(任意一个即可),否则输出-1。思路推演下标与值需要相等,这种问题的经常套路就是连接当前元素和其值下标的元素。为了方便思考,笔者的连接方式是反向的,即当前元素值对应的元素作为元素的父节点。然后在这个基础上思考,有规则:每个点仅存在一个父节点(这比较合理,也是反向连边的原因)抽象题意:思考可知,不用理会圈出元素的顺序,可以将圈出的元素看作涂了黑色,黑色点下的子节点会被默认涂成灰色,则需要满足以下条件:黑子节必须有一个儿子灰节点灰节点的父节点必须是黑节点所有点非黑即灰抽象之后,再次模拟思考,发现如果是链结构,则十分简单,核心难点在于环结构。先用topo处理链结构,这里需要注意自环的情况。接着看环情况。由于规则的限制,有可能一些环的点,必须是黑色,先检查。如果存在这样的点,就可以topo求出环,然后检查是否可行即可。如果不存在,则其所有点性质相同,随机指定一个点赋予颜色即可。赛时因为图写的太少,思路不够清晰(少部分原因在于思路,大部分原因在于图写少了),结果没出来。(不过即可出来了,也其实有一个小bug)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int fu[maxn], chu[maxn]; // 父节点、出度 vector<int> g[maxn]; // 仅存儿子节点 int color[maxn]; // 颜色,1代表灰色、2代表黑色 vector<int> tmpv; set<int> tmpst; void dfs(int u) // 找环点 { if (tmpst.count(u)) return; else { tmpv.push_back(u); tmpst.insert(u); dfs(fu[u]); } } int getc(int u) // 根据子节点推理颜色(颜色在子节点都涂色才有效) { int cnt1=0, cnt2=0; for (int v:g[u]) { if (color[v]==1) cnt1++; if (color[v]==2) cnt2++; } return (cnt1>0 ? 2 : 1); // 儿子有灰色,则必黑色,反之黑色 } inline void solve() { cin>>n; for (int v=1; v<=n; v++) { int u=in(); if (u==v) continue; fu[v] = u; g[u].push_back(v); chu[u]++; } flag = 1; // 处理所有的非环点 queue<int> q; for (int i=1; i<=n; i++) if (chu[i]==0) q.push(i); vector<bool> vis(n+5); while (q.size()) // topo处理 { int u=q.front(); q.pop(); vis[u]=1; color[u] = getc(u); chu[fu[u]]--; if (chu[fu[u]]==0 && fu[u]!=0) q.push(fu[u]); } for (int i=1; i<=n; i++) // 检查非环点是否存在冲突 { if (vis[i] && fu[i]==0 && color[i]!=2) flag = 0; } if (!flag) { cout<<-1<<endl; return; } // 处理环上点 for (int i=1; i<=n; i++) { if (vis[i]) continue; tmpv.clear(); tmpst.clear(); dfs(i); int num=0; for (int u:tmpv) { if (getc(u)==2) // 因为还有儿子,如果2值,说明必须是黑色,如果1值则不一定 { color[u]=2; vis[u] = 1; chu[fu[u]]--; num++; } } if (num==0) // 保证环有一个点被打开——才能开始topo { int u=tmpv.front(); color[u] = 2; vis[u] = 1; chu[fu[u]]--; num++; } queue<int> q; for (int u:tmpv) // 找环上的叶节点 { if (vis[u]) continue; if (chu[u]==0) q.push(u); } while (q.size()) // topo跑环 { int u=q.front(); q.pop(); vis[u]=1; color[u] = getc(u); chu[fu[u]]--; if (chu[fu[u]]==0) q.push(fu[u]); } for (int u:tmpv) // 检查环点是否存在冲突 if (getc(u)!=color[u]) flag = 0; } if (!flag) { cout<<-1<<endl; return; } vector<int> ans; for (int i=1; i<=n; i++) { if (color[i]==1) // 灰色 ans.push_back(fu[i]); } cout<<ans.size()<<endl; for (int x:ans) cout<<x<<" "; cout<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 901 (Div. 2)
Jellyfish and EVAEVA,出击!算法本质思维、dp题目大意给定有向图,其中保证边:由编号较小点 指向 编号较大点现在玩家和Alice一起从点1前往点n,玩家和Alice需要各自选择一条出点为当前点的边,Alice会随机选择(且玩家选择前不知道Alice的选择):选择道路一致玩家和Alice沿着选择边前进选择道路不一致选择的两条道路被破坏输出最大化两人抵达n点的概率。n <= 5e3 m <= 2e5思路推演稍加模拟可以发现,dp做法,需要从后向前推。核心在于,假设前方存在3个点,每个点的胜率不一致,当前玩家应该如何抉择。朴素的想,我们肯定希望尽可能地走胜率高的点,由于Alice的随机选择,核心在于计算出去不同点的概率。稍加模拟,发现并不存在一个简单的计算规律。但是有2个点提醒了玩家,n的范围给的相对奇怪,且每次失败会破坏2条道路。这实际上在提示玩家使用递推的方式去计算走不同点的概率。这里值得一提的是,在赛时,我们力求将走通概率最高的点分配给胜率高的点,实际上在计算走通概率时,完全没有必要。我们可以计算出所有点的走通概率之后,再排序就好。当时思路不够清晰。假设之后存在n个点可走。首先第一个点无论如何选择,其走通概率是1/n,考虑失败的情况,则需要在剩余n-1个点中选择一个点作为同样失败的点。如果第二个点选择的n-1个点中的第x个点,则剩余的n-2个点,就可以套用n-2的情况概率一一对应即可。考虑x的不同还有先前概率等细节,就可以递推求出不同点的概率了。求出之后,倒着dp即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<vector<double>> pi(n+5, vector<double>(n+5)); // 这里记录了胜率情况 for (int i=1; i<=n; i++) // 递推处理 { double base = 1.0/i; if (i%2) // 奇数层比较特殊,其胜率均分 { for (int j=1; j<=i; j++) pi[i][j] = base; continue; } pi[i][1] = base; int cntl=0, cntr=i-2; for (int j=2; j<=i; j++) // 这里递推公式看着有些复杂,实际不难,可以自行推导 { // cntl cntr表示第j个元素左右元素个数,如果去掉右侧元素,则其对应的为上一层的j-1位置,去掉左侧对应的是j-2位置 pi[i][j] = pi[i-2][j-1]*cntr + pi[i-2][j-2]*cntl; // 这里注意对应关系 pi[i][j] *= base; cntl++, cntr--; } } vector<vector<int>> g(n+5), g2(n+5); // g2记录反向图 vector<int> chu(n+5); vector<double> dp(n+5); while (m--) { int u, v; cin>>u>>v; g[u].push_back(v); g2[v].push_back(u); chu[u]++; } dp[n] = 1; queue<int> q; for (int i=1; i<=n; i++) if (chu[i]==0) q.push(i); while (q.size()) { int u=q.front(); q.pop(); int num = g[u].size(); vector<double> nxt; // 下一个点的胜率 for (int v:g[u]) nxt.push_back(dp[v]); sort(nxt.begin(), nxt.end()); nxt.push_back(0); // 维持1下标 reverse(nxt.begin(), nxt.end()); // 胜率大的在前 for (int i=1; i<=num; i++) // 当前点的胜率 = 选择下一个点的概率 * 下一个点的胜率 dp[u] += pi[num][i]*nxt[i]; for (int v:g2[u]) // 倒着向前topo { chu[v]--; if (chu[v]==0) q.push(v); } } double ans = dp[1]; cout<<fixed<<setprecision(12)<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 861 (Div. 2)
Petya, Petya, Petr, and Palindromes算法本质思维题目大意给定长度n的数组。定义某个奇长度数组的成本:以回文对不相等的对数输出所有长度k的子数组的成本之和。n k <= 2e5思路推演稍加模拟即可发现,数组奇偶下标可以分开看。为了避免重复,我们仅遍历左端点,通常来说,右端点是右侧k/2个元素(奇偶分开处理后)。但是首尾有所不同。一种方法是单独处理首尾附近的点。这其实就是模拟写法,推理写仔细点即可。还有一种方法是整体看待。对于每个左端点来说,其右端点是一个区间值。且题目要求保证与相同值关系很大。我们可以用一个vector来存放相同值的下标,然后方便计算期间。这个做法的难点在于计算区间的公式较难推理。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { cin>>n>>k; vector<vector<int>> cod0(2e5+5), cod1(2e5+5); // 奇偶分开讨论,记录每个值的下标 vector<int> a(2e5+5); for (int i=1; i<=n; i++) { vector<vector<int>> &v = (i%2 ? cod1 : cod0); int x=in(); a[i] = x; v[x].push_back(i); } int ans=0; for (int i=1; i<=n; i++) // 枚举a[i]为左端点 { vector<vector<int>> &v = (i%2 ? cod1 : cod0); int x=a[i]; int l = max(i, i+k-1-2*(i-1)); // l~r的范围是右端点的区间(a[]中的下标),这里的公式是重点 int r = min(i+k-1, i+2*(n-i - k/2)); if (r<l) continue; int sum = (r-l)/2 + 1; // sum表示l~r区间值的数目,num表示这其中值为x的数目 int num = upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l); ans += sum-num; } cout<<ans<<endl; return; }Minibuses on Venus (easy version)算法本质思维、想象力题目大意给定n k mod,定义长度n的数组a[]美丽:所有元素值范围[0~k-1]存在i使得$a_i ≡ \sum_{j=1}^na_j(\mod k)$输出长度n美丽数组个数。n <= 100 k <= 30思路推演中等版本是需要数学板子优化如此小的数据,实际上是对想象力的考验。显然是dp,思考状态,重点在于如何不重复。经过观察可发现,每个元素值v只对应一个和值sum,但是sum可能对应0~2个元素值v。所以整体思路应该是枚举sum值,然后判断其是否有对应的元素值。这里有两个朴素的想法:先计算和为sum值的所有方案数,再计算和为sum且没有使用对应元素值的方案数,两者相减即可如果有对应相同sum值,则称这两个元素值为一组。设计dp[i][s1][s2][0/1]:i表示下标,s1表示当前的和值,s2表示当前方案能否使得s2为合法和值。最后统计dp[n][s][s][1]的方案数即可。笔者使用的是方法2,但是写崩了,一直没改回来,看cup收到启发写了方法1,更简洁简单。代码写的是方法1,简单好理解。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k>>mod; vector<vector<int>> dp(n+5, vector<int> (k+5)); // dp[x][y]=t表示1~x位总和位y的方案数有t dp[0][0] = 1; for (int i=1; i<=n; i++) { for (int v=0; v<k; v++) { for (int last=0; last<k; last++) dp[i][(v+last)%k] += dp[i-1][last], dp[i][(v+last)%k]%=mod; } } int ans=0; for (int sum=0; sum<k; sum++) { vector<vector<int>> dp2(n+5, vector<int> (k+5)); // dp2[x][y]=t同上,但是不能使用sum对应的值 dp2[0][0] = 1; int v1=-1, v2=-1; // 计算sum对应的两个值 if (sum%2==0) v1=sum/2; if ((sum+k)%2==0) v2=(sum+k)/2; for (int i=1; i<=n; i++) { for (int v=0; v<k; v++) { if (v==v1 || v==v2) continue; for (int last=0; last<k; last++) dp2[i][(v+last)%k] += dp2[i-1][last], dp2[i][(v+last)%k]%=mod; } } ans += dp[n][sum] - dp2[n][sum]; ans = (ans%mod + mod) % mod; } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
1
2
3
4
...
18