AGC001题解

Source

AGC001
好题:B、E

A

请先思考后再展开
1
2
3
4
5
6
7
8
9
int a[MAX_N];
void main()
{
int n=qread();
for(int i=1;i<=2*n;i++) a[i]=qread();
sort(a+1,a+2*n+1);
int ans=0;for(int i=1;i<=2*n;i+=2) ans+=a[i];
write(ans);
}

B

请先思考后再展开

这题点子不错
就是每次割一个平行四边形,自己画画很容易想到
复杂度和gcd一样,为log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll ans;
void T(ll x,ll y)//x<y
{
if(x>y) swap(x,y);
printf("T(%lld,%lld)\n",x,y);
ll a=y/x,b=y%x;
if(b==0) ans+=(a*2-1)*x;
else ans+=(a*2)*x,T(x,b);
}
void main()
{
ll n=qread(),x=qread();ans=n;
T(x,n-x);write(ans);
}

C

请先思考后再展开

一开始想了个假的线性,然后改成假的线段树nlogn……好菜啊
最早的时候想过dp,感觉不知道搞些什么,然后想完上面的东西之后有了感觉才发现很好dp的
f(x,now)=【保证不过x的路径<=K,大小为now】下,子树到x的最大距离

题解做法好麻烦啊,还是这个好想

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
inline void chmax(int &x,const int y) {x=x>y?x:y;}
inline void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=2100;
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int K;
vector<int> son[MAX_N];
int dis[MAX_N],siz[MAX_N];
int ans=0;
int f[MAX_N][MAX_N];//f(x,now)=【保证不过x的路径<=K,大小为now】下,子树到x的最大距离
void solve(int x,int fa)
{
f[x][1]=0;siz[x]=1;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa) continue;
solve(y,x);siz[x]+=siz[y];
for(int all=siz[x];all>=1;all--) for(int b=1;b<=siz[y] and b<=all;b++)
if(f[x][all-b]+f[y][b]+1<=K) chmin(f[x][all],max(f[x][all-b],f[y][b]+1));
}
for(int i=siz[x];i>=1;i--) if(f[x][i]<=K) chmax(ans,i);
}
void main()
{
int n=qread();K=qread();
for(int i=1;i<n;i++)
{
int x=qread(),y=qread();
son[x].PB(y);son[y].PB(x);
}
memset(f,0x3f,sizeof f);
solve(1,0);write(n-ans);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

D

题意(看了好久):
就是N个点,然后给一个长为m的序列,要求重排列后为a,再构造一个b,每ai个是回文的,要求图联通

请先思考后再展开

日常不会做构造……

因为是连通图,然后每个节点度数不超过2,所以一定是环或者链,那么如果不止两个奇数,则度为1的点过多,无法联通
然后对于m=1的情况, ${a}->{a-1,1}$
然后类似地,考虑这样搞: ${a,b,c,d}->{a-1,b,c,d+1}$
但这种偏移在中间有奇数项的时候会gg,但因为奇数最多两个,可以把奇数放到序列头尾

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
using namespace std;
typedef long long ll;
ll qread()
{
ll ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
void write(ll num)
{
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(ll num) {write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
const int INF=0x3f3f3f3f;
void chmax(int &x,int y) {x=x>y?x:y;}
const int MAX_N=110;
int a[MAX_N];
int main()
{
int n=qread(),m=qread();
int cnt=0,x=0,y=0;
for(int i=1;i<=m;i++)
{
a[i]=qread();
if(a[i]&1) {cnt++;if(x==0) x=i; else y=i;}
}
if(m==1)
{
if(a[1]==1) printf("1\n1\n1\n",1);
else printf("%d\n2\n%d 1",a[1],a[1]-1);
return 0;
}
if(cnt>2) {puts("Impossible");return 0;}
if(x>0) swap(a[1],a[x]);
if(y>0) swap(a[m],a[y]);
for(int i=1;i<=m;i++) printf("%d ",a[i]);puts("");
if(a[1]==1) writeln(m-1); else writeln(m),printf("%d ",a[1]-1);
for(int i=2;i<=m;i++) printf("%d ",a[i]+(i==m));
}

E

请先思考后再展开

这题妙啊
众所周知组合数可以转化为网格图,从原点到(n,m),只能上或右的方案数
那现在不能枚举两个的拼接,但值域很小,不妨转化为从(-ai,-bi)走到(aj,bj)的方案数
注意要去掉自己到自己,以及无序二元组

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
inline void chmax(int &x,const int y) {x=x>y?x:y;}
inline void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=2e5+10;
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int inv[MAX_N],fac[MAX_N],facinv[MAX_N];
int C(int n,int m) {return (ll)fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
int f[5100][5100];
#define F(i,j) (f[(i)+2100][(j)+2100])
int a[MAX_N],b[MAX_N];
void main()
{
inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=(ll)fac[i-1]*i%MOD;
facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=(ll)facinv[i-1]*inv[i]%MOD;
int n=qread(),ans=0;
for(int i=1;i<=n;i++)
{
a[i]=qread(),b[i]=qread();
add(ans,MOD-C(2*a[i]+2*b[i],2*a[i]) );
F(-a[i],-b[i])++;
}
for(int i=-2000;i<=2000;i++) for(int j=-2000;j<=2000;j++) add(F(i+1,j),F(i,j)),add(F(i,j+1),F(i,j));
for(int i=1;i<=n;i++) add(ans,F(a[i],b[i]));
write((ll)ans*inv[2]%MOD);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

F

请先思考后再展开

设A[p[i]]=i即某个值的位置,那么就是每次交换相邻的,差>=K的值
注意到如果两个值,$差<K$,则相对位置是不会改变的
即对于A中的数字i,数字(i-K,i+K)与i的相对顺序不能改变

那么就是说我能得出一些顺序的限制条件,在满足这些条件的情况下构造一个拓扑序方案,我们已经获得了一个 $n^2$的做法
这个做法的主要瓶颈在于边数过多,这些边我能用bitset快速获得,但连边还是没办法优化
但这个边多只发生在K比较大的时候,而这种时候其实拓扑排序中没意义的边是很多的,所以思路是尽量减少边数

然后这里我一开始的想法是,对于每个i只考虑i-K部分,原本在前后的限制,然后发现很难做
但如果每个i,考虑i-K和i+K,他们原本在前面的限制,就完全不一样了,因为距离限制是对称的

具体而言,左边大小为K的部分,只需要向比i早而最晚出现的那个连边,因为其他已经出现的,都一定被这个覆盖;右边同理
这样边数是2n级别的,用线段树维护即可
时间复杂度为 nlogn

最后讲讲这个字典序的问题
不知道为什么很多题解都说,p最小就是让A最小,然而这应该是错的,但本题极难卡
这种让拓扑序的逆最小的模型,应该是建反向边,然后开大根堆

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=5e5+10;
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
struct SegmentTree
{
#define lc 2*x
#define rc 2*x+1
#define mid ((l+r)>>1)
pr mx[MAX_N*4];
void change(int x,int l,int r,int p,int c)
{
mx[x]=max(mx[x],MP(c,p));
if(l==r) return;
if(p<=mid) change(lc,l,mid,p,c);
else change(rc,mid+1,r,p,c);
}
pr ask(int x,int l,int r,int fl,int fr)
{
if(fl>fr) return MP(0,0);
if(l==fl and r==fr) return mx[x];
if(fr<=mid) return ask(lc,l,mid,fl,fr);
if(fl>mid) return ask(rc,mid+1,r,fl,fr);
return max(ask(lc,l,mid,fl,mid),ask(rc,mid+1,r,mid+1,fr));
}
}sgt;
int a[MAX_N],ans[MAX_N];
int ru[MAX_N];vector<int> to[MAX_N];
void ins(int x,int y) {ru[y]++;to[x].PB(y);}
priority_queue<int> q;
void main()
{
int n=qread(),K=qread();
for(int i=1;i<=n;i++) a[qread()]=i;
for(int i=1;i<=n;i++)
{
int num=a[i];sgt.change(1,1,n,num,i);
pr a=sgt.ask(1,1,n,max(1,num-K+1),num-1);if(a.FR>0) ins(num,a.SE);
pr b=sgt.ask(1,1,n,num+1,min(num+K-1,n));if(b.FR>0) ins(num,b.SE);
}
for(int i=1;i<=n;i++) if(ru[i]==0) q.push(i);
for(int now=n;now>=1;now--)
{
int x=q.top();q.pop();ans[x]=now;
for(int t=0;t<(int)to[x].size();t++)
{
int y=to[x][t];ru[y]--;
if(ru[y]==0) q.push(y);
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/794c.html
转载请注明出处,谢谢!