[JZOJ NOIP2018模拟10.20 A组]

由于T3数据出锅，还不清楚自己的分数...估分150，前100已经拿到了，T3的50没拍过（写的就是暴力怎么拍），感觉很不稳

考试的时候就是特别的困，大概是因为早上在房间里腐败...腐败完了才睡觉

T1：flow(CF990F)

题目链接：

http://172.16.0.132/senior/#contest/show/2533/0

题目：

你是申国的一个地方长官，你手下有n个城市。
为了加强基础设施建设，在2020全面建成小康社会，统筹推进经济建设、政治建设、文化建设、社会建设、生态文明建设，坚定实施科教兴国战略、人才强国战略、创新驱动发展战略、乡村振兴战略、区域协调发展战略、可持续发展战略、军民融合发展战略，突出抓重点、补短板、强弱项，特别是要坚决打好防范化解重大风险、精准脱贫、污染防治的攻坚战，使全面建成小康社会得到人民认可、经得起历史检验。你认为本省的水利调配非常有问题，这导致部分地区出现严重的缺水，而部分地区却全年洪灾泛滥。
于是你打算将原有的但是已经废弃了的m条水管重新使用。第i条水管连接城市xi和yi。这些水管联通了所有城市。每座城市对水的需求不同设为ai，部分城市处于缺水状态，ai为正，缺水量刚好为ai mol。部分城市因为有水库，ai为负，它需要向外输送-ai mol的水才能不形成洪灾。对于每条水管，你需要决定它的输送量fi，若fi为正则表示从xi向yi输送fi mol的水，fi为负则表示从yi向xi输送-fi mol的水。
你需要做到每个城市都刚好满足它的需求，即缺ai mol水的城市需要刚好输入ai的水，而多出-ai mol水的城市需要刚好输出-ai mol水。
你需要判断能否满足要求，若满足，你还需要输出所有的f。

题外话：

这题是签到题，考场上想想就过了。不过幸好考试快结束的时候手造了组数据，发现了一个bug，要不然就凉了。所以考试的时候还是要多检查一下，确保能得到的分不丢掉

题解：

随便搞一棵生成树，显然对于树的情况解是唯一的。这个时候发现非树边一点用都没有，直接当流量为0就行了

dfs一次，每次把儿子的贡献算到父亲上，再把儿子清空。如果有解的话根节点的值最后一定是0

这代码跑的还蛮快

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll; 

const int N=3e5+;

int n,m,tot;

int f[N],vis[N],head[N];

ll a[N],ans[N];

struct EDGE{

    int x,y;

}e[N];

struct E{

    int to,nxt,ty,id;

}edge[N<<];

