Codeforces Round #340 (Div. 2)

A：https://codeforces.com/contest/617/problem/A

题意：

水题，一只大象一次能走1，2，3，4，5步，问你到达n最少需要几步，大象初始在0位置。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 100010;
int main()
{
    int x;
    scanf("%d",&x);
    int k = x%5;
    if(k){
        cout<<x/5+1<<endl;
    }else{
        cout<<x/5<<endl;
    }
    return 0;
}

B：https://codeforces.com/contest/617/problem/B

题意：

给出n个木棒，每个木棒只能是1或者是0，问你一共有多少种方法可以分割成每一组都是有且仅一根为1的木棒，输出分割的方法数

题解：

组合相乘，就是每俩个1间距相乘，注意也有全为0的样例，得输出0

代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 100010;
int a[110],b[110];
int main()
{
    int n,cnt = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i] == 1){
            b[++cnt] = i;
        }
    }
    if(cnt == 0){
        printf("0\n");
        return 0;
    }
    ll ans = 1;
    for(int i=2;i<=cnt;i++){
        ans *= 1ll*(b[i] - b[i-1]);
    }
    printf("%lld\n",ans);

    return 0;
}

C:https://codeforces.com/contest/617/problem/C

题意：

给出俩个点代表俩个喷泉，让你构造俩个喷泉的半径r1和r2，要求每一朵花都要被浇灌到，输出最小的r1^2+r2^2

题解：

将其中一维排序，然后另外一维直接取剩下的最大值就好了

代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    ll l1,l2;
};
node a[2010];
bool cmp(node p1,node p2){
    if(p1.l1 == p2.l1)
        return p1.l2 < p2.l2;
    return p1.l1 < p2.l1;
}

ll n,x1,x2,yy,y2;
ll x[2010],y[2010];
ll pre[2010];
int main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&x1,&yy,&x2,&y2);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        a[i].l1 = 1ll*abs((x1 - x[i])*(x1 - x[i]) + (yy - y[i])*(yy - y[i]));
        a[i].l2 = 1ll*abs((x2 - x[i])*(x2 - x[i]) + (y2 - y[i])*(y2 - y[i]));
    }

    sort(a+1,a+1+n,cmp);
    for(int i=n;i>=1;i--)
        pre[i] = max(pre[i+1],a[i].l2);
    ll ans = pre[1];
    for(int i=1;i<=n;i++)
        ans = min(ans,a[i].l1 + pre[i+1]);

    printf("%lld\n",ans);
    return 0;
}

D:https://codeforces.com/contest/617/problem/D

题意：

给你三个点，问你最少用多少条线段将这三个点连一起。

题解：

讨论多种情况
1.3个点共线，输出1
2.2个点共线，如果第三个点在共线俩个点的外部，输出2，否则输出3
3.无共线，输出2

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    int x,y;
}a[4];
bool cmp1(node p1,node p2){
    return p1.x < p2.x;
}
bool cmp2(node p1,node p2){
    return p1.y < p2.y;
}
int main()
{
    for(int i=1;i<=3;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    if((a[1].x == a[2].x && a[1].x == a[3].x) || (a[1].y == a[2].y && a[1].y == a[3].y)){
        cout<<"1"<<endl;
        return 0;
    }
    sort(a+1,a+1+3,cmp1);
    for(int i=2;i<=3;i++){
        if(a[i].x == a[i-1].x){
            int maxx = max(a[i].y , a[i-1].y);
            int minn = min(a[i].y , a[i-1].y);
            if(i == 2){
                if(a[3].y < maxx && a[3].y > minn){
                    cout<<"3"<<endl;
                    return 0;
                }
                cout<<"2"<<endl;
                return 0;
            }else{
                if(a[1].y < maxx && a[1].y > minn){
                    cout<<"3"<<endl;
                    return 0;
                }
                cout<<"2"<<endl;
                return 0;
            }
        }
    }
    sort(a+1,a+1+3,cmp2);
    for(int i=2;i<=3;i++){
        if(a[i].y == a[i-1].y){
            int maxx = max(a[i].x , a[i-1].x);
            int minn = min(a[i].x , a[i-1].x);
            if(i == 2){
                if(a[3].x < maxx && a[3].x > minn){
                    cout<<"3"<<endl;
                    return 0;
                }
                cout<<"2"<<endl;
                return 0;
            }else{
                if(a[1].x < maxx && a[1].x > minn){
                    cout<<"3"<<endl;
                    return 0;
                }
                cout<<"2"<<endl;
                return 0;
            }
        }
    }
    cout<<"3"<<endl;
    return 0;
}

E：https://codeforces.com/contest/617/problem/E

题意：

模板题，给出长度为n的数组，每次询问l到r区间上有多少[L,R]满足异或和 = k

：

莫队

代码:

#include <bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1e6*2 + 10;
int T,n,m,k;
int pos[maxn];  /// 每个数所在的块， 用来排序
ll ans[maxn];   /// 每个询问的答案
ll cnt[maxn];   /// 每个前缀和出现的次数
ll Ans;         /// 当前的答案
int L, R;       /// 当前区间
int a[maxn];    /// 前缀异或值
struct node {
    int l, r, id;
    node(int l=0, int r=0, int id=0):l(l), r(r), id(id) {}
    bool operator < (const node& rhs) const {
        if(pos[l] == pos[rhs.l]) return r < rhs.r;
        else return pos[l] < pos[rhs.l];
    }
}Q[maxn];
inline void add(int x) {
    Ans += cnt[a[x]^k];
    cnt[a[x]]++;
}
inline void del(int x) {
    cnt[a[x]]--;
    Ans -= cnt[a[x]^k];
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    int sz = sqrt(n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] ^= a[i-1];
        pos[i] = i / sz;
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &Q[i].l, &Q[i].r);
        Q[i].id = i;
    }
    sort(Q+1, Q+m+1);
    L = 1, R = 0, Ans = 0;
    cnt[0] = 1;
    for(int i = 1; i <= m; i++) {
        while(L < Q[i].l) {
            del(L-1);
            L++;
        }
        while(L > Q[i].l) {
            L--;
            add(L-1);
        }
        while(R < Q[i].r) {
            R++;
            add(R);
        }
        while(R > Q[i].r) {
            del(R);
            R--;
        }
        ans[Q[i].id] = Ans;
    }
    for(int i = 1; i <= m; i++) {
        printf("%I64d\n", ans[i]);
    }
    return 0;
}