a.打标记判断即可 ll n,m,a,b,ans=inf; bool f; void solve(){ cin>>a>>b>>n; rep(i,1,n){ ll k;cin>>k>>m;f=0; rep(j,1,m){ int x;cin>>x; if(x==a)f=1; if(f&&x==b)ans=min(ans,k); } } if(ans==inf)cout<<-1; else cout<<ans; return; }  b.开两个数组，表示从a开始到某点的最小距离和从某点到...

Word Processor 简单模拟 void solve(){ string s; cin>>n>>m;ll cnt = 0; rep(i,1,n){ cin>>s; if(cnt+len(s)>m){ cout<<"\n"<<s<<" ";cnt=len(s); }else{ cout<<s<<" ";cnt+=len(s); } } return ; }  Photoshoot n<=1000,模拟操作即可,从小到大枚举ans[1],只要满足条件输出即可，因为i更小字典序一定更小...

a[n]=0时一定无解,因为1-n的排列无论如何变换都是1-n的排列 a[n]!=0时,遇到0就交换a[i],a[i+1]，这样可以满足只对i位置产生影响而不影响其余位置 #include <bits/stdc++.h> #define ls p<<1 #define print pt #define fi first #define rs p<<1|1 #define se second #define ins insert #define getchar nc #define pb push_back #define lread rd<ll>...

注意到开平方相较于除2和减1在n>2时一定更优，除2在n<=2时一定更优，所以先尽可能开方直到m=0或n=2，然后剩余的m进行-1操作即可 #include <bits/stdc++.h> #define ls p<<1 #define print pt #define fi first #define rs p<<1|1 #define se second #define ins insert #define getchar nc #define pb push_back #define lread rd<ll> #define r...

一种nlogn求解lis/lds问题的做法 维护一个tail数组,tail[i]表示tail[i]作为长度为i+1的最长上升子序列的最后一个元素，这样对于一个新的待处理a[i],可以在tail中二分寻找可插入位置。如果it==tail.end()，说明a[i]是最大的，让它成为最后一个元素,否则一定有a[i]<=it,将it替换为a[i]一定不比it差,循环结束后tail数组的大小就是lis的长度 对于求解lds,全部元素-1即可 #include <bits/stdc++.h> #define ls p<<1 #define print pt #define f...

断环成链，只有全部宝石都不相同时候无法断裂，否则记录当前宝石出现位置，再次遇到相同宝石时候更新位置比记录答案即可，注意两个宝石之间的宝石数量是(j-i-1) #include <bits/stdc++.h> #define ls p<<1 #define print pt #define fi first #define rs p<<1|1 #define se second #define ins insert #define getchar nc #define pb push_back #define lread rd<ll> #defin...

跑的还挺快的 先考虑朴素算法。处理出前缀和pre数组,双重循环枚举l,r,ans=max(ans,pre[r]-pre[l-1]) 显然O(n^2)无法通过此题 我们调整一下循环逻辑 for(int j = 1;j<=n;j++){ for(int i = 1;i<=j;i++){ ans=max(ans,pre[j]-pre[i-1]); } }  也就是固定右端点,枚举左端点。而每个位置的前缀和显然是固定的。那我们就将问转换成求[1,r-1]中的前缀最小值了 单调队列是一种特殊的队列，队列中的元素从队头到队尾是单调递减的。 具体来说： 队头（q[l]）的前缀和是队列中最大的。 ...

q次询问最短距离 有一条权为0的边，假设端点a，b，要求u，v最短距离 于是求min(dis(u,v),dis(u,a)+dis(v,b),dis(u,b)+dis(v,a))即可 过程用lca实现 #include <bits/stdc++.h> #define ls p<<1 #define print pt #define fi first #define rs p<<1|1 #define se second #define ins insert #define getchar nc #define pb push_back #define lrea...

二分检验 #include<bits/stdc++.h> using namespace std; #define int long long struct student{ int num; int be; int en; }; student a[1001000]; int room[1001000]; int pre[1001000]; int ans,l,r,mid,n,day,cnt; bool check(int mid){ memset(pre,0,sizeof(pre)); for(int i = 1;i<=mid;i++){ pre[a[i].be]+=a[...

题面 小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。 一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使...