Codeforces Round #517[CF1071]

发表于 分类于

Codeforces Round #517

A. Cram Time

显然，在里面的肯定是一段前缀。

先二分出最大值，找到这个前缀。

然后从大到小贪心减去即可。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
int a,b;
vector<int> s1,s2;
inline void print(vector<int> &V)
{
	printf("%d\n",V.size());
	for(auto x:V) printf("%d ",x);
	printf("\n");
}
int main()
{
	a=read(); b=read();
	int l=1,r=100000,mid;
	for(;l<=r;)
	{
		mid=l+r>>1;
		if(1ll*mid*(mid+1)/2<=a+b) l=mid+1;
		else r=mid-1;
	}
	l--;
	fd(i,l,1) if(a>=i) s1.pb(i),a-=i; else s2.pb(i),b-=i;
	print(s1);
	print(s2);
	return 0;
}

B. Minimum path

$n\times n$ 的网格，上面有字母。从左上到右下走，每次只能往下或往右走，一条路径形成了长度为 $2n-1$ 的字符串，你可以在网格图上修改 $k$ 次，每次修改一个字母，输出最小的字典序。

显然如果 $k\geq 2n-1$ ，则答案为 $2n-1$ 个 $a$。

然后把这个字符串分成两部分，一部分是前面的 $a$，另一部分是后面的东西。

考虑贪心，设 $dp_{i,j}$ 表示走到 $(i,j)$ 最少经过多少个不是 $a$ 的网格。

那么找到 $i+j-1$ 最大的且 $dp_{i,j}\leq k$ 的 $(i,j)$，前 $i+j-1$ 个就全都是 $a$ 了。

剩下的就一个 bfs 就好了。

注意bfs时的去重，以及 $k=0$ 的情况。

时间复杂度 $O(n^2)$ 左右。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2005;
int n,k,f[N][N];
char s[N][N];
struct P{
	int x,y;
	friend inline bool operator<(const P &A,const P &B)
	{
		if(A.x!=B.x) return A.x<B.x;
		return A.y<B.y;
	}
	friend inline bool operator==(const P &A,const P &B)
	{
		return A.x==B.x&&A.y==B.y;
	}
};
vector<P> p,q;
inline int find()
{
	int mi=27;
	for(auto u:q)
	{
		if(u.x<n) mi=min(mi,s[u.x+1][u.y]-'a');
		if(u.y<n) mi=min(mi,s[u.x][u.y+1]-'a');
	}
	return mi;
}
inline void getnext(int mi)
{
	for(auto u:q)
	{
		if(u.x<n&&s[u.x+1][u.y]-'a'==mi) p.pb((P){u.x+1,u.y});
		if(u.y<n&&s[u.x][u.y+1]-'a'==mi) p.pb((P){u.x,u.y+1});
	}
	sort(all(p));
	p.resize(unique(all(p))-p.begin());
	q=p; p.clear();
}
int main()
{
	n=read(); k=read();
	if(k>=2*n-1)
	{
		fo(i,1,2*n-1) putchar('a');
		return 0;
	}
	fo(i,1,n) scanf("%s",s[i]+1);
	memset(f,0x3f,sizeof(f));
	f[1][1]=(s[1][1]!='a');
	int c;
	fo(i,1,n) fo(j,1,n)
	{
		c=(s[i][j]!='a');
		if(i-1) f[i][j]=min(f[i][j],f[i-1][j]+c);
		if(j-1) f[i][j]=min(f[i][j],f[i][j-1]+c);
	}
	int mx=0;
	fo(i,1,n) fo(j,1,n) if(f[i][j]<=k) mx=max(mx,i+j-1);
	fo(i,1,mx) putchar('a');
	fo(i,1,n) fo(j,1,n) if(f[i][j]<=k&&i+j-1==mx) q.pb((P){i,j});
	if(f[1][1]==1&&k==0) k=1,putchar(s[1][1]),q.pb((P){1,1}),mx=1;
	int x;
	fo(t,mx+1,2*n-1)
	{
		x=find();
		putchar(x+'a');
		getnext(x);
	}
	return 0;
}

C. Triple Flips

打表题×1。

考虑暴力，枚举一个等差数列是否选择，然后判断。

然后你会发现，题目中的 $12$ 非常的奇怪。然后你又发现长度为 $8$ 的序列的等差数列个数就是 $12$。

暴力打表发现，所有长度为 $8$ 的情况都是可以的。

也就是说，长度小于 $8$ 的可以暴力做，长度大于 $8$ 的要通过不超过 $\frac{n}{3}$ 次操作搞成长度小于 $8$ 的就可以进行暴力了。

考虑当前区间 $[l,r]$ 左边连续的三个数，大力分类讨论：

  1. $0**$，直接变成子问题 $[l+1,r]$ 。

  2. $111$，操作一次 $(l,l+1,l+2)$ 。

  3. $101$，操作一次 $(l,l+2,l+4)$。

  4. $100$，操作一次 $(l,l+3,l+6)$。

  5. $110$，不会。

把右边连续的三个数也考虑上，那么“不会”的情况就是 $110\cdots011$。

显然再分类一下就必定可以用两次将这六位都变成 $0$。

