CodeForces,  ICPC/ACM

Codeforces Round 95

2020年9月18日 /

A – Buying Torches

题意

初始状态下你有一根火柴，合成一个火炬需要一根火柴和一份煤。

你可以做如下的两种交易

  • 你可以用$1$根火柴去兑换$x$根火柴
  • 你可以用$y$根火柴去兑换$1$份煤

试问你需要合成把火炬至少需要交易多少次

解题思路

你需要的火柴总数是$y\times(k+1)$合成这么多的火柴至少需要交易$\lceil \frac{y\times(k+1)-1}{x-1}\rceil$次，所以总的交易次数就是$k+\lceil \frac{y\times(k+1)-1}{x-1}\rceil$

时间复杂度$O(1)$

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    int T;
    ll x,y,k;
    cin>>T;
    while (T--)
    {
        cin>>x>>y>>k;
        cout<<k+(ll)ceil(1.0l*(k*y+k-1)/(x-1))<<endl;
    }
    return 0;
}

B – Negative Prefixes

题意

你有一个长度为数组。

这些数组中的某些位置是被锁住的，锁住的位置是不能和其他位置交换的。

定义$p$为$a$的前缀和数组，$k=\max(j)(p_j<0)$，若$p_j\ge0$恒成立那么$k=0$。

我们需要打乱数组，使得$k$最小

解题思路

简单贪心一下，我们只要把那些没有被锁住的位置的元素按照从小到大的顺序排序一下就好了。

时间复杂度$O(n\log n)$

参考代码

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
using namespace std;
const int MAXN=(int)1e5+5;
int a[MAXN];
int l[MAXN];
vector<int>p;
int main()
{
    int T,n;
    cin>>T;
    while (T--)
    {
        cin>>n;
        p.clear();
        rep(i,0,n)cin>>a[i];
        rep(i,0,n)cin>>l[i];
        rep(i,0,n)if(!l[i])p.push_back(a[i]);
        sort(all(p),greater<int>());
        for (int i = 0,j=0; i < n; i++)
        {
            if(l[i])cout<<a[i]<<" ";
            else cout<<p[j++]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    int T;
    ll x,y,k;
    cin>>T;
    while (T--)
    {
        cin>>x>>y>>k;
        cout<<k+(ll)ceil(1.0l*(k*y+k-1)/(x-1))<<endl;
    }
    return 0;
}

C – Mortal Kombat Tower

题意

给定一个长度为$n$的由$0$和$1$构成的数组$a$。

每个回合你和你的朋友交替从这个数组中按照顺序取走数字。

每个回合你们可以选择取$1$个或者$2$个数字。

你的朋友每取走一个$1$花费就加$1$。

第一个回合是你朋友的回合

试问花费最少是多少。

解题思路

我想到了一个比较简单的DP思路

$dp_{i,j,k}$表示到第$i$个位置第$j$个人取连续的第$k$次的所需的最小花费是多少。

然后我们就可以很快的写出转移方程（$j=1$代表朋友取$j=2$代表自己取）

$dp_{i,1,1}=\min(dp_{i-1,2,2},dp_{i-1,2,1})+a_i$

$dp_{i,1,2}=dp_{i-1,1,1}+a_i$

$dp_{i,2,1}=\min(dp_{i-1,1,1},dp_{i-1,1,2})$

$dp_{i,2,2}=dp_{i,2,1}$

时间复杂度$O(n)$

空间复杂度，虽然可以压成$O(n)$但是可读性几乎没有所以压成$O(2n)$就可以了

参考代码

#include <bits/stdc++.h>
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
using namespace std;
const int MAXN=(int)2e5+5;
int a[MAXN];
int dp[MAXN][2];
int main()
{
    int T,n;
    cin>>T;
    while (T--)
    {
        cin>>n;
        rep(i,0,n)cin>>a[i];
        int res=0;
        MEM(dp,0x3f);
        dp[0][0]=a[0];
        if(n>1)
        {
            dp[1][0]=dp[0][0]+a[1];
            dp[1][1]=dp[0][0];
        }
        for (int i = 2; i < n; i++)
        {
            dp[i][0]=min(dp[i-1][1],dp[i-2][1])+a[i];
            dp[i][1]=min(dp[i-1][0],dp[i-2][0]+a[i-1]);
        }
        res=dp[n-1][0];
        res=min(dp[n-1][1],res);
        if(n>1)res=min(dp[n-2][0]+a[n-1],res);
        if(n>1)res=min(dp[n-2][1],res);
        cout<<res<<endl;
    }
    
    return 0;
}

D – Trash Problem

题意

给定$n$个不重复的一维上的坐标

有$q$个询问

  • $0\ x$表示加入坐标$x$
  • $1\ x$表示删除坐标$x$

对于初始状态和每次询问后你需要求将所有的坐标最多移动到两个不同的位置上，对于坐标$x$上的所有元素移动到$x-1$或者$x+1$一共花费$1$，这样花费的最小值。

解题思路

在所有存在的点中连接两条边到两边最近的点形成路径，花费的最小值就是所有路径的和减去最长的路径。

对于每个加入的点我们需要找到它的前边的点和后面的点，然后与前后两点形成两条边，删去原先前后两个点形成的边。

找前后两个点我们可以用权值线段树来实现，但是因为数据范围太大，所以我们把数据和询问离线后离散化一下就好了，接下来用一个muti_set来维护最大边，和边的增删。

赛后发现要啥权值线段树set不香吗？

预处理时间复杂度为$n\log n$，查询的时间复杂度为$\log^2n$，时间上限取决于muti_set，如果用另外一颗权值线段树代替muti_set查询时间复杂度可以降到​$O(\log n)$

参考代码

离散化+权值线段树版本

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
const int MAXN=(int)2e5+5;
using namespace std;
int num[MAXN*5];

void update(int p,int l,int r,int v,int op)
{
	num[p]+=op;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)update(p<<1,l,mid,v,op);
	else update(p<<1|1,mid+1,r,v,op); 
}
int Findpre(int p,int l,int r)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(num[p<<1|1])return Findpre(p<<1|1,mid+1,r);
	return Findpre(p<<1,l,mid);
}

