模拟赛 29

T1

模拟即可，请输入文本。

点击查看代码

#include<bits/stdc++.h>
#define MAXN 10005
#define int long long
using namespace std;
const int inf=1e18;
string tmp,ans[20];
int T,n,cnt,pos;
char c[1005];
signed main(){freopen("address.in","r",stdin);freopen("address.out","w",stdout);scanf("%lld",&T);while(T--){cnt=0,pos=-1;scanf("%s",c+1);n=strlen(c+1);tmp="";for(int i=1;i<=n;i++){if(c[i]==':'){if(tmp=="")pos=cnt;else{ans[++cnt]="";for(int j=1;j<=4-tmp.size();j++)ans[cnt]+="0";ans[cnt]+=tmp;tmp="";}}else{tmp+=c[i];}}if(tmp!=""){ans[++cnt]="";for(int j=1;j<=4-tmp.size();j++)ans[cnt]+="0";ans[cnt]+=tmp;}if(pos==0){for(int i=1;i<=8-cnt;i++){cout<<"0000";if(i!=8)cout<<":";}}for(int i=1;i<=cnt;i++){cout<<ans[i];if(i!=cnt||pos==i)cout<<":";if(pos==i){for(int j=1;j<=8-cnt;j++){cout<<"0000";if(j!=8-i)cout<<":";}}}cout<<"\n";}return 0;
}

T2

图呢？？？？？

题面

P11791 [JOI 2017 Final] 准高速电车 / Semiexpress

题目描述

JOI 铁路公司是 JOI 国唯一的铁路公司。

在某条铁路沿线共有 \(n\) 个站点，依次编号为 \(1,2,\cdots, n\)。当前有两种列车服役，分别是高速列车和普通列车。

• 普通列车每站都停，对于每一个 \(i(1\leq i < N)\)，从站点 \(i\) 到站点 \(i+1\) 用时 \(A\) 分钟。

• 高速列车只在站点 \(S_1,S_2,\cdots,S_M(1=S_1<S_2<\cdots<S_M=N)\) 停车，对于每一个 \(i(1\leq i < N)\)，从站点 \(i\) 到站点 \(i+1\) 用时 \(B\) 分钟。

JOI 铁路公司拟定开设第三类车次：准高速列车。对于每一个 \(i(1\leq i < N)\)，从站点 \(i\) 到站点 \(i+1\) 用时 \(C\) 分钟。准高速列车停的站点还没有决定好，但是这些站点必须满足以下要求：

• 高速列车停的所有站点准高速列车都必须停。

• 准高速列车必须停恰好 \(K\) 个站点。

JOI 铁路公司想要最大化从 \(1\) 号站点在 \(T\) 分钟内可以到的站点数目（不计 \(1\) 号站点，不计等车和换乘时间），JOI 铁路公司想要合理地安排站点使得这个数目最大。

当合理地安排准高速列车停的站点时，从 \(1\) 号站点出发在 \(T\) 分钟内抵达的站点（\(1\) 号站点不计）最多是多少？

输入格式

第一行三个整数 \(N,M,K\)，意义如题面所示。

第二行三个整数 \(A,B,C\)，意义如题面所示。

第三行一个整数 \(T\)，意义如题面所示。

接下来 \(M\) 行，这 \(M\) 行中的第 \(i\) 行有一个整数 \(S_i\)，表示快车停的站点。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

10 3 5
10 3 5
30
1
6
10

输出 #1

8

输入输出样例 #2

输入 #2

10 3 5
10 3 5
25
1
6
10

输出 #2

7

输入输出样例 #3

输入 #3

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

输出 #3

2

输入输出样例 #4

输入 #4

12 3 4
10 1 2
30
1
11
12

输出 #4

8

输入输出样例 #5

输入 #5

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

输出 #5

72

输入输出样例 #6

输入 #6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

输出 #6

3000

说明/提示

【样例解释】

对于样例 \(1\)，一共有 \(10\) 个站点，快车停 \(1,6,10\) 三个站点。我们假设准快车停 \(1,5,6,8,10\) 五个站点，于是，在 \(2,3,\cdots,10\) 中，我们可以从 \(1\) 号站点在 \(30\) 分钟内抵达除了 \(9\) 号站点的所有站点。

对于某些 \(i\)，从 \(1\) 号站点到 \(i\) 号站点最优的方案如下：

• 从 \(1\) 号站点到 \(3\) 号站点，只需要乘坐普通列车，时间为 \(20\) 分钟。

• 从 \(1\) 号站点到 \(7\) 号站点，先乘坐高速列车到站点 \(6\)，然后转乘普通列车，时间为 \(25\) 分钟。

• 从 \(1\) 号站点到 \(8\) 号站点，先乘坐高速列车到站点 \(6\)，然后转乘准高速列车，时间为 \(25\) 分钟。

