Markdown编辑器
Sweetlemon
2018-08-24 09:36:28
设 $A_0, A_1, ..., A_n$ 都是集合，且有 $A_k\in A_{k+1}$ 和 $A_k \subseteq A_{k+1}$ 对一切 $k\in \{k\in \mathbb{N}∣0\le k<n\}$ 均成立。求 $A_n$ 元素个数的最小值。
$$A_0=\emptyset$$
$$A_n=A_{n-1}\cup \{A_{n-1}\}$$
$n$阶龙：$x(x+1)(x+2)\cdots (x+n-1)=\prod^{n-1}_{i=0}(x+i)$
龙的变形：
冠首：$(x-1)x(x+1)(x+2)\cdots(x+n-1)=\prod^{n-1}_{i=-1}(x+i)$
拖尾：$x(x+1)(x+2)\cdots(x+n-1)(x+n)=\prod^{n}_{i=0}(x+i)$
用新龙表示老龙：
$$\begin{aligned}&\ \ \ \ \ \ x(x+1)(x+2)\cdots(x+n-1)(x+n)-(x-1)x(x+1)(x+2)\cdots(x+n-1) \\ &=(n+1)x(x+1)(x+2)\cdots (x+n-1) \end{aligned}$$
求和时可以使用错位相减法。
$$\begin{aligned}&\ \ \ \ \ \ \ \frac{1}{4^2}+\frac{1}{7^2}+\cdots+\frac{1}{(3n-2)^2}\\&<\frac{1}{(4-1.5)(4+1.5)}+\frac{1}{(7-1.5)(7+1.5)}+\cdots+\frac{1}{(3n-3.5)(3n-0.5)}\\ &= \frac{1}{3}\left( \frac{1}{4-1.5}-\frac{1}{4+1.5}+\frac{1}{7-1.5}-\frac{1}{7+1.5} +\cdots+\frac{1}{3n-3.5}-\frac{1}{3n-0.5}\right)\\ &= \frac{1}{3}\left( \frac{1}{4-1.5}-\frac{1}{3n-0.5}\right)\\&<\frac{1}{3}\times \frac{2}{5}\\&=\frac{2}{15}\end{aligned}$$
[Images](https://pan.baidu.com/s/15BJdAsIKQ0Api7u11s0HXQ)
求数$n$的最小的约数$r$，使$r$满足性质$P$，这些性质满足这样的一个条件：若有$d|r$满足性质$P$，则有$r$也满足$P$。
首先$O(\sqrt{n})$直接暴力枚举因数显然可行，然而我们有更快的方法。
设$n=p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m}$
我们先从大到小枚举数$w_1$，使其成为最小的$w_1$使得$t=p_1^{w_1}p_2^{k_2}\ldots p_m^{k_m}$满足$P$。
再枚举$w_2$，使其成为最小的$w_2$使得$t=p_1^{w_1}p_2^{w_2}\ldots p_m^{k_m}$满足$P$。
一直枚举，得到数$t=p_1^{w_1}p_2^{w_2}\ldots p_m^{w_m}$，即为最终的答案。
正确性由性质的性质显然，不计因式分解，则总时间复杂度为$O(\lg n \cdot P)$。
这个方法的应用暂且知道两个：
一是求原根，枚举约数时直接改为上面的方法，验证一个数的时间降为$O(\lg^2 n)$。
二是求字符串的最小循环节，将本来的枚举约数改为上述算法，那就只用枚举$O(\lg n)$种长度。
问题：
~~1. 增量求最短路问题，如[探访](https://www.luogu.org/problemnew/show/T44251)~~ 已被证明是魔法森林的变形，SPFA动态加边是被认可的算法。
~~2. 贪心辅助搜索~~
$\begin{cases}x=2\\y=3\end{cases}$
$\begin{aligned}f(x)&=3x+2x+6\\&=5x+6\\&=5\times 3+6\\&=21\end{aligned}$
可修改$k$次的最长公共子串问题（$\text{O}(n^2)$）：
```cpp
#include <cstdio>
#include <cctype>
#define MAXIOLOG 25
#define MAXN 5005
using namespace std;
int io_temp[MAXIOLOG];
char stra[MAXN];
char strb[MAXN];
int f[MAXN];
//Start at i/j, changed k times, max length
int max(int a,int b);
typedef int io_t;
io_t uread(void);
void uwrite(io_t x,char spliter='\n');
void uread_str(char *str);
int main(void){
int n,kkk;
int ans=0;
n=uread(),kkk=uread();
uread_str(stra);
uread_str(strb);
int ubound=n-1;
for (int i=ubound;i>=0;i--){
//Common:[i,n-1](stra),[0,n-i-1](strb)
int al,ar,bl,br;
al=i,ar=n-1,bl=0,br=n-i-1;
for (int j=i,k=0;j<=ar;j++,k++)
f[k+1]=(stra[j]!=strb[k]);
f[0]=0;
for (int k=1;k<=br+1;k++)
f[k]+=f[k-1];
//j(l),k(r)
for (int j=0,k=1;k<=br+1;k++){
int target=f[k]-kkk;
while (f[j]<target)
j++;
ans=max(ans,k-j);
}
}
for (int i=1;i<=ubound;i++){
//Common:[0,n-i-1](stra),[i,n-1](strb)
int al,ar,bl,br;
al=0,ar=n-i-1,bl=i,br=n-1;
for (int j=0,k=i;j<=ar;j++,k++)
f[j+1]=(stra[j]!=strb[k]);
f[0]=0;
for (int j=1;j<=ar+1;j++)
f[j]+=f[j-1];
//j(l),k(r)
for (int j=0,k=1;k<=ar+1;k++){
int target=f[k]-kkk;
while (f[j]<target)
j++;
ans=max(ans,k-j);
}
}
uwrite(ans);
return 0;
}
inline int max(int a,int b){
return a>b?a:b;
}
io_t uread(void){
io_t ans=0;
int symbol=0;
char ch;
ch=getchar();
while (!isdigit(ch)){
if (ch=='-')
symbol=1;
ch=getchar();
}
while (isdigit(ch)){
ans=ans*10+(ch-'0');
ch=getchar();
}
return symbol?(-ans):(ans);
}
void uwrite(io_t x,char spliter){
if (!x){
putchar('0');
putchar(spliter);
return;
}
if (x<0){
putchar('-');
x=-x;
}
int len=0;
while (x){
io_temp[len++]=x%10;
x/=10;
}
while (len){
len--;
putchar(io_temp[len]+'0');
}
putchar(spliter);
}
void uread_str(char *str){
char ch;
ch=getchar();
while (!islower(ch))
ch=getchar();
while (islower(ch)){
(*str)=ch;
str++;
ch=getchar();
}
(*str)='\0';
}
```
---
骗分技巧 Codes
魔法阵 $10$分
```cpp
#include <iostream>
using namespace std;
int main(void){
int n,m;
cin >> n >> m;
for (int i=0;i<m;i++)
cout << "0 0 0 0\n";
return 0;
}
```
棋盘 $5$分
```cpp
#include <iostream>
using namespace std;
int main(void){
cout << "-1\n";
return 0;
}
```
小凯的疑惑 $30$分
```cpp
#include <iostream>
using namespace std;
int ok[10005]; //ok是标记数组，ok[i]==1表示金额i可以支付；数组开得比范围略大
int inf=10000; //假设不能支付的金额不会超过10000元
int max_coins=100; //假设每一种硬币支付的金额不会超过100枚
int main(void){
int a,b;
int ans=1; //1一定无法支付，否则没有答案
cin >> a >> b;
//枚举a,b两种硬币支付的数目
for (int i=0;i<=max_coins;i++) //支付a硬币数量
for (int j=0;j<=max_coins;j++) //支付b硬币数量
ok[a*i+b*j]=1; //支付i枚a硬币和j枚b硬币，是可以做到的
for (int i=0;i<=a*max_coins;i++)
if (ok[i]==0) //表明i不能被支付
ans=i; //由于i是从小到大枚举的，因此i就是当前不能支付的最大金额
cout << ans << endl;
return 0;
}
```
列队 $30$分
```cpp
```
天天爱跑步 $20$分
```cpp
#include <iostream>
using namespace std;
int w[1005]; //每个节点观察员的出现时间
int cnt[1005]; //每个节点观察员能够观察到的玩家数量
int main(void){
int n,m; //观察员的数量和玩家的数量
cin >> n >> m;
for (int i=1;i<=n-1;i++){
int u,v;
cin >> u >> v; //这个输入没用（骗分用不到）
}
for (int i=1;i<=n;i++)
cin >> w[i]; //读入观察员出现的时间
for (int i=1;i<=m;i++){
int s,t;
cin >> s >> t; //读入玩家的起点和终点
if (w[s]==0) //检查起点的观察员出现的时间是否为0
cnt[s]++; //如果为0，这个观察员能够观察到的玩家数目+1
}
for (int i=1;i<=n;i++)
cout << cnt[i] << ' ';
return 0;
}
```
写文件 示例（提交到洛谷上会Unaccepted）
```cpp
#include <cstdio>
using namespace std;
int main(void){
freopen("apb.in","r",stdin);
freopen("apb.out","w",stdout);
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
return 0;
}
```
线索 $40$分
```cpp
#include <iostream>
#include <algorithm>
#define MAXN 5005
using namespace std;
int color[5005]; //记录每条丝线的颜色
int temp_arr[5005]; //临时数组
int connect[5005][5005]={0}; //记录与每个点建立联系的点
int connect_num[5005]={0}; //记录与每个点建立联系的点的数量
int main(void){
int n,m; //n条丝线,m次操作
cin >> n >> m;
for (int i=1;i<=n;i++)
cin >> color[i]; //输入初始颜色
for (int i=0;i<m;i++){
int a,l,r,x;
cin >> a >> l >> r >> x;
switch (a){
case 1:
//把从l到r的丝线以及与这些丝线建立联系的所有丝线染成颜色x
for (int j=l;j<=r;j++){ //枚举区间内所有丝线
color[j]=x; //先把丝线本身染成x色
for (int k=0;k<connect_num[j];k++) //枚举与它建立联系的所有丝线connect[j][k]
color[connect[j][k]]=x; //染色
}
break;
case 2:
int is_connected=0; //记录l和r是否已经建立联系
color[l]=color[r]=x; //先对l,r进行染色
for (int k=0;k<connect_num[l];k++){
if (connect[l][k]==r){ //已经建立联系
is_connected=1;
break;
}
}
if (is_connected){ //如果已经建立联系，就只需要再染色就好了
for (int k=0;k<connect_num[l];k++) //枚举与l建立联系的所有丝线（也可以枚举与r建立联系的所有丝线）
color[connect[l][k]]=x; //染色
continue;
}
int new_connect_num=0; //记录形成的新的结所含的丝线数目
for (int k=0;k<connect_num[l];k++){
temp_arr[new_connect_num]=connect[l][k]; //把与l建立联系的丝线放进临时数组
new_connect_num++; //更新形成的新的结所含的丝线数目
}
for (int k=0;k<connect_num[r];k++){
temp_arr[new_connect_num]=connect[r][k]; //把与r建立联系的丝线放进临时数组
new_connect_num++; //更新形成的新的结所含的丝线数目
}
//再把l和r放进临时数组，并更新丝线数目
temp_arr[new_connect_num]=l;
new_connect_num++;
temp_arr[new_connect_num]=r;
new_connect_num++;
//对新的结中所有丝线进行染色，并更新与之建立联系的丝线数组(connect数组)和丝线数目(connect_num数组)
for (int j=0;j<new_connect_num;j++){
int now_process=temp_arr[j]; //记录当前处理的丝线编号
connect_num[now_process]=new_connect_num-1; //注意，减去1是因为丝线不能和自己建立联系
color[now_process]=x; //染色
int k=0; //k记录数组connect的下标
for (int t=0;t<new_connect_num;t++){
if (t==j) //不能把自己放进联系数组中
continue;
connect[now_process][k]=temp_arr[t]; //把temp_arr[t]放入联系数组
k++; //移动到下一个位置
}
}
break;
}
}
//输出每条丝线的颜色和与之建立联系的丝线数量
for (int i=1;i<=n;i++)
cout << color[i] << ' ';
cout << endl;
for (int i=1;i<=n;i++){
cout << connect_num[i] << ' ';
}
cout << endl;
return 0;
}
```