SICNU五一赛题解

🕗 发布于 2024-09-30 06:42 算法

题目	名称	知识点
A	a+b	思维
B	倒转乾坤	签到
C	不水杯	dfs
D	简单硬币	思维题，进制
E	子矩阵	双指针，前缀和
F	围墙	bfs
G	MH学长的旅行	最短路
H	WYR学长理财	二分答案
I	传纸条	线性dp

难度预估：B、A < D、E、H 、C < I、G、F

A、a+b

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> cnt;
int main(){
    int n,c;
    cin >> n >> c;
    for(int i = 1 ; i <= n ; i ++){
        int x; cin >> x;
        cnt[x]++;
    }
    ll ans = 0;
    for(auto [x,y] : cnt)
        if(cnt.count(c-x)){
            if(x!=c-x)ans += y*cnt[c-x];
            else ans += (y-1)*cnt[c-x]; 
        }
    cout << ans;
    return 0;
}

B、倒转乾坤

可以观察到，运动轨迹始终在直径上，所以答案是 $4 n d$ 。此题是去年四川省赛的原签到题。

D、简单硬币

贪心思维题，当1到x-1的硬币都能够凑齐，但x的值凑不齐时，我们可以用一枚x面值的硬币，使得前面所有硬币和他组合，能够凑齐x+1到 2x-1面值的硬币。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4+10;
int coin[N];

int main()
{
int n, target;
cin >> n >> target;

for(int i = 0; i < n; i ++ )
cin >> coin[i];

sort(coin, coin+n);

int num = 0, s = 0;
for(int i = 0; i < n && s < target; i ++ )
{
while(coin[i] > s+1)
{
s += s+1;
num ++;
if(s >= target) break;
}
s += coin[i];
}
while(s < target)
{
s += s+1;
num ++;
}
cout << num;
}

E、子矩阵

#include <bits/stdc++.h>
#define N 10001
using namespace std;
long long sum=0;
int a[N][N];
 
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
a[i][j]+=a[i-1][j];
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int s=0;
for(int l=1,r=1;r<=m;r++){
s+=a[j][r]-a[i-1][r];
while(s>k){
s-=a[j][l]-a[i-1][l];
l++;
}
sum+=r-l+1;
}
}
}
cout<<sum<<endl;
return 0;
}

H、 WYR学长理财

标准的二分答案

#include <bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=1e5+5;
ll ans=0;
ll len[N];
int n,k;
//check函数，用来判断mid是否满足条件，是二分答案的核心和难点所在 
int check(int mid)
{
int sum=0;//计算能切成多少长为mid的小木条 
for(int i=1;i<=n;i++){
sum+=(len[i]/mid);
}
if(sum<k) return 0;//小于k则不满足 
if(sum>=k) return 1;//大于k则满足 
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>len[i];
//答案区间[1,1e8] 
ll l=1,r=1e8;
//ans初始化以便于判断是否有答案 
ans=-1;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
//mid满足切成k段，则ans先记为mid 
ans=mid;
//去更大的区间找是否有满足的，以保证最后时最大值 
l=mid+1;
}
//密度不满足能切成k段，则去更小的区间找是否有满足的 
else r=mid-1; 
}
if(ans==-1) cout<<0;
else cout<<ans;
return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 0x3f3f3f3f
const int mod = 998244353;
const int N = 1e5 + 10;
int n, k;
int a[N];
bool check(int mid){
    int res = 0;
    for(int i = 1 ; i <= n ; i ++) res += a[i]/mid;
    return res >= k;
}
void solve(){
    cin >> n >> k;
    int mx = 0;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i];
        mx = max(a[i],mx);
    }
    int l = 0 , r = mx;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
}   
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}

C、不水杯

本题题目大家可能会想到写贪心，其实贪心是错误的，考虑以下样例：

选手A目前3分、选手B目前2分、选手C目前2分，B和C还要进行两场比赛，发现这种情况A一定不会是第一名；

事实上本题正确做法是dfs，因为每组用例的比赛局数 $m(\leq10)$ 很小，所以直接用dfs枚举

每一局的结果就可以做到 𝑂(3^{𝑚}𝑇) 的复杂度，可以通过本题

