NOI2013部分题解

Day 1

T1:向量内积

直接暴力有60。发现将n个向量合成$n imes d$的矩阵$A$，然后求$A imes A^T$，得到的矩阵包含了所有的答案。

先考虑$k=2$，将答案矩阵和全1矩阵比较，为0的地方就是答案。

回忆一个十分经典的问题：判断$A imes B$是否与$C$相等。

先随机一个行向量v，若$v imes(A imes B)=v imes A imes B eq v imes C$，则直接返回$false$。多次随机，成功率为$1-(frac12)^{times}$。

这种随机化算法通常用于：某对命题充分性和必要性仅具备一个，所以多做几次判定就能提高正确率。$Miller-Rabin$算法就是一个典型的例子。

回到这道题，应用lych的话：

假设对于i，我们求出i之前的所有向量与i的点积的和；如果所有的点积都>0 即=1，那么显然点积的和对二取模=(i-1)%2；否则如果≠(i-1)%2，显然i与i前面的某一个向量的点积=0，我们O(ND)寻找答案即可。但 是这样不一定能得到解，我们不妨随机打乱向量的顺序然后判断，这样至少是1-(1/2)^5的正确率了。

问题在3怎么做，因为不为0可能意味着为1或2，不能确定答案，但是发现在模意义下$1^2equiv 2^2 (mod 3)$。所以只要平方一下就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=100010,M=110;
int n,m,mod,a[N][M],q[N],b[M],c[M][M];

bool check(int x,int y){
    int tmp=0;
    rep(i,1,m) tmp+=a[x][i]*a[y][i];
    return !(tmp%mod);
}

int solve(int x){
    int ans=0;
    if (mod==2)
        rep(i,1,m) ans^=b[i]&a[x][i],b[i]^=a[x][i];
    else
        rep(i,1,m) rep(j,1,m) ans+=c[i][j]*a[x][i]*a[x][j],c[i][j]+=a[x][i]*a[x][j];
    return ans%mod;
}

int main(){
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    scanf("%d%d%d",&n,&m,&mod);
    rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]),a[i][j]%=mod;
    rep(i,1,n) q[i]=i;
    for (int T=7-mod; T--; ){
        if (mod==2) memset(b,0,sizeof(b)); else memset(c,0,sizeof(c));
        rep(i,2,n) swap(q[i],q[rand()%(i-1)+1]);
        rep(i,1,n) if (solve(q[i])!=(i-1)%mod)
            rep(j,1,i-1) if (check(q[i],q[j])){
                if (q[i]>q[j]) swap(i,j);
                printf("%d %d
",q[i],q[j]); return 0;
            }
    }
    puts("-1 -1");
    return 0;
}

T2:树的计数

想不到的DP题，略。

T3:小Q的修炼

这个题由于我码力极弱，玩了两个小时只写出一个暴搜拿了20+分。

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=50,M=27;
int n,m,k,mx,tot,v[N],res[N],tmp[N];
char ch,cc,op;
struct P{ int op,a,b,c,d,u,v; }S[1000010];

void dfs(int x,int p){
    if (x>M) return;
    if (p<1 || p>n){
        if (v[1]>mx){ mx=v[1]; tot=x-1; rep(i,1,tot) res[i]=tmp[i]; }
        return;
    }
    int T[N],T2[N];
    rep(i,1,m) T[i]=v[i];
    while (1){
        if (S[p].op==1){
            int t=S[p].c;
            if (S[p].b==1) t=v[S[p].c];
            if (S[p].d) t=-t;
            v[S[p].a]+=t; p++;
            if (p<1 || p>n){
                if (v[1]>mx){ mx=v[1]; tot=x-1; rep(i,1,tot) res[i]=tmp[i]; }
                rep(i,1,m) v[i]=T[i];
                return;
            }
            continue;
        }
        if (S[p].op==3){
            int x1,x2;
            if (S[p].a==0) x1=S[p].b; else x1=v[S[p].b];
            if (S[p].c==0) x2=S[p].d; else x2=v[S[p].d];
            if (x1<x2) p=S[p].u; else p=S[p].v;
            if (p<1 || p>n){
                if (v[1]>mx){ mx=v[1]; tot=x-1; rep(i,1,tot) res[i]=tmp[i]; }
                rep(i,1,m) v[i]=T[i];
                return;
            }
            continue;
        }
        if (S[p].op==2){
            rep(i,1,m) T2[i]=v[i];
            tmp[x]=1; dfs(x+1,S[p].a);
            rep(i,1,m) v[i]=T2[i];
            tmp[x]=2; dfs(x+1,S[p].b);
            rep(i,1,m) v[i]=T[i];
            return;
        }
    }
}

