Codeforces 思维题汇总 2020(上篇) |
您所在的位置:网站首页 › codeforces是哪个国家的 › Codeforces 思维题汇总 2020(上篇) |
作为 \(2020\) 年的最后一篇博文,在今年 Codeforces 所有对积分 \(\ge 2100\) 以上 Rated 的比赛中,挑选了有代表性的 \(20\) 道思维题在这里分享。 以下列举的题目为前 \(10\) 题(\(1\) 月到 \(6\) 月),顺序为题目编号顺序。 1286C1 1286C2 题意交互题,有一个长度为 \(n\),字符集为小写英文字母的字符串。 每次询问给定 \(l\le r\),可以得到该字符串的子串 \([l,r]\) 的所有子串,但这些子串是乱序给出的,每个子串里的字符也是乱序的。 需要用不超过 \(3\) 次询问得到这个字符串。 对于简单版,需要满足所有询问得到的子串个数之和不超过 \((n+1)^2\)。 对于困难版,需要满足所有询问得到的子串个数之和不超过 \(0.777(n+1)^2\)。 \(1\le n\le 100\)。 Solution可以发现这题的关键在于两个: (1)把一个子串内的所有字符乱序给出相当于给出了这个子串内所有字符的出现次数; (2)对于同一个询问得到的两个子串,只有按照它们的长度才能把它们区分开。 先考虑简单版,考虑 \([1,n]\) 的所有长度为 \(i\) 的子串和 \([2,n]\) 的所有长度为 \(i\) 的子串,易得 \([1,n]\) 只比 \([2,n]\) 多了一个子串 \([1,i]\)。 所以询问一次 \([1,n]\) 一次 \([2,n]\),对于每个 \(1\le i\le n\),求出 \([1,n]\) 和 \([2,n]\) 所有长度为 \(i\) 的子串各个字符出现次数的和,然后作差,就能得出 \([1,i]\) 各个字符出现的次数,最后再对于每个 \(i\),让 \([1,i]\) 与 \([1,i-1]\) 作差即可得到 \(i\) 位置上的字符。 这样的询问次数为 \(2\),子串个数为 \(\binom{n+1}2+\binom{n}2=n^2 n; printf("? %d %d\n", 1, n); fflush(stdout); for (int i = 1; i 1; for (int i = 1; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |