首页 > 编程语言 >【C++】 string类的模拟实现

【C++】 string类的模拟实现

时间:2024-10-04 18:47:54浏览次数:8  
标签:const string pos C++ char str 模拟 size

目录

string类各函数接口总览

构造函数

拷贝构造函数

赋值运行符重载函数

析构函数

迭代器相关函数

begin

end

容量和大小相关的函数

size

capacity

resize

reserve

empty

修改字符串相关函数

push_back

append

operator+=

insert

erase

clear

swap

c_str

访问字符串相关函数

operator[ ]

find

关系运算符重载

>>和<<运算符的重载以及getline函数

>>运算符的重载

<<运算符的重载

getline


string类各函数接口总览

namespace cl
{
	//模拟实现string类
	class string
	{
	public:
		typedef char* iterator;
		typedef const char* const_iterator;

		//默认成员函数
		string(const char* str = "");         //构造函数
		string(const string& s);              //拷贝构造函数
		string& operator=(const string& s);   //赋值运算符重载函数
		~string();                            //析构函数

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;

		//容量和大小相关函数
		size_t size();
		size_t capacity();
		void reserve(size_t n);
		void resize(size_t n, char ch = '\0');
		bool empty()const;

		//修改字符串相关函数
		void push_back(char ch);
		void append(const char* str);
		string& operator+=(char ch);
		string& operator+=(const char* str);
		string& insert(size_t pos, char ch);
		string& insert(size_t pos, const char* str);
		string& erase(size_t pos, size_t len);
		void clear();
		void swap(string& s);
		const char* c_str()const;

		//访问字符串相关函数
		char& operator[](size_t i);
		const char& operator[](size_t i)const;
		size_t find(char ch, size_t pos = 0)const;
		size_t find(const char* str, size_t pos = 0)const;
		size_t rfind(char ch, size_t pos = npos)const;
		size_t rfind(const char* str, size_t pos = 0)const;

		//关系运算符重载函数
		bool operator>(const string& s)const;
		bool operator>=(const string& s)const;
		bool operator<(const string& s)const;
		bool operator<=(const string& s)const;
		bool operator==(const string& s)const;
		bool operator!=(const string& s)const;

	private:
		char* _str;       //存储字符串
		size_t _size;     //记录字符串当前的有效长度
		size_t _capacity; //记录字符串当前的容量
		static const size_t npos; //静态成员变量(整型最大值)
	};
	const size_t string::npos = -1;

	//<<和>>运算符重载函数
	istream& operator>>(istream& in, string& s);
	ostream& operator<<(ostream& out, const string& s);
	istream& getline(istream& in, string& s);
}

为了和C++库中的string类区分开,这里我们将模拟实现放入命名空间域中实现

构造函数

构造函数

string(const char* str)
	:_size(strlen(str))
	,_capacity(_size)
	,_str(new char[_capacity + 1])
{
	memcpy(_str, str);
}

使用_capacity当_str申请空间的参数回有风险,因为它的初始化顺序是按照成员变量声明的顺序走的,在初始化列表中稍有不慎,程序就会有问题,这是我们不愿意看到的

默认构造函数

string()
:_size(0)
,_capacity(0)
,_str(new char[1]{0})
{}

对以上两种方式的结合:

string(const char* str = "")  
{
	_size = strlen(str);
	_capacity = _size;
	_str = new char[_capacity + 1];

	memcpy(_str, str, _size + 1);
}

""有一个标示符'\0',是可以有这样的写法的(空字符串),将定义放在初始化列表,初始化顺序只能跟着声明顺序走,太死板了,我这里直接就在构造函数中赋初值,这样更加灵活

拷贝构造函数

这里再说拷贝构造时,我们讲解一下深/浅拷贝

浅拷贝(值拷贝):对内置类型可以进行有效的处理,如果碰到动态申请的空间,那么源对象和目标对象的指针指向同一块区域,共用一份资源

