头像

不刷完课不改名




离线:8小时前


最近来访(31)
用户头像
StarLi9ht
用户头像
诚_7
用户头像
Resurgence1001
用户头像
V1
用户头像
su尔
用户头像
海问香
用户头像
李玉钊
用户头像
Data_Rookie
用户头像
手写的从前_2
用户头像
是如果说
用户头像
acwing_9231
用户头像
yxc
用户头像
搁浅_1
用户头像
一直很相信
用户头像
Silence_57
用户头像
曙光女神
用户头像
繁星_9
用户头像
Paradox.
用户头像
该训练了
用户头像
数论贪心图论DP通通不会

活动打卡代码 AcWing 845. 八数码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int bfs(string start)
{
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        int distance = d[t];
        if(t == end) return distance;

        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[k], t[a * 3 + b]);
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main()
{
    string c, start;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;
    return 0;
}


活动打卡代码 AcWing 4504. 字符串消除

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

using namespace std;

int res;

int main()
{
    string str, stk;
    cin >> str;

    for(auto c: str)
    {
        if(stk.back() == c)
        {
            res ++ ;
            stk.pop_back();
        }
        else stk += c;
    }

    if(res % 2) puts("Yes");
    else puts("No");
    return 0;
}



高精度加法 分为两种情况:压位,不压位

高精度压位运算

压位和不压位的高精度计算存在三点不同点(以下提到的压位都是压4位):

(1)存储:不压位的话,vector或者数组中每个数据是0~9;压位以后,每个数据是0~9999。

(2)计算过程:不压位的话,除数和模数都是10;压位以后,除数和模数都是10000。

(3)输出:不压位的话,直接输出;压位的话,需要格式化输出,最高位直接输出即可,其他位都需要输出4位数字,不足的前面补零

高精度加法

从前往后 位数大的作为A,t存储进位
从前往后遍历整个C数组 C中存储t % 10的值 从低位开始

#include<bits/stdc++.h>
using namespace std;

vector <int> add(vector <int> &A,vector<int> &B)
{
    if(A.size() < B.size()) add(B, A);//A的位数必须大于B的位数

    vector<int> C;//存答案
    int t = 0;//存储进位
    for(int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);

    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>> a >> b;

    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    vector<int> c = add(A, B);
    for(int i = c.size() - 1; i >= 0; i -- ) cout << c[i];
    cout<<endl;


    return 0;
}

压九位代码

#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % base);
        t /= base;
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }

    auto C = add(A, B);

    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
    cout << endl;

    return 0;
}

高精度乘法拓展版本

高精度x低精度

同样从小到大遍历数组 进位存储每一位与低精度

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() || t; i ++ )
    {
        if(i < A.size()) t += A[i] * b;//关键步骤
        C.push_back(t % 10);
        t /= 10;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导零 否则会出现00000 的情况
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');


    auto C = mul(A, b);
    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl;
    return 0;
}

高精度x高精度

从小到大遍历

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> C(A.size() + B.size() + 7, 0);

    for(int i = 0; i < A.size(); i ++ )
        for(int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];

    int t = 0;
    for(int i = 0; i < C.size(); i ++ )
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0 ; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0 ; i -- ) B.push_back(b[i] - '0');

    auto C = mul(A, B);

    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    return 0;
}

高精度减法

需要先存在一个比较函数 如果AB位数不等则返回A位数大于B
如果AB位数相等 判断各个字符是否相等 不等则返回A[i] > B[i]
输出模10以后的数

#include <iostream>
#include <vector>
using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();

    for(int i = A.size() - 1; i >= 0; i -- )
        if(A[i] != B[i]) return A[i] > B[i];

        return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;


    for(int i = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;//当借位为0 把其值赋为A[i]
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a,b;
    cin >> a >> b;
    vector<int> A, B;

    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    vector<int> C;
    if(cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl;
    return 0;
}

高精度除法(有些许不同)

从后往前遍历 输出r/b的答案 r = r * 10 + A[i]
最后利用reverse函数 调换顺序

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

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for(int i = A.size() - 1; i >= 0; i --) 
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());//之所以需要reverse 因为遍历是从后往前遍历的 先算高位
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}


int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;

    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r = 0;
    auto C = div(A, b ,r);

    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl << r <<endl;
    return 0;

}



###务必初始化
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5+10, M = 2*N;

int n, m;
int color[N];
int e[M],ne[M],idx,h[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u,int c)
{
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i] )
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 - c)) return false;
        }
        else if(color[j] == c) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    for(int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b),add(b, a);
    }

    bool flag = true;
    for(int i = 1; i <= n; i ++ )
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag = false;
                break;
            }
        }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}



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

using namespace std;
const int N = 1e5+10, M = 2e5+10, INF = 0x3f3f3f3f;

int n, m;
int p[N];
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &W)const
    {
        return w< W.w;
    }
}edges[M];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int krustra()
{
    sort(edges, edges + m);//按权重进行排序 所以要重载<号
    for(int i = 1; i <= n; i ++ ) p[i] = i;

    int cnt = 0,res = 0;
    for(int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);

        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }

    if(cnt < n-1) return INF;
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m ;i ++ )
    {
        int a, b, w;
        cin >>a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t=krustra();

    if(t == INF) puts("impossible");
    else printf("%d", t);

    return 0;
}



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