int Pre(int p,int l,int r,int v)
{
	if(r<v)
	{
		if(num[p])return Findpre(p,l,r);
		return 0;
	}
	int mid=(l+r)>>1,Re;
	if(mid+1<v&&num[p<<1|1]&&(Re=Pre(p<<1|1,mid+1,r,v)))return Re;
	return Pre(p<<1,l,mid,v);
} 
 
int Findnext(int p,int l,int r)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(num[p<<1])return Findnext(p<<1,l,mid);
	return Findnext(p<<1|1,mid+1,r);
} 
 
int Next(int p,int l,int r,int v)
{
	if(v<l)
	{
		if(num[p])return Findnext(p,l,r); 
		return 0;
	}
	int mid=(l+r)>>1,Re;
	if(v<mid&&num[p<<1]&&(Re=Next(p<<1,l,mid,v)))return Re;
	return Next(p<<1|1,mid+1,r,v);
}

int n,q;
vector<int>v;
unordered_map<int,int>mp;
int op[MAXN],k[MAXN];
int a[MAXN];
multiset<int,greater<int>>h;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    cin>>n>>q;
    rep(i,0,n){cin>>a[i];v.push_back(a[i]);}
    rep(i,0,q){cin>>op[i]>>k[i];v.push_back(k[i]);}
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for (int i = 0; i < v.size(); i++)
    {
        mp[v[i]]=i;
    }
    
    sort(a,a+n);
    int m=v.size();
    ll s=0;
    for (int i = 0; i < n; i++)update(1,-1,m,mp[a[i]],1);
    for (int i = 1; i < n; i++){h.insert(a[i]-a[i-1]);s+=a[i]-a[i-1];}
    update(1,-1,m,-1,1);
    update(1,-1,m,m,1);
    cout<<s-*h.begin()<<endl;
    for (int i = 0; i < q; i++)
    {
        int ha=mp[k[i]];
        int pre=Pre(1,-1,m,ha);
        int nex=Next(1,-1,m,ha);
        if(op[i])
        {
            if(nex!=m&&pre!=-1)
            {
                h.erase(h.lower_bound(v[nex]-v[pre]));
                s-=v[nex]-v[pre];
            }
            if(nex!=m)
            {
                h.insert(v[nex]-k[i]);
                s+=v[nex]-k[i];
            }
            if(pre!=-1)
            {
                h.insert(k[i]-v[pre]);
                s+=k[i]-v[pre];
            }
            update(1,-1,m,ha,1);
        }else
        {
            if(nex!=m&&pre!=-1)
            {
                h.insert(v[nex]-v[pre]);
                s+=v[nex]-v[pre];
            }
            if(nex!=m)
            {
                h.erase(h.lower_bound(v[nex]-k[i]));
                s-=v[nex]-k[i];
            }
            if(pre!=-1)
            {
                h.erase(h.lower_bound(k[i]-v[pre]));
                s-=k[i]-v[pre];
            }
            update(1,-1,m,ha,-1);
        }
        cout<<s-*h.begin()<<endl;
    }
    
    return 0;
}

直接set版本

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
const int MAXN=(int)2e5+5;
using namespace std;

int n,q;
unordered_map<int,int>mp;
int op,x;
int a[MAXN];
set<int>se;
multiset<int,greater<int>>h;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    cin>>n>>q;
    rep(i,0,n){cin>>a[i];}
    
    sort(a,a+n);
    ll s=0;
    for (int i = 0; i < n; i++)se.insert(a[i]);
    for (int i = 1; i < n; i++){h.insert(a[i]-a[i-1]);s+=a[i]-a[i-1];}
    cout<<s-*h.begin()<<endl;
    se.insert(-1);
    while (q--)
    {
        cin>>op>>x;
        auto pre=se.lower_bound(x);
        auto nex=se.upper_bound(x);
        pre--;
        if(op)
        {
            if(nex!=se.end()&&pre!=se.begin())
            {
                h.erase(h.lower_bound(*nex-*pre));
                s-=*nex-*pre;
            }
            if(nex!=se.end())
            {
                h.insert(*nex-x);
                s+=*nex-x;
            }
            if(pre!=se.begin())
            {
                h.insert(x-*pre);
                s+=x-*pre;
            }
            se.insert(x);
        }else
        {
            if(nex!=se.end()&&pre!=se.begin())
            {
                h.insert(*nex-*pre);
                s+=*nex-*pre;
            }
            if(nex!=se.end())
            {
                h.erase(h.lower_bound(*nex-x));
                s-=*nex-x;
            }
            if(pre!=se.begin())
            {
                h.erase(h.lower_bound(x-*pre));
                s-=x-*pre;
            }
            se.erase(x);
        }
        cout<<s-*h.begin()<<endl;
    }
    
    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点，欢迎评论。x
()
x