BruceJay's Blog

Bruce之NOIP模拟考梦魇系列一

| Comments

扯淡

运气好,运气好。

Day1

control

[Description]

在n*n的带权棋盘内放n个車,使得任意一个未放置車的位置都能被某个車攻击,求这n个車占据位置权值和的最大值。

[Hint]

[Solution]

分别求出每行最大值的和,和每列最大值的和。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 1010;
const int INF = 0x7f;
int Gpos[N]; ll Gmax[N];
int Fpos[N]; ll Fmax[N];
ll a[N][N]; ll ans1=0,ans2=0;
int n;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("control.in","r",stdin);
    freopen("control.out","w",stdout);
    n=read();
    memset(Gmax,-INF,sizeof(Gmax));
    memset(Fmax,-INF,sizeof(Fmax));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        a[i][j]=read();
        if(a[i][j]>Gmax[i]) {Gmax[i]=a[i][j],Gpos[i]=j;}
        if(a[i][j]>Fmax[j]) {Fmax[j]=a[i][j],Fpos[j]=i;}
    }
    for(int i=1;i<=n;i++) ans1+=Gmax[i],ans2+=Fmax[i];
    if(ans1>ans2){
        printf("%lld\n",ans1);
        for(int i=1;i<=n;i++) printf("%d %d\n",i,Gpos[i]);
    }
    else{
        printf("%lld\n",ans2);
        for(int i=1;i<=n;i++) printf("%d %d\n",Fpos[i],i);
    }
    return 0;
}

permu

[Description]

给定两个1~N的全排列A,B。有两个指针q和p,一开始q、p都为0,可执行以下三种操作:
1.q+1;2.p+1;3.q+1且p+1(Aq+1≠Bp+1时才可以这么做)。

[Hint]

[Solution]

很容易这题的DP方程
$$f[i][j]=f[i+1][j+1]+1,a[i+1]!=b[j+1]$$
$$f[i][j]=min(f[i+1][j],f[i][j+1])+1,a[i+1]==b[j+1]$$
对于第一种转移,我们可以简单地用队列处理:先将f[n][0~n]存在队列中,然后将f[n][0]出队,将f[n][1~n]++,变成f[n-1][0~n-1],再往队尾添加f[n-1][n],对f[i+1][0~n]转移到f[i][0~n]的情况亦然。
但这只是能解决第一种转移,第二种转移需要另作处理。对于f[i+1][0~n]到f[i][0~n]的转移,如果a[i+1]==b[j+1],f[i+1][j+1]就无法通过第一种转移转移到f[i][j]。对每个i,也存在且仅存在一个j,使得f[i][j]无法进行第一种转移(想一想,为什么?)。
对于第二种转移我们可以这样简化:
因为a[i+1]==b[j+1],所以a[i+1]!=b[j],所以f[i][j-1]==f[i+1][j]+1。
所以
有了这个方程,就可以在第一种转移完成后,找到使得a[i+1]==b[j+1]的j,取f[i][j]为队列中其前驱元素的值与其后继元素的值加1的较小值为f[i][j]的值。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000100;
int a[N]; int b[N]; int pos[N];
int q[N<<1]; int n;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("permu.in","r",stdin);
    freopen("permu.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++) pos[b[i]]=i;
    for(int i=0;i<=n;i++) q[i]=n-i;
    int head=0,tail=n;
    for(int i=n;i;i--){
        int t=pos[a[i]]; head++;
        q[head+t-1]=min(q[head+t-2],q[head+t]+1);
        q[++tail]=0;
    }
    printf("%d",n+q[head]);
    return 0;
}

pilgrims

[Description]

一棵n个节点的树,有m个神庙,其他点都是交通要道,每个神庙有一个朝圣者,每个朝圣者都想往离自己最远的任意一个神庙走。要封锁一个点,让尽量多的朝圣者走不到想去的神庙。

[Hint]

[Solution]

仍未解决。。。。顺手贴一发sumix173的标程

