挑战赛#18全题解（不是占位）
2025-05-21 19:43:05
发布于：北京
194阅读
0回复
0点赞
耶耶耶 T1、2、3 是首 A！
但是 T4 坠机
T1
基础语法，没什么好讲的。
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
while(i<n||j<m)
{
if(i<n)
{
s+='#';
i++;
}
if(j<m)
{
s+='*';
j++;
}
}
cout<<s;
return 0;
}
T2
纯模拟（好像算贪心？），排序后由大到小依次交给对方（小午给小枫，小枫给小午）。
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,greater<int>());
for(i=1;i<=n;i++)
{
if(i&1)sum2+=a[i];//以奇偶性判断目前谁给
else sum1+=a[i];
}
cout<<sum1<<" "<<sum2;
return 0;
}
T3
首先答案具有单调性（正整数依次上涨），所以可以使用二分答案。
二分每次搬运的大货物重量和的最小值，如果需要此次数小于等于 ，这个方案可行，可以尝试缩小。
check 请读者自行体会。
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(i=1;i<=n;i++)
{
cin>>w[i];
l=max(l,w[i]);
r+=w[i];
}
while(l<r)
{
int mid=(l+r)>>1,cnt=1,Sum=0;
for(i=1;i<=n;i++)
{
if(Sum+w[i]>mid)
{
cnt++;
Sum=w[i];
if(cnt>k)break;
}
else Sum+=w[i];
}
if(cnt<=k)r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
T4
致敬传奇 T4 坠机王 BaiRX，喜提 罚时。
注意到每次翻转区间，最右侧的 会被翻转至 ，可以继续作为左端点。
为了没有多余的 ，每次找到 作为左端点， 后的 第一个 作为右端点，如果没有结束就继续。
使用差分维护翻转次数。
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
nxt0[n]=nxt1[n]=-1;
for(i=n-1;i>=0;i--)
{
if(s[i]=='0')nxt0[i]=i;
else nxt0[i]=nxt0[i+1];
if(s[i]=='1')nxt1[i]=i;
else nxt1[i]=nxt1[i+1];
}
l=nxt0[0];
if(l==-1)
{
cout<<s;
return 0;
}
r=nxt1[l];
while(l<r)
{
f[l]++;
f[r+1]--;
l=r;
r=nxt1[l+1];
}
for(i=0;i<=n;i++)f[i]+=f[i-1];
for(int i=0;i<n;i++)res+=(s[i]-'0')^(f[i]&1)?'1':'0';
cout<<res;
return 0;
}
T5
水 BFS，状态增加是否有钥匙和是否救了小枫，按题意搜索即可。
struct Node
{
int x,y;
bool key,helpM;
};
pair<int,int> find(char c)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]==c)return {i,j};
}
}
return {-1,-1};
}
string bfs()
{
auto st=find('N'),ed=find('@');
queue<Node> q;
q.push({st.first,st.second,0,0});
vis[st.first][st.second][0][0]=1;
bool f=0;
while(!q.empty())
{
Node cur=q.front();
q.pop();
if(cur.x==ed.first&&cur.y==ed.second)
{
if(cur.helpM)return "we were here together";
else f=1;
}
for(int i=0;i<4;i++)
{
int nx=cur.x+dx[i],ny=cur.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m)continue;
bool nkey=cur.key,help=cur.helpM;
if(s[nx][ny]=='#'||(!cur.helpM&&s[nx][ny]=='$'))continue;
if(s[nx][ny]=='!')nkey=1;
if(s[nx][ny]=='M'&&cur.key)help=1;
if(!vis[nx][ny][nkey][help])
{
vis[nx][ny][nkey][help]=1;
q.push({nx,ny,nkey,help});
}
}
}
return f?"sorry":"NO";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)cin>>s[i][j];
}
cout<<bfs();
return 0;
}
T6
一道 DP 题， 表示使得模数为 的有多少情况。
注意空的时算作为 ，所以开始 。
动态转移方程请读者自行体会。
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
dp[0]=1;
for(i=1;i<=n;i++)
{
vector<int> tmp=dp;
for(int j=0;j<21;j++)
{
if(dp[j]==0)continue;
tmp[(j+a[i]%21)%21]=(tmp[(j+a[i]%21)%21]+dp[j])%mod;
}
for(int j=0;j<21;j++)dp[j]=tmp[j];
}
cout<<dp[0]%mod;
return 0;
}
有帮助，赞一个