2022/6/15

2022/6/15

        放假后第一天开始练习，状态非常不好，还睡了一下午，脑子反而更加蒙了，慢慢的调整状态，慢慢回复 

游园安排 - 蓝桥云课 (lanqiao)      最长递增子序列记录路径  

        好久没有做题了，看到一个最长递增子序列的题目，但是要求记录路径，拖着浑噩的脑子想了很久也没想出来，其实和其他的dp记录路径差不多，用一个path数组记录路径，不管是替换还是在末尾添加操作我们都让第i个字符串指向他在子序列中的前一个字符串，需要再开一个数组pa用来记录子序列中每个字符串在原来的字符串中的下标，nlogn做法最后一个字符串是确定的，所以我们就从最后一个往前推，最后用一个栈输出就可

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
string s[1000006],t,d[1000006];
ll len,cnt,pa[1000006],path[1000006];
int main(){len=0,cnt=0;cin>>t;for(int i=0;i<t.size();i++){if(t[i]>='A'&&t[i]<='Z') cnt++;s[cnt]+=t[i];}//for(int i=1;i<=cnt;i++) cout<<s[i]<<" ";cout<<endl;d[1]=s[1];len=1;pa[len]=1;path[1]=pa[0];for(int i=2;i<=cnt;i++){if(d[len]<s[i]){d[++len]=s[i];pa[len]=i;path[i]=pa[len-1];}else{ll j=lower_bound(d+1,d+len+1,s[i])-d;d[j]=s[i];pa[j]=i;path[i]=pa[j-1];}//cout<<path[i]<<" "<<pa[len]<<" "<<len<<endl;}stack<ll>st;ll x=pa[len];while(path[x]){st.push(x);x=path[x];}st.push(x);while(!st.empty()){cout<<s[st.top()];st.pop();}return 0;
}

阶乘约数 - 蓝桥云课 (lanqiao)约数定理与唯一分解定理 

1.唯一分解定理 对于一个大于1的整数n，可以将n分解成一些质因数的幂次和。

2.约数定理 一个正整数的正约数个数等于他通过唯一分解定理分解出来的所有质因数的次幂+1后的累乘结果

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
ll a[110]={0};
void f(ll n){for(int i=2;i<=n/i;i++){if(n%i==0){while(n%i==0){a[i]++;n/=i;}}}if(n>1) a[n]++;
}
int main(){for(int i=1;i<=100;i++) f(i);ll ans=1;for(int i=1;i<=100;i++){if(a[i])ans*=a[i]+1;}cout<<ans;return 0;
}

路径之谜 - 蓝桥云课 (lanqiao)  dfs记录路径

dfs用的不好，这题正好考了记录路径，记录一下，这个vector记录路径挺好用的

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
ll n,ex[25],ey[25],vis[25][25];
ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
ll flag;
vector<ll>path;
void dfs(ll x,ll y){if(ex[x]<0||ey[y]<0) return;if(x==n&&y==n){for(int i=1;i<=n;i++){if(ex[i]!=0||ey[i]!=0){return;}}//cout<<"sss"<<endl;for(int i=0;i<path.size();i++) cout<<path[i]-1<<" ";flag=1;return;}for(int i=0;i<4;i++){ll cx=x+dx[i],cy=y+dy[i];if(cx<1||cx>n||cy<1||cy>n||vis[cx][cy]) continue;ex[cx]--;ey[cy]--;path.push_back((cx-1)*n+cy);vis[cx][cy]=1;dfs(cx,cy);path.pop_back();//能到这说明上一个深搜不符合情况，所以把刚才添加的元素弹出vis[cx][cy]=0;ex[cx]++;ey[cy]++;}
}
int main(){scanf("%lld",&n);flag=0;for(int i=1;i<=n;i++) scanf("%lld",&ey[i]);for(int i=1;i<=n;i++) scanf("%lld",&ex[i]);vis[1][1]=1;path.push_back(1);ex[1]--;ey[1]--;dfs(1,1);return 0;
}

D-Breezing_牛客小白月赛53(重现赛) (nowcoder)7/11

光贪心的排序处理是不可以的，由于不确定到底是需要哪个数改变，所以这题得需要dp，通过题目很容易就可以看出数组中的数要么不变，要么是1，然后设dp状态:dp[i][0]为第i个数变为1时前i个数最大的可爱值，dp[i][1]为第i个数不变时前i个数最大的可爱值，然后根据题意列方程就可以了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,dp[100005][2],a[100005];
int main(){scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=2;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i-1]-1);dp[i][1]=max(dp[i-1][0]+a[i]-1,dp[i-1][1]+abs(a[i]-a[i-1]));}printf("%lld\n",max(dp[n][0],dp[n][1]));return 0;}

