头像

黎虽无意逐鹿




离线:2天前


最近来访(8)
用户头像
Mup丶Superman
用户头像
小huohuo
用户头像
ndream
用户头像
郭翔宇
用户头像
acwing_8436

活动打卡代码 AcWing 3284. 化学方程式

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

typedef unordered_map<string,int> MPSI;

MPSI dfs(string& str,int& u)
{//解析  Ba3(PO4)2
    MPSI res;
    while(u < str.size())
    {
        //处理 (
        if(str[u] == '(')
        {
            u ++;//过滤掉(
            auto t = dfs(str,u);
            u ++;//过滤掉 )
            //双指针 处理括号后的数字
            int cnt = 1 , k = u;
            while(k < str.size() && isdigit(str[k])) k++;
            if(k > u)
            {
                cnt = stoi(str.substr(u,k - u));
                u = k;
            }
            for(auto c: t)
                res[c.x] += c.y * cnt;
        }
        else if(str[u] == ')')break;
        //一般情况,是字母Ba3  从大写字母开始到小写字母为一个关键词
        else
        {
            int k = u + 1;
            //双指针 跑到小写字母之后
            while(k < str.size() && str[k] >= 'a' && str[k] <= 'z')k++;
            auto key = str.substr(u,k - u);
            u = k;
            //处理 关键词后的数字
            int cnt = 1;
            while(k < str.size() && isdigit(str[k]))k ++;
            if(k > u)
            {
                cnt = stoi(str.substr(u,k - u));
                u = k;
            }
            res[key] += cnt;
        }
    }
    return res;
}
MPSI fun(string str)
{
    MPSI res;
    for(int i = 0; i < str.size(); i ++)
    {
        int j = i + 1;
        //双指针 找到+号
        while(j < str.size() && str[j] != '+') j++;
        //处理当前+号之前的字符
        auto item = str.substr(i,j - i);
        i = j; //i跳到+号的位置
        //双指针 找出开头的数字 例如2H2 默认是1
        int cnt  = 1 , k = 0;
        while(k < item.size() && isdigit(item[k])) k++; //isdigit() 判断一个字符是不是数字
        //如果前面存在数字,就把数字提取出来
        if(k) cnt = stoi(item.substr(0,k));    
        //用dfs解析出item中前缀不包含数字项的其他项 例如2H2 => H2
        auto t = dfs(item,k);
        //遍历t中的每一项关键字
        for(auto c : t)
            res[c.x] += c.y * cnt;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string str;
        cin>>str;
        int k = str.find('=');
        auto left = fun(str.substr(0,k)),right = fun(str.substr(k+1));
        if (left == right) puts("Y");
        else puts("N");
    }
    return 0;
}


活动打卡代码 AcWing 3282. 报数

#include<bits/stdc++.h>
using namespace std;
int ans[4];
int main()
{
    int n , i = -1,k = 0; 
    cin>>n;
    while(n)
    {
        i++;
        k++;
        if(k % 7 == 0 || to_string(k).find('7') != -1)ans[i % 4] ++;
        else n--;
    }
    for(int i = 0 ; i < 4; i ++)cout << ans[i] << endl;
    return 0;
}


活动打卡代码 AcWing 3283. 回收站选址

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1100;
typedef pair<int,int>PII;
PII q[N];
int ans[5],s[8];
int dx[8] = {-1,-1,-1,0,1,1,1,0},
    dy[8] = {-1, 0, 1,1,1,0,-1,-1};
int main()
{
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i ++)cin>>q[i].x>>q[i].y;
    for(int i = 0 ; i < n ; i ++)//枚举每个点作为垃圾回收站
    {
        int s[8] = {0};//存储八个方位垃圾个数
        for(int j = 0 ; j < n ; j ++)//检查其他垃圾点点
            for(int k = 0; k < 8 ; k++)//遍历八个方位看看有无垃圾
                if(q[i].x + dx[k] == q[j].x && q[i].y + dy[k]==q[j].y)
                    s[k]++;
        //是垃圾点,计算分数(四个角的垃圾总数)
        if(s[1] && s[3] && s[5] && s[7])
            ans[s[0] + s[2] + s[4] + s[6]] ++;
    }
    for(int i = 0 ; i < 5 ; i++)cout<<ans[i]<<endl;
    return 0;
}


