摘要:无

11022020成外联考

T1

题目分析

考虑贪心,贪心地将尽量小的字母放到尽量前面去,每次都放到能放的最前面即可,因为操作次数不足以将最优字母放到最前面的情况仅存在一次所以是正确的.

拿一个树状数组记录每个字母原来的位置的后面有多少个字母被移动到了前面去,原来的位置加上这个值即为现在的位置.

代码实现要仔细一点,$k$要开long long.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#define debug(x) printf("debug:%d\n",x)
#define R register
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const int big=500010;
int n,front;
long long k;
int in[big],size[27],t[big];
char s[big];
std::priority_queue<int>pri[27];
std::vector<int>pachy;
std::vector<int>::iterator it;
inline int read()
{
char c(getchar());
int f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
return f*x;
}
inline void modify(int x,int k){for(;x;x-=lowbit(x))t[x]+=k;}
inline int query(int x){int sum(0);for(;x<=n;x+=lowbit(x))sum+=t[x];return sum;}
int main(void)
{
// freopen("escape.in","r",stdin);
// freopen("escape.out","w",stdout);
n=read(),k=read();
scanf("%s",s+1);
for(R int i(1);i<=n;++i)pri[s[i]-'a'].push(-i),++size[s[i]-'a'];
while(k)
{
int lefid,lefpos=INF,lefch,cost;
for(R int i(0);i<26;++i)
{
if(!size[i])continue;
int now=-pri[i].top(),tmp=now;
now+=query(tmp);
int pos=std::max(front+1,now-k);
if(pos<lefpos)lefpos=pos,cost=now-pos,lefid=tmp,lefch=i;
}
if(lefpos==INF)break;
++front,pri[lefch].pop(),pachy.push_back(lefid),in[lefid]=true;
k-=cost,--size[lefch];
modify(lefid,1);
}
for(it=pachy.begin();it!=pachy.end();++it)printf("%c",s[*it]);
for(R int i(1);i<=n;++i)if(!in[i])printf("%c",s[i]);putchar('\n');
return 0;
}

T2

题目分析

发现路径上单调性改变的点仅存在一个,所以将这个点作为根,然后处理出以每个点为起点的点编号递减的所有链,记录它的每个儿子的子树中有多少个点在链上,每个儿子与其他儿子组合求解.

然后就可以直接换根,因为把一个点换成根,发生改变的点仅为它的祖先,而它到祖先合法的情况是从这个点到某个祖先的路径上点的编号递增,所以这个点一定不存在于它的祖先处理出来的链中,直接加上祖先处理出来的值即可.

换根的过程也可以预处理,按照之前处理递减链的思路处理递增链即可.

然后注意遍历链的时候记录链头,从链头开始遍历,不然每次选取一个没被遍历的点开始遍历容易被卡.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#define debug(x) printf("debug:%d\n",x)
#define R register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const int big=300010;
int n,EdgeSize,maxd;
long long ans,poi;
int head[big],dp[2][big],sum[big],fa[big],vis[big],size[big],len[big],pre[big],root[big],deg[big];
struct _Edge{int v,next;}e[big<<1];
std::vector<int>edge[big],pachy[big];
std::vector<int>::iterator it;
#define add(u,v) EdgeAdd(u,v),EdgeAdd(v,u)
inline void EdgeAdd(int u,int v){e[EdgeSize]=(_Edge){v,head[u]};head[u]=EdgeSize++;}
inline int read()
{
char c(getchar());
int f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
return f*x;
}
void dfs(int u,int father)
{
fa[u]=father;
if(u<father)
{
edge[father].push_back(u);
if(fa[father]<father&&!vis[father])root[++root[0]]=father,vis[father]=true;
}
for(R int i(head[u]);~i;i=e[i].next)
{
int v=e[i].v;
if(v==father)continue;
dfs(v,u);
}
}
void dfs2(int u)
{
size[u]=1,vis[u]=true;
for(std::vector<int>::iterator it=edge[u].begin();it!=edge[u].end();++it)
{
int v=*it;
dfs2(*it);
size[u]+=size[v];
}
}
void dfs3(int u,int father)
{
for(R int i(head[u]);~i;i=e[i].next)
{
int v=e[i].v;
if(v==father)continue;
dfs3(v,u);
if(size[v]&&v<u)sum[u]+=size[v],pachy[u].push_back(size[v]);
}
}
void dfs4(int u,int fa,int sm,int dis)
{
pre[u]=sm,len[u]=dis;
for(R int i(head[u]);~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
if(v>u)dfs4(v,u,sm+sum[u],dis+1);
else dfs4(v,u,0,1);
}
}
int main(void)
{
// freopen("ride.in","r",stdin);
// freopen("ride.out","w",stdout);
memset(head,-1,sizeof head);
n=read();
for(R int i(1);i<n;++i){int u=read(),v=read();++deg[u],++deg[v];add(u,v);}
dfs(1,0);
for(R int i(1);i<=n;++i)if(deg[i]>maxd)maxd=deg[i];
for(R int i(1);i<=root[0];++i)dfs2(root[i]);
dfs3(1,0),dfs4(1,0,0,1);
for(it=pachy[1].begin();it!=pachy[1].end();++it)ans+=1ll*(sum[1]-(*it))*(*it);
for(R int i(2);i<=n;++i)
{
int all(sum[i]);
int tfa=fa[i],last(i),delta(len[i]),frs(pre[i]);
frs+=delta-1,all+=frs;
pachy[i].push_back(frs);
for(it=pachy[i].begin();it!=pachy[i].end();++it)ans+=1ll*(all-(*it))*(*it);
}
printf("%lld\n",ans);
return 0;
}