• 从 \(1\) 号站点到 \(9\) 号站点，先乘坐高速列车到站点 \(6\)，然后转乘准高速列车到站点 \(8\)，再换乘普通列车，时间为 \(35\) 分钟。

【数据范围与约定】

所有的数据满足以下条件：

• \(2\leq N\leq 10^9,2\leq M\leq K\leq 3000,K\leq N\)。

• \(1\leq B < C < A \leq 10^9,1\leq T\leq 10^{18}\)。

• \(1=S_1<S_2<\cdots<S_M=N\)。

1. Subtask \(1\)（\(18\) pts）：\(N\leq 3000,K-M=2,A\leq 10^6,T\leq 10^9\)。

2. Subtask \(2\)（\(30\) pts）：\(N\leq 300\)。

3. Subtask \(3\)（\(52\) pts）：无特殊限制。

感觉不是很难。首先发现到达一个站的最快方法肯定是先坐高速列车到该站之前的最近的站，然后再坐准高速到该站之前的最近的站，最后做普通到该站。然后就从每个高速站往后考虑，有一段普通列车就可以覆盖的区间，直接不管，如果在这个区间的下一个站放一个准高速的站的话从新站做普通列车往后走又可以覆盖一段区间，这就是新站的收益。显然由于普通车速严格小于准高速，因此这个新站往前或往后都是不优的。新站后再建新站的收益计算同理，这样我们就可以建一个优先队列维护每个待建新站的收益，直接贪即可。

点击查看代码

