一.闲话
打了下比赛，把A-E做了后，看了下F，思考了一会儿，发现不可做，就来写题解辣，qwq
二.题解部分
A 打怪
签到题，我的思路是先判断-1的情况（如果你可以一刀999秒掉小怪，由于你先手，那你就可以砍无数小怪了）
然后，我们先计算出，砍完一只小怪，你扣的血，假设为x，这样，答案就是floor((n-1)/x)[n-1的原因是你至少要留1滴血，不然GG，2333]
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int h,a,H,A;
scanf("%d%d%d%d",&h,&a,&H,&A);
if(a>=H){
puts("-1");
continue;
}
int kil=ceil(double(H)/a),ht=(kil-1)*A;
printf("%d\n",(h-1)/ht);
}
return 0;
} B 吃水果
这个题我想的时间比后面三道题还久。。。老了老了，qwq
我的思路很简单，首先特判n=m的情况，然后，我们来倒推一下
最后，肯定是经过我们一系列神奇的操作后，n=m，然后我们再用n天吃掉就好了
以下为了好讲解，我们不妨设n<m
我们注意到，我们的操作只有三种——和
和
我们仔细分析下，发现，因为n<m那么这个操作其实是完全没用的（只是无谓的增加了两者差距罢了），所以，我们实际有用的操作就只有n-1,m-1和
然后，因为上面我们说了，最后一定是变成了n=m这个情况，但是，很明显，n-1,m-1这个操作不能使得n=m,所以，使n=m的上一次操作一定是n*2,m
即此时一定满足n=m/2
那么，我们就来算算什么时候可以做到n=m/2
首先，我们假设我们现在不进行这个操作,那么设我们进行了x次n-1,m-1次操作后，使得n=m/2，即
2(n-x)=m-x
解得x=2n-m
当然，x必须大于等于0才有意义
然后，我们就可以直接枚举，我们一开始进行了i次n*2,m操作，这样，每次统计一下答案，取所有的最小即可
因为n*2,m这个操作会使得后面所需步骤几何级增大，所以，不难发现，我们枚举的i其实很小（我没仔细算，估计logn级别，所以，我就直接枚举到20）
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int T;
scanf("%lld",&T);
while(T--){
int n,m;
scanf("%lld%lld",&n,&m);
if(n==m){
printf("%lld\n",n);
continue;
}
if(n>m){
swap(n,m);
}
int ans=2e9;
for(int i=0;i<=20;++i){//乘i次2后，n是m的1/2
int now=2*n-m;
if(now>=0){
ans=min(ans,now+i+1+m-now);
}
n*=2;
if(n>m){
swap(n,m);
}
}
printf("%lld\n",ans);
}
return 0;
} C 四个选项
这道题，看到总共n就12，所以，我们按下先不考虑其他限制条件
12个题的选择结果总共有，注意到，总情况非常小，明显爆搜可以跑出，所以我们可以直接打爆搜再验证，但是，验证的复杂度是O(m),所以，为了稳重起见，我们要对代码进行一些小优化
注意到，题目给的限制是要求x和y相同，那么，我们再假设有一限制要求y和z相同，那么，就等价于
x,y,z都相同，注意到这个特点后，我们就可以直接开个并查集，将必须相同的点放同一个并查集里面，
每次枚举时判断下，自身所属的并查集是否已经选择了选项，如果选择了，就跳过不枚举即可。
当然，我们也可以同时判断下我们每次选一个选项时，若选项剩余的个数小于并查集的大小，那么该并查集就不能选这个选项了。
这样，速度就很快了~
代码
#include<bits/stdc++.h>
using namespace std;
const int N=13;
int fa[N],ans;
int siz[N];
bool c[N];
inline int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
int a=find(x),b=find(y);
if(a!=b){
fa[a]=b,siz[b]+=siz[a];
}
}
inline void dfs(int now,int na,int nb,int nc,int nd){
if(now==13){
++ans;
return;
}
if(c[fa[now]]){
dfs(now+1,na,nb,nc,nd);
return;
}
if(na>=siz[fa[now]]){
c[fa[now]]=1;
dfs(now+1,na-siz[fa[now]],nb,nc,nd);
c[fa[now]]=0;
}
if(nb>=siz[fa[now]]){
c[fa[now]]=1;
dfs(now+1,na,nb-siz[fa[now]],nc,nd);
c[fa[now]]=0;
}
if(nc>=siz[fa[now]]){
c[fa[now]]=1;
dfs(now+1,na,nb,nc-siz[fa[now]],nd);
c[fa[now]]=0;
}
if(nd>=siz[fa[now]]){
c[fa[now]]=1;
dfs(now+1,na,nb,nc,nd-siz[fa[now]]);
c[fa[now]]=0;
}
}
int main(){
int na,nb,nc,nd,m;
scanf("%d%d%d%d%d",&na,&nb,&nc,&nd,&m);
int n=na+nb+nc+nd;
for(int i=1;i<=n;++i){
fa[i]=i;siz[i]=1;
}
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
merge(x,y);
}
for(int i=1;i<=n;++i){
fa[i]=find(i);
}
dfs(1,na,nb,nc,nd);
printf("%d",ans);
return 0;
} D 最短路变了
这道题挺简单的，我们先分别算出1到所有点的最短路距离（正向建边，设为）,再算出所有点到n的最短路距离（反向建边，设为
）
然后，这里有个我猜的结论（滑稽，脑海中盲目证明了）：
如果反向的边是最短路上的边，那么最短路长度一定不会变小（即答案为NO）
这个我们可以直接标记一下就可以处理了
那么，现在我们该考虑的就是如果反向的边不是最短路上的边的情况
我们假设，这条边反向后，最短路长度变短了，那么，不难发现，如果最短路长度变短了，那么现在必然要走这条反向后的边，那么现在的必须走反向边的最短路的长度就变成了：
我们把上面的值和原来的最短路长度比较一下，现在比原来小的话就输出YES，否则输出NO，即可
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
struct node{
int v,w,nex,id;
}t[N];
int U[N],V[N],W[N];
priority_queue<pair<int,int> >sp;
bool init[N];
int dis[N][2];bool vis[N];
int las[N],len;
inline void add(int u,int v,int w,int id){
t[++len]=(node){v,w,las[u],id},las[u]=len;
}
inline void dijkstra(int st,int num){
memset(vis,0,sizeof(vis));
dis[st][num]=0;sp.push(make_pair(0,st));
while(!sp.empty()){
int x=sp.top().second;sp.pop();
if(vis[x]){
continue;
}
vis[x]=1;
for(int i=las[x];i;i=t[i].nex){
int v=t[i].v,w=t[i].w;
if(dis[v][num]>dis[x][num]+w){
dis[v][num]=dis[x][num]+w;
sp.push(make_pair(-dis[v][num],v));
}
}
}
}
signed main(){
memset(dis,0x3f3f,sizeof(dis));
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
U[i]=u,V[i]=v,W[i]=w;
add(v,u,w,i);
}
dijkstra(n,1);
memset(las,0,sizeof(las)),len=0;
for(int i=1;i<=m;++i){
add(U[i],V[i],W[i],i);
}
dijkstra(1,0);
int now=1;
while(now!=n){
for(int i=las[now];i;i=t[i].nex){
int v=t[i].v,w=t[i].w;
if(dis[now][0]+w+dis[v][1]==dis[n][0]){
now=v;init[t[i].id]=1;
break;
}
}
}
int q;
scanf("%lld",&q);
while(q--){
int x;
scanf("%lld",&x);
if(init[x]){
puts("NO");
}else{
int now=dis[V[x]][0]+W[x]+dis[U[x]][1];
if(now<dis[n][0]){
puts("YES");
}else{
puts("NO");
}
}
}
return 0;
} E 相似的子串
我们注意到，这个“公共前缀”其实没啥用，我们直接把公共前缀当一个串的话其实答案是一样的，所以我们可以把题目转化成，求至少出现k次，不重叠的最长子串
咋看一下像极了SA的一道模板题，然而，太久没打有点生疏了，所以，我打算直接hash暴力做（滑稽）
考虑二分答案
我们假设二分出，串的长度为x，那么我们就可以直接用hash判断串是否相等了（求hash可以直接O(n)递推出所有长度为x的串的hash，所以复杂度没问题）
现在问题就在于，如何使得串不重叠。
我们首先，假设有若干个相同的长度为的串，他们的起点分别为
a1,a2...ak
我们要尽量多的选出不重叠的串
定义：两个串i,j(i<j)不重叠，当且仅当(ai+x-1<aj)[即i串的末尾在j串开头的左边]
这个我们就可以直接贪心做了，我们每次尽量选靠前的串，能选就选，就可以了
关于这一步的实现，我一开始打算先把所有长度为x的串的hash值和起点存下来，再按照hash值为第一关键字，起点为第二关键字排序弄，想了下太麻烦了，就为了省事直接用map做了
复杂度其实一开始交的时候，我都以为可能会T，然后做好了卡常的准备了的，23333
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1,base=23;
string a;
int n,k;
unsigned long long S[N];
map<unsigned long long,pair<int,int> >s;
inline bool check(int x){
s.clear();
unsigned long long now=0;int tot=0;
for(int i=1;i<=x;++i){
now=now*base+(a[i-1]-'a'+1);
}
s[now]=make_pair(x,1);
for(int i=x+1;i<=n;++i){
now=now-(S[x-1]*(a[i-x-1]-'a'+1));
now=now*base+(a[i-1]-'a'+1);
if(s.find(now)!=s.end()){
if(s[now].first<i-x+1){
int fow=s[now].second;
if(fow+1==k){
return true;
}
s[now]=make_pair(i,fow+1);
}
}else{
s[now]=make_pair(i,1);
}
}
return false;
}
int main(){
S[0]=1;
scanf("%d%d",&n,&k);
if(k==1){
printf("%d",n);
return 0;
}
for(int i=1;i<=n;++i){
S[i]=S[i-1]*base;
}
cin>>a;
int l=1,r=n/k,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid,l=mid+1;
}else{
r=mid-1;
}
}
printf("%d",ans);
return 0;
} qwq终于写完了，%%%%%%各位神仙
京公网安备 11010502036488号