Codeforces Round#624(Div.3)(D暴力、E思考+複雑シミュレーション、F線分ツリー)
4598 ワード
タイトルリンク
D. Three Integers
标题:a b cあなたは今この3つの数に対して+1-1操作を行って最小限の操作を聞いた後にaをb bを除去してcを除去することができます
やり方:暴力はaとbを列挙すればいい、注意範囲はhackになりやすい
E. Construct the Binary Tree
題意:n dがツリーを表すn個のノードを入力し、各ノードはツリーに深さがあり、すべてのノードの度の和がdに等しくなるように二叉木を構築します.
出力NOが存在しない
構想:構想は簡単で、まず1本の単鎖を構築して、それから一番下からあるいは一番上から1つの点を取って上へ移動することを考えることができて、私のここは上から1つの点を選ぶのです.
コードリファレンスjiufengからのコミットコード
どのようにシミュレーションして書くのが複雑ですか.
F. Moving Points
題意:与えられたn個の位置xiとn個の速度viの位置がx=vi*t+xiに変化することを与えて、今あなたに2点の距離と最小を求めて、この問題はすべての点のtが一致することを読みやすくて、実はさもなくば各点の時間は異なって、その上各対の点の時間も異なっています.
つまり任意の2つの点の最も近い距離を求める時の距離と
方法:xを大きいから小さい順に並べ、v離散化に従ってセグメントツリー上でxが自分より小さいvが自分より大きい点を検索します.これらの点はこの点と重なるからです.
答えはまずすべての点対の距離と-重なることができる距離の点対の距離と
D. Three Integers
标题:a b cあなたは今この3つの数に対して+1-1操作を行って最小限の操作を聞いた後にaをb bを除去してcを除去することができます
やり方:暴力はaとbを列挙すればいい、注意範囲はhackになりやすい
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=2e5+10;
int n,m;
ll a,b,c;
ll A,B,C;
ll mx;
void cal(int i,int j,int k)
{
int t=abs(a-i)+abs(b-j)+abs(k-c);
if(t>_;while(_--)
{
scanf("%lld%lld%lld",&a,&b,&c);
mx=0x3f3f3f3f3f3f3f3f;
for(ll i=1;i<=2e4;++i){
for(ll j=i;j<=2e4;j+=i){
ll x=i,y=j,z=c/y*y;
if(z>=y) cal(x,y,z);
z=(c/y+1)*y;
cal(x,y,z);
}
}
printf("%lld
",mx);
printf("%lld %lld %lld
",A,B,C);
}
}
E. Construct the Binary Tree
題意:n dがツリーを表すn個のノードを入力し、各ノードはツリーに深さがあり、すべてのノードの度の和がdに等しくなるように二叉木を構築します.
出力NOが存在しない
構想:構想は簡単で、まず1本の単鎖を構築して、それから一番下からあるいは一番上から1つの点を取って上へ移動することを考えることができて、私のここは上から1つの点を選ぶのです.
コードリファレンスjiufengからのコミットコード
どのようにシミュレーションして書くのが複雑ですか.
#include
#define LL long long
#define PB push_back
#define POP pop_back()
#define PII pair
#define ULL unsigned long long
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1),eps=1e-10;
const int maxn=1<<17;
const int N=5e3+10,M=N*40;
int n,d;
int fa[N];
int son[N];
int de[N];//
int dp[N];//dp[i]: i dp[i]
int main()
{
de[1]=1;
int t;
cin>>t;
while(t--){
scanf("%d%d",&n,&d);
memset(de,0,sizeof(de));
de[1]=1;
int s=0;
for(int i=1;i<=n;i++)s+=i-1;//
int now=1;
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+1;// i-1
de[dp[i]]--;//
if(s-(n-i+1)>=d){//i , , n-i+1
//printf("i:%d n-i+1:%d d:%d
",i,n-i+1,d);
if(de[dp[i]-1]){// ,
s-=(n-i+1);
de[dp[i]-1]--;// dp[i]-1 , de[dp[i]-1]
de[dp[i]]++;//dp[i] +1 32
dp[i]--;//i
}
}
de[dp[i]+1]+=2;
//cout<
F. Moving Points
題意:与えられたn個の位置xiとn個の速度viの位置がx=vi*t+xiに変化することを与えて、今あなたに2点の距離と最小を求めて、この問題はすべての点のtが一致することを読みやすくて、実はさもなくば各点の時間は異なって、その上各対の点の時間も異なっています.
つまり任意の2つの点の最も近い距離を求める時の距離と
方法:xを大きいから小さい順に並べ、v離散化に従ってセグメントツリー上でxが自分より小さいvが自分より大きい点を検索します.これらの点はこの点と重なるからです.
答えはまずすべての点対の距離と-重なることができる距離の点対の距離と
#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct node
{
ll x,v;
}a[N];
ll X[N],len;
int n;
bool cmp(node a,node b)
{
return a.x>1;
if(pos<=mid) up(id<<1,l,mid,pos,val);
else up(id<<1|1,mid+1,r,pos,val);
s1[id]=s1[id<<1]+s1[id<<1|1];
s2[id]=s2[id<<1]+s2[id<<1|1];
}
void qu(int id,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr){
sum+=s1[id];
num+=s2[id];
return ;
}
int mid=l+r>>1;
if(ql<=mid) qu(id<<1,l,mid,ql,qr);
if(qr>mid) qu(id<<1|1,mid+1,r,ql,qr);
}
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);
X[++len]=a[i].v;
}
sort(X+1,X+1+len);
len=unique(X+1,X+1+len)-X-1;
sort(a+1,a+1+n,cmp);
ans=0,num=1,x1=a[1].x,sum=0;
for(int i=2;i<=n;++i){
ans+=num*(a[i].x-x1)-sum;
sum+=a[i].x-x1;
num++;
}
//printf("ans:%lld
",ans);
num=0,sum=0;
for(int i=1;i<=n;++i){
a[i].v=getid(a[i].v);
if(i==1){
up(1,1,len,a[i].v,a[i].x-x1);
continue;
}
num=0,sum=0;
if(a[i].v