程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 480B Long Jumps 規律題

Codeforces 480B Long Jumps 規律題

編輯：C++入門知識

Codeforces 480B Long Jumps 規律題

題目鏈接：點擊打開鏈接

題意：

輸出n l x y

有一根直尺長度為l

上面有n個刻度。

下面n個數字是距離開頭的長度（保證第一個數字是0，最後一個數字是l）

要使得直尺中存在某2個刻度的距離為x ，某2個刻度的距離為y

要添加最少幾個刻度。

問：

最少的刻度個數

輸出標記的位置。

思路：

分類討論一下。。

若本身尺子裡就有x、y就輸出0

若只有x 或只有y就輸出一個刻度。

若2個都沒有就：

1、加1個刻度ans，這個ans是距離某個刻度距離為x的，然後看一下是否有距離ans為y的刻度，若有則添加一個ans即可。

2、第1個都非法時就直接加2個刻度。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template 
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
const int N = 200050;

vectorG;
bool Find(ll x){
    for(int i = G.size()-2; i > 0; i--)
    {
        if(G[i] - x < 0)return false;
        if( G[lower_bound(G.begin(), G.end(), G[i] - x) - G.begin()] == G[i] - x)
            return true;
    }
    return false;
}
ll n, l, x, y;
ll go(){
    ll ans;
    for(int i = G.size()-2; i > 0; i--){
        ans = G[i]-x;
        if(ans >= 0 && ((ans+y<=l&&G[lower_bound(G.begin(), G.end(), ans+y) - G.begin()] == ans+y) || (ans-y>=0&&G[lower_bound(G.begin(), G.end(), ans-y) - G.begin()] == ans-y)))
            return ans;
        ans = G[i]+x;
        if(ans <= l && ((ans + y <= l && G[lower_bound(G.begin(), G.end(), ans+y) - G.begin()] == ans+y) || (ans-y>=0&&G[lower_bound(G.begin(), G.end(), ans-y) - G.begin()] == ans-y)))
             return ans;
    }
    return -1;
}
void input(){
    G.clear();
    G.push_back(-5000000001LL);
    ll tmp;
    while(n--){
        rd(tmp);
        G.push_back(tmp);
    }
    G.push_back(1e10);
}

int main() {
    while(cin>>n>>l>>x>>y){
        input();
        int havx = Find(x), havy = Find(y);
        if(havx + havy == 2)
            puts("0");
        else if(havx + havy == 1)
        {
            if(havx)
                printf("1\n%I64d\n", y);
            else
                printf("1\n%I64d\n", x);
        }
        else {
            ll ans = go();
            if(ans == -1)
            {
                printf("2\n%I64d %I64d\n", x, y);
            }
            else
                printf("1\n%I64d\n", ans);
        }
    }
    return 0;
}