codeforces Testing Round #12

A题意：问l,r之间多少个数整除k

思路：XJB判断（不要抱着想少几种判断还能过的心态疯狂交。。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 int main(){
 6     ll k,a,b;
 7     cin>>k>>a>>b;
 8     ll sum;
 9     if(k==1){
10         cout<<abs(b-a+1)<<endl;return 0;
11     }
12     if(a>0&&b>0){
13         sum=(b/k)-(a-1)/k;
14     }
15     else if(b>0&&a<0){
16         sum=b/k;
17         sum+=abs(a)/k;
18         sum++;
19     }
20     else {
21         sum=abs(a)/k-(abs(b)-1)/k;
22     }
23     if(b>0&&a==0){
24         sum=b/k+1;
25     }
26     else if(a<0&&b==0){
27            // cout<<a<<endl;
28         sum=abs(a)/k+1;
29     }
30     else if(a==0&&b==0) sum=1;
31 
32     cout<<sum<<endl;
33 }

B题意：问有多少个一点都不重合的区间

思路：贪心

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=500006;
 4 
 5 struct node{
 6     int l,r;
 7 }a[N];
 8 bool cmp(node p,node q){
 9     if(p.l==q.l) return p.r<q.r;
10     return p.l<q.l;
11 }
12 int main(){
13     int n;
14     cin>>n;
15 
16     for(int i=1;i<=n;i++){
17 
18         scanf("%d%d",&a[i].l,&a[i].r);
19     }
20     sort(a+1,a+1+n,cmp);
21     int rr=a[1].r;
22     int sum=0;
23     for(int i=2;i<=n;i++){
24 
25         if(a[i].l>rr){
26             sum++;
27             rr=a[i].r;
28 
29         }
30         else {
31             rr=min(rr,a[i].r);
32         }
33 
34     }
35     cout<<sum+1<<endl;
36 }

C题意：问有多少个长度为K的上升子序列

思路：dp[i][j]表示以i结尾的j长度子序列，那么他就+上前面比她小的dp[ii][j-1],树状数组维护下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e5+10;
 5 
 6 ll a[N],dp[N][20];
 7 ll b[N];
 8 int n,k;
 9 ll hh(int x,int y){
10     ll sum=0;
11     while(x){
12         sum+=dp[x][y];
13         x-=x&-x;
14     }
15     return sum;
16 }
17 void update(int x,int y,ll val){
18     while(x<=n){
19         dp[x][y]+=val;
20         x+=x&-x;
21     }
22 }
23 int  main(){
24     cin>>n>>k;
25     k++;
26     int x;
27     update(1,0,1);
28     for(int i=1;i<=n;i++){
29         scanf("%d",&x);
30         for(int j=k;j>=1;j--){
31             ll y=hh(x,j-1);
32             update(x,j,y);
33         }
34     }
35     cout<<hh(n,k)<<endl;
36 }