[折半搜索/BFS]T1:给定一个无向图，边权是1，点权\(vi\epsilon [1,1e18]\),要求你选出4个不重复的点，从1出发到这些点然后回到1，可以经过重复点，但是要求\(max(dis(1,i),dis(i,j),dis(j,u),dis(u,v),dis(v,1))<K\),不能重复计算贡献。求\(max(a_i+a_j+a_u+a_v)\)。(n<=2000)
正解
其实正常思路就是4个点，我从1出发找2个，把这\(n^2\)个点对拼起来，怎么拼？
【1】随机化+贪心：把\(n^2\)级别的合法点对找出来，sort一下\(ai+aj\),因为复杂度级别最大n^2,所以直接取前1000对进行拼接，暴力check是否互不重复和dis
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define chu printf
#define rint register int
#define ll long long
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int N=2500+100;
int d[N][N],n,head[(int)N],tot,m;
ll v[(int)N];int K;
bool r[(int)N];
struct node
{
int to,nxt;
}e[10000<<4];
deque<int>q;
vector<pair<int,int> >chs;
inline void add_e(int x,int y)
{
e[++tot]=(node){y,head[x]};
head[x]=tot;
}
inline void BFS(int st)
{
d[st][st]=0;
q.push_front(st);r[st]=1;
while(!q.empty())
{
int x=q.front();q.pop_front();
for(rint i=head[x];i;i=e[i].nxt)
{
int to=e[i].to;
if(r[to])continue;
d[st][to]=d[st][x]+1;
r[to]=1;
q.push_back(to);
}
}
}
inline bool cmp(pair<int,int>s1,pair<int,int>s2)
{
return v[s1.first]+v[s1.second]>v[s2.first]+v[s2.second];
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=re(),m=re(),K=re();
memset(d,0x3f,sizeof(d));
for(rint i=2;i<=n;++i)v[i]=re();
for(rint i=1;i<=m;++i)
{
int u=re(),v=re();
add_e(u,v);add_e(v,u);
}
// return 0;
for(rint i=2;i<=n;++i)
{
fill(r+1,r+1+n,0);
BFS(i);
}
for(rint i=2;i<=n;++i)
{
for(rint j=i+1;j<=n;++j)
{
//1-->i-->j
if(d[i][1]-1<=K&&d[i][j]-1<=K)chs.push_back(make_pair(i,j));
if(d[j][1]-1<=K&&d[j][i]-1<=K)chs.push_back(make_pair(j,i));//不存在最短路概念，因为我枚举了每2对作为答案
}
}
ll ans=0;
sort(chs.begin(),chs.end(),cmp);
for(rint i=0;i<min(1000,(int)chs.size());++i)
{
for(rint j=0;j<min(1000,(int)chs.size());++j)
{
if(i==j)continue;
pair<int,int>e1=chs[i],e2=chs[j];
//1_fir-->1_sec-->2_sec_-->2_fir
if(e1.first==e2.first||e1.first==e2.second||e1.second==e2.first||e1.second==e2.second)continue;
if(d[e1.second][e2.second]-1<=K)
ans=max(ans,v[e1.first]+v[e1.second]+v[e2.first]+v[e2.second]);
// if(ans==30)chu("%d %d %d %d\n",e1.first,e1.second,e2.first,e2.second);
}
}
chu("%lld",ans);
return 0;
}
/*
8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
*/
【2】分析，考虑枚举\([u,v]\)是合法的2个点对拼接的中转点，满足\(dis(u,v)<K\),发现保留u和v的来自点的最大、次大、次次大才可以找到合法匹配，所以BFS更新维护3个值然后取max9种情况.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll read(){
ll x = 0; char c = getchar();
while(!isdigit(c)){c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2505;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
ll val[maxn];
int dis[maxn][maxn];
int head[maxn], tot;
struct edge{int to, net;}e[20005];
void add(int u, int v){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
}
queue<int>q;
void get_dis(int s){
q.push(s);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(dis[s][v] > dis[s][x] + 1){
dis[s][v] = dis[s][x] + 1;
q.push(v);
}
}
}
}
int mx[maxn], cmx[maxn], ccmx[maxn];
ll getval(int x, int px, int y, int py){
if(!x || !y || !px || !py)return -inf;
if(x == y || x == py || y == px || px == py)return -inf;
if(dis[1][px] > k || dis[1][py] > k || dis[px][x] > k || dis[x][y] > k || dis[y][py] > k)return -inf;
return val[x] + val[px] + val[y] + val[py];
}
ll get(int x, int y){
ll ans = getval(x, mx[x], y, mx[y]);
ans = max(ans, getval(x, mx[x], y, cmx[y]));
ans = max(ans, getval(x, mx[x], y, ccmx[y]));
ans = max(ans, getval(x, cmx[x], y, mx[y]));
ans = max(ans, getval(x, cmx[x], y, cmx[y]));
ans = max(ans, getval(x, cmx[x], y, ccmx[y]));
ans = max(ans, getval(x, ccmx[x], y, mx[y]));
ans = max(ans, getval(x, ccmx[x], y, cmx[y]));
ans = max(ans, getval(x, ccmx[x], y, ccmx[y]));
return ans;
}
int main(){
// freopen("holiday.in","r",stdin);
// freopen("holiday.out","w",stdout);
n = read(), m = read(), k = read();
for(int i = 2; i <= n; ++i)val[i] = read();
for(int i = 1; i <= m; ++i){
int x = read(), y = read();
add(x, y); add(y, x);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dis[i][j] = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i){dis[i][i] = -1; get_dis(i);}
for(int i = 2; i <= n; ++i)if(dis[1][i] <= k){
for(int j = 2; j <= n; ++j)if(j != i && dis[i][j] <= k){
if(val[i] > val[mx[j]]){
ccmx[j] = cmx[j];
cmx[j] = mx[j];
mx[j] = i;
}else if(val[i] > val[cmx[j]]){
ccmx[j] = cmx[j];
cmx[j] = i;
}else if(val[i] > val[ccmx[j]])ccmx[j] = i;
}
}
ll ans = 0;
for(int i = 2; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
if(i != j && dis[i][j] <= k)
ans = max(ans, get(i, j));
printf("%lld\n",ans);
return 0;
}
[简单分类讨论/无脑博弈]T2：A和B玩游戏，给出序列A长度n，序列B长度m，Q个询问区间[l,r],A从中挑选一个位置作为Ai，B之后挑选一个位置作为Bj，\(val=Ai*Bj\),A希望这个值尽量大，B希望尽量小，求若干次询问的val值结果。（n,q<=1e5）
正解
发现如果确定了Ai，那么选出B的最值其实只和$max,min,max(<0),min(>=0)$4个值中找来源，具体分类讨论比较复杂可以不考虑直接取max/min，max和min可以在线段树上维护，比ST表好打！
对于不存在的，赋值inf在取答案的时候特判忽略掉就可以！【很巧妙！很简单！】
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define chu printf
#define rint register int
#define ll long long
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int N=1e5+100,inf=(1e9+7);//18
int n,m,q;
struct node
{
int mx,mi,mz,mf;
inline node operator+(const node&A)const
{
node res;
res.mi=min(mi,A.mi);
res.mx=max(mx,A.mx);
res.mf=max(mf,A.mf);
res.mz=min(mz,A.mz);
return res;
}
};
struct ST_table
{
node v[N<<2];int val[N];
#define lson (rt<<1)
#define rson (rt<<1|1)
inline void build(int rt,int l,int r)
{
if(l==r)
{
v[rt].mx=v[rt].mi=val[l];
v[rt].mf=-inf;v[rt].mz=inf;
// chu("before mshit %d %d\n",v[rt].mz,v[rt].mf);
if(val[l]<=0)v[rt].mf=val[l];
if(val[l]>=0)v[rt].mz=val[l];
// chu("shit %d %d\n",v[rt].mz,v[rt].mf);
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
v[rt]=v[lson]+v[rson];
//chu("(%d--%d)v[%d].mf:%d mz:%d\n",l,r,rt,v[rt].mf,v[rt].mz);
}
inline node query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return v[rt];
int mid=(l+r)>>1;
if(R<=mid)return query(lson,l,mid,L,R);
if(L>mid)return query(rson,mid+1,r,L,R);
return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
}ta,tb;
inline ll Max(ll x,node y)
{
ll ans=4e18;
ans=min(x*y.mi,x*y.mx);
if(y.mf!=-inf)ans=min(ans,x*y.mf);
if(y.mz!=inf)ans=min(ans,x*y.mz);
return ans;
}
int main()
{
//freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=re(),m=re(),q=re();
for(rint i=1;i<=n;++i)ta.val[i]=re();
for(rint i=1;i<=m;++i)tb.val[i]=re();
ta.build(1,1,n);
tb.build(1,1,m);
for(rint i=1;i<=q;++i)
{
int la=re(),ra=re(),lb=re(),rb=re();
node x=ta.query(1,1,n,la,ra);
node y=tb.query(1,1,m,lb,rb);
// chu("%d %d %d %d\n",x.mx,x.mi,x.mf,x.mz);
ll ans=max(Max(x.mx,y),Max(x.mi,y));
if(x.mf!=-inf)ans=max(ans,Max(x.mf,y));
if(x.mz!=inf)ans=max(ans,Max(x.mz,y));
chu("%lld\n",ans);
}
return 0;
}
/*
3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2
*/
[基环树/随机数赋值判断条件]T3：给出一个有向图，有4种操作[1]删除边[u,v]
[2]加入边[u,v]
[3]删除和x连接的所有入边
[4]加入和x连接的所有入边
每次一个操作后，判断图是否从任一点出发可以无限重复走下去，而且每点出度是1(n,Q<=1e5)
正解
发现只有出度是1有用，只判断这个就行。
转化成在边数=1的条件下，所有点出度是奇数（这样可以通过加边删除边的数量直接维护）。