记录
2026-08-12 08:46:18
发布于：浙江
61阅读
0回复
0点赞
第 道青，详细的写了一下，看代码吧。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace syh;
const int maxn=505;//字符串最大长度
const int maxk=105;//最大交换次数
const int inf=0xc0c0c0c0;//负无穷，用与对应memset初始化
int dp[maxn][maxk][maxk][2], n, k, ans=0;
//dp[i][j][z][l]
//i:处理第i个字符
//j:有多少个'j'变为'z'
//z:有多少个'z'变为'j'
//l:第i个字符最终是'j'还是'z'
//dp元素的值:最多有多少个'jz'子串
string s;
int main()
{
memset(dp,0xc0,sizeof dp);//初始化为负无穷
cin>>n>>k>>s;//读入长度、交换次数、字符串
int fir=(s[0]=='j')?0:1;//第1个字符，是'j'就为0，是'z'就为1
if(fir==0)//第一个是'j'
{
dp[1][0][0][0]=0;//不变，j到z为0，z到j为0，当前是j
if(k>=1) dp[1][1][0][1]=0;//'j'变成'z'，j为1，当前是z
}
else//第一个是'z'
{
dp[1][0][0][1]=0;//不变，j到z为0，z到j为0，当前是z
if(k>=1) dp[1][0][1][0]=0;//'z'变成'j'，z为1，当前是j
}
for(int i = 2;i<=n;i++)//从第二个字符开始dp，因为第一个已经处理了
{
int c=(s[i-1]=='j')?0:1;//当前位置原来是什么（'j'还是'z'）
for(int j = 0;j<=k;j++)//枚举j到z的次数
{
for(int z = 0;z<=k;z++)//枚举z到j的次数
{
for(int l = 0;l<=1;l++)//枚举前一个字符最终是什么
{
if(dp[i-1][j][z][l]==inf) continue;//无效状态*
for(int cu = 0;cu<=1;cu++)//枚举当前位置最终变成什么
{
int nj=j, nz=z;//当前j变z的次数和z变j的次数
if(c==0&&cu==1) nj++;//原j变z，次数加一
if(c==1&&cu==0) nz++;//原z变j，次数加一
if(nj>k||nz>k) continue;//某个变化次数超过了规定就跳过，不进入下面的dp
int a=(l==0&&cu==1)?1:0;//判断是否组成'jz'（前面是'j'现在是'z'）
dp[i][nj][nz][cu]=max(dp[i][nj][nz][cu],dp[i-1][j][z][l]+a);//更新dp值*
}
}
}
}
}
for(int i = 0;i<=k;i++)//枚举j到z与z到j相等的情况*
{
for(int l = 0;l<=1;l++)//枚举最后一个字符（两种可能）*
{
ans=max(ans,dp[n][i][i][l]);//只有j与z相等才是合法的交换*
}
}
cout<<max(0,ans);//答案至少为0，打擂输出
}
//无效状态*:值为inf的说明没有被计算过，出现不了这种状态所以要跳过
//更新dp值*:打擂更新前i-1个字符的最优值加上现在的子串数与原先的最优数量的最大值作为现在的最优值
//枚举j到z与z到j相等的情况*:因为交换必须成对出现，所以j到z的数量必须为z到j的数量
//枚举最后一个字符（两种可能）*:因为经过交换后最后一个字符的值可能发生变化，所以要枚举所有情况（j或z）才能更新最大值
//只有j与z相等才是合法的交换*:因为有两种情况，所以要选择最后为j或z的最大值，i=i是因为j到z的次数与z到j的次数一定相等，dp[n][][][]是因为已经处理了整个字符串，变化到第n个才能知道最终的答案
#include <iostream>
#include <cstring>//用于memset清空数组
using namespace syh;
const int maxl=3000005;//Trie树最多要有3e6个节点
int son[maxl][65];//son[节点编号][字符索引]=子节点编号（一共3e6个编号，10个数字+52(26个字母大小写)=62个索引）
//son[0]=子0、子1、子2...(根结点的所有子节点)
//son[1]=子0、子1、子2...(结点1的所有子节点)
int cnt[maxl];//cnt[u]表示经过u节点的字符串数量（多少字符串以该前缀开头）
int idx, max_u=0;//idx为当前最大节点编号，max_u为所有测试组里最大的idx值（用于优化内存）
inline int getid(char c)//字符映射函数（映射到完整的0-61区间）
{
if(c>='a'&&c<='z') return c-'a';//小写字符是最前的编号（1-25)
else if(c>='A'&&c<='Z') return c-'A'+26;//大写字符编号为26-51
else return c-'0'+52;//数字是最后一些编号（52-61）
}
void insert(const string &s)//插入函数
{
int u=0;//当前节点（从根结点开始）
for(char c:s)
{
int ch=getid(c);//将字符转换成对应的索引
if(!son[u][ch])//如果当前没有这个子节点
{
son[u][ch]=++idx;//创建新节点（idx先自增再使用，因为根结点什么都不存）
}
u=son[u][ch];//移动到当前的节点
cnt[u]++;//经过当前节点的字符串加一（cnt[0]始终为0，因为根结点不存）
}
}
int query(const string &s)//查询函数
{
int u=0;//从根结点开始查询
for(char c:s)//遍历字符串的每一个字符
{
int ch=getid(c);//将字符转为对应的索引
if(!son[u][ch]) return 0;//没有任何字符串以这个前缀开头就退出
u=son[u][ch];//移动到这个子节点
}
return cnt[u];//返回有多少个模式串以s为前缀
}
int main()
{
//输入输出优化
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n, q;//n为模式串个数，q为询问次数
cin>>n>>q;
//max_u永远覆盖要清空的范围（因为是idx(最大节点)的最大值）
for(int i = 0;i<=max_u;i++)//从根节点清空到现在最大的节点编号（根结点里有所有单字符的"目录"所以要清空）
{
memset(son[i],0,sizeof son[i]);//清空节点i的所有子节点指针（清空所有子节点的内容）
cnt[i]=0;//清空该节点的计数
}
idx=0;//重置节点计数器
for(int i = 1;i<=n;i++)
{
string s;
cin>>s;
insert(s);//插入模式串
}
max_u=max(max_u,idx);//更新一下最大值
for(int i = 1;i<=q;i++)
{
string s;
cin>>s;
cout<<query(s)<<"\n";//回答查询
}
}
}
P1463 [POI 2001 R1 / ZJOI2006 / HAOI2007] 反素数
//找1-n里多个约数最多的数里最小的数
#include <iostream>
using namespace std;
typedef long long ll;
ll n, bv;//bv为当前最优答案
int bc;//最优答案的约数个数
int prime[10]={2,3,5,7,11,13,17,19,23};//只用的上9个质数
//pos为当前枚举的第pos个质数
//last为上个质数用的指数，当前的指数小于等于last
//val 当前的数
//cnt val的约数个数
void dfs(int pos,int last,ll val,int cnt)
{
if(cnt>bc||(cnt==bc&&val<bv))//更新最优解*
{
bc=cnt;
bv=val;
}
if(pos>=9) return;//质数用完了，回溯
ll p=prime[pos];
ll now=val;
for(int i = 1;i<=last;i++)//选取指数（取多少次幂）
{
if(now>n/p) break;//超过n了不合法，直接剪枝
now*=p;//逐步增加指数
dfs(pos+1,i,now,cnt*(i+1));//下一个指数的指数上限为i（下一个质数的）
}
}
signed main()
{
cin>>n;
bv=1;
bc=1;
//初始数字1，约数个数1
dfs(0,30,1,1);//指数上限30
cout<<bv;
}
//更新最优解*:cnt>bc找到约数更多的数必然更新，cnt==bc&&val<bv虽然约数个数相同但数字更小也更新
这个才是第 道青，因为涂色升蓝了
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
const long long im=1e18;
vector<pair<int,int>> g[200005];
long long dis[100005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin>>n>>m>>s;
for(int i = 1;i<=n;i++) dis[i]=im;
dis[s]=0;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].emplace_back(v,w);
}
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> h;
h.emplace(0,s);
while(!h.empty())
{
long long d=h.top().first;
int u=h.top().second;
h.pop();
if(d>dis[u]) continue;
for(auto &e:g[u])
{
int v=e.first;
int w=e.second;
if(dis[v]>dis[u]+w&&dis[u]!=INT_MAX)
{
dis[v]=dis[u]+w;
h.emplace(dis[v],v);
}
}
}
for(int i = 1;i<=n;i++) cout<<dis[i]<<" ";
}
我之前怎么连数组开小RE都发现不了:(
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n, m;
ll b, f[10005], l=inf, r, ans;
vector<pair<int,ll>> g[10005];//邻接表，pair<v,边权c>
bool check(ll mid)
{
if(f[1]>mid||f[n]>mid) return false;//起点终点必须能走
vector<ll> dis(n+1,inf);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;//无负边权用dijkstra
dis[1]=0;
q.emplace(0,1);
while(!q.empty())
{
pair<ll,int> cur=q.top();
q.pop();
ll d=cur.first;
int u=cur.second;
if(d>dis[u]) continue;//不是最短路就不要
for(auto &edg:g[u])
{
int v=edg.first;
ll c=edg.second;
if(f[v]>mid) continue;//超过最大值不让走
if(dis[v]>d+c)
{
dis[v]=d+c;//更新最短路
q.emplace(dis[v],v);
}
}
}
return dis[n]<=b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
ans=-1;
cin>>n>>m>>b;
for(int i = 1;i<=n;i++)
{
cin>>f[i];
l=min(l,f[i]);
r=max(r,f[i]);
}
for(int i = 1;i<=m;i++)
{
int a, b;
ll c;
cin>>a>>b>>c;
//双向边
g[a].emplace_back(b,c);
g[b].emplace_back(a,c);
}
while(l<=r)//二分答案
{
ll mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans==-1) cout<<"AFK";
else cout<<ans;
}
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=500005;
const int LOG=20;
vector<int> g[maxn];//邻接表存树
int fa[maxn][LOG];
//fa[u][j]:节点u向上跳2^j步到达的祖先
//fa[u][0]:节点u的父节点
int dep[maxn];//节点u的深度
int n, m, rt;//点数，询问数，根
void bfs()
{
//bfs遍历整棵树，求出每个点的父节点fa[u][0]和深度dep[u]
//dp填充整张倍增祖先表fa[u][j]
queue<int> q;
q.push(rt);
fa[rt][0]=0;//根结点没有父亲
dep[rt]=1;//根结点深度为1
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u])
{
if(v!=fa[u][0])//无向图不走回根结点
{
fa[v][0]=u;
dep[v]=dep[u]+1;
q.push(v);
}
}
}
//倍增dp填表
//fa[i][j]=fa[fa[i][j-1]][j-1]
//向上跳2^j步，先跳2^j-1步，再跳2^j-1步
//顺序：先小j后大j
for(int j = 1;j<LOG;j++)
{
for(int i = 1;i<=n;i++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);//保证x是更深的点，如果不是就交换
//阶段1：把x拉到y的深度
for(int i = LOG-1;i>=0;i--)
{
if(dep[fa[x][i]]>=dep[y])//跳完后深度大于等于y的深度就跳
{
x=fa[x][i];
}
}
if(x==y) return y;//拉平深度后如果两值相等则说明y为x的祖先，返回y
//阶段2：x、y一起向上跳，但不能跳到目标值的上面
for(int i = LOG-1;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])//祖先不一样可以跳，更接近LCA且不会越过
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];//结束时两值都在LCA的直系子节点上，返回父节点即可
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>rt;
for(int i = 1;i<n;i++)//建无向树
{
int x, y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
bfs();//预处理深度、倍增数组
for(int i = 1;i<=m;i++)//处理m次询问
{
int a, b;
cin>>a>>b;
cout<<lca(a,b)<<'\n';
}
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long inf=1e18;
vector<pair<int,int>> g[50005];
long long dis[50005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin>>n>>m;
for(int i = 1;i<=n;i++) dis[i]=-inf;
dis[1]=0;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].emplace_back(v,w);
}
priority_queue<pair<long long,int>,vector<pair<long long,int>>> h;
h.emplace(0,1);
while(!h.empty())
{
long long d=h.top().first;
int u=h.top().second;
h.pop();
if(d<dis[u]) continue;
for(auto &e:g[u])
{
int v=e.first;
int w=e.second;
if(dis[v]<dis[u]+w&&dis[u]!=-inf)
{
dis[v]=dis[u]+w;
h.emplace(dis[v],v);
}
}
}
if(dis[n]!=-inf) cout<<dis[n];
else cout<<-1;
}
这个很像最大生成树的思想，但是这个做法大概是特性的力量。
P13085 [SCOI2009] windy 数（加强版）
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[20][12];
vector<ll> num;
ll dfs(ll pos,ll pre,bool limit,bool lead)
{
if(pos==num.size())
{
return lead==1?0:1;
}
if(!limit&&!lead&&dp[pos][pre]!=-1) return dp[pos][pre];
ll up=limit==1?num[pos]:9, res=0;
for(ll i = 0;i<=up;i++)
{
bool nlimit=limit&&(i==up);
bool nlead=lead&&(i==0);
if(nlead)
{
res+=dfs(pos+1,11,nlimit,nlead);
}
else if(lead)
{
res+=dfs(pos+1,i,nlimit,nlead);
}
else
{
if(abs(i-pre)>=2)
{
res+=dfs(pos+1,i,nlimit,nlead);
}
}
}
if(!limit&&!lead)
{
dp[pos][pre]=res;
}
return res;
}
ll sum(ll x)
{
if(x==0) return 0;
num.clear();
memset(dp,-1,sizeof dp);
while(x>0)
{
num.push_back(x%10);
x/=10;
}
reverse(num.begin(),num.end());
return dfs(0,11,true,true);
}
int main()
{
ll a, b;
cin>>a>>b;
cout<<sum(b)-sum(a-1);
}
青++。
感觉以后都可以出个专项讲这种变式题了
#include <iostream>
#include <bitset>
using namespace std;
bitset<3005> a[3005];
long long n, ans;
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
string s;
cin>>s;
for(int j = i;j<n;j++) a[i][j+1]=s[j]-'0';//存上三角，保证最小边只被枚举一次，避免重复
}
for(int i = 1;i<=n;i++)
{
for(int j = i+1;j<=n;j++)//每个点对只被枚举一次
{
if(a[i][j]) ans+=(a[i]&a[j]).count();//只有连接i与j的k才是1，用count统计k的总个数，前提是i与j相连
}
}
cout<<ans;
}
不是题解不是口胡是记录！！
有帮助，赞一个