首页 > 其他分享 >2024.5.17

2024.5.17

时间:2024-05-17 20:52:01浏览次数:27  
标签:itn oo 2024.5 17 int top st

2024.5.17 【这个世界早已无法拯救,可我们还必须成为英雄。】

Friday 四月初十


继续水数据结构。。。


P3045 [USACO12FEB] Cow Coupons G

//2024.5.17
//by white_ice
//P3045 [USACO12FEB] Cow Coupons G
#include <bits/stdc++.h>
#include <typeindex>
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 50004;

itn n,k,m;
itn sk[oo];

bool vis[oo];

struct nod{int k,id,typ;}st[oo<<1];
int top;
bool cmp(nod a,nod b){return a.k==b.k?sk[a.id]>sk[b.id]:a.k<b.k;}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    
    cin >> n >> k >> m;
    int a,b;
    for (itn i=1;i<=n;i++){
        cin >> a >> b;
        sk[i] = a;
        st[++top].id = i;
        st[top].k = a;
        st[top].typ = 0;
        st[++top].id = i;
        st[top].k = b;
        st[top].typ = 1;
    }

    sort(st+1,st+top+1,cmp);

    int num = 0;
    for (itn i=1;i<=top;i++){
        if (st[i].k>m)
            break;
        if (vis[st[i].id])
            continue;
        if (st[i].typ&&!k)
            continue;
        vis[st[i].id] = 1;
        if (st[i].typ) k--;
        m -= st[i].k;
        num++;
    }

    cout << num;

    return 0;
}

以上是一个错误做法,

但是在这个题中可以获得原数据100分的好成绩

错误方法就不说了

两组hack数据:

20 3 9130
423 107
883 602
400 45
734 159
360 223
937 719
259 124
188 23
7 1
819 690
63 58
290 44
944 733
750 278
843 425
841 461
911 410
113 3
390 30
590 257

答案19

2 1 5
2 1
1000 3

答案为2

(原题hack数据)

正解:

//2024.5.17
//by white_ice
//P3045 [USACO12FEB] Cow Coupons G
#include <bits/stdc++.h>
#define pi pair<int,int> 
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 50004;

itn n,k,m;
itn sk[oo];

int p[oo],c[oo];
bool vis[oo];

priority_queue<pair<int ,int>,vector<pi>,greater<pi>>s1,s2;
priority_queue<int,vector<int>,greater<itn>> del;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    
    cin >> n >> k >> m;
    for (itn i=1;i<=n;i++){
        cin >> p[i] >> c[i];
        s1.push(make_pair(p[i],i));
        s2.push(make_pair(c[i],i));
    }
    
    for (itn i=1;i<=k;i++)
        del.push(0);
    
    int num = 0;

    while (!s1.empty()&&m>=0){
        pi a = s1.top();
        pi b = s2.top();
        if (vis[a.second]){
            s1.pop();
            continue;
        }
        if (vis[b.second]){
            s2.pop();
            continue;
        }

        if (del.top()>a.first-b.first){
            m-=a.first;
            s1.pop();
            vis[a.second] = 1;
        }
        else {
            m-=b.first+del.top();
            del.pop();
            vis[b.second] = 1;
            del.push(p[b.second]-c[b.second]);
        }
        if (m>=0)
            num++;
    }

    cout << num ;

    return 0;
}

维护两个小根堆,

分别是折前价格和折后价格。

每次决策前将两组的最小值取出比较,

判断使用这一次优惠券能带来的最大收益,

用del堆维护收益,

由此判断是否选择使用。


P3870 [TJOI2009] 开关

一道数据结构典题

我用了分块打但是hack点始终t掉。。。

//2024.5.17
//by white_ice
//P3870 [TJOI2009] 开关
#include <bits/stdc++.h>
using namespace std;
#define itn int
constexpr int oo = 50004;

int n,m;
int sq[oo];
bitset<oo> st[oo];
int blok,ktt;

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

__inline void change(itn x){
    if (x == blok+1)
        sq[x] = ktt-sq[x];
    else sq[x] = blok - sq[x];
    st[x].flip();
}