[Code]

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define dmp (A[c[x]] + e[x])
#define chet(x, y, z) if (x == Am)  a += z, n ^= y;  else  if (x == Bm)  b += z, m ^= y;
#define solve(t)    if (a == 1 &&  Am > 0)  {            \
     if (d == Am)  res[z] += t;                                   \
        else  mark[n] += t;                                                 \
    }                                                                                            \
    else  if (!a  &&  b == 1  &&  Bm > 0)  {          \
        if (d == Bm)  res[z] += t;                                   \
        else  mark[m] += t;                                                 \
    }
const int inf = (int) 1e9 + 10;
using namespace std;

typedef int arr32[600010];

arr32 A, B, c, t, next, g, e, tot, res, mark;
int n, m, x, y, z, ap, ans;

void link(int x, int y, int t)
{
    c[++ap] = y, next[ap] = g[x], g[x] = ap;  e[ap] = t;
    c[++ap] = x, next[ap] = g[y], g[y] = ap;  e[ap] = t;
}
void dfs(int z, int f)
{
    A[z] = B[z] = -inf;
    if (t[z])  A[z] = 0;
    
    for (int x = g[z]; x; x = next[x])
        if (c[x] != f)
            if (dfs(c[x], z), dmp > A[z])  B[z] = A[z], A[z] = dmp;
            else  B[z] = max(B[z], dmp);
}
void dfs(int z, int f, int d)
{
    int a = 0, b = 0, n = 0, m = 0;
    int Am, Bm;
    if (d > A[z])  Am = d, Bm = A[z];
    else  Am = A[z], Bm = max(B[z], d);
    
    for (int x = g[z]; x; x = next[x])
        if (c[x] != f)  {
            chet(dmp, c[x], 1);
            
            if (A[z] != dmp)  dfs(c[x], z, max(d, A[z]) + e[x]);
            else  dfs(c[x], z, max(d, B[z]) + e[x]);
        }

    chet(d, 0, 1);

    for (int x = g[z]; x; x = next[x])
        if (c[x] != f)  {
            tot[z] += res[c[x]];
            chet(dmp, c[x], -1);

            solve(res[c[x]]);
            
            chet(dmp, c[x], 1);
        }

    if (t[z])  solve(1); 
}
void calc(int z, int f)
{
    tot[z] += mark[z];
    if (!t[z])  ans = max(ans, tot[z]);

    int h = A[z] != B[z] ? mark[z] : 0;
    for (int x = g[z]; x; x = next[x])
        if (c[x] != f)
            if (dmp == A[z])  mark[c[x]] += h, calc(c[x], z);
            else  calc(c[x], z);
}
int main()
{
    freopen("pilgrims.in", "r", stdin);
    freopen("pilgrims.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)  scanf("%d", &x), t[x] = 1;
    for (int i = 1; i < n; ++i)  {
        scanf("%d %d %d", &x, &y, &z);
        link(x, y, z);
    }

    dfs(1, 0);
    dfs(1, 0, -inf);
    calc(1, 0);

    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i)
        if (!t[i]  &&  tot[i] == ans)  printf("%d\n", i);
}

Day2

four

[Description]

给定a,b,c,d,问是否存在一个数n,恰好有a个因数模4等于0,恰好有b个因数模4等于1,恰好有c个因数模4等于2,恰好有d个因数模4等于3。

[Hint]

[Solution]

这题需要非常复杂的推导,诸多条件,缺一不可。
先考虑将数n唯一分解,分解出来的质数分为3类:2,4p+1,4p+3。
先不考虑2,得出b与d的关系。对于4p+1类质数,无论其幂次是多少,对4的模值始终是1,设n的因数中,只含有4p+1类质数的数的个数为x。对于4p+3类质数,若其幂次和为奇数,其对4的模值是3,若其幂次和为偶数,其对4的模值是1。设使得4p+3类质数幂次和为奇数的方案数为odd,使得4p+3类质数幂次和为偶数的方案数为even,可以证明odd==even或odd==even-1(归纳法),所以我们可以得出b与d的关系:b与d相等,或b-d=x,即b!=0,b>=d,(b-d)|b,(b-d)|d。
a和c的关系就简单些了,考虑n对2的幂次,若为0,则a=0,c=0;若为1,则a=0,c=b+d(想一想,为什么?);若大于1,则c|a,c=b+d。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
ll a,b,c,d;

