substr時間復雜度O（N），不能一遍遍找，會超時??

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int N=5e5+10;
map<string,int>mp;
vector<string>v[N];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;string s1,s2;cin>>s1>>s2;mp.clear();string ss;for(int i=0;i<=n;i++){ss+="1";}for(int i=0;i<n;i++){string x=s1[0]+s1.substr(1,i)+s2.substr(i);mp[x]++;//out<<s1.substr(0,i)<<" "<<s2.substr(i)<<endl;if(x<ss) ss=x;}cout<<ss<<endl<<mp[ss]<<endl;}return 0;
}

?

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int N=5e5+10;
map<string,int>mp;
vector<string>v[N];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;string s1,s2;cin>>s1>>s2;string x=s1+s2[n-1];int num=n-1;int flag=0;//substr時間復雜度O(n) 不可一一查詢會超時 for(int i=0;i<n;i++){//找到這個點時就是最佳的拐點 if(s1[i]=='1'&&s2[i-1]=='0'){x=s1.substr(0,i)+s2.substr(i-1);num=i-1;break;}}int cnt=1;for(int j=num;;j--){//倒著走不相等 就不可以了 如果相等說明向下向右都可以即++ 一定是連續的交叉相等//一旦出現不相等 就結束 即方案數 if(s1[j]!=s2[j-1]) break;cnt++;}cout<<x<<endl<<cnt<<endl;}return 0;
}

?DP

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int N=5e5+10;
map<string,int>mp;
vector<string>v[N];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;int arr[2][n];int dp[2][n];for(int i=0;i<=1;i++){string s;cin>>s;for(int j=0;j<n;j++){arr[i][j]=s[j]-'0';//首先預處理 dp[i][j]=0;//dp值預處理 }}dp[0][0]=1;//初始點唯一，一個方案 string ans;ans+=(char)(arr[0][0]+'0');//然后初始點也要在路徑字符串上算上 for(int i=0;i<=n-1;i++)//總共移動步數 {int tmp=1;//第一部分 看后面能不能轉移到0 for(int j=0;j<=1;j++)//向下幾次 {//枚舉當前可能的點 走不了 不可能轉移次數大于移動次數if(j>i) continue; int x=j,y=i-j;//找出枚舉的點 if(dp[x][y]==0) continue;//如果這個點不能被走到 就continue if(x==0)//否則能向下 {if(arr[x+1][y]==0)//看向下能不能走到0 {tmp=0;}}if(y<=n-2)//能向右 {if(arr[x][y+1]==0){tmp=0;//看向右能不能走到0}}}//把目前添加的字符添加進去 if(tmp==0) ans+='0';else ans+='1';//第二部分，我們再把應該轉移的去轉移一下 for(int j=0;j<=1;j++){if(j>i) continue;int x=j ,y=i-j;if(dp[x][y]==0)continue;if(x==0){if(arr[x+1][y]==tmp){dp[x+1][y]+=dp[x][y];}}if(y<=n-2){if(arr[x][y+1]==tmp){dp[x][y+1]+=dp[x][y];}}}} cout<<ans<<endl;cout<<dp[1][n-1]<<endl;}return 0;
}

?

?