这种题目，写个Trie随便切。
#include<cstdio>
#include<cstring>
#define N 110
#define NN 11000
using namespace std;
struct node
{
int a[30],id;
}tr[NN];int len=1;
void add(char ss[],int id)
{
int ed=strlen(ss+1),x=1;
for(int i=1;i<=ed;i++)
{
if(!tr[x].a[ss[i]-'a'])tr[x].a[ss[i]-'a']=++len;
x=tr[x].a[ss[i]-'a'];
}
tr[x].id=id;
}
int find(char ss[])
{
int ed=strlen(ss+1),x=1;
for(int i=1;i<=ed;i++)x=tr[x].a[ss[i]-'a'];
return tr[x].id;
}
char st[N][N],ss[5][N];
int n,m;
inline bool check(int x,int y)
{
if(strlen(st[x]+1)!=strlen(ss[y]+1))return false;
for(int i=strlen(st[x]+1);i>=1;i--)
{
if(st[x][i]!=ss[y][i])return false;
}
return true;
}
char ans[]={'A','B','C','D'};
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",ss[0]+1);
add(ss[0],i);
scanf("%s",st[i]+1);
}
for(int i=1;i<=m;i++)
{
scanf("%s%s%s%s%s",ss[0]+1,ss[1]+1,ss[2]+1,ss[3]+1,ss[4]+1);
int x=find(ss[0]);
for(int j=1;j<=4;j++)
{
if(check(x,j)==true)
{
printf("%c\n",ans[j-1]);
break;
}
}
}
return 0;
}以为很难，发现其实就是贪心，对于吃\(i\)种食品，那么满足感最大的肯定是最大的前\(i\)种食品啦。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 310000
using namespace std;
int n,a[N];
double ans=0;
inline bool cmp(int x,int y){return x>y;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
long long x=0;
for(int i=1;i<=n;i++)
{
x+=a[i];
ans=max(x*1.0/i*x,ans);
}
printf("%lf\n",ans);
return 0;
}比较简单的贪心。
对于自己获得最多的方案，就是优先编号小的。
那么是不是对于亏的少的，是不是就是一直跑编号大的？
不不不，对于这个图，这种做法就会走上我们的“星光大道”，直接WA声一片。还是有46pts
那么正确的贪心思想是什么呢。
我们想，如果现在就是走一个小数字，然后走一个特大数字，花费为\(2\)，那么如果我先走目前最大的数字，把小数字免了，然后再走特大数字，是不是也是\(2\)，很明显，后者在多数情况会更优。
那么贪心策略出来了。
对于目前的编号最大值，我们把所有能走的编号小于最大值的点都走了，直到不能走，那么再走现在能走的点钟编号最大的，然后继续重复此过程。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 510000
using namespace std;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
struct node
{
int y,next;
}a[N];int len,last[N];
inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int n,m,in1[N],in2[N];
void findans1()
{
for(int i=1;i<=n;i++)
{
if(!in1[i])q2.push(i);
}
int mmax=0,T=n-1,ans=0;
while(T--)
{
int x=q2.top();q2.pop();
if(x>mmax)ans++,mmax=x;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;in1[y]--;
if(!in1[y])q2.push(y);
}
}
if(q2.top()>mmax)ans++;
printf("%d\n",ans);
}
int sta[N],tail;
void findans2()
{
for(int i=1;i<=n;i++)
{
if(!in2[i])q1.push(i);
}
int mmax=0,T=n,ans=0;
while(T)
{
int x=q1.top();q1.pop();
mmax=x;ans++;sta[tail=1]=x;
while(!q1.empty())sta[++tail]=q1.top(),q1.pop();
while(tail)
{
T--;
int y=sta[tail--];
for(int k=last[y];k;k=a[k].next)
{
int z=a[k].y;in2[z]--;
if(!in2[z])
{
if(z>mmax)q1.push(z);
else sta[++tail]=z;//能走我的点
}
}
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);in1[y]++;in2[y]++;
}
findans1();
findans2();
return 0;
}这道题目如果没有神犇提示根本做不出来。
首先我们有个很明显的思路，带修莫队。
首先这道题目我们很明显可以得到\(n\)个数对，就是说区间内只要有这些数对的话就是Yes，那么对于\(P_i=j\)，我们就可以得到数对\((i,j)\)。
那么我们就可以对于每一个位置\(i\)，分别对于两个可以和他组成数对的\(k_1,k_2\)，求出最小的区间\([i,j](j>i,a[j]=k_1ork_2)\)，那么我们就可以得到\(2n\)个区间，问题就转化为了，询问区间中是否包含一个小区间。
那么我们就可以对于每个\(r\)建一棵线段树，对于管理\(r\)的叶子节点，他存的是最大的\(l\)使得有\([l,r]\)这个区间。
而对于非叶子节点，就是左右儿子的最大值，其实就是当\(r\)在这个区间的时候，最大的\(l\)是多少，然后在询问的时候把询问区间的\(l\)传进去，在\(l,r\)中询问一下，如果发现一个节点被完全覆盖且\(c\)值大于等于\(l\)，那么就是有小区间。
讲真当时想出来这个，立马命名成ZJJ判断线段树，迈着嚣张的步伐，然后被神犇ZFY吐槽：这不就是个最大值线段树吗。。。
查询复杂度\(O(logn)\)
但是吉利扒拉了一大坨，如何修改？
对于修改位置\(i\)，把\(i\)的\(old\)值改成\(now\)值。
那么我们需要维护四个区间，一个是原来\(l\) \(or\) \(r\)是\(i\)的，以及新的\(l\) \(or\) \(r\)是\(i\)的。
那么对于原来\(r\)是\(i\)的我们要怎么维护？
我们先找到\(j(j>i,a[j]=old)\)，然后把\(i\)的值赋到\(j\)上就行了。
对于原本\(l\)是\(i\)的呢？我们对于两种数对分别找到了区间\([i,r_1],[i,r_2]\)，我们要明白一个事情，\(x\)位置作为\(r\)的话，那么他的最大的\(l\)就是两种对数方案的最大的\(l\)的最大值，那么我们只需要对于\(r_1,r_2\)重新找一遍就行了。
对于新的\(l\)是\(i\)的，我们随便搞一下就行了。
对于新的\(r\)是\(i\)的，我们需要跑到前面找找最接近他的两种值。
那么问题来了，我们怎么知道数值为\(x\)的下标最接近\(y\)的点下标是多少？
树套树？不要，空间时间都SB了。
仔细想想，貌似我们只要对于每种数值建一棵下标为键值的平衡树，节点总数是为\(n\)个节点的，妙啊。
所以时间复杂度就是\(O((n+m)logn)\)
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define N 510000
#define NN 1100000
using namespace std;
struct node
{
int lc,rc,l,r,c;
}tr[NN];int len;
void bt(int l,int r)
{
len++;int now=len;
tr[now].l=l;tr[now].r=r;
if(l<r)
{
int mid=(l+r)>>1;
tr[now].lc=len+1;bt(l,mid);
tr[now].rc=len+1;bt(mid+1,r);
}
}
inline int mymax(int x,int y){return x>y?x:y;}
int change(int now,int x,int k,int type/*type=0表示代替，type=1表示取max*/)//返回的是x的值
{
if(tr[now].l==tr[now].r){int ans=tr[now].c;type==0?tr[now].c=k:tr[now].c=mymax(tr[now].c,k);return ans;}
int mid=(tr[now].l+tr[now].r)/2,lc=tr[now].lc,rc=tr[now].rc,ans=0;
if(x<=mid)ans=change(lc,x,k,type);
else ans=change(rc,x,k,type);
tr[now].c=mymax(tr[lc].c,tr[rc].c);
return ans;
}
bool findans(int now,int l,int r,int k/*参数*/)//返回是否包含区间
{
if(tr[now].l==l && tr[now].r==r)return tr[now].c>=k;
int mid=(tr[now].l+tr[now].r)/2,lc=tr[now].lc,rc=tr[now].rc;
if(r<=mid)return findans(lc,l,r,k);
else if(mid<l)return findans(rc,l,r,k);
else return findans(lc,l,mid,k)|findans(rc,mid+1,r,k);
}
//线段树
class fhq//fhq treap万岁
{
public:
int size[N],vio[N],root[N],key[N],son[N][2];
inline void pushup(int x){size[x]=size[son[x][0]]+size[son[x][1]];}
void spilt(int now,int k,int &x,int &y)
{
if(!now)x=0,y=0;
else
{
if(key[now]<=k)x=now,spilt(son[x][1],k,son[x][1],y),pushup(x);
else y=now,spilt(son[y][0],k,x,son[y][0]),pushup(y),pushup(y);
}
}
int merge(int x,int y)
{
if(!x || !y)return x+y;
if(vio[x]<=vio[y])son[x][1]=merge(son[x][1],y);
else son[y][0]=merge(x,son[y][0]),x^=y^=x^=y;
pushup(x);return x;
}
void first_do(int x)
{
for(int i=1;i<=x;i++)size[i]=1,vio[i]=rand(),key[i]=i;
}
void add(int &rt,int id/*编号*/)
{
if(!rt)rt=id;
else
{
int x,y;spilt(rt,id,x,y);
rt=merge(merge(x,id),y);
}
}
void del(int &rt,int id)//从根为rt的树中分离id
{
int x,y,z;spilt(rt,id-1,x,y);spilt(y,id,y,z);
rt=merge(x,z);
}
int findqian(int &rt,int k/*查找k的前驱*/)
{
if(rt==0)return 0;
int x=rt,ans=0;
while(x)
{
if(key[x]>=k)x=son[x][0];
else if(key[x]<k)ans=x,x=son[x][1];
}
return ans;
}
int findhou(int &rt,int k/*查找k的前驱*/)
{
if(rt==0)return 0;
int x=rt,ans=0;
while(x)
{
if(key[x]>k)ans=x,x=son[x][0];
else if(key[x]<=k)x=son[x][1];
}
return ans;
}
}zjj;
int to[N][2],n,m;
int a[N],b[N];
int main()
{
srand(999);
scanf("%d%d",&n,&m);
zjj.first_do(n);bt(1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
to[i][0]=b[i];to[b[i]][1]=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
zjj.add(zjj.root[a[i]],i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=1;j++)
{
int x=zjj.findhou(zjj.root[to[a[i]][j]],i);//找到符合对数的数字。
if(x)change(1,x,i,1);
}
}
//建树
for(int i=1;i<=m;i++)
{
int type,l,r;scanf("%d%d%d",&type,&l,&r);
if(type==2)
{
if(findans(1,l,r,l)==true)printf("Yes\n");
else printf("No\n");
}//短短的询问
else
{
int x=0;
for(int j=0;j<=1;j++)x=mymax(x,zjj.findqian(zjj.root[to[r][j]],l));//代替数字
x=change(1,l,x,0);//表示替代原来的位置，并且获取到现在的位置
//以新的"l"为r的区间
int y=zjj.findhou(zjj.root[a[l]],l);
if(y)change(1,y,x,1);
//以旧的"l"为r的区间
zjj.del(zjj.root[a[l]],l);zjj.add(zjj.root[r],l);
//平衡树换点
for(int j=0;j<=1;j++)
{
int xx=to[a[l]][j];//表示与他有关的
y=zjj.findhou(zjj.root[xx],l);
if(y)
{
int z=0;
for(int k=0;k<=1;k++)z=mymax(z,zjj.findqian(zjj.root[to[xx][k]],y));//重新去找
change(1,y,z,0);
}
}
//以旧的"l"为l的区间
for(int j=0;j<=1;j++)
{
x=zjj.findhou(zjj.root[to[r][j]],l);//代替数字
if(x)change(1,x,l,1);
}
//以新的"l"为l的区间
a[l]=r;
}
}
return 0;
}【LGR-062】洛谷10月月赛 III div.2（赛后题解）
原文：https://www.cnblogs.com/zhangjianjunab/p/11753257.html