首页 > 其他分享 >2023.3.14 日寄

2023.3.14 日寄

时间:2023-03-14 21:59:07浏览次数:50  
标签:std poz 14 long 2023.3 leq kro 代价

2023.3.14 日寄

\(~~~~\) π节快乐!

模拟赛

\(~~~~\) 没有题解的模拟赛……毫无意义!咕噜咕噜……

游戏

题意

\(~~~~\) 有 \(n\) 个数的序列 \(a\) 代表当前位置的怪物的血量,击败有 \(x\) 血的怪物需要 \(x\) 的代价。你有一个大招需要付出 \(W_b\) 的代价,可以击败连续的 \(k\) 个怪物。同时你还可以用 \(w_s\) 的代价交换两个相邻的怪物(被击败的怪物仍然占位,会影响相邻的判断)。求击败所有怪物的最小代价。
\(~~~~\) \(1\leq k\leq n\leq 10^6,1\leq a_i,w_s,w_b\leq 10^9\).

题解

\(~~~~\) 考虑不用大招那必定用 \(\sum a\) 的代价,那用大招就看我们可以节省多少代价。

\(~~~~\) 如果我们已经选出了 \(k\) 个怪物要击败,那必然我们会把他们交换到居中的位置(初一数学:绝对值在数轴上的几何意义)。那反过来如果我们确定了中间位置,我们必定就知道两侧要选 \(\frac{k}{2}\) 个数(具体视 \(k\) 的奇偶性需要微调。)

\(~~~~\) 那么枚举了分界线过后我们就会发现分界线左侧的数交换代价为每个数将要交换到的下标减去原始的下标乘以单次交换代价(即 \((aim-i)\times w_s\))右边每个数的交换代价为原始下标减去目标下标 (即 \((i-aim)\times w_s\)),最后减去选中的数的 \(a\) 再加上 \(w_b\),这就是可以节省的代价,求出这个东西的最小值即可。

\(~~~~\) 把上面这个东西拆开:所有目标位置的下标和对于固定分界线都是常数不管,那么左边单个数就是 \(-i\times w_s-a_i\),右边单个数就是 \(i\times w_s-a_i\) ,那我们只需要选两边这两个东西前 \(\frac{k}{2}\) 小的求和即可,用权值线段树维护。

\(~~~~\) 注意数据范围可能需要开 __int128,但是好像数据没卡。