signed main() {
    n = read(),m = read();

    blok = sqrt(n);
    ktt = n-blok*blok;

    int a,b,c;
    for (itn i=1;i<=m;i++){
        c = read(),a = read(),b = read();
        if (!c){
            int p = (a-1)/blok+1;
            int k = (b-1)/blok+1;
            if (p==k){
                for (itn i=a-(p-1)*blok;i<=b-(k-1)*blok;i++){
                    st[p][i] = ~st[p][i];
                    if (st[p][i])
                        sq[p]++;
                    else sq[p]--;
                }
            }
            else{
                for (itn i=a-(p-1)*blok;i<=blok;i++){
                    st[p][i] = ~st[p][i];
                    if (st[p][i])
                        sq[p]++;
                    else sq[p]--;
                }
                for (itn i=p+1;i<k;i++)
                    change(i);
                for (itn i=1;i<=b-(k-1)*blok;i++){
                    st[k][i] = ~st[k][i];
                    if (st[k][i])
                        sq[k]++;
                    else sq[k]--;
                }
            }
        }
        else {
            int out = 0;
            int p = (a-1)/blok+1;
            int k = (b-1)/blok+1;
            if (p==k){
                for (itn i=a-(p-1)*blok;i<=b-(k-1)*blok;i++){
                    if (st[p][i])
                        out++;
                }
            }
            else {
                for (itn i=a-(p-1)*blok;i<=blok;i++){
                    if (st[p][i])
                        out++;
                }
                for (itn i=p+1;i<k;i++)
                    out += sq[i];
                for (itn i=1;i<=b-(k-1)*blok;i++){
                    if (st[k][i])
                        out++;
                }
            }
            cout << out << '\n';
        }
    }

    return 0;
}

整体就是非常纯粹简单的分块,

注意小散块的处理。

还有用bitset,真的非常好用。


P4185 [USACO18JAN] MooTube G

带权并查集题目,

题中并没有要求在线,

所以我们对问题排序,优化程序

其中siz记录每个节点下子孙节点的个数,

通过遍历排序后的问题对答案求解。

依照题意对值大于k的节点进行查找。

//2024.5.27
//by white_ice
//P4185 [USACO18JAN] MooTube G
#include<bits/stdc++.h>
using namespace std;
#define itn int
constexpr itn oo = 100005;

itn jntm(itn a,itn b){return a>b?a:b;}
itn ngm (itn a,itn b){return a<b?a:b;}

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

struct ask{int k,v,id;}que[oo];
bool cmp2(const ask &a,const ask &b){return a.k>b.k;}

namespace Disjointset{
    struct edg{itn u,v,w;}st[oo];
    bool cmp(const edg &a,const edg &b){return a.w>b.w;}

    itn f[oo];
    int siz[oo];

    itn find(itn x){if (x==f[x])return x;
        f[x]=find(f[x]);
        return f[x];}
    void init(){for(int i=1;i<=n;i++){f[i] = i;siz[i] = 1;}}
}

itn top=1;
int out[oo];


itn main(){
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    using namespace Disjointset;

    cin >> n >> q;
    for (itn i=1;i<n;i++)
        cin >> st[i].u >> st[i].v >> st[i].w;
    for (itn i=1;i<=q;i++){
        cin >> que[i].k >> que[i].v;
        que[i].id = i;
    }

    init();

    sort(st+1,st+n+1,cmp);
    sort(que+1,que+q+1,cmp2);

    for (itn i=1;i<=q;i++){
        while (que[i].k<=st[top].w){
            itn x = find(st[top].v);
            itn y = find(st[top].u);
            siz[x]+=siz[y];
            f[y] = x;
            top ++;
        }
        out[que[i].id] = siz[find(que[i].v)];
    }

    for (itn i=1;i<=q;i++)
        cout << out[i]-1<< '\n';

	return 0;
}

类似题:

P1525 [NOIP2010 提高组] 关押罪犯

P1196 [NOI2002] 银河英雄传说


P1168 中位数

这里我们使用pb_ds大显身手

即时向红黑树中添加新元素实现查询。

编写非常简单

//2024.5.17
//by white_ice
//P1168 中位数
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
#define itn int
constexpr int oo = 100005;

int n;

int idx;
itn st[oo];
struct node{
	int x,tim;
	bool operator <(node o) const{
		if(x != o.x) return x < o.x;
		else return tim < o.tim;
	}
};
tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> tre;
void insert(int x){tre.insert({x,++idx});}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin >> n;
    cin >> st[1];
    insert(st[1]);
    cout << st[1] << '\n';
    for (itn i=3;i<=n;i+=2){
        cin >> st[i-1] >> st[i];
        insert(st[i-1]);
        insert(st[i]);
        cout << (tre.find_by_order(i/2)->x) << '\n';
    }

    if  (!n%2) 
        cin >> st[n];

    return 0;
}

