T1 Merchant

一眼二分，然后想了想维护凸包，好像并没有什么关系，

然后又想了想维护一个栈，发现跳指针细节过多不想打

最后直接打了二分，大点跑的飞快，感觉比较稳，出来$78$分

是没用神奇的$\textit{nth_element}$导致排序时间长了，加上就$A$了

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

 2 #define int long long

 3 using namespace std;

 4 const int NN=1e6+5;

 5 int n,m,S,tmp1,zhi[NN];

 6 struct SNOW{int k,b;}p[NN];

 7 inline bool cmp1(SNOW a,SNOW b){return a.b==b.b?a.k>b.k:a.b>b.b;}

 8 inline bool cmp(int a,int b){return a>b;}

 9 inline bool check(int t){

10     int ans=0;

11     for(int i=1;i<=n;i++) zhi[i]=p[i].k*t+p[i].b;

12     nth_element(zhi+1,zhi+m+1,zhi+n+1,cmp);

13     for(int i=1;i<=m;i++){

14         if(zhi[i]<=0) continue;

15         ans+=zhi[i];

16         if(ans>=S) return 1;

17     }

18     if(ans<S) return 0;

19     else return 1;

20 }

21 namespace WSN{

22     inline short main(){

23 //        freopen("merchant3.in","r",stdin);

24         scanf("%lld%lld%lld",&n,&m,&S);

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

26             scanf("%lld%lld",&p[i].k,&p[i].b);

27             if(p[i].k<=0) ++tmp1;

28         }

29         if(tmp1==n){puts("0");return 0;}

30         sort(p+1,p+n+1,cmp1);int tot=0;

31         for(int i=1;i<=m;i++){

32             tot+=p[i].b;

33             if(tot>=S){puts("0");return 0;}

34         }

35         int l=0,r=1e9,ans=l;

36         while(l<=r){

37             int mid=l+r>>1;

38             if(check(mid)) ans=mid,r=mid-1;

39             else l=mid+1;

40         }printf("%lld\n",ans);

41         return 0;

42     }

43 }

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

没有鸭行的优秀代码

T2 Equation

大力的进行跳爹，期望加上个$spj$能多拿几分，只是因为思想太清奇把题想难了。。

直接用柿子等量带换往下推，能推出来加入的方程用$x_1$怎么表示，

然后发现可以直接预处理出来任意一个点的只关于$x_1$一个未知数的表达式里边的常量

用线段树维护这个常量即可实现对$x_1$的$log$级求解

发现对于一个深度为偶数的点，他满足奇加偶减（奇偶对于深度）的关系（就是那个求$x_1$的表达式）

那么我们只把所有的点当作偶点，进行维护，每次查询的时候判断一下新加入方程两点的深度奇偶性，适当进行反转即可

线段树要卡一下常，建议快读。。。

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

 2 #define lid (id<<1)

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

 4 #define LL long long

 5 #define rint register int

 6 using namespace std;

 7 inline LL read(){

 8     int x=0,f=1; char ch=getchar();

 9     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11     return x*f;

12 }

13 int n,q,w[1000001],sm[1000001],opt,uu,vv,xx,cha,dfn[1000001],dep[1000001],siz[1000001],cnt,head[1000001],rp;

14 LL ss,ans1,ans2;

15 struct SNOW{int to,next;};SNOW e[1000001];

16 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]}; head[x]=rp;}

17 struct SNOWtree{

18     LL sum[1000001<<2],laz[1000001<<2];

19     inline void pushdown(int id){

20         if(!laz[id]) return;

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

22         sum[lid]+=laz[id]; sum[rid]+=laz[id];

23         laz[id]=0;

24     }

25     inline void insert(int id,int l,int r,int pos,LL v){

26         if(l==r){sum[id]=v;return;}

27         int mid=l+r>>1;

28         if(pos<=mid) insert(lid,l,mid,pos,v);

29         else insert(rid,mid+1,r,pos,v);

30     }

31     inline void update(int id,int l,int r,int L,int R,int v){

32         if(L<=l&&r<=R){

33             sum[id]+=v*1ll;laz[id]+=v*1ll;

34             return;

35         }pushdown(id); int mid=l+r>>1;

36         if(R<=mid) update(lid,l,mid,L,R,v);

37         else if(L>mid) update(rid,mid+1,r,L,R,v);

38         else update(lid,l,mid,L,mid,v),update(rid,mid+1,r,mid+1,R,v);

39     }

40     inline LL query(int id,int l,int r,int pos){

41         if(l==r) return sum[id];

42         pushdown(id);int mid=l+r>>1;

43         if(pos<=mid) return query(lid,l,mid,pos);

44         else return query(rid,mid+1,r,pos);

45     }

46 }tr;

47 inline void dfs(int f,int x){

48     dep[x]=dep[f]+1; dfn[x]=++cnt; siz[x]=1;

49     (dep[x]&1)?(sm[x]=sm[f]-w[x]):(sm[x]=sm[f]+w[x]); tr.insert(1,1,n,dfn[x],sm[x]);

50     for(rint i=head[x];i;i=e[i].next) dfs(x,e[i].to),siz[x]+=siz[e[i].to];

51 }

