CF1189

Posted on | Views:

$Div.2$

A Keanu Reeves

  • 显然只需要判断不分割是否可行,若不可行,就把第一个字符分出去,分成两段就好了.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=128;
char s[MAXN];
int main()
{
	int n=read();
	scanf("%s",s+1);
	int t[2]={0,0};
	for(int i=1;i<=n;++i)
		++t[s[i]-'0'];
	if(t[0]!=t[1])
	{
		puts("1");
		printf("%s\n",s+1);
	}
	else
	{
		puts("2");
		putchar(s[1]);
		putchar(' ');
		for(int i=2;i<=n;++i)
			putchar(s[i]);
		puts("");
	}
	return 0;
}

B Number CirCle

  • 假的一批,这个题被罚了 $3$ 次.
  • 构造方法是先将元素排序,先将最大的放在任意一个位置 $x$ ,然后次大的放在 $x+1$ ,第三大放在 $x-1$ ,第四大放在 $x+1\dots$
  • 然后检验是否合法,若这样放置不合法,则其他所有放置也不可能合法.
  • 为什么?因为题面中的图和样例就是这样做的.大概是因为一个比较大的数,它旁边的数尽量也安排成比较大的数,这样对于双方都最优.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,a[MAXN];
int b[MAXN];
bool check()
{
	if(b[1]>=b[n]+b[2])
		return false;
	if(b[n]>=b[1]+b[n-1])
		return false;
	for(int i=2;i<n;++i)
		if(b[i]>=b[i-1]+b[i+1])
			return false;
	return true;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n);
	int x=(n+1)/2;
	b[x]=a[n];
	int tot=n-1;
	for(int i=1;tot;++i)
	{
		b[x+i]=a[tot--];
		if(tot)
			b[x-i]=a[tot--];
	}
	if(check())
	{
		puts("YES");
		for(int i=1;i<=n;++i)
			printf("%d ",b[i]);
	}
	else
		puts("NO");
	return 0;
}

C Candies!

  • 仔细思考一下,不难发现答案就是 $\lfloor \frac {sum(l,r)} {10}\rfloor$ .
  • 因为这个答案就是进位的次数,与运算顺序无关,直接将它们加起来 $/10$ ,得到的就是进位次数. 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int a[MAXN];
int main()
{
	int n=read();
	for(int i=1;i<=n;++i)
		a[i]=a[i-1]+read();
	int q=read();
	while(q--)
	{
		int l=read(),r=read();
		int ans=a[r]-a[l-1];
		ans/=10;
		printf("%d\n",ans);
	}
	return 0;
}

D1 Add on a Tree

  • 容易发现,当且仅当存在两条边,它们只能同时加减同一个数时,就无法得到它们的权值不同的情况.
  • 若存在这样两条边,则一定存在两条这样相邻的边,要让它们满足条件,它们的公共点度数一定为 $2$ ,即不存在其他的边.
  • 于是判一下是否存在度数为 $2$ 的点即可.

代码就是 $D2$ 的一小部分,就不贴了.

D2 Add on a Tree: Revolution

好题.

  • 判断合法性和 $D1$ 一样,判是否有度数为 $2$ 的点.若合法,要将每条边的权值都改为要求的权值.特判 $n=2$ .
  • 考虑如何给一条路径 $(u,L_0)$ 上的所有边加上一个权值 $x$ ,其中 $L_0$ 为叶子节点.先选择一个非叶子节点作为根.
  • $u$ 的度数至少为 $3$ ,故一定可以找到另外两个叶子节点 $L_1,L_2$ ,并且这 $3$ 个叶子节点在 $u$ 的 $3$ 个不同子树内.
  • 因为边权都是偶数( $pairwise$ ),所以我们要加的 $x$ 也都选择偶数.于是执行 $(L_0,L_1,\frac x 2),(L_0,L_2,\frac x 2),(L_1,L_2,-\frac x 2)$ 这三个操作,路径 $(u,L_0)$ 上所有边权值就 $+x$ 了.
  • 再来解决原问题,对每条边,维护当前边上的权值与要求的权值还差 $\Delta$ ,然后从根节点开始 $dfs$ ,遍历到 $u$ 时,对它的每个儿子节点 $v$ ,选出子树 $v$ 内任一个叶子节点 $L_0$ ,用上面的操作给路径 $(u,L_0)$ 上的边加上 $\Delta_{u,v}$ 即可.
  • $n\le 1000$ ,可以暴力找/修改,不用写数据结构.时间复杂度 $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
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e3+10;
int head[MAXN],ecnt=0,to[MAXN<<1],nx[MAXN<<1],val[MAXN<<1];
int n,m=0;
struct opt
{
	int u,v;
	ll x;
	opt(int u=0,int v=0,ll x=0):u(u),v(v),x(x) {}
};
queue<opt> Q;
void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
int deg[MAXN],dfn[MAXN],siz[MAXN],idx=0;
int fa[MAXN];
ll Delta[MAXN];//Edge(i,fa_i)
bool In_SubTree(int v,int x)
{
	return dfn[v]<=dfn[x] && dfn[x]<=dfn[v]+siz[v]-1;
}
void Init(int u,int Fa)
{
	dfn[u]=++idx;
	siz[u]=1;
	fa[u]=Fa;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==Fa)
			continue;
		Delta[v]=val[i];
		Init(v,u);
		siz[u]+=siz[v];
	}
}
int rt;
void Assign(int u,int v0,int L0,ll x)
{
	int L1=0,L2=0;
	if(u!=rt)
	{
		for(int i=1;i<=n;++i)
		{
			if(deg[i]==1 && !In_SubTree(v0,i))
			{
				if(!L1 && In_SubTree(u,i))
					L1=i;
				if(!L2 && !In_SubTree(u,i))
					L2=i;
				if(L1 && L2)
					break;
			}
		}
	}
	else
	{
		int v1=0,v2;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v==v0 || v==v1)
				continue;
			if(!v1)
				v1=v;
			else
				v2=v;
		}
		for(int i=1;i<=n;++i)
			if(deg[i]==1 && In_SubTree(v1,i))
				L1=i;
			else if(deg[i]==1 && In_SubTree(v2,i))
				L2=i;
	}
	m+=3;
	Q.push(opt(L0,L1,x/2));
	Q.push(opt(L0,L2,x/2));
	Q.push(opt(L1,L2,-x/2));
	while(L0!=u)
	{
		Delta[L0]-=x;
		L0=fa[L0];
	}
}
void dfs(int u)
{
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa[u])
			continue;
		int L0=0;
		for(int j=1;j<=n && !L0;++j)
			if(deg[j]==1 && In_SubTree(v,j))
				L0=j;
		Assign(u,v,L0,Delta[v]);
		dfs(v);
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
		++deg[u],++deg[v];
	}
	if(n==2)
	{
		puts("YES");
		puts("1");
		printf("1 2 %d\n",val[1]);
		return 0;
	}
	for(int i=1;i<=n;++i)
		if(deg[i]==2)
		{
			puts("NO");
			return 0;
		}
	puts("YES");
	rt=0;
	for(int i=1;i<=n && !rt;++i)
		if(deg[i]>1)
			rt=i;
	Init(rt,0);
	dfs(rt);
	cout<<m<<endl;
	opt tmp;
	while(!Q.empty())
	{
		tmp=Q.front();
		Q.pop();
		printf("%d %d %I64d\n",tmp.u,tmp.v,tmp.x);
	}
	return 0;
}