inline ll read()
{
    ll t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ll)ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("four.in","r",stdin);
    freopen("four.out","w",stdout);
    while(1){
        a=read(); if(a==-1) break;
        b=read(); c=read(); d=read();
        if(!b || b<d) {puts("0");continue;}
        if(b>d && (b%(b-d) || d%(b-d))) {puts("0");continue;}
        if(!c && !a) {puts("1");continue;}
        if(!c && a)  {puts("0");continue;}
        if(c!=b+d) {puts("0");continue;}
        if(!a) {puts("1");continue;}
        if(a%c) {puts("0");continue;}
        puts("1");
    }
    return 0;
}

sequence

[Description]

给定一个长为n的非负整数数列,求所有不降子序列的元素积的和(mod 10^9+7)。

[Hint]

[Solution]

考虑ans[i]为以i这个数结尾的不降子序列的元素积的和。对于当前数值,不难得出
$$ans[x]=(∑ans[y]+1)*x,(y<=x)$$
离散化后,树状数组即可。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100100;
const int Mod = 1000000007;
struct node{ll x; int id;}data[N];
bool cmp(const node& data1,const node& data2)
{return data1.x<data2.x;}
ll a[N]; ll tr[N]; ll ans[N]; int pos[N];
int n,cnt=0; ll tot=0;

inline ll read()
{
    ll t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ll)ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Update(int x,ll y)
{
    for(int i=x;i<=cnt;i+=(i&-i))
        tr[i]=(tr[i]+y+Mod)%Mod;
}

ll Query(int x)
{
    ll res=0;
    for(int i=x;i;i-=(i&-i))
        res=(res+tr[i])%Mod;
    return res;
}

int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) data[i].x=a[i];
    for(int i=1;i<=n;i++) data[i].id=i;
    sort(data+1,data+n+1,cmp);
    pos[data[1].id]=++cnt;
    for(int i=2;i<=n;i++)
        pos[data[i].id]=data[i].x==data[i-1].x?cnt:++cnt;
    for(int i=1;i<=n;i++){
        ll res=(Query(pos[i])+1)*(a[i]%Mod)%Mod;
        Update(pos[i],res-ans[pos[i]]); ans[pos[i]]=res;
    }
    for(int i=1;i<=cnt;i++) tot=(tot+ans[i])%Mod;
    printf("%lld",tot); return 0;
}

plr

[Description]

给定一张n个点m条边的有向图,定义0到n-1号节点的每条路径都要经过的边为“关键边”,用两条长为p的隧道覆盖任意一条0到n-1号节点的路径,使得被覆盖的“关键边”最长。

[Hint]

[Solution]

显然,覆盖要选择在最短路上覆盖。
先求“关键边”,先跑出一条最短路,所有“关键边”必然在这条最短路上。删去最短路上的边并建立其反向边,在新图中求SCC,如果某条最短路上的边的反向边没有被缩掉(其起点终点不在同一SCC),那么这条边就是“关键边”(想一想,为什么?)。
求覆盖就很简单了。覆盖的起点一定是最短路上的某一个点,只要考虑两种情况:一条长为2p的隧道连续覆盖,和两条长为p隧道分开覆盖。

[Code]

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
const int M = 200100;
const int INF = 0x7f;
struct Edge{int u,v,w,nxt;}a[M<<1];
int head[N]; int Dfn[N]; int Low[N];
int Stack[N]; bool InStack[N]; int belong[N];
int pre[N]; int dis[N]; bool vis[N];
int Scc,top,tot,cnt; queue<int> q;
int path[N]; bool mark[M<<1]; int f[N]; bool val[N];
int T,n,m,p;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,int w)
{
    a[++m].u=u; a[m].v=v; a[m].w=w;
    a[m].nxt=head[u]; head[u]=m;
}

