Codeforces Round #624 (Div. 3) A-F
比赛链接
A.分情况讨论一下即可
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,a,b;
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>a>>b;
if(a==b)cout<<0<<'\n';
else if(b>a && (b-a)%2)cout<<1<<'\n';
else if(b>a){
cout<<2<<'\n';
}else if(a>b && (a-b)%2==0)cout<<1<<'\n';
else{
cout<<2<<'\n';
}
}
return 0;
}
B.模拟排序过程即可
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,n,m,a[N],vis[N];
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
vis[i]=0;
}
for(int i=1;i<=m;i++){
int x;
cin>>x;
vis[x]=1;
}
int sta=0;
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++){
if(a[j]>a[j+1]){
if(vis[j]){
swap(a[j],a[j+1]);
}else{
sta=1;
break;
}
}
}
}
if(sta)cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
C.前缀和累加即可
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,n,m,p[N],cnt[N][33],ans[33];
char a[N];
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n>>m>>a+1;
memset(ans,0,sizeof ans);
for(int i=1;i<=n;i++){
for(int j=0;j<26;j++)cnt[i][j]=cnt[i-1][j];
cnt[i][a[i]-'a']++;
}
for(int i=0;i<26;i++)ans[i]=cnt[n][i];
for(int i=1;i<=m;i++){
cin>>p[i];
for(int j=0;j<26;j++){
ans[j]+=cnt[p[i]][j];
}
}
for(int i=0;i<26;i++)cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}
D.枚举B，二分出A,C即可。注意枚举范围。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,a[N],b,c;
set<int>st[N],ts[N];
int main() {
ios::sync_with_stdio(false);
for(int i=1;i<=20000;i++){
for(int j=i;j<=40000;j+=i){
st[i].insert(j);
ts[j].insert(i);
}
}
for(cin>>t;t;t--){
for(int i=1;i<=3;i++)cin>>a[i];
sort(a+1,a+4);
int ans=1e9,x,y,z;
for(int i=1;i<=20000;i++){
int tot=abs(a[2]-i);
auto f=st[i].lower_bound(a[3]);
auto g=st[i].upper_bound(a[3]);
--g;
int tsa;
if(abs(a[3]-*f)>abs(a[3]-*g))tsa=*g;
else tsa=*f;
int on;
f=ts[i].lower_bound(a[1]);
g=ts[i].upper_bound(a[1]);
--g;
if(abs(*f-a[1])>abs(*g-a[1]))on=*g;
else on=*f;
tot+=abs(a[3]-tsa)+abs(a[1]-on);
if(tot<ans){
ans=tot;
x=on;y=i;z=tsa;
}
}
cout<<ans<<'\n';
cout<<x<<' '<<y<<' '<<z<<'\n';
}
return 0;
}
E.先构造成一条链，然后不断往上移即可，要注意模拟过程的各种细节问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,n,d;
int f[N],de[N],L[N],R[N],fa[N];
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n>>d;int sta=0;
for(int i=1;i<=n;i++){
f[i]=0;L[i]=R[i]=0;de[i]=0;fa[i]=0;
}
for(int i=2;i<=n;i++)f[i]=i-1,de[i]=i-1,L[i-1]=i,fa[i]=i-1;
int now=(1+n-1)*(n-1)/2;
for(int i=n;i>=2&&now>d;i--){
int dis=now-d,res=-1,pos;
for(int j=1;j<=n;j++){
if(j==i)
continue;
if(L[j]&&R[j]){
continue;
}
if(de[j]+1>=de[i])
continue;
if(de[i]-de[j]-1>dis)
continue;
if(de[i]-1-de[j]>res){
res=de[i]-de[j]-1;
pos=j;
}
}
if(res==-1){
sta=1;
break;
}
now-=res;
if(pos==1){
if(L[fa[i]]==i){
L[fa[i]]=0;
}else R[fa[i]]=0;
R[pos]=i;
L[i]=R[i]=0;
f[i]=pos;
fa[i]=pos;
de[i]=1;
}else{
if(L[fa[i]]==i){
L[fa[i]]=0;
}else R[fa[i]]=0;
fa[i]=pos;
L[i]=R[i]=0;
if(!L[pos])L[pos]=i;
else R[pos]=i;
f[i]=pos;
de[i]=de[pos]+1;
}
}
if(sta||now!=d){
cout<<"NO\n";
continue;
}
cout<<"YES\n";
for(int i=2;i<=n;i++)cout<<f[i]<<' ';
cout<<'\n';
}
return 0;
}
F.树状数组的简单应用。讨论一下几种情况即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,a[N],v[N],f[N];
int c[N],l;
int d[N],r;
void add(LL *t,int p,int d){
for(;p<N;p+=p&-p)t[p]+=d;
}
LL get(LL *t,int p){
LL ans=0;
for(;p;p-=p&-p)ans+=t[p];
return ans;
}
LL t[N],num[N];
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)f[i]=i;
sort(f+1,f+1+n,[](int x,int y){
return a[x]<a[y];
});
LL ans=0;
int cnt=0;
LL sum=0;
for(int i=1;i<=n;i++){
if(v[f[i]]==0){
ans+=1ll*cnt*a[f[i]]-sum;
}
if(v[f[i]]<=0){
cnt++;
sum+=a[f[i]];
}
}
for(int i=1;i<=n;i++){
if(v[f[i]]<0){
c[++l]=v[f[i]];
}
}
sort(c+1,c+1+l);
int len=unique(c+1,c+1+l)-c-1;
for(int i=1;i<=n;i++){
if(v[f[i]]<0){
d[f[i]]=lower_bound(c+1,c+1+len,v[f[i]])-c;
}
}
for(int i=1;i<=n;i++){
if(v[f[i]]<0){
ans+=get(num,d[f[i]])*a[f[i]]-get(t,d[f[i]]);
add(num,d[f[i]],1);
add(t,d[f[i]],a[f[i]]);
}
}
cnt=0;sum=0;
l=0;
for(int i=1;i<=n;i++){
if(v[f[i]]>0){
c[++l]=v[f[i]];
}
}
sort(c+1,c+1+l);
len=unique(c+1,c+1+l)-c-1;
for(int i=1;i<=n;i++){
if(v[f[i]]>0)d[f[i]]=lower_bound(c+1,c+1+len,v[f[i]])-c;
}
cnt=0;sum=0;
memset(num,0,sizeof num);
memset(t,0,sizeof t);
for(int i=1;i<=n;i++){
if(v[f[i]]<=0){
cnt++;
sum+=a[f[i]];
}else{
ans+=1ll*get(num,d[f[i]])*a[f[i]]-get(t,d[f[i]]);
ans+=1ll*cnt*a[f[i]]-sum;
add(num,d[f[i]],1);
add(t,d[f[i]],a[f[i]]);
}
}
cout<<ans<<'\n';
return 0;
}
腾讯成长空间 448人发布