7.28 EOI

时间：2023-07-28 19:13:35浏览次数：50

标签：ch const 7.28 int EOI long while getchar


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 2e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int t, n, k;

int w[N], v[N];

signed main()
{
    freopen("ball.in", "r", stdin);
    freopen("ball.out", "w", stdout);
    t = read();
    while (t--)
    {
        n = read(), k = read();
        for (int i = 1; i <= n; ++i)
            w[i] = read();
        sort(w + 1, w + n + 1);
        for (int i = 1; i <= k; ++i)
            v[i] = read() - 1;
        sort(v + 1, v + k + 1);
        ll res = 0;
        int r = n;
        for (int i = 1; i <= k; ++i)
        {
            if (!v[i])
                res += w[r] * 2;
            else
                res += w[r];
            r--;
        }
        for (int i = 1; i <= k; ++i)
        {
            if (!v[i])
                continue;
            res += w[r - v[i] + 1];
            r -= v[i];
        }
        printf("%lld\n", res);
    }
    return 0;
}


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define int long long

const int N = 1e2 + 50;
const int M = 1e3 + 50;
const int Mod = 1e9 + 7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int t, n, m;

int a[N], b[N];

int f[M];

// int q[M];

signed main()
{
    freopen("group.in", "r", stdin);
    freopen("group.out", "w", stdout);
    t = read();
    while (t--)
    {
        n = read(), m = read();
        for (int i = 1; i <= n; ++i)
            a[i] = read();
        for (int i = 1; i <= n; ++i)
            b[i] = read();
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int r = m; r > m - a[i]; --r)
            {
                for (int j = r; j >= a[i]; j -= a[i])
                {
                    for (int k = 1; k <= b[i]; ++k)
                    {
                        if (j >= k * a[i])
                            f[j] = (f[j] + f[j - k * a[i]]) % Mod;
                        else
                            break;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= m; ++i)
        {
            res = (res + f[i]) % Mod;
        }
        printf("%lld\n", res);
    }
    return 0;
}


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 3e2 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int t, n;

int v[N];

int a[N][N], f[N][N];

int main()
{
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    t = read();
    while (t--)
    {
        n = read();
        for (int i = 1; i <= n; ++i)
            v[i] = read();
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                a[i][j] = read();
            }
        }
        memset(f, 0, sizeof(f));
        for (int i = 0; i <= n; ++i)
            f[i][i] = i;
        for (int len = 1; len <= n; ++len)
        {
            for (int l = 1; l <= n - len + 1; ++l)
            {
                int r = l + len - 1;
                for (int k = l; k < r; ++k)
                {
                    if (a[f[l][k]][f[k + 1][r]])
                    {
                        if (v[f[l][r]] < v[f[l][k]])
                        {
                            f[l][r] = f[l][k];
                        }
                    }
                    else
                    {
                        if (v[f[l][r]] < v[f[k + 1][r]])
                        {
                            f[l][r] = f[k + 1][r];
                        }
                    }
                }
            }
        }
        printf("%d\n", v[f[1][n]]);
    }
    return 0;
}


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 2e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int t, n, k, MX;

int a[N];

priority_queue<int, vector<int>, greater<int>> s, CLEAR;

bool check(int x)
{
    s = CLEAR;
    for (int i = 1; i < k; ++i)
        s.push(a[i]);
    for (int i = k; i <= n; ++i)
    {
        s.push(a[i]);
        if (x >= s.top())
            x += s.top();
        else
            return false;
        s.pop();
        if (x >= MX)
            return true;
    }
    for (int i = 1; i < k; ++i)
    {
        if (x >= s.top())
            x += s.top();
        else
            return false;
        s.pop();
        if (x >= MX)
            return true;
    }
    return true;
}

