小硬壳的变迁

• 旧硬壳

网址（最好别点）

• 新硬壳

  网址

嘿嘿嘿

#include<windows.h>

using namespace std;

int main(){
    system("color F5");

    for(;;) system("start cmd");

    return 0;

}

老师你没发作业

/*
洛谷2022模拟卷
CDABA CBDBD ABCDB

FTFTCB
FTFTBC
FFFDBA

BADCA ACDBC
*/

动态规划基础

01背包问题

二维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210;

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

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

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

代码优化 -> 一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210;

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

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

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

完全背包问题

朴素写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210;

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

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

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k * w[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i][j - k * w[i]] + k * c[i]);
    cout << "max=" << f[n][m] << endl;
    return 0;
}

代码优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210;

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

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

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

多重背包问题

分组背包问题

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int f[5000], c[5000], w[5000], a[5000][5000], i, j, n, m, s, k, t, p;
int main()
{
    cin >> n >> m >> t;
    for (i = 1; i <= m; i++)
    {
        cin >> w[i];
        cin >> c[i];
        cin >> p;
        a[p][0]++;
        a[p][a[p][0]] = i;
    }
    for (k = 1; k <= t; k++)
        for (i = n; i >= 0; i--)
            for (j = 1; j <= a[k][0]; j++)
                if (i >= w[a[k][j]])
                    f[i] = max(f[i], f[i - w[a[k][j]]] + c[a[k][j]]);
    cout << f[n] << endl;
}

图

图的存储——邻接矩阵

// 邻接矩阵
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1000;
int n;
int v[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (v[i][j] > 0)
            {
                printf("顶点%d到顶点%d的权重是%d\n", i, j, v[i][j]);
            }
        }
    return 0;
}

图的存储——邻接表

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int N = 1000;

struct edge
{
    int to, cost;
};

int n, m; // n-顶点， m-边
vector<edge> p[N];
int v[N][N];

int main()
{
    scanf("%d %d", n, m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, l;
        cin >> u >> v >> l;
        p[u].push_back((edge){v, l});
    }

    // 邻接表 -> 邻接矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= p[i].size(); j++)
            v[i][p[i][j].to] = p[i][j].cost;
    // 输出
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            printf("%d ", v[i][j]);
        printf("\n");
    return 0;
}

P1551 亲戚

#include <iostream>

using namespace std;

int n, m, p, x, y, family[5010];

int find(int x)  // 检查是否为同一家族
{
    if (x == family[x])
        return x;
    return family[x] = find(family[x]);
}

void join(int c1, int c2)  // 连接两个家族
{
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2)
        family[f1] = f2;
}

int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        family[i] = i;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        join(x, y);
    }
    for (int i = 0; i < p; i++)
    {
        cin >> x >> y;
        if (find(x) == find(y))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 101
#define MOD 123
#define E 1e-6
int tree[101];
using namespace std;
int main()
{
    int n,m;
    int x,y;
 
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        tree[y]=x;
    }
 
    int root;
    for(int i=1;i<=n;i++)
        if(tree[i]==0)
        {
            root=i;
            break;
 
        }
    int maxx=-INF;
    int maxroot;
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<=n;j++)
            if(tree[j]==i)
                sum++;
        if(maxx<sum)
        {
            maxx=sum;
            maxroot=i;
        }
    }
 
    cout<<root<<endl;
    cout<<maxroot<<endl;
    for(int i=1;i<=n;i++)
        if(tree[i]==maxroot)
            cout<<i<<" ";
    cout<<endl;
 
    return 0;
}

二叉树

若根节点的层数为1，则一棵非空二叉树的第i层的节点数最多为2^(i-1)个。

若根节点的层数为1，则一棵深度为k二叉树的节点数最多为2^k-1个。

二叉树遍历

#include <iostream>

using namespace std;

typedef struct _TreeNode
{
    char _data;
    struct _TreeNode *_left;
    struct _TreeNode *_right;
} TreeNode;

void preOrder(TreeNode *root)
{
    if (root)
    {
        cout << root->_data << ' ';
        preOrder(root->_left);
        preOrder(root->_right);
    }
}

void midOrder(TreeNode *root)
{
    if (root)
    {
        preOrder(root->_left);
        cout << root->_data << ' ';
        preOrder(root->_right);
    }
}

void postOrder(TreeNode *root)
{
    if (root)
    {
        preOrder(root->_left);
        preOrder(root->_right);
        cout << root->_data << ' ';
    }
}



int main()
{
    return 0;
}

位运算

按位与运算

&

