# A -- simple math problem

Time Limit：2s Memory Limit：128MByte

Submissions：1599Solved：270

SAMPLE INPUT

5

20

1314

SAMPLE OUTPUT

5

21

1317

SOLUTION

“玲珑杯”ACM比赛 Round #19

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 typedef long long ll;
7 const int mo=1e9+7;
8 int pow(int a,int b,int c){int ret=1;for(;b;b>>=1,a=1LL*a*a%c)if(b&1)ret=1LL*ret*a%c;return ret;}
9
10 int p[10], q[10];
11
12 int work(int n){
13     int t = 0;
14     for(int i = 0;i <= 9;i ++) if(n >= q[i]) t = i;
15     return n + t;
16 }
17
18 int gr(){
19     return (rand() << 16) + rand();
20 }
21
22 int main(){
23     p[0] = 1;
24     int t = 1;
25     for(int i = 1;i <= 9;i ++) p[i] = p[i - 1] * 10, q[i] = p[i] + 2 - i;
26     int n;
27     while(scanf("%d", &n) != EOF) printf("%d\n", work(n));
28     return 0;
29 }```

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int n;
4 int main()
5 {
6     while(cin>>n)
7     {
8         if(n>=0&&n<=10)
9             cout<<n<<endl;
10         else
11         {
12             int ans=0,t=0;
13             int m=n;
14             while(m)
15             {
16                 m/=10;
17                 t++;
18             }
19             if((n+t-1)>pow(10,t))
20                 cout<<n+t<<endl;
21             else
22                 cout<<n+t-1<<endl;
23         }
24     }
25     return 0;
26 }```

# B -- Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：682Solved：178

``` 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 using namespace std;
6
7 #define N 200010
8
9 int n, K, a[N], lg[N], f[20][N], g[20][N];
10
11 int ask(int l, int r){
12     int k = lg[r - l + 1];
13     return max(f[k][l], f[k][r - (1 << k) + 1]) - min(g[k][l], g[k][r - (1 << k) + 1]);
14 }
15
16 int main(){
17 //    freopen("1.in", "r", stdin);
18     scanf("%d%d", &n, &K);
19     for(int i = 2;i <= n;i ++) if(i & (i - 1)) lg[i] = lg[i - 1]; else lg[i] = lg[i - 1] + 1;
20     for(int i = 1;i <= n;i ++) scanf("%d", &a[i]), f[0][i] = g[0][i] = a[i];
21     for(int i = 1;(1 << i) <= n;i ++){
22         for(int j = 1;j + (1 << i) - 1 <= n;j ++){
23             f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
24             g[i][j] = min(g[i - 1][j], g[i - 1][j + (1 << (i - 1))]);
25         }
26     }
27     long long ans = 0;
28     for(int i = 1;i <= n;i ++){
29         int l = i, r = n, mid;
30         while(l <= r){
31             mid = (l + r) >> 1;
32             if(ask(i, mid) <= K) l = mid + 1; else r = mid - 1;
33         }
34         ans += l - i;
35     }
36     cout << ans << endl;
37     return 0;
38 }```

# C -- Collecting apples

Time Limit：2s Memory Limit：128MByte

Submissions：24Solved：7