inline ll read(){

    char ch=getchar();ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int find(int x){

    if (f[x]!=x) f[x]=find(f[x]);

    return f[x];

}

void link(int u,int v,int ty,int id) {edge[++tot]=(E){v,head[u],ty,id};head[u]=tot;}

void dfs(int x,int pre){

    for (int i=head[x];i;i=edge[i].nxt){

        int y=edge[i].to;

        if (y==pre) continue;

        dfs(y,x);

        if (a[y]<)

        {

            if (edge[i].ty==) ans[edge[i].id]=a[y];

            else ans[edge[i].id]=-a[y];

            a[x]+=a[y];a[y]=;

        }

        else if (a[y]>)

        {

            if (edge[i].ty==) ans[edge[i].id]=a[y];

            else ans[edge[i].id]=-a[y];

            a[x]+=a[y];a[y]=;

        }

    }

}

int main()

{

    //freopen("flow.in","r",stdin);

    //freopen("flow.out","w",stdout);

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

    m=read();

    for (int i=;i<=m;i++) e[i].x=read(),e[i].y=read();

    int cnt=;

    for (int i=;i<=n;i++) f[i]=i;

    for (int i=;i<=m;i++){

        int x=e[i].x,y=e[i].y;

        x=find(x);y=find(y);

        if (x!=y){

            vis[i]=;

            f[x]=y;

            link(e[i].x,e[i].y,,i);

            link(e[i].y,e[i].x,,i);

            ++cnt;

            if (cnt==n-) break;

        }

    }

    dfs(,);

    if (a[]!=) {puts("Impossible");return ;}

    puts("Possible");

    for (int i=;i<=m;i++)

        if (!vis[i]) printf("0\n");

        else printf("%lld\n",ans[i]);

    return ;

}

T2：Car(CF983E)

题目链接：

http://172.16.0.132/senior/#main/show/5918

题目：

作为申国的学生，你正在进行时事政治学习。
1.美国前国务卿是
A.希拉前 B. 希拉后 C.希拉里 D.希拉外
2.现任日本首相是
A.安倍晋一 B. 安倍晋二 C. 安倍晋三 D. 安倍晋四
3.现任申国国家元首是
A.吸寿瓶 B. 吸权瓶 C. 吸金瓶 D. 帘刃瓶
由于题目太难你不会做，你只好思考几天后的旅行问题。
有若干个城市形成一棵树的形状。
有若干辆双向班车往返于两个城市（中途经过的城市都会停）。
有人要从城市x到城市y，问最少坐几趟班车。
如果到不了，输出-1。

题外话：

纪中的政治颇有些敏感啊

题解：

预处理出每个点坐一次车最远能到哪个点（注意不能自己到自己），具体方法看代码

然后我们记录$f[x][i]$表示$x$坐$2^i$次车最远到哪个节点

对于一次询问$(x,y)$，把路径按lca拆成左右两部分。让$x$不断向上跳，直到跳到一个点在lca之下（不能跳到lca），对$y$也同样处理，求出现在跳的步数

设$x$跳到$a$，$y$跳到$b$，显然若存在一趟车包含这两个点$a,b$，那么答案就是当前步数+1，否则就是当前步数+2

问题转化为询问是否存在一条链跨过两个点

转化为dfs序上的问题，满足条件的链满足$st[a]<=l<=ed[a],st[b]<=r<=ed[b]$($st,ed$分别是节点的dfs序和子树中的最大dfs序，l,r分别是链的端点的dfs序)

这是一个二维数点问题，我们把$(l,r)$看成平面上一个点，问题就是矩形是否包含一个点

这个问题用树状数组+扫描线可以解决，具体实现就是把询问和修改按x排序，从左到右统计答案就是了，看看代码就理解了

这个我的代码跑的也挺快

#include<cstring>

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=2e5+;

int n,tot,tim,ask;

int head[N],dep[N],fa[N][],st[N],ed[N],f[N][],ans[N],ANS[N],tree[N];

struct EDGE{

    int to,nxt;

}edge[N<<];

struct node{

    int x,y,k,id;

}t[N<<];

bool operator <(node a,node b){return a.x<b.x||(a.x==b.x&&a.id<b.id);}

inline char nc(){

    static char buf[],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

}

inline int read(){

    char ch=nc();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=nc();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=nc();}

    return s*f;

}

void link(int u,int v){edge[++tot]=(EDGE){v,head[u]};head[u]=tot;}

void dfs1(int x,int pre){

    dep[x]=dep[pre]+;

    fa[x][]=pre;

    st[x]=++tim;

    for (int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];

    for (int i=head[x];i;i=edge[i].nxt){

        int y=edge[i].to;

        if (y==pre) continue;

        dfs1(y,x);

    }

    ed[x]=tim;

}

