#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 22;
int n,sum; //sum记录答案
int a[2]={0,1};
bool st[N]; //st[i]=true代表第i位数是1，否则不是1
void dfs(int u){
if(u==n){ //dfs到终点，答案++
sum++;
return;
}
for(int i=0;i<2;i++){ //依次判断第u位选0还是1
if(u==0){ //特判第0位
if(i==1){ //是1就直接选
st[u]=true; //标记该位为1
dfs(u+1); //递归下一位
st[u]=false; //回溯
}
else dfs(u+1); //是0就直接选并递归下一位
}
else if(i==1){ //不是第0位且判断是否选1
if(!st[u-1]){ //若前一位不是1则当前位可以为1
st[u]=true;
dfs(u+1);
st[u]=false;
}
}
else dfs(u+1); //是0就直接选
}
}
int main(){
cin>>n;
dfs(0); //从第0位开始递归
cout<<sum;
return 0;
}
将每个字母转换为数字后加入小根堆，最小的那个数肯定要选，然后依次取堆顶，若减去上一个数大于等于2就加入答案，并将上一个数更新为当前数，并将其弹出
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
int n,k;
while(cin>>n>>k){
string s;
cin>>s;
priority_queue<int,vector<int>,greater<int>> q; //小根堆
for(int i=0;i<s.size();i++) q.push(s[i]-'a'+1); //转换为数字
int sum=q.top(),last=q.top(); //sum记录答案，last记录上一个数
k--; //最小的那个数肯定在答案
q.pop(); //弹出
while(q.size()&&k!=0){ //堆空或选满k个数就退出
if(q.top()-last>=2){
sum+=q.top(); //加入答案中
k--;
last=q.top(); //更新last为当前数
q.pop();
}
else q.pop();
}
if(k!=0) puts("-1"); //没选满
else cout<<sum<<endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s1;
char s[4]={'E','A','S','Y'};
bool dfs(int u,int i){
int x=s1.find(s[u],i); //从字符串s1的下标为i的位置开始找s[u]
if(x==-1) return false; //找不到就false
else{ //找到就从当前位置找下一个字母
if(u==3) return true; //边界
return dfs(u+1,x);
}
}
int main(){
while(cin>>s1){
if(dfs(0,0)) puts("easy");
else puts("difficult");
}
return 0;
}
活动打卡代码
AcWing 895. 最长上升子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int dp[N]; //dp[i]表示以a[i]为结尾的最长上升子序列
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
/*
dp[i]的倒数第二个数可以是dp[1],dp[2]...dp[i-1]，也可以没有倒数第二个数
即dp[i]只包含a[i]，即长度为1
若倒数第二个数为a[k]，且a[k]<a[i]，则有dp[i]=max(dp[k]+1,dp[i])
dp[k]即以a[k]为结尾的最长上升子序列，dp[k]+1即将a[i]加入子序列中
即：dp[i]=max(dp[1]+1,dp[2]+1,...,dp[i-1]+1,dp[i])
*/
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++)
if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,dp[i]);
cout<<res;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
string s1,s2,a,b;
cin>>s1>>s2;
if(s1.size()<s2.size()) a=s1,b=s2;
else a=s2,b=s1;
reverse(a.begin(),a.end()); //反转字符串以保证找到的第一个即使最后一个
bool flag=false;
for(int i=a.size();i>=1;i--){
if(flag) break;
for(int j=0;j<=a.size()-i;j++){
string c=a.substr(j,i);
reverse(c.begin(),c.end());
if(b.find(c)!=-1){
cout<<i<<endl<<c<<endl;
flag=true;
break;
}
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
map<string,int> m;
m["zero"]=0,m["one"]=1,m["two"]=2,m["three"]=3,m["four"]=4;
m["five"]=5,m["six"]=6,m["seven"]=7,m["eight"]=8,m["nine"]=9;
string s;
while(getline(cin,s)){
int i=s.find('+'),j=s.find('=');
string s1=s.substr(0,i-1),s2=s.substr(i+2,j-i-3);
if(s1=="zero"&&s2=="zero") break;
int x=s1.find(' '),y=s2.find(' ');
int a,b;
if(x==-1) a=m[s1];
else{
string s3=s1.substr(0,x);
string s4=s1.substr(x+1);
a=m[s3]*10+m[s4];
}
if(y==-1) b=m[s2];
else{
string s3=s2.substr(0,y);
string s4=s2.substr(y+1);
b=m[s3]*10+m[s4];
}
cout<<a+b<<endl;
}
return 0;
}
经典的BFS问题
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 11;
char g[N][N];
bool st[N][N];
int w,h;
int bfs(PII start,int X){
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //上、右、下、左
queue<PII> q;
q.push(start);
st[start.x][start.y]=true;
int res=1;
while(q.size()){
auto t=q.front();
q.pop();
int a=t.x+dx[X],b=t.y+dy[X];
if(a<0||a>=w||b<0||b>=h||st[a][b]||g[a][b]=='*'){
X++; //旋转90°
if(X==4) X=0; //特判
a=t.x+dx[X],b=t.y+dy[X];
if(a<0||a>=w||b<0||b>=h||st[a][b]||g[a][b]=='*') return res;
q.push({a,b});
st[a][b]=true;
res++;
}
else{
q.push({a,b});
st[a][b]=true;
res++;
}
}
return res;
}
int main(){
while(cin>>w>>h){
int X;
memset(st,0,sizeof st);
PII start;
for(int i=0;i<w;i++) cin>>g[i];
for(int i=0;i<w;i++)
for(int j=0;j<h;j++){
if(isalpha(g[i][j])){
start={i,j};
if(g[i][j]=='U') X=0; //初始移动方向
if(g[i][j]=='R') X=1;
if(g[i][j]=='D') X=2;
if(g[i][j]=='L') X=3;
break;
}
}
cout<<bfs(start,X)<<endl;
}
return 0;
}
/*
dp[i]表示以下标i结尾的最大连续子序列，l[i]表示以下标i结尾的最大连续子序列的左端点的下标
dp[i]只与dp[i-1]与a[i]有关
若dp[i-1]<0，则dp[i-1]+a[i]肯定小于a[i]，此时dp[i]=a[i]
若dp[i-1]非负，则dp[i-1]+a[i]>=a[i]，此时dp[i]=dp[i-1]+a[i]，因为要求左右端点都最小
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp[N],l[N];
int main(){
int n;
while(cin>>n){
int max=-1,left,right;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(i==0) dp[i]=x,l[i]=i;
else{
if(dp[i-1]<0) dp[i]=x,l[i]=i;
else dp[i]=dp[i-1]+x,l[i]=l[i-1];
}
if(dp[i]>max) max=dp[i],left=l[i],right=i;
}
if(max<0) puts("0 0 0");
else cout<<max<<" "<<left<<" "<<right<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
char a[N][N];
bool col[N],dg[N],udg[N];
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!='Q') cout<<'.';
else cout<<a[i][j];
}
cout<<endl;
}
cout<<endl;
}
for(int i=0;i<n;i++)
if(!col[i]&&!dg[u+i]&&!udg[u-i+8]){
a[u][i]='Q';
col[i]=dg[u+i]=udg[u-i+8]=true;
dfs(u+1);
a[u][i]='.';
col[i]=dg[u+i]=udg[u-i+8]=false;
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}
活动打卡代码
AcWing 3472. 八皇后
如何标识正对角线：正对角线的表达式为y=-x+b，每个正对角线的唯一标识为b，b=x+y，即行号就+列号
同理，副对角线为y=x+b，b=y-x，以免造成为负数，再加上8
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
bool col[N],dg[N],udg[N];
int sum,cnt;
char path[8];
vector<int> v;
void dfs(int u){
if(u==8){
v.push_back(stoi(path));
return;
}
for(int i=0;i<8;i++)
if(!col[i] && !dg[u+i] && !udg[u-i+8]){
path[u]=i+1+'0';
col[i]=dg[u+i]=udg[u-i+8]=true;
dfs(u+1);
col[i]=dg[u+i]=udg[u-i+8]=false;
}
}
int main(){
dfs(0);
int n;
cin>>n;
while(n--){
int b;
cin>>b;
cout<<v[b-1]<<endl;
}
return 0;
}
