Testing Round #12

傷城~ 2022-08-10 06:18 45阅读 0赞

[A. Divisibility][]  
直接分类讨论

#include<bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        long long a,b,c;
        cin>>c>>a>>b;
        long long ans = 0;
        if(a<=0 && b<=0)
        {
            swap(a,b);
            a=-a,b=-b;
        }
        if(a<=0 && b>=0)
        {
            ans=(-a)/c+b/c;
            ans++;
        }
        else
        {
            ans=(b/c)-(a-1)/c;
        }
        cout<<ans<<endl;
        return 0;
    }

[B. Restaurant][]  
按照右坐标排序，直接贪心

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN=500005;
    
    struct Node
    {
        int l,r;
    };
    bool cmp(Node a,Node b)
    {
        if(a.r==b.r)return a.l<b.l;
        return a.r<b.r;
    }
    Node p[MAXN];
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d%d",&p[i].l,&p[i].r);
        sort(p,p+n,cmp);
        int ans = 0;
        int last = -1;
        for(int i=0; i<n; i++)
        {
            if(p[i].l>last)
            {
                ans++;
                last = p[i].r;
            }
        }
        printf("%d\n",ans);
        return 0;
    }

[C. Subsequences][]  
dp\[i\]\[j\]表示坐标为i，长度为j的上升子序列的个数  
然后我们转移就用前面小于a\[i\]的dp\[k\]\[j-1\]的和转移过来就好了  
用树状数组维护  
今年多校训练、网赛、区域赛似乎都出现过类似的题目

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN=100105;
    long long dp[MAXN][12];
    
    void add(int x,int y,long long val)
    {
        for(int i=x; i<MAXN; i+=i&(-i))
            dp[i][y]+=val;
    }
    
    long long sum(int x,int y)
    {
        long long ans = 0;
        for(int i=x; i>0; i-=i&(-i))
            ans+=dp[i][y];
        return ans;
    }
    
    int main()
    {
        int n,k;
        scanf("%d%d",&n,&k);
        add(1,0,1);
        for(int i=0; i<n; i++)
        {
            int x;
            scanf("%d",&x);
            x++;
            for(int j=k+1; j>0; j--)
            {
                long long temp = sum(x,j-1);
                add(x,j,temp);
            }
        }
        long long ans = sum(n+1,k+1);
        printf("%lld\n",ans);
        return 0;
    }

[A. Divisibility]: http://codeforces.com/contest/597/problem/A
[B. Restaurant]: http://codeforces.com/problemset/problem/597/B
[C. Subsequences]: http://codeforces.com/problemset/problem/597/C