挑战赛#18 全题解
2025-05-21 21:19:10
发布于：北京
19阅读
0回复
0点赞
T1
按照题意模拟即可，注意 while 循环条件不要写错。
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
while(n||m){
if(n){
n--;
cout<<'#';
}
if(m){
m--;
cout<<'*';
}
}
return 0;
}
T2
既然他们都想让对方拿的数更大，那么我们不妨让他们依次拿大数给对方，排个序即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,x,y;
ll a[200005];
int main(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,greater<ll>());
for(ll i=1;i<=n;i++){
if(i&1) x+=a[i];
else y+=a[i];
}
cout<<y<<' '<<x;
return 0;
}
T3
简单来说，让你把一个数列分成连续的不超过 段，求每一段重量和中的最大值，最小化之后，是多小。
最大值最小化，明显的二分，check 也不难写。
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
ll n,k,l,r,mid,ans;
ll a[MAXN];
inline bool can(const ll &mid){
ll res=1,sum=0;
for(ll i=1;i<=n;i++){
if(a[i]>mid) return false;
sum+=a[i];
if(sum>mid){
sum=a[i];
res++;
}
}
return res<=k;
}
int main(){
cin>>n>>k;
for(ll i=1;i<=n;i++) cin>>a[i];
l=0,r=1e18;
while(l<=r){
mid=l+r>>1;
if(can(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
T4
首先给出了限制 ，那么我们直接记录每一个位置上的，右边第一个 。
接下来制定贪心策略（注意：任意次操作，本入赛时没看到）。首先容易想到，最高位越大，二进制越大。所以，我们选择最左边的 作为 即可。
接下来， 要取 右方第一个 ，为什么呢？这样想，如果取到了第一个 ，那么它会变成 ，这样，下一次的 就可以取到 变成的 ，显然比其他位置更加优秀。
修改直接按题意即可。
Code:
#include<bits/stdc++.h> //%%% BaiRX
using namespace std;
int n,l,r;
int nxt[2][1000001];
string s;
int main(){
cin>>n>>s;
for(int i=n-1;i>=0;i--){
if(s[i]=='0'){
nxt[0][i]=i;
nxt[1][i]=nxt[1][i+1];
}
else{
nxt[0][i]=nxt[0][i+1];
nxt[1][i]=i;
}
}
l=nxt[0][0];
r=nxt[1][l];
while(l<r){
for(int i=l;i<=r;i++) s[i]^=1;
l=r;
r=nxt[1][l+1];
}
cout<<s;
return 0;
}
T5
一眼 bfs，但是有点不一样。
考虑使用 个二进制位表示是否已经拿到钥匙和是否已经拯救小枫，扩展的时候写几个判断即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e3+13;
struct node{
ll floor,x,y;
};
ll n,m,bx,by,ex,ey;
ll dist[4][MAXN][MAXN];
ll dire[2][4]={{1,-1,0,0},{0,0,1,-1}};
bool vis[4][MAXN][MAXN];
char ch[MAXN][MAXN];
queue<node> que;
inline void bfs(){
node a,b;
vis[0][bx][by]=true;
que.push({0,bx,by});
while(!que.empty()){
a=que.front();
que.pop();
for(ll i=0;i<4;i++){
b={a.floor,a.x+dire[0][i],a.y+dire[1][i]};
if(b.x<=0||b.x>n||b.y<=0||b.y>m) continue;
b.floor|=ch[b.x][b.y]=='!';//是否有钥匙
b.floor|=(ch[b.x][b.y]=='M'&&(b.floor&1))<<1;//有钥匙且走到小枫位置可以解救
if(ch[b.x][b.y]=='#'||vis[b.floor][b.x][b.y]) continue;
if(ch[b.x][b.y]=='$'&&!(b.floor&2)) continue;
dist[b.floor][b.x][b.y]=dist[a.floor][a.x][a.y]+1;
vis[b.floor][b.x][b.y]=true;
que.push(b);
}
}
return;
}
int main(){
cin>>n>>m;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>ch[i][j];
if(ch[i][j]=='N'){
bx=i;
by=j;
}
else if(ch[i][j]=='@'){
ex=i;
ey=j;
}
}
}
bfs();
if(vis[3][ex][ey]) cout<<"we were here together";
else if(vis[0][ex][ey]) cout<<"sorry";
else cout<<"NO";
return 0;
}
T6
dfs 是很显然的，考虑优化。
显然的，优化 dfs，第一种是记忆化，第二种是 dp，记忆化没写过，直接考虑 dp。
令 表示取模后为 的方案数量，容易得到 。
注意负数，随时取模。（赛时没取模喜提罚时）
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+16,MOD=998244353;
ll n;
ll dp[21],a[MAXN],t[21];
int main(){
cin>>n;
for(ll i=1;i<=n;i++){
cin>>a[i];
a[i]%=21;
}
dp[0]=1;
for(ll i=1;i<=n;i++){
for(ll j=0;j<21;j++) t[j]=dp[((j-a[i])%21+21)%21];
for(ll j=0;j<21;j++){
dp[j]+=t[j];
if(dp[j]>=MOD) dp[j]-=MOD;
}
}
cout<<dp[0];
return 0;
}
有帮助，赞一个