第一题会卡一下同时用set和cin。。
其他的注意下矩阵对角线下标的应用即可
#include<bits/stdc++.h> using namespace std; #define maxn 2005 int mp1[maxn][maxn],n,m,mp2[maxn][maxn]; vector<int>s1[maxn],s2[maxn]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp1[i][j]),s1[i+j].push_back(mp1[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp2[i][j]),s2[i+j].push_back(mp2[i][j]); for(int i=2;i<=n+m;i++){ sort(s1[i].begin(),s1[i].end()); sort(s2[i].begin(),s2[i].end()); if(s1[i]!=s2[i]){ puts("NO"); return 0; } } puts("YES"); }
/* 问题可转化为有多少个点可以把最后一个点（n）推移上来 按位置将所有点排序，建立一个集合s 起初将最后一个点放在集合里，然后倒序访问之前的结点， 如果结点i可以将n推上来，那么之后的结点j再要将n推上来时就不用考虑i， 否则需要考虑j是否可以推到i后面，再然后将n推上来 如果之前结点i有边到达集合里的所有点，那么这个结点就可以把点n推上来， 如果不行，这个点i放入集合中 复杂度分析：每条边都会在集合里判断一次，mlogn */ #include<bits/stdc++.h> #include<set> using namespace std; #define maxn 500005 int m,n,pos[maxn],id[maxn]; set<int>s,G[maxn]; set<int>::iterator it; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&id[i]),pos[id[i]]=i; int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); G[u].insert(v); } int ans=0; s.insert(id[n]); for(int i=n-1;i>=1;i--){ int cur=id[i],flag=0; for(it=s.begin();it!=s.end();it++) if(G[cur].find(*it)==G[cur].end()){ flag=1; s.insert(cur); break; } if(!flag)ans++; } cout<<ans<<endl; }
e也太难了。。留个坑吧
补坑。。区间覆盖线段树调了半天，最后发现有个地方没写long long ...气死我了.
所以总结一下，，区间覆盖和区间更新的pushdown还是有点差距的，，还有本题的lazy初始值要设为INF
/* 给定数组a1...an, k1...kn-1 两种操作： 第一种为ai+x，完成本次操作后若ai+1<ai+ki,则ai+1=ai+ki，以此类推 即后面的数不得小于前面的数+ki 第二种为求和操作 推导公式可得a1<=a2-sumk1<=a3-sumk2<=a4-sumk3...<=an-sumkn-1 令 bi=ai-sumki-1 b1<=b2<=b3<=b4...<=bn ai+x <=> bi+x,同时所有在bi后面且小于bi+x的数都要变成bi+x 所以直接用lower_bound找到第一个不小于bi+x的数 用线段树维护bi，进行区间覆盖操作 query时先query 区间bi的和，再使用前缀和求出区间sumki的值 注意lazy */ #include<bits/stdc++.h> using namespace std; #define maxn 200005 #define ll long long ll n,m,a[maxn],k[maxn],b[maxn],sumk[maxn],sumkk[maxn]; #define INF 1e18 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 ll sum[maxn<<2],lazy[maxn<<2]; inline void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } inline void pushdown(int l,int r,int rt){ if(lazy[rt]!=INF+1){ int m=l+r>>1; sum[rt<<1]=lazy[rt]*(m-l+1); sum[rt<<1|1]=lazy[rt]*(r-m); lazy[rt<<1]=lazy[rt]; lazy[rt<<1|1]=lazy[rt]; lazy[rt]=INF+1; } } void build(int l,int r,int rt){ lazy[rt]=INF+1; if(l==r){sum[rt]=b[l];return;} int m=l+r>>1; build(lson);build(rson); pushup(rt); } void modify(int L,int R,ll val,int l,int r,int rt){ if(L<=l&&R>=r){ lazy[rt]=val;sum[rt]=val*(r-l+1); return; } pushdown(l,r,rt); int m=l+r>>1; if(L<=m)modify(L,R,val,lson); if(R>m)modify(L,R,val,rson); pushup(rt); } ll query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r)return sum[rt]; pushdown(l,r,rt); int m=l+r>>1; ll res=0; if(L<=m)res+=query(L,R,lson); if(R>m)res+=query(L,R,rson); return res; } void add(int i,ll val){ if(val==0)return; ll cur=query(i,i,1,n,1)+val;//查询第l个点当前值 int l=i,r=n,mid,ans=l;//查询最右边的比cur小的数 while(l<=r){ mid=l+r>>1; if(query(mid,mid,1,n,1)<cur) ans=mid,l=mid+1; else r=mid-1; } modify(i,ans,cur,1,n,1); } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<n;i++)cin>>k[i]; for(int i=2;i<=n;i++)sumk[i]=sumk[i-1]+k[i-1]; for(int i=1;i<=n;i++)b[i]=a[i]-sumk[i]; for(int i=2;i<=n;i++)sumkk[i]=sumkk[i-1]+sumk[i]; build(1,n,1); cin>>m; while(m--){ char op[2];ll l,r; cin>>op>>l>>r; if(op[0]=='+')add(l,r); else cout<<query(l,r,1,n,1)+sumkk[r]-sumkk[l-1]<<" "; } return 0; }