深拷贝:对浅拷贝问题的优化,目标对象会开辟一块空间用来存放源空间的资源

方法一:传统写法

这里就是深拷贝实现

string(const string& str)
	//:_str(str._str)这相当于是一个浅拷贝, 浅拷贝很多缺点,不推荐
{
	//帮_str开辟一个空间存放str._str的值,进行深拷贝
	_str = new char[str._capacity + 1];

	//将对象的成员函数_str赋值给它
	memcpy(_str, str._str);
	_size = str._size;
	_capacity = str._capacity;
}

方法二:现代写法

string(const string& str)
	:_str(nullptr)
	,_size(0)
	,_capacity(0)
{
	string tmp(str._str);

	swap(tmp);
}

这里的实现方法:创建tmp对象,使用str的动态资源进行初始化,然后与_str进行交换,这样就全自动的进行了拷贝,这里需要注意的是必须让_str在初始化列表进行初始化,因为每个编译器在对象实例化的时候都可能会有自己的个性化处理(帮对象初始化),但是C++语法规定,构造函数不会去初始化自置类型,自定义会去调用它的构造函数,相信编译器很不靠谱,所以为了增强代码的可移植性最好的方法是我们手动进行初始化

例如以上代码再VS2022下,没有进行初始化,析构函数就会析构一个没有初始化 (随机值) 的空间,所以编译器就会报错

swap在后面会实现

赋值运行符重载函数

传统方法:

和拷贝构造函数一样,也是使用一个临时对象tmp拷贝s的资源然后释放_str,最后将tmp拷贝给_str完成实现深拷贝

//传统方法:
string& operator=(const string& s)
{
	//避免自己和自己赋值
	if (this != &s)
	{
		char* tmp = new char[_capacity + 1];
		//注意:这里不能使用strcpy,这个函数到\0就结束了
		//不能拷贝\0之后的数据,这里建议使用memcpy,它是根据_size有效字符串的个数来进行拷贝的
		memcpy(tmp, s._str, _size + 1);
		//需要释放地址,不然会内存泄漏
		delete[] _str;
		_str = tmp;

		_size = s._size;
		_capacity = s._capacity;
	}
}

现代方法:

方法一:

这种写法就相当于全自动深拷贝,使用函数就帮我们实现了深拷贝,形参是传的引用,所以不会调用拷贝构造,并且需要进行相同地址的判断,避免自己给自己赋值

例如:s1 = s3; 就只需要调用赋值运算符重载函数就可以完成

注意:等号的特性,左值改变,右值不改变,所以我们需要临时变量,来帮我们完成交换,如果没有临时变量,就会改变右值

string& operator=(const string& s)
{
	if (this != &s)
	{
		string tmp(s);

		swap(tmp);
	}

	return *this; //返回左值支持连续赋值
}

方法二:

这种方法则会去多调用一个拷贝构造函数,就是让系统帮我们创建一个临时变量(右值),然后去给左值进行赋值,上面那个写法算是半自动,这个写法才是真正的全自动,而且不需要担心自己给自己赋值的问题

string& operator=(string s)
{
	swap(s);
	//下面这段写法是不行的,传对象的话会陷入死循环,会不断的调用赋值重载
	/*std::swap(*this, s);*/
	return *this;
}

这里推荐使用方法二,比较便利

析构函数

因为我们模拟实现string中有很动态资源所以我们需要手动写析构函数

if判断语句,_str为空,就没有释放的必要

//析构函数
~string()
{
	if (_str)
	{
		delete[] _str;
		_str = nullptr;
		_size = _capacity = 0;
	}
}

迭代器相关函数

在string中迭代器(iterator)就是字符指针char*

typedef char* iterator;
typedef const char* const_iterator;

迭代器只是与指针用法很像,不是所有迭代器都是指针

begin和end

string中begin和end函数实现相当简单,有普通版本和const版本的,系统会根据情况去匹配最适合的版本

begin

iterator begin()
{
	return _str;
}

