首页
关于
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
CodeTON Round 4 (Div. 1 + Div. 2)
A.Beautiful Sequence算法本质思维题目大意对于长度n的数组a[],定义其美丽的:至少存在一个a[i]=i定义其帅气的:其子序列至少一个是美丽的现在检查长度为n的a[]是否帅气。思路推演题目转化为,我们找到一个子序列,其中的一个元素等于其下标,这个元素称为奇点。假设a[1]为奇点,则必须保证a[1]=1,若a[2]为奇点,则必须保证a[2]<=2。随后验证a[i]<=n时可以称为奇点。检测一遍即可。B.Candies算法本质思维题目大意初始时有一颗糖,可以进行以下两种操作(操作数之和最多40):糖数 = 原糖数*2 - 1糖数 = 原糖数*2 + 1最终需要得到n颗糖,复述操作步骤。(不能输出-1)思路推演显然,偶数是不可行的。倒推可以发现,设当前有y颗糖,操作后为x颗糖。若已知y,想保证x为奇数,则只有其中一个操作可以做到。选择可行的操作,然后循环这个逻辑即可。C.Make It Permutation算法本质思维题目大意给定长度n的a[],进行以下操作,使a[]变为非空排列(下标1开始):c元:删除一个元素d元:在任意地方插入一个任意元素思路推演有一种方法肯定可行:删除所有元素再加个1。不过这个结论用处有限,继续思考。既然最后是排列,则重复的元素一定需要删除。对于a[],先排序再去重。设a[i]为最后排列的最大值。遍历所有情况的成本,选最小即可。(包括全删加1的情况)D.Climbing the Tree算法本质思维、模拟题目大意对于一只蜗牛和树,树高h,蜗牛白天爬a,晚上下降b。现在给你一颗高度暂时不知的树,接下来有q只蜗牛会来和你交流,有以下两种交流:爬过树的蜗牛:会告诉你关于它的a b数值,和其所用时间d。如果你目前收集到的情况能证明它说谎,不用理会它;否则当作真实信息接受。没爬过树的蜗牛:告诉你关于它的a b数值,希望你计算出一个切确的爬树时间。若无法切确到多少天,则输出-1。思路推演我们设定树可能最大高度、可能最小高度。爬过树的蜗牛:通过a b d计算出其爬树的最大可能高度、最小可能高度,与原范围取交集。(若无交集说明其说谎)没爬过树的蜗牛:用当前树的最大可能高度、最小可能高度与a b计算出最长、最短的爬树时间,若一致则输出,否则-1。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int f(int a, int b, int h) // 给定属性,看需要爬多少天 { if (a>=h) return 1; int res=1; h -= a; res += (h+a-b-1)/(a-b); return res; } inline void solve() { //init int q; cin>>q; int mm=1e18, mi=-1e18; while (q--) { int op, a, b, d; cin>>op; if (op==1) // 爬过树的蜗牛 { cin>>a>>b>>d; int da = (a-b)*(d-1) + a; // 当前蜗牛爬树的最大可能高度 int xiao = (a-b)*(d-2) + a + 1; // 最小可能高度 if (d==1) // 如果d==1的话,xiao需要特殊处理一下 xiao = 1; if (da>=mi && xiao<=mm) // 与原数据有交集,说的是大实话 { mi = max(mi, xiao); // 更新 mm = min(mm, da); cout<<1<<" "; } else // 在说谎 cout<<0<<" "; } else if (op==2) // 没爬树的蜗牛 { cin>>a>>b; int d1 = f(a, b, mm); // 最长时间 int d2 = f(a, b, mi); // 最短时间 if (d1==d2) cout<<d1<<" "; else cout<<-1<<" "; } } cout<<endl; return; }E.Monsters算法本质思维题目大意给定一个无向图,每个节点存在一个防御力为a[i]的怪物(需要主角的攻击力>=a[i]才能击杀),只有当前节点的怪物被消灭了才可以随意通行。主角初始攻击力为0,每击杀一个怪物攻击力+1。主角可以选择某个节点开始,问是否可以击杀所有的怪物。思路推演显然,起点只能是a[i]=0的点。对于一个起点来说,判断是否可行相对简单,类似prime最小生成树的模型即可。还需要解决的一个问题是:多个起点怎么降低复杂度:当我们跑某个起点时,遇到其他起点可以顺路标记了(不用重复跑了),这个优化使得最多跑2n个节点。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; vector<int> g[maxn]; set<int> v0_used; // 记录已经使用过的0值下标 struct node { int val, pos; // bool operator < (const node &b) const { return val > b.val; } }; int f(int s) { // v0_used.insert(s); vector<bool> vis(n+5, 0); priority_queue<node> q; int power=0; q.push({a[s], s}); while (q.size()) { if (power < q.top().val) return -1; node u=q.top(); q.pop(); if (vis[u.pos]==1) continue; // 检测是否用过了 vis[u.pos] = 1; if (u.val==0) v0_used.insert(u.pos); // 优化复杂度 power++; for (int nxt:g[u.pos]) { if (vis[nxt]==0) q.push({a[nxt], nxt}); } } return power==n; } void clear() { for (int i=1; i<=n; i++) g[i].clear(); v0_used.clear(); } inline void solve() { //init cin>>n>>m; clear(); vector<int> v0; // 记录0值下标 for (int i=1; i<=n; i++) { cin>>a[i]; if (a[i]==0) v0.push_back(i); } while (m--) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } //cal flag=0; for (int s:v0) { if (v0_used.count(s)) continue; // 已经遍历过了 if (f(s)==1) { flag=1; break; } } // out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 882 (Div. 2)
A.The Man who became a God算法本质思维题目大意给定a[]信息,在不改变相对顺序条件下,把a[]分成k个组,每个组的成本为:(总成本为每组成本之和)相邻2个数绝对值差之和输出最小化的所有组成本和。思路推演分组的实际意义是,切断了a[i]和a[i+1]之间的连续,使得成本下降了abs(a[i]-a[i+1])。所以记录n-1个绝对值差,减去前k-1个值,即得到剩余的最小化组成本和。B.Hamon Odyssey算法本质思维题目大意给定a[]信息,在不改变相对顺序条件下,把a[]分成若干组,每组的成本为:(总成本为每组成本之和)a[l] & a[l+1] & ... & a[r]输出保证最后成本最小能分的最大组数。思路推演首先可知,若a[1] & a[2] & .. a[n]不为0,则一定不可分割,因为必然会导致值增加。若其全部与运算后为0,则需要保证分割前后都是0才行——即a[l~r]中,每个二进制位都存在某个数此位0。我们选择从左往右遍历,一旦满足这个条件,则记录重置条件。(用贪心思想看,显然正确)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn][40]; // 数组、数组二进制 inline void solve() { cin>>n; for (int i=1; i<=n; i++) { cin>>a[i]; for (int j=0, x=a[i]; j<=30; j++, x/=2) b[i][j] = x%2; } int ans=0; set<int> st; for (int i=1; i<=n; i++) { for (int j=0; j<=30; j++) { if (b[i][j]==0) st.insert(j); } if (st.size()==31) // 重置 { ans++; st.clear(); } } ans = max(ans, 1ll); // 担心整体与运算>0导致ans=0 cout<<ans<<endl; return; }C.Vampiric Powers, anyone?算法本质思维、数据结构题目大意给定长度n的a[]信息,现在可以对其进行若干次操作:选择l使得x = a[l] ^ a[l+1] ^ ... a[n]将x放入a[]末尾,使得其长度+1输出最大化操作后a[]的最大值。n <= 1e5 a[i] <= 2^8思路推演首先抽象操作,设前两次操作分别选择了l1 l2,可以发现,a[n+1]的范围是l1~n,a[n+2]的范围是l1~l2(或l2~l1)。以此类推,a[n+1]和a[n+2]可以看作一起,范围是l2~n。所以后面制造出来的数的实质是:区间异或和。其题目的本质是最大区间异或和。但是数据范围给的耐人寻味,显然存在某种暴力之法。思路推演 - 暴力最基本的暴力是O(n^2^)的,即每次遍历时确定r,然后遍历l去获取不同区间的值。但是由于其值上限只有256,所以其至多有256种情况,可以用256*n的复杂度搞定。思路推演 -ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; set<int> st; int res=0, ans=0; st.insert(0); // 0下标的异或值 for (int i=1; i<=n; i++) { res ^= a[i]; // res表示[1~i]的异或和 for (int x:st) // 遍历前面区间的可能性——至多256种情况 ans = max(ans, res^x); st.insert(res); } cout<<ans<<endl; return; }D.Professor Higashikata算法本质思维题目大意给定01字符串s,指定了m个区间,接下来会有q次询问,每次询问会翻转某位字符信息,玩家可以执行若干次操作:(并不赋值给下一次s,假设性操作)交换某2个字符位置操作后需要保证:根据指定的m个区间截取s生成子串t(1) t(2) ... t(m),再顺序连接组成新01子串t,使得t的字典序尽可能大输出每次询问的最小操作数。思路推演既然是使得t的字典序大,观察给出m个区间,可以对s的下标进行权重的排序,即先给出的下标权重更大。这里就涉及一个多区间修改的问题,设立R[]来表示右侧未被权重赋值的下标,配合类似并查集find(),能够较好应对。能被赋予权重的下标数目可能达不到n,这里设为len表示,用num1表示当前s中1的数目,会有2种情况:num1 >= len则赋权下标可以全修改为1,计算赋权下标中为0的数目即可。num1 < len记录赋权下标中前s前num1下标为0的数目即可。可以看到的是,这部分是单点修改,区间查询,暴力一点的话,用树状数组可以直接搞定,复杂度为log。当然,这里的区间查询之间的变化至多为1,所以也可以通过一些技巧避开树状数组,但是想要降低复杂度还是比较难。(也能降低,但是写起来比较麻烦)这里选择用树状数组,检查一下,需要原下标到新下标的映射。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 差分树状数组忽略 int R[maxn], vis[maxn]; // R[i]需要赋值为i+1 int find(int x) // 找到右边(含自己)第一个未被遍历的 { if (vis[x]==0) return x; return R[x] = find(R[x]); } inline void solve() { int q, num1=0, len=0; // num1表示s中1的数目,len表示赋权的下标数目 cin>>n>>m>>q>>s; s = " " + s; for (int i=1; i<=n; i++) { R[i] = i+1; num1 += s[i]=='1'; } map<int, int> mp; // 旧id-->新id(新id越小,说明权重越高) while (m--) { int l, r; cin>>l>>r; for (int p=find(l); p<=r; p=find(p)) { vis[p] = 1; mp[p] = ++len; // 更新mp add(len, len, s[p]=='1'); // 树状数组依照新id建立,因为len<=n,所以长度给n没问题 } } while (q--) { int x, val; cin>>x; if (s[x]=='1') s[x]='0', val=-1; else s[x]='1', val=1; num1 += val; if (mp.count(x)) // 说明有对应的新id add(mp[x], mp[x], val); int r=min(len, num1); // 检查树的范围[1~r]中0的个数 int ans = r - getsum(1, r); cout<<ans<<endl; } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 F.The Boss's Identity算法本质思维题目大意给定无限长数组a[]前n个元素信息,其后面元素的大小定义:a[i] = a[i-n] | a[i-n+1](i>n)接下来有q次询问,每次询问给出x,找到大于x的a[]种的最小下标。(无则返回-1)前缀知识以或运算为例,长度n、大小范围0~2^m-1的a[]的区间异或和至多存在n*m个值。先确定r,遍历l,这是个以r为右端点后缀异或和,显然至多有m个不同值。 存在n个这样的r,至多为n*m个值。(实际严格小于这个值)不仅或运算,与运算(看作0的或运算)、gcd(看作未取素数的或运算)同理。思路推演手动模拟n=5情况:(a1隐藏)长度a2结尾a3结尾a4结尾a5结尾1a2a3a4a52a1~a2a2~a3a3~a4a4~a53a5~a2a1~a3a2~a4a3~a54a4~a2a5~a3a1~a4a2~a55a3~a2(全部)a4~a3(全部)a5~a4(全部)a1~a5(全部)可以发现的是,后面的元素实际上是前面元素的区间或结果,所以从区间的角度思考。结合前缀知识,一个显然的想法是,将这所有区间或至多nlog(1e9)个值取出来,按编号排序,再删去某些点保证其严格递增(删除的点总是存在更优解替代)。那应该如何取出来呢,思考单个元素的贡献,考虑这是位运算,思考单个元素的单个二进制的贡献。我们假设确立a[i]为左端点,其二进制第一位是1,r不断向右延申(注意这里相当于是环形的),首先当r=l时,其对自身的[l,l]区间二进制第一位做出了贡献,接着当r>l时,其对[l, r]二进制第一位做出贡献。当然,前提是[l+1, r]的所有数都没有对其二进制第一位做出贡献。如果发现了在此之前有其他元素先于其做出贡献了,则停止(因为后面做出贡献的时间都是更晚的,存在更优解替代)。在记录这些贡献时,以r为key值来记录,这样就可以得到了r --> 每个二进制位为1的时间点,大概是这样的数据:tim[r][j]=len所有右端点为r的区间,第j位二进制数为1的贡献,最早记录来自于长度为len时(即由r-len+1这个左端点贡献)。我们可以据此每个右端点写出31个{出现id + 异或和值},共计n * 31个值,排升序,然后遍历删去某些点保证id和值都严格升序,将值作为检索,之后对q次询问二分查找。注意看模拟的图,a1结尾的只有其自身一个,写下标的时候请注意ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn][40]; // b[i][j]:a[i]的第j为二进制数 int tim[maxn][40]; // tim[r][j]=len:以r为右端点的区间,第j位二进制为1的首先贡献是r-len+1的左端点 int er[40]; // 记录二进制值,方便用 inline void solve() { cin>>n>>m; for (int i=1; i<=n; i++) { int x; cin>>x; a[i] = x; for (int j=0; j<=30; j++) { b[i][j] = x%2; // 二进制位记录 x /= 2; tim[i][j] = 0; // 顺便清洗一下tim[][] } } for (int l=1; l<=n; l++) { for (int j=0; j<=30; j++) { if (b[l][j]==0) continue; int len=1; tim[l][j] = len; // 自己对自己的贡献 for (int r=l%n+1; r!=l; r=r%n+1) // 数学推论,这里不会T { // 这里注意别让r>n了 if (b[r][j]==1) break; // 之后的地方,用r做左端点是更优解,所以break tim[r][j] = ++len; } } } vector<pair<int, int>> v1, v2; // {id, 值} v1记录n*m个,只能保证id递增,v2清洗v1,保证id、值都递增 v1.push_back({1, a[1]}); // a[1]特殊处理 for (int i=2; i<=n; i++) { map<int, vector<int>> cod; // cod[len]={a, b, c}:r-len+1的左端点首先贡献了第a b c二进制位的值 for (int j=0; j<=30; j++) { if (tim[i][j]==0) continue; // 说明第j位二进制都没有,忽略 cod[tim[i][j]].push_back(j); } int val=0; for (auto it:cod) { for (int x:it.second) // 遍历这些二进制位,把值加入val val += er[x]; int len=it.first, idx=(len-1)*(n-1)+i; // 计算id v1.push_back({idx, val}); } } sort(v1.begin(), v1.end()); // 以idx排序 // 清洗v1,保证id、值都递增,放置v2 for (auto [idx, val]:v1) { if (v2.size()==0 || val>v2.back().second) v2.push_back({idx, val}); } // v2放到mp中,以值为key值方便二分查找 map<int, int> mp; for (auto [idx, val]:v2) mp[val] = idx; // 正式开始询问 while (m--) { int x; cin>>x; auto it = mp.upper_bound(x); // 第一个>x的下标 int ans=-1; if (it!=mp.end()) // 说明没有比x大的值,输出最后一个 ans = it->second; cout<<ans<<endl; } return; } inline void solve_init() { er[0] = 1; for (int i=1; i<=30; i++) er[i] = er[i-1]*2; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 870 (Div. 2)
A.Trust Nobody算法本质思维题目大意给定长n的数组a[],其a[x]表示第x个人说:这里有至少a[x]个说谎者。一共n个人,每个人只有说谎者和非说谎者身份。若存在满足条件的情况,输出说谎者数目反之输出-1思路推演很显然,我们只需要暴力假设说谎者数目,然后检查当前假设的数目是否符合条件(通过前缀和、桶排序、sort处理等等其中一种方法,可以使得单次查询复杂度O(1)),所以整体是O(n)的复杂度。B.Lunatic Never Content算法本质思维题目大意给定长度n的数组a[],对齐进行一次以下操作:选择整数x,使得a[]中所有元素都对x取余保证最后a[]成为一个回文数组,输出最大化x。(若x无限大输出0)思路推演最后的目的是让a[]形成回文,则将a[]的元素一对一对拿出来,有n/2对:现在目的是找到一个x,使得这些对元素对x同余。这一步,更换题意,进一步抽象题目的意思,找到算法本质两数对x同余,很快可以写成两数之差对x取余为0。显然,这里有n/2个条件,要使得x尽可能大,我们取差的最大公因数即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; int ans=0; for (int l=1, r=n; l<=r; l++, r--) ans = gcd(ans, abs(a[l]-a[r])); // gcd对于0的一些特性 cout<<ans<<endl; return; }C.Dreaming of Freedom算法本质思维题目大意给定n m,现在有n个人,m个选项。会经历若干次投票,直到选项个数为1,规则如下:每个投票某个选项票数最多的选项保留,其余丢弃询问,是否存在一直投票的可能。思路推演”可能“一词,表示我们的思考方向应该是尽可能让人们平票,贴近无限投票情况。显然当选项>=人数时,肯定是存在无限情况——因为每个人可以分别投票给某个选项。既然如此,进一步思考:两人投一个选项、三人投一个选项……然后会发现,这于因子有关。当选项数>=人数的某个非1因数时,就可以一直保留某几个选项。D.Running Miles算法本质思维题目大意给定长度n的数组b[]。有n种草药,每种草药的价值为b[],现在小明可以选择一对l r,带走下标属于[l, r]的三种草药,同时消耗r-l的价值。输出最大化带走草药的价值。n <= 1e5思路推演观察题目:n为1e5范围,显然此题需要信息复用——贪心、dp、二分等等同时这个“三种”也让人心生疑惑:为什么刚好是三种,不是两种,不是四种价值的消耗,与范围线性相关(可以联想类似的题目解法)这些都是题目的疑点,在不能看题就想到思路的时候,从疑点入手。为了快速解题,先尝试了从n范围入手:但是思路寥寥,暂无解法。随后选择从“三种”疑点切入:“一种”,显然可解。“两种”,我们可以在确定某个值后,贪心计算出另外一个值的信息。显然,想到了“两种”的解法,就知道了“三种”的解法:我们假设第二个元素下标为x,贪心计算出左右边元素价值,加上即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], pre[maxn], suf[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; for (int i=1; i<=n; i++) { pre[i] = a[i]+i; // 这个值设计的很巧,十分方便后面的r-l代价计算 suf[i] = a[i]-i; } //cal pre[0] = pre[n+1] = suf[0] = suf[n+1] = -1e18; // 注意这里是负数,因为pre和suf可能是负数,最大-n左右 for (int i=1; i<=n; i++) pre[i] = max(pre[i], pre[i-1]); for (int i=n; i>=1; i--) suf[i] = max(suf[i], suf[i+1]); int ans = 0; for (int i=2; i<=n-1; i++) ans = max(ans, pre[i-1]+suf[i+1]+a[i]); cout<<ans<<endl; return; }E.Walk the Runway算法本质思维、bitset题目大意有n个模特,每个模特有自己的出场费a[]。(走m场秀的出场费)有m场秀,每场秀的每个模特的评分为b[][]。对于每场秀,有以下规定:所有秀出现的模特集合相等所有秀模特的出场顺序相同所有秀出场的模特所得评分必须严格单增输出最大化的模特出场费之和。思路推演所有秀中,模特出场集合、顺序都是一致的,所以我们可以把每个模特看成一个node,第i场秀的评分为这个node的第i个属性。(抽象题意)在编排模特出场顺序时,发现模特之间有大小关系(大于、小于、不相等三种关系),且这种关系具备一定传递性。这导致其n个node会组合成一个DAG(无环有向图)最后要最大化的出场费,实际是找一条路径的最大和,显然可以在建图后使用dp搞定。目前的核心问题在于建图(二维直达图)的朴素做法是n^2^m——每2个node之间的关系需要通过m个属性来判断,即使其有传递性,但是传递性并无法降低如此大的复杂度。当时的希望是从评分<=n这点入手的,但是思路寥寥。思路推演 - 正解正解做法是:利用bitset加速处理。因为最终要建的图,可以用临边矩阵表示,用1表示可达,用0表示不可达。通过调整代码,使代码符合bitset的处理方式,从而使得复杂度降低为n^2^m/w(这里w通常为32或64)。ac核心代码因为后面缺乏思维性理解,所以使用别人代码,添加自己注释作为代码。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>m>>n; vector<vector<int>> a(n, vector<int>(m+1)); rep(i,0,n-1) cin >> a[i][m]; // 价格放入a中,方便一会排序带着走 for (int i=0; i<m; i++) for (int j=0; j<n; j++) cin>>a[j][i]; // 评分表:[模特][走秀] sort(a.begin(), a.end()); // 评分表根据模特的第一场秀评分重新排序(偏序),方便后面计算 //cal vector<bitset<maxn>> lower(n); for (int i=0; i<n; i++) lower[i].set(); // 全部设置为1 vector<int> inds(n); iota(inds.begin(), inds.end(), 0); // inds[i]=i for (int i=0; i<m; i++) { sort(inds.begin(), inds.end(), [&] (int x, int y){ return a[x][i] < a[y][i]; }); // inds表示第i场秀评分从小到大的模特编号 bitset<maxn> cur=0; // cur[i]=1表示模特i在第i场秀的评分比当前模特小 int p=0; for (int j=0; j<n; j++) { while (a[inds[p]][i] < a[inds[j]][i]) // 避免相等但是仍然不可达的情况 cur.set(inds[p++], 1); lower[inds[j]] &= cur; // 利用bitset加速 } } vector<long long> dp(n); // dp[i]表示走到i点所获得的最大值 for (int i = 0; i < n; i++) { dp[i] = a[i][m]; // 初始赋值 for (int j = 0; j < i; j++) { if (lower[i][j]) // 可达 dp[i] = max(dp[i], dp[j]+a[i][m]); // 更新 } } cout << *max_element(dp.begin(), dp.end()) << '\n'; // 输出最大值 return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 866 (Div. 2)
A.Yura's New Name算法本质思维、读题题目大意给定一串由^和_组成的字符串,现在要求你向其中添加字符,使其合法。合法字符串的定义:对于任意字符,其可以和相邻的若干个字符组成^_^或^^字符串输出最小化添加字符数。思路推演分类讨论,文字详述略微复杂。B.JoJo's Incredible Adventures算法本质思维题目大意给定长度n的01字符串s,复制n个s分别称作s[1]、 s[2]、...、s[n],组成一个n*n的01矩阵。随后将s[i]字符循环左移i位。对变化后的01矩阵,输出其中最大全1矩形面积。n <= 2e5思路推演稍加模拟可以发现,1的出现都是成片的,其源头是s中连续的1。若s全为1,显然面积为n*n否则:对于s连续的x个1,一定会形成一个倾斜角为45度的x*x的平行四边形。其中可以选中的矩形,长边之和固定为x+1,所以最大面积为(x+1)/2 * (x-(x+1)/2)C.Constructive Problem算法本质思维题目大意给定长度n的数组a[],现在选择一对l r,使a[l~r]元素变成同样的任意正整数。能否使得改变后的a[]的MEX值恰好为改变前a[]的MEX值+1。输出Yes或No。思路推演设改变前的MEX值为x。我们想要使得改变后MEX为x+1,需要3个条件:创造出x消灭x+1保留0~x-1为了满足创造x的条件,则我们这个任意正整数的值,必须是x。为了满足消灭x+1的条件,则x+1出现的区间,我们一定需要选中。至于能不能保留0~x-1,尽可能使选中的区间较小即可。当然,这里需要讨论一个额外的可能:不存在x+1,那只需要看改变前的MEX是否为n值即可。D.The Butcher算法本质思维、模拟题目大意原有数据不详的大矩形a*b,现在对其切割n-1刀(横切or竖切),分割成n个矩形,切割规则如下:每次切割后的矩形,其中一块放入盒子里,另外一块留在案板上继续等待切割矩形无法旋转现给出这n个打乱顺序后的矩形,请计算其可能的初始形状。思路推演现在,这种题要么从最先切的块的矩形开始猜,要么从最后切的块的开始猜。最后切的块不太好找,最先切的块可以把范围缩小,分别是长最长,宽最长。因为其独特的切割规则,所以初始矩形必然存在长or宽可以被找到。所以我们可以假设其第一次是横切、第一次是竖切。然后依次用长宽还原其切割方式,若能还原则说明可行,不能说明不可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int l[maxn], r[maxn]; map<int, vector<int>> a2b, b2a; bool vis[maxn]; bool qie(int &a, int &b, char c) { bool f=0; if (c=='a') { for (int idx:b2a[b]) { if (vis[idx]) continue; a -= l[idx]; f = 1; vis[idx] = 1; } } else if (c=='b') { for (int idx:a2b[a]) { if (vis[idx]) continue; b -= r[idx]; f = 1; vis[idx] = 1; } } return f; } // 还原,返回1表示可行,返回0表示不可行 bool dfs(int a, int b, int ct=0) { if (a==0 || b==0) return 1; if (ct%2) { if (!qie(a, b, 'a')) return 0; } else { if (!qie(a, b, 'b')) return 0; } return dfs(a, b, ct+1); } inline void solve() { //init cin>>n; int ma=0, mb=0, sum=0; a2b.clear(), b2a.clear(); for (int i=1; i<=n; i++) { cin>>l[i]>>r[i]; sum += l[i]*r[i]; // 拿到总面积 ma=max(ma, l[i]); mb=max(mb, r[i]); a2b[l[i]].push_back(i); b2a[r[i]].push_back(i); } set<pair<int, int> > ans; if (sum%ma==0) // 初步判断是否第一次为竖切 { rep(i,1,n) vis[i]=0; if (dfs(ma, sum/ma, 0)) // 进一步判断,第一次竖切能否切割成功 ans.insert({ma, sum/ma}); // 可行加入答案 } if (sum%mb==0) { rep(i,1,n) vis[i]=0; if (dfs(sum/mb, mb, 1)) ans.insert({sum/mb, mb}); } cout<<ans.size()<<endl; for (auto i:ans) cout<<i.first<<" "<<i.second<<endl; return; }
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 865 (Div. 2)
A.Ian Visits Mary算法本质思维题目大意已知a b从(0,0)最多跳2次到(a,b)点,要求每次跳跃的dx dy互质。思路推演1与所有数互质,只需要先填x轴再跳y轴就可以了。B.Grid Reconstruction算法本质思维题目大意给定偶数n,在2*n的地图上,将1~2n的数字填入其中。当走到x+y为偶数的格子会使得成本加上当前格子的数字,反之减去。现在小明要从左上角走到右下角,他会选择成本最小的路。现在需要你构造这个地图,最大化小明的行走成本。思路推演已知有n个格子是增加成本的,有n个格子是减少成本的。自然用大数填充前面的,小数填充后面的。另外起点和终点是必然经过的,其他点都是可能不经过的,所以起点终点需要填2n 2n-1。接下来探讨中间格子填什么,当小明已知地图要求最少成本路径时,是用的dp来求。而我们已经确定格子的数字大小,只能做调换的时候:让每个格子从上面2种可能状态转移过来的成本尽可能相近是显然的正解。观察一下样例蕴含的规律。C.Ian and Array Sorting算法本质思维题目大意给定长度n的数组a[],你可以进行任意次以下操作,目标是使得a[]非递减排序,检查是否可能:选择a[i] a[i+1]都+1或者-1思路推演稍加模拟扩展,可以发现,对任意差距为偶数的元素,可以做到+1 -1,即元素值的转移。这是一个很好的结论,这意味我们可以把元素分为奇数下标、偶数下标两组。这两组元素内部可以转移值,所以必然可以构造非递减。那现在的情况就是,需要构造两组元素之间的非递减。若元素个数为偶数可行的结果显然是:偶数下标组和 >= 奇数下标组和若元素个数为奇数则奇数组多了一个元素,可操作性就大很多了。模拟一下,必然成立。D.Sum Graph算法本质思维(交互题)题目大意存在一个长度n且未知的排列、一个有n个节点的空图,现在你可以进行至多2n次以下操作之一,最后需要猜测排列2次:建图:输入x,图中编号之和为x的节点连接一条边查询:输入i j,返回图中编号为p[i] p[j]的最短距离(无法抵达输出-1)最后可以猜测排列2次,其中一次正确即为正解。思路推演先拿到这个题还是有点蒙。仔细查看查询操作,其依赖于建立好的图,所以建立好图非常关键。模拟一下建图,显然第一次操作的最有解为x=n+1,每个点都是平等的,这样可以多建边。已当前图为例,我们可以用n-1次操作得到相连的2个点,显然信息不够的。最大的一个问题是,没有利用好距离,只利用了是否可达。于是我们再次尝试,x=n,将所有图连接成一条线。这次很好解决了问题,如果我们随机选择一点让其查询其他所有点,而且对于同一点来说:相同距离表示的点至多有2个点。但是正是这不确定性,让我们没办法用剩下的n-1次查询搞定。为了解决这种不确定性,查询点在线边缘即可解决,我们可以找到距离随机点最远的点,其一定是边缘点。然后通过边缘点,查询其他所有点。但是边缘点本身在左在右不确定后,对应了题目最后允许猜测2次。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], ans1[maxn], ans2[maxn]; int dis[maxn]; inline void solve() { //init int x; cin>>n; int l=1, r=n; cout<<"+ "<<1+n<<endl; // 建图 cin>>x; cout<<"+ "<<2+n<<endl; cin>>x; for (int i=1; i<=n; i++) // 记录建图之后的顺序、节点值 { if (i%2) a[i] = l++; else a[i] = r--; } for (int i=2; i<=n; i++) // 找个随机点p[1],询问与其他点的距离 { cout<<"? 1 "<<i<<endl; cin>>dis[i]; } int s=2; // s为边缘点 for (int i=2; i<=n; i++) // 距离最远的肯定是边缘点 if (dis[i] > dis[s]) s = i; //cal ans1[s] = a[1]; // 可能是左边缘 ans2[s] = a[n]; // 可能是右边缘 for (int i=1; i<=n; i++) { int w; if (i==s) continue; // 自己和自己不需要询问 else { cout<<"? "<<s<<" "<<i<<endl; // 询问距离,通过距离推断 cin>>w; } ans1[i] = a[1+w]; ans2[i] = a[n-w]; } cout<<"! "; // 猜测答案 for (int i=1; i<=n; i++) cout<<ans1[i]<<" "; for (int i=1; i<=n; i++) cout<<ans2[i]<<" \n"[i==n]; cin>>x; return; }E.Between算法本质思维题目大意给定n m,有编号1~n的节点,需要你构造一个尽可能长的序列(可能是无限),满足以下条件:序列的元素是某个节点节点1只有一个接下来会给出m对i j,表示序列每两个i节点中至少存在一个j节点若序列无限输出“无限”否则输出序列n <= 1.5e3思路推演-数目稍加模拟发现这是一个需要用图来思考的题:i j其实是j-->i的边,点x的最大数目 == min( 所有指向x点节点的最大数目中 ) + 1顺带可以发现,当某个点不受限制时,变存在无限长的情况。结合题目性质,想当然认为这是topo排序。经过模拟,成环情况下,其实也并不影响节点数目的判断,类似于最短路,到节点1的最短路。那么现在节点可行的最大数目都求得,接下来需要考虑怎么排序才能满足其中的“夹”条件。思路推演-构造-1首先肯定得优先用数目多的节点,然后接着用其指向的节点,大致思路是这样的。所以把边反向:即数目多的点 --> 数目少的点。这样更好思考。我们观察节点的连接情况,其指向的其他节点的数目,都是>=当前数目-1的。其中数目少的节点x --> 数目多的节点y其实也可以看作y-->x。(相同数目也可行)通过这个操作,重新改变节点边关系,可以保证无环。然后可以用稍加改造的topo来搞定:入度0的点入队若队头的节点数目还有,输出一次,队头节点数目--弹出队头节点,其指向节点入度--,若入度为0则入队这样重复多次直到所有节点数目为0即可。思路推演-构造-2(超越答案思路)但是之前的做法有些麻烦,需要修改边,然后再度topo,继续思考:对于当前数目多节点 --> 数目少节点的情况,指向一个节点也是指,指向多个也是指(最坏情况就是全部指)让数目多节点 --> 所有数目比其少的节点则可以省略修改边的过程,topo排列也变的简单无比ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int num[maxn]; vector<int> g[maxn]; void cls() { for (int i=1; i<=n; i++) g[i].clear(), num[i]=-1; } inline void solve() { //init cin>>n>>m; cls(); while (m--) { int u, v; cin>>u>>v; g[v].push_back(u); } //cal num[1] = 1; queue<int> q; q.push(1); int cnt=0; // 记录遍历的点数 while (q.size()) // 最短路bfs { int u=q.front(); q.pop(); cnt++; for (int v:g[u]) { if (num[v] == -1) { num[v] = num[u] + 1; q.push(v); } } } if (cnt!=n) // 存在不走到1的节点 { cout<<"INFINITE"<<endl; return; } // 否则一定可行 int len=0; for (int i=1; i<=n; i++) len += num[i]; cout<<"FINITE"<<endl; cout<<len<<endl; vector<int> v; // topo排序输出 rep(i,1,n) v.push_back(i); sort(v.begin(), v.end(), [](int a, int b){return num[a] > num[b];}); while (num[v[0]]) { for (int u:v) { if (num[u]==0) break; cout<<u<<" "; num[u]--; } } cout<<endl; return; }
2024年08月26日
1 阅读
0 评论
0 点赞
1
...
11
12
13
...
18