int main(){
    freopen("train.in","r",stdin);
    freopen("train.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        scanf(" %c",&op);
        if (op=='v'){
            S[i].op=1; scanf("%d",&S[i].a);
            scanf(" %c %c",&cc,&ch);
            if (ch=='c') S[i].b=0; else S[i].b=1;
            scanf("%d",&S[i].c); if (cc=='-') S[i].d=1;
        }
        if (op=='s'){
            S[i].op=2; scanf("%d%d",&S[i].a,&S[i].b);
        }
        if (op=='i'){
            S[i].op=3;
            scanf(" %c",&ch);
            if (ch=='c') S[i].a=0; else S[i].a=1;
            scanf("%d",&S[i].b);
            scanf(" %c",&ch);
            if (ch=='c') S[i].c=0; else S[i].c=1;
            scanf("%d",&S[i].d);
            scanf("%d%d",&S[i].u,&S[i].v);
        }
    }
    dfs(1,1);
    rep(i,1,tot) printf("%d
",res[i]);
    return 0;
}

4,5,6都是DP，较复杂，略。

7,8,9,10是DP+暴力，略。

仔细观察第3个点，发现格式是每170行成为一段，段与段之间是互不影响的，所以直接段内暴搜，整体合并即可。

发现自己非常不擅长玩提答，稍微总结一下这种题的套路吧（虽然这种题没有太多套路）

1. 对码力要求较高，玩提答的时候动作一定要快，不能沉迷到游戏里去了。

2. 一般有这几种考察点：手玩，暴搜，贪心，DP，网络流，模拟退火。有些题里面会放数论算法的点。

3. 针对每个考察点需要注意的是：手玩不要搞复杂，感觉手玩比较难的时候不如考虑写暴搜。

4. 也不要一开始就急着先写暴搜，如果暴搜较复杂的话不如先看看后面的点。暴搜一般的收获是前两个点的满分和后面所有点的1~2分。

5. 一般不会有两个完全一样的点，但可能会有后面的点只是前面的代码稍作修改，或者要多跑一会而已。

6. 要多想DP和贪心，有时网络流和匈牙利也很有用。模拟退火+随机调整感觉凭自己水平还很难写出来，多写写随机化贪心。

7. 不要因为提答丢失了前面传统题的分。

Day 2

T1:矩阵游戏

最简单的一道题。首先已知f[i][1]可以通过等比数列求和公式轻松推出f[i][m]。然后合并系数可以轻松从f[1][1]得到f[n][1]，最后直接从f[n][1]推到f[n][m]即可。注意公比为1要特殊处理。

关于读入，由于n和m在公比不为1时是指数，为1时是系数，所以要边读边mod p或p-1。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int mod=1000000007;
int n,m,a,b,c,d,n1,m1,X,Y;
char s[1000010];

void Rd(int &n,int &n1){
    scanf("%s",s+1); int l=strlen(s+1); n=0; n1=0;
    rep(i,1,l) n=(n*10ll+s[i]-'0')%(mod-1),n1=(n1*10ll+s[i]-'0')%mod;
}

int ksm(int a,int b){
    int res=1;
    for (; b; a=1ll*a*a%mod,b>>=1)
        if (b&1) res=1ll*res*a%mod;
    return res;
}

void cal1(int a,int b,int n){ if (n<0) n+=mod; X=1; Y=1ll*n*b%mod; }
void cal(int a,int b,int n){ if (n<0) n+=mod-1; X=ksm(a,n); Y=1ll*(X-1)*ksm(a-1,mod-2)%mod*b%mod; }

int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    Rd(n,n1); Rd(m,m1); scanf("%d%d%d%d",&a,&b,&c,&d);
    if (a==1) cal1(a,b,m1-1); else cal(a,b,m-1);
    int p=X,q=Y,w=(p+q)%mod,u=1ll*c*p%mod,v=(1ll*c*q+d)%mod;
    if (u==1) cal1(u,v,n1-1); else cal(u,v,n-1);
    w=(1ll*X+Y)%mod; w=(1ll*p*w+q)%mod; printf("%d
",w);
    return 0;
}

T2:书法家

较复杂的DP，略。

T3:快餐店

首先如果是树，答案显然为直径的一半，这启发我们不要太深入的考虑环套树DP，而是使用常规的破环成树的方法。

显然所有点对间的最短路径可以都不经过某条边，枚举这条不需要的边，破环成树，在树上做前缀和与前缀最大值，再搞一搞就好了。

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long long ll;
using namespace std;

const int N=100010;
int n,cnt,tot,tim,u,v,w,dfn[N],fa[N],a[N],b[N],c[N],h[N],to[N<<1],nxt[N<<1],val[N<<1];
ll f[N],u1[N],u2[N],v1[N],v2[N],ans;
bool d[N];

void add(int u,int v,int w){ to[++cnt]=v; nxt[cnt]=h[u]; val[cnt]=w; h[u]=cnt; }

void dfs(int x){
    dfn[x]=++tim;
    For(i,x) if ((k=to[i])!=fa[x]){
        if (!dfn[k]){ fa[k]=x; c[k]=val[i]; dfs(k); }
        else if (dfn[k]>dfn[x]){
            for (; k!=x; k=fa[k]) d[k]=1,a[++tot]=k,b[tot]=c[k];
            d[x]=1; a[++tot]=x; b[tot]=val[i];
        }
    }
}

void DP(int x,int fa){
    For(i,x) if ((k=to[i])!=fa && !d[k])
        DP(k,x),ans=max(ans,f[x]+f[k]+val[i]),f[x]=max(f[x],f[k]+val[i]);
}

int main(){
    freopen("food.in","r",stdin);
    freopen("food.out","w",stdout);
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    dfs(1); ll sm=0,mx=0;
    rep(i,1,tot) DP(a[i],0);
    rep(i,1,tot){
        sm+=b[i-1]; u1[i]=max(u1[i-1],f[a[i]]+sm);
        v1[i]=max(v1[i-1],f[a[i]]+sm+mx);
        mx=max(mx,f[a[i]]-sm);
    }
    ll tmp=b[tot]; sm=mx=b[tot]=0;
    for (int i=tot; i; i--){
        sm+=b[i]; u2[i]=max(u2[i+1],f[a[i]]+sm);
        v2[i]=max(v2[i+1],f[a[i]]+sm+mx);
        mx=max(mx,f[a[i]]-sm);
    }
    ll mn=v1[tot];
    rep(i,1,tot-1) mn=min(mn,max(max(v1[i],v2[i+1]),u1[i]+u2[i+1]+tmp));
    ans=max(ans,mn); printf("%lld.%d
",ans>>1,(ans&1)?5:0);
    return 0;
}