头像

Loading_0

天津大学




离线:8小时前


活动打卡代码 AcWing 148. 合并果子

Loading_0
14小时前
#include<iostream>
#include<queue>

using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> heap;
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin>>x;
        heap.push(x);
    }

    int res=0;
    while(heap.size() > 1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += (a + b);
        heap.push(a+b);
    }

    cout << res << endl;
    return 0;
}


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

Loading_0
14小时前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
struct Range
{
    int l, r;
    bool operator < (Range &W)
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    cin >> st >> ed;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);


    //双指针算法
    int res = 0;
    bool success = false;
    for(int i=0; i<n; i++)
    {
        int j=i, r = -2e9;
        while(j<n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j++;
        }

        if(r < st)
            break;

        res++;

        if(r>=ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j-1;
    }

    if(success) cout<<res<<endl;
    else cout<<"-1"<<endl;

    return 0;
}


活动打卡代码 AcWing 906. 区间分组

Loading_0
15小时前
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100010;

struct Range
{
    int l, r;
    bool operator <(Range &W)
    {
        return l<W.l;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range+n);

    priority_queue<int, vector<int>, greater<int>> heap;

    for(int i=0; i<n; i++)
    {
        if(heap.empty() || heap.top() >= range[i].l)
            heap.push(range[i].r);
        else
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }

    cout << heap.size() <<endl;
    return 0;
}



#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100010;

struct Range
{
    int l, r;
    bool operator < (Range &W)
    {
        return r < W.r;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for(int i=0; i<n; i++)
    {
        if(ed < range[i].l)
        {
            res++;
            ed = range[i].r;
        }
    }

    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100010;

//重写小于号, 使用sort
struct Range
{
    int l, r;
    bool operator < (Range &W)
    {
        return r < W.r;
    }
}range[N];

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);
    int res=0, ed = -2e9;
    for(int i=0; i<n; i++)
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }

    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 900. 整数划分

#include<iostream>
#include<cstring>

using namespace std;

//f[i][j]代表在1~i中取数,总体积为j的方案
//f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2*i] + ... + f[i-1][j-c*i]

//转移方程 f[i][j] = f[i-1][j] + f[i][j-i]

const int N = 1010, mod = 1e9 + 7;
int f[1010];

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

    f[0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            f[j] = (f[j] + f[j-i]) % mod;

    cout << f[n] <<endl;
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

#include<iostream>
#include<cstring>

using namespace std;
const int N = 510;
int g[N][N], f[N][N];
//f[n][m]以n,m为起点的路径的长度
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;

int dp(int x, int y)
{
    if(f[x][y] != -1) return f[x][y];
    int &v = f[x][y];

    v = 1;
    //初始化,f[][]最小为1
    for(int i=0; i<4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a>=1 && a<=n && b>=1 && b<=m && g[x][y] > g[a][b])
                v = max(v, dp(a, b) + 1);
        }
    return v;
}


int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> g[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<iostream>
#include<cstring>

using namespace std;
const int N = 6010;
int happy[N];
//f[N][1]代表取第N个点方案的快乐度, f[N][0]代表不取第N个点的方案的快乐度
int f[N][2];
//需要一个数组存储根节点坐标
bool has_fa[N];
//单链表
int h[N], e[N], ne[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int a)
{
    f[a][1] = happy[a];
    for(int i=h[a]; i!=-1; i=ne[i])
    {
        int j = e[i];
        dfs(j);
        f[a][1] += f[j][0];
        f[a][0] += max(f[j][0], f[j][1]);
    }
}


int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin >> happy[i];
    memset(h, -1, sizeof h);

    for(int i=1; i<=n-1; i++)
    {
        int a, b;
        cin>>a>>b;
        add(b, a);
        has_fa[a] = true;
    }

    int root = 1;
    while(has_fa[root]) root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]) <<endl;

    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

const int N = 20, M = 1<<N;
//f[n][m] 表示经过点为n的二进制,终点为m的路径
//w表示各个点之间的距离
int w[N][N], f[M][N];

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;
    for(int i=0; i<1<<n; i++)
        for(int j=0; j<n; j++)
            if(i>>j & 1)
                for(int k=0; k<n; 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;

    return 0;
}



#include<iostream>
#include<cstring>

using namespace std;
const int N = 12, M = 1<<N;
//f[n][m]表示第n列有m个突出方形的方案数
long long f[N][M];
//st表示i是否存在连续偶数个空缺
bool st[M];
int n, m;

int main()
{
//逗号语法,从左到右执行,以最后一个语句定真假
    while(cin>>n>>m, n||m)
    {
        for(int i=0; i<1<<n; i++)
        {
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
            {
                if(i>>j & 1)
                {
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            if(cnt & 1) st[i] = false;
        }
        //提前处理st数组

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        //只有一种方案,不填充
        for(int i=1; i<=m; i++)
            for(int j=0; j<1<<n; j++)
                for(int k=0; k<1<<n; k++)
                //注意运算符优先级
                    if((j&k) == 0 && st[j|k])
                        f[i][j] += f[i-1][k];

        cout<<f[m][0]<<endl;
    }
    return 0;
}