标签:itn,oo,2024.5,17,int,top,st
From: https://www.cnblogs.com/white-ice/p/18198591

相关文章

  • Codeforces 1178B WOW Factor
    题目简述给定一个只含$v$和$o$的字符串$s$,求字符串中有多少个$wow$(一个$w$即为连续的两个$v$)。题目分析考虑枚举每一个$o$,设下标为$i$,统计它左边和右边各有多少个$w$,分别设为$a_{i-1}$和$b_{i+1}$,依据乘法原理,将它们乘起来即为答案,累加即可。接下来,考虑怎么处......
  • 2024.5
    1.pkuwc2024d2t2排序暴力就是按值从大到小填,记录初始序列有哪些位置被填了,每次填上一个数计算它与比它大的数之间的交换次数,模拟一下希尔排序,这个做法是\(\mathcal{O}(2^nnm)\)。先优化掉状态数,需要swap次数最多,那么按\(d_1\)分组后每组内部一定是递减的,将已经填入的看......
  • 【Linux】《VMware17搭建Ubuntu.22.04-Rust开发环境》
    下载VMware17安装包下载链接:创建虚拟机之后都默认就可以了。进入系统设置登录账号和密码以及修改下语言,剩余都默认即可。设置中文界面设置中文输入法接下来开始设置输入法切换快捷键设置使用Ctrl+Alt+T打开终端,输入ibus-setup重启,看一下是......
  • 5.17
    计算机网络5.8TCP的拥塞控制5.8.1拥塞控制的一般原理拥塞:某段时间,若对网络中某资源的需求超过了该资源所能提供的可用部分,网络的性能就要变坏,这种现象称为拥塞出现拥塞的原因:对资源的需求>可用资源增加资源解决拥塞:不能。拥塞由多种因素引起,不能单纯通过增加资源解决拥塞的......
  • hdu1176免费馅饼java
    一个数塔问题,以时间为纵坐标、位置为横坐标创建一个二维数组,然后从下往上相加。状态转移方程:9>=j>=1时dp[i][j]+=max(max(dp[i+1][j],dp[i+1][j+1]),dp[i+1][j-1])  j=0时 dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]) j=10时dp[i][j]+=......
  • 2024.5.16鲜花/燃料不纯的火箭与璀璨夺目的陨星
    前言在阅读本篇之前,建议先阅读上一篇鲜花。正文作为星际新闻局长,审核新闻稿之类的事自然是不需要我亲自动手,所以我每天都有大把的私人时间,这时候,我就会去看看星际新闻,也算是为自己负责的节目增加一点收视率。某一天,我看见一则新闻:【数据删除】中学校领导在线上招生典礼上介......
  • esp32笔记[17]-显示网络延迟
    摘要使用esp32c3;使用软件i2c方式驱动ssd1306显示屏显示网络延迟和NTP时间;关键信息开发环境:ArduinoIDE主控:esp32c3显示屏:ssd1306原理简介ping测试网络延迟简介[https://github.com/dvarrel/ESPping][https://blog.csdn.net/qq_31536117/article/details/134757851......
  • 2024.5.16
    2024.5.16【就算一次也好,我想在这颗星球上尽情奔跑。】Thursday四月初九数据结构P4588TJOI2018数学计算//2024.5.16//bywhite_ice//P4588[TJOI2018]数学计算#include<bits/stdc++.h>usingnamespacestd;#defineitnlonglong#defineintlonglongconste......
  • 群晖ds1517+解决第三方Marvell AQC107 10Gbe网卡驱动问题
    群晖ds1517+解决第三方MarvellAQC10710Gbe网卡驱动问题转载注明来源:本文链接来自osnosn的博客,写于2024-05-15.说明这是网友mohawk解决问题的经过,征得同意后,贴在这里。给大家参考。背景好友打算升级到全屋有线万兆2.5g网络,陆续装备了路由器、交换机等,但家里的群晖ds......
  • Angular Material 17+ 高级教程 – Material Tooltip
        目录上一篇 AngularMaterial17+高级教程–CDKOverlay下一篇TODO想查看目录,请移步 Angular17+高级教程–目录......