```  1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 using namespace std;
6
7 typedef int value_t;
8 typedef long long calc_t;
9 const int MaxN = 1 << 19;
10 const value_t mod_base = 119, mod_exp = 23;
11 const value_t mod_v = (mod_base << mod_exp) + 1;
12 const value_t primitive_root = 3;
13 int epsilon_num;
14 value_t eps[MaxN], inv_eps[MaxN], inv2, inv[MaxN];
15
16 value_t dec(value_t x, value_t v) { x -= v; return x < 0 ? x + mod_v : x; }
17 value_t inc(value_t x, value_t v) { x += v; return x >= mod_v ? x - mod_v : x; }
18 value_t pow(value_t x, value_t p){
19     value_t v = 1;
20     for(; p; p >>= 1, x = (calc_t)x * x % mod_v)
21         if(p & 1) v = (calc_t)x * v % mod_v;
22     return v;
23 }
24
25 void init_eps(int num){
26     epsilon_num = num;
27     value_t base = pow(primitive_root, (mod_v - 1) / num);
28     value_t inv_base = pow(base, mod_v - 2);
29     eps[0] = inv_eps[0] = inv[0] = 1;
30     for(int i = 1; i < num; ++i)
31         inv[i] = pow(i, mod_v - 2);
32     for(int i = 1; i < num; ++i){
33         eps[i] = (calc_t)eps[i - 1] * base % mod_v;
34         inv_eps[i] = (calc_t)inv_eps[i - 1] * inv_base % mod_v;
35     }
36 }
37
38 void transform(int n, value_t *x, value_t *w = eps){
39     for(int i = 0, j = 0; i != n; ++i){
40         if(i > j) swap(x[i], x[j]);
41         for(int l = n >> 1; (j ^= l) < l; l >>= 1);
42     }
43     for(int i = 2; i <= n; i <<= 1){
44         int m = i >> 1, t = epsilon_num / i;
45         for(int j = 0; j < n; j += i){
46             for(int p = 0, q = 0; p != m; ++p, q += t){
47                 value_t z = (calc_t)x[j + m + p] * w[q] % mod_v;
48                 x[j + m + p] = dec(x[j + p], z);
49                 x[j + p] = inc(x[j + p], z);
50             }
51         }
52     }
53 }
54
55 void inverse_transform(int n, value_t *x){
56     transform(n, x, inv_eps);
57     value_t inv = pow(n, mod_v - 2);
58     for(int i = 0; i != n; ++i)
59         x[i] = (calc_t)x[i] * inv % mod_v;
60 }
61
62 void polynomial_inverse(int n, value_t *A, value_t *B){
63     static value_t T[MaxN];
64     if(n == 1){
65         B[0] = pow(A[0], mod_v - 2);
66         return;
67     }
68     int half = (n + 1) >> 1;
69     polynomial_inverse(half, A, B);
70     int p = 1;
71     for(; p < n << 1; p <<= 1);
72     fill(B + half, B + p, 0);
73     transform(p, B);
74     copy(A, A + n, T);
75     fill(T + n, T + p, 0);
76     transform(p, T);
77     for(int i = 0; i != p; ++i)
78         B[i] = (calc_t)B[i] * dec(2, (calc_t)T[i] * B[i] % mod_v) % mod_v;
79     inverse_transform(p, B);
80 }
81
82 void polynomial_logarithm(int n, value_t *A, value_t *B){
83     static value_t T[MaxN];
84     int p = 1;
85     for(; p < n << 1; p <<= 1);
86     polynomial_inverse(n, A, T);
87     fill(T + n, T + p, 0);
88     transform(p, T);
89     copy(A, A + n, B);
90     for(int i = 0; i < n - 1; ++i)
91         B[i] = (calc_t)B[i + 1] * (i + 1) % mod_v;
92     fill(B + n - 1, B + p, 0);
93     transform(p, B);
94     for(int i = 0; i != p; ++i)
95         B[i] = (calc_t)B[i] * T[i] % mod_v;
96     inverse_transform(p, B);
97     for(int i = n - 1; i; --i)
98         B[i] = (calc_t)B[i - 1] * inv[i] % mod_v;
99     B[0] = 0;
100 }
101
102 void polynomial_exponent(int n, value_t *A, value_t *B)
103 {
104     static value_t T[MaxN];
105     if(n == 1){
106         B[0] = 1;
107         return;
108     }
109     int p = 1;
110     for(; p < n << 1; p <<= 1);
111     int half = (n + 1) >> 1;
112     polynomial_exponent(half, A, B);
113     fill(B + half, B + p, 0);
114     polynomial_logarithm(n, B, T);
115     for(int i = 0; i != n; ++i)
116         T[i] = dec(A[i], T[i]);
117     T[0] = inc(T[0], 1);
118     transform(p, T);
119     transform(p, B);
120     for(int i = 0; i != p; ++i)
121         B[i] = (calc_t)B[i] * T[i] % mod_v;
122     inverse_transform(p, B);
123 }
124
125 value_t tmp[MaxN];
126 value_t A[MaxN], B[MaxN], C[MaxN], T[MaxN];
127
128 int main(){
129 //    freopen("1.in", "r", stdin);
130 //    freopen("1.out", "w", stdout);
131     int n, m, nn, xx, yy;
132     scanf("%d%d", &nn, &n);
133     for(int i = 1;i <= n;i ++) tmp[i] = 0;
134     for(int i = 1;i <= nn;i ++) scanf("%d%d", &xx, &yy), tmp[yy] += xx;
135     inv2 = mod_v - mod_v / 2;
136     int p = 1;
137     for(; p < (n + 5) << 1; p <<= 1);
138     init_eps(p);
139     for(int j = 1;j <= n;j ++){
140         for(int i = 1;i * j <= n;i ++)
141             if(j & 1) A[i * j] = (A[i * j] + 1LL * inv[j] * tmp[i]) % mod_v;
142             else A[i * j] = ((A[i * j] - 1LL * inv[j] * tmp[i]) % mod_v + mod_v) % mod_v;
143     }
144     polynomial_exponent(n + 5, A, B);
145     for(int i = 1; i <= n;i ++) printf("%d\n", (B[i] + mod_v) % mod_v);
146     return 0;
147 }```