using namespace std;

const int N = 510,INF = 0x3f3f3f3f;

int g[N][N];
int n, m;
int dist[N];//各个节点到生成树距离
bool st[N];//是否被加到生成树中

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;//存答案
    for(int i = 0; i < n ;i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
        if(!st[j]&&(t == -1 || dist[t] > dist[j]))//当前点未走过 或者 第一个数或者 当前到集合中的点不是最短路 
        t = j;//不在集合中距离最近的点

        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];

        st[t] = true;

        for(int j = 1; j <= n; j ++ )
        dist[j] = min(dist[j], g[t][j]);

    }

    return res;
}

int main()
{
    cin >> n >>m;
    memset(g, 0x3f, sizeof g);

    while(m -- )
    {
        int a, b, w;
        cin >> a >> b>> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    int t = prim();

    if(t == INF) puts("impossible");
    else printf("%d", t);

    return 0;
}



···

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 510,INF = 0x3f3f3f3f;

int g[N][N];
int n, m;
int dist[N];//各个节点到生成树距离
bool st[N];//是否被加到生成树中

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;//存答案
for(int i = 0; i < n ;i ++ )
{
    int t = -1;
    for(int j = 1; j <= n; j ++ )
    if(!st[j]&&(t == -1 || dist[t] > dist[j]))//当前点未走过 或者 第一个数或者 当前到集合中的点不是最短路 
    t = j;//不在集合中距离最近的点

    if(i && dist[t] == INF) return INF;
    if(i) res += dist[t];

    for(int j = 1; j <= n; j ++ )
    dist[j] = min(dist[j], g[t][j]);
    st[t] = true;
}

return res;

}

int main()
{
cin >> n >>m;
while(m – )
{
int a, b, w;
cin >> a >> b>> w;
g[a][b] = g[b][a] = min(g[a][b], w);
}

int t = prim();

if(t == INF) puts("impossible");
else printf("%d", t);

return 0;

}
···



活动打卡代码 AcWing 901. 滑雪

···

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
const int N = 310;
int n,m; //网格滑雪场的行和列
int f[N][N]; //状态转移式
int h[N][N]; //网格滑雪场
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int x,int y){
int &v = f[x][y]; //Y总说的小技巧,等于把f[x][y]简化成了v,如果v发生变化,f[x][y]也会随之变化
if(v != -1) return v; //如果已经计算过了,就可以直接返回答案
v = 1; //注意v要先赋值为1哦~
for(int i = 0;i < 4;i ){ //四个方向
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走
v = max(v,dp(xx,yy) + 1); //更新
}
}
return v; //别忘了返回v啊(被坑了
}
int main(){
cin>>n>>m; //输入滑雪场行和列
for(int i = 1;i <= n;i
){
for(int j = 1;j <= m;j ){
cin>>h[i][j]; //读入滑雪场数据
}
}
memset(f,-1,sizeof f);
int res = 0; //最后答案
for(int i = 1;i <= n;i
){
for(int j = 1;j <= m;j ++){
//因为这个人可以在任意一点开始滑,所以要遍历一遍滑雪场
res = max(res,dp(i,j)); //更新答案
}
}
cout<<res<<endl;
return 0;
}
···




···

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //上面有解释哦~
int e[N],ne[N],h[N],idx; //链表,用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点
void add(int a,int b){ //把a插入树中
e[idx] = b,ne[idx] = h[a],h[a] = idx ;
}
void dfs(int u){ //开始求解题目
f[u][1] = happy[u]; //如果选当前节点u,就可以把f[u,1]先怼上他的高兴度
for(int i = h[u];~i;i = ne[i]){ //遍历树
int j = e[i];
dfs(j); //回溯
//状态转移部分,上面有详细讲解~
f[u][0] += max(f[j][1],f[j][0]);
f[u][1] += f[j][0];
}
}
int main(){
scanf(“%d”,&n);
for(int i = 1;i <= n;i
) scanf(“%d”,&happy[i]); //输入每个人的高兴度
memset(h,-1,sizeof h); //把h都赋值为-1
for(int i = 1;i < n;i ){
int a,b; //对应题目中的L,K,表示b是a的上司
scanf(“%d%d”,&a,&b); //输入~
has_father[a] = true; //说明a他有爸爸(划掉)上司
add(b,a); //把a加入到b的后面
}
int root = 1; //用来找根节点
while(has_father[root]) root
; //找根节点
dfs(root); //从根节点开始搜索
printf(“%d\n”,max(f[root][0],f[root][1])); //输出不选根节点与选根节点的最大值
return 0;
}

···



活动打卡代码 AcWing 91. 最短Hamilton路径

···

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N=20,M=1<<N;

int f[M][N],w[N][N];//w表示的是无权图

int main()
{
int n;
cin>>n;

for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
  cin>>w[i][j];

memset(f,0x3f,sizeof(f));//因为要求最小值,所以初始化为无穷大
f[1][0]=0;//因为零是起点,所以f[1][0]=0;

for(int i=0;i<1<<n;i++)//i表示所有的情况
 for(int j=0;j<n;j++)//j表示走到哪一个点
  if(i>>j&1)
   for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离
    if(i>>k&1)
     f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离

cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
//位运算的优先级低于'+'-'所以有必要的情况下要打括号
return 0;

}

···