Codeforces Round#624(Div.3)(D暴力、E思考+複雑シミュレーション、F線分ツリー)


タイトルリンク
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