# D -- Delivering parcels

Time Limit：2s Memory Limit：128MByte

Submissions：114Solved：16

``` 1 #include <iostream>
2 #include <stdio.h>
3 #include <math.h>
4 #include <string.h>
5 #include <time.h>
6 #include <stdlib.h>
7 #include <string>
8 #include <bitset>
9 #include <vector>
10 #include <set>
11 #include <map>
12 #include <queue>
13 #include <algorithm>
14 #include <sstream>
15 #include <stack>
16 #include <iomanip>
17 using namespace std;
18 #define pb push_back
19 #define mp make_pair
20 typedef pair<int,int> pii;
21 typedef long long ll;
22 typedef double ld;
23 typedef vector<int> vi;
24 #define fi first
25 #define se second
26 #define fe first
27 #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
28 #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
29 #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
30 #define es(x,e) (int e=fst[x];e;e=nxt[e])
31 #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
32 #define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
33 #define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}
34 #define SZ 666666
35 int n,w[SZ],v[SZ];
36 ll ans=1e18;
37 pii ps[SZ];
38 int hm[SZ];
39 #include <ext/pb_ds/tree_policy.hpp>
40 #include <ext/pb_ds/assoc_container.hpp>
41 using namespace __gnu_pbds;
42 typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtt;
43 rbtt rbt;
44 void case1(int A,int B)
45 {
46     rbt.clear();
47     int r=n-1,g=0;
48     for(int i=1;i<=n+n;++i)
49         if(i!=A&&i!=B) ps[++g]=pii(w[i],v[i]);
50     sort(ps+1,ps+1+g); hm[g+1]=-1e9;
51     for(int i=g;i>=1;--i)
52         hm[i]=max(hm[i+1],ps[i].se);
53     for(int i=1;i<=g;++i)
54     {
55         rbt.insert(ps[i].se);
56         if(g-i>r) continue;
57         int cur=hm[i+1],rm=r-(g-i);
58         if(rm) cur=max(cur,*rbt.find_by_order(rm-1));
59         ans=min(ans,(ll)max(w[B],ps[i].fi)*v[B]+(ll)w[A]*max(cur,v[A]));
60     }
61 }
62 void case2(int A,int B)
63 {
64     rbt.clear();
65     int g=0;
66     for(int i=1;i<=n+n;++i)
67         if(i!=A&&i!=B) ps[++g]=pii(w[i],v[i]);
68     sort(ps+1,ps+1+g);
69     int pp=0,p2=0;
70     for(int i=1;i<=g;++i)
71     {
72         rbt.insert(ps[i].se);
73         if(rbt.size()<n) continue;
74         int cur=*rbt.find_by_order(n-1);
75         ans=min(ans,(ll)w[A]*v[B]+(ll)ps[i].fi*cur);
76     }
77 }
78 int main()
79 {
80     scanf("%d",&n);
81     for(int i=1;i<=n+n;++i)
82         scanf("%d",w+i);
83     for(int i=1;i<=n+n;++i)
84         scanf("%d",v+i);
85     if(n==1)
86     {
87         printf("%lld\n",w[1]*(ll)v[1]+w[2]*(ll)v[2]);
88         return 0;
89     }
90     pii m1(-1e9,-1e9),m2(-1e9,-1e9);
91     for(int i=1;i<=n+n;++i)
92         m1=max(m1,pii(w[i],i)),
93         m2=max(m2,pii(v[i],i));
94     int A=m1.se,B=m2.se;
95     if(A!=B) case1(A,B);
96     case2(A,B);
97     printf("%lld\n",ans);
98 }```

