這次比賽從名字就可以看出非常水，然鵝因為第一次打codeforces不太熟悉操作只來的及做簽到題（還錯了一次）
A，B，C都是簽到題考點思維就不寫了
D題
https://codeforces.ml/problemset/problem/1311/D
題目大意是:有t組資料每組資料給你三個數，a，b，c每次一個數加一或
者減一都算一次操作（不能為變負數），問最小的操作次數構造出A，
B，C使b%a==0，c%b==0，
t<1000,a,b,c<1e4 時限2s
首先想到是找b的倍數與a，c最近的數再直接加減
再一看時限兩秒，，，果斷暴力
然后就列舉這樣的數對A，B，C，答案就是其a，b，c的差的最小值
#代碼后面有時間再補
E題：
https://codeforces.ml/contest/1311/problem/E
奈何本人沒文化，題目沒怎么懂，日后有時間再補（flag）
接下來才是重頭戲
F題
https://codeforces.ml/problemset/problem/1311/F
題目大意：給你n（<2e5）個點a1，a2，...，an在同一個數軸上，保證坐標不會重復， 每個點有一個固定的速度（-1e8到1e8），對某一個t時刻，某兩個點距離最小，輸出這些最小值之和（min d（i，j）i<j之和）
容易先想到將a按坐標排序，xi<xj,vi<vj那d（i，j）肯定不會減小則min d（i，j）=xj-xi，如果vi>vj 則min d（i，j）=0
暴力n^2代碼很簡單
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n;
long long tot;
struct node
{
long long x,v;
}a[N];
bool cmp(node x,node y)
{
return x.x<y.x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i].x);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i].v);
sort(a+1,a+n+1,cmp);
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i].v>=a[j].v)
{
tot+=a[i].x-a[j].x;
}
}
}
printf("%lld",tot);
return 0;
}
因為ans+=xi?cnt?sum可以將每次列舉看成從當前新建的陣列中添加一個元素，因為從小到大遍歷的所以速度小于i而x大于i的一定還沒有被加入新建的陣列所以此想法可以算出滿足條件的num和tot，
具體做法是新建兩個陣列q,p開始都為空，第一個陣列q[i]代表a[1~i].v中速度為q的a[1~i].x（坐標）的和，第二個陣列p[i]代表速度為p[i]的個數而這可以用樹狀陣列優化，
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,m,pos,v[N];
long long tot,s[N][2];
struct node
{
long long x,v;
}a[N];
bool cmp(node x,node y)
{
return x.x<y.x;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)//更新陣列
{
while(x<=n)
{
s[x][0]++;
s[x][1]+=val;
x+=lowbit(x);//從x往上更新所有q，p陣列有關a[x]的值
}
}
long long getsum(int x,int flag)//獲取陣列1~x的和
{
long long res=0;
while(x)
{
res+=s[x][flag];
x-=lowbit(x); //從x往下加故是減號
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i].x);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].v);
v[i]=a[i].v;
}
sort(a+1,a+n+1,cmp);
sort(v+1,v+n+1);
m=unique(v+1,v+n+1)-v-1;
for(int i=1;i<=n;i++)
{
pos=lower_bound(v+1,v+m+1,a[i].v)-v;
tot+=getsum(pos,0)*a[i].x-getsum(pos,1);//s[][0]代表p[i],s[][1]代表q[i]
update(pos,a[i].x);
}
printf("%lld",tot);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/206285.html
標籤：其他
上一篇：左旋轉字串