T1 送花

按照题解意思说是扫描线题，但我觉得像一个线段树优化$dp$

主要思想一样，就是暴力枚举右端点，同时维护左端点的最值，

考虑两种情况，

如果左端点在$r$扫到的数$i$上一次出现的位置之前，

那么这个数是无法在区间$[l,r]$中作出贡献的

如果左端点在上次出现的位置之后，则可以作出贡献，

那么对应的操作就是

考虑从左往右扫答案的右端点，线段树维护每个左端点对应的答案

每次会让当前颜色的上上次出现位置到上次出现位置减掉贡献，上次出现位置到当前位置加上贡献

以后看到这种找最值区间的题目应该想到使用线段树维护，

线段树很方便的把一层枚举换成了$log$级别的

 1 #include<bits/stdc++.h>

 2 #define pb push_back

 3 #define LL long long

 4 using namespace std;

 5 const int NN=1e6+5;

 6 int n,m,c[NN],d[NN],pre[NN][2];

 7 LL ans;

 8 set<int> s[NN];

 9 struct SNOWtree{

10     #define lid (id<<1)

11     #define rid (id<<1|1)

12     int ll[NN<<2],rr[NN<<2];

13     LL maxn[NN<<2],laz[NN<<2];

14     inline void pushup(int id){

15         if(ll[id]==rr[id]) return;

16         maxn[id]=max(maxn[lid],maxn[rid]);

17     }

18     inline void pushdown(int id){

19         if(!laz[id]||ll[id]==rr[id]) return;

20         laz[lid]+=laz[id]; laz[rid]+=laz[id];

21         maxn[lid]+=laz[id]; maxn[rid]+=laz[id];

22         laz[id]=0;

23     }

24     void build(int id,int l,int r){

25         ll[id]=l;rr[id]=r;

26         if(l==r) return; int mid=l+r>>1;

27         build(lid,l,mid); build(rid,mid+1,r);

28     }

29     void update(int id,int l,int r,int val){

30         if(l<=ll[id]&&rr[id]<=r){

31             maxn[id]+=val,laz[id]+=val;

32             return;

33         }pushdown(id); int mid=ll[id]+rr[id]>>1;

34         if(l<=mid) update(lid,l,r,val);

35         if(r>mid) update(rid,l,r,val);

36         pushup(id);

37     }

38     LL query(int id,int l,int r){

39         if(l<=ll[id]&&rr[id]<=r) return maxn[id];

40         pushdown(id); int mid=ll[id]+rr[id]>>1;

41         LL ans=0;

42         if(l<=mid) ans=max(ans,query(lid,l,r));

43         if(r>mid) ans=max(ans,query(rid,l,r));

44         return ans;

45     }

46 }tr;

47 namespace WSN{

48     inline short main(){

49         scanf("%d%d",&n,&m);

50         for(register int i=1;i<=n;++i) scanf("%d",&c[i]);

51         for(register int i=1;i<=m;++i) scanf("%d",&d[i]);

52         tr.build(1,1,n);

53         for(register int i=1;i<=n;++i){

54             if(pre[c[i]][0]) tr.update(1,pre[c[i]][1]+1,pre[c[i]][0],-d[c[i]]);

55             tr.update(1,pre[c[i]][0]+1,i,d[c[i]]);

56             ans=max(ans,tr.query(1,1,n));

57             pre[c[i]][1]=pre[c[i]][0]; pre[c[i]][0]=i;

58         }

59         printf("%lld\n",ans);

60         return 0;

61     }

62 }

63 signed main(){return WSN::main();}

T2 星空

考场上看出关于一个点的斜坐标系上的点与这个点的距离为$0$之后，就考虑起维护凸包

然后就不明所以的去打别的题目了，还因为调试没改回来爆了$35$分

首先此题可以很显然的按照题意建出一个完全图，然后爱跑那个最短路算法跑那个

除了$Floyd$，就能拿$45$分

考虑正解我们把本题给出的距离定义换一下，

每个点的斜坐标系会和主坐标系有两个截距，我们设为$b1=y+x,b2=y-x$

那么吧原始柿子的绝对值拆开产生的$8$种不同情况，然后取最小值

