17-05-31模拟赛

T1:枚举每个数及每两个数的平均数即可。

可将读入的数乘2以避免计算平均数时出现分数。

Code:

 1 #include<iostream> 
 2 #include<cmath> 
 3 #include<cstdio> 
 4 #include<cstdlib> 
 5 #include<cstring> 
 6 #include<algorithm> 
 7 using namespace std; 
 8 int a[100005],n,ans; 
 9 bool b[200005]; 
10 int main() 
11 { 
12     scanf("%d",&n);memset(b,0,sizeof(b)); 
13     for (int i=1;i<=n;++i) scanf("%d",&a[i]),a[i]<<=1; 
14     sort(a+1,a+n+1); 
15     for (int i=1;i<=n;++i) if (!b[a[i]]) b[a[i]]=1,++ans; 
16     for (int i=1;i<n;++i) 
17     for (int j=i+1;j<=n;++j){ 
18         int c=(a[i]+a[j])>>1; 
19         if (!b[c]) b[c]=1,++ans; 
20     } 
21     printf("%d",ans);return 0; 
22 }

T2:将每个数减k并计算其前缀和，统计前缀和等于该数的前缀和的数的个数（即两数中间数的和为0，即该段平均数为k）即可。

Code:

 1 #include<cstdio> 
 2 #include<map> 
 3 #define ll long long  
 4 using namespace std; 
 5 int a,sum,n,k; 
 6 ll ans; 
 7 map <ll,int> m; 
 8 int main() 
 9 { 
10     scanf("%d%d",&n,&k);m[0]=1; 
11     for (int i=1;i<=n;++i) { 
12         scanf("%d",&a);sum+=(a-k); 
13         ans+=m[sum];++m[sum]; 
14     } 
15     printf("%lld",ans);return 0; 
16 }

T3:

Code:

 1 #include<cstdio> 
 2 #include<algorithm> 
 3 #define inf 0x7fffffffffffffffLL 
 4 #define ll long long 
 5 #define MN 500005 
 6 #define t (a[i]%5) 
 7 using namespace std; 
 8 int q[5][MN],a[MN],qn[5],l[5],r[5]; 
 9 ll dif[5],mx,b,c,sum,cnt,ans; 
10 int n,m,pmx; 
11 int main() 
12 { 
13     scanf("%d%d%lld%lld",&n,&m,&b,&c);if (b*5<c) c=b*5; 
14     for (int i=1;i<=n;++i) scanf("%d",&a[i]);sort(a+1,a+n+1); 
15     for (int i=1;i<=n;++i) ++qn[t],q[t][qn[t]]=a[i]; 
16     for (int k=0;k<5;++k){ 
17         for (int i=0;i<5;++i) dif[(k-i+5)%5]=i,l[i]=1,r[i]=0;sum=cnt=0; 
18         for (int i=1;i<=n;++i){ 
19             ++r[t];++cnt;sum+=dif[t]*b-(a[i]+dif[t])/5*c; 
20             while((a[i]+dif[t])/5*c*cnt+sum>m){ 
21                 mx=-inf; 
22                 for (int j=0;j<5;++j){ 
23                     if (l[j]<=r[j]&&dif[j]*b-(q[j][l[j]]+dif[j])/5*c>mx) 
24                     mx=dif[j]*b-(q[j][l[j]]+dif[j])/5*c,pmx=j; 
25                 } 
26                 ++l[pmx];--cnt;sum-=mx;  
27             }ans=max(ans,cnt); 
28         } 
29     }printf("%lld",ans);return 0; 
30 }

T4:题意即求，其中。

我们可以发现，所以只要在行走过程中记录和的值即可。

考虑用动态规划(dp)解决，f[i][j][t]表示走到第i行第j列 =t时的值。

边界条件为f[0][1][0]=f[1][0][0]=0;其余为inf。

转移方程为f[i][j][k]=min(f[i-1][j][k-a],f[i][j-1][k-a])+a²;

Code:

 1 #include<cstdio> 
 2 #include<cstring> 
 3 #include<algorithm> 
 4 #define Mx 5000 
 5 #define inf 707406378 
 6 using namespace std; 
 7 int f[52][52][5005],n,m,a,ans=inf; 
 8 int main() 
 9 { 
10     scanf("%d%d",&n,&m);memset(f,127/3,sizeof(f)); 
11     f[0][1][0]=f[1][0][0]=0; 
12     for (int i=1;i<=n;++i) 
13     for (int j=1;j<=m;++j){ 
14         scanf("%d",&a); 
15         for (int k=a;k<=Mx;++k) 
16         f[i][j][k]=min(f[i-1][j][k-a],f[i][j-1][k-a])+a*a; 
17     } 
18     for (int i=1;i<=Mx;++i) 
19     if (f[n][m][i]<inf) ans=min(ans,(n+m-1)*f[n][m][i]-i*i); 
20     printf("%d",ans);return 0; 
21 }