A:https://ac.nowcoder.com/acm/contest/1085/A

题意：

题目本意是用若干个区间覆盖长度为n的数轴，最后问没有覆盖到的区间最大长度

题解：

排序，从左到右维护最大值

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 100005;
struct node{
    int l,r;
    bool operator <(const node& y)const
    {
        if(l == y.l)
            return r < y.r;
        return l < y.l;
    }
}a[maxx];
int main()
{
    int n,m,ans = 0;
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&a[i].l,&a[i].r);
    }
    a[++n].l = 0,a[n].r = 0;
    a[++n].l = m+1,a[n].r = m+1;
    sort(a+1,a+1+n);
    for(int i=2,j=1;i<=n;i++)
    {
        if(a[i].l <= a[j].r)
            a[j].r = max(a[j].r,a[i].r);
        else{
            ans = max(ans,a[i].l - a[j].r -1);
            j = i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

C：https://ac.nowcoder.com/acm/contest/1085/C

题意：

给你一个数列，输出这个数列中，出现次数为奇数个的数字的异或和

题解：

真是自己sb了，直接从头到尾异或，因为出现次数为偶数的直接异或为0

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 1010;
ll x;
int main()
{
    int n,cnt = 0;
    scanf("%d",&n);
    ll ans = 0 ;
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        ans ^= x;
    }
    printf("%lld\n",ans);
    return 0;
}

F：https://ac.nowcoder.com/acm/contest/1085/F

题意：

数学求缺球的高

题解：

直接套公式，注意精度问题
V = pai(h*h(r - h/3)；h是缺球的高，r是球的半径，V是缺球的面积，pai是3.1415926

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
double R,v,h = 0,pai = 3.1415926;
double esp = 0.0001;
int main()
{
    cin>>R>>v;
    double l = 0, r = 2*R , h , ans;
    while(r - l >= esp)
    {
        h = (l + r)/2;
        ans = pai*h*h*(R - h/3);
        if(ans - v > esp){
            r = r - esp;
        }
        else{
            l = l + esp;
        }
    }
    printf("%.2lf\n",2*R - h);
    return 0;
}

G：https://ac.nowcoder.com/acm/contest/1085/G

题意：

给出序列，每次输出[l,r]区间上的 ai*sum(ai) 的和 ，sum(ai)代表ai在区间[l,r]上区间的次数

题解：

莫队（不会，先放下，记得补）

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 100010;
const int blo = 310;
struct node{
    int l,r,id;
    bool operator < (node x)const
    {
        return l/blo == x.l/blo ? r < x.r : l < x.l;
    }
};
node b[maxx];
ll ans1[maxx];
int n,m,a[maxx],cnt[maxx];
ll ans = 0;
void add(int x,int v)
{
    ans -= 1ll*(cnt[x]*cnt[x]*x);
    cnt[x] += v;
    ans += 1ll*(cnt[x]*cnt[x]*x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&b[i].l,&b[i].r);
        b[i].id = i;
    }
    sort(b+1,b+1+m);
    int l = 1,r = 1;
    add(a[1],1);
    for(int i=1;i<=m;i++){
        int L = b[i].l , R = b[i].r;
        while(L < l) add(a[--l],1);
        while(r < R) add(a[++r],1);
        while(l < L) add(a[l++],-1);
        while(r > R) add(a[r--],-1);
        ans1[b[i].id] = ans;
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans1[i]);
    }
    return 0;
}

J：https://ac.nowcoder.com/acm/contest/1085/J

题意：

有一个含有n个数字的序列，每个数的大小是不超过1000的正整数，同时这个序列是个单调不增序列。但是很不幸的是，序列在保存过程中有些数字丢失了，计算出有多少种不同的序列满足上述条件，答案对1e9+7取模。

题解：

设dp[i][j]代表长度为i，最后一位为j的非递增序列的个数；
则推导出来 dp[i][j] = C(i+j-1,i);
如果遇到5 0 0 0 2 就是dp[4][5-2+1]
这里打表2000的C(x,y)要学习一下。
##代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1000005;
ll k1[maxn],k2[maxn],a[maxn];
ll pow_mod(ll a,ll b,ll mod){
    ll ans = 1;
    while(b){
        if(b&1)
           ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
const ll mod = 1e9+7;
void init(){
    k1[0] = 1,k2[0] = 1;
    for(int i=1;i<=maxn;i++){
        k1[i] = (k1[i-1]*i)%mod;
        k2[i] = pow_mod(k1[i],mod-2,mod);
    }
}
ll C(ll x,ll y){
    if(y == 0)
        return 1;
    return ((k1[x]%mod*k2[y]%mod)%mod*k2[x-y]%mod)%mod;
}
int main()
{
    int n,cnt = 0,pre = 1000;
    ll ans = 1;
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    a[n+1] = 1;
    for(int i=1;i<=n+1;i++){
        if(a[i]){
            int k = pre - a[i] + 1;
            ans *= C(k+cnt-1,cnt);
            ans %= mod;
            pre = a[i];
            cnt = 0;
        }else{
            cnt++;
        }
    }
    printf("%lld\n",ans);

    return 0;
}