2019hdu第二场

￡神魔★判官ぃ 2023-10-11 09:16 14阅读 0赞

10：签到求n!取模

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <iterator>
    #include <algorithm>
    typedef long long ll;
    using namespace std;
    const ll mod=1e6+3;
    ll n;
    ll res[mod+3];
    int main(){
        res[0]=1%mod;
        res[1]=1%mod;
        for(int i=2;i<=mod+1;i++){
            res[i]=(res[i-1]*i)%mod; 
        } 
        while(scanf("%lld",&n)!=EOF){
            if(n>=mod) printf("0\n");
            else printf("%lld\n",res[n]);
        }
        return 0;
    }

11：签到，主席树维护a\[\]数组，然后对于每个q，去询问区间第1大，第2大，第3大，如果不能组成三角形，则询问区间第4大，依次类推，询问次数最多为O(logn)，总复杂度O(qlogn\*logn)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*
    主席树维护区间[l,r]
    查找第1大，第2大，第3大，第4大 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 100005
    #define ll long long 
    ll a[maxn],n,b[maxn];
    
    int tot,m,rt[maxn];
    struct Node{
         int lc,rc,sum;}t[maxn*25];
    int update(int last,int l,int r,int pos){
        int now=++tot;
        t[now]=t[last];t[now].sum++;
        if(l==r)return now;
        int mid=l+r>>1;
        if(pos<=mid)
            t[now].lc=update(t[last].lc,l,mid,pos);
        else t[now].rc=update(t[last].rc,mid+1,r,pos);
        return now;
    }
    int query(int st,int ed,int l,int r,int k){
        if(l==r)return l;
        int mid=l+r>>1;
        int sum=t[t[ed].lc].sum-t[t[st].lc].sum;
        if(k<=sum)return query(t[st].lc,t[ed].lc,l,mid,k);
        else return query(t[st].rc,t[ed].rc,mid+1,r,k-sum);
    }
    int build(int l,int r){
        int now=++tot;
        t[now].lc=t[now].rc=t[now].sum=0;
        if(l==r)return now;
        int mid=l+r>>1;
        t[now].lc=build(l,mid);
        t[now].rc=build(mid+1,r);
        return now;
    }
    
    int main(){
        int q;
        while(scanf("%d%d",&n,&q)==2){
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
                b[i]=a[i];
            }
            sort(b+1,b+1+n);
            m=unique(b+1,b+1+n)-(b+1);
    //cout<<m<<endl;
            for(int i=1;i<=n;i++)
                a[i]=lower_bound(b+1,b+1+m,a[i])-b;
            
            tot=0;
            rt[0]=build(1,m);
            for(int i=1;i<=n;i++)
                rt[i]=update(rt[i-1],1,m,a[i]);
            int l,r;
            while(q--){
                scanf("%d%d",&l,&r);
                if(r-l+1<3){puts("-1");continue;}
                int len=r-l+1;
                ll x=b[query(rt[l-1],rt[r],1,m,len)],y=b[query(rt[l-1],rt[r],1,m,len-1)],z=b[query(rt[l-1],rt[r],1,m,len-2)];
                len-=3;
                while(x>=y+z){
                    if(len==0)break;
                    x=y,y=z;z=b[query(rt[l-1],rt[r],1,m,len)];
                    len--;
                }
                if(x>=y+z)puts("-1");
                else cout<<x+y+z<<'\n';
            }
                
        }    
    }

12：队友过的规律题，从\[1,n\]里随机选一个数丢进函数里，问最后答案的期望值

实质是一个概率dp，可以通过n^2的转移来做，当然也可以直接找规律推出线性通项公式做

这是比较好的题解（比官方题解容易懂）[https://www.cnblogs.com/isakovsky/p/11247444.html][https_www.cnblogs.com_isakovsky_p_11247444.html]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cctype>
    #include <string>
    #include <vector>
    #include <map>
    #include <set>
    #include <vector>
    #include <queue>
    #include <stack>
    const int MOD = 998244353;
    #define rep(i,n,m) for(int i=n;i<=m;++i)
    const double eps = 1e-16;
    #define ll long long
    using namespace std;
    const int maxn = 10000000;
    const int maxm = 2e5 + 10;
    const int inf = 1 << 28;
    typedef pair<int, int> P;
    #define zero(a) fabs(a)<eps
    inline int read()
    {
        int x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = 10 * x + ch - '0';
            ch = getchar();
        }
        return x * f;
    }
    
    
    ll quick_mod(ll x, ll n) {
        ll res = 1;
        while (n) {
            if (n & 1) res = res * x % MOD;
            x = x * x % MOD;
            n = n >> 1;
        }
        return res;
    }
    ll a[3005];
    void init()
    {
        a[0] = a[1] = 0;
        a[2] = 2;
        for (int i = 3; i <= 3000; ++i)
            a[i] = a[i - 1] + (i - 1) * 2;
        for (int i = 1; i <= 3000; ++i)
            a[i] += a[i - 1];
    }
    int main()
    {
        ll n;
        init();
        while (~scanf("%lld", &n))
        {
            if (n == 1) { cout << "0" << endl; continue; }
            ll a1 = a[n];
            ll b = 3 * n;
            ll x = quick_mod(b, MOD - 2);
            cout << a1 % MOD * x % MOD<<endl;
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11366024.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[https_www.cnblogs.com_isakovsky_p_11247444.html]: https://www.cnblogs.com/isakovsky/p/11247444.html