成都网站建设成都网络公司,门户网站建设需要多少钱,山西网架公司,两个域名 两个网站 如何推广CF Edu 127 A-D vp补题
继续每日一vp#xff0c;今天晚上有课#xff0c;时间不太多#xff0c;回去就直接vp。前三题比较简单#xff0c;过了之后排名rk2000#xff0c;然后就去洗澡了。d题没怎么认真思考#xff0c;其实也可做。最后rk4000。发挥还行#xff0c;b题罚…CF Edu 127 A-D vp补题
继续每日一vp今天晚上有课时间不太多回去就直接vp。前三题比较简单过了之后排名rk2000然后就去洗澡了。d题没怎么认真思考其实也可做。最后rk4000。发挥还行b题罚时4次确实不应该。继续加油 题目链接
A. String Building 签到 题意给你一个只含‘a’和‘b’的字符串问你能否通过‘aa’‘aaa’‘bb’‘bbb’来组成。 思路很明显直接判断字符串中是否存在单独的‘a’或者‘b’即可。 经典的双指针写法
void Showball(){string s;cins;for(int i0;is.size();i){int ji;while(js.size()-1s[j]s[j1]) j;if(ij) {coutNOendl;return;}ij;}coutYESendl;
}B. Consecutive Points Segment 贪心 题意给你一个严格递增的序列你可以对每一个数x进行x1x-1或者不变的操作。问你能否把序列构造成形如l,l1,l2,...,ln−1l,l1,l2,...,ln-1l,l1,l2,...,ln−1的连续的序列。 思路直接贪心分析第一个数的情况比较特殊单独分析一旦前面的数确定就不能改变了我们每次尽可能让数变大如果相邻差值超过3那么无法进行构造。具体看代码。当时写的时候细节没有处理好wa了4发气急败坏
void Showball(){int n;cinn;vectorint a(n);for(int i0;in;i) cina[i];for(int i0;in-1;i){int ta[i1]-a[i];if(!i){if(t0) a[i1];else if(t1) a[i],a[i1];else if(t2) a[i];else if(t3) a[i],a[i1]--;else {coutNOendl;return;}}else{if(t0) a[i1];else if(t1) continue;else if(t2) a[i1]--;else {coutNOendl;return;}}}coutYESendl;
}C. Dolce Vita 前缀和贪心 题意你每天都有x元一开始给你n个物品的价格每天所有的物品的价格都会1。问你一共最多可以买几件物品。 思路这个题算法本场高光了看完题立马有了思路简单理了一下逻辑直接就开码了。码之前还提醒自己这题要开long long 然后很快样例过了。交上去…看到一直在过数据直呼稳了。然后wa 5。以为贪心错了结果看了一下vector没有开long long。下次注意 回归正题这个题贪心我们就先从小到大给商品排个序。然后求一下前缀和。由于我们要算一共能买几件商品我们直接统计每件商品最多能买几次再求和就可以。对于第iii个物品如果xs[i],那么说明这个物品一次都买不了因为我们要尽可能买便宜的商品。不妨令t(x-s[i])。那么我们发现每个物品最多可以买t/i1t/i1t/i1次。因为我们排了序所以如果t0,说明第一次我们可以直接买到1-i这些商品t就是剩下的钱。因为每天每件商品会涨价1元。所以t/it/it/i就是剩下的钱能够在涨价后还能买几天。因为第一天没有涨价所以还要加上第一天的一次。最后统计就ok。代码十分简洁
void Showball(){LL n,x;cinnx;vectorLL a(n1);LL sum0;//写题解时发现前缀和边算边用for(int i1;in;i) cina[i];sort(a.begin()1,a.end());LL ans0;for(int i1;in;i){suma[i];LL tx-sum;if(t0) ans(t/i1);}coutansendl;
}D. Insert a Progression 贪心思维 题意给你一个序列和一个正整数x。你需要将1-x之间的数插入到这个序列中去(可以插入到开头和结尾)然后求出最小的相邻两项绝对值之差的总和。 思路经过分析我们很快可以发现一些性质对于单调的区间插入后维持单调性是不会影响结果的。比如在2和7之间插入3 4 5 6。结果还是5。反过来也如此进行拓展我们就可以发现在序列最大值和最小值之间的数可以直接插入并且对结果没有影响。接下来我们考虑这之外的数如何处理。我们设序列最大值为maxnmaxnmaxn最小值为minnminnminn。通过刚才的分析我们发现对于111到minn−1minn-1minn−1这些数如果我们按照连续的顺序插入其实和直接插入1的结果是一样的例如我们将1,2,3插入到4 6 7这个序列中。1,2,3,4,6,7。可以发现符合前面讲的单调的性质所以2,3这些元素对结果不影响。所以我们只需要考虑1的插入。同理我们也只需要考虑x的插入。 对1插入的位置进行分析。无非就是开头结尾和minnminnminn的旁边。 对于开头的情况我们发现对答案的贡献是max(a0−1,0)max(a_0-1,0)max(a0−1,0)。对于结尾的情况。贡献则是max(an−1−1,0)max(a_{n-1}-1,0)max(an−1−1,0)。对于最小值旁边的情况贡献则是2∗max(minn−1,0)2*max(minn-1,0)2∗max(minn−1,0)。因为左边贡献一次右边贡献一次。不理解的话选三个数手算一下就明白了。对于x的插入分析同理。
LL a[N];
void Showball(){LL n,x;cinnx;for(int i0;in;i) cina[i];if(n1){coutmax(a[0],x)-1endl;return;}LL ans0;LL minn*min_element(a,an);LL maxn*max_element(a,an);for(int i0;in-1;i){ansabs(a[i]-a[i1]);}LL t1min({2*max(0ll,x-maxn),max(0ll,x-a[0]),max(0ll,x-a[n-1])});LL t2min({2*max(0ll,minn-1),max(0ll,a[0]-1),max(0ll,a[n-1]-1)});coutanst1t2endl;
}E. Preorder思维计数 题意给你一个满二叉树每个节点都有一个字符‘A’或者‘B’。然后总的字符串就是从根节点按照序号连起来的字符。你可以将一个非叶子节点的左二子和右儿子交换。问你一共能够构成多种字符串。 思路题目也很清晰。我们知道当两个儿子不同的时候那么就可以有两种情况。所以我们就可以递归处理如果左边和右边的字符串不相同答案就会乘2。因此我们需要较快的去比较左右字符串的大小。因此我们就可以进行规定每次组合都按照字典序进行组合那么对于两个一样情况的字符串我们就可以直接进行比较了。 ps:对于char数组 使用
char s[N];
cins1;这样读入在c20里是不被允许的会报错。一定要使用的话可以循环读入字符或者使用std::string
char s[N];
int n;
int f[N];
//快速幂 a^b mod p
LL qmi(int a, int b, int p)
{LL res 1 % p;while (b){if (b 1) res res * a % p;a a * (LL)a % p;b 1;}return res;
}
string dfs(int u){if(!s[u1]) return s[u]A?A:B;string s1dfs(u1),s2dfs(u1|1);f[u]f[u1]f[u1|1];if(s1!s2) f[u];if(s1s2) return s1s[u]s2;else return s2s[u]s1;
}
void Showball(){ s[0]?;cinn;for(int i1;i1n;i) cins[i];dfs(1);coutqmi(2,f[1],mod)endl;
}完结撒花
