2019中國足協U13集訓，noip2019集訓測試賽（七）

Problem A: Maze

Time Limit: 1000 ms Memory Limit: 256 MB

Description

考慮一個N×M的網格，每個網格要么是空的，要么是障礙物。整個網格四周都是墻壁（即第1行和第n行，第1列和第m列都是墻壁），墻壁有且僅有兩處開口，分別代表起點和終點。起點總是在網格左邊，終點總是在網格右邊。你只能朝4個方向移動：上下左右。數據保證從起點到終點至少有一條路徑。

從起點到終點可能有很多條路徑，請找出有多少個網格是所有路徑的必經網格。

Input

第一行包含兩個整數 N,M，表示網格 N 行 M列。

接下來 N行，每行 M個字符，表示網格。'#'表示障礙物或墻壁，'.'表示空地。

Output

輸出文件包含一個整數，必經點的個數。

Sample Input
7 7
#######
....#.#
#.#.###
#.....#
###.#.#
#.#....
#######Sample Output
5

HINT

2019中國足協U13集訓，樣例解釋

(2, 1) (2, 2) (4, 4) (6, 6) (6, 7)

數據范圍與約定

對于10%的數據， 3≤N,M≤50

對于50%的數據， 3≤N,M≤500

對于所有數據， 3≤N,M≤1000

Solution

2019消防員集訓一年。先建個圖，然后tarjan割點

割點的時候判斷這個點在不在起點到終點的路上，如果不在就沒必要算入答案。

#include<bits/stdc++.h>
using namespace std;
struct qwq{int v;int nxt;
}edge[4000001];
int head[1000001];
int cnt=-1;
void add(int u,int v){edge[++cnt].nxt=head[u];edge[cnt].v=v;head[u]=cnt;
} 
int dfn[1000001];
int low[1000001];
int rt;
int ind;
int s,t;
bool pd[1000001];
bool tarjan(int u){dfn[u]=low[u]=++ind;int child=0;bool flag=false;for(int i=head[u];~i;i=edge[i].nxt){int v=edge[i].v;bool fflag=false;if(!dfn[v]){fflag=tarjan(v);flag=flag||fflag;low[u]=min(low[u],low[v]);if(dfn[u]<=low[v]&&fflag){pd[u]=true;}}low[u]=min(low[u],dfn[v]);}return flag||u==t;
}
bool mapn[1001][1001];
int movex[4]={0,1,0,-1};
int movey[4]={1,0,-1,0};
int main(){memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){char ch;cin>>ch;if(ch=='.'){mapn[i][j]=true;if(j==1){s=(i-1)*n+j;}if(j==n){t=(i-1)*n+j;}}}}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(!mapn[i][j])continue;for(int k=0;k<4;++k){int x=i+movex[k],y=j+movey[k];if(x<1||y<1||x>n||y>m||!mapn[x][y])continue;add((i-1)*n+j,(x-1)*n+y);}}}//cout<<s<<" "<<t<<endl;tarjan(s);int ans=0;for(int i=1;i<=n*m;++i){if(pd[i]){ans++;//cout<<i<<endl;}}printf("%d\n",ans+1);
}

Problem B: 懶人跑步

Time Limit: 1000 ms Memory Limit: 256 MB

Description

在ZJU，每個學生都被要求課外跑步，并且需要跑夠一定的距離 K，否則體育課會掛科。

ZJU有4個打卡點，分別標記為 p1,p2,p3,p4。每次你到達一個打卡點，你只需要刷一下卡，系統會自動計算這個打卡點和上一個打卡點的距離，并將它計入你的已跑距離。

系統把這4個打卡點看成一個環。 p1與 p2 相鄰、 p2 與 p3 相鄰、 p3 與 p4 相鄰、 p4 與 p1 相鄰。當你到達打卡點 pi時，你只能跑到與該打卡點相鄰的打卡點打卡。

打卡點 p2是離宿舍最近的一個打卡點。CJB總是從 p2 出發，并回到 p2 。因為CJB很圓，所以他希望他跑的距離不少于 K，但又要盡量小。

Input

數學中考專題分類集訓2019。第一行為一個整數 T，表示數據組數。

