AGC032题解

Source

AGC032

A

请先思考后再展开

首先显然,一个序列必须满足 $num_{ \leq i} \geq i$
然后我们考虑倒推,那么就变成每次值域总是在i以内,i不断减小
当前最后一次操作一定满足 $A_k=k$ ,如果有多个,只能选择最后一个
否则这个球的位置一定会$<k$,再也无法拿走

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
//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>
using namespace std;
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
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=5e5+10;
int a[MAX_N],ct[MAX_N];
vector<int> ans;
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),ct[a[i]]++;
for(int i=1;i<=n;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--)
{
for(int j=i;j>=1;j--) if(ct[j]<j) {puts("-1");return;}
bool ok=0;
for(int j=i;j>=1;j--) if(j==a[j])
{
ans.PB(j);for(int t=j;t<=i;t++) ct[t]--;
for(int t=j;t<=i-1;t++) swap(a[t],a[t+1]);
ok=1;break;
}
if(ok==0) {puts("-1");return;}
}
reverse(ans.begin(),ans.end());
for(int t=0;t<(int)ans.size();t++) printf("%d\n",ans[t]);
}
};
int main()
{
srand(time(0));
mine::main();
}

B

请先思考后再展开

考虑一个图,如果强制i->i,然后不允许连向所有点
生成的图能满足编号和的限制,那么其补图一定是个连通图,而且也满足编号和限制
于是就很好构造了
偶数数:{1,n-1},{2,n-2}……
奇数:{1,n},{2,n-1}……{n/2+1}

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
//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>
using namespace std;
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
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=1e3+10;
bool v[MAX_N][MAX_N];
void main()
{
int n;scanf("%d",&n);
if(n&1) for(int i=1;i<=n/2;i++) v[i][n-i]=1;
else for(int i=1;i<=n/2;i++) v[i][n+1-i]=1;
printf("%d\n",n*(n-1)/2-(n/2) );
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!v[i][j]) printf("%d %d\n",i,j);
}
};
int main()
{
srand(time(0));
mine::main();
}

C

请先思考后再展开

首先这个图必须是欧拉回路,否则没有合法解
首先两个环如果有公共交点是可以合并为1个的,所以只要我们能找到至少3个环即可

结论1:如果有公共交点,那么那个公共交点的度数必然>=6,如果有则合法
证明:将这个点的欧拉路径分3段即可,必定经过这里6次以上

结论2:【度数=4】的点如果>=3个,则合法
证明:我们只需考虑每个点度数=2或4的情况,设某3个【度数=4】的点为A,B,C
情况一,A出去的两个环,其中一个环B出现了两次,那么把B回到B的路径拉为第3个环即可
情况二,在这两个环中B和C都在每个中出现一次,那么总能拆开来,画画图就知道了

结论3:【度数=4】的点如果=2个(显然1个的话无解)
为什么不一定合法呢?可以看看官方题解的图
即A和B之间恰好有两条路径(显然不会有除A、B外的交点)
然后一个比较巧妙的判断方法是把A去掉后,联通块数>=3

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
//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>
using namespace std;
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
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
int dg[MAX_N];pr e[MAX_N];
int fa[MAX_N];int findfa(int x) {return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void main()
{
int n,m;scanf("%d%d",&n,&m);
int tmp=0;
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
dg[x]++;dg[y]++;e[i]=MP(x,y);
}
for(int i=1;i<=n;i++) if(dg[i]&1) {puts("No");return;}
for(int i=1;i<=n;i++) if(dg[i]>=6) {puts("Yes");return;}
int cnt=0,A;for(int i=1;i<=n;i++) if(dg[i]==4) cnt++,A=i;
if(cnt>=3) {puts("Yes");return;}
if(cnt==1) {puts("No");return;}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) if(e[i].FR!=A and e[i].SE!=A) fa[findfa(e[i].FR)]=findfa(e[i].SE);
int tot=0;for(int i=1;i<=n;i++) tot+=(findfa(i)==i);
if(tot>=3) puts("Yes"); else puts("No");
}
};
int main()
{
srand(time(0));
mine::main();
}

未完待续……

D

请先思考后再展开

先转化一下题意:把问题放到实数数轴上,那么显然每个数最多被操作一次
$ans=\sum A(ai<bi)+B(ai>bi)$
那么不难设计一个dp,自己想一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll f[MAX_N];//前缀和
int a[MAX_N];
void main()
{
int n=qread(),A=qread(),B=qread();
for(int i=1;i<=n;i++) a[qread()]=i;
for(int i=1;i<=n;i++)
{
for(int j=n;j>=0;j--)
{
f[j]=f[j]+A*(a[i]<=j)+B*(a[i]>j);
if(j==a[i]) chmin(f[j],f[j-1]);
else if(j) chmin(f[j],f[j-1]+A*(a[i]<j)+B*(a[i]>j));
}
for(int j=1;j<=n;j++) chmin(f[j],f[j-1]);
}
ll ans=LLINF;for(int j=0;j<=n;j++) chmin(ans,f[j]);write(ans);
}

E

请先思考后再展开

先有序化
结论:一定存在一个合法方案形如

证明的话,最好别像题解这样瞎jb画画图就没了,可以设未知数,列些不等式
我在证颜色交叉那种情况的时候漏了几条不等式被mldD飞了

然后考虑那个分界点,满足左边是1~A,右边是B~n,如果 $B<A$ 则取B,求A和B可以二分
另外,个人认为官方题解有个小细节没证明,就是B<=A
不过也挺好证明的,反证一下,如果B>A,即右边弹簧拉到最左,左边部分依然>M,则直接全部红色会更优,即弹簧没有到最左

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
int a[MAX_N];
void main()
{
int n=qread(),M=qread();for(int i=1;i<=n*2;i++) a[i]=qread();sort(a+1,a+n+n+1);
int l,r,A,B;
l=1,r=n,A=0;
while(l<=r)
{
int mid=(l+r)>>1;bool bk=0;
for(int tl=1,tr=2*mid;tl<=tr;tl++,tr--) if(a[tl]+a[tr]>=M) {bk=1;break;}
if(!bk) A=mid,l=mid+1;
else r=mid-1;
}
l=0,r=n-1,B=n;
while(l<=r)
{
int mid=(l+r)>>1;bool bk=0;
for(int tl=mid*2+1,tr=2*n;tl<=tr;tl++,tr--) if(a[tl]+a[tr]<M) {bk=1;break;}
// printf("l=%d r=%d mid=%d bk=%d\n",l,r,mid,bk);
if(!bk) B=mid,r=mid-1;
else l=mid+1;
}
if(B>A)
{
printf("error A=%d B=%d\n",A,B);
}
else
{
int mx=0;
for(int tl=1,tr=2*B;tl<=tr;tl++,tr--) chmax(mx,a[tl]+a[tr]);
for(int tl=2*B+1,tr=2*n;tl<=tr;tl++,tr--) chmax(mx,a[tl]+a[tr]-M);
write(mx);
}
}

F

请先思考后再展开
1
2

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