刚好和以$b1,b2$为横，纵坐标系算出的$min(abs(x1-x2),abs(y1-y2))$得出的情况相同

所以换新的坐标来做

将距离为$0$的点按并查集合并，合并后只剩下距离不是$0$的点考虑他们的最小距离

每次分别按照$x,y$排序后，经典指针扫到每一个点后面第一个和他距离不为零的点更新答案

第二问就是在更新过程中记录点对，去重后将两并查集连起来，方案数明显是两个并查集的大小乘积

 1 #include<bits/stdc++.h>

 2 #define pii pair<int,int>

 3 #define fi first

 4 #define se second

 5 #define mp make_pair

 6 #define pb push_back

 7 using namespace std;

 8 const int NN=1e5+5;

 9 int n,fa[NN],siz[NN],vc[NN<<2][2];

10 vector<pii > ha[NN];

11 map<pii ,int> vis;

12 struct SNOW{int id,x,y;};SNOW s[NN],nw[NN];

13 inline bool cmp1(SNOW a,SNOW b){return a.x==b.x?a.y<b.y:a.x<b.x;}

14 inline bool cmp2(SNOW a,SNOW b){return a.y==b.y?a.x<b.x:a.y<b.y;}

15 inline int getfa(int x){return fa[x]=((fa[x]==x)?x:getfa(fa[x]));}

16 inline void merge(int x,int y){

17     x=getfa(x);y=getfa(y);

18     if(x==y) return;

19     fa[y]=x; siz[x]+=siz[y];

20 }

21 namespace WSN{

22     inline short main(){

23         scanf("%d",&n);

24         for(int i=1;i<=n;i++){

25             scanf("%d%d",&s[i].x,&s[i].y);

26             fa[i]=i,siz[i]=1;

27         }

28         for(int i=1;i<=n;i++){

29             int b1=s[i].y+s[i].x,b2=s[i].y-s[i].x;

30             if(vc[b1+2*NN][0]) merge(vc[b1+2*NN][0],i);

31             if(vc[b2+2*NN][1]) merge(vc[b2+2*NN][1],i);

32             vc[b1+2*NN][0]=vc[b2+2*NN][1]=i;

33             nw[i].x=b1; nw[i].y=b2; nw[i].id=i;

34         }

35         sort(nw+1,nw+n+1,cmp1);

36         int i=1,ans=0x3fffffff;

37         while(i<=n){

38             int j=i;while(getfa(nw[i].id)==getfa(nw[j].id)) ++j;

39             if(j>n){++i;continue;}

40             int res=min(abs(nw[i].x-nw[j].x),abs(nw[i].y-nw[j].y));

41             if(ans>=res){

42                 ans=res;

43                 int t=min(getfa(nw[i].id),getfa(nw[j].id));

44                 int u=max(getfa(nw[i].id),getfa(nw[j].id));

45                 ha[ans].pb(mp(t,u));

46             }++i;

47         }sort(nw+1,nw+n+1,cmp2); i=1;

48         while(i<=n){

49             int j=i;while(getfa(nw[i].id)==getfa(nw[j].id)) ++j;

50             if(j>n){++i;continue;}

51             int res=min(abs(nw[i].x-nw[j].x),abs(nw[i].y-nw[j].y));

52             if(ans>=res){

53                 ans=res;

54                 int t=min(getfa(nw[i].id),getfa(nw[j].id));

55                 int u=max(getfa(nw[i].id),getfa(nw[j].id));

56                 ha[ans].pb(mp(t,u));

57             }++i;

58         }if(ans==0x3fffffff){puts("-1");return 0;}

59         printf("%d\n",ans);

60         int sz=ha[ans].size(),tmp=0;

61         for(int i=0;i<sz;i++){

62             pii now=ha[ans][i];

63             if(vis[now]) continue;

64             vis[now]=1;

65             tmp+=siz[now.fi]*siz[now.se];

66         }printf("%d\n",tmp);

67         return 0;

68     }

69 }

70 signed main(){return WSN::main();}

T3 零一串

沽沽

巴特西

Noip模拟40 2021.8.15

T1 送花

T2 星空

T3 零一串

最新文章

热门文章