所以大家要学会看数据范围做题，当看到数据范围是dfs可过、这个dfs又不难写的时候，就别想别的了，直接dfs启动

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int MAX=100+10;
struct node{
    int idx,score;
} a[MAX];
int ans,cnt;
int n, m;
vector<pair<int,int> >  res;
void dfs(int step){
    if(step == cnt ){
        int rank = 1;
        for(int i = 2 ; i <= n ; i ++)
        {
            if(a[i].score > a[1].score) rank ++;
        }
        ans = min(ans,rank);
        return;
    }
    //对于每场没有1,x和y的比赛，有三种情况x胜利,y胜利,打平
    for(int i = 1 ; i <= 3; i ++){
        if(i == 1){
            a[res[step].fi].score += 3;
            dfs(step + 1);
            a[res[step].fi].score -= 3;
        }else if(i == 2){
            a[res[step].se].score += 3;
            dfs(step + 1);
            a[res[step].se].score -= 3;
        }else{
            a[res[step].fi].score += 1;
            a[res[step].se].score += 1;
            dfs(step + 1);
            a[res[step].fi].score -= 1;
            a[res[step].se].score -= 1;
        }
    }
}
void solve()
{
    res.clear();
    cnt = 0;
    ans = INT_MAX;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i].score;
        a[i].idx = i;
    }
    int mm = m;
    while(mm--)
    {
        int x ,y;
        cin >> x >> y;
        if(x == 1 || y == 1) a[1].score += 3;//如果有和1比的就让1胜
        else {//否则dfs剩下的
            res.push_back({x,y}); 
            cnt ++;
        }
    }
    dfs(0);
    cout << ans << "\n";
}
int main()
{
    int _;
    cin >> _;
    while(_--) solve();
    return 0;
}

I、传纸条

$dp_{i,j}$ 表示传到点 $i, j$ 的最大路径条数，根据题目可以标记不能到达的点为vis=1, $dp_{i,j}=0$ ,否则 $dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}$ , $dp_{x,y}$ 即为答案

#include<bits/stdc++.h>
#define ll long long
using namespace std;
// 马能够控制的位置 
const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int bx, by, mx, my;
ll f[40][40];
bool s[40][40];
int main(){
    scanf("%d%d%d%d", &bx, &by, &mx, &my);
    bx += 2; by += 2; mx += 2; my += 2;
    f[2][1] = 1;
    s[mx][my] = 1;
    for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
    for(int i = 2; i <= bx; i++)
{
        for(int j = 2; j <= by; j++)
{
            if(s[i][j]) continue;
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    printf("%lld\n", f[bx][by]);
    return 0;
}

G、 MH学长的旅行

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<utility> 
#include<functional>

int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
    {
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

using std::priority_queue;
using std::pair;
using std::vector;
using std::make_pair;
using std::greater;

struct Edge
{
    int to,next,cost;
}edge[4500001];
int cnt,head[210005];

void add_edge(int u,int v,int c=0)
{
    edge[++cnt]=(Edge){v,head[u],c};
    head[u]=cnt;
}

int dis[210005];
bool vis[210005];
void Dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > points;
    points.push(make_pair(0,s));
    while(!points.empty())
    {
        int u=points.top().second;
        points.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]>dis[u]+edge[i].cost) 
                {
                    dis[to]=dis[u]+edge[i].cost;
                    points.push(make_pair(dis[to],to));
                }
            }
        }
    }
}

int main()
{
    int n=Read(),m=Read(),k=Read(),s=Read(),t=Read();
    int u,v,c;
    for(int i=0;i<m;++i)
    {
        u=Read(),v=Read(),c=Read();
        add_edge(u,v,c);
        add_edge(v,u,c);
        for(int j=1;j<=k;++j)
        {
            add_edge(u+(j-1)*n,v+j*n);
            add_edge(v+(j-1)*n,u+j*n);
            add_edge(u+j*n,v+j*n,c);
            add_edge(v+j*n,u+j*n,c);
        }
    }
    for(int i=1;i<=k;++i)
{
add_edge(t+(i-1)*n,t+i*n);
}//预防奇葩数据
    Dijkstra(s);
    printf("%d",dis[t+k*n]);
    return 0;
}

F、围墙

这个题主要思路就是两部分，第一要判断能不能走到围墙下面，第二就是要记录围墙代表的#的个数和岗哨代表的#的个数（这个还是很好区分，因为题目保证了一个岗哨四周不会出现别的岗哨也就是一个#的四个方向上不会有#，如果有就代表它一定是围墙）。