const_iterator begin() const
{
	return _str;
}

end

iterator end()
{
	return _str + _size;
}

const_iterator end() const
{
	return _str + _size;
}

迭代器的用法:

string s1("hello world");
string::iterator it = s1.begin();
while(it != s1.end())
{
    cout << *it << ' ';
    ++it;
}
cout << endl;

实现迭代器之后,其实范围for也可以使用了,因为范围for的底层就是使用迭代器来实现的

string s1;
for(auto e : s1)
{
    cout << e << ' ';
}
cout << endl;

容量和大小相关的函数

size和capacity

size

获取当前有效元素个数

//大小
size_t size()const
{
	return _size; //返回字符串当前的有效长度
}

capacity

获取容量

//容量
size_t capacity()const
{
	return _capacity; //返回字符串当前的容量
}

resize和reserve

resize

使用规则:

1.扩容的大小大于当前容量,扩大容量至指定容量,并且有效字符之外的容量使用指定字符来充填,如果没有指定字符,那么默认使用\0来填充

2.扩容的大小小于当前容量,缩容至指定大小

void resize(size_t n, char c)
{
	if (n < _size)
	{
		_size = n;
		_str[_size] = '\0';
	}
	else
	{
		reserve(n + 1);
		
		for (size_t i = _size; i < n; ++i)
		{
			_str[i] = c;
		}

		_size = n;
		_str[_size] = '\0';
		
	}
}

reserve

使用规则:

1.需扩容大小大于当前大小,则扩容至等于或大于指定大小

2.小于当前大小,则什么都不做

//reserve 义有保留的意思,用来扩容,缩容时系统不会理睬
void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1] {0};
		memcpy(tmp, _str, _size + 1);
		delete[] _str;
		_str = tmp;
		_capacity = n;
	}
}

注意:这里推荐使用memcpy函数进行拷贝而不是使用strcpy,是因为strcpy到\0就结束了,可能会出现问题,而memcpy是跟据_size的个数来进行拷贝的,基本上不会出现什么问题

empty

判断字符串是否为空

//判断_str是否为空
bool empty()
{
	return *this == ""; //或者使用strcmp(_str, "") == 0;
}

使用*this == ”“;,==需要进行重载,后面会进行说明

修改字符串相关函数

push_back

push_back函数的作用就是在当前字符串的后面尾插上一个字符,尾插之前首先需要判断是否需要增容,若需要,则调用reserve函数进行增容,然后再尾插字符,注意尾插完字符后需要在该字符的后方设置上’\0’,否则打印字符串的时候会出现非法访问,因为尾插的字符后方不一定就是’\0’。

void push_back(char ch)
{
	if (_size == _capacity)
	{
		//代码效率太低,需要频繁扩容
		/*reserve(_capacity);*/
		reserve(_capacity == 0 ? 4 : _capacity * 2); //两倍扩容
	}

	//ch将'\0'给覆盖了,所以后面一个补一个'\0'
	_str[_size] = ch;
	++_size;
	_str[_size] = '\0';
}

如果我们实现了insert那我们还可以直接使用insert来实现push_back

//尾插字符
void push_back(char ch)
{
	insert(_size, ch); //在字符串末尾插入字符ch
}

append

append函数的作用是在当前字符串的后面连接一个字符串,尾插前需要判断当前字符串的空间能否容纳下尾插后的字符串,若不能,则需要先进行增容,然后再将待尾插的字符串尾插到对象的后方,因为待尾插的字符串后方自身带有’\0’,所以我们无需再在后方设置’\0’。

//在字符串后面链接字符串
void append(const char* str)
{
	size_t len = _size + strlen(str); //连接之后的大小(不包括\0)
	if (len > _capacity)//这里如果有等于的话len就需要加1,需要一个位置放'\0'
	{
		//代码有问题,如果len + 1大于两倍的_capacity,就报错了
		//reserve(_capacity * 2);
		//至少扩到len的大小
		reserve(len);
	}
	/*strcat(_str, str);
	_size += strlen(str);*/
	//或者使用strcpy
	memcpy(_str + _size, str, strlen(str) + 1);
	_size += strlen(str);
}

