头像

没有只因的蛋蛋




离线:7小时前


最近来访(107)
用户头像
sc重新启程
用户头像
Wyz0856
用户头像
锦木千束
用户头像
homoLZR
用户头像
宇宙有边
用户头像
yangxiufeng
用户头像
codefish7
用户头像
Yang洋Yang
用户头像
保底不歪抽早柚
用户头像
这道题有点难耶
用户头像
ackermann
用户头像
我想上成都电子科技大学
用户头像
黄瓜山第一痛苦哥
用户头像
恋影
用户头像
雨下一整晚
用户头像
wqh2003
用户头像
成_0
用户头像
爱情丶眨眼而去
用户头像
yyjjhh
用户头像
violet_garden

活动打卡代码 AcWing 1245. 特别数的和

太暴力了
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n;

bool check(int x)
{
    string s = to_string(x);
    for(int i = 0 ; i < s.size() ; i ++)
    {
        if(s[i] == '0' || s[i] == '1' || s[i] == '2' || s[i] == '9')
        {
            return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(check(i)) ans += i;
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 4726. 寻找数字

我尝试用dfs的全排列的方式来枚举所有情况,发现有太多的重复项,而且当枚举最后n = 5 的会后TLE了
#include<bits/stdc++.h>

using namespace std;
int n;
char q[20];
bool st[20];
char h[20];
void dfs(int u,int s,string str)
{
    if(u == s) 
    {
        for(int i = 0 ; i < s; i ++) cout << h[i] << ' ';
        cout << endl;
    }
    for(int i = 0 ; i < s ; i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            h[u] = q[i];
            dfs(u + 1 ,s ,str);
            st[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= 5 ; i ++)
    {
        memset(st ,false ,sizeof st);
        int u = i * 2;
        for(int i = 0 ; i < u / 2 ; i ++) q[i] = '4';
        for(int i = 0 ; i < u / 2 ; i ++) q[u / 2 + i] = '7';
        string str = "";
        dfs(0,u,str);
    }
    return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string num;
string ans;

void dfs(string str, int u, int s4, int s7)
{
    if (u == num.size())
    {
        if (str >= num && (ans.empty() || ans > str))
            ans = str;
        return;
    }

    if (s4 < num.size() / 2) dfs(str + '4', u + 1, s4 + 1, s7);
    if (s7 < num.size() / 2) dfs(str + '7', u + 1, s4, s7 + 1);
}

int main()
{
    cin >> num;

    if (num.size() % 2) num = '0' + num;

    dfs("", 0, 0, 0);

    if (ans.empty())
    {
        num = "00" + num;
        dfs("", 0, 0, 0);
    }

    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 1210. 连号区间数

寻找题目的切入点
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N = 10010;
int n;
int q[N];
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&q[i]);
    int ans = 0;
    for(int i = 0 ; i < n ; i ++)
    {
        int max_q = q[i];
        int min_q = q[i];
        for(int j = i ; j < n ; j ++)
        {
            max_q = max(max_q,q[j]);
            min_q = min(min_q,q[j]);
            if(max_q - min_q == j - i ) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}


新鲜事 原文

o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o
图片



简单做法

C++ 代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string c;

    getline(cin,c);
    for(int i = c.size() - 1; i >= 0 ; i --)
    {
        if(isalpha(c[i]) != 0)
        {
            if(c[i] == 'a' || c[i] == 'e' ||c[i] == 'i' ||c[i] == 'o' ||c[i] == 'u' ||c[i] == 'y' ||c[i] == 'A' || c[i] == 'E' ||c[i] == 'I' ||c[i] == 'O' ||c[i] == 'U' ||c[i] == 'Y')
            {
                cout << "YES" << endl;
                break;
            }
            else
            {
                cout << "NO" << endl;
                break;
            }
        }
    }
    return 0;
}



状态表示:f[i,j,k,c] 所有从起点到(i,j),且已经取了k件物品,且最后一件物品的价值为C的合法方案的集合
状态表示:
第一层:所有最后一步是从上往下走的走法, 所有最后一步是从左往右走的走法
第二层:第一层的两种方式又可以分为取和不取。 f[i -1,j,k,c] f[i,j - 1 ,k c]
第三层:第二层的两种取的方式中,又可以分为12种价值。
需满足w[i,j] == c    f[i - 1,j,k - 1 ,c‘] c‘  < c     f[i,j - 1 , k - 1 ,c]
一共四个维度

初始化:
f[1,1,1,w[1,1]]  取第一个物品
f[1,1,0,-1] 不取第一个物品
因为数组没有负数,所以将所有的数都加上1

C++ 代码

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

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m, k;
int w[N][N];
int f[N][N][13][14];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> w[i][j];
            w[i][j] ++ ;
        }

    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (i == 1 && j == 1) continue;
            for (int u = 0; u <= k; u ++ )
                for (int v = 0; v <= 13; v ++ )
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;
                    val = (val + f[i][j - 1][u][v]) % MOD;
                    if (u > 0 && v == w[i][j])
                    {
                        for (int c = 0; c < v; c ++ )
                        {
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
        }

    int res = 0;
    for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 1212. 地宫取宝

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

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m, k;
int w[N][N];
int f[N][N][13][14];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> w[i][j];
            w[i][j] ++ ;
        }

    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (i == 1 && j == 1) continue;
            for (int u = 0; u <= k; u ++ )
                for (int v = 0; v <= 13; v ++ )
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;
                    val = (val + f[i][j - 1][u][v]) % MOD;
                    if (u > 0 && v == w[i][j])
                    {
                        for (int c = 0; c < v; c ++ )
                        {
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
        }

    int res = 0;
    for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 787. 归并排序

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

using namespace std;
const int N = 100010;
int n;
int q[N],temp[N];

void merge_sort(int q[] ,int l,int r)
{
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(q,l,mid);
    merge_sort(q,mid + 1 , r);
    int i = l;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= r)
    {
        if(q[i] < q[j]) temp[k ++] = q[i ++];
        else temp[k ++ ] = q[j ++];
    }
    while(i <= mid) temp[k ++] = q[i ++];
    while(j <= r) temp[k ++] = q[j ++];
    for(int i = l, j = 0 ; i <= r ; j ++, i ++)
    {
        q[i] = temp[j];
    }

}
int main()
{
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&q[i]);
    merge_sort(q,0, n - 1);
    for(int i = 0 ; i < n ; i ++) cout << q[i] << ' ';
    return 0;
}



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])