时间复杂度为 $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
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
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=1e5+5;
int n;
bool a[N],b[N],flag;
vector<pair<int,int> > vec,opt;
inline void update(int x,int y)
{
	a[x]^=1; a[y]^=1; a[(x+y)>>1]^=1;
}
void work(int l,int r)
{
	for(;r-l+1<8&&l>1;l--);
	for(;r-l+1<8&&r<n;r++);
	fo(i,l,r)
		fo(j,i+1,r)
			if((j-i)%2==0)
				opt.pb(mp(i,j));
	int k=opt.size(),m=1<<k;
	bool bo;
	ff(s,0,m)
	{
		fo(i,l,r) b[i]=a[i];
		bo=0;
		ff(i,0,k)
			if((1<<i)&s)
				update(opt[i].fi,opt[i].se);
		fo(i,l,r) if(a[i]) {bo=1; break;}
		if(!bo)
		{
			flag=1;
			ff(i,0,k) if((1<<i)&s) vec.pb(opt[i]);
			break;
		}
		fo(i,l,r) a[i]=b[i];
	}
}
void solve(int l,int r)
{
	if(r-l+1<=8) return work(l,r);
	if(!a[l]) return solve(l+1,r);
	if(!a[r]) return solve(l,r-1);
	if(a[l+1]&&a[l+2])
	{
		vec.pb(mp(l,l+2)),update(l,l+2);
		return solve(l+3,r);
	}
	if(a[l+2])
	{
		vec.pb(mp(l,l+4)),update(l,l+4);
		return solve(l+3,r);
	}
	if(!a[l+1])
	{
		vec.pb(mp(l,l+6)),update(l,l+6);
		return solve(l+3,r);
	}
	if(a[r-1]&&a[r-2])
	{
		vec.pb(mp(r-2,r)),update(r-2,r);
		return solve(l,r-3);
	}
	if(a[r-2])
	{
		vec.pb(mp(r-4,r)),update(r-4,r);
		return solve(l,r-3);
	}
	if(!a[r-1])
	{
		vec.pb(mp(r-6,r)),update(r-6,r);
		return solve(l,r-3);
	}
	if((r-l+1)&1)
	{
		vec.pb(mp(l,r)),update(l,r);
		vec.pb(mp(l+1,r-1)),update(l+1,r-1);
		return solve(l+3,r-3);
	}
	else
	{
		vec.pb(mp(l+1,r)),update(l+1,r);
		vec.pb(mp(l,r-1)),update(l,r-1);
		return solve(l+3,r-3);
	}
}

int main()
{
	n=read();
	fo(i,1,n) a[i]=read();
	solve(1,n);
	if(!flag) return puts("NO")&0;
	puts("YES");
	printf("%d\n",vec.size());
	for(auto v:vec) printf("%d %d %d\n",v.fi,(v.se+v.fi)/2,v.se);
	return 0;
}

D. Familiar Operations

打表题×2。

先把数 $x$ 质因数分解：$x=\prod p_i^{a_i}$，

然后把 $a_i$ 排序，$a$ 序列相同的数归为一类。

显然有用的数的 $a$ 序列长度不会超过 $8$。

通过打表发现，有意义的 $a$ 序列不同的个数在 $1000$ 以内。

通过打表又发现 $\prod (a_i+1)$ （即约数个数）不同的种类在 $200$ 左右。

打表可以用dfs实现。

接着就把不同的 $a$ 序列看成一个点，和在序列上加一或减一后形成的序列对应的点连一条权值为 $1$ 的边。

最终结果是使得两个序列的约数个数相等。

那么枚举最后相同的约数个数是哪一类，然后求出最短距离就好了。

求最短距离用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
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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int inf=0x3f3f3f3f;
int p[]={19,17,13,11,7,5,3,2};
map<vector<int>,int> ma;
vector<int> d[4010],vec,ve,E[4010],h[100010];
int cnt,siz,f[4000][4000];
queue<int> q;
inline void bfs(int id,vector<int> &V)
{
	fo(i,1,cnt) f[id][i]=inf;
	for(auto x:V) q.push(x),f[id][x]=0;
	for(int u;!q.empty();)
	{
		u=q.front(); q.pop();
		for(auto v:E[u])
			if(f[id][v]==inf)
			{
				f[id][v]=f[id][u]+1;
				q.push(v);
			}
	}
}
void dfs(ll now,int limit,int k)
{
	if(k==8)
	{
		++cnt;
		ma[vec]=cnt;
		d[cnt]=vec;
		int x=1;
		for(auto v:vec) x*=v+1;
		h[x].pb(cnt);

		ff(i,0,vec.size())
		if((i==0&&vec[i])||(i!=0&&vec[i]!=vec[i-1]))
		{
			ve=vec; ve[i]--;
			x=ma[ve];
			E[x].pb(cnt); E[cnt].pb(x);
		}

		return;
	}
	fo(i,0,30)
	{
		if(now>100000000ll) break;
		if(i>=limit) vec.pb(i),dfs(now,i,k+1),vec.pop_back();
		now*=p[k];
	}
}
inline ll g(int x)
{
	vec.clear();
	int y;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
		{
			for(y=0;x%i==0;x/=i) y++;
			vec.pb(y);
		}
	if(x!=1) vec.pb(1);
	for(;vec.size()<8;vec.pb(0));
	sort(all(vec));
	return ma[vec];
}

int main()
{
	memset(f,0x3f,sizeof(f));
	dfs(1,0,0);
	ff(i,1,100000)
		if(h[i].size())
			++siz,bfs(siz,h[i]);
	int x,y,ans;
	CASET
	{
		x=g(read()),y=g(read()); ans=inf;
		fo(i,1,siz) ans=min(ans,f[i][x]+f[i][y]);
		printf("%d\n",ans);
	}
	return 0;
}