E Count Pairs

  • 这个题比 $D2$ 简单许多.对于原方程,因为 $a_i\not= a_j$ ,两边乘上 $(a_i-a_j)$ ,可得
    $$
    a_i^4 - a_j^4 \equiv k(a_i-a_j)
    $$

  • 可以 $O(n) $枚举 $j$ ,计算有多少个 $i$ 满足方程.于是 $a_j$ 此时为常数,整理一下,得到
    $$
    a_i^4-k\cdot a_i \equiv a_j^4-k\cdot a_j
    $$

  • $k$ 是不变的,所以用一个 $map$ 对于每个 $x\in [0,P)$ 记录 $a_i^4-k\cdot a_i\equiv x$ 的 $i$ 有多少个就好了. 

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;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int P;
int add(int a,int b)
{
	return (a + b) % P;
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int pw4(int x)
{
	x=mul(x,x);
	x=mul(x,x);
	return x;
}
const int MAXN=3e5+10;
unordered_map<int,int> cnt;
int n,a[MAXN];
int main()
{
	n=read(),P=read();
	int k=read();
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		int x=pw4(a[i]);
		x=add(x,mul(P-k,a[i]));
		if(cnt.find(x)!=cnt.end())
			ans+=cnt[x];
		++cnt[x];
	}
	cout<<ans<<endl;
	return 0;
}

F Array Beauty

  • 元素的顺序是不影响答案的,所以可以先将所有元素从小到大排序.记最大的元素为 $m$ .
  • $Beauty$ 值最大为 $m$ ,记 $Beauty$ 值 $\ge x$ 的子序列有 $p_x$ 个,那么答案为 $\sum_{x=1}^m p_x$ ,因为若一个子序列的 $Beauty$ 值为 $s$ ,它就会在求和中贡献 $s$ 次.
  • 枚举 $x$ 的值,用 $dp$ 求解 $p_x$ .设 $f(i,j)$ 表示以第 $i$ 个数结尾,长度为 $j$ 的,且美丽值 $\ge x$ 的子序列数目.
  • 转移有 $f(i,j)=\sum f(d,j-1),d<i,a_j-a_d\ge x$ .由于 $a$ 已经排过序,所以合法的 $d$ 一定是一段前缀,可以用 $two\ pointer$ 维护,并记录 $f$ 的前缀和.这样, $p_x=\sum f(i,k)$ ,求一个 $p_x$ 的时间复杂度为 $O(n\cdot k)$ .
  • 注意到 $x$ 只需要枚举到 $\lfloor \frac m {k-1}\rfloor$ ,若 $x$ 大于这个值,子序列首尾元素差值就会 $> m$ ,不可能出现.
  • 所以整个问题的时间复杂度为 $O(m \cdot 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
const int MAXN=1e3+10;
int n,k;
int f[MAXN][MAXN],sum[MAXN][MAXN],a[MAXN];
int solve(int x)
{
	for(int i=1;i<=n;++i)
		f[i][1]=1,sum[i][1]=i;
	for(int j=2;j<=k;++j)
	{
		sum[0][j]=0;
		int r=1;
		for(int i=1;i<=n;++i)
		{
			while(a[r]<=a[i]-x)
				++r;
			f[i][j]=sum[r-1][j-1];
			sum[i][j]=add(sum[i-1][j],f[i][j]);
		}
	}
	return sum[n][k];
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n);
	int m=a[n];
	int ans=0;
	for(int x=1;x<=m/(k-1);++x)
		ans=add(ans,solve(x));
	cout<<ans<<endl;
	return 0;
}