P1321 单词覆盖还原 简单思路 字符串
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#define ll long long
using namespace std;
string s;
int cnta, cntb;
int main(){
cin>>s;
int len = s.length();
for(int i = 0; i < len; i++){
if(s[i] == 'b' || s[i+1] == 'o' || s[i+2] == 'y')
cnta++;
if(s[i] == 'g' || s[i+1] == 'i' || s[i+2] == 'r' || s[i+3] == 'l')
cntb++;
}
cout<<cnta<<endl;
cout<<cntb<<endl;
return 0;
}
P1885 Moo 递归
// 3
// 3 + 1 + 3 + 3 = 10
// 3 + 1 + 3 + 3 +（1+4）+ 3 + 1 + 3 + 3 = 15
// 3 + 1 + 3 + 3 +（1+4）+ 3 + 1 + 3 + 3 + （1+5） + 3 + 1 + 3 + 3 +（1+4）+ 3 + 1 + 3 + 3
// 15 + 6 + 15 = 36
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int s[30];
char f(int n, int t){
if(t == 0){
if(n == 1) return 'm';
else return 'o';
}
int la = (s[t] - (1 + t + 2))/2 ;
int lb = la + (1 + t + 2);
if(n == la + 1) return 'm';
else if(n > la+1 && n <= lb) return 'o';
else if(n > lb) return f(n - lb, t-1);
else return f(n, t-1);
}
int main(){
int n,t; scanf("%d",&n);
s[0] = 3;
for(int i = 1; ;i++){
s[i] = s[i-1] * 2 + 1 + i + 2;
if(s[i] >= n){//s[i] >= 1000000000
t = i; break;
}
}
// cout<<t<<endl;
cout<<f(n, t)<<endl;
return 0;
}
单词接龙 字符串+dfs
#include<bits/stdc++.h>
using namespace std;
char a[105][105];
int n,side[105][105],vis[105],mx=-2147483647;
void h(int i,int j){
int leni=strlen(a[i]+1);
int lenj=strlen(a[j]+1);
int l=0,len=leni<lenj?leni:lenj;
while(l<=len){
l++; int k;
for(k=1;k<=l;k++){//
if(a[i][leni-l+k]!=a[j][k]) break;
}
if(k==l+1){//
side[i][j]=lenj-l;
// cout<<"hhh: "<<a[i]+1<<" "<<a[j]+1<<" "<<side[i][j]<<endl;
break;
}
}
if(i>j) h(j,i);
}
void dfs(int x,int len){
mx=max(len, mx);
for(int i=1;i<=n;i++){//
if(side[x][i]>0&&vis[i]<2){//一遍没用过，或者用过一遍，可以再用一次
vis[i]++;
dfs(i,len+side[x][i]);
vis[i]--;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n+1;i++){
cin>>a[i]+1;
for(int j=1;j<=i;j++){
h(i,j);
}
}
dfs(n+1,1);
cout<<mx;
return 0;
}