尽快将前面的练习补上！
每日一练
2.1
Problem A Laurenty and Shop
题意：选择不同的两条路线使得总等待时间最小。
简析：路线不同在于过马路的地方不同。
预处理前缀和，可以O(1)得到走每条路时间，挑选最小的两个即可。
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int a[2][50], b[50];
5 const int INF = 1e9;
6
7 int main(void)
8 {
9 int n;
10 scanf("%d", &n);
11 for(int i = 1; i < n; i++) scanf("%d", &a[0][i]), a[0][i] += a[0][i-1];
12 for(int i = 1; i < n; i++) scanf("%d", &a[1][i]), a[1][i] += a[1][i-1];
13 for(int i = 0; i < n; i++) scanf("%d", b + i);
14 int A = INF, B = INF;
15 for(int i = 0; i < n; i++)
16 {
17 int pos = a[0][i] + b[i] + a[1][n-1] - a[1][i];
18 if(pos <= A) B = A, A = pos;
19 else if(pos < B) B = pos;
20 }
21 printf("%d\n", A + B);
22 return 0;
23 } 参考代码
Problem B Gennady the Dentist
题意：模拟牙医看病。
简析：可以维护一个标记来判断小孩有没有逃走，然后从前往后扫这个队列。
过程中进行两个操作：
①看病：按题意减去后面小孩的信心，然后处理逃走。
②逃走：给小孩标记出队，给后面的人减去信心，同时处理连锁反应。
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 using namespace std;
5 const int maxn = 5000;
6 int v[maxn], d[maxn], p[maxn];
7 vector<int> ans;
8 bool out[maxn];
9 int n;
10
11 void run(int pos)
12 {
13 out[pos] = 1;
14 for(int i = pos + 1; i < n; i++)
15 {
16 if(out[i]) continue;
17 p[i] -= d[pos];
18 if(p[i] < 0) run(i);
19 }
20 return;
21 }
22
23 void cure(int pos)
24 {
25 for(int i = pos + 1; i < n; i++)
26 {
27 if(v[pos] == 0) break;
28 if(out[i]) continue;
29 p[i] -= v[pos], v[pos]--;
30 }
31 for(int i = pos + 1; i < n; i++)
32 {
33 if(out[i]) continue;
34 if(p[i] < 0) run(i);
35 }
36 return;
37 }
38
39 int main(void)
40 {
41 scanf("%d", &n);
42 for(int i = 0; i < n; i++) scanf("%d%d%d", v+i, d+i, p+i);
43 for(int i = 0; i < n; i++)
44 {
45 if(out[i]) continue;
46 ans.push_back(i);
47 cure(i);
48 }
49 printf("%d\n", ans.size());
50 for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i] + 1);
51 puts("");
52 return 0;
53 } 参考代码
2.2
Problem A Duff in Love
题意：给出 一个 n ,找到最大的 x ,使得 x 满足 ，x 是 n 的因子，并且x 的因子中没有平方数
简析：将 n 分解质因数，每个质因数取一个
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<vector>
7 #include<set>
8 using namespace std;
9
10 typedef long long LL;
11 const int maxn = 100005;
12 int dp[maxn];
13 int Max[maxn];
14 vector<int> p;
15
16 int vis[maxn];
17 int T,a[105];
18 int cnt[maxn];
19 set<long long > s;
20 LL n;
21
22 void solve( long long x){
23 LL y = x;
24 // printf("y = %I64d\n",y);
25 for(long long j = 2;1LL*j*j <= y;j++){
26 if(y%j == 0){
27 // printf("j = %I64d\n",j);
28 while(y%j == 0){
29 s.insert(j);
30 y = y/j;
31 }
32 }
33 }
34 if(y > 1) s.insert(y);
35
36 // for(set<long long >::iterator it = s.begin();it != s.end();++it){
37 // printf("*it = %d\n",*it);
38 //}
39
40 }
41
42 void work(){
43 if(n == 1){
44 puts("1");
45 return;
46 }
47 if(s.size() < 2){
48 printf("%I64d\n",*s.begin());
49 return;
50 }
51 LL res = 1;
52 for(set<long long >::iterator it = s.begin();it != s.end();++it){
53 res = res*(*it);
54 }
55 printf("%I64d\n",res);
56 }
57
58 int main(){
59 while(scanf("%I64d",&n) != EOF){
60 s.clear();
61 solve(n);
62 work();
63 }
64 return 0;
65 } 参考代码
Problem B Duff and Weight Lifting
题意：给出 n 个数，如果满足 2^a1 + 2^a2 +...+2^ak = 2^x = S,则可以将 a1，a2,...ak消掉，问最少需要多少次消掉所有的数
简析：从小到大的消，两个 1 变成一个 2，两个2变成一个3，模拟这样的过程，剩下的不能再合并的数的个数就是需要的操作数
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<vector>
6 #include<queue>
7 using namespace std;
8
9 const int maxn = 1000005;
10 int a[maxn];
11 int n;
12
13 priority_queue<int,vector<int>,greater<int> > q;
14
15 int main(){
16 while(scanf("%d",&n) != EOF){
17 while(!q.empty()) q.pop();
18
19 for(int i = 1;i <= n;i++) scanf("%d",&a[i]),q.push(a[i]);
20
21 int c = 0;
22 while(!q.empty()){
23 if(q.size() >= 2){
24 int x = q.top();q.pop();
25 int y = q.top();q.pop();
26 if(x == y) q.push(x+1);
27 else {
28 q.push(y);
29 c++;
30 }
31
32 // printf("x = %d y = %d\n",x,y);
33 }
34 if(q.size() == 1) {
35 int x = q.top();q.pop();
36 c++;
37 }
38 if(q.size() == 0) break;
39 }
40 printf("%d\n",c);
41
42 }
43
44 } 参考代码
然后，可以发现是在 统计 S 的二进制表现形式中 1 的个数
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6
7 const int maxn = 5e6+5;
8 int a[maxn],bit[maxn];
9 int n;
10
11 void solve(){
12 int ans = 0;
13 for(int i = 0;i < maxn;i++){
14 bit[i+1] += bit[i]/2;
15 bit[i] = bit[i]%2;
16 ans += bit[i];
17 }
18 printf("%d\n",ans);
19 }
20
21 int main(){
22 while(scanf("%d",&n)!= EOF){
23 memset(bit,0,sizeof(bit));
24 for(int i = 1;i <= n;i++){
25 scanf("%d",&a[i]);
26 bit[a[i]]++;
27 }
28 solve();
29 }
30 return 0;
31 } 参考代码
可以再做一下这两题，也和进制有关
Vanya and Scales
Slime Combining
2.3
Problem A Rebranding
题意：给一个长度为n的字符串，做m次字母替换，求替换后的字符串。
简析：先初始化一个字母表到自己本身的映射，每一次替换，把相应字母的象做一次交换。
最后根据交换完成后的映射，将字符串转化成新串。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 const int maxn = 2e5 + 10;
6 int pos[26], re[26];
7 char s[maxn];
8
9 int main(void)
10 {
11 int n, m;
12 scanf("%d %d %s", &n, &m, s);
13 for(int i = 0; i < 26; i++) pos[i] = i;
14 for(int i = 0; i < m; i++)
15 {
16 char x[5], y[5];
17 scanf("%s %s", x, y);
18 swap(pos[x[0]-'a'], pos[y[0]-'a']);
19 }
20 for(int i = 0; i < 26; i++) re[pos[i]]=i;
21 for(int i = 0; i < n; i++) putchar(re[s[i]-'a']+'a');
22 puts("");
23 return 0;
24 } 参考代码
Problem B Median Smoothing
题意：给一个二进制串，定义一种操作：将101变为111,010变为000.问几次操作后该串不再变化。
简析：首先要发现只有101和010会发生变化，也即是说一旦出现了连续两个相同字符，这两个字符就不会变。
我们除去所有连续相同的字符，剩下的就只有01交错的串，它们在经过一系列操作后会最终变为相同。
很容易发现要将一个长度为x的01交错串变为相同需要(x - 1) / 2次操作。
所以考虑所有的01交错串，最长的那个决定了答案。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 const int maxn = 5e5 + 10;
6 int a[maxn];
7
8 bool ok(int i)
9 {
10 return a[i] != a[i-1] && a[i] != a[i+1];
11 }
12
13 int main(void)
14 {
15 int n;
16 scanf("%d", &n);
17 for(int i = 1; i <= n; i++) scanf("%d", a + i);
18 int ans = 0;
19 for(int i = 2; i < n; i++)
20 {
21 if(ok(i))
22 {
23 int cnt = 0, p = i;
24 while(p < n && ok(p)) p++, cnt++;
25 ans = max(ans, ( cnt + 1 ) / 2);
26 for(int j = 0; j < ( cnt + 1 ) / 2; j++)
27 a[i+j] = a[i+j-1], a[i+cnt-j-1] = a[i+cnt-j];
28 }
29 }
30 printf("%d\n", ans);
31 for(int i = 1; i <= n; i++) printf("%d ",a[i]);
32 return 0;
33 } 参考代码
2.4
Problem A The Monster and the Squirrel
题意：给出一个 n 边形，问收集完所有核桃需要跳多少次
简析：找规律是 (n-2)*(n-2)
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<vector>
6 #include<queue>
7 using namespace std;
8
9
10 typedef long long LL;
11 const int maxn = 1e5+5;
12 int n,m;
13 int a[maxn];
14
15 void solve(){
16 if(n == 3){
17 puts("1");
18 return;
19 }
20
21 printf("%I64d\n",1LL*(n-2)*(n-2));
22 }
23
24 int main(){
25
26 while(scanf("%d",&n) != EOF){
27 solve();
28 }
29 return 0;
30 } 参考代码
Problem B The Big Race
题意：A,B两人赛跑，速度相等，但是A的步长是 w,B 的步长是 b,跑道的长度 是 L，在大于L的地方都是深渊，A,B两人打成平手的条件是两人同时落入深渊
给出 t ，问[1,t] 内可以选择出多少个L，输出个数与 t 的比
简析：L 满足 L % w = L % b，即L 满足
L = x*w + r = y*b + r -------------- (1)
在一个周期M = lcm(w,b)内，满足 (1) 式的r 的个数 为 k = min(w,b)
证明：在第一个 周期 [1,M] 内，r 的取值范围是 [0,min(w,b)-1]
又因为需要 满足 (1)式子
所以，L - r = x*w = y*b >= M
所以在 一个周期 lcm 内只有 min(w,b) 个
如果 t > M, 那么 ans = t/M * k + min(min(w,b)-1, t%M)
如果 t < M，那么 ans = min(min(w,b)-1, t)
在判断 t 和 M 的大小的时候，可能会爆long long，可以两边取一下 log 来判断大小关系
1 #include<cstdio>
2 #include<cmath>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 typedef long long LL;
9 LL t,w,b;
10
11 LL gcd(LL a,LL b){
12 return (!b)?a:gcd(b,a%b);
13 }
14
15 int sgn(double x){
16 if(fabs(x) < 1e-6) return 0;
17 return x > 0?1:-1;
18 }
19
20 void solve(){
21 LL g = gcd(w,b);
22 LL fz = 0;
23 LL fm = t;
24 double cha = log(1.0*w)+log(1.0*b)-log(1.0*g)-log(1.0*t);
25 if(sgn(cha)>0){
26 fz = min(t,min(w,b)-1);
27 }
28 else{
29 LL lcm = (w/gcd(w,b))*b;
30 LL c = (t/lcm);
31 fz = c*min(w,b);
32 LL l1 = t%lcm;
33 LL l2 = t-c*lcm;
34 t = t%lcm;
35 fz += min(t,min(w,b)-1);
36 }
37 LL gg = gcd(fz,fm);
38 printf("%I64d/%I64d\n",fz/gg,fm/gg);
39 }
40
41 int main(){
42 while(scanf("%I64d %I64d %I64d",&t,&w,&b) != EOF){
43 solve();
44 }
45 return 0;
46 } 参考代码
2.5
Problem A BerSU Ball
题意：男女skill相差不能超过1，求最大匹配。
简析：男女分别排序后，从小到大扫一遍男，贪心的尽可能先与小的女匹配。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cmath>
5 using namespace std;
6 int a[111], b[111];
7
8 int main(void)
9 {
10 int n, m;
11 scanf("%d", &n);
12 for(int i = 0; i < n; i++) scanf("%d", a + i);
13 scanf("%d", &m);
14 for(int i = 0; i < m; i++) scanf("%d", b + i);
15 sort(a, a + n);
16 sort(b, b + m);
17 int j = 0, ans = 0;
18 for(int i = 0; i < n; i++)
19 {
20 if(j == m) break;
21 if(abs(a[i] - b[j]) <= 1) j++, ans++;
22 else
23 {
24 while(j < m - 1 && b[j] < a[i] - 1) j++;
25 if(abs(a[i] - b[j]) <= 1) j++, ans++;
26 }
27 }
28 printf("%d\n", ans);
29 return 0;
30 } 参考代码
Problem B Given Length and Sum of Digits...
题意：求一共m位，且每位数字和为s的最小的数与最大的数。
简析：首先如果s为0且m大于1，或者s大于9m是无解的。
最小的数只要先在最高位填1，然后从最低位开始尽可能填9。
最大的数只要从最高位开始往后尽可能填9即可。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 int a[111], b[111];
6
7 int main(void)
8 {
9 int m, s;
10 scanf("%d %d", &m, &s);
11 if(!s && m > 1 || s > m * 9) puts("-1 -1");
12 else
13 {
14 int tmp = s;
15 for(int i = 1; i <= m; i++)
16 tmp -= a[i] = min(tmp, 9);
17 tmp = s - 1;
18 b[1] = 1;
19 for(int i = m; i; i--)
20 b[i] += min(tmp, 9), tmp -= min(tmp, 9);
21 for(int i = 1; i <= m; i++) printf("%d", b[i]);
22 putchar(' ');
23 for(int i = 1; i <= m; i++) printf("%d", a[i]);
24 }
25 return 0;
26 } 参考代码
2.6
Problem A Valuable Resources
题意：给出n个点，求包含这 n 个点的最小的正方形的面积
简析：扫一遍求出 xmin 和 xmax,ymin,ymax,取 max(xmax-xmin,ymax-ymin) 作为边长
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6
7 int a[1005],b[1005];
8 long long area;
9
10 int main()
11 {
12 int i,j,n;
13 long long ans1,ans2;
14 scanf("%d",&n);
15 for(i=0;i<n;i++)
16 {
17 cin>>a[i]>>b[i];
18 }
19 sort(a,a+n);
20 sort(b,b+n);
21
22 ans1=a[n-1]-a[0];
23 ans2=b[n-1]-b[0];
24 long long t=max(ans1,ans2);
25 printf("%I64d\n",t*t);
26 } 参考代码
Problem B Bits
题意：给出 n 个询问 ，求出在[1,r] 之间的 bitcount（x） 最大的x
简析：从 l 开始一位一位的加 1直到大于 r
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include <cmath>
5 #include<algorithm>
6 using namespace std;
7
8 typedef long long LL;
9
10 int main()
11 {
12 int n;
13 LL l,r;
14 scanf("%d",&n);
15 while(n--)
16 {
17 scanf("%I64d %I64d",&l,&r);
18 for(int i=0;i<63;i++)
19 if((l|(1LL<<i))<=r) l|=(1LL<<i);
20
21 printf("%I64d\n",l);
22 }
23 } 参考代码
2.7
Problem A Towers
题意：最多进行k次移动单块操作，使得最高塔与最低塔高度差最小。
简析：因为数据很小，反复排序把最高的移一个到最低的即可。
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <algorithm>
5 using namespace std;
6 typedef pair<int, int> pii;
7 vector<pii> ans;
8 pii t[111];
9
10 int main(void)
11 {
12 int n, k;
13 scanf("%d %d", &n, &k);
14 for(int i = 0; i < n; i++)
15 {
16 scanf("%d", &t[i].first);
17 t[i].second = i + 1;
18 }
19 for(int i = 0; i < k; i++)
20 {
21 sort(t, t + n);
22 if(t[0].first == t[n-1].first) break;
23 t[0].first++, t[n-1].first--;
24 ans.push_back(pii(t[n-1].second, t[0].second));
25 }
26 sort(t, t + n);
27 printf("%d %d\n", t[n-1].first - t[0].first, ans.size());
28 for(int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
29 return 0;
30 } 参考代码
Problem B Exams
题意：n门考试，第$i$门可以在${a}_{i}$或者${b}_{i}$时考$(a > b)$，但是登记仍按照${a}_{i}$，
要求登记时间非严格递增，问考完至少要几天。
简析：先按照${a}_{i}$排序，从前往后扫，维护前几门考完的时间，
如果这门${b}_{i}$大于等于前面考完的时间则提前考，否则按原时间。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 typedef pair<int, int> pii;
6 pii c[5555];
7
8 int main(void)
9 {
10 int n;
11 scanf("%d", &n);
12 for(int i = 0; i < n; i++) scanf("%d %d", &c[i].first, &c[i].second);
13 sort(c, c + n);
14 int ans = c[0].second;
15 for(int i = 1; i < n; i++)
16 ans = c[i].second >= ans ? c[i].second : c[i].first;
17 printf("%d\n", ans);
18 return 0;
19 } 参考代码
转载于:https://www.cnblogs.com/chdacm/p/5174680.html
![goalng nil interface浅析持续学习[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)