Codeforces Round 361 div2

雪崩、全部間違ってGGを落としました.前の2つの問題は前の問題に比べて難易度が高いでしょうが、A問題には1ではなく0から始まるという低級な間違いを犯すべきではありません.B問題の差は多くないBFSですが、私はその時ずっと最短の経路を回って書いていて、ずっといろいろなTLEとWAを持っていました.C問題は1本の2点で、とても簡単で、昨日ずっとBを書いていて、しなかったのは本当に残念です.
A
DFSで書いたのですが、比較的面倒でした.その変化の順序に従って、0-9をすべて試して、満足しているかどうかを見ます.そのサイクルでうっかり1-9と書いてしまい、そのまま崩れてしまいました.ああ、教訓.
B
頂点1から他のすべての頂点への最短パス値を求めることです.2つのポイント間の距離は、下付きの差の絶対値です.また、各ポイントには自分のaiがあり、ポイントiからaiまでの距離は1です.全部で20 wの頂点がありますが、そこを最短にする方法で直接単源最短経路を求めたいのですが、SPFA(時間複雑度O(kE))でもスタック最適化dijkstra(時間複雑度O(E+nlogn))でもタイムアウトします.最後に自分でまた変なdfsを試してみましたが、タイムアウトして、最後までここでカードが終わりました.2日目に問題解を見るとBFSで書かれていることがわかりました.DFS拡張の状態が多すぎる(毎回n個ある)ため、繰り返し計算をもたらすことが多く効率が低下しますが、実際には、後処理の距離が前処理の距離よりも長いので、現在の状態の前、後、ジャンプの3つの状態を処理すればいいのです.すでに処理したものはもう処理しないでください.

//
//  main.cpp
//  Codeforces 361 A
//
//  Created by    on 16/7/7.
//  Copyright © 2016    . All rights reserved.
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int MAX = 99999999;
int n,dis[200010],a[200010];
int flag[200010];
using namespace std;
queue<int> q,q2;
void pushing(int x,int y)
{
    if (x < 1 || x > n || flag[x])
        return ;
    q.push(x);
    q2.push(y);
    flag[x] = 1;
    dis[x] = y;
}
int main()
{
    int i,j,s,t;
    cin >> n;
    memset(flag,0,sizeof(flag));
    for (i = 1; i <= n; ++i)
        scanf("%d",&a[i]);
    q.push(1);
    q2.push(0);
    flag[1] = 1;
    while (!q.empty())
    {
        s = q.front();
        q.pop();
        t = q2.front();
        q2.pop();
        pushing(s-1,t+1);
        pushing(s+1,t+1);
        pushing(a[s],t+1);
    }

    for (i = 1; i <= n; ++i)
    {
        cout << dis[i] << " " ;
    }
    return 0;
}

C
第1の数をxとすると、第2、3、4の数はそれぞれkx、k*k*x、k*k*k*xとなり、そのうちkは任意である.そして,この4つの数はいずれもnより大きくすることができず,次に条件を満たすm群があると仮定した.テーマはmを与えて、m対のこの4つの数の最小nを満たすのはいくらですかを聞きます.最大値の最小を求める.2点n毎に,x毎に[n/(x^3)]個のkがある.xを2から3回ルートでnをループして求めればいいです.

//
//  main.cpp
//  Codeforces 361 C
//
//  Created by    on 16/7/7.
//  Copyright © 2016    . All rights reserved.
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int MAX = 99999999;
typedef long long ll;
ll n,dis[200010],a[200010];
using namespace std;
ll work(ll k)
{
    ll i,j;
    j = 0;
    for (i = 2; i * i * i <= k; ++i)
    {
        j += k/(i*i*i);
    }
    return j;
}
int main()
{
    ll h,i,j,l,r,mid,ans;
    cin >> n;
    l = 1;
    r = 1e18;
    ans = -1;
    while (l <= r)
    {
        mid  = (l+r) >> 1;
        h = work(mid);
        if (h >= n)
        {
            if (h==n)
                ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }

    cout << ans << endl;
    return 0;
}

D
二分+データ構造問題大意は、長さ20 wの2つの配列a,bを与え、max{a[i]}=min{b[i]}を満たすサブ区間がどれだけあるかを求めることです.私たちのやり方は区間の右位置を固定して、どれだけの左位置が条件を満たすかを求めます.そしてこれらを合わせるといいです.右位置が固定されると,a配列の左位置に関する最大値は単調に上昇せず,b配列は左位置について単調に低下しないので,二分法を用いて問題意を満たすサブ区間をどれだけ求めることができるかを求めた.このような値tを維持することで、[t,i]区間において、aの最大値がbの最小値よりも必ず小さい(これ以上位置tが機能しないため、このときtを後ろにずらす)ようにし、[t,i]区間内でaの最大値とbの最小値の位置を見つけ、それらの小さい値をmpとすると、t...mp位置の[j,i]から必ず満たされる.参考データ:6 1 2 3 2 2 6 7 1 2 3
3番目の位置では、Aの最大値3>Bの最小値1が、AとBが空になるまで一歩後ろにアーチされます.4番目の位置では、Aの最大値2=Bの最小値1であり、このとき4から4までが[j,i]で満たされる.cnt +=1; 5番目の位置では、Aの最大値2は依然として=Bの最小値1であり、このときAの最大値は4であり、Bの最小値は4であり、このとき4から4まで[j,i]が満たされる.cnt+=1は5番目の位置で、Aの最大値2は依然として=Bの最小値1であり、このときAの最大値は6であり、Bの最小値は6であり、このとき4から6まで[j,i]が満たされる.cnt+=3;

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long Long;
typedef pairint> PLI;

int main() {

    int N;
    cin >> N;
    vector<int> A(N),  B(N);
    for(int &v : A)cin >> v;
    for(int &v : B)cin >> v;
    int t = 0;
    Long cnt = 0;
    set SB;//  pair        ，             
    set> SA;//a       ，         greater  
    for(int i = 0; i < N; ++i){
        SA.insert(PLI(A[i],i));//            set 
        SB.insert(PLI(B[i],-i));
        while(!SA.empty() && !SB.empty() && SA.begin()->first > SB.begin()->first )
        {//    A       B      ，  [t,i]       ，   t   ，   A     ，B     
            SA.erase(SA.lower_bound(PLI(A[t],t)));
            SB.erase(SB.lower_bound(PLI(B[t],-t)));
            t++;
        }
        if(!SA.empty() && !SB.empty() && SA.begin()->first == SB.begin()->first){//    A     B      。        j   [j,i]    。
            int mp = min( SA.begin()->second, -(SB.begin()->second) );//A         t i         
            cnt += mp - t + 1;//j  [t,mp]   [j,i]  ...
        }
    }
    cout << cnt << endl;
    return 0;
}