考的烂得不行,还是应该多敲暴力搞分啊。。。
首先容易发现实际上是找去掉一条边后,剩下的是一个二分图的边数
然后发现这条边一定不在偶环上,一定在所有奇环上(或者根本没有奇环)
如果\(DFS\)显然不对,因为你没法打\(vis\),所以考场上想到这就跳了。。
实际上,这种跟环有关的,都可以借鉴一下\(tarjan\)的部分思想
比如我们搞出了\(DFS\)树,然后考虑非树边,由于是\(DFS\)树,而且是无向图,所以成环的边一定是返祖边,然后我们就可以通过树上查分来记录每条边在多少个奇环上
然后再考虑一下非树边,这里粘一下题解
也就是说当且仅当有一个奇环时,这个非树边才有贡献,特判即可
#include<cstdio> #include<cstring> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f; const int maxn=100005; const int maxm=500005; int n,m,dep[maxn],tim,tot=1,head[maxn],cf[maxn],odd; struct edge{int net,to;}e[maxm]; void add(int u,int v){ e[++tot].net=head[u]; head[u]=tot; e[tot].to=v; } bool vis[maxm]; void dfs(int u){ for(int i=head[u];i;i=e[i].net){ if(vis[i])continue; vis[i]=vis[i^1]=1; int v=e[i].to; if(dep[v]){ if((dep[u]-dep[v])%2){ ++cf[v];--cf[u]; }else{ --cf[v];++cf[u];++odd; } } else{dep[v]=dep[u]+1;dfs(v);} } } void dfs_2(int x){ for(int i=head[x];i;i=e[i].net){ int v=e[i].to; if(vis[v])continue; vis[v]=1; dfs_2(v); cf[x]+=cf[v]; } } int main(){ // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dep[1]=1; dfs(1); for(int i=1;i<=n;++i)printf("%d ",cf[i]);puts(""); for(int i=1;i<=n;++i)vis[i]=0; vis[1]=1;dfs_2(1); int ans=0; for(int i=2;i<=n;++i)ans+=cf[i]==odd?1:0; if(odd==1&&ans!=0)++ans; printf("%d\n",ans); return 0; }
显然有重叠的区间可以拆开,因为他们的交集必然合法
包含的区间,小区间必须合法(废话),大区间扔掉小区间后是个合法区间即可
区间长度为奇数无解
先考虑如何拆区间
考场假做法:对于第\(i\)个要求的区间,每个位置加上\(i\),然后根据每个位置的数字进行判断,假的
\(cd\)优化:把加\(i\)搞成进位取模,相当于一个\(hash\),可能能过
\(STL\)乱搞大法:原来\(STL\)还能这么用。。,对每个位置开一个\(vector\),每个要求往对应位置插\(i\),然后用map映射vector
对于包含区间,将区间按长度排序处理,打个\(vis\)即可
然后考虑处理一个区间,用栈模拟出来,统计\(cz\),\(cy\)表示有多少非法左右括号
其实可以发现,最后非法的串一定是\()))....(((\),我们需要尽少的次数使其合法,发现一次操作可以消去一对或者两对非法括号
我们尽可能消去两对,发现如果只剩下一个左/右括号时,我们必须操作一次消去这组非法括号
那么实际上我们可以直接写成\(ans+=(min(cz,cy)+1)/2\)
然后这时,这个区间至多有一种括号,而且一定为偶数个,我们先统计下来最后统一处理
处理时,考虑两个区间的左右括号,一次操作一定能消去两对,对于剩下的一种括号,我们必须从没有要求的区间里搞来不同的括号,我们只需要剩余括号数量/2个括号,也就是这么多次操作即可,记得判一下括号够不够用。
#include<map> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f; const int maxn=20000005; int vis[maxn],n,len,rm[maxn],cnt; char s[maxn]; struct op{int l,r,len;}o[maxn]; bool cmp(op x,op y){return x.len<y.len;} int zuo,you,ans,rem[maxn]; char sta[maxn];int top; vector<int>v[2005]; map<vector<int>,int>mp; int work(){ for(int i=1;i<=n;++i)if((o[i].r-o[i].l)%2==0)return -1; for(int i=1;i<=n;++i) for(int j=o[i].l;j<=o[i].r;++j)v[j].push_back(i); for(int i=0;i<len;++i){ if(v[i].size()==0)continue; if(mp[v[i]]==0){mp[v[i]]=++cnt;o[cnt].l=i;} o[mp[v[i]]].r=i; } for(int i=1;i<=cnt;++i){ o[i].len=o[i].r-o[i].l; if(o[i].len%2==0)return -1; } sort(o+1,o+cnt+1,cmp); for(int i=1;i<=cnt;++i){ top=0; for(int j=o[i].l;j<=o[i].r;++j){ if(rem[j]){j=rem[j];continue;} if(s[j]==')'&&top&&sta[top]=='(')--top; else sta[++top]=s[j]; } rem[o[i].l]=o[i].r; int cz=0,cy=0; for(int j=1;j<=top;++j)if(sta[j]=='(')++cz;else ++cy; if(cz>=cy){ans+=(cy+1)/2;you+=cz-cy;} else{ans+=(cz+1)/2;zuo+=cy-cz;} } int cz=0,cy=0; for(int i=0;i<len;++i){ if(rem[i]){i=rem[i];continue;} if(s[i]=='(')++cz; else ++cy; } zuo/=2;you/=2; if(zuo>=you){ ans+=you; zuo-=you; if(zuo>cz)return -1; else return ans+zuo; }else{ ans+=zuo; you-=zuo; if(you>cy)return -1; else return ans+you; } } int main(){ freopen("b.in","r",stdin); freopen("b.out","w",stdout); scanf("%s",s);len=strlen(s); scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&o[i].l); for(int i=1;i<=n;++i)scanf("%d",&o[i].r); printf("%d\n",work()); return 0; }
结论题,排序不等式,排序乘起来即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f; const int maxn=1000055; ll a[maxn],b[maxn],ans; int main(){ freopen("nj.in","r",stdin); freopen("nj.out","w",stdout); int n;scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%lld",&a[i]); for(int i=1;i<=n;++i)scanf("%lld",&b[i]); sort(a+1,a+n+1); sort(b+1,b+n+1); ll ans=0; for(int i=1;i<=n;++i)ans+=a[i]*b[i]; printf("%lld\n",ans); return 0; }
考场搞了三棵值域树状数组,还写挂了,后来发现前缀和一下就行了。。。
不过最后用的还是\(cdsidi\)大佬的解法
先考虑\(a[1],a[2]\)之间和\(a[3],a[4]\)之间的关系,(就是枚举所有二元组)
然后枚举\(a[1],a[2]\),在二维树状数组里查询即可,具体做法可以参考代码,赶进度,不详细写了。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f; const int maxn=5005; int n,a[11],b[maxn]; int q[maxn][maxn],h[maxn][maxn]; struct tree{ int t[maxn][maxn]; int lowbit(int x){return x&-x;} void add(int x,int y,int d){ if(d==0)return; for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) t[i][j]+=d; } int get(int x,int y){ int ans=0; if(x<=0||y<=0)return 0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ans+=t[i][j]; return ans; } int query(int x1,int x2,int y1,int y2){ return get(x2,y2)+get(x1-1,y1-1)-get(x1-1,y2)-get(x2,y1-1); } }T; void pushpos(int i){ if(a[3]<a[4]){for(int j=b[i]+1;j<=n;++j)if(h[b[i]][j])T.add(b[i],j,1);} else {for(int j=1;j<b[i];++j)if(h[b[i]][j])T.add(j,b[i],1);} } ll work(){ for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if((a[2]-a[1])*(b[j]-b[i])>0) q[b[i]][b[j]]=1; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if((a[4]-a[3])*(b[j]-b[i])>0) h[b[i]][b[j]]=1; int m1=min(a[1],a[2]),m2=max(a[1],a[2]); ll ans=0; for(int i=n-2;i>=2;--i){ pushpos(i+1); for(int j=1;j<=n;++j){ if(q[j][b[i]]==0)continue; int mi=min(b[i],j),mx=max(b[i],j); if(m1==1&&m2==2){ans+=T.query(mx+1,n,1,n);continue;} if(m1==1&&m2==3){ans+=T.query(mi+1,mx-1,mx+1,n);continue;} if(m1==1&&m2==4){ans+=T.query(mi+1,mx-1,mi+1,mx-1);continue;} if(m1==2&&m2==3){ans+=T.query(1,mi-1,mx+1,n);continue;} if(m1==2&&m2==4){ans+=T.query(1,mi-1,mi+1,mx-1);continue;} if(m1==3&&m2==4){ans+=T.query(1,mi-1,1,mi-1);continue;} } } return ans; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=4;++i)cin>>a[i]; for(int i=1;i<=n;++i)cin>>b[i]; cout<<work()<<'\n'; return 0; }