#include<bits/stdc++.h>
#define MAXN 3005
#define int long long
#define pi pair<int,int>
#define mk make_pair 
using namespace std;
const int inf=1e18;
int n,m,k,a[MAXN],A,B,C,T,ans,b[MAXN];
priority_queue<pi,vector<pi>,less<pi> >q;
int que(int lst,int x,int nxt){int pt=(lst-1)*B;if(T-pt<0)return 0;int nt=T-pt-(x-lst)*C;if(nt<0)return 0;int nans=nt/A+1;nans=min(nans,nxt-x);
//	cout<<lst<<' '<<x<<' '<<nxt<<' '<<nans<<"!!!\n";return nans;
}
signed main(){freopen("express.in","r",stdin);freopen("express.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&k);scanf("%lld%lld%lld",&A,&B,&C);scanf("%lld",&T);for(int i=1;i<=m;i++)scanf("%lld",&a[i]);a[m+1]=n+1;k-=m;for(int i=1;i<=m;i++){int nans=que(a[i],a[i],a[i+1]);if(nans>0){ans+=nans;int nx=a[i]+nans;if(nx<a[i+1]){int tans=que(a[i],nx,a[i+1]);if(tans>0)b[i]=nx,q.push(mk(tans,i));}}}//cout<<ans<<"\n";while(k&&!q.empty()){k--;int tans=q.top().first,x=q.top().second;q.pop();ans+=tans;int nx=b[x]+tans;if(nx>=a[x+1])continue;int nans=que(a[x],nx,a[x+1]);if(nans>0)b[x]=nx,q.push(mk(nans,x));}printf("%lld\n",ans-1);return 0;
}

时间复杂度 \(O(K\log K)\)，强烈谴责出小数据范围误导选手的出题人。选手不会打暴力，不开玩笑。

T3

扩展域并查集 + 树形 dp，牛的。

设 \(f_{x,0/1}\) 表示 \(x\) 连到它父亲的边的方向是正/反时的方案数。开一个扩展域并查集，点 \(i\) 表示这条边是正方向，\(i+n\) 表示反方向。对于这两个在同一块中的情况那就说明矛盾了，直接 \(f_{x,0}=f_{x,1}=0\) 跑路。然后对于 \(x\) 子树内的转移是简单的，直接找出每个状态所属块的情况乘起来即可。接下来考虑某个要求的另一个端点向上越过了 \(x\) 的情况，找到向上延伸的儿子，把它们全部合并起来，最后遍历所有儿子把可行方案数相乘加和即可。

点击查看代码

#include<bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
const int inf=1e18,mod=1e9+7;
int n,m,cnt,head[MAXN],son[MAXN],dfn[MAXN],num,bot[MAXN],siz[MAXN],top[MAXN],deep[MAXN],fa[MAXN],f[MAXN][2];
struct Edge{int value,next;
}edge[MAXN];
void addedge(int u,int v){edge[++cnt].value=v;edge[cnt].next=head[u];head[u]=cnt;
}
int tree[MAXN],cf[MAXN],qans[MAXN];
vector<int>addx[MAXN];
struct Node{int l,r,id;
};
vector<Node>que[MAXN];
int lb(int x){return x&(-x);
}
void add(int x,int y){for(int i=x;i<=n;i+=lb(i))tree[i]+=y;
}
int query(int y){
//	cout<<x<<' '<<y<<"\n";int tans=0;for(int i=y;i;i-=lb(i))tans+=tree[i];return tans;
}
int r[MAXN];
int find(int x){if(r[x]!=x)r[x]=find(r[x]);return r[x];
}
void merge(int x,int y){//cout<<x<<' '<<y<<"!!!\n";if(find(x)!=find(y)){r[find(x)]=find(y);}
}
void dfs1(int x,int father){fa[x]=father;deep[x]=deep[fa[x]]+1;siz[x]=1;dfn[x]=++num;for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){dfs1(y,x);if(!son[x]||siz[son[x]]<siz[y]){son[x]=y;}siz[x]+=siz[y];}}bot[x]=dfn[x]+siz[x]-1;
}
void dfs2(int x,int topx){top[x]=topx;if(son[x])dfs2(son[x],topx);for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]&&y!=son[x]){dfs2(y,y);}}
}
int LCA(int x,int y){//cout<<"lc"<<x<<' '<<y<<"\n";while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);x=fa[top[x]];}if(deep[x]>deep[y])swap(x,y);//cout<<"lcans"<<x<<"\n";return x;
}
int findtop(int x,int y){int last=0;//cout<<"ff"<<x<<' '<<y<<"\n";while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);last=top[x],x=fa[top[x]];}if(x==y)return last;if(deep[x]>deep[y])swap(x,y);return son[x];
}
bool vis[MAXN];
void dfs(int x){if(!son[x]){f[x][0]=f[x][1]=1;return;}int upp=0,flag=0;for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){dfs(y);if(cf[y]>qans[y])upp=y;cf[x]+=cf[y];}}for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){if(find(y)==find(y+n)){flag=1;break;}if(cf[y]>qans[y]){//cout<<"@@@\n";merge(upp,y);merge(upp+n,y+n);}}}if(flag){f[x][0]=f[x][1]=0;return;}for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){if(find(y)>n)f[find(y)-n][1]=f[find(y)-n][1]*f[y][0]%mod;else if(find(y)!=y)f[find(y)][0]=f[find(y)][0]*f[y][0]%mod;if(find(y+n)<=n)f[find(y+n)][0]=f[find(y+n)][0]*f[y][1]%mod;else if(find(y+n)!=y+n)f[find(y+n)-n][1]=f[find(y+n)-n][1]*f[y][1]%mod;}}if(upp){int uppx=find(upp),uppnx=find(upp+n);vis[uppx]=vis[uppnx]=1;f[x][0]=(uppx<=n?f[uppx][0]:f[uppx-n][1]);f[x][1]=(uppnx<=n?f[uppnx][0]:f[uppnx-n][1]);}else{f[x][0]=f[x][1]=1;}for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){int ta=find(y),tb=find(y+n);if(vis[ta]||vis[tb])continue;vis[ta]=vis[tb]=1;int wa=0,wb=0;if(ta>n)ta-=n,wa=1;if(tb>n)tb-=n,wb=1;//cout<<ta<<' '<<wa<<' '<<tb<<' '<<wb<<"\n";f[x][0]=f[x][0]*(f[ta][wa]+f[tb][wb])%mod;f[x][1]=f[x][1]*(f[ta][wa]+f[tb][wb])%mod;}}//cout<<x<<' '<<f[x][0]<<' '<<f[x][1]<<"\n";
}
signed main(){freopen("dispatch.in","r",stdin);freopen("dispatch.out","w",stdout);scanf("%lld%lld",&n,&m);for(int i=1;i<=n*2;i++)r[i]=i;for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);addedge(u,v),addedge(v,u);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=m;i++){int x,y;scanf("%lld%lld",&x,&y);int lca=LCA(x,y);addx[dfn[x]].push_back(dfn[y]);addx[dfn[y]].push_back(dfn[x]);cf[x]++,cf[y]++;cf[lca]-=2;if(x!=lca&&y!=lca){x=findtop(x,lca);y=findtop(y,lca);//cout<<"%%%";merge(x,y+n);merge(y,x+n);}}for(int i=2;i<=n;i++){int x=fa[i],y=i;que[dfn[y]-1].push_back((Node){dfn[x],bot[x],-i});que[dfn[y]-1].push_back((Node){dfn[y],bot[y],i});que[bot[y]].push_back((Node){dfn[x],bot[x],i});que[bot[y]].push_back((Node){dfn[y],bot[y],-i});}for(int i=1;i<=n;i++){for(int j=0;j<(int)addx[i].size();j++)add(addx[i][j],1)/*,cout<<"Add "<<i<<' '<<addx[i][j]<<"\n"*/;for(int j=0;j<(int)que[i].size();j++){if(que[i][j].id<0)qans[-que[i][j].id]-=(query(que[i][j].r)-query(que[i][j].l-1));else qans[que[i][j].id]+=(query(que[i][j].r)-query(que[i][j].l-1));}}//for(int i=1;i<=n;i++)cout<<"qans:"<<qans[i]<<"\n";
//	cout<<"###";dfs(1);printf("%lld\n",f[1][0]);return 0;
}