当前位置： 首页 > news >正文

C++算法训练第八天

news 2026/3/26 20:27:44

C++算法训练第八天

以下为牛客挑战

今日收获

学习到了ksm的写法
int ksm(int p,int q,int mod){int result=1;p=p%mod;while (q>0){if(q&1){//result=(1ll*result*p)%mod;}q=q>>1;p=(1ll*p*p)%mod;}return result%mod;
}知道了滚动数组
先有一个数组，然后在操作时候弄一个一样的数组，dp转移完成之后，直接赋值回最先的数组。为了节省空间。练习了一下BFS搜图

【算法竞赛知识点-数学】：快速幂_哔哩哔哩_bilibili

牛客周赛 Round 127

(36条未读私信) 牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

Get The Number

A-Get The Number_牛客周赛 Round 127 (nowcoder.com)

image-20260119195044452

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,x;cin>>n>>m>>x;if(x==(n+m)||(n-m)==x ||((n/m==x)&&(m*x==n))){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}return 0;
}

Sudoku

B-Sudoku_牛客周赛 Round 127 (nowcoder.com)

image-20260119195203324

2
1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

YES
NO

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int m[5][5]={0};for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){cin>>m[i][j];}}for(int i=1;i<=4;i++){set<int>str;for(int j=1;j<=4;j++){str.emplace(m[i][j]);}if(str.size()!=4){cout<<"NO"<<endl;return;}}for(int i=1;i<=4;i++){set<int>str;for(int j=1;j<=4;j++){str.emplace(m[j][i]);}if(str.size()!=4){cout<<"NO"<<endl;return;}}for(int i=1;i<4;i+=2){for(int j=1;j<4;j+=2){int sum=0;sum=m[i][j]+m[i][j+1]+m[i+1][j]+m[i+1][j+1];if(sum!=10){cout<<"NO"<<endl;return;}}}cout<<"YES"<<endl;};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

Carry The Bit

C-Carry The Bit_牛客周赛 Round 127 (nowcoder.com)

image-20260119203924832

3
3749
105
999

4000
110
1000

我们可以用string去存储，一共才2x10五次方

