头像

星瑞




离线:5小时前


活动打卡代码 AcWing 422. 校门外的树

星瑞
5小时前

数据不大,暴力就好,如果数据大的话可以用sort+pair降低复杂度至O(nlogn)

#include<iostream>
using namespace std;

int n, m;
int a[10005];
int x, y;
int ans;
signed main()
{
    cin >> n >> m;
    //ans = n;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        for (int j = x; j <= y; j++)
        {
            if(!a[j])
                ans++;
            a[j] = 1;
        }
    }
    cout << n-ans+1 << endl;
    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

星瑞
1天前

和昨天一样的二分

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, m;
ll l, r, mid;
ll a[100005][2];
signed main()
{
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld",&a[i][0],&a[i][1]);
    }
    l = 1;
    r = 100000;
    while (l <= r)
    {
        mid = (l + r)/2;
        int t = 0;
        for (int i = 1; i <= n; i++)
        {
            t += (a[i][0] / mid) * (a[i][1] / mid);
        }
        if (t > m)
            l = mid+1;
        else
            r = mid-1;
    }
    mid = (l + r)/2;
    printf("%lld",mid);
    return 0;
}



星瑞
2天前

二分朴素写法,简单易懂

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
int n;
int m;
double a[maxn];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { cin >> a[i]; }
    double l = 0, r = 1e9;
    double mid = 0;
    while (l <= r)
    {
        mid = (l + r) / 2;
        ll temp = 0;
        for (int i = 1; i <= n; i++)temp += a[i] / mid;
        if (temp >= m)
            l = mid+0.001;
        else
            r = mid-0.001;
    }
    printf("%.2f", mid);
    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

星瑞
2天前

二分,注意精度问题

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
int n;
int m;
double a[maxn];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { cin >> a[i]; }
    double l = 0, r = 1e9;
    double mid = 0;
    while (l <= r)
    {
        mid = (l + r) / 2;
        ll temp = 0;
        for (int i = 1; i <= n; i++)temp += a[i] / mid;
        if (temp >= m)
            l = mid+0.001;//精度
        else
            r = mid-0.001;//精度
    }
    printf("%.2f", mid);
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

星瑞
3天前

【广度优先遍历写法】

#include<bits/stdc++.h>
using namespace std;
int n, m;
char a[25][25];
int vis[25][25];
struct node
{
    int x;
    int y;
};
int bfs(int x, int y)
{
    queue<node>p;
    p.push({ x,y });
    int ans = 1;
    vis[x][y] = 1;
    while (!p.empty())
    {
        int xx = p.front().x;
        int yy = p.front().y;
        p.pop();
        if (xx + 1 <= n && !vis[xx + 1][yy])
        {
            vis[xx + 1][yy] = 1;
            p.push({ xx + 1,yy });
            ans++;
        }
        if (xx - 1 >= 1 && !vis[xx - 1][yy])
        {
            vis[xx - 1][yy] = 1;
            p.push({ xx - 1,yy });
            ans++;
        }
        if (yy + 1 <= m && !vis[xx][yy+1])
        {
            vis[xx][yy+1] = 1;
            p.push({ xx,yy+1 });
            ans++;
        }
        if (yy - 1 >= 1 && !vis[xx][yy-1])
        {
            vis[xx][yy-1] = 1;
            p.push({ xx,yy-1 });
            ans++;
        }
    }
    return ans;
}
signed main()
{
    while (cin >> m >> n && n&&m)
    {
        int sx, sy;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                if (a[i][j] == '@')
                    sx = i, sy = j;
                else if (a[i][j] == '#')
                    vis[i][j] = 1;
            }
        cout << bfs(sx, sy) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

星瑞
3天前
#include<bits/stdc++.h>
using namespace std;
int n, m;
int cnt=1;
int a[505][505];
signed main()
{
    cin >> n >> m;
    int x = 1, y = 0;
    while (cnt <= n*m)
    {
        for (int i = 0; cnt<=n*m&&i < m; i++)
        {
            if (!a[x][y + 1])
                a[x][++y] = cnt++;
        }
        for (int i = 0; cnt <= n * m&&i < n-1; i++)
        {
            if (!a[x+1][y])
                a[++x][y] = cnt++;
        }
        for (int i = 0; cnt <= n * m&&i < m-1; i++)
        {
            if (!a[x][y-1])
                a[x][--y] = cnt++;
        }
        for (int i = 0; cnt <= n * m&&i < n-2; i++)
        {
            if (!a[x - 1][y])
                a[--x][y] = cnt++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
}



星瑞
6天前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[505][505];
signed main()
{
       cin>>n;
       memset(a,-0x3f,sizeof(a));
       int ans=INT_MIN;
       for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)
            {
                cin>>a[i][j]; 
                if(i != 1)a[i][j] += max(a[i-1][j],a[i-1][j-1]); 
                if(i == n)ans = max(ans,a[i][j]);

            }
        cout<<ans;
        return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 898. 数字三角形

星瑞
6天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;

int n;
int a[505][505];
int dp[505][505];
signed main()
{
       cin>>n;
       int ans=INT_MIN;
       for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            if(j == 1)
            dp[i][j] = dp[i-1][j]+a[i][j];
            else if(j == i)
            dp[i][j] = dp[i-1][j-1]+a[i][j];
            else
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
            if(i == n)
            ans = max(ans,dp[i][j]);
        }
        cout<<ans;
        return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 104. 货仓选址

星瑞
6天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include[HTML_REMOVED]

using namespace std;
int a[100005];
int n;
signed main()
{
cin>>n;
for(int i=0;i[HTML_REMOVED]>a[i];
sort(a,a+n);
int ans =0 ;
for(int i=0;i[HTML_REMOVED]>1];
cout<<ans<<endl;
return 0;
}