这是大师出的一套题，虽然感觉很难但最后还是调对了 %%ZCQ
T1 Trap
题目描述
小鼠Jack已经很多天没吃东西了，今天他终于忍不住来到了餐厅，碰巧发现了一块刚做好的海绵蛋糕。正当他准备好好享用时，他却失望的发现主人已经早有防备，在蛋糕附近布下了许多陷阱。为此，他想知道怎样才能最快拿到那块蛋糕。
我们假设餐厅的布局是一个由N个点（编号从1-N，Jack的初始位置在1号节点，蛋糕的位置在N号节点），M条双向边组成的连通图，第i条边连接Ai、Bi两个点，长度为Li。其中有一些点是可以安全通过的点，而另一些点则设有陷阱。已知主人在K个点上设有陷阱，其中第i个陷阱设在第Pi号节点上。因为Jack的身体很脆弱，所以他最多只能经过H个陷阱。现在Jack想知道，从1走到N，在最多经过H个陷阱的情况下，最短的路径长度是多少。
保证1号节点和N号节点不设有陷阱
输入格式
第1行为4个整数N，M，K，H
接下来的M行，第i行有3个整数Ai，Bi，Li
接下来的1行，有K个整数Pi
输出格式
第1行有1个整数，如果Jack能在经过不多于H个陷阱的情况下到达目的地，则输出最短路径长度，否则输出 -1
数据范围
对于20%的数据，H=0
对于40%的数据，1≤N≤1000，1≤M≤2000
对于100%的数据，1≤N≤10000，1≤M≤50000，1≤K≤N，1≤Ai，Bi≤N，
1≤Li≤10000，0≤H≤1
题目分析：
这道题的H再大一点的话就可以写分层图了2333
最短路需要改进：不管一个点上的是否有陷阱 我们都能更新从起点到该点的距离 但是不能用它来更新-即不能把它压入队列
因为0≤H≤1，所以分类讨论：
H=0时,直接是一个裸的最短路
H=1时,从1点和n点分别跑一次最小路 最后枚举求和即可
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k,h;
int dis[210000][3];
int head[210000];
int net[210000],to[210000],val[210000];
int tot;
bool book[210000];
void add(int x,int y,int v)
{
net[++tot]=head[x];
to[tot]=y;
val[tot]=v;
head[x]=tot;
}
bool vis[210000];
void spfa(int x,int t)
{
queue<int>q;
dis[x][t]=0;
q.push(x);
vis[x]=true;
while(q.size())
{
int tmp=q.front();
q.pop();
vis[tmp]=false;
for(int i=head[tmp];i;i=net[i])
{
if(dis[to[i]][t]>dis[tmp][t]+val[i])
{
dis[to[i]][t]=dis[tmp][t]+val[i];
if(!vis[to[i]]&&!book[to[i]])
{
q.push(to[i]);
vis[to[i]]=true;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&h);
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
for(int i=1;i<=k;i++)
{
int tmp;
scanf("%d",&tmp);
book[tmp]=true;
}
memset(dis,0x3f,sizeof dis);
if(h==0)
{
spfa(1,1);
if(dis[n][1]==0x3f3f3f3f)
printf("-1");
else printf("%d",dis[n][1]);
}
else
{
spfa(1,1);
spfa(n,2);
int ans=0x7f7f7f7f;
for(int i=1;i<=n;i++)
ans=min(ans,dis[i][1]+dis[i][2]);
if(ans>=0x3f3f3f3f) printf("-1");
else printf("%d",ans);
}
return 0;
}T2 Army
题目描述
都说doge拿耗子多管闲事，但是邻居的doge却总是对小鼠们的安全造成威胁，于是，Jack决定率领N只小鼠组成军队对doge进行还击。
已知小鼠的军队排成一条直线，小鼠从左到右编号为1-N，已知第i只小鼠的初始高度为Hi。接着Jack会对军队发出M个指令，指令共分为3种，每种的输入格式如下：
1 L R X：使[L，R]中的所有小鼠都长高X个单位
2 L R：使[L，R]中的所有小鼠身高翻倍
3 L R：使[L，R]中的所有小鼠对doge发起攻击，攻击强度为[L，R]中所有小鼠的身高之和
每次指令发出后，doge都会很愤怒，会攻击并杀死[1，N]中最高的小鼠，如果有多个身高最高的小鼠，则杀死编号最小的那个
注意：当一个小鼠被杀死后，他就不能长高和翻倍，也不能发起攻击，保证M次指令后小鼠不会死光
现在Jack想知道每次攻击的攻击强度是多少
输入格式
第1行2个整数N，M
第2行N个整数Hi
接下来的M行每行3个整数，代表Jack发出的指令
输出格式
对于每个3指令，输出攻击的强度，每个占一行
数据范围
对于40%的数据，1≤N≤2000，1≤M≤2000
对于100%的数据，1≤N≤20000，1≤M≤20000，1≤Hi，X≤1000，1≤L，R≤N
保证答案不超过263-1
题目分析：
线段树拓展应用 记录区间和,区间最大值,区间内有多少小鼠被杀 和两个Lazy标记
在考试时 update_add()中有一个等号忘写了 导致T2RE !!!! 加上瞬间就A了好么QAQ
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
long long c[30000];
struct your
{
int x,y;
long long sum;
long long maxx;
long long add;
long long mul;
long long ber;
}a[100000];
void build(int dx,int dy,int num)
{
a[num].x=dx;a[num].y=dy;
a[num].add=0;a[num].mul=1;a[num].ber=0;
if(dx==dy)
{
a[num].sum=a[num].maxx=c[dx];
return ;
}
int mid=(dx+dy)>>1;
build(dx,mid,num<<1);
build(mid+1,dy,num<<1|1);
a[num].ber=a[num<<1].ber+a[num<<1|1].ber;
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
return ;
}
void push_down(int num)
{
if(a[num<<1].ber<a[num<<1].y-a[num<<1].x+1)
{
a[num<<1].mul=a[num<<1].mul*a[num].mul;
a[num<<1].add=a[num<<1].add*a[num].mul+a[num].add;
a[num<<1].maxx=a[num<<1].maxx*a[num].mul+a[num].add;
a[num<<1].sum=a[num<<1].sum*a[num].mul+a[num].add*(a[num<<1].y-a[num<<1].x+1-a[num<<1].ber);
}
if(a[num<<1|1].ber<a[num<<1|1].y-a[num<<1|1].x+1)
{
a[num<<1|1].mul=a[num<<1|1].mul*a[num].mul;
a[num<<1|1].add=a[num<<1|1].add*a[num].mul+a[num].add;
a[num<<1|1].maxx=a[num<<1|1].maxx*a[num].mul+a[num].add;
a[num<<1|1].sum=a[num<<1|1].sum*a[num].mul+a[num].add*(a[num<<1|1].y-a[num<<1|1].x+1-a[num<<1|1].ber);
}
a[num].add=0,a[num].mul=1;
return ;
}
void update_mul(int dx,int dy,long long val,int num)
{
if(a[num].ber==a[num].y-a[num].x+1) return ;
if(a[num].x==dx&&a[num].y==dy)
{
a[num].mul=a[num].mul*val;
a[num].add=a[num].add*val;
a[num].sum=a[num].sum*val;
a[num].maxx=a[num].maxx*val;
return ;
}
if(a[num].mul!=1||a[num].add!=0)
push_down(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) update_mul(dx,dy,val,num<<1|1);
else if(dy<=mid) update_mul(dx,dy,val,num<<1);
else
{
update_mul(dx,mid,val,num<<1);
update_mul(mid+1,dy,val,num<<1|1);
}
a[num].ber=a[num<<1].ber+a[num<<1|1].ber;
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
return ;
}
void update_add(int dx,int dy,long long val,int num)
{
if(a[num].ber==a[num].y-a[num].x+1) return ;
if(a[num].x==dx&&a[num].y==dy)
{
a[num].add=a[num].add+val;
a[num].maxx=a[num].maxx+val;
a[num].sum=a[num].sum+val*(a[num].y-a[num].x+1-a[num].ber);
return ;
}
if(a[num].mul!=1||a[num].add!=0)
push_down(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) update_add(dx,dy,val,num<<1|1);
else if(dy<=mid) update_add(dx,dy,val,num<<1);
else
{
update_add(dx,mid,val,num<<1);
update_add(mid+1,dy,val,num<<1|1);
}
a[num].ber=a[num<<1].ber+a[num<<1|1].ber;
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
return ;
}
long long ask(int dx,int dy,int num)
{
if(a[num].x==dx&&a[num].y==dy)
return a[num].sum;
if(a[num].mul!=1||a[num].add!=0)
push_down(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) return ask(dx,dy,num<<1|1);
else if(dy<=mid) ask(dx,dy,num<<1);
else return (ask(dx,mid,num<<1)+ask(mid+1,dy,num<<1|1));
}
void del(int num)
{
if(a[num].ber==a[num].y-a[num].x+1) return ;
if(a[num].x==a[num].y)
{
a[num].sum=0;
a[num].ber=1;
a[num].maxx=0;
return;
}
if(a[num].mul!=1||a[num].add!=0)
push_down(num);
if(a[num<<1].maxx>a[num<<1|1].maxx)
del(num<<1);
else if(a[num<<1].maxx<a[num<<1|1].maxx)
del(num<<1|1);
else if(a[num<<1].maxx==a[num<<1|1].maxx)
del(num<<1);
a[num].ber=a[num<<1].ber+a[num<<1|1].ber;
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int tmp;
scanf("%d",&tmp);
if(tmp==1)
{
int x,y;
long long c;
scanf("%d%d%lld",&x,&y,&c);
update_add(x,y,c,1);
}
else if(tmp==2)
{
int x,y;
scanf("%d%d",&x,&y);
update_mul(x,y,2,1);
}
else if(tmp==3)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",ask(x,y,1));
}
del(1);
}
return 0;
}T3 Dining
题目描述
为了庆祝对doge发起进攻的顺利结束，Jack决定和所有的小鼠一起举办一场宴会
宴会一共有N只小鼠参加，小鼠从左到右坐成一排，标号为1-N，每只小鼠穿着一种颜色的服装，一共有M种颜色的服装，第i只小鼠的服装颜色为Ci。现在，为了使所有服装整体看起来美观，Jack想找到一段区间，使得这段区间内服装的颜色种类不少于K种，并且Jack希望这段区间尽可能的短，现在请你帮他找出最短区间的长度。
输入格式
第1行3个整数N，M，K
第2行N个整数Ci
输出格式
第行1个整数，代表符合题意的最短区间的长度，保证一定存在符合题意的区间
数据范围
对于30%的数据，1≤N≤2000
对于100%的数据，1≤N≤500000，1≤K，Ci≤M≤N
题目分析：
其实第三题才是今天最水的一题 这个方法貌似叫做双指针法，也叫尺取法。
先定义l为左指针，r为右指针
枚举右指针r，找出最大的r使得[1,r]符合题目条件。然后不断向右移动左端点l，并始终保证[l ,r]符合条件，每次移动后再向右移动移动右指针r，每次移动后用r-l+1更新答案就行了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int a[510000];
int n,m,k;
int ans=0x7f7f7f7f;
int vis[510000];
int l=1;
int tmp;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
if(vis[a[i]]==0)
tmp++;
vis[a[i]]++;
if(tmp==k)
{
ans=min(i-l+1,ans);
while(l<i&&tmp==k)
{
ans=min(ans,i-l+1);
vis[a[l]]--;
if(vis[a[l]]==0) tmp--;
l++;
}
}
}
printf("%d",ans);
return 0;
}