头像

没有只因的蛋蛋




离线:24分钟前


最近来访(96)
用户头像
Yang洋Yang
用户头像
保底不歪抽早柚
用户头像
Wyz0856
用户头像
yangxiufeng
用户头像
这道题有点难耶
用户头像
sc重新启程
用户头像
ackermann
用户头像
我想上成都电子科技大学
用户头像
黄瓜山第一痛苦哥
用户头像
恋影
用户头像
雨下一整晚
用户头像
wqh2003
用户头像
成_0
用户头像
爱情丶眨眼而去
用户头像
yyjjhh
用户头像
violet_garden
用户头像
Hard_IINE
用户头像
wlun
用户头像
123_59
用户头像
99的手速加上1的运气


set就是集合,STL的set用二叉树实现,
集合中的每个元素只出现一次(参照数学中集合的互斥性),
并且是排好序的(默认按键值升序排列)
(1)set的创建
set<int> a;
set<int> a = {1,2,3,4};
set<int,greater<int>> q = {1,2,3,4};//倒叙创建
其中可以是各种类型,包括结构体
(2)判断set是否为空 O(1)
a.empty(); 
(3)set的大小 O(1)
a.size();
(4)将set清空
a.clear();
(5)set中加入元素 O(log(n))
a.insert(2);
(6)set删除元素 O(log(n)
a.erase(1);
(7)set的二分 O(logn)
a.lower_bound(1);//找到大于等于x的最小的元素的迭代器
a.upper_bound(2);//找到大于x的最小的元素的迭代器
(8)set返回某个元素的个数(判断某个元素是否存在) O(k + log(n))
a.count(4) == 1;
(9)set的遍历
for(auto x : a)
(10)用hash实现的set
unordered_set<int> s;
里面的增删改查都为O(1)



C++ 大大增强了对字符串的支持,除了可以使用C风格的字符串,
还可以使用内置的 string 类。
string 类处理起字符串来会方便很多
,完全可以代替C语言中的字符数组或字符串指针。
(1)string的创建
string s1;
string s2 = "123456789";
string s3 = s2;
string s4(5,'s');
(2)字符串的输入
1.cin >> 
会过滤掉不可见字符(如 空格 回车,TAB 等)
2.cin.get()
cin.get(字符数组名,接收字符数目)用来接收一行字符,可以接收空格.
3.cin.getline() 
cin.getline()实际上有三个参数,
cin.getline(接受字符串的名称m,接受个数5,结束字符)当第三个参数省略时,
系统默认为'\n' 
4.getline() 
接受一个字符串,可以接收空格并输出
(3)将字符串转换为数 O(1)
stoi stol stoul stoll stoull stof stod stold
int a = stoi(s2);
(4)获取字符串的长度 O(1)
s1.size();
(5)字符串的ASCII编码值:'A' - 'Z'为65 ~ 90,'a' - 'z'是97-122,'0' - '9' 是48-57;
(6)两个字符串相加O(1)
string s5 = s2 + s5;
string s5 = s2.append(s5);//在尾部追加
(7)字符串的截取 O(1)
string s6 = s5.substr(1,3)//第一个参数是字符串的索引开始,第二个是长度
(8)字符串的翻转O (n)
reverse(s2.begin(),s2.end());
(9)找到某个字符在字符串中第一次出现的索引 O (n)
int h = s2.find('1');
(10)字符串的替换O(1)
s2.replace(1,3,'b');
将s2的索引1-3之间所有字符替换为b
(11)字符串的插入
s4.insert(1,"wda");
(12)判断两个字符串是否相等
s1 == s2
s1.compare(s2);
(13)字符串的交换
swap(s4[1],s4[5])



非暴力枚举,用数学去解决问题

C++ 代码

#include<bits/stdc++.h>

using namespace std;
const int N = 10000;
typedef pair<int,int> PII;
PII q[N];
int n;
char dx[5] = {'a','b','c','d','e'};

int main()
{
    scanf("%d",&n);
    int l = 1,r = 5;
    int h = 1;
    int i = 0;
    while(r < n)
    {
        q[i].first = l,q[i].second = r;
        i ++;
        h *= 2;
        l = r + 1;
        r += h * 5;
    }
    q[i].first = l,q[i].second = r;
    n -=  q[i].first;   
    int a = n / h;
    cout << dx[a] << endl;
    return 0;
}



C++ 代码

#include<bits/stdc++.h>

using namespace std;
int n;

int main()
{
    scanf("%d",&n);
    int ans = 0;
    int flag = 0;
    for(int i = 1 ; i <= 500 ; i ++)
    {
        ans += i;
        if(ans == n)
        {
            flag = 1;
            break;
        }
        else if(ans > n)
        {
            flag = 2;
            break;
        }
    }
    if(flag == 1) cout <<"YES" << endl;
    else if(flag == 2) cout << "NO" << endl;
    return 0;
}


活动打卡代码 AcWing 1216. 饮料换购

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
int n;

int main()
{
    scanf("%d",&n);
    int ans = n;
    while(n / 3 > 0)
    {
        ans += n / 3;
        n = n % 3 + n / 3; 
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1211. 蚂蚁感冒

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 60;
int n;
int q[N];
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&q[i]);
    int res = 1;
    if(q[0] < 0)
    {
        for(int i = 1 ; i < n ; i ++)
            if(q[i] > 0 && abs(q[i]) < abs(q[0])) res ++; 

        if(res != 1)
            for(int i = 1 ; i < n ; i ++)
                if(q[i] < 0 && abs(q[i]) > abs(q[0])) res ++;
    }
    else
    {
        for(int i = 1 ; i < n ; i ++)
            if(q[i] < 0 && abs(q[i]) > abs(q[0])) 
                res ++; 
        if(res != 1)
            for(int i = 1 ; i < n ; i ++)
                if(q[i] > 0 && abs(q[i]) < abs(q[0])) res ++;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1205. 买不到的数目

裴蜀定理 : 若a,b是整数,且gcd(a,b)=d,
那么对于任意的整数x,y,ax+by都一定是d的倍数,
特别地,一定存在整数x,y,使ax+by=d成立
在这个题当中,如果p和q互质,则p和q不能凑出来的最大数为M = (p-1)(q - 1) - 1
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m; 
int main()
{
    scanf("%d%d",&n,&m);
    cout << (n - 1) * (m - 1) - 1 << endl;
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int N = 110;
int n;

int main()
{
    scanf("%d",&n);
    while(n -- )
    {
        int r,c;
        int a[N][N];
        int f[N][N];
        scanf("%d%d",&r,&c);
        for(int i = 1 ; i <= r ; i ++)
            for(int j = 1 ; j <= c ; j ++)
                scanf("%d",&a[i][j]);
        for(int i = 1 ; i <= r ; i ++)
        {
            for(int j = 1 ; j <= c ; j ++)
            {
                f[i][j] = max(f[i - 1][j] ,f[i][j - 1]);
                f[i][j] += a[i][j];
            }
        }
        cout << f[r][c] << endl;
    }

    return 0;
}



#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
int n;
int a[N],f[N];
int main()
{
    scanf("%d",&n);
    int res = 0 ; 
    for(int i = 1; i <= n ; i ++)
    {
        scanf("%d",&a[i]);
        f[i] = 1;
        for(int j = 1 ; j < i ; j ++)
            if(a[j] < a[i]) f[i] = max(f[j] + 1 , f[i]);
        res = max(res, f[i]);
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i ++)
        scanf("%d%d",&v[i],&w[i]);

    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = m ; j >= v[i] ; j --)
        {
            f[j] = max(f[j] , f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}