coci专题

COCI模拟考试心得体会

今天考了一场COCI的比赛，感觉题目没考什么特别难的算法，但是有些题就实现很麻烦。第一题键盘打字，就是个打表题，打了我好大半天，还好没打错。第二题一群固执的老人看电视，模拟一下谁去换台，换了什么台就可以过了，注意有循环就输出-1 第三题building，一道卡格式的题，给出每个矩形的左下角右上角坐标，让你勾勒整个透视图的轮廓。我想的是从外围跑一次flood fill，能

COCI Parametriziran —— 状压+dfs求相似字符串个数

Description Input Output Sample Input 3 3 ??b c?? c?c 4 6 ab??c? ??kll? a?k??c ?bcd?? 5 2 ?? b? c? ?g cg Sample Output 2 3 8 Hint 题意：给你n个长度相同的字符串，这些字符串中含有小写字母和’?’，’?'可以替换成任意字符，如果两个替换之

COCI HASH —— 扩展欧几里得

应该能进题意：定义哈希如下：现在问你长度为n的字符串中，有多少哈希值 % 2 m \%2^m %2m是k 题解：那么这道题就是个水题，我一眼就看出来是折半暴力， 2 6 5 26^5 265只有1e7种情况，然后从前往后dfs一下，之后再从后往前，因为它有点特殊，不能像普通哈希一样乘，可以推出来： x ∗ 33 x*33 x∗33^ y = k y=k y=k = > x

COCI ACM —— 线段树+枚举

This way 题意：现在哟n道题目，有三个人对这些题目打分(1~5)，现在要将这n道题目划分为3个连续的区间，分配给这三个人去做，每个人的值就是他对于他负责的区间的打分的值的和。问你所有人的值的和最小是多少。题解：那么其实这道题的解法很明显，首先每个人有先后顺序，但是只有3个人，所以可以暴力枚举每个人的先后情况。然后对于当前的情况，我们可以枚举第一个人负责的区间到哪，然后找到

BZOJ 2223 [Coci 2009]PATULJCI 主席树

Description Input Output 10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10 Sample Input no yes 1 no yes 1 no yes 2 no yes 3 Sample Output HINT Notice:输入第二个整数是序列中权

[COCI 2023-2024 #2] Kuglice 解题记录

[COCI 2023-2024 #2] Kuglice 解题记录题意简述一个长度为 n n n 的序列中有 n n n 个球，每个球有一个颜色。现在 A 和 B 轮流从两端取球，如果取的球的颜色之前没有取过就得一分，输出最终比分。题目分析因为这个序列是不断缩小的，且两端都可以删除，所以可以看成一个区间，考虑使用区间 DP。如何设状态？既然是区间 DP，那么状态肯定是

P9905 [COCI 2023/2024 #1] AN2DL 题解

思路首先考虑暴力算法，枚举每一个右端点，再遍历求最大值，枚举的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，遍历复杂度同样 O ( n 2 ) O(n^2) O(n2)。显然，在 n = 3000 n=3000 n=3000 时无法通过，考虑更优解法。大眼观察，发现这道题和 P1886 滑动窗口 /【模板】单调队列是几乎一样的；也就是把一维单调队列变成了二维的单调队列

洛谷----P1873 [COCI 2011/2012 #5] EKO / 砍树

题目描述伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。 Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下

COCI 2013/2014 1st round, September 28th, 2013 解题报告

TRENER 给出一堆人的英文名字（全是小写字母），若有一些字母作为首字母出现不少于5次，则输出所有符合条件的字母。每读入一个姓名，就给该姓名首字母的次数+1。最后扫一遍所有字母作为首字母出现的次数，大于等于5的输出。 #include<bits/stdc++.h>#define ll long long#define inf 999999999using namespace

[COCI 2008/2009 #2] PERKET

[COCI 2008/2009 #2] PERKET 题目描述 Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n n n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s s s 和苦度 b b b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。众所周

【字符串处理·新定义表达式（括号处理·递归）·思维】Kvalitetni--7.2测试 COCI

样例210 6((?)+(?))6.0000032 5 3(((?)+(?))*(?))6.0000032 10 6((?)*(?)*(?))8.000000000 分析首先，我们可以发现，这个问题是可以递归的（大多数表达式都可以递归），递归到最小的子问题的话，这个什么质量表达式本质上有三类： ( A ) (A) (A) ( A 1 + A 2 + … + A k )

【模拟细节】Imena 7.2测试 COCI

样例：1Spavas li Mirno del Potro Juan martine?42An4 voli Milovana. Ana nabra par Banana.12 比较简单但是考场上只拿了60分记录一下错误：没有考虑到单词仅有一个字母的情况只要这个字母大写，就可以之前的做法则没有考虑到这一点想的是最后一位要么是小写英文字母要么是标点 #include<

COCI 2021-2022 #1 - Set 题解

思路我们将原题中的数的每一位减一，此时问题等价。下面的异或都是在三进制下的异或。（相当于不进位的加法）我们考虑原题中的条件，对于每一位，如果相同，则异或值为 0 0 0，如果为 1 1 1， 2 2 2， 3 3 3 的排列，则异或值也为 0 0 0。于是我们设 C k C_k Ck 表示有没有 k k k 这个数， a n s = ∑ i ⊕ j ⊕ k = 0

COCI 2021-2022 #1 - Kamenčići 题解

题目大意给定长为 n n n 一个石子序列，其中的石子有红色和蓝色，可以从左边和右边取。两个人开始取石子，谁先取到 k k k 个石子就输，求先手是否必胜。思路 n n n 比较小，考虑记搜。设 f l , r , k 1 , k 2 f_{l,r,k_1,k_2} fl,r,k1,k2 表示现在剩的石子序列是 l l l 到 r r r，先手再取 k 1 k