子希

思维题

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论最短路(8) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 算法设计与分析题库(15) 线段树(10) 网络比赛(6) 题解(43)

/ 注册

全部文章 / 思维题（共23篇）

C. Kuroni and Impossible Calculation（鸽巢 + 思维）

题意：给你一个长度为n的序列，要你求他们的连乘，最后mod m。思路：如果O(n^2)暴力的话很好求，但是因为n = 2e5 所以肯定会超时。先给出结论，如果 n > m ，连乘直接为0。（等下给出证明）如果n <= m ，直接O(n^2)暴力即可，因为m最大取值 = 1e3。 ...

2020-05-21

0 457

B. Count Subrectangles

唉，补题补题，太菜了当时看到这个题一点思路没有。。。。看了大佬的思路才懂。。。唉，还是思维没有练起来得多多刷题咯，（为啥一天天的困得要死）思路：先求出k的所有因子，然后分别从向量a和向量b找连续k的因子个1的数量，然后求出所有的因子就行了。（想不到想不到！！）（至于为什么找连续个稍微用笔画一画...

2020-05-21

0 422

B 牛能和小镇

思路：看到这个题很容易想到(i,j)建边权就是上面的公式然后跑一下最小生成树就出来了。然后N=1e5，克鲁斯卡尔应该不会超时，但是会超空间。事实上这个题目很简单。通过这个式子可以反应出，原本两点之间的距离会依赖于两个点的坐标，但是化简后我们可以发现其实两点之间的距离并不需要依赖两点之间的坐标...

2020-05-21

0 752

D. A and B and Interesting Substrings(前缀和+思维)

题目大意：先输入26个字符[‘a’,‘z’]的权值，然后给你一个字符串，问你满足以下条件的子串有多少个。 1：第一个和最后一个字符相等的子串。 2：在这个子串中除掉第一个和最后一个字符的权值，剩下的字符权值之和等于0。思路：求一段区间和我们可以用前缀和O(1)解决，但是要在一个串中找所有首位字符...

2020-05-21

0 337

C. Ehab and Path-etic MEXs(思维+构造)

题意：给你一颗n个点的树，用[0,n-2]去给n-1条边编号，使得mex(u,v)的最大值最小。 mex(u,v)表示任意两点的简单路径中不在这条边上的最小非负整数。思路：这个题目好巧妙啊~~~~哈哈哈哈，题目中给了一个很重要的信息被我忽略了，那就是它给出的是一棵树，意味着任意两点有且仅有一条简...

2020-05-21

0 405

D. Ehab the Xorcist(构造+思维)

题意：给你u,v，要你构造一个最短的数组使得数组的各元素异或和为u，总和为v。思路：首先考虑几组特殊的情况 u == v == 0返回0即可 u == v != 0 返回u即可 u > v 返回 -1 这都比较简单验证但凡要构造什么东西的题目都是比较难的。这道题我们可以从异或这个运算出发...

2020-05-21

0 572

Codeforces Global Round 7(A - D题解) 来自专栏

题意：给你一个数n，要你找一个数>0并且它的位数等于n，并且不能被它自己的数整除(比如23，不能被2,和3整除)。思路：一开始构造了一个2222(n-1个2)3,wa了两发(哭了)。后面想起一个定理，只有各位数之和能被3整除这个数才能被3整除，于是我们构造这样一个数233333(n-1个...

2020-05-21

0 469

The Lazy Cow(silver)(二维前缀和)

题意：给你一个n* n的矩阵，还有一个k，要你找一个起点坐标，然后上下左右四个方向走k步，然后计算他们的和，使得这个和最大化。思路：一开始写了一个bfs，O(n^4)超时，然后改了一下。然后观察了一下最后我们要求的和是一个菱形，如果这个菱形内的和可以O(1)计算这题O(n ^ 3)就过了，但是...

2020-05-21

0 379

树(DP or 组合数学)

题目描述： shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。输入描述: 第一行两个整数n，k代表点数和颜色数；接下来n-1行，每行两个整数x,y表示x与y之间...

2020-05-21

0 340

D - RGB Triplets(前缀和+思维)

题意很好懂，就是一个长度为n的序列，s[i] 只可能是r,g,b，要你要满足就 j - i != k - j,并且s[i],s[j],s[k]两两不相同，并且i < j < k，的个数有多少个。思路：暴力O(n^3)模拟一遍铁超时，j - i != k - j 一开始一直在观察这个式...

2020-05-21

0 439