對于每組數據，有5個正整數 K,d1,2,d2,3,d3,4,d4,1(1≤K≤10^18,1≤d≤30000)，表示至少要跑的距離和每兩個相鄰的打卡點的距離。

Output

對于每組數據，輸出一個整數表示CJB最少需要跑多少距離。

Sample Input1
2000 600 650 535 380Sample Output2165

HINT

樣例解釋

最優路徑為 2?1?4?3?2

數據范圍與約定

信息學奧賽2019。對于30%的數據， 1≤K≤30000,1≤d≤30000

對于100%的數據， 1≤K≤10^18,1≤d≤30000,1≤T≤10

Solution

首先我們顯然可以在任意一條道路上來回摩擦

那么假設我們有一條長度為K的路徑，設w=min(dis(1,2),dis(2,3))，肯定有一條長度為k+2w的路徑

所以我們設dis[i][j]為到達某一個點，且dis[i][j]≡j(mod 2w)的最短距離

然后用類似最短路的方式更新，最后到達2號點的mod 2w的值最小的路徑的就好了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct data{int p;int m;
};
int d[4];
ll dis[4][100001];
bool vis[4][100001];
void spfa(int w){memset(dis,0x7f,sizeof(dis));//memset(vis,0,sizeof(vis));queue<data> q;q.push(data{1,0});dis[1][0]=0;vis[1][0]=true;while(!q.empty()){int p=q.front().p,m=q.front().m;int nxt=(p+1)%4,pre=(p+3)%4;//cout<<p<<" "<<m<<" "<<nxt<<" "<<pre<<endl;q.pop();vis[p][m]=false;if(dis[p][m]+d[p]<dis[nxt][(m+d[p])%w]){dis[nxt][(m+d[p])%w]=dis[p][m]+d[p];if(!vis[nxt][(m+d[p])%w]){q.push(data({nxt,(m+d[p])%w}));vis[nxt][(m+d[p])%w]=true;}}if(dis[p][m]+d[pre]<dis[pre][(m+d[pre])%w]){dis[pre][(m+d[pre])%w]=dis[p][m]+d[pre];if(!vis[pre][(m+d[pre])%w]){q.push(data{pre,(m+d[pre])%w});vis[pre][(m+d[pre])%w]=true;}}}
}
int main(){int T;scanf("%d",&T);while(T--){ll k;scanf("%lld%d%d%d%d",&k,&d[0],&d[1],&d[2],&d[3]);int w=min(d[0],d[1]);spfa(w*2);while(dis[1][k%(w*2)]>k)k++;printf("%lld\n",k);}
}

Problem C: 道路建設

Time Limit: 4000 ms Memory Limit: 512 MB

noip2018？

Sample Input5 7
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
4 7
11 12
11 13
18 19Sample Output3
9
8
14
13

HINT

樣例解釋

解密后的詢問為 (1,2),(1,4),(2,3),(3,5),(4,5)

修建道路最小費用的方案為 {(1,2),(4,5)},{(2,1),(1,5),(5,4),(4,3)},{(1,2),(1,5),(3,4)},{(1,5),(5,2),(2,3),(3,4)},{(3,2),(2,5),(1,4)}

數據規模與約定

子任務1（5分）： 1≤n,m,q≤1000,online=1

2019寒假作業。子任務2（11分）： 1≤n≤1000,1≤m,q≤10^5,online=0

子任務3（14分）： 1≤n≤1000,1≤m,q≤10^5,online=1

子任務4（21分）： 1≤n,m,q≤10^5,online=0

子任務5（49分）： 1≤n,m,q≤10^5,online=1

Solution

首先如果此題沒有強制在線，我們可以用LCT模擬建立最小生成樹的過程。

首先把邊權從大到小排序，不斷把邊插入LCT中，

2019年寒假作業、如果當前加入的邊與原來的邊構成了一個環，我們找到這個環上最大的邊去掉，然后加入這條邊。

現在我們要讓他能夠在線處理，那我們就建立一棵主席樹來方便查詢歷史版本。

然后每次查詢l,r只需要查詢版本為l且小于等于r的邊的和就可以了（因為在這個版本中比l小的還未加入進來）

有史以來寫過的最惡心的題