void Spfa()
{
    memset(dis,INF,sizeof(dis));
    memset(pre,0,sizeof(pre));
    dis[0]=0; q.push(0); vis[0]=true;
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=false;
        for(int i=head[u];i;i=a[i].nxt){
            int v=a[i].v;
            if(dis[u]+a[i].w<dis[v]){
                dis[v]=dis[u]+a[i].w; pre[v]=i;
                if(!vis[v]) {q.push(v); vis[v]=true;}
            }
        }
    }
}

void Dfs(int u)
{
    if(!u) return; Dfs(a[pre[u]].u);
    path[++cnt]=a[pre[u]].u; mark[pre[u]]=true;
}

void Tarjan(int u)
{
    Dfn[u]=Low[u]=++tot;
    Stack[++top]=u; InStack[u]=true;
    for(int i=head[u];i;i=a[i].nxt){
        if(mark[i]) continue; int v=a[i].v;
        if(!Dfn[v]) Tarjan(v),Low[u]=min(Low[u],Low[v]);
        else if(InStack[v]) Low[u]=min(Low[u],Dfn[v]);
    }
    if(Dfn[u]==Low[u]){
        int v; Scc++;
        do{
            v=Stack[top--];
            InStack[v]=false;
            belong[v]=Scc;
        }while(v!=u);
    }
}

void Solve()
{
    int ans=0;
    int now=1,tmp=0;
    for(int i=1;i<=cnt;i++){
        while(now<cnt && dis[path[now+1]]-dis[path[i]]<=(p<<1)){
            if(val[now]) tmp+=dis[path[now+1]]-dis[path[now]];
            now++;
        }
        if(val[now]) ans=max(ans,tmp+(p<<1)-dis[path[now]]+dis[path[i]]);
        else ans=max(ans,tmp);
        if(val[i]) tmp-=dis[path[i+1]]-dis[path[i]];
    }
    now=1,tmp=0;
    for(int i=1;i<=cnt;i++){
        while(now<cnt && dis[path[now+1]]-dis[path[i]]<=p){
            if(val[now]) tmp+=dis[path[now+1]]-dis[path[now]];
            now++;
        }
        f[i]=tmp; if(val[now]) f[i]+=p-dis[path[now]]+dis[path[i]];
        if(val[i]) tmp-=dis[path[i+1]]-dis[path[i]];
    }
    now=1,tmp=0;
    for(int i=1;i<=cnt;i++){
        while(now<=cnt && dis[path[i]]-dis[path[now]]>p){
            tmp=max(tmp,f[now]); now++;
        }
        ans=max(ans,tmp+f[i]);
    }
    printf("%d\n",ans);
}

int main()
{
    freopen("plr.in","r",stdin);
    freopen("plr.out","w",stdout);
    T=read();
    while(T--){
        n=read(); m=read(); p=read();
        memset(head,0,sizeof(head));
        for(int i=1;i<=m;i++){
            a[i].u=read(); a[i].v=read(); a[i].w=read();
            a[i].nxt=head[a[i].u]; head[a[i].u]=i;
        }
        Spfa(); if(dis[n-1]==dis[n]){puts("-1"); continue;}
        memset(mark,false,sizeof(mark));
        cnt=0; Dfs(n-1); path[++cnt]=n-1;
        for(int i=1;i<=m;i++) if(mark[i]) Addedge(a[i].v,a[i].u,a[i].w);
        memset(Dfn,0,sizeof(Dfn)); tot=0,top=0,Scc=0;
        for(int i=0;i<n;i++) if(!Dfn[i]) Tarjan(i);
        memset(val,false,sizeof(val));
        for(int i=1;i<cnt;i++) if(belong[path[i]]!=belong[path[i+1]]) val[i]=true;
        Solve();
    }
    return 0;
}

Comments

comments powered by Disqus