首页 > 代码库 > Testing Round #12 A,B,C 讨论,贪心,树状数组优化dp

Testing Round #12 A,B,C 讨论,贪心,树状数组优化dp

题目链接:http://codeforces.com/contest/597

A. Divisibility
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of k-divisible numbers on the segment [a, b]. In other words you need to find the number of such integer values x that a ≤ x ≤ b and x is divisible by k.

Input

The only line contains three space-separated integers ka and b (1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).

Output

Print the required number.

Examples
input
1 1 10
output
10
input
2 -4 4
output
5

 

题意:找出[a,b]区间内整除k的数的个数;

思路:小心点特判即可;

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e5+10,M=4e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;///   数组大小int main(){    ll k,a,b;    scanf("%lld%lld%lld",&k,&a,&b);    if(a<=0&&b>=0)        printf("%lld\n",(b/k)-(a/k)+1);    else if(a>=0&&b>=0)        printf("%lld\n",(b/k)-(a/k+(a%k?1:0))+1);    else        printf("%lld\n",(abs(a)/k)-(abs(b)/k+(abs(b)%k?1:0))+1);    return 0;}

 

B. Restaurant
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li ≤ ri).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can‘t share even a moment of time. If one order ends in the moment other starts, they can‘t be accepted both.

Input

The first line contains integer number n (1 ≤ n ≤ 5·105) — number of orders. The following n lines contain integer values li and ri each (1 ≤ li ≤ ri ≤ 109).

Output

Print the maximal number of orders that can be accepted.

Examples
input
2
7 11
4 7
output
1
input
5
1 2
2 3
3 4
4 5
5 6
output
3
input
6
4 8
1 5
4 7
2 5
1 3
6 8
output
2

 

 

贪心:按r从小到大排序即可;

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=5e5+10,M=4e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;struct is{    int l,r;    bool operator <(const is &c)const    {        return r<c.r;    }}a[N];///   数组大小int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d%d",&a[i].l,&a[i].r);    sort(a+1,a+1+n);    int s=0,ans=0;    for(int i=1;i<=n;i++)    {        if(a[i].l>s)        {            ans++;            s=a[i].r;        }    }    printf("%d\n",ans);    return 0;}

 

C. Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Examples
input
5 2
1
2
3
5
4
output
7

题意:给你n个数,最长上升子序列长度为k+1的个数;

思路:看下数据范围k<10很关键,dp[i][j]表示以i为结束长度为j时候的方案数

   现在你到i的时候你只需要再T[j](树状数组)的a[i]的位置表示方案数;

   统计小于a[i]的方案,k==0时候特判;

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x)  cout<<"bug"<<x<<endl;const int N=1e5+10,M=4e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;struct AYT{    ll tree[N];    int lowbit(int x)    {        return x&-x;    }    void update(int x,ll c)    {        while(x<N)        {            tree[x]+=c;            x+=lowbit(x);        }    }    ll query(int x)    {        ll ans=0;        while(x)        {            ans+=tree[x];            x-=lowbit(x);        }        return ans;    }};AYT T[12];///   数组大小int a[N];int main(){    int n,k;    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    if(k==0)        return 0*printf("%d\n",n);    ll ans=0;    for(int i=1;i<=n;i++)    {        ans+=T[k].query(a[i]-1);        for(int j=k;j>=2;j--)        {            ll x=T[j-1].query(a[i]-1);            T[j].update(a[i],x);        }        T[1].update(a[i],1);    }    printf("%lld\n",ans);    return 0;}

 

 

 

A. Divisibility
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of k-divisible numbers on the segment [a, b]. In other words you need to find the number of such integer values x that a ≤ x ≤ b and x is divisible by k.

Input

The only line contains three space-separated integers ka and b (1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).

Output

Print the required number.

Examples
input
1 1 10
output
10
input
2 -4 4
output
5

 

Testing Round #12 A,B,C 讨论,贪心,树状数组优化dp