E-Calling_牛客小白月赛53(重现赛) (nowcoder) 代码

先放大的然后小的插空，难点在于如何写代码，我没有写出来，看了题解发现竟然可以用这么少的代码写出来，非常简洁，这也是思路清晰的一种表现吧

牛客小白月赛 53 赛后总结及题解_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,a,b,c,d,e,f,s,res=0;
int main(){cin>>t;while(t--){res=0;cin>>s;cin>>a>>b>>c>>d>>e>>f;res+=f+e+d+c/4;ll putb=d*5;if(c%4!=0){res++;if(c%4==1) putb+=5;else if(c%4==2) putb+=3;else if(c%4==3) putb+=1;}if(b>putb) res+=(b-putb)/9;if((b-putb)%9>0) res++;ll used=6*6*f+5*5*e+4*4*d+3*3*c+2*2*b;ll puta=36*res-used;if(a>puta) res+=(a-puta)/36;if((a-puta)%36>0) res++;if(res>s) cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0;}

D-操作题_牛客小白月赛51 (nowcoder) 进制

这道题的思路在于进制，可以把n看成是一个x进制的数，仿照十进制写出n的x进制的形式：

n=a*x^3+b*x^2+c*x+d;那这样我们就可以按照十进制那样取余的方式构造出一个操作序列来了

牛客小白月赛51题解~_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n,x;
vector<ll>v;
vector<char>c;
int main(){cin>>t;while(t--){v.clear();c.clear();cin>>n>>x;while(n){for(int i=0;i<n%x;i++){v.push_back(1);c.push_back('a');}v.push_back(2);c.push_back('b');n/=x;}cout<<v.size()<<endl;for(int i=0;i<v.size();i++){cout<<v[i]<<" "<<c[i]<<endl;}}return 0;
}

E-语法题_牛客小白月赛51 (nowcoder) 数学

自己写的时候只是注意到了满足条件的n是在[n*bi,(n+1)*bi-1]这个区间内，并且n如果大于全部的ai那么这样最后结果就是1；但是没有注意到n必须要是正整数，也没有注意到有可能求得区间是重复的（这一点发现之后就不想做了，，），另外还有一点就是ai要是单调递增的才有意义，因为只要n<ai,那么就会进入判断条件之后输出，所以一开始是要把ai预处理成单调递增的，然后重点就是求交集了，影响结果的是有两个区间一个是[n*bi,(n+1)*bi-1],再一个是[a[i-1],a[i]-1]，因为处理成单调递增之后，这两个区间的交集对于结果来说是没有重复的，所以最后直接输出累加后的sum就可以了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll x,a[100005],b[100005],n,c[100005],d[100005];
int main(){scanf("%lld",&x);ll sum=0,maxx=0,cnt=0,mx=0;for(int i=1;i<=x;i++){scanf("%lld%lld",&c[i],&d[i]),maxx=max(maxx,c[i]);if(c[i]>mx) a[++cnt]=c[i],b[cnt]=d[i],mx=c[i];}scanf("%lld",&n);if(n>=maxx){printf("1\n");return 0;}for(int i=1;i<=cnt;i++){if(a[i]<a[i-1]) continue;ll l=max(a[i-1],n*b[i]),r=min(a[i]-1,(n+1)*b[i]-1);l=max(l,1LL);sum+=max(0LL,r-l+1);}printf("%lld\n",sum);return 0;
}