T3

题目分析

因为边的长度都为$1$,所以只要$u$到$v$的最短路为偶数,那么只要随便选一条边不断来回走就一定可以满足$d$是偶数的情况,奇数亦然.

把每个点拆成奇点和偶点,连边$(u,v)$的时候$u$的奇点向$v$的偶点连边,$u$的偶点向$v$的奇点连边,然后bfs遍历出最短路即可.

注意判孤点.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define R register
#define debug(x) printf("debug:%d\n",x)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const int big=100010;
int n,m,q,EdgeSize;
int head[big],nonly[big],dis[big],ans[big];
struct _Edge{int v,next;}e[big<<1];
struct _Question
{
int s,t,d,id;
inline bool operator <(const _Question &another)const{return s==another.s?t<another.t:s<another.s;}
}qus[big];
std::queue<int>que;
inline int read()
{
char c(getchar());
int x(0),f(-1);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
return x;
}
#define add(u,v) EdgeAdd(u,v),EdgeAdd(v,u)
inline void EdgeAdd(int u,int v){e[EdgeSize]=(_Edge){v,head[u]},head[u]=EdgeSize++;}
inline void bfs(int s)
{
memset(dis,0x3f,sizeof dis),que.push(s),dis[s]=0;
while(!que.empty())
{
int u=que.front();que.pop();
for(R int i(head[u]);~i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+1)dis[v]=dis[u]+1,que.push(v);
}
}
}
int main(void)
{
// freopen("data.in","r",stdin);
memset(head,-1,sizeof head);
n=read(),m=read(),q=read();
for(R int i(1);i<=m;++i)
{
int a=read(),b=read();
add(a,b+n),add(a+n,b);
nonly[a]=nonly[b]=true;
}
for(R int i(1);i<=q;++i)
{
qus[i]=(_Question){read(),read(),read(),i};
if(qus[i].s>qus[i].t)std::swap(qus[i].s,qus[i].t);
}
std::sort(qus+1,qus+1+q);
for(R int i(1);i<=q;++i)
{
if(qus[i].s!=qus[i-1].s)bfs(qus[i].s);
if(qus[i].s==qus[i].t&&!nonly[qus[i].s]&&qus[i].d)continue;
ans[qus[i].id]=dis[qus[i].t+(qus[i].d&1?n:0)]<=qus[i].d;
}
for(R int i(1);i<=q;++i)printf(ans[i]?"Yes\n":"No\n");
return 0;
}

T4

真不会.

总结

早上一到机房开机突然发现自己电脑主板坏了,于是只好换了台devcpp都有锅,鼠标上都结了蜘蛛网的怪电脑用,而且考试的时候发现这台电脑一个exe只要运行5遍以上就会被给管理员权限,然而管理员密码早就被人遗忘了,于是只有隔一会就重开一个cpp来运行,比赛体验—.

T1做得挺快,看了一小会样例发现直接贪心做即可,实现细节有点多,花了半个小时打完代码.不过没注意到$k$要开long long掉了10pts.

T2开始在想dp,但是发现可以直接换根后统计答案,直接就上去打了,打完测样例发现自己统计答案方式写错了,还好错得不大小改一下就没事了,还是得想清楚再打.

这种树上的题经常得调特别久,打完后调了一个小时才过完所有样例,不过换根的时候写的是暴力上跳统计祖先贡献,当时因为还剩一个半小时,后面两题还没动就没管了,但其实在随机数据下效率差距没多大,中午回寝室稍微想了一下就发现这东西也可以直接预处理.然而在遍历新树的子树的时候写丑了导致树的形态为链的20pts被卡掉了.

T3是图论题,现在考试尤其是这种四道题的,考到后面感觉就很疲惫了,不怎么愿意去想题,其实这题考虑边权都为$1$然后奇偶性就很好想了,要是放T2的话一个半小时做出来完全不是问题.但是当时也不怎么愿意去想正解,用矩阵乘法打过了30pts,而且还因为很久没动矩阵了调了半个小时.

T4就没动了.

考试的时候还是精神点,每次都要当成在联赛现场,而且没开long long和遍历方式写丑这种小错误也不该犯.