C语言算法训练第八天，如何为？
摘要：C++算法训练第八天 以下为牛客挑战 今日收获 学习到了ksm的写法 int ksm(int p,int q,int mod){ int result=1; p=p%mod; while (q&a
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)
解题代码
#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)
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)
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)
示例1
2
6
1 2 2 1 3 1
5
1 1 2 2 4
6
2
我们看到这个和顺序没有关系，我们可以直接先排序。然后统计个数，因为这个是必须按照1-i这样的，所以我们对于这一次，就是选出两个i的数方法，去和上次的x，再加就行了
解题代码
#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])/2
for(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)
2
0?1
????
0
8
思维题。
题目要我们求相同的对数，那我们直接反过来求不同的对数，然后用1-n一共n-1对减去相同的对数就可以判断不同的对数的奇偶性。
就是s[i]!=s[i+1];
这个不同可以用异或来
s[i]^s[i+1],如果相同直接是0，如果不同不为0；
然后我们要去相加这些数。
结果相加，看看不同的奇偶性。
这个可以化简为，
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种情况讨论就行了
没有？全是其他的。直接判断一下就行了。
有一个那肯定可以组成一个
有两个可以组成两个。
最后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)
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;
}