E
https://codeforces.com/contest/1154/problem/E
题意
一个大小为n(1e6)的数组(a[i])(n),两个人轮流选数,先找到当前数组中最大的数然后选择以这个数为半径k的所有数,问两个人的选数情况
题解
- set维护剩下数的最大
- 链表维护左右第一个存在的数的位置
代码
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n,k,a[MAXN],p[MAXN],L[MAXN],R[MAXN],group=0,ans[MAXN];
set<int>S;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
S.insert(a[i]);
L[i]=i-1;R[i]=i+1;
}
while(S.size()){
int x=*(--S.end());
int l=p[x],r=p[x],d=0;
while(d<=k&&l>=1){
//cout<<a[l]<<endl;
S.erase(a[l]);
ans[l]=group+1;
l=L[l];
d++;
}
d=0;
while(d<=k&&r<=n){
//cout<<a[r]<<endl;
S.erase(a[r]);
ans[r]=group+1;
r=R[r];
d++;
}
L[r]=l;
R[l]=r;
group^=1;
}
for(int i=1;i<=n;i++)printf("%d",ans[i]);
}
F
https://codeforces.com/contest/1154/problem/F
题意
有n个物品,你需要买k个,每个物品价格为(a[i]),然后m个优惠方式,买(x[i])个的话最便宜的y[i]个免费
题解
- 贪心:买最便宜的k个,x相同取y最大
- 定义(dp[i])为买前i个用的最少费用,(dp[i]=min(dp[i],dp[j]+sum[i]-sum[j+of[i-j]]),0leq j leq i-1)
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;
ll dp[2005],a[200005],sum[200005];
int n,m,k,x,y,of[200005];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
of[x]=max(of[x],y);
}
sort(a+1,a+n+1);
k=min(n,k);
for(int i=1;i<=k;i++)sum[i]=sum[i-1]+a[i];
memset(dp,inf,sizeof(dp));
dp[0]=0;
for(int i=1;i<=k;i++)
for(int j=0;j<i;j++)
dp[i]=min(dp[i],dp[j]+sum[i]-sum[j+of[i-j]]);
cout<<dp[k];
}
G
https://codeforces.com/contest/1154/problem/G
题意
一个大小为n(1e6)的数组(a[i])(1e7),问lcm(a[l],a[r])最小的l和r,l!=r
题解
- (a[i])(1e7),枚举公因数位置,nlogn
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>G[10000005];
ll n,ans,a,b,y,A,B,x;
int main(){
cin>>n;
for(ll i=1;i<=n;i++){
scanf("%lld",&x);
if(G[x].size()<2)G[x].push_back(i);
}
ans=1e18;
a=b=0;
for(ll i=1;i<=1e7;i++){
x=y=a=b=0;
for(ll j=i;j<=1e7;j+=i){
if(a==0){
if(G[j].size()>=2){
a=G[j][0];
b=G[j][1];
x=y=j;
break;
}else if(G[j].size()){
a=G[j][0];
x=j;
}
}else if(b==0){
if(G[j].size()){
b=G[j][0];
y=j;
break;
}
}
}
if(x&&y&&a&&b&&ans>x/__gcd(x,y)*y){
ans=x/__gcd(x,y)*y;
A=a;B=b;
}
}
cout<<min(A,B)<<" "<<max(A,B);
}