Codeforces Round #361 (Div. 2)

A

脑筋急转弯

 1 // #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 110<<2;
22 const int MOD = 1e9+7;
23 #define LL long long
24 #define mi() (l+r)>>1
25  double const pi = acos(-1);
26 
27 //void fre() {
28 //    freopen("in.txt","r",stdin);
29 //}
30 int vis[20];
31 int ans[5];
32 int main(){
33      int n;
34      string s;
35      cin>>n;
36      cin>>s;
37      clc(vis,0);
38      clc(ans,0);
39      for(int i=0;i<s.length();i++) vis[s[i]-'0']=true;
40      for(int i=0;i<=9;i++){
41          if(!vis[i]) continue;
42          if(i==1||i==2||i==3) ans[1]=1;
43          if(i==3||i==6||i==9||i==0) ans[2]=1;
44          if(i==9||i==0||i==7) ans[3]=1;
45          if(i==7||i==4||i==1||i==0) ans[4]=1;
46      }
47      printf("%s
",ans[1]&ans[2]&ans[3]&ans[4]?"YES":"NO");
48      return 0;
49 }
View Code

B - Mike and Shortcuts

从i到j的花费是fabs(j-i)

现在每个点有一条路ai，可以使得i走到ai的花费为1

现在问你从1走到i点的花费是多少

搜索i点前后两个点

 1 // #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 200010;
22 const int MOD = 1e9+7;
23 #define LL long long
24 #define mi() (l+r)>>1
25  double const pi = acos(-1);
26 
27 //void fre() {
28 //    freopen("in.txt","r",stdin);
29 //}
30 int a[N];
31 int ans[N];
32 int vis[N];
33 int n;
34 struct  Node{
35      int x,w;
36      Node(int a,int b):x(a),w(b){} 
37 };
38 void bfs(){
39      queue<Node>q;
40      q.push(Node(1,0));
41      while(!q.empty()){
42           Node f=q.front();
43           q.pop();
44           if(vis[f.x]) continue;
45            vis[f.x]=true;
46            ans[f.x]=f.w;
47           if(!vis[a[f.x]])
48             q.push(Node(a[f.x],f.w+1));
49           if(!vis[f.x+1]&&(f.x+1)<=n)
50             q.push(Node(f.x+1,f.w+1));
51           if(!vis[f.x-1]&&(f.x-1)>=0)
52             q.push(Node(f.x-1,f.w+1));
53      }
54 }
55 int main(){
56      // int n;
57      cin>>n;
58      for(int i=1;i<=n;i++)
59         scanf("%d",&a[i]);
60      bfs();
61      for(int i=1;i<=n;i++){
62         printf("%d%c",ans[i],i!=n?' ':'
' );
63      }
64      return 0;
65 }
View Code

 C - Mike and Chocolate Thieves

题意：

求一个数，恰好可以分成n个（a.ak.ak^2.ak^3）的形式。且符合条件最小的数。。看样列yy一下题意。。

思路：直接二分答案

 1 // #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 110<<2;
22 const int MOD = 1e9+7;
23 #define LL long long
24 #define mi() (l+r)>>1
25  double const pi = acos(-1);
26 
27 //void fre() {
28 //    freopen("in.txt","r",stdin);
29 //}
30 LL n;
31 LL cube(LL x){
32     return x*x*x;
33 }
34 LL fun(LL k){
35      LL sum=0;
36      for(int i=2;i<=1e6;i++){
37          if(cube(i)>k) break;
38          sum+=k/cube(i);
39      }
40      return sum;
41 }
42 int main(){
43      cin>>n;
44      LL l=0,r=1e18;
45      LL mid;
46      while(l<=r){
47          mid=(l+r)>>1;
48          if(fun(mid)>=n) r=mid-1;
49          else l=mid+1;
50      }
51      if(fun(r+1)==n) printf("%I64d
",r+1);
52      else printf("-1
");
53      return 0;
54 }
View Code

D - Friends and Subsequences

题意：a b两个数组，[l,r]上，a的最大值等于b的最小值，问有几个这样区间

思路：首先一看这种题肯定是二分来做。

枚举l，二分r。a数组中最大值肯定是非递减的，b最小值肯定是非递增的。所以二分r的时候，根据这个性质。

两次二分，二分r的极右端，极左端需要技巧。看代码。

求区间最大值可以用rmq，O(n*logn+1);

线段树查询时（logn），也可以。

  1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <sstream>
  6 #include <string>
  7 #include <algorithm>
  8 #include <list>
  9 #include <map>
 10 #include <vector>
 11 #include <queue>
 12 #include <stack>
 13 #include <cmath>
 14 #include <cstdlib>
 15 // #include <conio.h>
 16 using namespace std;
 17 #define clc(a,b) memset(a,b,sizeof(a))
 18 #define inf 0x3f3f3f3f
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N = 201000;
 22 const int MOD = 1e9+7;
 23 #define LL long long
 24 #define mi() (l+r)>>1
 25 double const pi = acos(-1);
 26 
 27 void fre() {
 28     freopen("in.txt","r",stdin);
 29 }
 30 
 31 // inline int r() {
 32 //     int x=0,f=1;char ch=getchar();
 33 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
 34 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
 35 // }
 36 
 37 int a[N],b[N];
 38 int maxa[N][50],minb[N][50];
 39 
 40 void init(int n){
 41     int i,j;
 42     for(i=0;i<n;i++){
 43         maxa[i][0]=a[i];
 44         minb[i][0]=b[i];
 45     }
 46     for(j=1;(1<<j)<=n;j++)
 47         for(i=0;i+(1<<j)-1<n;i++){
 48             maxa[i][j]=max(maxa[i][j-1],maxa[i+(1<<(j-1))][j-1]);
 49             minb[i][j]=min(minb[i][j-1],minb[i+(1<<(j-1))][j-1]);
 50         }
 51 }
 52 
 53 int rmq(int l,int r,int c)
 54 {
 55     int k=0;
 56     while((1<<(k+1))<=r-l+1) k++;
 57     if(c)
 58         return max(maxa[l][k],maxa[r-(1<<k)+1][k]);
 59     else
 60         return min(minb[l][k],minb[r-(1<<k)+1][k]);
 61 }
 62 
 63 int main() {
 64     // fre();
 65     int n;
 66     scanf("%d",&n);
 67     for(int i=0; i<n; i++)
 68         scanf("%d",&a[i]);
 69     for(int i=0; i<n; i++)
 70         scanf("%d",&b[i]);
 71     init(n);
 72     LL ans=0;
 73     for(int i=0; i<n; i++) {
 74         int l=i,r=n-1;
 75         int rmin,rmax;
 76         bool flag=0;
 77         while(l<=r) {
 78             int mid=(l+r)>>1;
 79             int ans_a=rmq(i,mid,1);
 80             int ans_b=rmq(i,mid,0);
 81             if(ans_a==ans_b){
 82                  flag=1;
 83             }
 84             if(ans_a>ans_b){
 85                  r=mid-1;
 86             }
 87             else 
 88                  l=mid+1;
 89         }
 90         if(!flag) continue;
 91         rmax=r;
 92         l=i;
 93         while(l<=r){
 94              int mid=(l+r)>>1;
 95              int ans_a=rmq(i,mid,1);
 96              int ans_b=rmq(i,mid,0);
 97              if(ans_a<ans_b)
 98                  l=mid+1;
 99              else
100                  r=mid-1;
101         }
102         rmin=l;
103         ans+=(LL)(rmax-rmin+1);
104     }
105     printf("%I64d
",ans);
106     return 0;
107 }
View Code

 E - Mike and Geometry Problem

题意：k个区间，求C(k,n)个区间的交集

思路：数据太大显然不能直接暴力。区间交集等价与每个点被覆盖了几次，最后答案就是每个点覆盖的次数C(nex,n)求和。

lucas超时，费马小。。。

统计每个点被覆盖的次数类似扫描线处理离线化树状数组

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 201000;
22 const int MOD = 1e9+7;
23 #define LL long long
24 #define mi() (l+r)>>1
25 double const pi = acos(-1);
26 
27 void fre() {
28     freopen("in.txt","r",stdin);
29 }
30 
31 // inline int r() {
32 //     int x=0,f=1;char ch=getchar();
33 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
34 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
35 // }
36 LL fac[N];
37 
38 LL qpow(LL a,LL b)
39 {
40     LL ans=1;a%=MOD;
41     for(LL i=b;i;i>>=1,a=a*a%MOD)
42         if(i&1) ans=ans*a%MOD;
43     return ans;
44 }
45 
46 LL Comb(LL n,LL m){
47     if(m>n||m<0) return 0;
48     LL s1=fac[n],s2=fac[n-m]*fac[m]%MOD;
49     return s1*qpow(s2,MOD-2)%MOD;
50 }
51  int main(){            
52     int k,n;
53     fac[0]=1;
54     fac[0]=1;
55     for(int i=1;i<N;i++)
56         fac[i]=fac[i-1]*i%MOD;
57     scanf("%d%d",&k,&n);
58     vector<pair<int,int> >p;
59     for(int i=0;i<k;i++){
60          LL r,l;
61          scanf("%I64d %I64d",&l,&r);
62          p.push_back(make_pair(l-1,1));
63          p.push_back(make_pair(r,-1));
64     }
65     sort(p.begin(),p.end());
66     LL ans=0;
67     int nex=0,last=0;
68     for(int i=0;i<(int)p.size();i++){
69         ans=(ans+Comb(nex,n)*(p[i].first-last))%MOD;
70         nex+=p[i].second;
71         last=p[i].first;
72     }
73     printf("%I64d
",ans);
74     return 0;
75  }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ITUPC/p/5655991.html