代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
ll n,k,Ws,Wb,arr[1000005];
ll brr[1000005],crr[1000005];
struct SegmentTree{
	#define ls p<<1
	#define rs p<<1|1
	#define lson p<<1,l,mid
	#define rson p<<1|1,mid+1,r
	ll tr[4000005],Siz[4000005];
	inline void pushUp(ll p)
	{
		tr[p]=tr[ls]+tr[rs];
		Siz[p]=Siz[ls]+Siz[rs];
	}
	void Modify(ll p,ll l,ll r,ll aim,ll Val,ll Type)
	{
		if(l==r){Siz[p]+=Val;tr[p]+=Val*(Type==1?brr[l]:crr[l]);return;}
		ll mid=(l+r)>>1;
		if(aim<=mid) Modify(lson,aim,Val,Type);
		if(mid<aim)  Modify(rson,aim,Val,Type);
		pushUp(p);
	}
	ll Query(ll p,ll l,ll r,ll K)
	{
		if(Siz[p]<K) return 1e18;
		if(K==Siz[p]) return tr[p];
		ll mid=(l+r)>>1;
		if(Siz[ls]<K) return tr[ls]+Query(rson,K-Siz[ls]);
		else return Query(lson,K);
	}
	#undef ls
	#undef rs
	#undef lson
	#undef rson
}Seg1,Seg2;
ll LSiz,RSiz;
inline ll Calc(ll x)
{
	return 1ll*Ws*(((x-LSiz+1+x)*LSiz/2)-((x+1+x+RSiz))*RSiz/2);
}
ll cnt1,cnt2;
inline ll ID1(ll x){x=-1ll*x*Ws-arr[x];return lower_bound(brr+1,brr+1+cnt1,x)-brr;}
inline ll ID2(ll x){x=+1ll*x*Ws-arr[x];return lower_bound(crr+1,crr+1+cnt2,x)-crr;}
int main() {
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	read(n);read(k);ll Sum=0;
	for(ll i=1;i<=n;i++) read(arr[i]),Sum+=arr[i];
	read(Ws);read(Wb);
	
	for(ll i=1;i<=n;i++) crr[i]=1ll*i*Ws-arr[i],brr[i]=-1ll*i*Ws-arr[i];
	sort(brr+1,brr+1+n); sort(crr+1,crr+1+n);
	cnt1=unique(brr+1,brr+1+n)-brr-1;
	cnt2=unique(crr+1,crr+1+n)-crr-1;
	
	for(ll i=1;i<(k+1)/2;i++) 
		Seg1.Modify(1,1,cnt1,ID1(i),1,1);
	for(ll i=(k+1)/2;i<=n;i++) 
		Seg2.Modify(1,1,cnt2,ID2(i),1,2);
	LSiz=(k+1)/2,RSiz=k-LSiz;
	ll Ans=0;
	for(ll i=LSiz;i+RSiz<=n;i++)
	{
		Seg1.Modify(1,1,cnt1,ID1(i),1,1); Seg2.Modify(1,1,cnt2,ID2(i),-1,2);
		Ans=min(Ans,Seg1.Query(1,1,cnt1,LSiz)+Seg2.Query(1,1,cnt2,RSiz)+Calc(i)+Wb);
	}
	printf("%lld",Sum+Ans);
	return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。

拆开贡献,枚举这个k的区间的中间位置,权值线段树求出两边前k小的值的和 
*/

石子

\(~~~~\) 【道理已删除】

\(~~~~\) 没人说得清楚自己或者 std 为什么是对的。


划分 / 「Czech, Polish and Slovak Preparation Camp 2017, Day PL」 GCD-sum

题意

\(~~~~\) 把 \(n\) 个数划入 \(k\) 个集合,定义每个集合的权值为其中元素的 \(\gcd\),划分的权值为所有集合权值的和,求对于 \(k\in [1,n]\) 每种情况最大的划分和。
\(~~~~\) \(1\leq n\leq 5\times 10^5,1\leq a_i\leq 10^{12}\).

题解

\(~~~~\) 贴个同学的题解 ,不过这位同学被公认 S 区可能有点问题(?)

pp1FRL6.png

pp1F2sx.png

代码

\(~~~~\) 贴的std,请不要问我 95~97 行它在干什么,我也想知道。

查看代码
#include <iostream>
#include <vector>
#include <algorithm>
long long n, x;
int k;
const long long MAXEL=1000LL*1000LL*1000LL*1000LL;
std::vector<long long> li, result;
std::vector<std::pair<long long, int> > kro;
long long nwd(long long a, long long b)
{
    while (a != 0) {
        b %= a;
        std::swap(a, b);
    }
    return b;
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin >> n;
    result.resize(n+2);
    for (int i = 0; i < n; i++) {
        std::cin >> x;
        li.emplace_back(x);
    }
    sort(li.begin(), li.end());
    int ile = 0;
    long long last = li.front();
    for (auto l : li) {
        if (l == last) {
            ile++;
        } else {
            kro.emplace_back(last, ile);
            ile = 1;
            last = l;
        }
    }
    kro.emplace_back(last, ile);
    long long nw = 0;
    long long sum = 0;
    for (auto x : kro)
        sum += x.first;
    for (std::size_t i = 0; i < kro.size(); i++) {
        long long tmp = nwd(nw, kro[i].first);
        //std::cout<<i<<" tmp nw "<<tmp<<" "<<nw<<std::endl;
        if (tmp != nw) {
            long long max = -MAXEL; 
            for (std::size_t j = i; j < kro.size(); j++) 
                max = std::max(max, nwd(nw,kro[j].first ) - kro[j].first);
                long long sum2 = sum + max;
                //std::cout<<"m n "<<max<<" "<<nw<<" "<<sum<<std::endl;
                result[kro.size()-i] = std::max(result[kro.size()-i] ,sum2);
                
                result[kro.size()-i+1] = std::max(result[kro.size()-i+1] ,sum2-max+nw);
            
                //std::cout<<"$result["<<kro.size()-i<<"]= "<<result[kro.size()-i]<<std::endl;
                //std::cout<<"$result["<<kro.size()-i+1<<"]= "<<result[kro.size()-i+1]<<std::endl;
                int ite = 0;
                int poz = kro.size() - 1;
                std::vector<long long> str;
                while (true) {
                    while (poz >= int(i) && kro[poz].second == 1)
                        poz--;
                    if (poz < int(i))
                        break;
                    kro[poz].second--;
                    str.emplace_back(poz);
                    ite++;
                    sum2 += kro[poz].first;
                    result[kro.size()-i+ite] = std::max(result[kro.size()-i+ite],sum2);
                    result[kro.size()-i+ite+1] = std::max(result[kro.size()-i+ite+1],sum2-max+nw);
                    //std::cout<<"result["<<kro.size()-i+ite<<"]= "<<result[kro.size()-i+ite]<<std::endl;
                    //std::cout<<"result["<<kro.size()-i+ite+1<<"]= "<<result[kro.size()-i+ite+1]<<std::endl;
                  
                    
                }
                for(auto x:str)
                    kro[x].second++;
            
            nw=tmp;
        }
        sum-=kro[i].first;//*kro[i].second;

    }
    sum=0;
    for (auto x : li)
        sum += x;
    nw=0;
    for (std::size_t i = 0; i < li.size(); i++) {
        
        long long tmp = nwd(nw, li[i]);
        
        if(tmp!=nw){
            long long max=-MAXEL;
            for(std::size_t j=i;j<li.size();j++){
                max=std::max(max,nwd(li[i],nw))-li[i];
            }
            result[li.size()-i]=std::max(result[li.size()-i],sum+max);
        }else{
            result[li.size()-i]=std::max(result[li.size()-i],sum-li[i]+nw);
        }
        
        sum-=li[i];
        nw=tmp;
        
    }

   
    for (int i=1;i<=n;i++) {
        std::cout << result[i] << "\n";
    }

    
}

标签:std,poz,14,long,2023.3,leq,kro,代价
From: https://www.cnblogs.com/Azazel/p/17216542.html

相关文章

  • 2023年3月14日(软件工程日报)
    Application是Android的一大组件,在App运行过程中有且仅有一个Application对象贯穿应用的整个生命周期。打开AndroidManifest.xml,发现activity节点的上级正是application节......
  • 3.14,每日总结
    今天做了几道python习题,完成了android系统第二阶段的开发   总结查询 自动统计 ......
  • 3月14日软件工程结队日报
    学习时间:五小时代码量:600博客量:1任务:今天我和我的cp完成了对于之前安卓程序的收尾工作,然后绘制完了地铁查询系统的前端界面。 ......
  • 2023.3.14 状压 dp 模拟赛题解
    好强啊。不说是谁了,都好强啊呜呜呜。   首先T1的一个优化luoguP1842奶牛玩杂技,需要一个贪心排序来优化序列顺序。关于贪心排序:像这样有两种及以上性质的序列,......
  • Spring Study lesson02 - 案例学习二-23-03-14
    把dao中UserDao的实现类写入到beans.xml中,三个实现类。<beanid="MySqlDaoImpl"class="com.feijian.dao.MySqlDaoImpl"/><beanid="OracleDaoImpl"class="com.feiji......
  • 浙江理工大学每日一题3.14
    点击查看代码#pragmaGCCoptimize(1)#pragmaGCCoptimize(2)#pragmaGCCoptimize(3,"Ofast","inline")#include<bits/stdc++.h>typedeflonglongll;using......
  • 【洛谷】P2414 [NOI2011] 阿狸的打字机(AC自动机+离线询问)
    原题链接题意给定\(n\)个字符串,\(m\)次询问一个字符串\(x\)在另一个字符串\(y\)的出现次数。\(1\leqn,m\leq10^5\)。思路要解决多个字符串的问题,不难想到......
  • 2023.3.14结对总结
    今天建立了数据库的链接,完善了Android个人作业,构思一条线上车站的查找函数,输入起始站得到线路1输入终止站得到线路2,将线路1与线路2对比得到一条线的路线。   ......
  • 2023/3/14结对总结
     ......
  • 20230314-Python-文件的读写
    1.文件读取          2.文件写入     ......