52 namespace WSN{

53     inline short main(){

54 //        freopen("1.in","r",stdin);

55         n=read();q=read();

56         if(!q) return 0;

57         for(rint i=1,u;i<n;++i){

58             u=read(); w[i+1]=read();

59             add(u,i+1);

60         }dfs(0,1);

61         while(q--){

62             opt=read();

63             if(opt==2){

64                 uu=read();vv=read();

65                 cha=w[uu]-vv;w[uu]=vv;

66                 tr.update(1,1,n,dfn[uu],dfn[uu]+siz[uu]-1,(dep[uu]&1)?cha:-cha);

67                 continue;

68             }

69             if(opt==1){

70                 uu=read();vv=read();ss=read();

71                 ans1=tr.query(1,1,n,dfn[uu]),ans2=tr.query(1,1,n,dfn[vv]);

72                 if(dep[uu]&1) ans1=-ans1;

73                 if(dep[vv]&1) ans2=-ans2;

74                 ss-=ans1+ans2;

75                 xx=((dep[uu]&1)?1:-1)+((dep[vv]&1)?1:-1);

76                 if(!xx&&!ss){puts("inf");continue;}

77                 if(!xx||(ss*1.0/xx*1.0-ss/xx!=0)){puts("none");continue;}

78                 printf("%lld\n",ss/(xx*1ll));continue;

79             }

80         }

81         return 0;

82     }

83 }

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

T3 Rectangle

如果题解看不明白就看它

再不明白就看它

再再不明白就看：

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

 2 #define rin register int

 3 #define pii pair<int,int>

 4 #define mp make_pair

 5 #define val first

 6 #define num second

 7 using namespace std;

 8 inline int read(){

 9     int x=0,f=1; char ch=getchar();

10     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

11     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

12     return x*f;

13 }

14 const int p=1e9+7;

15 int n,maxn;

16 long long ans;

17 pii bin[5005];

18 bool vis[2505];

19 struct SNOW{int x,y;}s[10005];

20 vector<int> pos[2505];

21 struct tree{

22     pii tr[2505];

23     inline int lowbit(int x){return x&(-x);}

24     inline void update(int x,pii v){for(rin i=x;i<=2501;i+=lowbit(i)) tr[i].val+=v.val,tr[i].num+=v.num;}

25     inline pii query(int x){pii ans=mp(0,0);for(rin i=x;i;i-=lowbit(i)) ans.val+=tr[i].val,ans.num+=tr[i].num;return ans;}

26 }S[2505];

27 namespace WSN{

28     inline short main(){

29         n=read();

30         for(rin i=1;i<=n;++i){

31             s[i].x=read(),s[i].y=read();

32             pos[s[i].x].push_back(s[i].y);

33             maxn=max(maxn,s[i].x);

34         }

35         for(rin i=1;i<=maxn;++i) sort(pos[i].begin(),pos[i].end());

36         for(rin i=1;i<=maxn;++i){

37             memset(vis,0,sizeof(vis));

38             for(rin j=0;j<pos[i].size();++j) if(!vis[pos[i][j]]){

39                 S[i].update(pos[i][j],mp(pos[i][j],1));

40                 vis[pos[i][j]]=1;

41             }

42             for(rin j=i-1;j>=1;--j){

43                 int it1=0,it=0;

44                 for(rin k=0;k<pos[j].size();++k){

45                     if(!vis[pos[j][k]]){

46                         S[i].update(pos[j][k],mp(pos[j][k],1));

47                         vis[pos[j][k]]=1;

48                     }

49                     while(it1<pos[i].size()&&pos[i][it1]<pos[j][k]) bin[++it]=mp(pos[i][it1],0),++it1;

50                     bin[++it]=mp(pos[j][k],1);

51                 }

52                 while(it1<pos[i].size()) bin[++it]=mp(pos[i][it1],0),++it1;

53                 it1=it-1; int it0=2501;

54                 if(it1>=1){

55                     for(rin k=it;k>=it1;--k){

56                         while(it1>=1&&bin[k].num==bin[it1].num) --it1;

57                         if(it1){

58                             pii sum1,sum3=S[i].query(it0),sum4=S[i].query(bin[k].val-1);

59                             sum1=mp(sum3.val-sum4.val,sum3.num-sum4.num);

60                             pii sum2=S[i].query(bin[it1].val);

61                             (ans+=1ll*(i-j)*(sum1.val*sum2.num-sum2.val*sum1.num))%=p;

62                             it0=bin[k].val-1;

63                         }

64                         else break;

65                     }

66                 }

67             }

68         }

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

70         return 0;

71     }

72 }

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

巴特西

Noip模拟34 2021.8.9

T1 Merchant

T2 Equation

T3 Rectangle

最新文章

热门文章