本次模考共4题 我的得分情况如下
| 张的弓 <19503 |
绝对公平 <21048> |
AI作曲 <21039> |
小信的特工行动 <21002> |
|---|---|---|---|
| Accepted 100 分 | Accepted 100 分 | Time Limit Exceeded 30分 | Time Limit Exceeded 55分 |
T1难度 
经过分析 我们可以将行走步数简化为
x个从(1,2n)到(1,2n+2)的过程
即
x=k/(n*2)
剩余y步
y=kmod(n*2)
如果y<n 就说明第k步走到了(2*x+1,1+y）
如果y>=n 就说明第k步走到了(2*x+2,2*n-y)
即
\Delta (A,B)=\begin{cases}
2*x+y （y<n） \\
2*x+2*n-y（n \le y<n*2）
\end{cases}
具体代码如下
if(y<n) cout<<2*x+y<<endl;
else cout<<2*x+2*n-y<<endl;
T2 难度
读完题后我们不难发现 如果想让所以数字的值相等
就要保证每个质因数的个数必须为n的倍数
该题就变的简单多了
核心代码如下
void pri(int x){
while(x!=1){
for(int i=2;i<=x;i++){
if(x%i==0){
facto[i]++;
x/=i;
maxx=max(maxx,i);
break;
}
}
}
}
T3难度
该题的30分是不难拿到的
只需暴力搜索时考虑好边界即可
void dfs(int l,int r,int sum){
if(l==r+1){
maxx=max(maxx,sum+score[a[l-1]][a[l]]);
return ;
}
for(int i=1;i<=m;i++){
int now_sum=sum+score[a[l-1]][i];
a[l]=i;
dfs(l+1,r,now_sum);
a[l]=-1;
}
}
正数为我们将整首乐谱自然地分成了几个区域
我们只需遍历两个整数间连续的负数区域即可
(其中l,r分别代表负数区域的起始和结束位置）
要将30分改为100分需要一点小小的思维转变
先设置一个二维数组dp[i][j]
(i,j分别表示当前下标和a[i]中的音符,dp[i][j]中存储的是当a[i]=j时当前最好情况）
所以我们只需分四种情况讨论
1. 当a[i]>0且a[i-1]>0时
因为此时的a[i]和a[i-1]的值都是固定的
所以
dp[i][a[i]]=dp[i-1][a[i-1]]+score[a[i-1][a[i]]
2. 当a[i]>0且a[i-1]<0时
此时我们需枚举a[i-1]的值j
dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+score[j][a[i]])
3. 当a[i]<0且a[i-1]>0时
此时我们需枚举a[i]的值j
dp[i][j]=max(dp[i][j],dp[i-1][a[i-1]]+score[a[i-1][j])
4. 当a[i]<0且a[i-1]<0时
此时我们需枚举a[i-1]的值j和a[i]的值k
dp[i][k]=max(dp[i][k],dp[i-1][j]+score[j][k])
具体代码如下
for(int i=2;i<=n;i++){
if(a[i]>0){
if(a[i-1]>0){
dp[i][a[i]]=dp[i-1][a[i-1]]+score[a[i-1]][a[i]];
}
else{
for(int j=1;j<=m;j++){
dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+score[j][a[i]]);
}
}
}
else{
if(a[i-1]>0){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i][j],dp[i-1][a[i-1]]+score[a[i-1]][j]);
}
}
else{
for(int j=1;j<=m;j++){
for(int k=1;k<=m;k++){
dp[i][k]=max(dp[i][k],dp[i-1][j]+score[j][k]);
}
}
}
}
}
T4 难度
读完题后观察到要对2^64取模 这里使用 unsigned long long
暴力搜索可以得到50分
void dfs(int x,unsigned long long sum){
if(x==n){
if(sum==s){
for(int i=0;i<n;i++){
cout<<ans[i];
}
flag=1;
}
return ;
}
if(flag==1) return ;
ans[x]='0';
dfs(x+1,sum);
ans[x]='1';
dfs(x+1,sum+b[x]);
}
如何从50分改到100分呢
我们需要用到折半搜索以及
unordered_map<unsigned long long,string> mp
进行2次dfs搜索 每次搜索n/2
将第一次搜索的sum和ans放到mp中
第二次搜索结束后查找s-sum的值是否在mp中并执行后续操作
具体代码如下
void dfs1(int x,unsigned long long sum){
if(x==n/2){
mp[sum]=ans.substr(0,n/2);
return ;
}
ans[x]='0';
dfs1(x+1,sum);
ans[x]='1';
dfs1(x+1,sum+b[x]);
}
void dfs2(int x,unsigned long long sum){
if(x==n){
unsigned long long tem=s-sum;
if(mp.count(tem)){
cout<<mp[tem]<<ans.substr(n/2,n-n/2);
}
return ;
}
ans[x]='0';
dfs2(x+1,sum);
ans[x]='1';
dfs2(x+1,sum+b[x]);
}
在主函数中别忘记给ans定义初始长度