第一部分判断可以用 $b f s$ 去判断能不能走到，也可以用 $df s$

第二部分计算可以用 $b f s$ 或者 $df s$ 去搜围墙代表的#的个数，也可以直接根据围墙和岗哨的区别去遍历地图上每一个#来判断这个#具体代表的是围墙还是岗哨。（后者要简单一点，如果比赛的时候用后者写的可以再用前面的 $b f s$ 或者 $df s$ 思路写一下,加深理解。）

#include <bits/stdc++.h>
using namespace std;

const int N=110;
int n,m;
int stx,sty,xx,yy;//起始点坐标、bfs走到的第一个围墙#坐标 
char mp[N][N];//记录地图 
bool pd[N][N];//标记点走没走过 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0}; 
int cnt=0;//记录#的个数 
int res_cnt=1;//记录围墙面积（围墙#个数） 

//用来判断这个点是不是围墙 
bool check(int x,int y){ 
for(int i=0;i<4;i++){ //遍历这个点的周围四个方向 
int nex=x+dx[i],ney=y+dy[i];
if(nex<1||ney<1||nex>n||ney>m)return false; //越界了 
if(mp[nex][ney]=='#')//说明x,y这个点四周有#存在 说明这个点必是围墙 
return true;
}
return false;
}

//正常bfs的check逻辑，来判断有没有越界或者走没走过 
bool check_1(int x,int y){
  if(x<1||y<1||x>n||y>m)return false;
if(pd[x][y])return false;
return true;
}

//先判断能不能走到围墙周围，也可以用dfs 
bool bfs_1(){   
queue<pair<int,int>>q;
q.push({stx,sty});
pd[stx][sty]=1;

//正常的bfs过程 
while(!q.empty()){
auto t=q.front();
q.pop();
int nowx=t.first,nowy=t.second;

for(int i=0;i<4;i++){ //遍历四个方向 
int nex=nowx+dx[i];
int ney=nowy+dy[i];

if(check_1(nex,ney)){ //判断走没走过这个点或者这个点有没有越界 
if(mp[nex][ney]=='#'){//如果遇到了 # 去判断是不是岗哨 
if(check(nex,ney)){ //如果是围墙 
xx=nex;//记录下来这个围墙的坐标，下一步记录围墙面积可以从这个点开始 
yy=ney;
return true;//找到了，直接返回 
}else
continue;
}

pd[nex][ney]=1;
q.push({nex,ney});
} 
}
}
return false;//走不到围墙 
}

//第二次bfs计算围墙面积的check，保证只能走有#的格子 
bool check_2(int x,int y){
  if(x<1||y<1||x>n||y>m)return false;//越界 
if(pd[x][y])return false;//走过了 
if(mp[x][y]!='#')return false;//不是# 

return true;
}

//用来计算围墙#的个数 
void bfs_2(int xx,int yy){
queue<pair<int,int>>q;
q.push({xx,yy});
pd[xx][yy]=1;

//正常bfs过程 
while(!q.empty()){
auto t=q.front();
q.pop();
int nowx=t.first,nowy=t.second;

for(int i=0;i<4;i++){
int nex=nowx+dx[i];
int ney=nowy+dy[i];

if(check_2(nex,ney)){//只能走有#的格子 
res_cnt++;//围墙#的个数加一 
pd[nex][ney]=1;
q.push({nex,ney});
} 
}
}
}

void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='M'){
stx=i;//找起始点位置 
sty=j;
}
if(mp[i][j]=='#')cnt++;//记录#的总个数
}

if(!bfs_1()){//走不到围墙 
cout<<"Game over!"<<endl;
}else{
memset(pd,0,sizeof pd);//记得初始化标记数组 
bfs_2(xx,yy);//这一次的bfs_2是用来记录围墙的面积就是res_cnt
cout<<"yeah!"<<endl;
cout<<cnt*5-4*res_cnt<<endl;//#的总个数乘5减去围墙个数乘4就是最终答案 
} 
}

void init(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}

int main()
{
init(); 
    solve();
    
    return 0;
}

原文地址：https://blog.csdn.net/XUE_DING_E/article/details/142629337

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：用开源软件制作出精美的短视频#视频编辑
下一篇：通信工程学习：什么是TCF技术控制设施

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30