实现append也可以复用insert函数

//尾插字符串
void append(const char* str)
{
	insert(_size, str); //在字符串末尾插入字符串str
}

operator+=

这里直接复用push_back和append就可以了

//+=运算符重载(shiy)
string& operator+=(const char ch)
{
	push_back(ch);
	return *this;
}
string& operator+=(const char* str1)
{
	append(str1);
	return *this;
}

insert

在字符串任意位置插入,使用前需要判断pos位置的合法性,不合法,则代码无法进行,还需要判断当前容量能否支持插入之后的新字符串的大小,若不能则使用reserve进行扩容,将pos位置的K空间空出来,pos及后面的字符全部往后挪动一位,然后将新字符插入到pos位置

插入字符:

//插入,注意:pos是下标
string& insert(size_t pos, size_t n, const char ch)
{
	assert(pos <= _size);

	size_t len = _size + n;
	//扩容
	if (len >= _capacity)
	{
		reserve(len);
	}

	//挪动数据,当pos为0时,end为-1,无符号整型的-1是很大的一个数
	/*size_t end = _size;
	while (end >= pos)
	{
		_str[end + n] = _str[end];
		--end;
	}*/
	//解决方法一:将等号去掉,从后往前拷贝,不建议,写出来代码可读性不高
	//解决方法二:将end的类型改为int,然后强制类型转换pos为int
	//int end = _size;
	这里pos如果没有强转为int,那么这里会发生隐式类型转换,end(int -> szie_t)
	//while (end >= (int)pos)
	//{
	//	_str[end + n] = _str[end];
	//	--end;
	//}
	//解决方法三:加一个循环条件 end != npos,控制当pos等于0,而end为-1的情况
	size_t end = _size;
	while (end >= pos && end != npos) 
	{
		_str[end + n] = _str[end];
		--end;
	}

	//在pos位置插入数据
	for (size_t i = pos; i < pos + n; ++i)
	{
		_str[i] = ch;
	}

	//改变当前字符串大小
	_size += n;

	return *this;
}

插入字符串:

string& insert(size_t pos, const char* str)
{
	assert(pos <= _size);

	size_t len = strlen(str);
	//扩容
	if (len + _size >= _capacity)
	{
		reserve(len + _size);
	}
	//解决方法三:加一个循环条件 end != npos,控制当pos等于0,而end为-1的情况
	size_t end = _size;
	while (end >= pos && end != npos)
	{
		_str[end + len] = _str[end];
		--end;
	}

	//在pos位置插入数据
	for (size_t i = 0; i < len; ++i)
	{
		_str[i + pos] = str[i];
	}
	

	//改变当前字符串大小
	_size += len;

	return *this;

}

注意:插入字符串的时候使用memcpy,不能使用strcpy,否则会将待插入的字符串后面的’\0’也插入到字符串中。

erase

erase函数的作用是删除字符串任意位置开始向后的n个字符。删除字符前也需要判断pos的合法性,进行删除操作的时候分两种情况:
1、pos位置(包括pos)之后的有效字符都需要被删除。
这时我们只需在pos位置放上’\0’,然后将对象的size更新即可。
2、pos位置(包括pos)之后的有效字符只需删除一部分。
这时我们可以用后方需要保留的有效字符覆盖前方需要删除的有效字符,此时不用在字符串后方加’\0’,因为在此之前字符串末尾就有’\0’了。


string& erase(size_t pos = 0, size_t len = npos)
{
	assert(pos <= _size);

	//满足其中一个就需要删
	if (len == npos || pos + len >= _size)
	{
		_str[pos] = '\0';
		_size = pos;
	}
	else
	{
		size_t end = pos + len;
				
        //直接将数据进行覆盖删除
		while (end <= _size)
		{
			_str[pos++] = _str[end++];
		}

		_size -= len;
	}

	return *this;
}

