C语言算法训练第九天，如何针对进行优化？
摘要：C++算法训练第九天 以下为牛客挑战 今日收获 学到了三元组，就是当我们从一大堆数中选着3个数的方案。就是不一样位置的数如果相同，但是角标不一样也算不一样的。 常规3层for循环 而三元组 》 prev2
C++算法训练第九天
以下为牛客挑战
今日收获
学到了三元组，就是当我们从一大堆数中选着3个数的方案。就是不一样位置的数如果相同，但是角标不一样也算不一样的。
常规3层for循环
而三元组---》
prev2相当于前面所组成的二元组的个数，prev表示前面的数的和，an+前面组合的数x单前的数。--》三元组。cnt[i]i的个数
ll prev = 0, prev2 = 0;
REP(i, 26) {
ans += prev2 * cnt[i];
prev2 += prev * cnt[i];
prev += cnt[i];
}
对BFS可用魔法的更深入一层。
牛客周赛 Round 121
幽幽子想吃东西
A-幽幽子想吃东西_牛客周赛 Round 121 (nowcoder.com)
1 2 3 4
4
解题代码
#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 a,b,c,n;
cin>>a>>b>>c>>n;
int m=a*n;
if(n<=b){
cout<<m-c;
}else{
cout<<m;
}
return 0;
}
米斯蒂娅不想被吃掉
枚举
B-米斯蒂娅不想被吃掉_牛客周赛 Round 121 (nowcoder.com)
2
3 1
2 0 1
3 2
6 0 1
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 n,x;
cin>>n>>x;
vector<int>s(n+1);
for(int i=1;i<=n;i++){
cin>>s[i];
}
for(int i=1;i<=n;i++){
if(s[i-1]<x&&s[i-1]>=0){
int m=x-s[i-1];
s[i]-=m;
}
if(s[i]<0){
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;
}
三妖精say subsequence ！！！
递推三元组。
C-三妖精say subsequence ！！！_牛客周赛 Round 121 (nowcoder.com)
3
abc
6
因为是字母所以我们可以直接去统计然后3个循环去遍历，按照顺序的三元组，然后我们继续去×6，因为排列组合，3个排成6就行了。
解题代码
#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];
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
vector<int>m(26,0);
cin>>n>>s;
for(int i=0;i<n;i++){
m[s[i]-'a']++;
}
int ans=0;
for(int i=0;i<=23;i++){
for(int j=i+1;j<=24;j++){
for(int k=j+1;k<=25;k++){
ans+=((m[i]*m[j])%mod*m[k])%mod;
ans%=mod;
}
}
}
cout<<ans*6%mod<<endl;
return 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];
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
vector<int>m(26,0);
cin>>n>>s;
for(int i=0;i<n;i++){
m[s[i]-'a']++;
}
int ans=0;
int prev=0,prev2=0;
for(int i=0;i<26;i++){
ans+=prev2*m[i];
prev2+=prev*m[i];
prev+=m[i];
}
cout<<ans*6%mod<<endl;
return 0;
}
恋恋的01串大冒险
模拟
D-恋恋的01串大冒险_牛客周赛 Round 121 (nowcoder.com)
3 1
000
0 1 2 3
这个题是这样的，做法就是模拟
解题代码
#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,k;
string s;
cin>>n>>k>>s;
vector<int>cnt(n+1,0);
s=" "+s;
int i=1;
int cur=0;
int used=0;
while (i<=n){
if(s[i]=='1'){
while (i<=n&&s[i]=='1'){
i++;
}
cur=0;
}else{
cur++;
if(cur>=k){
cnt[used]=i-1;
used++;
cur=0;
}
i++;
}
if(i>n){
cnt[used]=i-1;
break;
}
}
for(int i=1;i<=n;i++){
cnt[i]=max(cnt[i-1],cnt[i]);
}
for(int i=0;i<=n;i++){
cout<<cnt[i]<<" ";
}
return 0;
}
the world
BFS最短路加可用魔法
E-the world_牛客周赛 Round 121 (nowcoder.com)
1 4 1
1 2 1 3
3
这个题是bfs的想法
我们可以定义一个数组
int dp[1005][1005][2][2];
前两个表示位置，第3个表示现在是奇数时间还是偶数，最后一个是有没有用魔法
我们发现用了魔法和没有用魔法也就第一秒不同，只是把原来的下一步调换一下位置就行了
没有魔法
if(g[x1][y1]==1&&(list%2)==0){ continue;}
if(g[x1][y1]==2&&(list)%2==1){ continue;}
有魔法
if(g[x1][y1]==1&&(list%2)==1){ continue;}
if(g[x1][y1]==2&&(list)%2==0){ continue;}
转移
if(dp[x1][y1][list%2^1][used]==-1){
q.push({x1,y1,list+1,1});
}
list%2^1，表示奇变偶，偶变奇。
然后写的去就行了
先初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j][0][0]=-1;
dp[i][j][0][1]=-1;
dp[i][j][1][0]=-1;
dp[i][j][1][1]=-1;
}
}
代码解释
#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 dp[1005][1005][2][2];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct node{
int x,y,list,used;
}Node;
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>g(n+1,vector<int>(m+1));
for(int i=0,x1,y1,x2,y2;i<k;i++){
cin>>x1>>y1>>x2>>y2;
g[x1][y1]|=1;
g[x2][y2]|=2;
}//初始化宿主
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j][0][0]=-1;
dp[i][j][0][1]=-1;
dp[i][j][1][0]=-1;
dp[i][j][1][1]=-1;
}
}
queue<node>q;
q.push({1,1,1,0});
while(q.size()){
auto [x,y,list,used]=q.front();
q.pop();
if(dp[x][y][list%2][used]!=-1)continue;
dp[x][y][list%2][used]=list;
for(int i=0;i<4;i++){
int x1=x+dx[i];
int y1=y+dy[i];
if(x1<1||y1<1||x1>n||y1>m||g[x1][y1]==3)continue;
if(g[x1][y1]==1&&(list%2)==0){ continue;}
if(g[x1][y1]==2&&(list)%2==1){ continue;}
if(dp[x1][y1][list%2^1][used]==-1){
q.push({x1,y1,list+1,used});
}
}
if(!used){
for(int i=0;i<4;i++){
int x1=x+dx[i];
int y1=y+dy[i];
if(x1<1||y1<1||x1>n||y1>m||g[x1][y1]==3)continue;
if(g[x1][y1]==1&&(list%2)==1){ continue;}
if(g[x1][y1]==2&&(list)%2==0){ continue;}
if(dp[x1][y1][list%2^1][used]==-1){
q.push({x1,y1,list+1,1});
}
}
}
}
int ans=1e9;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
if(dp[n][m][i][j]==-1){
continue;
}
ans=min(dp[n][m][i][j],ans);
}
}
if(ans>1e8){
ans=0;
}
cout<<ans-1;
return 0;
}