1 & 1 = 1
1 & 0 = 0 & 1 = 0 & 0 = 0

按位或运算

|

0 | 0 = 0
1 | 0 = 0 | 1 = 1 | 1 = 1

按位异或运算

^

1 ^ 1 = 0 ^ 0 = 1
1 ^ 0 = 0 ^ 1 = 0

按位取反运算

~
~1 = 0
~0 = 1

链表

int链表的头文件是<list>，有以下方法：

队列(queue)

约瑟夫问题

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;
int n, k;

void f()
{
    int i;
    for (i = 1; i <= n; i++)
        q.push(i);
    while (q.size() != 1)
    {
        for (i = 1; i < k; i++)
        {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ' ';
        q.pop();
    }
}

int main()
{
    cin >> n >> k;
    f();
    cout << q.front() << endl;
    return 0;
}

栈(stack)

// 括号匹配
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>

using namespace std;

stack <char> s;
int n;

char trans(char a)
{
    if (a == ')')
        return '(';
    if (a == ']')
        return '[';
    if (a == '}')
        return '{';
    return '\0';
}

int main()
{
    cin >> n;
    string s1;
    getline(cin, s1);
    while (n--)
    {
        while (!s.empty())
        {
            s.pop();
        }
        getline(cin, s1);
        for (int i = 0; i < s1.size(); i++)
        {
            if (s.empty())
            {
                s.push(s1[i]);
                continue;
            }
            if (trans(s1[i]) == s.top())
                s.pop();
            else
                s.push(s1[i]);
        }
        if (s.empty())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

// 后缀表达式
#include <iostream>
#include <stack>

using namespace std;

stack<int> n;
int s = 0, x, y;

int main()
{
    char ch;
    do
    {
        ch = getchar();
        if (ch >= '0' && ch <= '9')
            s = s * 10 + ch - '0';
        else if (ch == '.')
            n.push(s), s = 0;
        else if (ch != '@')
        {
            x = n.top();
            n.pop();
            y = n.top();
            n.pop();
            switch (ch)
            {
            case '+':
                n.push(x + y);
                break;
            case '-':
                n.push(y - x);
                break;
            case '*':
                n.push(x * y);
                break;
            case '/':
                n.push(y / x);
                break;
            }
        }
    } while (ch != '@');
    cout << n.top() << endl;
    return 0;
}

vector

询问学号

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m, stu;
    vector<int> a;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> stu;
        a.push_back(stu);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> stu;
        cout << a[stu - 1] << endl;
    }
    return 0;
}

考前临时抱佛脚

#include <iostream>

using namespace std;

int maxtime, nowtime, maxdeep, sumtime, ans, s[4], a[21];

void dfs(int x)
{
    if (x > maxdeep)
    {
        maxtime = max(maxtime, nowtime);
        return;
    }
    if (nowtime + a[x] <= sumtime / 2)
    {
        nowtime += a[x];
        dfs(x + 1);
        nowtime -= a[x];
    }
    dfs(x + 1);
}

int main()
{
    cin >> s[0] >> s[1] >> s[2] >> s[3];
    for (int i = 0; i < 4; i++)
    {
        nowtime = 0;
        maxdeep = s[i];
        sumtime = 0;
        for (int j = 1; j <= s[i]; j++)
        {
            cin >> a[j];
            sumtime += a[j];
        }
        maxtime = 0;
        dfs(1);
        ans += sumtime - maxtime;
    }
    cout << ans << endl;
    return 0;
}

搜索 - 八皇后

// n皇后问题，只返回方案数
#include <iostream>

using namespace std;

int a[100], n, ans = 0, b1[100], b2[100], b3[100];

void dfs(int x)
{
    if (x > n)
    {
        ans++;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (b1[i] == 0 && b2[x + i] == 0 && b3[x + 15 - i] == 0)
        {
            a[x] = i;
            b1[i] = 1;
            b2[x + i] = 1;
            b3[x + 15 - i] = 1;
            dfs(x + 1);
            b1[i] = 0;
            b2[x + i] = 0;
            b3[x + 15 - i] = 0;
        }
    }
}

int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}

大学计算机基础mooc

点击进入

5 和 7 不用看

二分查找

#include <iostream>
#include <cstdio>

using namespace std;

long long a[10000000], n, m, q;

int find(int x)
{
    int l = 1, r = n + 1;
    while (l < r)
    {
        int mid = (l + r) / 2; // 中间值
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (a[l] == x)
        return l;
    else
        return -1;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> q;
        cout << find(q) << ' ';
    }
    return 0;
}