clear

将对象的有效字符清空,将_size赋为0,然后改变第一个元素为\0

//清数据clear
void clear()
{
	_size = 0;
	_str[_size] = '\0';
}

swap

交换两个对象的资源,C++库中有实现,string类中也有实现,若需要使用C++库中的需要在swap前面加域作用限定符(::)到库中取出使用,这里建议使用string类中的swap,因为在string类中的函数成员访问私有成员时不受访问限定符的作用

void swap(string& s) //不能加const,s会改变
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}

c_str

c_str函数用于获取对象C类型的字符串,实现时直接返回对象的成员变量_str即可。

//转化为字符串
const char* c_str() const
{
	return _str;
}

访问字符串相关函数

operator[ ]

[ ]运算符的重载是为了让string对象能像C字符串一样,通过[ ] +下标的方式获取字符串对应位置的字符。
在C字符串中我们通过[ ] +下标的方式可以获取字符串对应位置的字符,并可以对其进行修改,实现[ ] 运算符的重载时只需返回对象C字符串对应位置字符的引用即可,这样便能实现对该位置的字符进行读取和修改操作了,但需要注意在此之前检测所给下标的合法性。

这种实现方式可读可写:

//[]运算符重载
char& operator[](size_t pos)
{
	assert(pos < _size);

	return _str[pos];
}

这种实现方式只能读不能写:

在某些场景下,我们可能只能用[ ] +下标的方式读取字符而不能对其进行修改。例如,对一个const的string类对象进行[ ] +下标的操作,我们只能读取所得到的字符,而不能对其进行修改。所以我们需要再重载一个[ ] 运算符,用于只读操作。

const char& operator[](size_t pos) const
{
	assert(pos < _size);

	return _str[pos];
}

find和rfind

find函数和rfind函数都是用于在字符串中查找一个字符或是字符串并且返回它们所在位置的下标,find函数和rfind函数分别用于正向查找和反向查找,即从字符串开头开始向后查找和从字符串末尾开始向前查找。

find

1.正向寻找第一个匹配的字符

首先判断所给pos的合法性,然后通过遍历的方式从pos位置开始向后寻找目标字符,若找到,则返回其下标;若没有找到,则返回npos。(npos是string类的一个静态成员变量,其值为整型最大值)

//寻找失败返回npos
size_t find(char ch, size_t pos = 0) const
{
	//判断下标合法性
	assert(pos < _size);

    //如果pos有值就从pos的位置开始找
	char* tmp = strchr(_str + pos, ch);
	if (tmp != NULL)
	{
		return tmp - _str;
	}
	//失败返回npos,npos是无符号整型的静态成员
	return npos; 
}

2.正向寻找第一个匹配的字符串

首先也是先判断所给pos的合法性,然后我们可以通过调用strstr函数进行查找。strstr函数若是找到了目标字符串会返回字符串的起始位置,若是没有找到会返回一个空指针。若是找到了目标字符串,我们可以通过计算目标字符串的起始位置和对象C字符串的起始位置的差值,进而得到目标字符串起始位置的下标。

size_t find(const char* str, size_t pos = 0) const
{
	//判断下标合法性
	assert(pos < _size);

	char* tmp = strstr(_str, str);
	if(tmp != NULL)
	{
		return tmp - _str;
	}
	//失败返回npos,npos是无符号整型的静态成员
	return npos;
}

关系运算符重载

关系运算符有 >、>=、<、<=、==、!= 这六个,但是对于C++中任意一个类的关系运算符重载,我们均只需重载其中的两个,剩下的四个关系运算符可以通过复用已经重载好了的两个关系运算符来实现。

例如,对于string类,我们可以选择只重载 > 和 == 这两个关系运算符。

方法一:

//重载关系运算符 <
//方法一:
bool operator<(const string& s) const
{
	int it1 = 0;
	int it2 = 0;

	while (it1 != _size && it2 != s._size)
	{
		if (_str[it1] < _str[it2])
		{
			return true;
		}
		else if (_str[it1] > _str[it2])
		{
			return false;
		}
		else
		{
			++it1;
			++it2;
		}

		return _size < s._size;
	}
}

方法二:

复用库里面的函数

//方法二:复用库里面的函数
bool operator<(const string& s) const
{
	//这里没有使用strcmp,是因为这个函数遇到\0终止,可能导致最终结果不准确
	int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);

	return ret == 0 ? _size < s._size : ret < 0;
}

这里不能使用strcmp,因为这个函数到\0就结束了,不能比较\0后面的字符,而memcmp就不同他是根据_size(有效字符)进行比较时不会漏掉字符

剩下的关系运算符

bool operator==(const string& s) const
{
	return !(*this > s) && !(*this < s);
}

bool operator>=(const string& s) const
{
	return !(*this < s);
}

bool operator>(const string& s) const
{
	return !(*this < 0) && !(*this == 0);
}

bool operator<=(const string& s) const
{
	return !(*this > s);
}

bool operator!=(const string& s) const
{
	return !(*this != s);
}

>>和<<运算符的重载以及getline函数

>>运算符的重载

重载>>运算符是为了让string对象能够像内置类型一样使用>>运算符直接输入。输入前我们需要先将对象的C字符串置空,然后从标准输入流读取字符,直到读取到’ ‘或是’\n’便停止读取。

//重载流插入运算符, 这里需要引用一个istream里面的函数 get() 一个一个字符来提取,不会因为分割符而停止
istream& operator>>(istream& in, string& s)
{
    //将原字符串中的数据清理
	s.clear();

	char ch = in.get();
	//清理 空格和'\0'
	while (ch == ' ' || ch == '\n')
	{
		ch =in.get();
	}

	//避免空间固定开太大,导致浪费空间
	//或者频繁的开辟空间
	//解决方法:开一个固定大小为128的字符数组,满127个字符就输入进对象,然后重置这个数组
	char buff[128] = { '\0' };

	size_t i = 0;
	while (ch != ' ' && ch != '\n')
	{
		buff[i++] = ch;
		if (i == 127)
		{
			buff[i] = '\0';
			s += buff;
			i = 0;
		}

		//清理 已经存放到buff数组中的字符,避免重复放入第一个字符导致死循环
		ch = in.get();
	}


	if (i != 127)
	{
		buff[i] = '\0';
		s += buff;
	}

	return in;
}

<<运算符的重载

重载<<运算符是为了让string对象能够像内置类型一样使用<<运算符直接输出打印。实现时我们可以直接使用范围for对对象进行遍历即可。

//流插入<<运算符重载
ostream& operator<<(ostream& out, const string& s)
{
	for (auto e : s)
	{
		out << e;
	}

	return out;
}

getline

getline函数用于读取一行含有空格的字符串。实现时于>>运算符的重载基本相同,只是当读取到’\n’的时候才停止读取字符。

istream& getline(istream& in, string& s)
{
    //将原字符串中的数据清理
    s.clear();

	char ch = in.get();
	char buff[128] = { 0 };
	int i = 0;
	while (ch != '\n')
	{
		buff[i] = ch;
		if (i == 127)
		{
			buff[i] = '\0';
			s += buff;
			i = 0;
		}

		++i;
		ch = in.get();
	}

	if (i != 127)
	{
		buff[i] = '\0';
		s += buff;
	}
	return in;
}

标签:const,string,pos,C++,char,str,模拟,size
From: https://blog.csdn.net/m0_73634434/article/details/142683981