signed main()
{
    freopen("monster.in", "r", stdin);
    freopen("monster.out", "w", stdout);
    t = read();
    while (t--)
    {
        n = read(), k = read();
        MX = 0;
        for (int i = 1; i <= n; ++i)
            a[i] = read(), MX = max(MX, a[i]);

        int l = 0, r = 1e9, ans = Mod;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid))
            {
                ans = min(ans, mid);
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

标签：ch,const,7.28,int,EOI,long,while,getchar
From： https://www.cnblogs.com/R-V-G/p/17588704.html

7.28 后记
T1异或和塞到状态里就不用管路径相交了式子：\[f_{i,j,k\operatorname{xor}G_{i,j},0}=f_{i-1,j,k,0}+f_{i,j-1,k,0}\]\[f_{i,j,k\operatorname{xor}G_{i,j},1}=f_{i-1,j,k,1}+f_{i,j-1,k,1}\]\[f_{i,j,k,1}=f_{i-1,j,k,0}+f_{i,j-1,k,0}\]T2朋友能到达\(k\)的人一定都......
暑假集训D5 2023.7.28 补题
首先来回顾一下\(dijkstra\)和\(SPFA\)里面\(vis\)数组的作用和区别,以及不用\(vis\)数组的影响.(今天发现之前写堆优化的\(Dijkstra\)都不加\(vis\)数组...)\(Dijkstra\)算法中,每次取出距离源点最近的一个点来更新与他相连的其他点,置\(vis\)数组为\(true\)......
【2023.07.28】三年计划
=主线任务今年的主线是考上研究生，并让学校所有人都认识我攒钱买辆车（大概率小米）明年的主线是软考高项，业余时间去考电工和思科支线任务增肥上60kg，让自己身体更好，目前只有53还是太瘦了和妹妹拼完一整个柜子的积木（目前四层已经塞满两层）谈恋爱，找女朋友入校后打算......
Mock 3: CEOI2021 Day1 P3
让我简化一下题目吧：有两个玩家,A和B。A并不知道B的位置，但是B知道A的位置然后可以做相应的动作。让B在任何结点,做一个路径保证A肯定会抓到B或表示抓不到B。路径必须最短.每个回合B必须要往任何一个相邻的结点移动。我是先考虑链的情况:非常明显的是肯定可以抓到。那么......
CEOI2017 Building Bridges
小清新斜率优化题。分段问题显然dp，令\(f_i\)为将第\(1\)根柱子和第\(i\)根柱子连接的最小代价。\(f_1=0\)，每次枚举\(i\)向前直接连接的柱子：\[f_{i}=\min\limits_{j=1}^{i-1}\left\{f_j+(h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\right\}\]令\(s_{i}=\sum\limits_{j=......
CEOI Team Selection D1T2 Prosjek
首先全奇全偶的情况是容易的，将\(\bmod4\)意义下相同的合并即可保持原来的奇偶状态，当只有两个是直接合并即可，归纳即可说明全奇全偶一定合法。但关键的问题在于奇偶状态可能互相影响，一个直观的想法是将奇合并为一个\(x\)，偶合并为一个\(y\)，如果\(x,y\)的奇偶性相同，那么它们即......
7.3-7.28海亮游记
7.3早上到机场看到xj提前半个小时来了十分震惊快乐的飞机上写完了莫队但是下飞机挂到了\(30pts\)晚上机房开会还好提前去看了否则就是正能量大会茶话会\(day1\)"如果爱能磨平山海,如果分手能算表白."7.4海亮D1数据结构被薄纱被薄纱和反复被薄纱\(bot\)在开场\(5s\)......
题解 P4108【[HEOI2015]公约数数列】
看到这种奇怪的操作，首先想到分块。以下记值域为\(w\)，块长为\(B\)。前缀\(\gcd\)显然单调不增，而且后一个必须是前一个的因数，如果变化至少要减半。因此，我们知道，共有\(\mathcalO(\logw)\)个不同的前缀\(\gcd\)。我们可以接受对这些块暴力，只需要对前缀\(\gcd\)都相同的块......
P5999 [CEOI2016] kangaroo
前言写这篇题解的原因是这道题提供了一种新的dp思路——插入dp。题意给定一个长为\(n\)的数轴，一只袋鼠在上面要从\(s\)跳到\(t\)，跳跃过程中，每次跳跃方向必须与上一次相反，求方案数。分析拿到这个题其实还是蛮蒙的，但是如果我们转化（抽象）一下题意，就会发现这道题可以看作：......
[CEOI2017] Sure Bet(双指针)
题目大意:给出两个数组A,B,可以在两个数组选择任意多个数,代价为选择的数的数目,得到的奖励为在数组A和数组B中选择的数的两个总和较小的那个,求能得到的最大收益思路:1.先给两个数组分别由大到小排序后求前缀和,不难得出在数组A中选择i个数,数组B中选择j个数时,最大收益为:m......

7.28 EOI

相关文章

赞助商

阅读排行