一、单项选择题 1-5 DDBBB 6-10 AACDC 11-15 BBCCA 二、阅读程序题 16 (1)F(2)F(3)T(4)T(5)F(6)B 17 (1)F(2)T(3)C(4)D 18 (1)T(2)F(3)T(4)B(5)D 三、完善程序题 19 (1)A(2)A(3)A(4)C(5)D 20 (1)A(2)D(3)B(4)B(5)C

贪心例题

// 排队接水
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

struct water
{
    int num, time;
} a[10000];

bool compare(water x, water y)
{
    if (x.time != y.time)
        return x.time < y.time;
    return x.num < y.num;
}

int main()
{
    int n;
    long long sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].time;
        a[i].num = i;
    }
    sort(a + 1, a + n + 1, compare);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i].num << ' ';
        sum += i * a[n - i].time;
    }
    printf("\n%.2lf\n", 1.0 * sum / n);
    return 0;
}

// 数的计算
#include <iostream>

using namespace std;

int solve(int x)
{
    if (x == 1)
        return 1;
    int ans = 1;
    for (int i = 1; i <= x / 2; i++)
        ans += solve(i);
    return ans;
}

int main()
{
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

/*
有一个单端封闭的管子，将 𝑁(1 ≤ 𝑁 ≤ 18)个不同的小球按顺序放 入管子的一端。在将小球放入管子的过程中也可以将管子最顶上 的一个或者多个小球倒出来。
请问倒出来方法总数有多少种?
*/


#include <iostream>

using namespace std;

int main()
{
    int N, f[28] = {1, 1};
    cin >> N;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            f[i] += f[j] * f[i - j - 1];
        }
    }
    cout << f[N] << endl;
    return 0;
}

Bigint结构体

#include <iostream>

using namespace std;
#define maxn 100
struct Bigint
{
    int len, a[maxn];
    Bigint(int x = 0)
    {
        memset(a, 0, sizeof(a));
        for (len = 1; x; len++)
        {
            a[len] = x % 10, x /= 10;
        }
        len--;
    }
    int &operator[](int i)
    {
        return a[i];
    }
    void flatten(int L)
    {
        len = L;
        for (int i = 1; i <= len; i++)
            a[i + 1] += a[i] / 10, a[i] %= 10;
        for (; !a[len];)
            len--;
    }
    void print()
    {
        for (int i = max(len, 1); i >= 1; i--)
            printf("%d", a[i]);
    }
};

重载 “+” 运算符

Bigint operator+(Bigint a, Bigint b)
{
    Bigint c;
    int len = max(a.len, b.len);
    for (int i = 1; i <= len; i++)
    {
        c[i] = a[i] + b[i];
    }
    c.flatten(len + 1);
    return c;
}

给个预告： 1，明天我会发布本人新游戏（更新了人物和装备） 敬请期待🎉️ 🎉️

老夫聊发少年狂，左牵黄，右擎苍，锦帽貂裘，千骑卷平冈。为报倾城随太守，亲射虎，看孙郎。

酒酣胸胆尚开张，鬓微霜，又何妨！持节云中，何日遣冯唐？会挽雕弓如满月，西北望，射天狼。

风住尘香花已尽，日晚倦梳头。物是人非事事休，欲语泪先流。

闻说双溪春尚好，也拟泛轻舟。只恐双溪舴艋舟，载不动许多愁。

你站在桥上看风景，看风景的人在楼上看你，明月装饰了你的窗子，你装饰了别人的梦。

轻轻的我走了， 正如我轻轻的来； 我轻轻的招手， 作别西天的云彩。

那河畔的金柳， 是夕阳中的新娘； 波光里的艳影， 在我的心头荡漾。

软泥上的青荇， 油油的在水底招摇； 在康河的柔波里， 我甘心做一条水草！

那榆荫下的一潭， 不是清泉，是天上虹； 揉碎在浮藻间， 沉淀着彩虹似的梦。

寻梦？撑一支长篙， 向青草更青处漫溯； 满载一船星辉， 在星辉斑斓里放歌。

但我不能放歌， 悄悄是别离的笙箫； 夏虫也为我沉默， 沉默是今晚的康桥！

悄悄的我走了， 正如我悄悄的来； 我挥一挥衣袖， 不带走一片云彩。

众里寻他千百度，蓦然回首，那人却在，灯火阑珊处。

为什么我的眼里常含泪水，因为我对这土地爱得深沉

选择排序

// 选择排序
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[i])
                swap(a[i], a[j]);
        }       
    }

冒泡排序