#include<bits/stdc++.h>
using namespace std;
struct node{int ch[2];int fa;int val;int tag;int mp;
}t[300001];
bool nroot(int x){return t[t[x].fa].ch[0]==x||t[t[x].fa].ch[1]==x;
}
void pushup(int x){t[x].mp=x;int lc=t[x].ch[0],rc=t[x].ch[1];if(t[t[lc].mp].val>t[t[x].mp].val)t[x].mp=t[lc].mp;if(t[t[rc].mp].val>t[t[x].mp].val)t[x].mp=t[rc].mp;
}
void rev(int x){swap(t[x].ch[0],t[x].ch[1]);t[x].tag^=1;
}
void pushdown(int x){if(t[x].tag){if(t[x].ch[0])rev(t[x].ch[0]);if(t[x].ch[1])rev(t[x].ch[1]);t[x].tag=0;}
}
void rotate(int x){int fa=t[x].fa;int gfa=t[fa].fa;bool k=t[fa].ch[1]==x;if(nroot(fa))t[gfa].ch[t[gfa].ch[1]==fa]=x;t[x].fa=gfa;t[fa].ch[k]=t[x].ch[k^1];if(t[x].ch[k^1])t[t[x].ch[k^1]].fa=fa;t[fa].fa=x;t[x].ch[k^1]=fa;pushup(fa);pushup(x);
}
int st[2000001];
void splay(int x){int y=x,z=0;st[++z]=y;while(nroot(y)){st[++z]=y=t[y].fa;}while(z)pushdown(st[z--]);while(nroot(x)){int fa=t[x].fa;int gfa=t[fa].fa;if(nroot(fa)){if((t[fa].ch[1]==x)^(t[gfa].ch[1]==fa))rotate(x);else rotate(fa);}rotate(x);}pushup(x);
}
void access(int x){int y=0;while(x){//cout<<y<<" "<<x<<" "<<t[x].fa<<endl;splay(x);t[x].ch[1]=y;pushup(x);y=x;x=t[x].fa;}
}
void makeroot(int x){access(x);splay(x);rev(x);
}
void link(int x,int y){makeroot(x);t[x].fa=y;
}
int cutmax(int x,int y){makeroot(x);access(y);splay(y);x=t[y].mp;splay(x);t[t[x].ch[0]].fa=t[t[x].ch[1]].fa=0;t[x].ch[0]=t[x].ch[1]=0;return x;
}
struct qwq{int u,v,w;
}edge[1000001];
bool operator <(qwq a,qwq b){return a.w>b.w;
}
int fa[100001];
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);
}
struct seg{int l,r,val; 
}tt[4000001];
int rt[10001];
int cnt;
void update(int now,int &root,int p,int v,int l,int r){root=++cnt;tt[root]=tt[now];tt[root].val+=v;if(l==r)return;int mid=(l+r)/2;if(p<=mid)update(tt[now].l,tt[root].l,p,v,l,mid);else update(tt[now].r,tt[root].r,p,v,mid+1,r);
}
int query(int now,int L,int R,int l,int r){if(now==0)return 0;if(L<=l&&r<=R)return tt[now].val;int mid=(l+r)/2;int ret=0;if(L<=mid)ret+=query(tt[now].l,L,R,l,mid);if(mid<R)ret+=query(tt[now].r,L,R,mid+1,r);return ret;
}
int main(){int n,m,online;scanf("%d%d%d",&n,&m,&online);for(int i=1;i<=m;++i){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);}sort(edge+1,edge+1+m);for(int i=1;i<=n;++i)fa[i]=i;int N=edge[1].w;for(int i=1;i<=m;++i){rt[edge[i].w]=rt[edge[i-1].w];int u=edge[i].u,v=edge[i].v;int x=findfa(u),y=findfa(v);int q;if(x==y){q=cutmax(u,v);update(rt[edge[i].w],rt[edge[i].w],t[q].val,-t[q].val,1,N);}else {fa[x]=y;q=i+n;}t[q].val=edge[i].w;t[q].mp=q;link(u,q);link(q,v);update(rt[edge[i].w],rt[edge[i].w],edge[i].w,edge[i].w,1,N);}for(int i=N;i>=2;i--){if(!rt[i-1]){rt[i-1]=rt[i];}}int q,last=0;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);l-=last*online;r-=last*online;printf("%d\n",last=query(rt[l],1,r,1,N));}
}