int lca(int x,int y){

    if (dep[x]<dep[y]) swap(x,y);

    for (int i=;i>=;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];

    if (x==y) return x;

    for (int i=;i>=;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

    return fa[x][];

}

void dfs2(int x,int pre){

    for (int i=head[x];i;i=edge[i].nxt){

        int y=edge[i].to;

        if (y==pre) continue;

        dfs2(y,x);

        if (!f[x][]||(f[y][]&&dep[f[x][]]>dep[f[y][]])) f[x][]=f[y][];

    }

}

void modify(int x,int y){

    while (x<=n){

        tree[x]+=y;

        x+=x&-x;

    }

}

int query(int x){

    int re=;

    while (x) {

        re+=tree[x];

        x-=x&-x;

    }

    return re;

}

int main(){

    n=read();

    for (int i=,u;i<=n;i++){

        u=read();

        link(i,u);link(u,i);

    }

    dfs1(,);

    int m=read();

    for (int i=;i<=m;i++){

        int x=read(),y=read();

        if (st[x]>st[y]) swap(x,y);

        int L=lca(x,y);

        if (!f[x][]||(dep[f[x][]]>dep[L])) f[x][]=L;

        if (!f[y][]||(dep[f[y][]]>dep[L])) f[y][]=L;

        t[++ask]=(node){st[x],st[y],,};

    }

    for (int i=;i<=n;i++) if (f[i][]==i) f[i][]=;

    dfs2(,);

    for (int i=;i<=n;i++) if (f[i][]==i||dep[f[i][]]>dep[i]) f[i][]=;

    for (int i=;i<;i++) for (int j=;j<=n;j++) f[j][i]=f[f[j][i-]][i-];

    int q=read();

    for (int k=;k<=q;k++){

        int x=read(),y=read(),L=lca(x,y);

        if (st[x]>st[y]) swap(x,y);

        for (int i=;i>=;i--) if (f[x][i]&&dep[f[x][i]]>dep[L]) x=f[x][i],ans[k]+=<<i;

        for (int i=;i>=;i--) if (f[y][i]&&dep[f[y][i]]>dep[L]) y=f[y][i],ans[k]+=<<i;

        if ((!f[x][]&&x!=L)||(!f[y][]&&y!=L)) {ans[k]=-;continue;}

        if (x==L||y==L) {ans[k]++;continue;}

        ans[k]+=;

        t[++ask]=(node){st[x]-,st[y]-,,k};

        t[++ask]=(node){st[x]-,ed[y],-,k};

        t[++ask]=(node){ed[x],st[y]-,-,k};

        t[++ask]=(node){ed[x],ed[y],,k};

    }

    sort(t+,t++ask);

    for (int i=;i<=ask;i++){

        if (!t[i].id){

            modify(t[i].y,t[i].k);

        }

        else {

            ANS[t[i].id]+=t[i].k*query(t[i].y);

        }

    }

    for (int i=;i<=q;i++) ans[i]-=(ANS[i]>);

    for (int i=;i<=q;i++) printf("%d\n",ans[i]);

    return ;

}

T3:moon(CF989E)

题目链接：

http://172.16.0.132/senior/#main/show/5917

题目：

作为申国的学者，你需要严格遵守三大基本原则：
战争即和平
自由即奴役
无知即力量
你正在对一本书进行审核，其中片段写道：
“少焉，月出于东山之上，徘徊于斗牛之间。白露横江，水光接天。纵一苇之所如，凌万顷之茫然。浩浩乎如冯虚御风，而不知其所止；飘飘乎如遗世独立，羽化而登仙。”
这种行为明显不符合三大原则，比如“纵一苇之所如”中自由的意思已经在新话中杯删除了。
但是你在修改的同时，发现书中夹着一道问题：
酥室等人现在的位置是(x,y)，同时还有n个景点，坐标分别为(xi,yi)。
每次移动按照下面的顺序操作：
1、选择一条直线，要求直线经过现在的位置和至少两个景点（如果现在在某个景点那里，也算一个）如果有多条直线满足要求，等概率选择一条。
2、在选择的这条直线中，等概率选择一个直线覆盖了的景点移动过去，如果目前在景点上，也有可能停住不动。
酥室会进行若干次询问，第i次询问从一个你选的任意点出发（可以不是景点），然后连续移动mi步，最后到达ti的最大概率是多少。

题外话：

老实说这题我是看别人标程才A掉的，矩阵乘法相关内容还有待加强，但我觉得这好像也不NOIP...志向只在NOIP的蒟蒻...

题解：

如果知道两个点之间一次性直接到达的概率$A_{i,j}$，那么记$f_{i,j}$为走$i$步到点$j$的概率，$f_{i,j}=\sum{k=1}{n} f_{i-1,k} \times A_{k,j} $，发现这是个矩阵乘法，可以快速幂优化

也就是我们定义转移矩阵$A$，$A_{i,j}$表示i走一次到j的概率。但是这样算我们显然还是会超时，根据矩阵乘法的结合律，我们可以预处理出从$i$走$2^p$次走到$j$的概率

首先我们考虑初始只走一次$A_{i,j}$怎么计算，显然$i,j$在同一直线上，令$tot_i$表示$i$经过$i$的直线的条数，$S$表示$i,j$所在直线上点的个数，显然$A_{i,j}=\frac{1.0}{S \times tot_i}$

这样预处理的时间复杂度是$O(n^3logm_i)$的

考虑对于每次询问，实际上我们都需要花一步走到一条线上，因此一开始步数要$-1$

然后我们把$m_i$二进制分解，用类似倍增的方法不断更新答案就好

当我们结束倍增之后，每条直线的贡献是固定的，而如果我们选的出发点在几个直线的交汇处，得到的便是这几条直线贡献的平均值，这不如直接选一条贡献最大的直线，而这总是可以做到的。因此输出答案最大的一条直线的答案即可。

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef double db;

const int N=+;

int n,cnt;

int inlin[N][N],tot[N];

db coef[N][N],tmp[N],prob[N];

struct point{

    db x,y;

}P[N];

struct Matrix{

    db a[N][N];Matrix () {mem(a,);};

}Bas[];

vector <int> list[N*N];

inline int read(){

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

bool cross(point a,point b,point c){

    return (a.y-b.y)*(b.x-c.x)==(a.x-b.x)*(b.y-c.y);

}

Matrix operator *(Matrix a,Matrix b)

{

    Matrix res;

    for (int i=;i<=n;i++)

        for (int j=;j<=n;j++)

            for (int k=;k<=n;k++) res.a[i][j]+=a.a[i][k]*b.a[k][j];

    return res;

}

void Init(){

    for (int i=;i<n;i++)

        for (int j=i+;j<=n;j++)

        if (!inlin[i][j]){

            list[++cnt].pb(i);list[cnt].pb(j);

            for (int k=j+;k<=n;k++) if (cross(P[i],P[j],P[k])) list[cnt].pb(k);

            for (int k=;k<list[cnt].size();k++) for (int l=;l<list[cnt].size();l++) inlin[list[cnt][k]][list[cnt][l]]=;

        }

    for (int i=;i<=cnt;i++)

        for (int j=;j<list[i].size();j++) ++tot[list[i][j]];

    for (int i=;i<=cnt;i++){

        int S=list[i].size();

        for (int j=;j<S;j++)

            for (int k=;k<S;k++)

                coef[list[i][j]][list[i][k]]+=1.0/tot[list[i][j]]/S;

    }

    for (int i=;i<=n;i++) for (int j=;j<=n;j++) Bas[].a[i][j]=coef[i][j];

    for (int i=;i<;i++) Bas[i]=Bas[i-]*Bas[i-];

}

db Answer(int times,int ver){

    if (!(--times)){

        for (int i=;i<=n;i++) prob[i]=(i==ver);

    }

    else {

        bool fg=true;

        for (int p=;p<;p++)

            if ((times>>p)&){

                if (fg) {fg=false;for (int i=;i<=n;i++) prob[i]=Bas[p].a[i][ver];}

                else {

                    for (int i=;i<=n;i++){

                        db cur=;

                        for (int j=;j<=n;j++) cur+=Bas[p].a[i][j]*prob[j];

                        tmp[i]=cur;

                    }

                    swap(prob,tmp);

                }

            }

    }

    db re=;

    for (int i=;i<=cnt;i++){

        db cur=;

        for (int j=;j<list[i].size();j++) cur+=prob[list[i][j]]/list[i].size();

        re=max(re,cur);

    }

    return re;

}

int main(){

    //freopen("moon.in","r",stdin);

    //freopen("moon.out","w",stdout);

    scanf("%d",&n);

    for (int i=;i<=n;i++) P[i]=(point){read(),read()};

    Init();

    int m=read();

    while (m--){

        int ver=read(),times=read();

        printf("%.12lf\n",Answer(times,ver));

    }

    return ;

}

巴特西

[JZOJ NOIP2018模拟10.20 A组]

T1：flow(CF990F)

题目链接：

题目：

题外话：

题解：

T2：Car(CF983E)

题目链接：

题目：

题外话：

题解：

T3:moon(CF989E)

题目链接：

题目：

题外话：

题解：

最新文章

热门文章