DDOSvoid's Blog

题目描述

https://codeforces.com/contest/1609/problem/E

简要题意：给定一个字符串 $S$，该字符串只含有 $a,b,c$ 这三个字符，你现在可以修改任意次，每次可以将任意一个字母修改成 $a,b,c$ 这三个字符中的某一个，求最小修改多少次使得不存在 $abc$ 这样的子序列，同时现在有 $m$ 次询问，每次询问修改 $S$ 的一个字符，求最小修改次数

$|S|,m \le 10^5$

题目描述

https://codeforces.com/contest/1608/problem/D

简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案

$n\le 10^5$

题目描述

https://codeforces.com/contest/1608/problem/D

简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案

$n\le 10^5$

题目描述

简要题意：给定一个串 $S$，现在有 $m$ 次询问，每次询问本质不同的第 $k$ 小的子串，这里的字典序是长度不同，则长度小的字典序小，长度相同按照从前向后按位判断

$|S|,m\le 10^6$

题目描述

http://codeforces.com/gym/103427/problem/D

简要题意：给定一个 $a\times b$ 的四连通网格图，有 $n$ 个起点和 $n$ 个终点，现在有 $n$ 个人来到这 $n$ 个起点，同一时间不能有两个人在同一个点，每个时刻每个人可以选择移动或者停止，一个人来到终点可以随时选择离开，每个终点只能使用一次，求最少多长时间所有人都离开

$a\times b \le 100,n\le 100$

题目描述

http://codeforces.com/gym/103427/problem/M

简要题意：给定一个串 $S$，对于它的每个前缀求这个前缀的字典序最大的子串

$|S|\le 10^6$

简介

整数三分

1
2
3
4
5
6
7
8

while (l <= r) { 
	m1 = l + (r - l) / 3;
    m2 = r - (r - l) / 3;
    s1 = calc(m1); s2 = calc(m2);
    if (s1 < s2) r = m2 - 1;
    else l = m1 + 1; 
    ans = min(s1, s2);
}

题目描述

http://codeforces.com/problemset/problem/438/E

简要题意：给定一个含有 $n$ 个相异正整数的序列 $c_i$，现在要求用这些数构造一个带点权的有根无标号二叉树（形态不同，二叉树不同），一棵二叉树的权值为所有点的权值的和，现在给定 $m$，求权值为 $m$ 的二叉树的个数

$n,m\le 10^5$

题目描述

https://www.luogu.com.cn/problem/P4451

简要题意：令 $f_n$ 为斐波那契数第 $n$ 项，求 $\sum \prod_{i=1}^m f_{a_i}$，$m>0,a_1,a_2,\cdots,a_m>0,\sum_{i=1}^ma_i=n$

$n\le 10^{100000}$

题目描述

https://www.luogu.com.cn/problem/P4389

简要题意：现在有 $n$ 种物品，每种物品都有无限多个，第 $i$ 个物品的体积为 $v_i$，求恰好装满 $k,k\in[1,m]$ 的背包的方案数

$n,m\le 10^5$