活动打卡代码 AcWing 839. 模拟堆

//映射+手写堆
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int h[N],hp[N],ph[N],Size,m;
void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
void down(int x)
{
    int t = x;
    if(2*x<=Size && h[2*x] <= h[t])t=2*x;
    if(2*x+1<=Size &&h[2*x + 1] <= h[t]) t=2*x + 1;
    if(t != x)
    {
        heap_swap(t,x);
        down(t);
    }
}
void up(int u)
{
    while(u/2 && h[u/2] > h[u])
    {
        heap_swap(u/2,u);
        u/=2;
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {   char op[10];
        int k,x;
        scanf("%s",op);
            if(!strcmp(op,"I")){//插入一个数到堆中
                cin>>x;
                Size ++;
                m ++;
                ph[m] = Size; hp[Size] = m;
                h[Size] = x;
                up(Size);
            }else if (!strcmp(op,"PM"))//输出最小值h[1]
                cout<<h[1]<<endl;
            else if (!strcmp(op,"DM")){//删除最小值h[1]
                heap_swap(1,Size);
                Size --;
                down(1);
            }else if(!strcmp(op,"D")){//删除h[k];
                cin>>k; 
                k = ph[k];
                heap_swap(k,Size);
                Size --;
                down(k);
                up(k);
            }else{//修改h[k]为x
                scanf("%d%d",&k,&x);
                k = ph[k];
                h[k] = x;
                down(k);
                up(k);
            }
    }
    return 0;
}



/*并查集
三中基本操作:
1.如何判断树根:if(p[x] == x)
2.如何求x的集合编号 while(p[x] !=x ) x = p[x];
3.如何合并两个集合: p[x] = y;
连通块点的个数:只要保证祖宗的size有意义即可
                合并的时候 size[find(b)] += size[find(a)]
*/
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
//返回x的祖宗
int p[N]; 
int n,m;
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int size[N];
    char op[5];
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i] = i,size[i] =1;
    while(m--)
    {
        scanf("%s",op);
        int a,b;
        if(op[0] == 'C')
        {
            scanf("%d%d",&a,&b);
            //特判:如果a b已经在同一个集合中
            if(find(a) == find(b))continue;
            size[find(b)] += size[find(a)];
            p[find(a)] = find(b);
        }
        else if(op[1] == '1')
        {
            scanf("%d%d",&a,&b);
            if(find(a) == find(b))puts("Yes");
            else puts("No");
        }
        else
        {
            scanf("%d",&a);
            cout<<size[find(a)]<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

在区间[l,r]中二分答案 l - r < 1e-8表示精确度

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double l = -10000,r = 10000;
    while(r - l > 1e-8)
    {
        double m = (l + r)/2;
        if(m*m*m >= x)r = m;
        else l = m;
    }
    printf("%lf",l);
    return 0;
}



【问题描述】

给定一个方形整数数组 A,我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

【输入形式】

第一行输入数组的大小n,第二行以后输入的n行分别是数组的第n行元素

【输出形式】

输出1行中含有一个数字,表示最短下降路径和。

【样例输入】

3

2 1 3

6 5 4

7 8 9
【样例输出】

13

【题解】
最短 下降路径
DP:1.状态表示
1.1集合:f[i][j] 从第1行到点(i,j)的下降路径和
1.2属性:Min
2.状态计算:f[i][j]可以由
min(f[i-1][j] , f[i-1][j-1], f[i-1][j+1]) + g[i][j]转移

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,g[N][N];
int f[N][N];
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin>>g[i][j];
    //初始化
    for(int j = 1 ; j <= n; j++)f[1][j] = g[1][j];

    for(int i = 2 ; i <= n; i ++)
        for(int j = 1 ; j <= n; j ++)
        {
            f[i][j] = f[i-1][j];
            if(j-1>=1)f[i][j] = min(f[i][j],f[i-1][j-1]);
            if(j+1<=n)f[i][j] = min(f[i][j],f[i-1][j+1]);
            f[i][j] += g[i][j]; 
        }
    int res = 1e9;
    for(int i = 1 ; i <= n ; i ++)
        res = min(res,f[n][i]);
    cout<<res;
    return 0;
}



