牛客NOIP暑期七天营-提高组5+普及组5

<h1>————提高组————</h1>   <h1>第一题：deco的abs</h1> <h2>题目链接：<a href="https://ac.nowcoder.com/acm/contest/934/A" target="_blank">https://ac.nowcoder.com/acm/contest/934/A</a></h2> 因为每个数都可以加任意次 d ，所以可以推出 0 <= 相邻两个数的差值的绝对值 < d  ，于是我们先让所有数对d取模 再枚举每个位置，用 last 记录上一个数的值，然后求 abs(a[now] - last) 、abs( a[now] + d - last)、abs( a[now] - d, last )即可 下面贴代码：　　　　 <div class="cnblogs_code" onclick="cnblogs_code_show('7821cb70-b844-43a9-9413-df114537236f')"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850150923_BEE14B9FE62E4101C719260C64AA4C83"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850150948_BE319C0086E6D58007898F5FCE19C980"> <div id="cnblogs_code_open_7821cb70-b844-43a9-9413-df114537236f" class="cnblogs_code_hide"> <pre> 1 #include <bits/stdc++.h> 2 #define ll long long 3 const int N = 1e3+10; 4 using namespace std; 5 int n, d, now, last; 6 ll ans; 7 int main() 8 { 9 ios::sync_with_stdio(false); 10 while(cin>>n>>d>>last) 11 { 12 ans = 0; 13 for (int i = 2; i <= n; i++) 14 { 15 cin>>now; 16 int k = (now - last) % d; 17 ans += min(abs(k), min(abs(k - d), abs(k + d))); 18 last = now; 19 } 20 cout << ans << endl; 21 } 22 return 0; 23 }</pre> </div> View Code </div>     <h1>第二题：</h1> <h2> 题目链接：<a href="https://ac.nowcoder.com/acm/contest/934/B" target="_blank">https://ac.nowcoder.com/acm/contest/934/B</a></h2> 这道题的解法是莫比乌斯反演，因为这个算法我也才刚开始学，所以打的过程中出了很多问题 然后就是题目本身的数据好像也有点问题，很多正解的代码提交也是tle，不过听说赛后重测了 （我的分数本来是170，排在59，但后来分数没变排名却成了55（滑稽...滑稽）） 下面是作者给的题解 <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151272_91A4A0E99C43F1199FD20A2E19A1B2A4">   贴下我的代码tle <div class="cnblogs_code" onclick="cnblogs_code_show('0d97d53b-df99-40f1-b86e-56f6187a1fd0')"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151285_BEE14B9FE62E4101C719260C64AA4C83"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151304_BE319C0086E6D58007898F5FCE19C980"> <div id="cnblogs_code_open_0d97d53b-df99-40f1-b86e-56f6187a1fd0" class="cnblogs_code_hide"> <pre> 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1000010; 4 const int mod=998244353; 5 int vis[N],p[N],phi[N],num[N],cnt,ans=1,K; 6 int fac[N],rev[N],Mn[N],P[N]; 7 vector<int>G[N]; 8 int pow_mod(int a,int x) 9 { 10 int res=1; 11 while(x) 12 { 13 if(x&1) res=1LL*res*a%mod; 14 x>>=1; 15 a=1LL*a*a%mod; 16 } 17 return res; 18 } 19 void init() 20 { 21 for(int i=2; i<N; i++) 22 { 23 if(!vis[i]) p[++cnt]=i,Mn[i]=mod,P[i]=i; 24 for(int j=1; j<=cnt&&i*p[j]<N; j++) 25 { 26 vis[i*p[j]]=1; 27 P[i*p[j]]=p[j]; 28 if(!(i%p[j])) break; 29 } 30 } 31 } 32 int main() 33 { 34 ios::sync_with_stdio(false); 35 int n,Q,x; 36 init(); 37 cin>>n; 38 for(int i=1; i<=n; i++) 39 { 40 cin>>x; 41 while(x>1) 42 { 43 int t=P[x],res=0; 44 while(x%t==0) x/=t,res++; 45 G[t].push_back(res); 46 } 47 } 48 for(int i = 1; i<=cnt; i++) 49 { 50 if(G[p[i]].size()==0) continue; 51 sort(G[p[i]].begin(),G[p[i]].end()); 52 int res=0,sum=0; 53 res=G[p[i]][0]; 54 for(int j=1; j<G[p[i]].size(); j++) sum+=res,res+=G[p[i]][j]; 55 ans=1LL*ans*pow_mod(p[i],sum)%mod; 56 } 57 cout<<ans<<endl; 58 return 0; 59 }</pre> </div> View Code </div> 贴下大佬accept的代码 <div class="cnblogs_code" onclick="cnblogs_code_show('b06f0b20-a280-4d33-9a9e-8f77dd8f2742')"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151326_BEE14B9FE62E4101C719260C64AA4C83"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151347_BE319C0086E6D58007898F5FCE19C980"> <div id="cnblogs_code_open_b06f0b20-a280-4d33-9a9e-8f77dd8f2742" class="cnblogs_code_hide"> <pre> 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define M 1000005 5 #define inf 0x3f3f3f3f 6 const int Mod=998244353; 7 int n; 8 int Max,A[M]; 9 int Ans=1; 10 int Cnt[M]; 11 LL f[M]; 12 int R_P(int x,LL y) { 13 int res=1; 14 while(y) { 15 if(y&1)res=1LL*res*x%Mod; 16 x=1LL*x*x%Mod,y>>=1; 17 } 18 return res; 19 } 20 int main() { 21 scanf("%d",&n); 22 for(int i=1; i<=n; ++i) 23 scanf("%d",A+i),Max=max(A[i],Max),++Cnt[A[i]]; 24 for(int i=Max; i>1; --i) { 25 int res=0; 26 for(int j=i; j<=Max; j+=i)res+=Cnt[j]; 27 if(res>1) { 28 f[i]=1LL*res*(res-1)>>1; 29 for(int j=i+i; j<=Max; j+=i)f[i]-=f[j]; 30 Ans=1LL*Ans*R_P(i,f[i])%Mod; 31 } 32 } 33 printf("%d",Ans); 34 }</pre> </div> View Code </div>     ps：第三题题目有点恶心就直接暴力拿了20分走人       <h1>————普及组————</h1>   <h1>第一题：手术等级???</h1> <h2>题目链接：<a href="https://ac.nowcoder.com/acm/contest/929/A" target="_blank">https://ac.nowcoder.com/acm/contest/929/A</a></h2> 个人感觉挺经典的一道题。。。 a[ N ] 存题目给定的数组，sum[ N ] 存 a[ i ] * i的前缀和，sum_[ N ] 存 a[ i ]的前缀和那么假设我们 要切的位置为k和k+1之间，那么切开后的区间为 1......k 和 k......n，那么此时的完美度可以这么表示： wmd = a[1]*1+a[2]*2+...+a[k]*k     +    a[i]*(i - k) + a[i+1]*(i+1-k)+...+a[n]*[n-k] ，对于后半部分我们可 以发现 a[ i ]*(i - k) 可以分解为 a[ i ]*i - a[ i ]*k ，所以最后的 wmd 可以表示为下面的式子： wmd = a[ 1 ] * 1 + a[ 2 ] * 2 + ... + a[ k ] * k + ... + a[ n ] * n - k*( a[ k+1] + ... + a[ n ])   = sum[ n ] - k * (sum_[ n ] - sum[ n-k ]); 贴下代码： <div class="cnblogs_code" onclick="cnblogs_code_show('cff8df56-ece8-4aeb-acd1-2f1cd030c4e6')"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151357_BEE14B9FE62E4101C719260C64AA4C83"> <img src="https://uploadfiles.nowcoder.com/images/20191127/552689300_1574850151367_BE319C0086E6D58007898F5FCE19C980"> <div id="cnblogs_code_open_cff8df56-ece8-4aeb-acd1-2f1cd030c4e6" class="cnblogs_code_hide"> <pre> 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define inf 0x3f3f3f3f3f3f3f 5 template<class T> void read(T &x) 6 { 7 x=0; 8 char ch=getchar(); 9 while(!isdigit(ch))ch=getchar(); 10 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 11 } 12 const int N = 1e5+10; 13 ll a[N],sum[N],sum_[N]; 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 int n; 18 while(cin>>n) 19 { 20 cin>>a[1]; 21 sum[1] = a[1]; 22 for(int i=2;i<=n;i++) 23 { 24 cin>>a[i]; 25 sum[i] = sum[i-1] + a[i] * i; 26 } 27 partial_sum(a+1,a+1+n,sum_+1); 28 ll ans = inf; 29 // a[1]*1 + a[2]*2 + a[3]*3 + a[4]*4 + a[5]*5; 30 // -3*(a[4] + a[5]); 31 for(int k=0;k<=n;k++) 32 { 33 ans = min(ans,sum[n] - k*(sum_[n] - sum_[k])); 34 } 35 cout<<ans<<endl; 36 //cout<<inf<<endl; 37 } 38 return 0; 39 }</pre> </div> View Code </div>   因为打完提高组已经没多少时间了，所以我普及组就做了一题，剩下的题目留给以后慢慢