# E -- Expected value of the expression

Time Limit：2s Memory Limit：128MByte

Submissions：119Solved：56

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 char op[1005][3];
8 double f[2][1005], p[1005];
9 int a[1005];
10 int n;
11
12 int main(){
13     scanf("%d", &n);
14     n ++;
15     for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
16     for(int i = 2;i <= n;i ++) scanf("%s", op[i]);
17     for(int i = 2;i <= n;i ++) scanf("%lf", &p[i]);
18     double ans = 0;
19     for(int j = 0;j < 20;j ++){
20         for(int i = 1;i <= n;i ++){
21             int v = (a[i] >> j) & 1;
22             f[0][i] = f[1][i] = 0.0;
23             if(i == 1){
24                 f[v][1] = 1;
25                 f[v ^ 1][1] = 0;
26             }else{
27                 if(op[i][0] == '&'){
28                     f[0][i] += f[0][i - 1] * p[i];
29                     f[1][i] += f[1][i - 1] * p[i];
30                     f[0 & v][i] += f[0][i - 1] * (1 - p[i]);
31                     f[1 & v][i] += f[1][i - 1] * (1 - p[i]);
32                 }
33                 if(op[i][0] == '|'){
34                     f[0][i] += f[0][i - 1] * p[i];
35                     f[1][i] += f[1][i - 1] * p[i];
36                     f[0 | v][i] += f[0][i - 1] * (1 - p[i]);
37                     f[1 | v][i] += f[1][i - 1] * (1 - p[i]);
38                 }
39                 if(op[i][0] == '^'){
40                     f[0][i] += f[0][i - 1] * p[i];
41                     f[1][i] += f[1][i - 1] * p[i];
42                     f[0 ^ v][i] += f[0][i - 1] * (1 - p[i]);
43                     f[1 ^ v][i] += f[1][i - 1] * (1 - p[i]);
44                 }
45             }
46         }
47         ans += f[1][n] * (double)(1 << j);
48     }
49     printf("%.6lf\n", ans);
50     return 0;
51 }```

0 条评论

• ### 回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则，并且当前这个目录下的文章数量为0(都是因为我懒QAQ)，作为开局第一篇文章，为初学者的入门文章，自然要把该说明的东西说明清楚，于是。。...

• ### 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元，D,模拟，E,前缀和，F,LCS，H,Prim算法，I,胡搞，J,树状数组)

A-------------------------------------------------------------------------------...

• ### 零基础学贪心算法

本文在写作过程中参考了大量资料，不能一一列举，还请见谅。 贪心算法的定义： 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上...

• ### 二分图最大匹配

二分图也叫二部图，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不...

• ### 2017 清北学堂 Day 6终极考试报告

预计分数： 100+70+70 = 240 实际假分数 ： 40+80+70= 190  in cena（好吧不得不承认这个分数，，，，，，=.=） 实际真分数...

• ### HDOJ(HDU) 2502 月之数(进制)

Problem Description 当寒月还在读大一的时候，他在一本武林秘籍中（据后来考证，估计是计算机基础，狂汗-ing），发现了神奇的二进制数。 ...

• ### P3717 [AHOI2017初中组]cover

题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器，每个探测器有个探测半径r，问这n*n个点中有多少个点能被探测到。 输入输出...

• ### HDU 1875 畅通工程再续(kruskal)

畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

• ### 天梯赛题库

L1-009 N个数求和 (20分) 思路：分母相乘，分子先相乘在相加，然后约分。

• ### HPU personal-training 2

A - Kefa and Park 题意：就是一棵树，然后本人的家在根上，餐厅在叶子节点上。然后在前往叶子结点的餐厅的时候，途中的结点上有猫，而这个人特别怕...