// 冒泡排序
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j + 1] < a[j])
                swap(a[j], a[j + 1]);
        }
    }

插入排序

// 插入排序
    for (int i = 0; i < n; i++)
    {
        int new_num = a[i], j;
        for (j = i - 1; j >= 0; j--)
        {
            if (a[j] > new_num)
                a[j + 1] = a[j];
            else
                break;
        }
        a[j + 1] = new_num;
    }

快速排序

// 快排
void quick_sort(int a[], int l, int r)
{
    int i = l, j = r, flag = a[(l + r) / 2];
    do
    {
        while (a[i] < flag)
            i++;
        while (a[j] > flag)
            j--;
        if (i <= j)
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j)
        quick_sort(a, l, j);
    if (i < r)
        quick_sort(a, i, r);
}

计数排序例题

// luogu P1271 选举学生会
#include <iostream>
using namespace std;
int main()
{
    int n, m, a[2000010] = {0}, tmp;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> tmp;  // 输入候选人编号
        a[tmp]++;    // 票数增加
    }

    for (int j = 1; j <= n; j++)
    {
        for (int i = 0; i < a[j]; i++)
            cout << j << ' ';
    }
    return 0;
}

void quickSort(int left, int right, vector<int>& arr)
if(left >= right)
		return;
	if(left < 0 || right >= arr.size())	{
		cout << "error args! array bound." << endl;
		return;
	}
	int i, j, base, temp;
	i = left, j = right;
	base = arr[left];
	while (i < j){
		while (arr[j] <= base && i < j)
			j--;
		while (arr[i] >= base && i < j)
			i++;
		if(i < j){
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);
	quickSort(i + 1, right, arr);
}

#include <iostream>
#include <string>
using namespace std;
int a[510], b[510], c[510];
int main()
{
    string A, B;
    cin >> A >> B;
    for (int i = 1, j = A.length() - 1; j >= 0; i++, j--)
    {
        a[i] = A[j] - '0'; 
    }
    for (int i = 1, j = B.length() - 1; j >= 0; i++, j--)
    {
        b[i] = B[j] - '0';
    }
    for (int i = 0; i < A.length(); i++)
    {
        for(int j=0;j<B.length();j++)
        	c[i+j]+=a[i]*b[j];
    }
    int lenc=A.length()+B.length();
    for(int i=1;i<=lenc;i++){
    	c[i+1]=c[i]/10;
    	c[i]%=10;	
	}
	for(;!c[lenc];)
		lenc--;
    for (int i=max(1,lenc);i>=1;i--)
        cout << c[i];
    return 0;
}

// A*B problem 高精度
#include <iostream>
#include <string>
using namespace std;
int a[5000], b[5000], c[5000];
int main()
{
    string A, B; // A = 123456
    cin >> A >> B;

    for (int i = A.length() - 1; i >= 0; i--)
    {
        a[A.length() - i] = A[i] - '0';
    }
    for (int i = B.length() - 1; i >= 0; i--)
    {
        b[B.length() - i] = B[i] - '0';
    }
    //  高精度乘法
    for (int i = 0; i < A.length(); i++)
        for (int j = 0; j < B.length(); j++)
            c[i + j] += a[i] * b[j];

    int lenc = A.length() + B.length();

    for (int i = 1; i <= lenc; i++)
    {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }

    for (; !c[lenc];) 
        lenc--;

    for (int i = max(1, lenc); i >= 1; i--)
        cout << c[i];
    return 0;
}

#include<iostream>
using namespace std;
int main(){
	int k,n=1;
	cin>>k;
	double sn=0;
	do
	{
		sn+=1.0/n;
		n++;
	}while(sn<=k);
	cout<<n-1<<endl;
	return 0;
}

p497

// A+B problem 高精度
#include <iostream>
#include <string>
using namespace std;
int a[510], b[510], c[510];
int main()
{
    string A, B; // A = 123456
    cin >> A >> B;
    int len = max(A.length(), B.length());
    for (int i = 1, j = A.length() - 1; j >= 0; i++, j--)
    {
        a[i] = A[j] - '0'; 
    }
    for (int i = 1, j = B.length() - 1; j >= 0; i++, j--)
    {
        b[i] = B[j] - '0';
    }
    //  高精度加法
    for (int i = 1; i <= len; i++)
    {
        c[i] += a[i] + b[i];
        c[i + 1] = c[i] / 10;
        c[i] = c[i] % 10;
    }
    if (c[len + 1])
        len++;
    for (int i = len; i >= 1; i--)
        cout << c[i];
    return 0;
}

😄 我作业写完了