ACGO挑战赛#36非官方题解
2026-09-27 13:45:23
发布于：四川
我不是官方，我只发题解
第一题：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int cnt = 0;
for (int i=0;i<n;i++){
string s;
cin >> s;
int sum=0,even=0;
for (int j=0;j<s.size();j++){
int num = s[j] - '0';
int pos = j + 1;
if (pos % 2 == 1){
sum+= num;
}
else{
even += num;
}
}
if (abs(sum - even) <= k){
cnt++;
}
}
cout << cnt << endl;
return 0;
}
第2题：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<long long>d(n+2,0);
for(int i=0;i<m;i++){
int l,r,w;
cin>>l>>r>>w;
d[l]+=w;
d[r+1]-=w;
}
long long now=0,maxv=0;
int cnt=0;
for(int i=1;i<=n;i++){
now+=d[i];
if(now>maxv){
maxv=now;cnt=1;
}else if(nowmaxv){
cnt++;
}
}
cout<<maxv<<" "<<cnt<<endl;
}
第3题：
#include<bits/stdc++.h>
using namespace std;
int main(){
iossync_with_stdio(false);cin.tie(nullptr);
int n;cin>>n;
vector<long long>st;
for(int i=0;i<n;i++){
long long x;cin>>x;
st.push_back(x);
while(st.size()>=2){
int len=st.size();
if(st[len-1]==st[len-2]){
long long v=st.back();
st.pop_back();st.pop_back();
st.push_back(v+1);
}else break;
}
}
cout<<st.size()<<'\n';
for(int i=0;i<st.size();i++){
if(i>0)cout<<' ';
cout<<st[i];
}
cout<<'\n';
}
第4题：
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v;long long w;
bool operator<(const Edge&o)const{return w<o.w;}
};
vector<int>fa;
int find(int x){
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main(){
iossync_with_stdio(false);cin.tie(nullptr);
int n,m;cin>>n>>m;
vector<Edge>e(m);
for(int i=0;i<m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
sort(e.begin(),e.end());
fa.resize(n+1);
for(int i=1;i<=n;i++)fa[i]=i;
long long ans=0;int cnt=0;
for(auto&ed:e){
int fu=find(ed.u),fv=find(ed.v);
if(fu!=fv){
fa[fv]=fu;ans+=ed.w;cnt++;
if(cntn-1)break;
}
}
if(cntn-1)cout<<ans<<'\n';
else cout<<-1<<'\n';
return 0;
}
第5题：
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const char dir[]={'U','D','L','R'};
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m;cin>>n>>m;
vector<string>g(n+1);
for(int i=1;i<=n;i++)cin>>g[i];
int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
vector<vector<int>>dis(n+1,vector<int>(m+1,0x3f3f3f3f));
deque<pair<int,int>>q;
dis[sx][sy]=0;
q.push_back({sx,sy});
while(!q.empty()){
auto [x,y]=q.front();q.pop_front();
if(xtx&&yty)break;
char c=g[x][y-1];
for(int d=0;d<4;d++){
int nx=x+dx[d];
int ny=y+dy[d];
if(nx<1||nx>n||ny<1||ny>m)continue;
int cost=(cdir[d])?0:1;
if(dis[nx][ny]>dis[x][y]+cost){
dis[nx][ny]=dis[x][y]+cost;
if(cost0)q.push_front({nx,ny});
else q.push_back({nx,ny});
}
}
}
cout<<dis[tx][ty]<<'\n';
return 0;
}
第6题：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;cin>>n;
vector<vector<long long>>c(n,vector<long long>(n));
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>c[i][j];
vector<long long>dp(1<<n,-1);
dp[0]=0;
for(int mask=0;mask<(1<<n);mask++){
if(dp[mask]-1)continue;
int i;
for(i=0;i<n;i++)if(!(mask&(1<<i)))break;
for(int j=i+1;j<n;j++){
if(!(mask&(1<<j))){
int nmask=mask|(1<<i)|(1<<j);
dp[nmask]=max(dp[nmask],dp[mask]+c[i][j]);
}
}
}
cout<<dp[(1<<n)-1]<<'\n';
return 0;
}
有帮助，赞一个