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 ",x,tmp); 22 if(tmp){ 23 l += pm[c]; 24 // printf("--l = %d ",l); 25 } 26 c++; 27 } 28 // printf("l = %d ",l); 29 res.push_back(l); 30 n -= l; 31 x = n; 32 } 33 printf("%d ",res.size()); 34 for(int i = 0;i < res.size();i++) printf("%d ",res[i]); 35 printf(" "); 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 ",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 ", 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 ",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 ",i,v[i]); 40 sum+=v[i]; 41 } 42 printf("%d ",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 ", 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(" "); 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 ", 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 ", 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 ",ans-2); 35 printf("%d %d ",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 ",ans-1); 45 printf("%d %d ",dp[i][j],has[j]); 46 return 0; 47 } 48 } 49 } 50 51 printf("%d ",ans); 52 printf("-1 -1 "); 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 ", (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 ", 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 ", 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 %I64d ",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 ",min(min(n,m),(n+m)/3)); 12 } 13 return 0; 14 }