noip模拟63 solutions
不得不说，这两天确实挺带劲的
好像是因为我这两天做的梦都被我记住了，高兴的吧
昨天切了两个，今天切了一个，但是波波好像又说我们菜了
但是今天还有一个点，T2的暴力没有打，T3文件名点写成逗号
导致我还没有zxb暴力分高....
T1 电压机制
这个首先观察吧。。。
你发现这个可以没有电流的边一定在所有的奇数环中，一定不再任何一个偶数环中
所以你就直接搜就好了
直接差分记录每个边属于多少个奇数环
但是还有一个条件是对偶数环的限制，所以我们遇到偶数环就减掉，保证不在任意一个偶数环中
虽然应该直接判断是不是在偶数环中，但是这样在奇数环的计数器中减掉相当于变相的把他变得不合法了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e5+5;
const int M=2e5+5;
int n,m,ans;
int to[M*2],nxt[M*2],head[N],rp=1;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int dep[N],cir;
int ble[M*2],blp[N];
int vis[M*2],val[N];
void dfs(int x,int d){
dep[x]=d;
for(int i=head[x];i;i=nxt[i]){
if(vis[i])continue;
vis[i]=vis[i^1]=true;
int y=to[i];
if(dep[y]){
int tmp=dep[x]-dep[y]+1;
if(tmp&1){
ble[i]++;ble[i^1]++;
val[y]--;cir++;
}
else {
ble[i]--;ble[i^1]--;
val[y]++;
}
val[x]+=ble[i];
continue;
}
dfs(y,d+1);
ble[i]=ble[i^1]=val[y];
val[x]+=val[y];
}
}
signed main(){
#ifdef oj
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
fo(i,1,m){
int x,y;scanf("%d%d",&x,&y);
add_edg(x,y);add_edg(y,x);
}
dfs(1,1);
for(int i=2;i<=rp;i+=2)if(ble[i]==cir)ans++;
printf("%d",ans);
}
T2 括号密码
这个题并不是难在你去分析每一步如何去做
而是难在你要如何拆分这个区间，让他们变成许多互不相交但是可以包含的情况
这样子之后就可以从小到大处理，一个区间一个区间的处理
那么我们拆分的时候就直接将那些相交但是不包含的区间拆分成三个区间
然后我们对所有区间排好序，直接处理就好了
处理的时候先找到所有区间需要换啥，需要得到啥
先让这些区间内部解决一下，然后再从外面进口
针对匹配不上的情况，直接内部交换就好了，实现的时候细节非常非常的多，结束了。。。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2005;
char s[N];
int nn,n,len;
struct question{
int l,r;
question(){}
question(int x,int y){l=x;r=y;}
bool operator < (question a)const{
if(l==a.l)return r<a.r;
return l<a.l;
}
bool operator == (question a)const{
return l==a.l&&r==a.r;
}
}a[N],qus[N*N*5];
bool vis[N];
bool comp(question a,question b){
return a.r-a.l<b.r-b.l;
}
int in,ot,ans;
signed main(){
#ifdef oj
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
scanf("%s",s+1);len=strlen(s+1);
scanf("%d",&n);
fo(i,1,n){
scanf("%d",&a[i].l),a[i].l++;
vis[a[i].l]=true;
}
fo(i,1,n){
scanf("%d",&a[i].r),a[i].r++;
if(vis[a[i].r]){printf("-1");return 0;}
}nn=n;n=0;
fo(i,1,nn){
fo(j,1,nn){
if(a[i].l<a[j].l&&a[i].r>a[j].l&&a[i].r<a[j].r){
qus[++n].l=a[i].l;qus[n].r=a[j].l-1;
qus[++n].l=a[j].l;qus[n].r=a[i].r;
qus[++n].l=a[i].r+1;qus[n].r=a[j].r;
}
}
}
fo(i,1,nn)qus[++n].l=a[i].l,qus[n].r=a[i].r;
sort(qus+1,qus+n+1);n=unique(qus+1,qus+n+1)-qus-1;
sort(qus+1,qus+n+1,comp);
memset(vis,false,sizeof(vis));
fo(i,1,n){
int sum=0,mn=0;
fo(j,qus[i].l,qus[i].r){
if(vis[j])continue;
vis[j]=true;
if(s[j]=='(')sum++;
else sum--;
mn=min(mn,sum);
}
if(abs(sum)&1){printf("-1");return 0;}
if(sum>0)in+=sum/2;
else ot-=sum/2;
if(sum<0)mn-=sum;
if(mn<0){ans+=(abs(mn)+1)/2;}
}
int le=0,ri=0;
fo(i,1,len)if(s[i]=='('&&!vis[i])le++;
fo(i,1,len)if(s[i]==')'&&!vis[i])ri++;
if(in>ot&&ri<in-ot){printf("-1");return 0;}
if(in<ot&&le<ot-in){printf("-1");return 0;}
printf("%d",ans+max(in,ot));
}
T3 排列
这个考场上就想的是‘分治’，但是不是传统意义上的，就是对24种情况分别做就行了
主要将对于特殊情况的 \(2\ 4\ 1\ 3\) 的这个不能找到一个可以将值域和位置都卡在别的地方的情况
所以我们枚举3，用一个树状数组维护前面三个值
这里我们要用到两个树状数组，我们再前面的序列中枚举4在哪里，用树状数组维护4前面的和后面的
维护的时候就每一次挪动4的位置，就更新左右两侧的树状数组，这样就可以了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2005;
int n,a[N],b[N],ans;
int pre[N][N];
struct BIT{
int tr[N];
void ins(int x,int v){
for(int i=x;i<=n;i+=(i&(-i)))tr[i]+=v;
}
int query(int x){
int ret=0;
for(int i=x;i;i-=(i&(-i)))ret+=tr[i];
return ret;
}
void clear(){memset(tr,0,sizeof(tr));}
}x,y;
signed main(){
#ifdef oj
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
scanf("%lld",&n);
fo(i,1,4)scanf("%lld",&a[i]);
fo(i,1,n)scanf("%lld",&b[i]);
if(a[1]==4&&a[2]==3&&a[3]==2&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==3&&a[2]==4&&a[3]==2&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==4&&a[2]==2&&a[3]==3&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==2&&a[2]==4&&a[3]==3&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==3&&a[2]==2&&a[3]==4&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==2&&a[2]==3&&a[3]==4&&a[4]==1)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==4&&a[2]==3&&a[3]==1&&a[4]==2)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==3&&a[2]==4&&a[3]==1&&a[4]==2)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==4&&a[2]==1&&a[3]==3&&a[4]==2)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==3&&a[2]==1&&a[3]==4&&a[4]==2)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==4&&a[2]==2&&a[3]==1&&a[4]==3)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
if(a[1]==4&&a[2]==1&&a[3]==2&&a[4]==3)reverse(a+1,a+4+1),reverse(b+1,b+n+1);
fo(i,1,n)pre[i][b[i]]=1;
fo(i,1,n)fo(j,1,n)pre[i][j]+=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
if(a[1]==1&&a[2]==2&&a[3]==3&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]>b[j])continue;
int tmp1=pre[i-1][b[i]-1]-pre[0][b[i]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[n][n]-pre[n][b[j]]-pre[j][n]+pre[j][b[j]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==1&&a[2]==2&&a[3]==4&&a[4]==3){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]>b[j])continue;
int tmp1=pre[i-1][b[i]-1]-pre[0][b[i]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[j-1][n]-pre[j-1][b[j]]-pre[i][n]+pre[i][b[j]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==1&&a[2]==3&&a[3]==2&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[i-1][b[j]-1]-pre[0][b[j]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[n][n]-pre[j-1][n]-pre[n][b[i]]+pre[j-1][b[i]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==1&&a[2]==3&&a[3]==4&&a[4]==2){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[i-1][b[j]-1]-pre[0][b[j]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[j-1][n]-pre[i][n]-pre[j-1][b[i]]+pre[i][b[i]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==1&&a[2]==4&&a[3]==2&&a[4]==3){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[i-1][b[j]-1]-pre[0][b[j]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[n][b[i]-1]-pre[j][b[i]-1]-pre[n][b[j]]+pre[j][b[j]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==1&&a[2]==4&&a[3]==3&&a[4]==2){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[i-1][b[j]-1]-pre[0][b[j]-1]-pre[i-1][0]+pre[0][0];
int tmp2=pre[j-1][b[i]-1]-pre[i][b[i]-1]-pre[j-1][b[j]]+pre[i][b[j]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==2&&a[2]==1&&a[3]==3&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]>b[j])continue;
int tmp1=pre[j-1][b[i]-1]-pre[i][b[i]-1]-pre[j-1][0]+pre[i][0];
int tmp2=pre[n][n]-pre[j][n]-pre[n][b[j]]+pre[j][b[j]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==2&&a[2]==1&&a[3]==4&&a[4]==3){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]>b[j])continue;
int tmp1=pre[j-1][b[i]-1]-pre[i][b[i]-1]-pre[j-1][0]+pre[i][0];
int tmp2=pre[n][b[j]-1]-pre[j][b[j]-1]-pre[n][b[i]]+pre[j][b[i]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==2&&a[2]==3&&a[3]==1&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[i-1][b[i]-1]-pre[0][b[i]-1]-pre[i-1][b[j]]+pre[0][b[j]];
int tmp2=pre[n][n]-pre[j][n]-pre[n][b[i]]+pre[j][b[i]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==2&&a[2]==4&&a[3]==1&&a[4]==3){
fo(i,4,n){
x.clear();y.clear();
int sum=0;
fo(j,1,i-1)y.ins(b[j],1);
fo(j,1,i-2){
if(b[j]>b[i])ans+=sum;
else {
sum-=x.query(n)-x.query(b[j]);
sum+=y.query(b[j]-1);
y.ins(b[j],-1);
x.ins(b[j],1);
//cout<<sum<<" ";
}
}
}
}
if(a[1]==3&&a[2]==1&&a[3]==2&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]<b[j])continue;
int tmp1=pre[j-1][b[j]-1]-pre[i][b[j]-1]-pre[j-1][0]+pre[i][0];
int tmp2=pre[n][n]-pre[j][n]-pre[n][b[i]]+pre[j][b[i]];
ans+=tmp1*tmp2;
}
}
}
if(a[1]==3&&a[2]==2&&a[3]==1&&a[4]==4){
fo(i,1,n){
fo(j,i+1,n){
if(b[i]>b[j])continue;
int tmp1=pre[i-1][b[j]-1]-pre[0][b[j]-1]-pre[i-1][b[i]]+pre[0][b[i]];
int tmp2=pre[j-1][b[i]-1]-pre[i][b[i]-1]-pre[j-1][0]+pre[i][0];
ans+=tmp1*tmp2;
}
}
}
printf("%lld",ans);
}