2.6

Problem A?Quasi Binary

題意：給出 n ，輸出n至少由k個只含 01的數組成

簡析：按照 n 的位數如果相應的一位不是0的話，就填 1 ，再減去，直到減到 n 為0

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 int n; 9 int b[1005],a[15],pm[10]; 10 11 void solve(){ 12 pm[0]=1; 13 for(int i = 1;i <= 7;i++) pm[i] = pm[i-1]*10; 14 int x = n; 15 vector<int> res; 16 while(n){ 17 int c = 0,l = 0; 18 while(x){ 19 int tmp = x%10; 20 x = x/10; 21 // printf("x = %d tmp = %d\n",x,tmp); 22 if(tmp){ 23 l += pm[c]; 24 // printf("--l = %d\n",l); 25 } 26 c++; 27 } 28 // printf("l = %d\n",l); 29 res.push_back(l); 30 n -= l; 31 x = n; 32 } 33 printf("%d\n",res.size()); 34 for(int i = 0;i < res.size();i++) printf("%d ",res[i]); 35 printf("\n"); 36 } 37 38 int main(){ 39 while(scanf("%d",&n) != EOF){ 40 solve(); 41 } 42 return 0; 43 } 參考代碼

?

Problem B?Tourist's Notes

題意：一個人登山 n 天，給出 m 天的di,hi （表示在第di天登山的高度為hi）,且 abs(h[i]-h[i-1]) <= 1,問這n天登山的最高高度

簡析：假設第 di天的登山高度 為 x，di+1天的登山高度 為 y,這兩個日期的時間間隔為 day,假設這兩個日期之間能夠到達的最大高度為 maxx

如果 x == ?y，

(maxx-x) + (maxx-x) = day

所以 maxx = day/2+x

如果 x > y 或者 x < y

(maxx-x)+(maxx-y) = day

所以 maxx = (day+x+y)/2

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 8 const int maxn = 5e5+5; 9 int n,m; 10 11 struct node{ 12 int d,h; 13 }a[maxn]; 14 15 void solve(){ 16 int maxx = -1; 17 for(int i = 1;i <= m+1;i++){ 18 if(i == 1){ 19 maxx = max(a[i].h+(a[i].d-1),maxx); 20 continue; 21 } 22 if(i == m+1){ 23 maxx = max(a[i-1].h+(n-a[i-1].d),maxx); 24 continue; 25 } 26 int x = a[i].h,y = a[i-1].h; 27 int day = a[i].d-a[i-1].d; 28 if(x == y){ 29 maxx = max(max(x,maxx),day/2+x); 30 continue; 31 } 32 if(abs(x-y) > day){ 33 puts("IMPOSSIBLE"); 34 return; 35 } 36 maxx = max(max(x,y),maxx); 37 maxx = max(maxx,(day+x+y)/2); 38 } 39 printf("%d\n",maxx); 40 } 41 42 int main(){ 43 while(scanf("%d %d",&n,&m) != EOF){ 44 for(int i = 1;i <= m;i++) scanf("%d %d",&a[i].d,&a[i].h); 45 solve(); 46 } 47 return 0; 48 } 參考代碼

?

2.7

Problem A?Tavas and SaDDas

題意：問一個數是僅由4和7構成的數中第幾小的。

簡析：從右往左第ii位對應于2i?12i?1，4對應乘1，7對應乘2，讓高翔帶你自由飛翔吧！

1 #include<cstdio> 2 using namespace std; 3 int main(){ 4 int n,temp=1,ans=0; 5 scanf("%d",&n); 6 while(n){ 7 if(n%10==4) 8 ans+=temp; 9 else 10 ans+=temp*2; 11 temp*=2; 12 n/=10; 13 } 14 printf("%d",ans); 15 return 0; 16 } 參考代碼

?

Problem B?Tavas and Karafs

題意：第ii個迷の棒狀物的長度是A+(i?1)×BA+(i?1)×B，一次操作是選mm個物體啃掉1，

　　　給你一個左端點ll，求最大的右端點rr，使得tt次能啃完[l,r][l,r]的物體。

簡析：二分右端點。

1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 typedef long long LL; 5 6 int main(void) 7 { 8 LL A, B, n; 9 scanf("%I64d %I64d %I64d", &A, &B, &n); 10 while(n--) 11 { 12 LL l, t, m; 13 scanf("%I64d %I64d %I64d", &l, &t, &m); 14 if(A + B * (l - 1) > t) {puts("-1"); continue;} 15 LL L = l, R = 1e7, M; 16 while(L < R) 17 { 18 M = R - (R - L) / 2; 19 LL sum = A * (M - l + 1) + B * (M * (M - 1) - (l - 1) * (l - 2)) / 2; 20 if(A + B * (M - 1) <= t && sum <= m * t) L = M; 21 else R = M - 1; 22 } 23 printf("%I64d\n", L); 24 } 25 return 0; 26 } 參考代碼

?

2.8

Problem A?Covered Path

題意：第1秒的速度 為v1,第t秒的速度為v2,每一秒速度的大小的變化最大為 d，問這t秒內走過的最大路程

簡析：可以直接算出 vi = min(v1+d*i,v2+d*(t-i-1))

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=100005; 17 int v[maxn]; 18 19 int main(){ 20 int i,j,a,b,t,d,sum=0; 21 scanf("%d %d",&a,&b); 22 scanf("%d %d",&t,&d); 23 if(d==0) { 24 printf("%d\n",a+b+a*(t-2)); 25 return 0; 26 } 27 v[1]=a; 28 v[t]=b; 29 for(i=2;i<t;i++) 30 v[i]=v[i-1]+d; 31 32 for(i=t;i>1;i--){ 33 if(v[i-1]-v[i]>d){ 34 v[i-1]=v[i]+d; 35 } 36 } 37 38 for(int i=1;i<=t;i++){ 39 // printf("v[%d]=%d\n",i,v[i]); 40 sum+=v[i]; 41 } 42 printf("%d\n",sum); 43 return 0; 44 45 46 } 參考代碼

因為 d 值很小，對于每一秒，從 -d 到 d 枚舉速度的變化量，只要能夠保證能夠在剩下的時間里能夠減速到v2，就是合法的

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() 6 { 7 int v1, v2, t, d; 8 cin >> v1 >> v2 >> t >> d; 9 10 vector<int> v; v.push_back(v1); 11 int now = v1; 12 for(int i = 2; i <= t-1; i++) 13 { 14 int dd; 15 for(dd = d; dd >= -d; dd--) 16 if(now + dd <= (t - i) * d + v2) 17 break; 18 now += dd; 19 v.push_back(now); 20 } 21 v.push_back(v2); 22 int s = 0; 23 for(int i = 0; i < v.size(); i++) s += v[i]; 24 printf("%d\n", s); 25 26 return 0; 27 } 參考代碼

?

Problem B?Polycarpus' Dice

題意：有?n 個骰子，每個骰子最大的點數為 di，n 個骰子的點數之和為 A，問每個骰子不能夠表示的點數的個數

簡析：計算每個骰子能夠表示的最小點數，最大點數

最小點數可以考慮到其他骰子都為最大值的時候還不夠A

最大點數可以考慮到其他骰子點數都不能為0

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 5e6+5; 9 int d[maxn],ans[maxn]; 10 int n; 11 LL A,sum; 12 13 void solve(){ 14 LL leftsum = 0,minn,maxx; 15 for(int i = 1;i <= n;i++){ 16 leftsum = sum-d[i]; 17 if(A - leftsum > 0) minn = A-leftsum; 18 else minn = 1; 19 maxx = min(1LL*d[i],A-(n-1)); 20 21 if(minn > maxx) printf("%d ",d[i]-1); 22 else printf("%d ",d[i]-(maxx-minn+1)); 23 } 24 printf("\n"); 25 } 26 27 int main(){ 28 while(scanf("%d %I64d",&n,&A) != EOF){ 29 sum = 0; 30 for(int i = 1;i <= n;i++) scanf("%d",&d[i]),sum += 1LL*d[i]; 31 solve(); 32 } 33 return 0; 34 } 參考代碼

?

2.9

Problem A?Pasha and String

題意：給一個字符串，求m次翻轉操作后的字符串。

簡析：翻轉兩次等于沒有翻轉，所以先標記出所有翻轉的位置，最后掃一遍。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 2e5 + 10; 7 char s[maxn]; 8 int rev[maxn]; 9 10 int main(void) 11 { 12 int m, x; 13 scanf("%s %d", s + 1, &m); 14 int l = strlen(s + 1); 15 while(m--) 16 { 17 scanf("%d", &x); 18 rev[x] ^= 1; 19 } 20 int tmp = 0; 21 for(int i = 1; i <= l / 2; i++) 22 { 23 tmp ^= rev[i]; 24 if(tmp) swap(s[i], s[l-i+1]); 25 } 26 printf("%s\n", s + 1); 27 return 0; 28 } 參考代碼

?

Problem B?Ilya and Sticks

題意：n根棍子，每根棍子可以不變或縮短1，用這些棍子拼矩形，求最大面積和。

簡析：排序后從大到小考慮，如果相鄰的長度相等或者僅相差1，則將它們作為一對邊，

　　　最后拼矩形的時候長邊與長邊配對，短邊與短邊配對，所得的面積和最大。

1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1e5 + 10; 8 vector<LL> v; 9 int l[maxn]; 10 11 int main(void) 12 { 13 int n; 14 scanf("%d", &n); 15 for(int i = 0; i < n; i++) scanf("%d", l + i); 16 sort(l, l + n); 17 for(int i = n - 1; i > 0; i--) 18 if(l[i] - l[i-1] < 2) 19 v.push_back(l[i-1]), i--; 20 LL ans = 0, sz = v.size(); 21 for(int i = 0; i < sz - 1; i += 2) ans += v[i] * v[i+1]; 22 printf("%I64d\n", ans); 23 return 0; 24 } 參考代碼

?

2.10

Problem A?Error Correct System

題意：給出兩個字符串 s，t 可以交換 s中兩個字符的位置，求s,t的最小距離

簡析：用 dp[a][b] = i?表示 在第i個位置，s[i] = 'a' ，t[i] = 'b'，

如果存在 dp[a][b] 和 dp[b][a] ，直接交換這兩個字符就好

如果不存在，就交換 dp[a][b] 和dp[b][c]

如果還不存在，就是 -1 ，-1

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<queue> 9 #include<algorithm> 10 #define mod=1e9+7; 11 using namespace std; 12 13 typedef long long LL; 14 const int maxn=200005; 15 char s[maxn],t[maxn]; 16 int dp[105][105]; 17 int has[maxn]; 18 19 int main(){ 20 int i,j,n,ans=0; 21 scanf("%d",&n); 22 cin>>(s+1)>>(t+1); 23 for(i=1;i<=n;i++){ 24 if(s[i]!=t[i]){ 25 dp[s[i]-'a'][t[i]-'a']=i; 26 has[s[i]-'a']=i; 27 ans++; 28 } 29 } 30 31 for(i=0;i<26;i++){ 32 for(j=0;j<26;j++){ 33 if(dp[i][j]!=0&&dp[j][i]!=0){ 34 printf("%d\n",ans-2); 35 printf("%d %d\n",dp[i][j],dp[j][i]); 36 return 0; 37 } 38 } 39 } 40 41 for(i=0;i<26;i++){ 42 for(j=0;j<26;j++){ 43 if(dp[i][j]!=0&&has[j]!=0){ 44 printf("%d\n",ans-1); 45 printf("%d %d\n",dp[i][j],has[j]); 46 return 0; 47 } 48 } 49 } 50 51 printf("%d\n",ans); 52 printf("-1 -1\n"); 53 return 0; 54 } 參考代碼

?

Problem B?Glass Carving

題意：給出一塊w*h的玻璃，再切m刀，求每切一刀后，被切割成的玻璃片面積最大的是多少

簡析：用一個 multiset 存每次切口的位置，再用一個 multiset 存相鄰切口之間的距離

如果當前操作的切口位置 為 x ，在位置集合里找到x 所在的區間 [a,b] ，將x-a,b-x 插入距離集合，同時從距離集合里面刪去b-a

每次對應分別取出長和寬距離集合里的最大值相乘

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<queue> 9 #include<set> 10 #include<algorithm> 11 #define mod=1e9+7; 12 using namespace std; 13 14 typedef long long LL; 15 multiset<int> hh,vv; 16 set<int >ph,qv; 17 set<int>::iterator r,l; 18 19 int main(){ 20 char c; 21 int x,w,h,n; 22 scanf("%d%d%d",&w,&h,&n);getchar(); 23 ph.insert(0);ph.insert(h); 24 qv.insert(0);qv.insert(w); 25 hh.insert(h);vv.insert(w); 26 27 while(n--){ 28 scanf("%c %d",&c,&x);getchar(); 29 30 if(c == 'H') 31 { 32 l = ph.lower_bound(x); 33 r = l; l--; 34 ph.insert(x); 35 hh.insert(x-(*l)); 36 hh.insert((*r)-x); 37 hh.erase(hh.find((*r) - (*l))); 38 } 39 else 40 { 41 l = qv.lower_bound(x); 42 r = l; l--; 43 qv.insert(x); 44 vv.insert(x - (*l)); 45 vv.insert((*r) - x); 46 vv.erase(vv.find((*r) - (*l))); 47 } 48 49 printf("%I64d\n", (long long)(*hh.rbegin()) * (*vv.rbegin())); 50 51 52 } 53 return 0; 54 } 參考代碼

?

2.11

Problem A?Two Buttons

題意：給n，m兩個數，一次操作是將n減一或者乘二，問把n變為m最少要幾步。

簡析：因為n與m的范圍都很小，所以可以無腦のBFS一下。

1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <set> 5 using namespace std; 6 typedef pair<int, int> pii; 7 8 int main(void) 9 { 10 int n, m; 11 scanf("%d %d", &n, &m); 12 set<int> s; 13 queue<pii> q; 14 s.insert(n); 15 q.push(pii(n, 0)); 16 while(!q.empty()) 17 { 18 pii tmp = q.front(); q.pop(); 19 int cur = tmp.first, t = tmp.second; 20 if(cur == m) {printf("%d\n", t); break;} 21 if(cur > 1 && !s.count(cur-1)) s.insert(cur-1), q.push(pii(cur-1, t+1)); 22 if(cur < m && !s.count(cur*2)) s.insert(cur*2), q.push(pii(cur*2, t+1)); 23 } 24 return 0; 25 } 參考代碼

?

Problem B?DNA Alignment

題意：問存在多少個不同的字符串t，使得對于已定義的：

　　　

　　　滿足

　　　

　　　其中shift表示左移1個字符，h表示相同位置字符相同數。

簡析：先考慮這個和式的意義，用s_cnt[A]表示A在s中出現的次數，其他類似的表示，

顯然原式等價于n * (?s_cnt[A] * t_cnt[A] +?s_cnt[T] * t_cnt[T] +?s_cnt[C] * t_cnt[C] +?s_cnt[G] * t_cnt[G] )? 那么對于已知的s，如何構造t讓這個和盡量大呢？ 顯然只要讓t中的所有字符都為s中出現次數最多的那個即可，如果s中有多個字符次數同時最多，則均可選擇。 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 const LL mod = 1e9 + 7; 7 const int maxn = 1e5 + 10; 8 char s[maxn]; 9 int cnt[4]; 10 11 LL qpow(LL a, int b) 12 { 13 LL ret = 1LL; 14 while(b) 15 { 16 if(b & 1) ret = ret * a % mod; 17 a = a * a % mod; 18 b >>= 1; 19 } 20 return ret; 21 } 22 23 int main(void) 24 { 25 int n; 26 scanf("%d%s", &n, s); 27 for(int i = 0; i < n; i++) 28 { 29 if(s[i] == 'A') cnt[0]++; 30 else if(s[i] == 'G') cnt[1]++; 31 else if(s[i] == 'C') cnt[2]++; 32 else cnt[3]++; 33 } 34 sort(cnt, cnt + 4); 35 int tot = 1; 36 for(int i = 0; i < 3; i++) tot += cnt[i] == cnt[3]; 37 printf("%I64d\n", qpow(tot, n)); 38 return 0; 39 } 參考代碼

?

2.12

Problem A?A and B and Compilation Errors

題意：第一行 n 個數 a[i],第二行 n-1個數b[i],第三行 n-2個數 c[i]，求第二行比第一行少的那個數，第三行比第二行少的那個數

簡析：第一行的和為 A,第二行的和為 B，第三行的和為 C，所以為 A-B，B-C

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 5e5+5; 9 int a[maxn],b[maxn],c[maxn]; 10 int n; 11 12 int main(){ 13 while(scanf("%d",&n) != EOF){ 14 LL A = 0,B = 0,C = 0; 15 for(int i = 1;i <= n;i++){ 16 scanf("%d",&a[i]); 17 A += 1LL*a[i]; 18 } 19 for(int i = 1;i <= n-1;i++){ 20 scanf("%d",&b[i]); 21 B += 1LL*b[i]; 22 } 23 for(int i = 1;i <= n-2;i++){ 24 scanf("%d",&c[i]); 25 C += 1LL*c[i]; 26 } 27 printf("%I64d\n%I64d\n",A-B,B-C); 28 } 29 return 0; 30 } 參考代碼

?

Problem B?A and B and Team Training

題意：有n個A和 m個B，可以一個A兩個B一隊，也可以兩個A一個B一隊，求最多能夠組成多少隊

簡析：先要滿足 n+m >= 3才能組成一隊，然后如果 n 更大，就組成兩個A一個B一隊，如果m更大,就組成一個A兩個B一隊

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 int n,m; 8 9 int main(){ 10 while(scanf("%d %d",&n,&m) != EOF){ 11 printf("%d\n",min(min(n,m),(n+m)/3)); 12 } 13 return 0; 14 } 參考代碼

?

轉載于:https://www.cnblogs.com/chdacm/p/6372921.html

總結

以上是生活随笔為你收集整理的2017寒假练习题解 第四周 2.6-2.12的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。