程设练习一 心得

小蒟蒻程设练习一心得~

debug

1542 数列

题干

心得

bug：TLE
debug：循环条件写了while(s[index] != 0)，，它真不一定回0…
改成while(used[s[index]] = fasle)

1549 2的幂次 I

题干

心得

bug：WA
debug：2的幂次，没打全，注意ai+aj范围，应该要打到2的30次

1583 彩球

题干

心得

bug：TLE
debug：

1. 前缀和优化，本来是从前往后和从后往前遍历2次。善用color[]数组，同时达成位置记录里的 next_same_color_index和 last_same_color_index，优化遍历为一次。ps：真正有效达到ac的不一定是这个优化

p[n].last_same_color_index = color[input[n]];
p[color[input[n]]].next_same_color_index = n;
color[input[n]] = n;

2. …cin 改成scanf…ac了…
3. 考虑过，可以在O(n)复杂度实现，去掉读入储存的那步，一边读一边前缀和处理（…结果读入有的问题好像会读空格还是别的什么原因没细究）

1484 刷油漆

题干

思路（谢大）

orz太腻害啦

心得

一点点小小心得（不好意思写啦）
从后往前数被部分覆盖的格子（就是涂行，会被后面涂列部分遮挡，涂列同理），本来想每次遍历一边后面涂色次数的（太蠢啦），其实用cnt单独记录一下在它之后的涂列、行的次数就好了

1539 区间

题干

心得

bug：WA
debug：

for(int begin = 0; begin < length; begin++) {
	for(int end = begin; end <= length; end++) {
		//去掉子串的范围[)

第二个for循环 的循环条件 end <= length，不然因为区间长[)这样去不掉最后一个字符
鸣谢 encode(“utf-8”) ，orz ！！！
所以说，以后区间还是长这样 [] 吧

1576 分段

题干

心得

原来是 因式分解
先得到它的因数，然后遍历累加，不满足从头开始试下一个因数即可

1560 平方数

题干

思路（谢大）

orz 太腻害了

心得

1. 学到了Set…（我真是孤陋寡闻）
2. 10^8 遍历找因数不会TLE，但是要一边找一边计算+set，不然好像会TLE（经历过，不确定是不是一定是这个原因）

//一边找一边计算的意思的这样
for(int i = 1; i * i <= mid; i++) {
    if(mid % i == 0) {
        int m = i + mid / i - 2 * B;
        if(m <= 0 || m % 4 != 0) continue;
        s.insert(m / 4);
    }
}

1567 3个矩形与1个正方形

心得

可以用DFS，这次是数量少，不然顺序写不完
同理拼图也可以（佬佬是DFS，我是小懒虫懒得再写呜呜呜
bug: WA
debug：数组下标乱窜 + 用错数组…（赣！

1578 拼图

心得

bug：WA
debug：删getchar…注意读入方式以及不能太信任样例的格式…

1565 Markdown

题干

略

心得

我逗，单元格为空的情况！
鸣谢 encode(“utf-8”) ，orz ！！！

笔记

C++ list 用法（双向链表）

参考 【总结】C++ 基础数据结构 —— STL之链表（list）用法详解
用于 1538 打字机
只要每次搞明白 迭代器 it 指向哪里就好

1. 希望it指向，插入元素位置的后一个元素

it = l.insert(it, str[t]); 
// it=别忘了
it++;

2. end() 返回的是指向最后一个元素之后的位置

it = l.end(); 
//end() 返回的是指向最后一个元素之后的位置

3. begin() 返回的是指向第一个元素的迭代器

it = l.begin();
// begin() 返回的是指向第一个元素的迭代器

4. 执行完 erase，it会指向被删除元素的后一个元素

it = l.erase(it);
//执行完，it会指向被删除元素的后一个元素

C++ STL对付回文数组

小蒟蒻一定在lqb专栏总结过，又忘记了…
用于 1548 回文串

1. 翻转

#include <string> //!!

string s = "hello";
cout<<string(s.rbegin(),s.rend())<<endl;

2. 插入

string str = "ello";
char s = 'H';
str.insert(0, 1, s); // Hello
//在原串下标为1的字符e前插入字符串s

亲测没有第二个参数‘1’，会报错…
如果用to_string，会变成ASCII，然后变成插入数字

3. 删除

str.erase（pos，n;
//从给定起始位置pos处开始删除, 删除n个字符

太香了咱就是说，直接插入，翻转对比，删除复原，（循环）

STL Set

参考 VS c++ SET类
用于 1560 平方数
头文件

#include<set>

1. 声明

set<int> mySet;

默认从小到大，如需从大到小则显式声明

set<int, greater<int>> mySet;

2. 插入

mySet.insert(1);

3. 删除
   iterator erase(const_iterator Where);

auto it1 = mySet.erase(next(mySet.begin));
//删除mySet的第二个元素
//it1 是指向删除下一个元素的迭代器

iterator erase(const_iterator First, const_iterator Last);

auto it2 = mySet.erase(next(mySet.begin()), prev(mySet.end()));
//删除mySet的第二个元素到倒数第二个元素
//it2 是指向 mySet.end() 的迭代器

size_type erase(const key_type& Key);

简而言之就是删除 set 的键值
返回的是删除的数量（int）

set<string> mySet;
mySet.insert("A");
mySet.insert("B");
int cnt = mySet.erase("B");
cout << cnt << endl; // 1
printset(mySet); // 只有 A

4. 遍历

auto e = mySet.end();
for(auto it = mySet.begin(); it != e; it++) {
	printf("%d ", *it);
}

mySet.end() 指向的是有效元素的下一个，可以用 prev(mySet.end()) 指向有效元素的最后一个
mySet.begin() 指向的是有效元素的d第一个，可以用 next(mySet.begin()) 指向有效元素的第二个

5. 空判断

if ( mySet.empty( ) )
  cout << "The set s1 is empty." << endl;
else
  cout << "The set s1 is not empty." << endl;

6. 长度

mySet.size()

判断一个数是不是完全平方数

参考 C++ 判断一个数是不是完全平方数

bool isPerfectSquare(int num)
{
    if(num == 1)
        return true;
 
    int start = 2;
    int end = num;
    int mid;
    while(start <= end)
    {
        mid = start + (end - start)/2;
        if(mid * mid == num)
            return true;
 
        if(mid > num / mid)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return false;
}

完结撒花🌺🌺