盡快将前面的練習補上！
每日一練
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=)