AGC006 做题记录
A
显然等价于求 \(s\) 的后缀与 \(t\) 的前缀相同的最大长度。注意到 \(N\le100\) ，可以直接暴力。我不想暴力怎么办啊？ 那可以用字符串哈希做到 \(O(N)\) 。
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int P=998244353;
ll n,p[105],pre[105],suf[105];
char s[105],t[105];
int main(){
n=read();scanf("%s%s",s+1,t+1);p[0]=1;
rep(i,1,n){
p[i]=p[i-1]*26%P;
pre[i]=(t[i]-'a'+pre[i-1]*26%P)%P;
}
rep(i,0,n-1){
suf[i+1]=(suf[i]+p[i]*(s[n-i]-'a')%P)%P;
}
for(int len=n;len;--len){
if(pre[len]==suf[len]){
printf("%d\n",2*n-len);return 0;
}
}
printf("%d\n",2*n);
return 0;
}
|
B
构造题。不妨先找找规律和性质，有
- 如果某一行中相邻元素 \(a_i=a_{i+1}=x\) ，那么这行往上的第 \(i,i+1\) 列的元素均为 \(x\) 。
- 因为第一层数字需要为第二层的中位数，故 \(1,2n-1\) 两数不可能在顶层。
有了这两个性质，我们不妨思考一下对于满足 \(1<x<2n-1\) 的 \(x\) 在顶层时该如何构造。最好的构造就是最底层满足 \((a_{n-1},a_n,a_{n+1})\) 和 \((a_n,a_{n+1},a_{n+2})\) 中均有 \(a_n=x\) 为中位数，由性质1得顶层元素一定为 \(x\) 。
有一说一这道题rating才1600怎么就紫了
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5;
int n,x,ans[N];
bool vis[N];
int main(){
n=read(),x=read();
if(x==1||x==2*n-1)return puts("No"),0;
if(x==2){
puts("Yes");
ans[n-1]=2*n-1,ans[n]=2,ans[n+1]=1,ans[n+2]=2*n-2;
rep(i,1,n-2)ans[i]=i+2;
rep(i,n+3,2*n-1)ans[i]=i-2;
}else{
puts("Yes");
ans[n-1]=1,ans[n]=x,ans[n+1]=2*n-1,ans[n+2]=2;
vis[1]=vis[x]=vis[2*n-1]=vis[2]=1;
int j=1;
rep(i,1,2*n-1){
while(ans[i])i++;
while(vis[j])j++;
ans[i]=j++;
}
}
rep(i,1,2*n-1)printf("%d\n",ans[i]);
return 0;
}
|
C
有点妙的期望题。
通过计算可以发现，第 \(i\) 个兔子跳跃后新的期望位置为
看起来不太有规律，然而如果我们画了图的话，会发现这一次跳跃本质上交换了 \(d_i=a_i-a_{i-1},d_{i+1}=a_{i+1}-a_i\) 这两段距离。（也可以通过移项发现 \(a'_i-a_{i-1}=d_{i+1},a_{i+1}-a'_i=d_i\) ）给定的 \(m\) 个交换构成一个置换，我们要求的就是置换 \(k\) 次后最终的序列，把差分还原就能得到答案。做法很多，可以使用快速幂或者利用一个置换为若干个轮换构成的性质。两者的时间复杂度分别为 \(O(n\log k)\) 和 \(O(n)\) ，这里用的是快速幂。
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5;
int n,d[N],ans[N],T[N],a[N];
double b[N];
ll m,k;
int main(){
n=read();
rep(i,1,n)a[i]=read(),d[i]=ans[i]=i;
m=read(),k=read();
rep(i,1,m){
int x=read();
swap(d[x],d[x+1]);
}
while(k){
if(k&1){
rep(i,1,n)T[i]=ans[d[i]];
rep(i,1,n)ans[i]=T[i];
}
rep(i,1,n)T[i]=d[d[i]];
rep(i,1,n)d[i]=T[i];
k>>=1;
}
rep(i,1,n)b[i]=a[ans[i]]-a[ans[i]-1];
rep(i,1,n)printf("%.1lf\n",b[i]+=b[i-1]);
return 0;
}
|
### D
二分思想很妙的应用。
暴力显然不行，我们回忆一下B中得到的性质1：
如果某一行中相邻元素 \(a_i=a_{i+1}=x\) ，那么这行往上的第 \(i,i+1\) 列的元素均为 \(x\) 。
可以通过二分答案来检验顶层元素是否 \(\ge x\) 。把所有 \(a_i<x\) 设为 \(0\) ， \(a_i\ge x\) 设为 \(1\) ，那么最接近中心的连续两个相同元素决定了顶端的取值。如果连续两个 \(1\) ，那么顶端也为 \(1\) ，即 \(\ge x\) ，反之顶端为 \(0\) 。只有当 \(01\) 交错时没有这样的连续段，此时顶端元素 \(=a_1\) 。
时间复杂度： \(O(n\log n)\)
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5;
int n,a[N],b[N];
bool check(int x){
rep(i,1,2*n-1)b[i]=(a[i]>=x);
rep(i,0,n-2){
if(b[n+i]==b[n+i+1])return b[n+i];
if(b[n-i]==b[n-i-1])return b[n-i];
}
return b[1];
}
int main(){
n=read();
rep(i,1,2*n-1)a[i]=read();
int l=1,r=2*n-1,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
l=mid+1;ans=mid;
}else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
|
E
一股 [AGC003C] BBuBBBlesort! 的既视感（。
观察发现每个操作等价于交换并翻转 \(i,i+2\) 两列，同时翻转 \(i+1\) 列。注意到操作不会改变每一列下标的奇偶性，于是可以分奇数列和偶数列进行考虑。设 \(tot_0,tot_1\) 分别为奇数列和偶数列的总操作次数，\(inv_0, inv_1\) 为奇偶列颠倒的列数。注意到奇数列的每个操作会带来某个偶数列的一次翻转，于是
是能操作回原矩阵的必要条件。此时可以大胆猜想该条件充分，因为并不需要证明（雾） 下面证明其充分性。记操作 \(i\) 为翻转 \(i,i+1,i+2\) 这三列。那么经过操作 \(1,3,1,3,1,3,2,1,2,1\) 后，第 \(1\) 和 \(3\) 列被翻转，且其他列不变。进而可以不改变其他列的情况下生成奇数列和偶数列各自上的任意偶数次翻转。解决了翻转次数的奇偶性问题，而对换相邻行生成置换又是显然的，这就证明了上述结论的充分性。
最后思考如何求解，这并不难（比上面的容易多了），可以用 \(O(n\log n)\) 求逆序对数来判断置换所需要的对换数，也可以通过另一个神仙做法优化到 \(O(n)\) 。对于第二种做法，我们把置换用若干个轮换来表示，环的大小与逆序对的个数的奇偶性相反。
时间复杂度： \(O(n)\)
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5;
int a[N][3],to[N],n,tot[2];
int main(){
n=read();
rep(i,0,2)rep(j,1,n)a[j][i]=read();
rep(i,1,n){
if((a[i][0]==a[i][1]-1&&a[i][2]==a[i][1]+1)||(a[i][0]==a[i][1]+1&&a[i][2]==a[i][1]-1)){
to[i]=a[i][1]/3+1;
if(i%2!=to[i]%2||a[i][1]%3!=2)return puts("No"),0;
if(a[i][0]>a[i][2])tot[i&1]^=1;
}
else return puts("No"),0;
}
rep(i,1,n){
while(i!=to[i]){
swap(to[i],to[to[i]]);
tot[i&1^1]^=1;
}
}
if(tot[0]||tot[1])puts("No");
else puts("Yes");
return 0;
}
|
F
题目描述看上去很怪，先找一下等价命题，发现可以看做 \(n\) 个点 \(m\) 条边的图，且如果 \((u,v),(v,w)\) 有边，\((w,u)\) 也连一条边。再转换一下，对于 \(v\) 的所有出边和入边对的节点，出点向入点连一条边。
首先观察到加边只在弱连通分量里进行，我们可以单独考虑每个这样的分量。
- 如果不存在一组 \((u,v),(v,w)\) 的话，图不会变化。
- 如果存在，将一个节点染红，其出点染蓝，入点染绿；入边对绿点或出边对蓝点的所有点染红，这些红点再继续引出新的点染色。染色若成功， \(R\to G\to B\to R\) ，三种颜色构成了三元环。不难发现，颜色不同的节点两两之间都会有一条边。让我们更好的描述这个染色过程，实质上为起点为红色，该点连向的所有点染蓝色，蓝色点连向的所有点染绿色。设三色点数量分别为 \(R,G,B\) ，那么该连通分量对答案贡献为 \(RG+RB+GB\) 。
- 然而，我们忽略了在上述染色过程中失败的可能性，即出现染色的矛盾。不妨设矛盾出现在点 \(u\) 且它同时染了红色和蓝色，根据上个染色的性质（红点和蓝点连边）， \(u\) 会有自环。而自环又可以推出 \(u\) 也能染绿色，进而发现所有点都向 \(u\) 连边，而这引出了所有点的染色矛盾，整个图将变成包括自环的完全图。对答案贡献为 \(tot^2\) ，其中 \(tot\) 为连通分量大小。
时间复杂度： \(O(n)\)
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 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5;
int n,m,col[N],flag,tot,etot;
bool vis[N];
ll ans,cnt[3];
struct Edge{int tp,to;};
vector<Edge> G[N];
void dfs(int u){
++cnt[col[u]];vis[u]=1;++tot;
for(auto tmp:G[u]){
etot+=(tmp.tp==1);
int v=tmp.to;
if(!vis[v]){
col[v]=(col[u]+tmp.tp)%3;dfs(v);
}else if(col[v]!=(col[u]+tmp.tp)%3)flag=0;
}
}
int main(){
n=read(),m=read();
rep(i,1,m){
int u=read(),v=read();
G[u].push_back({1,v});
G[v].push_back({2,u});
}
rep(i,1,n)if(!vis[i]){
memset(cnt,0,sizeof(cnt));
flag=1;etot=tot=0;
dfs(i);
if(!flag)ans+=1ll*tot*tot;
else if(cnt[0]&&cnt[1]&&cnt[2]){
ans+=cnt[0]*cnt[1]+cnt[1]*cnt[2]+cnt[2]*cnt[0];
}else ans+=etot;
}
printf("%lld\n",ans);
return 0;
}
|