头像

黎虽无意逐鹿




离线:1天前


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


//(总数 - 摘数) - 掉落 = 剩余
//掉落 = (总数 - 摘数) - 剩余

include[HTML_REMOVED]

using namespace std;
const int N = 1010;
vector[HTML_REMOVED] q[N];// q[i][j] 表示第i棵树第j次操作是什么
bool st[N];
int n;
//返回第k次操作开始往后的摘掉的总和
int get(vector[HTML_REMOVED]& a,int k)
{
int res = a[k];
for(int i = k + 1 ; i < a.size() ; i )
{
if(a[i] <= 0)
{
res += a[i];
}
}
return res;
}
int main(){
cin>>n;
for(int i = 0 ; i < n ; i
)
{
int k;
cin>>k;
while(k –)
{
int x;
scanf(“%d”,&x);
q[i].push_back(x);
}
}
int T = 0,D = 0,E = 0;
for(int i = 0 ; i < n ; i )
{
int a,b;//a:剩余数量 b:(总数 - 摘掉)
for(int j = q[i].size() - 1 ; j >= 0 ; j –)
{
//从后往前找到第一个大于0的数q[i][j]
if(q[i][j] > 0)
{
a = get(q[i] , j);
break;
}
}
b = get(q[i] , 0);
T += a;
//b-a 表示掉落的数量
if(b > a)st[i] = true, D
;
}
for(int i = 0 ; i < n ; i )
if(st[i] && st[(i+1) % n] && st[(i+2) %n])E
;

cout << T << " " << D << " " << E <<endl;
return 0;

}



活动打卡代码 AcWing 3277. 小明种苹果

include[HTML_REMOVED]

using namespace std;
int n,m;
const int N = 1e5;
int main()
{
cin>>n>>m;
int T = 0,K,P = -1;
for(int i = 1; i <= n ; i )
{
int tot , sum = 0 ,x;
scanf(“%d”,&tot);
for(int j = 0 ; j < m ; j
)
{
scanf(“%d”,&x);
sum += abs(x);
}
T += tot - sum;
if(sum > P) K = i , P = sum;
}
cout << T << ” ” << K << ” ” << P << endl ;
return 0;
}



活动打卡代码 AcWing 907. 区间覆盖

区间覆盖
以最小的区间数量覆盖给定的线段区间
基本思路:
1.按照左端点从小到大排序
2.从前往后依次枚举每个区间,在所有能覆盖st的区间中,选择右端点最大的区间,
然后更新st为右端点。


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+ 10;
struct Range{
    int l,r;
    bool operator<(const Range &w)const{
        return l<w.l;
    }
}range[N];
int main()
{
    int n,st,ed;
    cin>>st>>ed>>n;
    for(int i = 0 ; i < n ; i ++)
    {
        int l , r ;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    //1.排序
    sort(range,range+n);
    //2.贪心
    int res = 0;
    bool flag = false;//表示能否覆盖
    for(int i = 0 ; i < n ; i ++)
    {
        int j = i , r = -2e9;
        //找到能覆盖st的区间中右端点最大的区间edge[j]
        while(j < n && range[j].l <= st)
        {
            r = max(r,range[j].r);
            j++;
        }
        if(r < st)
        {
            res = -1;
            break;
        }
        res++;
        //检查是否得到答案
        if(r >= ed)
        {
            flag = true;
            break;
        }
        st = r;
        i = j - 1;
    } 
    if(!flag) puts("-1");
    else cout<<res;
    return 0;
}


活动打卡代码 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;
}