2021牛客OI赛前集训营-普及组(第三场)解析
P.S. 传送门:https://ac.nowcoder.com/acm/contest/20102#question
1. A-反码:https://ac.nowcoder.com/acm/contest/20102/A
解析:考察基本的字符串处理,题意明确。注意使用 getline 时,对于 string 类型的字符串s,格式为 getline(cin,s); 而对于长度为 N 的字符数组s,格式为 cin.getline(s,N); 记得下标从 0 开始。
代码:(好习惯:尽量用getline读入一行)
#include<cstdio> #include<iostream> #include<cstring> using namespace std; string s; int main() { getline(cin,s); if(s[0]=='0') cout<<s; else for(int i=0; i<s.size(); ++i) if(i==0) cout<<s[i]; else if(s[i]=='1') cout<<'0'; else cout<<'1'; return 0; }
2.B-异或:https://ac.nowcoder.com/acm/contest/20102/B
解析:如果每次都移动,时间复杂度 O(n*m),一定会超时。那么可以思考到本题的特殊性质:第一个是异或和,可以考虑用前缀和维护区间异或和;第二个是循环移动,由定义可得每移动 n 格就会回到原地,因此移动 cnt 格可以变为移动 cnt%n 格,再者观察可得,向右循环移动 cnt 格后,其实是把原数列分成了两部分:以 a[n] 为界限,右边是原来的 a[1]~a[n-cnt],而左边是原来的 a[n-cnt+1]~a[n]。这样变成了静态区间合并的问题,就可以用前缀和维护啦。(注意特判,而且要加上中间的 a[n]^a[1] )。
代码:(别忘开long long)
#include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<cmath> using namespace std; #define int long long const int N=1e5+5; int n,m,a[N],b[N],sum[N],cnt; int get_sum(int l,int r) { return l==r?0:l==1?sum[r]:sum[r]-sum[l]; } void solve() { scanf("%lld%lld",&n,&m); for(int i=1; i<=n; ++i) { scanf("%lld",&a[i]); if(i==1) sum[i]=0; else if(i==2) sum[i]=a[i-1]^a[i]; else sum[i]=sum[i-1]+(a[i-1]^a[i]); } printf("%lld ",sum[n]); for(int i=1; i<=m; ++i) { scanf("%lld",&b[i]); cnt=(cnt+b[i]%n)%n; if(cnt==0) printf("%lld ",sum[n]); else printf("%lld ",get_sum(1,n-cnt)+get_sum(n-cnt+1,n)+(a[1]^a[n])); } } signed main() { solve(); return 0; }
3.C-最大公约数:https://ac.nowcoder.com/acm/contest/20102/C
解析:小学奥数题。如果暴力枚举任意两个数,显然只有20分,那么可以考虑逆向思维--枚举所有可能的公因数,找到其中合法的最大的那一个;也就是从公因数出发,找到要选的两个数。显然不管如何选择这两个数,他们的最大公因数一定在 [1,r] 之间。设选择的最大公因数为 i ,要找到两个数为 a 和 b (a < b)。最大公因数的定义即为两者共同的因数,那么显然 a, b 都是 i 的倍数即可。为了保证其在区间[l,r]之内,可以考虑最小和最大的情况,也就是距离 l 最近且大于 l 的第一个 i 的倍数,和距离 r 最近且小于 r 的第一关 i 的倍数。数学表达即为:a = ceil(l/i) * i , b = floor(r/i) * i .如果 a, b 均在区间内且 a < b,就可以认为此 i 合法,选最大的即可。
代码:
#include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<cmath> #include<bitset> using namespace std; const int N=1e7+3; int l,r,ans; void solve() { scanf("%d%d",&l,&r); for(int i=r; i>=1; --i) { int a=(l%i==0?l/i:l/i+1)*i,b=r/i*i; if(a<b&&a>=l&&a<=r&&b>=l&&b<=r) { ans=i; break; } } printf("%d",ans); } int main() { solve(); return 0; }
4.D-波浪:https://ac.nowcoder.com/acm/contest/20102#question
解析:所谓“波浪数组”,体现在图形上就是一“峰”一“谷”交替,“峰”高“谷”低。如何将一个图形改为“峰谷”形式?从前向后依次修改,首先要确定起始点到底是“峰”还是“谷”,这样才能决定下一步走向。由于两者并无交集,全集就是这两种情况分别讨论,看那个更优即可。那么什么时候需要修改呢?又怎样修改?显然,如果当前点是“谷”,那么它一定比上一个点低,所以如果大于等于就是不合法情况,重新把它按入谷底,送个最小值即可;同理,如果当前点是“峰”,那么它一定比上一个点高,所以如果小于等于就是不合法情况,重新把它抬入云霄,送个最大值即可。最后,如何判定当前是在“峰”还是“谷”呢?看起始点,分奇偶讨论(或者叫找规律)就完成了。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+5,MAX=0x3f3f3f3f,MIN=-MAX; int n,a[N],a1[N],a2[N],ans1,ans2; void solve() { scanf("%d",&n); for(int i=1; i<=n; ++i) scanf("%d",&a[i]),a1[i]=a2[i]=a[i]; if(n<=2) { //特判 printf("0"); return; } for(int i=2; i<=n; ++i) { //将起始点作为“峰”的情况,则第二个点为“谷” if(i%2==0&&a1[i]>=a1[i-1]) { //为“谷”时的不合法情况 a1[i]=MIN;//修改为“谷” ++ans1;//统计这次修改 } if(i%2==1&&a1[i]<=a1[i-1]) { //为“峰”时的不合法情况 a1[i]=MAX;//修改为“峰” ++ans1;//统计这次修改 } } for(int i=2; i<=n; ++i) { //将起始点作为“谷”的情况,则第二个点为“峰” if(i%2==1&&a2[i]>=a2[i-1]) { //为“谷”时的不合法情况 a2[i]=MIN;//修改为“谷” ++ans2;//统计这次修改 } if(i%2==0&&a2[i]<=a2[i-1]) { //为“峰”时的不合法情况 a2[i]=MAX;//修改为“峰” ++ans2;//统计这次修改 } } printf("%d",min(ans1,ans2));//两种情况无交集,取个最小值即可 } int main() { solve(); return 0; }
咳咳,点个赞再走吧~
全部评论
(0) 回帖