模拟赛 1 题解
A 上班
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int x,y,z;
int main()
{
cin>>x>>y>>z;
printf("%d",x+min(y,z));
}
B 崇拜
代码
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=2e5+100;
int n,x,y,a;
int main ()
{
int ans=0;
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(a>y) ans+=3;
}
printf("%d",ans);
return 0;
}
C 方豆子
标签
递推,递归 字符串
思路
- 用 python 按行暴力拼接。
- 时间复杂度为 \(\mathcal O(4^n)\)。
代码
点击查看代码
n=eval(input())
ans=['******','******','******',\
'***...','***...','***...']
ansi=['......','......','......',\
'...***','...***','...***']
for i in range(n-1):
l=len(ansi)
cur,curi=['' for _ in range(2*l)],['' for _ in range(2*l)]
for j in range(l):
cur[j]=ansi[j]+ansi[j]
cur[j+l]=ansi[j]+ans[j]
for j in range(l):
curi[j]=ans[j]+ans[j]
curi[j+l]=ans[j]+ansi[j]
ans=[e for e in cur]
ansi=[e for e in curi]
for e in ans:
print(e)
D 矩阵
标签 1
BFS 结构体
思路 1
- 如果删去可花费单位时间变换数字的操作，则本题便为简单的 BFS。易发现，BFS 删去上述操作后可做的原因是，先入队列的点花费的时间一定较小。但添加上述操作后，导致先入队列的点花费的时间不一定较小，故可将队列中元素按花费时间由小到大排序，采用优先队列即可。
- 时间复杂度为 \(\mathcal O(n^2\log n)\)。
代码 1
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e3+100;
struct p
{
int x,y,s;
bool operator < (p a) const
{
return a.s<s;
}
};
int n,m;
priority_queue<p> q;
int head,tail;
bool vis[maxn][maxn];
char a[maxn][maxn];
const int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
void bfs()
{
p node;
node.x=1,node.y=1,node.s=0;
q.push(node);
vis[1][1]=true;
head=1,tail=1;
while(!q.empty())
{
int x=q.top().x,y=q.top().y,s=q.top().s;
if(x==n&&y==m)
{
printf("%d",s);
return;
}
q.pop();
for(int i=0;i<4;i++)
{
int tx=x+dx[i], ty=y+dy[i];
if(tx<1||ty<1||tx>n||ty>m) continue;
if(vis[tx][ty]) continue;
if(a[x][y]!=a[tx][ty])
{
vis[tx][ty]=true;
p node;
node.s=s+1,node.x=tx,node.y=ty;
q.push(node);
}
else
{
a[tx][ty]=a[x][y]=='0'?'1':'0';
vis[tx][ty]=true;
p node;
node.s=s+2,node.x=tx,node.y=ty;
q.push(node);
}
}
}
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
bfs();
return 0;
}
标签 2
最短路 Dijkstra
思路 2
- 对于一个方格 P：若其某临近方格与之数字不同，则两点之间连边权为 \(1\) 的边；否则，连边权为 \(2\) 的边。随后跑 \(Dijkstra\) 即可。
- 时间复杂度为 \(\mathcal O(n^2\log n)\)。
E 数数
标签
树状数组/前缀和 递推,动态规划
思路
- 考虑数列大小为 \(i\) 时，可组成的“美好数组”的个数。因为前 \(i-1\) 个数的状态难以搜寻且没有意义，故关注其和——发现其和一定是 \(i-1\) 的 \(1\) 到 \(m\) 倍。故设状态 \(dp_{i,j}\) 表示数列大小为 \(i\) 且其和为 \(j*m\)时，“美好数组”的个数。
- 考虑状态转移方程。从 \(1\) 到 \(m\) 枚举 \(j\)（其中 \(j\) 表示前 \(i\) 数的和是 \(i\) 的 \(j\) 倍），则有：\(dp_{i,j}=\sum dp_{i-1,l},其中，\frac{j*m-a_i}{i-1}=l,a_i\in{1,\dots,m}\)。因为 \(a_i\) 的取值区间是连续的，故 \(l\) 的取值区间是连续的，故只需求出 \(l\) 的最大值与最小值。由此可以用前缀和或树状数组去维护 \(dp_{i-1,*}\)，以便获得任意区间和。
- 若使用树状数组，时间复杂度为 \(\mathcal O(nm\log m)\)；若使用前缀和，时间复杂度为 \(\mathcal O(nm)\)。
代码 PS：采用树状数组
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=2e3+100;
const int MOD=1e9+7;
int n,m,dp[maxn][maxn];
int t[maxn];
void add(int x,int k)
{
if(x>m) return;
for(int i=x;i<=m;i+=(i&-i))
t[i]=((t[i]+k)%MOD+MOD)%MOD;
}
int ask(int x)
{
if(x<=0) return 0;
if(x>m) x=m;
int ans=0;
for(int i=x;i;i-=(i&-i))
ans=(ans+t[i])%MOD;
return ans;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int j=1;j<=m;j++)
dp[1][j]=1,add(j,1);
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int l=(i*j-m+i-2)/(i-1),r=(i*j-1)/(i-1);
dp[i][j]=((ask(r)-ask(l-1))%MOD+MOD)%MOD;
}
for(int j=1;j<=m;j++)
add(j,-dp[i-1][j]+dp[i][j]);
}
printf("%d",(ask(m)+MOD)%MOD);
return 0;
}
教训 PS：因为过于惨烈，所以不能单纯称其为“收获”。
- 在实际运行中，\(l\) 的最大值可能超过 \(m\)，最小值可能小于 \(0\)，从而超出前缀和（或树状数组）的边界，在今后的敲题中一定要注意判断是否越界以及做出相应的处理。
F 打牌
标签
概率 递归 暴力枚举
思路
- 因为只有三张牌且唯有小宁的选牌方式特殊，故可以根据小宁的手牌进行暴力枚举。设 \(cal(A,B,C,tot)\) 表示假设第 \(tot\) 回合为开始回合，小宁、小 a、小 b手牌分别为 A、B、C时，小宁赢的概率。故若设某一状态为 \(P\)，\(P\) 的一级子状态的集合为 \(son_P\)，则 \(cal(P)=\sum\limits_{j\in son_P} (cal(j)*p_j)，p_j为状态 j 出现的概率\)。故采用递归。
- 时间复杂度为 \(\mathcal O(27n)\)。
代码
点击查看代码
n=eval(input())
A,B,C=list(input()),list(input()),list(input())
A.sort();B.sort();C.sort();
def judge(x):
if sorted(x)==['i','n','w']:
return True
return False
mod=10**9+7;
mod27=pow(27,mod-2,mod)
mod18=pow(18,mod-2,mod)
def copyi(x):
return [e for e in x]
def cal(A,B,C,tot):
if judge(A):
return 1
elif judge(B) or judge(C):
return 0
elif tot==n:
return 0
ret=0
if (A[0]==A[1] and A[1]==A[2]) or (A[0]!=A[1] and A[1]!=A[2] and A[0]!=A[2]):
cp=list(range(3))
modi=mod27
else:
modi=mod18
if A[0]==A[1]:
cp=range(2)
elif A[0]==A[2]:
cp=(0,2)
else:
cp=(1,2)
for i in cp:
for j in range(3):
for k in range(3):
Ai,Bi,Ci=copyi(A),copyi(B),copyi(C);
Ai[i],Bi[j],Ci[k]=Ci[k],Ai[i],Bi[j]
ret+=cal(Ai,Bi,Ci,tot+1)*modi
return ret%mod
print(cal(A,B,C,0))