直接string去存储，找到第一个大于5的数，然后剩下的按格式输出就行了，没找到就把最后的变成0；

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){string s;cin>>s;s='0'+s;int p=-1;int l=s.size();for(int i=1;i<l;i++){int m=s[i]-'0';if(m>=5){p=i;break;}}cout<<p<<endl;if(p==-1){for(int i=1;i<l-1;i++){cout<<s[i];}cout<<0<<endl;}else{if(p==1){cout<<1;for(int i=1;i<l;i++){cout<<0;}cout<<endl;return;}for(int i=1;i<p-1;i++){cout<<s[i];}cout<<(s[p-1]-'0')+1;for(int i=p;i<l;i++){cout<<0;}}cout<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

Permutation² Counting

D-Permutation² Counting_牛客周赛 Round 127 (nowcoder.com)

image-20260119212843110

示例1

2
6
1 2 2 1 3 1
5
1 1 2 2 4

6
2

我们看到这个和顺序没有关系，我们可以直接先排序。然后统计个数，因为这个是必须按照1-i这样的，所以我们对于这一次，就是选出两个i的数方法，去和上次的x，再加就行了

image-20260119213328256

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=998244353;
int a[N],b[N],c[N];
void solve(){int n;cin>>n;vector<int>cnt(n+1);for(int i=1,x;i<=n;i++){cin>>x;if(x<1||x>n){continue;}cnt[x]++;}int pre=1;int ans=0;//我们去枚举i，因为，我们知道n的活动范围就是在1-n的，当为1，时候就是冲cnt[i]个数中排列组合一下，选两个(cnt[i]-1)*(cnt[i])/2for(int i=1;i<=n;i++){pre*=((cnt[i]-1)*cnt[i]/2%mod);pre%=mod;ans=(ans+pre)%mod;}cout<<ans<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

Balanced 01-String

E-Balanced 01-String_牛客周赛 Round 127 (nowcoder.com)

image-20260120113955911

2
0?1
????

0
8

思维题。

题目要我们求相同的对数，那我们直接反过来求不同的对数，然后用1-n一共n-1对减去相同的对数就可以判断不同的对数的奇偶性。

就是s[i]!=s[i+1];

这个不同可以用异或来

s[i]^s[i+1],如果相同直接是0，如果不同不为0；

然后我们要去相加这些数。

结果相加，看看不同的奇偶性。

image-20260120114804100

这个可以化简为，

s[0]^s[1]^s[1]^s[2]^s[2]^s[3]........s[n-2]^s[n-1]

由异或的性质相同异或的为0，0……其他等于本身。

化简为

s[0]^s[n-1]

所以只要判断这两个数的就行了，

最后用个去

((n-1)%2-(s[0]^s[n-1]))%2==0

这个，然后个数我们只需要看里面的2的cnt次方个就行了。

s[0]与s[n-1]分3种情况讨论就行了

  1. 没有？全是其他的。直接判断一下就行了。
  2. 有一个那肯定可以组成一个
  3. 有两个可以组成两个。

最后chen中间的个数。

代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
int ksm(int p,int q,int mod){int result=1;p=p%mod;while (q>0){if(q&1){result=(1ll*result*p)%mod;}q=q>>1;p=(1ll*p*p)%mod;}return result%mod;
}
const int N=2e5+10,M=1e3+10,mod=998244353;
int a[N],b[N],c[N],pre[N];
void solve(){string s;cin>>s;int m=0;int n=s.size();if(n==1){if(s[0]=='?'){cout<<2<<endl;return;}else{cout<<1<<endl;return;}}for(int i=1;i<s.size()-1;i++){if(s[i]=='?'){m++;}}int cnt=ksm(2,m,mod);if(s[0]!='?'&&s[n-1]!='?'){if(((n-1)%2-(s[0]^s[n-1]))%2==0){cout<<cnt<<endl;}else{cout<<0<<endl;}}else{if(s[0]=='?'&&s[n-1]=='?'){cout<<(2*cnt)%mod<<endl;}else{cout<<cnt<<endl;}}};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

dp+滚动数组求解

我们定义一个发f[0/1][0/1];
表示当前，为奇数或者偶数的状态下，当前位置为0/1的方案数，转移就是，我们根据你一个方案来转移，一共四个状态，判断单前位置不等于1，那我们不用管，先假设选的就是0；，然后转移g[0][0]和g[1][0],就可以得到，因为我当前位置已经知道了，我们可以看前面为0，1的时候的次数，和奇偶性来判断g[0][0],这个数。g[0][0]=f[1][0]+f[0][1];g[1][0]=f[1][1]+f[0][0];以此类推后面的。结果为，f[0][1]+f[0][0]

代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=998244353;
int a[N],b[N],c[N],pre[N];
void solve(){string s;cin>>s;int n=s.size();s=" "+s;vector<vector<int>>f(2,vector<int>(2));if(s[1]=='?'){f[0][1]=1;f[0][0]=1;}else if(s[1]=='1'){f[0][1]=1;}else{f[0][0]=1;}for(int i=2;i<=n;i++){vector<vector<int>>g(2,vector<int>(2));if(s[i]!='0'){g[0][1]=f[0][0]+f[1][1];g[1][1]=f[1][0]+f[0][1];}if(s[i]!='1'){g[0][0]=f[1][0]+f[0][1];g[1][0]=f[1][1]+f[0][0];}//处理数据。mod；for(int j=0;j<2;j++){for(int k=0;k<2;k++){g[j][k]%=mod;}}f=g;}cout<<(f[0][0]+f[0][1])%mod<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

Matrix Coloring

BFS搜索

F-Matrix Coloring_牛客周赛 Round 127 (nowcoder.com)

image-20260120144421822

2
3
010
101
010
5
00000
01110
01000
01010
01110

111
111
111
00000
01110
01110
01110
01110

我们可以知道这个就是一个简单的BFS，但是这个是先把图先扫一边，把满足条件的先丢进栈中，然后再根据改的，慢慢扩散开来，已达到最后的效果。

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve(){int n;cin>>n;vector<string>s(n);for(int i=0;i<n;i++){cin>>s[i];}queue<pair<int,int>>q;auto check=[&](int x,int y)->bool{if(s[x][y]=='1')return 0;for(int i=0;i<4;i++){int x1=x+dx[i],y1=y+dy[i];int x2=x+dx[(i+1)%4],y2=y+dy[(i+1)%4];if(x1<0|x1>=n||y1<0||y1>=n||x2<0||x2>=n||y2<0||y2>=n)continue;if(s[x1][y1]=='1'&&s[x2][y2]=='1'){return 1;}}return 0;};vector<vector<int>>vis(n,vector<int>(n));//对队列进行初始化for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(s[i][j]=='1')continue;if(check(i,j)&&!vis[i][j]){q.emplace(i,j);vis[i][j]=1;}}}//取出并且进行处理，然后再扩展到旁边相邻的。while(q.size()>0){auto [x,y]=q.front();s[x][y]='1';q.pop();for(int i=0;i<4;i++){int x1=x+dx[i],y1=y+dy[i];if(x1<0||x1>=n||y1<0||y1>=n)continue;if(check(x1,y1)&&!vis[x1][y1]){q.emplace(x1,y1);vis[x1][y1]=1;}}}for(int i=0;i<n;i++){cout<<s[i]<<endl;}};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}
http://www.jsqmd.com/news/273818/

相关文章：

  • 【实战项目】 方正科技市场营销策略研究
  • 2026年上海防水补漏行业顶尖企业权威评测：全面解析防水、修复、翻新与检测服务 - shruisheng
  • 【Web安全】SSRF - 教程
  • 聊聊五种 Redis 部署模式
  • 京东e卡回收真的靠谱吗？揭秘背后真相！ - 京顺回收
  • [MCP] Prompt
  • 从复杂到有序：汽车制造企业多元数据库管理走向自治智能的实践观察
  • 写论文软件哪个好？实测科普！宏智树 AI 凭 “学术真功夫” 成毕业刚需
  • 2026年硅胶模具厂家深度选型指南：食品级与医用级需求下的三大方案解析 - 博客万
  • 【实战项目】 基于springboot的前后端分离学生健康体检管理系统
  • 当 Agent 进入系统阶段，AI 产品开始真正分化
  • 2026年知名的公务车品牌厂家推荐及行业发展解析 - 品牌排行榜
  • 【实战项目】 数字孪生在水利调度中的应用
  • 2026Q1唐山口碑财税公司推荐榜：正规备案为基 - 品牌智鉴榜
  • 【RPA】拼多多商家后台取数口径
  • 【实战项目】 基于单片机激光打靶语音播报系统的设计与实现
  • 2026年盛世笔特国际文化创意产业集团有限公司排名，市场份额情况究竟如何？ - 工业品牌热点
  • 9 款 AI 写论文哪个好？实测封神！宏智树 AI 凭硬核实力稳坐头把交椅
  • 【实战项目】 基于DSP新型电能质量监测装置的研究
  • Spring Boot之@Transactional注解实践
  • 2026年聚乙二醇6000粉末厂家权威推荐榜：聚乙二醇6000粉末、聚乙二醇8000、聚乙二醇8000粉末、聚乙二醇10000粉末选择指南 - 优质品牌商家
  • 想入行网络安全？这份零基础入门指南，帮你避开90%的常见学习误区。
  • 【实战项目】 基于Flutter的新闻资讯APP开发
  • 2026年水性联线高光光油厂家选哪家？汇华科技用性能与口碑给出答案 - 博客万
  • RAG不是万能的：没有可观测性，你的系统只是在“碰运气”
  • js 并发任务
  • 【实战项目】 边缘计算设备的安全启动
  • EasyGBS算法算力平台：园区全域智能安防监控体系方案设计
  • 2026年诚信的医疗周转箱,周转箱过滤,定制周转箱厂家采购选型指南 - 品牌鉴赏师
  • 寒假做题记录