记录acwing蓝桥杯每日一题
3956.截断数组
思路：好吧从j循环那边我就有点想不到，y总的思路就是固定第二个分割点，枚举第一个分割点的位置
3729.改变数组元素
思路：主要就是差分，记录一下差分模板，差分可以用来处理对某一区间的数据同时加上或者减去一个数
1460.我在哪？
先放上一个暴力算法（遇到估计我也只能暴力了，能拿几分是几分了）
y总的优化思路：使用二分，且用哈希表
很好哈希表又是我还不会的东西
unordered_set<string> hash//定义一个哈希表
string类型中substr(i,j)函数可以截取区间i-j的字符串
1497.树的遍历
思路：把后序中序分为三段：根节点、左子树、右子树
感觉数据结构经常用到这样的递归，记住是怎么做的吧orz
1249.亲戚
终于有一道我会做的了，但是没想到习惯用的cin cout会被判超时（果然还是要用scanf吗）
2058. 笨拙的手指
#include <bits/stdc++.h>
using namespace std;
const int N=1e9;
int base(string s,int a){
int ans=0;
for (int i=0;i<s.size();i++){
ans=a*ans+s[i]-'0';
}
return ans;
}
int main(){
string x,y;
cin>>x>>y;
unordered_set<int> hash;
for (int i=0;i<x.size();i++){
string s=x;
s[i]^=1;
if(s.size()>1&&s[0]=='0') continue;
hash.insert(base(s,2));
}
for (int i=0;i<y.size();i++){
for (int j=0;j<3;j++){
if(y[i]-'0'!=j){
string s=y;
s[i]=j+'0';
if(s.size()>1&&s[0]=='0') continue;
int n=base(s,3);
if(hash.count(n))
cout<<n<<endl;
}
}
}
return 0;
}思路：需要查找的时候就考虑用哈希表的insert和count函数，然后进制转换的模板也背一下
3485. 最大异或和（每日一题
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=31e5+10;//最多有n*31
int p[N][35],ct[N],idx;//ct[n]的作用是标记滑动窗口内0，1的数量
int sum[100010];//sum[i]存前i个数的异或和
void insertt(int u,int c){
int t=0;
for(int i=30;i>=0;i--){
int x=u>>i&1;
if(!p[t][x]){
p[t][x]=++idx;
}
t=p[t][x];
ct[t]+=c;//标记这里（有或删除）一个数可以达到该位置
}
}
int query(int u){
int t=0;
int res=u;
for(int i=30;i>=0;i--){
int x=u>>i&1;
if(ct[p[t][!x]]>0){//当x对面的那个数！x存在时(0,1)
x=(x+1)%2;//x就变成另外一个数 !x
}
res^=x<<i;
t=p[t][x];
}
return res;
}
int main(){
cin>>n>>m;
int t;
for(int i=1;i<=n;i++){
scanf("%d",&t);
sum[i]=sum[i-1]^t;//sum[i]表示前i个数的^
}
insertt(0,1);//插入0，是为了方便前m个数进行异或得出的答案可以是它本身的值
int res=0;//求最大值
for(int i=1;i<=n;i++){
if(i>m) insertt(sum[i-m-1],-1);//将滑动窗口外的数除去，这时就要修改ct，故-1
res=max(res,query(sum[i]));//在滑动窗口内求最大值
insertt(sum[i],1);//求完后记得插入该值，方便后面的值进行异或
}
cout<<res;
return 0;
}
思路：目前感觉最难的一道题，前缀和是真的没想到，但是是不是异或就适合用trie数组，也是模板背一下（估计遇到也不会的）
1562. 微博转发
#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=100010;
int n,L;
int e[M],h[N],ne[M],idx;
bool st[N];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int bfs(int start){
queue<int> q;
memset(st,0,sizeof st);
q.push(start);
st[start]=true;
int res=0;
for (int i=0;i<L;i++){
int sz=q.size();
while(sz--){
int t=q.front();
q.pop();
for (int j=h[t];~j;j=ne[j]){
int x=e[j];
if(!st[x]){
q.push(x);
res++;
st[x]=true;
}
}
}
}
return res;
}
int main(){
cin>>n>>L;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int cnt;cin>>cnt;
while(cnt--){
int x;cin>>x;
add(x,i);
}
}
int m;
cin>>m;
while(m--){
int x;cin>>x;
cout<<bfs(x)<<endl;
}
return 0;
}思路：add函数是模板，背一下，以及我老是忘记memset，其实bfs也是模板
3502.不同路径数
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int a[N][N];
string str;
int n,m,k;
unordered_set<int> S;
void dfs(int i,int j,int x,int num){
if(x==k){
S.insert(num);
}
else {
if(0<=i&&i<n&&0<=j+1&&j+1<m)
dfs(i,j+1,x+1,num*10+a[i][j+1]);
if(0<=i&&i<n&&0<=j-1&&j-1<m)
dfs(i,j-1,x+1,num*10+a[i][j-1]);
if(0<=i+1&&i+1<n&&0<=j&&j<m)
dfs(i+1,j,x+1,num*10+a[i+1][j]);
if(0<=i-1&&i-1<n&&0<=j&&j<m)
dfs(i-1,j,x+1,num*10+a[i-1][j]);
}
}
int main(){
cin>>n>>m>>k;
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
cin>>a[i][j];
}
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
dfs(i,j,0,a[i][j]);
}
}
cout<<S.size();
return 0;
}难的又是一个自己做出来的题，提醒一下不要直接用hash可能会重名，换一个名字
1488.最短距离
#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=N*3;
typedef pair<int,int> PII;
int e[M],h[N],ne[M],w[M],idx;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,0});
dist[0]=0;
while(heap.size()){
//当堆栈中有数时
auto t=heap.top();
heap.pop();
int d=t.first,ver=t.second;//ver起点编号
if(st[ver]) continue;//如果已经拓展过就continue
st[ver]=true;//标记一下
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
cin>>m;
while(m--){
int x;
cin>>x;
add(0,x,0);
}
dijkstra();
cin>>m;
while(m--){
int x;
cin>>x;
cout<<dist[x]<<endl;
}
return 0;
}思路：当点数多的时候就不能用朴素dijkstra算法了，要用这个进阶版，朴素版的我也放一下：
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for (int i=0;i<n;i++){
int t=-1;
for (int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
st[t]=true;
for (int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}优化版的使用了小根堆（其实也不大懂为什么但总而言之先背下来），这题还有个重要思路就是先手动填上一个虚拟原点，这样就可以把出发点统一起来了。不过要注意：dijkstra算法适用于求正权有向图中，源点到其余各个节点的最短路径。图中可以有环，但不能有负权边。
3305.作物杂交
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=200010;
int n,m,k,t;
int h[N],e[M],ne[M],target[M],w[N],idx,dist[N];
bool st[N];
queue<int> q;
void add(int a,int b,int c){
e[idx]=b;target[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void spfa(){
while(q.size()){
auto x=q.front();
q.pop();
st[x]=false;
for (int i=h[x];~i;i=ne[i]){
int y=e[i],z=target[i];
if(dist[z]>max(dist[x],dist[y])+max(w[x],w[y])){
dist[z]=max(dist[x],dist[y])+max(w[x],w[y]);
if(!st[z]){
q.push(z);
st[z]=true;
}
}
}
}
}
int main(){
cin>>n>>m>>k>>t;
memset(h,-1,sizeof h);
for (int i=1;i<=n;i++){
cin>>w[i];
}
memset (dist,0x3f,sizeof dist);
while(m--){
int x;
cin>>x;
q.push(x);
dist[x]=0;
st[x]=true;
}
while(k--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<dist[t];
return 0;
}思路：一个一开始根本就没有想到用图做的题，spfa看起来比dijkstra简单点，都是单源最短路，不过spfa可以计算图中有负权边的。
4074.铁路与公路
#include<bits/stdc++.h>
using namespace std;
const int N=410,INF=0x3f3f3f3f;
int n,m;
int f[N][N],g[N][N];
int floyd(int d[][N]){
if(d[1][n]==1) return 1;
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
return d[1][n];
}
int main(){
cin>>n>>m;
memset(f,0x3f,sizeof f);
memset(g,0x3f,sizeof g);
while(m--){
int x,y;
cin>>x>>y;
f[x][y]=f[y][x]=1;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if(i!=j&&f[i][j]!=1) g[i][j]=g[j][i]=1;
}
}
int res=max(floyd(f),floyd(g));
if(res==INF) res=-1;
cout<<res;
return 0;
}思路：floyd可以用于多源最短路，不过三层循环时间会慢一点，数据量少的时候可以用，不顾看起来模板是最好背的 乐
下面的题目就不全是acwing蓝桥杯每日一题了，自己找了点网站别的题做做（依然还是什么都不会写）
4865.有效类型
#include <bits/stdc++.h>
using namespace std;
int flag=1;
string str="",s;
void input(){
if(cin>>s){
str+=s;
if(s=="pair"){
str+='<';
input();
str+=',';
input();
str+='>';
}
}
else flag=0;
}
int main(){
int n;
cin>>n;
input();
if(cin>>s) flag=0;
if(flag==0) cout<<"Error occurred";
else cout<<str;
return 0;
}思路：y总的思路是构造一棵二叉树，可能会出现两种异常：1、需要输入的时候没有输入了 2、输入完毕了发现还有要输入的。思路真的巧妙但愿我能记住吧
3382.整数划分
#include <bits/stdc++.h>
using namespace std;
const int N=21,M=1000010,MOD=1e9;
int m,f[M];
int main(){
cin>>m;
f[0]=1;
int n=0;
for (int i=1,v=1;v<=m;i++,v*=2){
n++;
for (int j=v;j<=m;j++){
f[j]=(f[j]+f[j-v])%MOD;
}
}
cout<<f[m];
return 0;
}思路：有限制的选择问题可以选择用背包，然后就是模板了，二维转换为一维的优化需要记一下。背包背包背包，你咋老是想不起来用。
以上仅是我个人学习记录，有问题还请大家指正