A. Buying Torches
题目大意:
初始时你有一根木棍，你可以选择下列操作的一种：
1、用一根木棍换取x根木棍
2、用y根木棍换成一个炭
现在需要组成k根火炬（一根木棍一个炭），求最小操作数
思路:
k根火炬需要的木棍数为k + k ∗ y − 1 ，求用操作1使得木棍数量不少于该数值的最小操作次数即可，最后加上k次换木炭就行
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int x, y, k;
void solve(){
cin>>x>>y>>k;
x--;
int ans=k+k*y-1;
cout<<(ans+x-1)/x+k<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T;
cin>>T;
while(T--) solve();
return 0;
}
B. Negative Prefixes（贪心，构造）
题目大意:
给你一个长度为n的数组a，每个数字对应一个0或者1，为0即为可以移动，你可以任意移动对应为0的数字
使得前缀和数组p的最大值所在的位置最小
输出移动后的数组
思路:
为使得前缀和的最大值尽可能的早出现，所以我们需要将可以移动的值中大的值尽可能的往前放
即为将可以移动的位置的值按非递增的方式培训然后插入不可移动中
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N], flag[N];
int b[N];
void solve(){
cin>>n;
memset(b,0,sizeof(b));
int k=0;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++){
cin>>flag[i];
if(flag[i]==0){
b[++k]=a[i];
}
}
sort(b+1, b+1+k);
for(int i=1; i<=n; i++){
if(flag[i]==1) cout<<a[i]<<" ";
else cout<<b[k--]<<" ";
}
cout<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T;
cin>>T;
while(T--) solve();
return 0;
}
C. Mortal Kombat Tower（DP）
题目大意:
你和你朋友打游戏，给你一个长度为n的数组代表boss，数组中包含0和1，你朋友先手
你可以打败任意boss而不消耗值，你朋友在打败1的boss时需要消耗1，每次可以选择打败1~2个boss
求最小的通关花费
思路:
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N];
int dp[N];
void solve(){
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
if(n==1 || n==2) {cout<<a[1]<<endl; return ;}
dp[1]=a[1], dp[2]=a[1]+a[2];
dp[3]=dp[1]+a[3], dp[4]=min(min(dp[2],dp[1])+a[4], dp[1]+a[3]+a[4]);
for(int i=5; i<=n; i++)
dp[i]=min( min(dp[i-2], dp[i-3]) +a[i], min(dp[i-3], dp[i-4]) +a[i] +a[i-1]);
cout<<min(min(dp[n], dp[n-1]), dp[n-2])<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T;
cin>>T;
while(T--) solve();
return 0;
}
D. Trash Problem（线段树）
题目大意:
有n堆垃圾，每一堆的坐标为x，合并两堆垃圾的花费为这两堆垃圾的坐标之差的绝对值。
你可以进行q次操作。1 x表示在x位置上增加一堆垃圾，0 x表示删除x位置上的垃圾。
输出将这n堆垃圾合并成两堆垃圾所需的花费，以及每次操作之后改变的答案。
思路:
每次合并垃圾之后，所有相邻的垃圾的坐标差去掉最大值之后的和即为此次合并的最小花费
先将所有需要用的数进行一个离散化，再用这个离散化之后的数组建树。
用权值线段树维护：
相邻的两个有效数的差的最大值max。u段的max等于 两个子段中的max 和 右子段的左端点值（最大值）-左子段的右端点值（最小值）的最大值。因此我们还需要维护两个额外信息：这一段中的最大值ma和最小值mi。
AC Code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
struct Node{
int mi,ma; //每一段的最小值、最大值
int max; //这一段中相邻两个数的差的最大值
}tr[N*4];
int a[N],b[N];
bool st[N]; //标记每个点十分在当前序列中
int op[N],q[N]; //记录q次操作的询问（离线算法）
void pushup(int u) //注意不要让st[i]=0的点去跟新信息
{
tr[u].ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
if(tr[u<<1].mi==0||tr[u<<1|1].mi==0) tr[u].mi=max(tr[u<<1].mi,tr[u<<1|1].mi);
else tr[u].mi=min(tr[u<<1].mi,tr[u<<1|1].mi);
if(tr[u<<1].ma==0||tr[u<<1|1].mi==0) tr[u].max=max(tr[u<<1].max,tr[u<<1|1].max);
else tr[u].max=max(max(tr[u<<1].max,tr[u<<1|1].max),tr[u<<1|1].mi-tr[u<<1].ma);
}
void build(int u,int l,int r)
{
if(l==r)
{
if(st[l]) tr[u]={a[l],a[l],0}; //因为此段只有一个点，因此max=0
else tr[u]={0,0,0}; //st[i]=0的点统一赋成 0 0 0
}
else
{
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int x,bool op)
{
if(l==r)
{
if(op) tr[u]={a[l],a[l],0}; //op=1，加入一个数
else tr[u]={0,0,0}; //op=0，删除一个数
}
else
{
int mid=l+r>>1;
if(x<=mid) modify(u<<1,l,mid,x,op);
else modify(u<<1|1,mid+1,r,x,op);
pushup(u);
}
}
int query() //最小合并费用即为整段的相邻数的差（最大值-最小值）-相邻数差的最大值max
{
return tr[1].ma-tr[1].mi-tr[1].max;
}
int main()
{
int n,Q;
scanf("%d %d",&n,&Q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i]; //b[]备份初始的n个数
}
for(int i=1;i<=Q;i++) //将所有需要用到的坐标放入a[]中
{
scanf("%d %d",&op[i],&q[i]);
a[i+n]=q[i];
}
sort(b+1,b+1+n);
sort(a+1,a+1+n+Q); //离散化
int cnt=unique(a+1,a+1+n+Q)-a-1;
for(int i=1;i<=Q;i++)
q[i]=lower_bound(a+1,a+1+cnt,q[i])-a;
int k=1;
for(int i=1;i<=n;i++) //将初始的n个数进行标记
{
while(b[i]!=a[k]) k++;
st[k]=true;
}
build(1,1,cnt); //建树
printf("%d\n",query()); //查询
for(int i=1;i<=Q;i++)
{
modify(1,1,cnt,q[i],op[i]);
printf("%d\n",query());
}
return 0;
}
Comments | NOTHING