首页
关于
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 796 (Div. 2)
The Enchanted Forest算法本质思维题目大意一维坐标上1~n上有n个金币产生器,0秒时每个金币产生器旁的金币是a[]表示,其每秒可以产生1金币。玩家0秒时可以移动至任意一点,一秒内会顺序进行以下操作:玩家移动至相邻格子或者不变玩家收集在这个格子上的所有金币金币产生器都产出1金币在第k秒时,输出最大化的金币收集数。(相当于进行以上k次操作)思路推演朴素的想可以发现,当k<n时,玩家总是不喜欢走回头路的。然后开始证明。玩家的收益可以大体分成两个部分:初始金币 + 增长金币如果玩家回头,则两部分收益都会下降,得证。不回头,则增长金币收益不变,所以只要找长度k的最大子段和。但是k>=n的情况可能有所不同。初始金币一定是会完全收集的,那如何才能得到最多的增长金币呢。也许可以反过来想一想,既然时间固定,增长金币的总数是一定的,我们只需要让增长金币最后剩余在地图上最少即可——k操作的最后n次操作完整走一遍地图即可。(之前的时间可以在原地发呆)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5); read(a, 1, n); int res, ans; if (k<n) { res = accumulate(a.begin()+1, a.begin()+1+k, 0ll); ans = res; for (int i=k+1; i<=n; i++) { res += -a[i-k] + a[i]; ans = max(ans, res); } ans += (k-1)*k/2; // 增长金币部分 } else { ans = accumulate(a.begin()+1, a.begin()+1+n, 0ll); int more = (n-1)*n/2; more += (k-n)*n; ans += more; } cout<<ans<<endl; return; }Sanae and Giant Robot算法本质思维 !题目大意给定两个长度n数组a[] b[]和m个区间,玩家希望让a[]变得同b[]一致,可以进行任意次一下操作:选择某个区间l r,保证$\sum_{i=l}^{r}a_i = \sum_{i=l}^{r}b_i$,然后使得a[l~r] := b[l~r]思路推演朴素地去想暂时没结果,缺少进入的思路。然后就想不出来了显然,如果a[] b[]的元素之和不相等,则肯定不可行。当我们使用操作时,似乎将一个数组分割成了两份,我们是否需要维护两份数组的也遵从上面的规律呢。我们回溯操作观察,这个规律会更明显。至此我们修改操作的规则:选择某个区间l r,保证$pa[l-1]=pb[l-1] \quad and \quad pa[r]=pb[r] $,然后使得a[l~r] := b[l~r]新的操作规则,才能称之为有效操作,其他的操作可以视作无效甚至于破坏相等抽象题意:可以视作这里有下标0开始长度n+1的01数组c[]和m个区间。若区间l r满足c[l] = c[r] = 1则可以使得c[l~r] := 1。最后希望使得c[0 ~ n]=1分析一下,我们希望能做一个类似触发器的东西,当c[l] = c[r] = 1时可以触发至某个区间。当然使用二维信息作key值显然复杂度不允许,所以就以下标做key值,触发时判断一下另外一个条件即可。另外当我们进行c[l~r] := 1操作时,那些从0值变成1值,会进行一次触发。这可以使用并查集里的find来优化——因为所有下标只触发一次。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 借用并查集find的优化结构 int go[maxn]; int find(int x) // 找到右边(含自己)第一个未被遍历的 { if (go[x]==0) return x; return go[x] = find(go[x]); } inline void solve() { cin>>n>>m; vector<int> a(n+5), b(n+5), c(n+5); read(a, 1, n); read(b, 1, n); vector<int> tol(m+5), tor(m+5); // 第i个区间的信息:id --> 下标 vector<vector<int>> booml(n+5), boomr(n+5); // 下标 --> id for (int i=1; i<=m; i++) { int l, r; cin>>l>>r; l--; tol[i] = l; tor[i] = r; booml[l].push_back(i); boomr[r].push_back(i); } queue<int> q; auto f = [&](int p) { // 触发器 c[p] = 1; go[p] = p+1; for (int id:booml[p]) if (c[ tor[id] ]) // 成功触发 q.push(id); for (int id:boomr[p]) if (c[ tol[id] ]) q.push(id); }; int pa=0, pb=0; for (int i=0; i<=n+1; i++) go[i]=0; // 这里注意细节使得go[n+1]=0 for (int i=0; i<=n; i++) { pa += a[i]; pb += b[i]; if (pa==pb) f(i); // 触发 } while (q.size()) { int id=q.front(); q.pop(); int l=tol[id], r=tor[id]; for (int p=find(l); p<=r; p=find(p)) // 触发 f(p); } flag = 1; for (int i=0; i<=n; i++) flag &= c[i]; cout<<(flag ? "YES" : "NO")<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 794 (Div. 2)
Linguistics算法本质思维题目大意玩家手中有4种不同的字符串特定个数:a b ab ba题目会给出s,输出玩家能否恰好使用完手中的字符串,将其组合成s。思路推演稍加模拟可以发现,因为不存在某个字符串有连续的a或b,所以可以将s分开成若干组,每组不得有连续a或b。这样情况就缩小至4种了:偶数长度(分别考虑a打头和b打头)以abababab为例,其中一种情况自然是使用4个ab搞定。思考如果使用了ba的情况,则可以视作a + b + 3个通用,这里的通用指的是ab或ba,没有限制奇数长度(分别考虑a打头和b打头)以abababa为例,肯定需要一个离散的a,剩下部分用3个通用即可还有一点需要思考的是,偶数长度的组,到底应该使用哪种情况。这里贪心的想,离散的a b优先级是最高的,我们希望ababab最好使用3个ab,当然这里有多个组,但是每个组选择另一种情况都是消耗相同的一对离散a b。所以我们将这些组按长度排序,尽可能满足长度小的组(这样尽可能减少a b的使用)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { map<string, int> mp, cod; vector<int> ab, ba; cin>>mp["a"]>>mp["b"]>>mp["ab"]>>mp["ba"]; // 记录玩家手中的字符串 string s; cin>>s; auto f = [&](int l, int r) { int len=r-l+1; if (len%2) { cod["tong"] += len/2; // 使用ab ba a+b if (s[l]=='A') cod["a"]++; // 使用离散a else cod["b"]++; // 使用离散b } else { if (s[l]=='A') ab.push_back(len/2); // 需要用len/2个ab 或者 a+b+(len/2-1)个通用 else ba.push_back(len/2); // 同理 } }; for (int l=0, r; l<s.length(); l=r+1) // 分组 { r=l; while (r<s.length()-1 && s[r]!=s[r+1]) r++; f(l, r); } flag = 1; sort(ab.begin(), ab.end()); reverse(ab.begin(), ab.end()); sort(ba.begin(), ba.end()); reverse(ba.begin(), ba.end()); // 长度小的组放后边 // 先考虑离散的 a b mp["a"] -= cod["a"]; mp["b"] -= cod["b"]; if (mp["a"]<0 || mp["b"]<0 || mp["a"]!=mp["b"]) flag = 0; int cnt = mp["a"]; // a+b数目 while (ab.size() && mp["ab"]>=ab.back()) // 优先使用原生ab { mp["ab"] -= ab.back(); ab.pop_back(); } while (ba.size() && mp["ba"]>=ba.back()) // 优先使用原生ba { mp["ba"] -= ba.back(); ba.pop_back(); } if (cnt < ab.size() + ba.size()) // 有ab.size() + ba.size()实在需要离散对 a+b flag = 0; cnt += mp["ab"] + mp["ba"]; cod["tong"] += accumulate(ab.begin(), ab.end(), 0ll) + accumulate(ba.begin(), ba.end(), 0ll); if (cnt != cod["tong"]) flag = 0; cout<<(flag ? "YES" : "NO")<<endl; return; }Bring Balance算法本质思维题目大意给定长度2n的括号序列,其中有n个左括号、n个右括号。玩家希望最后的括号序列合法,可以执行以下操作:选择区间l r,执行s.reverse(l, r)输出最小化的操作次数。思路推演括号序列的合法,这类题目使用前缀和数组来看待是最好的。玩家的目的是使得前缀和数组都>=0。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 793 (Div. 2)
Circular Spanning Tree算法本质思维题目大意n个点顺序围成了一个环,给定长度n的01串s,现在玩家需要连接n-1条边,需要满足:形成连通所有点的树结构所有的边的交点只能在节点上s[i]是01分别表示第i个点的度是偶数、奇数输出连接方案思路推演核心在于奇偶ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; cin>>n>>s; int cnt = count(s.begin(), s.end(), '1'); if (cnt==0 || cnt%2) { cout<<"NO"<<endl; return; } vector<pair<int, int>> ans; int p=s.find_first_of('1'); // 找到一个字符作为起点 vector<int> cod; for (int l=p, r; l<p+n; l=r) { r = l+1; while (s[r%n]=='0') { ans.push_back({(r-1)%n, r%n}); r++; } cod.push_back((r-1)%n); } for (int i=1; i<cod.size(); i++) ans.push_back({cod[0], cod[i]}); cout<<"YES"<<endl; for (auto [u,v]:ans) cout<<u+1<<' '<<v+1<<endl; return; }Unordered Swaps算法本质思维、图论基础题目大意给定长度n排列p[],Alice执行了m次交换操作使得p[]升序(保证m是最小操作次数),每次操作记录交换元素下标。现在将这m次操作乱序后给出,玩家需要恢复其顺序使其合法。(恢复的顺序可以使得p[]升序)思路推演对于排列交换、形式与[1, 2, ... , n]有关的,都可以将其分组。分组的方式:对于任意p来说。a[p]、a[ a[p] ]在同一集合,且可以视作a[p] --> a[ a[p] ]每组会必然形成一个环利用分组进行观察,使其升序的本质是每个元素单独一组。为了尽可能少的交换,我们需要保证每次交换操作都是选择两个同组的元素操作,这样可以将一个组打破成两个组。难点在于,操作是固定的,我们是分配其顺序,需要保证所有的操作都是打破组,或者说所有操作的元素都是同组的。那么,对于一次x y的交换来说,其对于环来说的意义是什么。在组里,元素值和下标随时都在转换,它既是元素值、也是另一元素的下标!模拟:a[]: 2 4 1 5 3 这个数组仅会形成一个环:2 --> 4 --> 5 --> 3 --> 1 如果交换(2, 5)则会变成:2 3 1 5 4 即:2 --> 3 --> 1 和 5 --> 4多次使用可以发现,选择(x, y),则会以x y为起点分裂出两个环。如果有两个(x, y1)和(x, y2),则显然我们需要先使用举例x较远的y,这样至少对于有x的操作来说,其不会犯错。进一步思考可以发现,对于任意两个交换操作,若其在同一环上出现,则其仅有包含、相离这两种情况,不会出现存在部分交集的情况。否则其就不符合使用最小次数使得p[]升序。于是我们就可以随意组合其他的操作顺序。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<int> a(n+5); vector<vector<pair<int, int>>> g(n+5); for (int i=1; i<=n; i++) cin>>a[i]; for (int i=1; i<=m; i++) { int u, v; cin>>u>>v; g[u].push_back({v, i}); g[v].push_back({u, i}); } vector<int> vis(n+5), pos(n+5); // vis[x]记录元素值x是否使用,pos[x]记录元素值x在环的相对位置 vector<vector<int>> g2(m+5); // g2以id1为key值记录边的topo图 vector<int> ru(m+5), ans; // g2图的入度 for (int i=1; i<=n; i++) { int x = a[i]; if (vis[x]) continue; vector<int> v; // v[]用于记录当前环的元素值 set<int> cod; // cod用于维护当前轮次g2图的入度0的id int siz=0; while (vis[x]==0) { vis[x] = 1; pos[x] = siz++; // 每个环的下标 v.push_back(x); x = a[x]; } for (int u:v) // 依次处理环的每个值 { sort(g[u].begin(), g[u].end(), [&](const pair<int,int> &a, const pair<int,int> &b) { // 距离u相对远的放在前 int v1=a.first, v2=b.first; return (pos[v1] - pos[u] + siz) % siz < (pos[v2] - pos[u] + siz) % siz; }); for (int j=1; j<g[u].size(); j++) { int id1=g[u][j-1].second, id2=g[u][j].second; g2[ id1 ].push_back(id2); ru[id2]++; } if (g[u].size()) // 记录可能的入度0的id cod.insert(g[u][0].second); } queue<int> q; for (int id:cod) if (ru[id]==0) q.push(id); while (q.size()) { int u=q.front(); q.pop(); ans.push_back(u); for (int v:g2[u]) if (--ru[v]==0) q.push(v); } } for (int x:ans) cout<<x<<" "; cout<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 155 (Rated for Div. 2)
Chips on the Board算法本质思维题目大意给定2个长度n的数组a[] b[],现在有一个空白的n*n的棋盘,玩家需要放置若干个棋子满足:每个棋格的所处的行或列至少存在一个棋子每个棋子放置有成本:放置在(i, j)位置,需要a[i]+b[j]元输出玩家的最小化成本。思路推演一种朴素的想法就是:以行为单位,每行必须存在一个棋子以列为单位,每列必须存在一个棋子证: 若存在某种方式,第i行不存在棋子、第j列不存在棋子 则(i,j)格子不合法所以,既然每行都需要一个棋子,则a[]数组的贡献就是其元素和,b[]的贡献可以调整最小元素*n。Make it Alternating算法本质思维题目大意给定01串s,希望s变成交错的(不出现连续1或连续0),玩家可以操作:删除某个字符在最少删除次数下,玩家删除的方案数。(注意,删除不同下标的字符视作不同操作,不同删除顺序视作不同操作)思路推演最少删除次数很容易求得。例如100011110删除的次数显然是2+3。核心在于操作数的计算,例如3个0,实际上只能删除2个元素。计算方式:3个0中,C(3, 1)计算留下来的0的情况,另外2个操作放入操作池,4个1也同理。操作池有5个操作,全排列即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; cin>>s; int ans=1, kind=0; for (int l=0, r=0; l<s.length(); l=r) { while (r<s.length() && s[l]==s[r]) r++; kind++; ans = ans * (r-l) % mod; } for (int i=1; i<=s.length()-kind; i++) ans = ans*i%mod; cout<<s.length()-kind<<" "<<ans<<endl; return; }Sum of XOR Functions算法本质思维题目大意给定长度n数组a[],定义:$f(l,r) = a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r]$输出$\sum_{l=1}^n\sum_{r=l}^nf(l,r) * (r-l+1)$思路推演首先想到的就是拆位,拆位后效果会好很多。拆位后题目就变成一个很简单的了,至少思路上没有什么障碍了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> a(n+5); for (int i=1; i<=n; i++) cin>>a[i]; int ans=0; for (int val=1; val<=1e9; val*=2) { // num[0]表示奇数目前能作为左端点的个数,w[0]表示能作所有奇数左端点到目前下标的和 int num[2]={0, 0}, w[2]={0,0}; int res=0, x=0; // x表示当前是奇数点还是偶数点(注意奇偶切换的状态) for (int i=1; i<=n; i++) { num[x]++; w[0] += num[0]; w[1] += num[1]; if (a[i] & val) // 奇偶切换 x ^= 1; res += w[x^1]; // 当前点作为右端点,可以收获w[x^1]的倍率 num[x] %= mod; w[0] %= mod; w[1] %= mod; res %= mod; } ans += res*val; ans %= mod; } cout<<ans<<endl; return; }Interactive Game with Coloring算法本质思维题目大意给定n大小的树,其中1是根节点。玩家需要对树的边染色,然后保证在以下游戏必胜:初始时玩家会被传送至某个未知的非1节点如果玩家目前处于非1节点,可以知道附近任意颜色的边的数目,(玩家看来)相同颜色的边没有区别,然后选择一条边走玩家必须保证每次行动都能缩减与节点1的距离,否则计为失败,当抵达1时成功在保证必胜的前提下,减少使用的颜色种类。玩家需要输出染色方案,同时还需要完成游戏(交互题)。思路推演稍加模拟就发现了一个特别简单的思路:设节点1深度为0,则对任意深度为x的通向父节点的边,模3同余的点染相同颜色。这样的话,每个节点的边至多存在2种颜色——一共三种可能,然后根据情况选择,可以保证自己深度一直减小。那接下来还需要考虑仅用1种颜色和2种颜色的情况了。通过样例可以发现,如果节点最大深度为1,那就可以使用1种颜色即可,那增加深度是否还可以保证仅用一种颜色呢?显然不行,深度>1时一定存在某点有多条边,同种颜色边无区别,玩家无法选择唯一正确的边行动。那接下来就是2种颜色的情况了。当最大深度>2时,能否存在情况仅用2种颜色——显然是可行的。思考,可行动的本质是什么,首先正确的边的颜色只能为1。所以在2种颜色的情况下,边的颜色交替染色,还有一个问题是:某个节点的2种颜色的数目都是1——这需要事先规定。我们称仅有2条边相连的非1节点为斑点,节点1以下的子树是一个整体,这个整体中的斑点如果深度的奇偶不一致,则不可行,反之可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int fu[maxn], c[maxn]; vector<int> g[maxn]; vector<int> ck(int u, int dep) // 检查斑点的奇偶个数 { vector<int> res(2); if (g[u].size()==1) res[dep%2]++; for (int v:g[u]) { vector<int> t=ck(v, dep+1); res[0] += t[0]; res[1] += t[1]; } return res; } void tu(int u, int col, int top) // 染色函数 { if (col>top) col-=top; c[u] = col; for (int v:g[u]) tu(v, col+1, top); } inline void solve() { cin>>n; k = 1; for (int v=2; v<=n; v++) { int u=in(); g[u].push_back(v); fu[v] = u; if (fu[v]!=1) k=2; } if (k==1) // 检查是否可以用1种颜色搞定 { cout<<k<<endl; for (int i=2; i<=n; i++) cout<<1<<" \n"[i==n]; cout.flush(); while (1) { int op=in(); if (op==1) break; int t=in(); cout<<1<<endl; cout.flush(); } return; } for (int u:g[1]) // 检查k=2的情况 { vector<int> x=ck(u, 1); if (x[0]>0 && x[1]>0) k = 3; } if (k==2) { cout<<k<<endl; for (int u:g[1]) // 默认如果1、2颜色都是数目1,选择颜色1 { vector<int> x=ck(u, 1); if (x[0]>0) tu(u, 2, k); else tu(u, 1, k); } for (int i=2; i<=n; i++) cout<<c[i]<<" \n"[i==n]; cout.flush(); while (1) { int op=in(); if (op==1) break; vector<int> num(k+1); cin>>num[1]>>num[2]; cout<<(num[1]==1 ? 1 : 2)<<endl; // 默认如果1、2颜色都是数目1,选择颜色1 cout.flush(); } return; } // k=3的情况 cout<<k<<endl; tu(1, 0, k); for (int i=2; i<=n; i++) cout<<c[i]<<" \n"[i==n]; cout.flush(); while (1) { int op=in(); if (op==1) break; vector<int> num(k+1); cin>>num[1]>>num[2]>>num[3]; int res; if (num[1] + num[2] + num[3] == 1) { if (num[1]==1) res=1; else if (num[2]==1) res=2; else res=3; } else if (num[1]==0) res=2; else if (num[2]==0) res=3; else res=1; cout<<res<<endl; cout.flush(); } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 144 (Div. 2)
Prime Deletion算法本质思维题目大意给定长度9的排列数组,删除其中至多7个元素,剩下的元素按顺序以十进制拼接为一个新数,使得其为素数。输出最后的素数。思路推演考虑是A题,应该具有简单的方法,其中一个想法就是,存在ab是素数且ba是素数,这样可以覆盖所有情况。查阅100以内的素数表,发现79和97都是素数。Two Binary Strings算法本质思维题目大意给定2个长度相等的01字符串a b,保证以0开头、以1结尾,接下来可以执行任意次操作:选择a或b字符串,选择2个相等的字符,将其中间字符都修改为所选字符检查a b最终是否可以相等。思路推演显然的一个找规律的题目,或者叫做洞察其本质。观察样例,可行的情况稍微有点多,反过来观察不可行的情况——一定是存在某个下标p,a[p]和b[p]不同且无法通过操作来改变。但是这样的情况有很多,继续找其特征。因为操作无限制,且可以对两个字符串都使用,所以还有一个特征是:若两者可行,一定可以变为000011111的形式到此为止,只需要检查是否存在某个下标p,能作为01的分界线即可。分界线是否可行,判断十分简单,这里就不说了。Queries for the Array算法本质模拟、思维题目大意初始存在一个空数组,接下来会有3种操作:新添加一个随机数字放置末尾移出末尾的数字检查数组是否单调不减(需要返回0或1,0表示非,1表示满足)现在Alice展示了她玩这个的指令,检查这个指令是否可能存在。思路推演这是一个典型的模拟题,其中0或1会告诉我们信息,重点在于用什么形式将这些信息完全捕获:1的信息数字有序是一个连续的性质,所以仅需要一个下标存储就好了。当有新增元素时,下标不变,当元素减少时,若当前下标元素没了,下标后退一步即可0的信息表示当前数组不有序,即至少存在某个元素不有序,其实也可以这样理解,假如现在有n个数字,被告知不有序,则我们可以假设存在一个p<n,前p个元素是有序的,但是这个p是不定的。通过上面的分析,可以发现的是,对于数组来说,可以分成三段:下标[1, l]的部分,是保证有序的下标[1, r]的部分,是可能有序、可能无序的下标[1, 末尾]的部分,是一定无序的对于每个操作来说,维护l r值即可,若其有冲突,则不可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { string s; cin>>s; flag = 1; int siz=0, l=0, r=0; // siz表示当前数组长度,l r同上含义 for (char c:s) { if (c=='+') { siz++; if (r==siz-1) // 新增元素时,l不需要移动,r需要判断是否移动 r=siz; } else if (c=='-') // 删除元素时,保证l r不越界 { siz--; l = min(l, siz); r = min(r, siz); } else if (c=='1') { if (siz > r) // siz>r表示一定是无序的,起了冲突,不可行 { flag=0; break; } l = r = siz; // 重新赋值l r } else if (c=='0') { if (siz<2 || siz==l) // 一定有序的条件 { flag=0; break; } if (r==siz) r--; } } cout<<(flag ? "YES" : "NO")<<endl; return; }Sorting By Multiplication算法本质思维题目大意给定长度n的正整数数组,现在可以若干次执行操作:选择l r x,使得a[l~r]都乘上x(x可以为任意值,包括零和负数)使得操作后数组严格递增,输出最小化的操作次数。思路推演还是老样子,分析一下操作的本质:如果x>0的话,因为只关心元素的相对大小,所以这个操作其实可以看作加法。那这个就非常简单了,只需要检查相邻元素之间非递增关系的个数即可。但是这里存在x<=0的情况,继续思考。稍加模拟可以发现:因为最后是升序情况,所以最终必然是前一部分为负数,后一部分为正数的情况。而初始全正,前一部分的负数用一次操作统一处理,而且具体哪个负值没有意义,视作都用-1即可。一个朴素的想法是,那检查正负分界线即可。前面负数部分,操作数是:相邻元素之间非递减关系的个数+1后面整数部分,操作数是:相邻元素之间非递增关系的个数这里只需要用前缀和处理一下即可,注意考虑全正全负的情况。这里还有一个小坑导致赛时wa了一发,就是假如前负数部分是[1, p],正数部分是[p+1, n],p和p+1之间的关系是不用考虑的,其必然严格递增。ac核心代码代码会稍微奇怪一点,构建了a[],长度n-1,表示n个元素之间的关系:1表示严格大于0表示等于-1表示严格小于头文件、宏定义、快读模板、常见变量、常见变量等略。 { cin>>n; n--; vector<int> a(n+5), pre0(n+5), pre1(n+5); int last=in(); for (int i=1; i<=n; i++) { int now=in(); if (now > last) a[i] = 1; else if (now < last) a[i] = -1; last = now; } for (int i=1; i<=n; i++) { pre0[i] = pre0[i-1]; // pre0[i]=x表示前i个关系中,有x个关系都是等于或大于 pre1[i] = pre1[i-1]; // 类似pre0[] if (a[i]==0 || a[i]==1) pre0[i]++; if (a[i]==0 || a[i]==-1) pre1[i]++; } int ans = pre1[n]; // 考虑全正的情况 pre1[n+1] = pre1[n]; // 可能会越界,特殊处理 for (int i=1; i<=n; i++) { int res = pre0[i] + pre1[n] - pre1[i+1] + 1; // 考虑前i个关系为负数 ans = min(ans, res); } cout<<ans<<endl; return; }Non-Intersecting Subpermutations算法本质思维、dp题目大意给定n k,表示合法合规数组长度n,元素范围1~k。定义数组的美丽值:将其任意划分,若某个部分为长度k的排列则贡献值+1,划分方案所能达到的最大贡献值输出所有合法合规数组的美丽值之和。k n <= 4e3思路推演-初步思路这种题通常有2个思考方向:计算美丽值为x的合法数组个数,然后最后统一乘法求和计算某个部分对整体的贡献值,统一相加但是不管选择哪种方法,其最大的问题在于,用贪心思路去计算,会计算重复——这表明只能用dp去解决,通过巧妙的设计,解决重复计算的问题。这里为了避免重复计算,设定一个规则,比如数组[3, 2, 1, 2, 3]对于k=3的情况来说,这个数组的美丽值为1,但是有2种分割方式,根据贪心可知,总是用靠前的分割方式是最优解,所以视作[3, 2, 1]和[2, 3],为了方便叙述,我们称这个下标3的位置为奇点。一个朴素的想法是,通过制造方向性来避免重复计算:假设f[i]表示填写[1~i]位且i是奇点的方案数。(注意,这里的每个方案数,其最后k位可以视作已经固定了的)这样答案就可以表示为:$\sum_{i=1}^nf(i)*k^{n-i}$转移方程的话,可以通过枚举上一个奇点位置来转移。接下来研究两个奇点如何转移。设靠前奇点位置是j,靠后奇点位置是i,首先因为题目规定,所以j <= i-k。其次通过模拟可以发现,如果i是第一个奇点,情况会比较特殊,要特殊处理,这里先讨论i非第一个奇点的情况。讨论1——i不是第一个奇点的情况转移方程用文字描述是:(暂时没有考虑i是第一个奇点的情况)$f(i) = \sum_{j=k}^{i-k}f(j)*(已知ij是奇点、且ij之间不存在奇点、且已知j为奇点的排列方式的方案数)$为了解决这个问题,通过模拟发现,贪心比较难,但是可以用dp来解决。所以构建式子g[x]表示:存在某个下标p是奇点、已知p奇点的排列方式、p+x是下一个奇点(中间无其他奇点)的方案数。这样的话可以优化f[]的求解为:$f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j)$接着完善g[]的维护方程,这里引入g[]的前缀和函数pre[]方便描述:i<k已知了p奇点的排列方式,要使得p+i为奇点,则所选的元素种类的固定的,可以改变的是其排列方式,再减去重复的方案即可(中间有奇点的情况)$g(i) = i!-pre(i-1)$i>=k则后k个元素一定是排列,还剩余的i-k个元素随意取,减去重复方案即可(中间奇点情况)$g(i) = k!*k^{i-k}-pre(i-1)$讨论2——i是第一个奇点的情况前面的讨论给了我们很大的启发,i是第一个奇点的情况显然也可以使用dp来维护。设h[i]表示i是第一个奇点的方案数。思考出转移方程:i<kh[i]=0i>=k$h(i) = k!*k^{i-k}-\sum_{j=1}^{i-1}h(j)*g(i-j)$显然这里也可以用前缀和辅助优化汇总当预处理好了g[]和h[]就可以表示f[]:$f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j) + h(i)$$ans = \sum_{i=1}^nf(i)*k^{n-i}$第一个式子,前部分表示i是非第一个奇点的方案数,后部分表示i是第一个奇点的方案数。注意f[<k]显然为0ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
1
...
5
6
7
...
18