普及组周模拟赛16题解
首先来看T1，咦？怎么没看懂题，再一看，咦？怎么还是看不懂。再看一下样例，欸？这不就是求阶乘吗？
真的没有描述里的那么可怕。盘他！（别忘了取模）
MY CODE：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
long long sum=1;//保险一点啊
for(int i=1;i<=n;i++)
{
sum*=i;//算阶乘
sum%=int(1e9+7);//取模啦
}
cout<<sum%int(1e9+7);
return 0;
}第二题，
首先来考虑暴力，我们发现要是把所有数都变成9，一定是最优的。我们又发现把越小的数变成9.一定会更优。为什么呢？很简单，如果我们把1变成9，那么序列的和会加上8，而把7变成9，那么序列的和只会加上2 。于是有了这点，我们就可以先从小到大排一遍序，之后暴力修改每一个数。复杂度，可以得到50分的好成绩。
50分MY CODE：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int m;
cin>>m;
int a[n+5];
int s[n+5];
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
// s[i]=s[i-1]+a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
a[i]=9;//暴力的修改
int sum=0;
for(int j=1;j<=n;j++)
sum+=a[j];//暴力的查询
if(sum>=m)//暴力的去算
{
cout<<i;
return 0;
}
// if(i*9-s[i]+s[n]-s[i]>=m)i
// {
// cout<<i;
// return 0;
// }
}
}修改？查询？
这不是线段树吗（树状数组也可以）？首先我们可以将数组排一下序。之后用线段树将上过程模拟，即可。复杂度最坏O(NlogN)。可以通过本题。
MY CODE：
#include <bits/stdc++.h>
#define maxn 4*1000005
#define ls rt<<1
#define rs rt<<1 | 1
using namespace std;
typedef long long ll;
int n,a[maxn],m;
ll sum[maxn];
void update(int rt)
{
sum[rt]=sum[ls]+sum[rs];
}
void build(int rt,int L,int R)
{
int mid=(L+R)/2;
if (L==R)
sum[rt]=a[L];
else
{
build(ls,L,mid);
build(rs,mid+1,R);
update(rt);
}
}
void modify(int rt,int L,int R,int p,int x)
{
sum[rt]+=x;
if (L==R)
return ;
int mid = L+R>>1;
if (p<=mid)
modify(ls,L,mid, p, x);
else
modify(rs,mid+1, R, p, x);
}
ll query(int rt,int L,int R,int l,int r)
{
int mid=L+R>>1;
ll res=0;
if (L>=l&&R<=r)
return sum[rt];
if (l<=mid)
res+=query(ls,L,mid,l,r);
if (r > mid)
res+=query(rs, mid + 1, R, l,r);
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
int sum=0;//sum记录序列的总和
int jsq=0;//jsq记录当前的序号
sort(a+1,a+n+1);
while(sum<=m)
{
jsq++;
int op,l,r,p,x;
modify(1,1,n,jsq,9-a[jsq]);//修改
if(query(1,1,n,1,n)>=m)//查询
{
cout<<jsq;//输出当前的序号
return 0;
}
}
return 0;
}69行！好长啊！
难道没有别的做法了吗，of course there is.线段树是O(logN)查询，那么有没有O(1)查询的哪？很显然我们只需要维护一个前缀和，之后也只需模拟上过程，即可。
MY CODE：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int m;
cin>>m;
int a[n+5];
int s[n+5];
int sum=0;
s[0]=0;
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+(9-a[i]);//计算前缀和
if(sum+s[i]>=m)
{
cout<<i<<endl;
return 0;
}
}
}好清新啊，好多了！！！
第三题
首先我们考虑暴力，我们只需要模仿涂卡的过程，即可，我们可以枚举全排列。
之后判断两个涂的矩阵是否相等。复杂度很高是，可以通过<=8的点，like this:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int sum=0;
if(n==1)
cout<<1;
if(n==2)
cout<<2;
if(n==3)
{
int a[n+5][n+5];
//memset(a,0,sizeof(a));
int c[n+5][n+5];
//memset(c,0,sizeof(c));
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[1][i]=1;
a[2][j]=1;
a[3][k]=1;
c[i][1]=1;
c[j][2]=1;
c[k][3]=1;
int flg=1;
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
if(a[x][y]!=c[x][y])
flg=0;
}
}
if(flg==1)
{
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
cout<<a[x][y];
}
puts("");
}
}
}
}
}
}
if(n==4)
{
int a[n+5][n+5];
//memset(a,0,sizeof(a));
int c[n+5][n+5];
//memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=1;l<=n;l++)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[1][i]=1;
a[2][j]=1;
a[3][k]=1;
a[4][l]=1;
c[i][1]=1;
c[j][2]=1;
c[k][3]=1;
c[l][4]=1;
int flg=1;
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
if(a[x][y]!=c[x][y])
flg=0;
}
}
if(flg==1)
sum++;
}
}
}
}
cout<<sum;
}
if(n==5)
{
int a[n+5][n+5];
//memset(a,0,sizeof(a));
int c[n+5][n+5];
//memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=1;l<=n;l++)
{
for(int g=1;g<=n;g++)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[1][i]=1;
a[2][j]=1;
a[3][k]=1;
a[4][l]=1;
a[5][g]=1;
c[i][1]=1;
c[j][2]=1;
c[k][3]=1;
c[l][4]=1;
c[g][5]=1;
int flg=1;
for(int x=1;x<=n;x++)
{
for(int y=1;y<=n;y++)
{
if(a[x][y]!=c[x][y])
flg=0;
}
}
if(flg==1)
sum++;
}
}
}
}
}
cout<<sum;
}
...
return 0;
}我们可以把这些数，写下来，得到这样的一个序列
1，2，4，10，26，76，232...
我们令f[i]表示第i个数。那么我们会发现，
f[i]=f[i-1]+(i-1)*f[i-2];
利用这个公式，我们就可以，套到代码里，之后就可以AC，啦！
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
long long f[n+5];
f[0]=1;
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[i-1]+(i-1)*f[i-2];//套公式
f[i]%=int(1e9+7);//别忘了取模
}
cout<<f[n];//输出要求的那个
return 0;
}
第四题是什么鬼啊，不会。。。 \kk
于是你就拿到了300分。。。
离AKIOI又近了一步。。。
左边刷题右边 chat 效果很好