相关文章

  • String
    String题面:给定两个字符串\(a\),\(b\),我们称这两个字符串的所有子序列为坏字符串。求最短的非坏字符串。做法:首先要解决一个问题,假设你有一个字符串你需要判断这个字符串是否是坏的,怎么快速判断?我们预处理出nxta[i][j]表示\(a\)字符串中第\(i\)个位置之后第一个\(......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2过T2了,赢了T3T4暴力没写满,输了A挤压我是唐诗老哥一个半小时才过T1发现要求的是\(E(s^2)\),因为有个异或,所以直接考虑拆贡献到每一位\[E(s^2)=E(\sums_i\sums_j)=\sumE(s_is_j)\]所以直接考虑后面那个咋做,就是\(i,j\)位同时是一的时候贡献\(2^......
  • 20241003 模拟赛
    这场...打得还行吧。(至少没有爆零A.旋律的总数难度:橙签到题。只要第一个都选\(1\),就能保证不同。答案为\(m^{n-1}\)。#include<bits/stdc++.h>#definelllonglong#definemod1000000007usingnamespacestd;intT;lln,m;llquickpow(lla,llb){llre......
  • 10.2 代码源 2024 CSP-S 模拟赛 Day 7
    省流:\(55+5+0+10=70\)简称:唐诗T1第一眼发现在二进制下加法不能进位,然后码了个DP就放那了……DP代码:intS=(1<<14)|1;fd(i,0,r[1])f[1][i]=1;fd(i,2,n){fd(j,0,S){f[i][j]=f[i-1][j];for(ints=j;s;s=(s-1)&j){(f......
  • 10.4 模拟赛(2025 炼石计划 NOIP 模拟赛 #7)
    2025--炼石计划--9月25日--NOIP模拟赛#7【订正】-比赛-梦熊联盟(mna.wang)复盘赢麻了。浏览题。T1没理解“中间节点”是啥意思,样例太大先不模拟了。T2什么东西,密铺?T3好像看懂了题。脑子中瞬间有一个\(n^3\)DP,发现\(n\le200\)感觉切了。但其实DP假的很......
  • KDY-二轮模拟-ZHX补题报告
    1.比赛情况T1三个T2合体T3矩形T4数对总分100pts70pts20pts20pts210pts2.赛中概况第一第二题比较简单,用了1小时搞定。(第一题全体AK)第3,4题难度飙升,想了好久最后改用暴力,共得40分,符合预期。3.题目解析 T1暴力出奇迹1.1问题描述现在科学家在培养 A,B,C三种微生......
  • [DMY]2024 CSP-S 模拟赛 Day 7
    题目T1T2T3T4当前分数这场打成一坨了。几乎写的全是暴力。赛时开T1,不太会正解,先写了个暴力丢到那儿。胡了一个\(\mathcal{O}(n^2)\)的做法,但是样例假了,照着手推一遍发现错的很彻底。已经过了1h,于是去看T2。T2还是先写出来了暴力思路。感觉这东西......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2\(T1\)P294.挤压\(40pts\)部分分\(20\%\):爆搜,时间复杂度为\(O(2^{n})\)。另外\(20\%\):观察到值域较小,将值域计入状态设计,时间复杂度为\(O(nV)\)。点击查看代码constllmod=1000000007;lla[100010],p[100010],pp[100010],q[100010],f[2]......
  • 10.4 代码源 2024 CSP-S 模拟赛 Day 9
    省流:\(100+0+0+0=100\)简称:唐诗T1先写了个暴力,然后在想怎么优化,然后想了个区间DP但是写的时候又不会了……然后发现如果这一块数的二进制每一位都有一个数的这一位为\(0\)或者都相同,那么这些数合并起来一定最优,然后双指针搞,复杂度\(O(30n)\)。(这么绕口)赛后听别人说有......
  • [DMY]2024 CSP-S 模拟赛 Day 9
    T2调了1h没调出来,丢了一坨没分的shi扔了。我想放一下作为开头:include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inlineintread(){intw=1,s=0;charch=getchar();while(!isdigit(ch)){if(ch'-')w=-1;ch=getchar();}while(isdigit(ch)){s=s10+(ch-......