ZJT's Blog

大変に気分がいい~

[自选题 #128] [Codeforces #736 D] Permutations

2017-12-26 20:112017-12-26 20:11
集训队作业自选题Codeforces高斯消元

传送门

垃圾题面,毁我青春好吧其实是我眼瞎qwq。。。

显然题目可以转化成一个模$2$意义下的行列式(其实是积和式,但是模$2$所以积和式等于行列式),每次把其中一个$1$变成$0$,问剩下的行列式。不难发现其实就是在问每个$1$的余子式。

一开始没看到保证行列式不为0,想了半天根本不会做,结果弃疗去看题解之后才发现看漏了。。。

可逆就能随便做了,直接求个逆,然后转置一下得到伴随矩阵然后就得到每个位置的余子式了。

然而不保证可逆的情况下怎么做啊,还是不会啊QAQ

哪位dalao会做的话请务必联系我qwq

#include <bits/stdc++.h>
#define MAXN 2010
using namespace std;

int n,m;
bitset<MAXN> a[MAXN],b[MAXN],temp;
int e[500010][2];

void gao(){
    for(int i=1;i<=n;i++){
        int pos=0;
        for(int j=i;j<=n;j++)
            if(a[j][i]) pos=j;
        if(i^pos){
            temp=a[pos];
            a[pos]=a[i];
            a[i]=temp;
            temp=b[pos];
            b[pos]=b[i];
            b[i]=temp;
        }
        for(int j=1;j<=n;j++)
            if(i!=j && a[j][i]){
                a[j]=a[j]^a[i];
                b[j]=b[j]^b[i];
            }
    }
}

int main(){
#ifdef DEBUG
    freopen("128.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[x][y]^1;
        e[i][0]=x; e[i][1]=y;
    }
    for(int i=1;i<=n;i++) b[i][i]=1;
    gao();
    for(int i=1;i<=m;i++){
        if(b[e[i][1]][e[i][0]]) puts("NO");
        else puts("YES");
    }
    return 0;
}

查看详细内容

[CF 853D]Michael and Charging Stations

2017-10-18 19:562017-10-18 19:56
Codeforces结论题二分答案

传送门

最近一直在不务正业,没怎么做AtCoder。打了几场cf的vp,状态都不怎么好,基本都是卡一题卡1h多都没做出来,赛后仔细想想就突然会做了。感觉还是场上心态不对,尤其是cf这种时间紧的比赛,看来还是要多打现场比赛才行。

这几天打的所有题卡我卡得最久的应该就是这题了,这题场上就有一堆人过了,然而我场上一直在瞎找结论,找了一些没什么用的结论,然后一直在想怎么dp,结果也没刚出来。赛后仔细想了想,发现有几个很明显的结论我场上都直接无视了,有这些结论就好做很多了。

第一个结论就是一定存在一个最优解,使得所有攒的积分都被用完。因为如果最后剩下的积分大于等于200,则随便把之前攒了积分的某天改成用积分,最后剩下的积分一定会减少,且答案不会变劣。如果最后只剩下100的积分,且前面存在某天攒了100积分,就可以把这天改成用积分,这样就不存在剩余积分了。否则,前面一定只要攒了积分就是攒200,这样的话根本不会出现剩100分(因为每次用都是200的倍数),这就矛盾了。

第二个结论是一定存在一个最优解,使得某个前缀里面每天都攒积分,并且这个前缀之后肯定只有连续且花费相等的一段是在攒积分,而其他时间都在用积分。这个的证明就是如果后面有两段,就根据前面的位置关系,可以把最后那一段的某个位置挪到前面去,然后就减少了最后一段的长度,直到把最后那些多出来的段删完为止。

有了这两个结论,我们直接枚举前缀的长度,然后二分后面那段的长度,看看能把积分用完的情况下最多能积多少分,然后就做完啦。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300010
using namespace std;

int n;
int a[MAXN],s[MAXN];
int f1[MAXN];
int next1[MAXN],next2[MAXN];
int ans=0;

int getS(int l,int r){ return s[r]-s[l-1]; }

void pre_gao(){
    int last1=n+1,last2=n+1;
    for(int i=n;i>=1;i--){
        next1[i]=last1;
        next2[i]=last2;
        if(a[i]==1) last1=i;
        else last2=i;
    }
}

void update(int x){
    if(x>ans) ans=x;
}

void gao(int x){
    if(getS(x+1,n)*10>=getS(1,x)) update(s[x]);
    if(next1[x]<=n){
        int s1=s[x],s2=getS(x+1,next1[x]-1);
        int s3=max(s1-10*s2,0);
        int l=next1[x],r=next2[next1[x]]-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getS(mid+1,n)*10>=s3+getS(next1[x],mid)) l=mid;
            else r=mid-1;
        }
        if(getS(l+1,n)*10>=s3+getS(next1[x],l))
            update(s1+getS(next1[x],l));
    }
    if(next2[x]<=n){
        int s1=s[x],s2=getS(x+1,next2[x]-1);
        int s3=max(s1-10*s2,0);
        int l=next2[x],r=next1[next2[x]]-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getS(mid+1,n)*10>=s3+getS(next2[x],mid)) l=mid;
            else r=mid-1;
        }
        if(getS(l+1,n)*10>=s3+getS(next2[x],l))
            update(s1+getS(next2[x],l));
    }
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]/=1000;
        s[i]=s[i-1]+a[i];
    }
    pre_gao();
    for(int i=1;i<=n;i++)
        gao(i);
    ans=s[n]*10-ans;
    printf("%d00\n",ans);
    return 0;
}

查看详细内容