首页 > 其他分享 >[USACO23JAN] Tractor Paths P 题解

[USACO23JAN] Tractor Paths P 题解

时间:2024-09-29 22:00:55浏览次数:7  
标签:Paths qr emplace int 题解 back USACO23JAN id

T4 [USACO23JAN] Tractor Paths P

唯二的两道蓝题之一,但难度至少紫黑之间。思路是这篇题解的。

首先一个贪心:跳到与当前区间相连的最靠右的区间肯定是最优的,由此倍增易得第一问。重点在于第二问的求解,我们发现这个东西很麻烦,这时候就需要一些寄巧了。具体来说,前人之述备矣。

坑点:DFS 序必须用 vector 存图,因为链式前向星存图是倒着存的,而这题我们需要用 DFS 序找所有的儿子,所以必须用 vector。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x))) 
#define lowbit(x) (x&-x)
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
string reads(){
	string s=" ";
	char ch=getchar();
	while(!isalnum(ch))ch=getchar();
	while(isalnum(ch))s+=ch,ch=getchar();
	return s;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('\n'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
constexpr int MAXN=2e5+5;
int n,q,totl,totr,F;
string s;
struct{int l,r;}a[MAXN];
int st[MAXN];
void add(int x,int k){
	while(x<=n)st[x]+=k,x+=lowbit(x);
}
int sum(int x){
	int res=0;
	while(x)res+=st[x],x-=lowbit(x);
	return res;
}
int fa[MAXN][31],dfn[MAXN],dfncnt;
vector<int>g[MAXN];
void dfs(int u){
	dfn[u]=++dfncnt;
	for(int i=1;i<=F;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v:g[u])dfs(v);
}
int dis[MAXN],ans[MAXN];
struct fk{
	int x,w,id;
	fk(int x,int w,int id):x(x),w(w),id(id){}
};
vector<fk>qr[MAXN];
void ad(int l,int r,int L,int R,int id){
	qr[r].emplace_back(R,1,id);
	qr[r].emplace_back(L-1,-1,id);
	qr[l-1].emplace_back(R,-1,id);
	qr[l-1].emplace_back(L-1,1,id);
}

int main(){
	n=read(),q=read(),s=reads();
	F=log2(n);
	for(int i=1;i<=n<<1;++i)
		if(s[i]=='L')a[++totl].l=i;
		else a[++totr].r=i;
	for(int i=2,pos=1;i<=n;++i)
		while(pos<i&&(i==n||a[i+1].l>a[pos].r)){
			fa[pos][0]=i;
			g[i].emplace_back(pos++);
		}
	dfs(n);
	s=reads();
	for(int i=1,x,y,tmp;i<=q;++i){
		x=read(),y=read();
		dis[i]=1;
		tmp=x;
		for(int j=F;~j;--j){
			if(!fa[x][j]||fa[x][j]>=y)continue;
			dis[i]+=1ll<<j,x=fa[x][j];
		}
		if(dfn[tmp]<dfn[y])ad(tmp,y,1,dfn[tmp],i),ad(tmp,y,dfn[y],n,i);
		else ad(tmp,y,dfn[y],dfn[tmp],i);
	}
	for(int i=1;i<=n;++i){
		if(s[i]=='1')add(dfn[i],1);
		for(auto x:qr[i])ans[x.id]+=sum(x.x)*x.w;
	}
	for(int i=1;i<=q;++i)write(dis[i],' '),write(ans[i]);
	return fw,0;
}

标签:Paths,qr,emplace,int,题解,back,USACO23JAN,id
From: https://www.cnblogs.com/laoshan-plus/p/18440843

相关文章

  • 题解:AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights
    题目传送门题目翻译给你一个NNN个点,MMM条边的有向图,其中边有边......
  • [2023四校联考3]sakuya 题解(根号分治)
    题目链接。题目分析第一个操作类似哈希冲突那一道题,可以运用类似的思路开一个二维表,很容易想到两种做法:开一个二维表,表上的第\(i\)行,第\(j\)列表示序列下标在模\(i\)意义下等于\(j\)的加法标记。对于修改操作,直接暴力修改对应的那一行的值即可,查询时用线段树查询那个......
  • 联考题解
    联考题解龙(dragon)难点:(1)删边后如何寻找新的最短路。(2)A,B两方的决策互相影响十分复杂。(3)如何统计每个起点的ans。解题:(3)解决这类多起点一终点的问题,可以想到dp。(1)解决这类最短路转移的问题,可以考虑最短路树。(2)解决这类博弈问题,可以设计两个dp数组,分别维护影响前后的ans,在转移......
  • [雅礼集训 2017 Day1]市场 题解
    题目链接题目分析听说是很典的一道题,很明显难点在于除法下取整的操作。类似花神那一道题,但是由于有区间加,所以无法进行暴力修改。很明显暴力复杂度爆炸,考虑下取整带来的性质:对于一对相邻的数,很明显有\(\lfloor\frac{x-1}{k}\rfloor\le\lfloor\frac{x}{k}\rfloor-1\)。......
  • i++和++i的区别,面试题解析
    i++和++i都是自增操作符,用于将变量的值增加1。i++是后增操作符,它首先返回变量的值,然后再将变量的值增加1。例如,如果i的初始值为1,执行i++后,i的值变为2。++i是前增操作符,它首先将变量的值增加1,然后再返回变量的值。例如,如果i的初始值为1,执行++i后,i的值变为2。区别在于返回值的......
  • CSP-J历年真题(部分)解析与题解
    目录序言:[CSP-J2020]直播获奖前言:题目描述输入格式输出格式输入输出样例说明/提示样例1解释数据规模与约定提示65分思路及代码前言:思路:代码:85分代码及思路:前言:插入排序:思路:代码: AC思路及代码:前言:思路:   代码: [CSP-J2022]乘方前言:题目描......
  • C语言 | Leetcode C语言题解之第445题两数相加II
    题目:题解:structListNode*addTwoNumbers(structListNode*l1,structListNode*l2){intstack1[100];intstack2[100];inttop1=0;inttop2=0;intcarry=0;intsum=0;structListNode*temp=NULL;structListNode*he......
  • C语言 | Leetcode C语言题解之第443题压缩字符串
    题目:题解:voidswap(char*a,char*b){chart=*a;*a=*b,*b=t;}voidreverse(char*a,char*b){while(a<b){swap(a++,--b);}}intcompress(char*chars,intcharsSize){intwrite=0,left=0;for(intr......
  • C++ | Leetcode C++题解之第445题两数相加II
    题目:题解:classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){stack<int>s1,s2;while(l1){s1.push(l1->val);l1=l1->next;}while(l2){......
  • C++ | Leetcode C++题解之第443题压缩字符串
    题目:题解:classSolution{public:intcompress(vector<char>&chars){intn=chars.size();intwrite=0,left=0;for(intread=0;read<n;read++){if(read==n-1||chars[read]!=chars[read......