【问题描述】给定n个矩阵M1,M2…Mn,他们的维数分别是r1c1,r2c2…rn*cn,要求使用【动态规划】的策略求解矩阵连乘的最优计算代价(总乘法次数最少)。题目保证矩阵相乘一定是有效的。

例如有三个矩阵M1,M2,M3,他们的维度分别是210,102,210。按照矩阵乘法的结合律,可以先把M1和M2相乘,然后把结果和M3相乘,总的乘法次数为2102+2210=80次;也可以先把M2和M3相乘,再用M1去相乘,这种方式下总的乘法次数为10210+210*10=400次。因此最优计算代价为80。
【输入形式】输入的第1行中有1个数字n,表示矩阵的个数;接下来n行,每行2个整数ri和ci,分别表示矩阵Mi的行数和列数。
【输出形式】输出1行中有一个数字,表示n个矩阵相乘的最优计算代价。
【样例输入】

3

2 10

10 2

2 10
【样例输出】

80

矩阵链,求最小乘法次数
DP:
1.状态表示:
1.1 集合:f[i][j] : 表示从矩阵Mi 到矩阵Mj (i<j)的相乘次数
1.2 属性:Min
2 状态计算:Ai…j = Ai…k * Ak+1 …j
枚举区间长度 len from 2 to n
将f[i][j]划分为 i i+1 … k … j-1子集和 k从i枚举到j-1
f[i][j] = min(f[i][k] + f[k+1][j] + p[i-1]p[k]p[j] ,f[i][j])

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
struct Mat{
    int r,c;
}mat[N];
int main()
{
    int n, f[N][N];
    int p[N];
    cin>>n;
    for(int i = 1 ; i <= n ; i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        p[i-1] = a ; p[i] = b;
    }
    for(int len = 2 ; len <= n; len ++)
    {
        for(int i = 1; i <= n - len + 1 ; i ++)
        {//j - i + 1 = len
            int j = i + len -1;
            f[i][j] = 1e9;
            for(int k = i; k <= j - 1; k ++)
            {
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}



【问题描述】给定无向连通图G和m种不同的颜色,用这些颜色给图的各个顶点着一种颜色,若某种方案使得图中每条边的2个顶点的颜色都不相同,则是一个有效方案。请使用回溯法编程找出所有的有效方案。

【输入形式】输入的第一行有3个正整数n,m和k,分别表示图G中有n个顶点,m条边,k种颜色。接下来m行,每行中有2个整数i,j,表示节点i和节点j之间存在一条边(节点编号从1开始)。

【输出形式】输出1行包含1个正整数,表示所有的着色方案数。
【样例输入】

5 7 3

1 2

1 3

2 4

2 5

3 4

3 5

4 5

【样例输出】

12

#include<bits/stdc++.h>
using namespace std;
int n , m, k;
const int N = 1e5+10;   
int h[N],e[N],ne[N],idx;
int color[N];//color[i] 表示第i个点的颜色 
int ans;
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++; 
}
//判断点u能否染上颜色co
bool check(int u,int co)
{
    //检查相邻点的颜色
    for(int i = h[u] ; i != -1; i = ne[i])
    {
        int j = e[i];
        if(color[j] == co)return false;
    }
    color[u] = co;
 return true;
}
void dfs(int x)
{
    //递归出口
    if(x == n + 1)
    {
        ans++; 
        return;
    }
    //依次遍历颜色,染上合适的颜色 
      for(int i = 1 ;i <= k ; i ++) 
      {
        if(check(x,i))
        {
            dfs(x+1);
        }
        color[x] = 0;
      }

}
int main()
{
    memset(h,-1,sizeof h); 

    cin>>n>>m>>k;
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);//无向图 
    }

    dfs(1);
    cout<<ans;
    return 0;
}



输入N,输出N皇后问题的可能解的个数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int res;
int c[N];
bool check(int row,int col)
{
    for(int i = 1; i < row; i ++)
    {
        if(c[i] == col || abs(row - i) == abs(col - c[i]))return false;
    }
    return true;
}
void dfs(int x)
{
    //递归出口 
    if(x == n + 1) res++; 
    else
    {
        //在row = x 寻找合适的能够放皇后的 col 
        for(int i = 1 ; i <= n ; i++)
        {
            c[x] = i;
            //如果该位置可以放皇后 
            if(check(x,c[x]))
                dfs(x +1);
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<res;
    return 0;
}