1
problem
对有限集合(A),存在函数(f:N→A)具有下述性质：若(|i－j|)是素数,则(f(i)≠f(j),N={1,2,…})．求有限集合A的元素的最少个数．
solution
【引理】(forall pge 2),若(p)为质数，则(p=4n+1)或(p=4n+3,nin mathbb N)
证明：①所有大于2的素数都是奇数
②(4n+1,4n+3)表示了所有的奇数
【证明】
(1,3,6,8)中每两个数的差为素数,所以(f(1),f(3),f(5),f(8))互不相同,(|A|≥4)．
另一方面,令(A={0,1,2,3})．对每一自然数(n),令(f(n)=noperatorname{mod} 4),则在(f(i)=f(j))时,(|i－j|)被4整除．所以不被4整除时，(f(i)
eq f(j))，因而(|i-j|)是质数。
因而(f)是满足条件的函数，A的元素个数最少为4．
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
long long read(){
int a=0,op=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') op=-1;c=getchar();}
while(c>='0'&&c<='9'){a*=10,a+=c^48,c=getchar();}
return a*op;
}
int n, ans = 0x3f3f3f3f, now, col[10], ans_col[10];
int main()
{
scanf("%d", &n);
if (n <= 6)
{
printf("%d
", (n + 1) / 2);
for (int i = 1; i <= n; i++)
printf("%d ", (i + 1) / 2);
}
else
{
puts("4");
for (int i = 1; i <= n; i++)
printf("%d ", 1 + (i & 3));
return 0;
}
return 0;
}
2
problem
对于给定的长(m)的序列(a)，求一个长度为(m)的序列(b)，满足以下性质：
①(forall iin[1,m],b_iin[0,n]∩mathbb Z)②(sumlimits_{i=1}^ma_ib_ile D)
在满足以上条件的情况下，求(left( sumlimits_{i=1}^mb_i+kmin_{i=1}^mb_i
ight)_{max})
(T)组数据.
solution
首先有贪心：(a_ile a_j)则(b_ige b_j)，将(a)排序，枚举有多少个(b)达到了上界(n)。若有(s)个达到了上界。我们设(b_{s+1}=x)，则答案为：
后面是形如(x+aleftlfloor dfrac{bx+c}{d}
ight
floor(age 0))的形式，这个函数形如锯齿状，有三种可能达到最大值。
(1)开始的第一个峰值
m
/|
/ | /|
|/ | /
|/
(2)结束的最后一个峰值
m
/|
/| / |/
/| / |/
/ |/
(3)结束点
m
/
/| /
/| / |/
/ |/
放在题中就是
- 尽可能提高(min b_i)，零头去提高(b_s)
- 尽可能提高(b_s)，零头去提高(min b_i)（虽然零头显然不足以提高）
- 让(min b_i)增加1，剩下全部去提高(b_s)
时间复杂度(O(Tnlog n))
code
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 200005;
int T, m;
long long k, n, ans, sum, D, a[Maxn];
int main()
{
freopen("array.in", "r", stdin);
freopen("array.out", "w", stdout);
scanf("%d", &T);
while (T--)
{
sum = ans = 0;
scanf("%lld%d%lld%lld", &n, &m, &k, &D);
for (int i = 1; i <= m; i++)
scanf("%lld", &a[i]), sum += a[i];
sort(a + 1, a + 1 + m);
for (int i = 1; i <= m; i++)
{
int whole = min(n, D / sum);
ans = max(ans, whole * (m + k - i + 1) + min(n - whole, (D - whole * sum) / a[i]) + n * (i - 1));
if (D < a[i] * n)
{
ans = max(ans, D / a[i] + n * (i - 1));
break;
}
if (i != m)
{
long long tmp = (D - a[i] * n) / (sum - a[i]) + 1;
if (D >= tmp * sum)
ans = max(ans, tmp * (m + k - i + 1) + min(n, (D - tmp * sum) / a[i]) + n * (i - 1));
}
sum -= a[i];
D -= a[i] * n;
}
printf("%lld
", ans);
}
return 0;
}
3
problem
你有一棵(n)节点的树 ，回答(m)个询问，每次询问给你两个整数(l,r)，问存在多少个整数(k)使得从(l)沿着(l ightarrow r)的简单路径走(k)步恰好到达(k)
solution
考虑将链拆分为(a)到(operatorname{lca}(a,b))与(operatorname{lca}(a,b))到(b)。记(operatorname{dep}(x))表示(x)的深度。
(a)到(operatorname{lca}(a,b))上的答案就是(operatorname{dep}(x)-operatorname{dep}(a)=x)的(x)个数，也就是说(operatorname{dep}(x)-x=operatorname{dep}(a))的(x)个数，另一段类似，先讨论一段。
注意到前面的这是个常数，令(b_x=operatorname{dep}(x)-x)，所以就是查链上有多少个点(x)满足(b_x)为常数(operatorname{dep}(a))，这个查分一下，可以变成查询点到根路径上有多少个点满足(b_x)为常数。
离线做一个树上前缀和，维护一个数组，表示每个(b_x)的出现次数，然后( ext{dfs})，( ext{dfs})到(x)时将(b_x)插入到这个数组中，( ext{dfs})出(x)的时候，将(b_x)删去，( ext{dfs})到一个点的时候处理所有被离线到这个点的询问即可。总时间复杂度(O(n+m))。
code
4
problem
对于一个长为01序列，初始都为1.先有(m)条指令，第(i)条指令是一对数((x_i,y_i))，你可以选择：
- 记录该条指令为1，表示将(y_i)变为0，(x_i)变为1
- 记录该条指令为0，表示将(x_i)变为0，(y_i)变为1
输出一个长为(m)的01串，第(i)个数（0或1）表示第(i)条指令的情况，并使得最终仍有不小于(leftlfloor dfrac{n}{2} ight floor)个数为1.
solution
看到(leftlfloor dfrac{n}{2} ight floor)容易想到两两分组。刚开始我们令((1,2))一组，((3,4))一组，如果最后一个数是奇数则(n)单独一组。一组((x,y))表示经过前若干个操作后可以在(x)或(y)中，组与组之间互不影响。
经过一个导线((x,y))后，如果之前分组((x),(y,z))合并则调整为((x,y),(z))，如果是((x,u),(y,v))则调整为((x,y),(u,v))。考虑所有情况容易发现这样不会出错。构造只需要反推。复杂度(O(n+m))。