正文

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

IP云
IP云V管理员/3 阅读
09/09
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

————提高组————

第一题：deco的abs

题目链接：https://ac.nowcoder.com/acm/contest/934/A

因为每个数都可以加任意次 d ，所以可以推出 0 <= 相邻两个数的差值的绝对值 < d  ，于是我们先让所有数对d取模

再枚举每个位置 ，用 last 记录上一个数的值 ，然后求 abs(a[now] - last) 、abs( a[now] + d - last)、abs( a[now] - d, last )即可

下面贴代码：

#include <bits/stdc++.h>
#define ll long long
const int N = 1e3+;
using namespace std;
int n, d, now, last;
ll ans;
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>d>>last)
{
ans = ;
for (int i = ; i <= n; i++)
{
cin>>now;
int k = (now - last) % d;
ans += min(abs(k), min(abs(k - d), abs(k + d)));
last = now;
}
cout << ans << endl;
}
return ;
}

第二题：

题目链接：https://ac.nowcoder.com/acm/contest/934/B

这道题的解法是莫比乌斯反演，因为这个算法我也才刚开始学，所以打的过程中出了很多问题

然后就是题目本身的数据好像也有点问题，很多正解的代码提交也是tle，不过听说赛后重测了

（我的分数本来是170，排在59，但后来分数没变排名却成了55（滑稽...滑稽））

下面是作者给的题解

贴下我的代码tle

#include<bits/stdc++.h>
using namespace std;
const int N=;
const int mod=;
int vis[N],p[N],phi[N],num[N],cnt,ans=,K;
int fac[N],rev[N],Mn[N],P[N];
vector<int>G[N];
int pow_mod(int a,int x)
{
int res=;
while(x)
{
if(x&) res=1LL*res*a%mod;
x>>=;
a=1LL*a*a%mod;
}
return res;
}
void init()
{
for(int i=; i<N; i++)
{
if(!vis[i]) p[++cnt]=i,Mn[i]=mod,P[i]=i;
for(int j=; j<=cnt&&i*p[j]<N; j++)
{
vis[i*p[j]]=;
P[i*p[j]]=p[j];
if(!(i%p[j])) break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n,Q,x;
init();
cin>>n;
for(int i=; i<=n; i++)
{
cin>>x;
while(x>)
{
int t=P[x],res=;
while(x%t==) x/=t,res++;
G[t].push_back(res);
}
}
for(int i = ; i<=cnt; i++)
{
if(G[p[i]].size()==) continue;
sort(G[p[i]].begin(),G[p[i]].end());
int res=,sum=;
res=G[p[i]][];
for(int j=; j<G[p[i]].size(); j++) sum+=res,res+=G[p[i]][j];
ans=1LL*ans*pow_mod(p[i],sum)%mod;
}
cout<<ans<<endl;
return ;
}

贴下大佬accept的代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define M 1000005
#define inf 0x3f3f3f3f
const int Mod=;
int n;
int Max,A[M];
int Ans=;
int Cnt[M];
LL f[M];
int R_P(int x,LL y) {
int res=;
while(y) {
if(y&)res=1LL*res*x%Mod;
x=1LL*x*x%Mod,y>>=;
}
return res;
}
int main() {
scanf("%d",&n);
for(int i=; i<=n; ++i)
scanf("%d",A+i),Max=max(A[i],Max),++Cnt[A[i]];
for(int i=Max; i>; --i) {
int res=;
for(int j=i; j<=Max; j+=i)res+=Cnt[j];
if(res>) {
f[i]=1LL*res*(res-)>>;
for(int j=i+i; j<=Max; j+=i)f[i]-=f[j];
Ans=1LL*Ans*R_P(i,f[i])%Mod;
}
}
printf("%d",Ans);
}

ps：第三题题目有点恶心就直接暴力拿了20分走人

————普及组————

第一题：手术等级???

题目链接：https://ac.nowcoder.com/acm/contest/929/A

个人感觉挺经典的一道题。。。

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 ]);

贴下代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f
template<class T> void read(T &x)
{
x=;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();
}
const int N = 1e5+;
ll a[N],sum[N],sum_[N];
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin>>n)
{
cin>>a[];
sum[] = a[];
for(int i=;i<=n;i++)
{
cin>>a[i];
sum[i] = sum[i-] + a[i] * i;
}
partial_sum(a+,a++n,sum_+);
ll ans = inf;
// a[1]*1 + a[2]*2 + a[3]*3 + a[4]*4 + a[5]*5;
// -3*(a[4] + a[5]);
for(int k=;k<=n;k++)
{
ans = min(ans,sum[n] - k*(sum_[n] - sum_[k]));
}
cout<<ans<<endl;
//cout<<inf<<endl;
}
return ;
}

因为打完提高组已经没多少时间了，所以我普及组就做了一题，剩下的题目留给以后慢慢