B. 学数学
打表只发现了连续的$(2, 8)(8, 30)(30, 112)$似乎比较有规律的样子，通过他们算出来的$a=xy+1，b=x^2+y^2$恰好是$2^2$倍数，如果是“以3为起点的链表”就是$3^2$.但是不知道有什么用……
于是枚举这个像链表头一样的东西$i*i*i<=n$，剩下的另一个数循环一下，每次让$x$等于找到的$y$再继续找。估分$60$.
结果由于没有预处理前缀和$TLE 20$，好像不久之前某$T4$的$KMP$还有更多的题都是这么错的……
有更高级的规律：从上一对$x，y$得到下一对的方式就是$x=y'，y=ky'-x'$，把所有答案的最小值放进数组里排完序二分答案。
有一个细节就是乘法会越界，可以开$long double$也可以把它写成除法。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 2;
int T, cnt;
ll n, a[maxn];
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("math.in", "r", stdin);
freopen("math.out", "w", stdout);
n = 1e18; a[++cnt] = 1;
for(ll i=2; i<=1000000; i++)
{
ll k = i * i, x = i;
for(ll y=i*i*i; y<=n; )
{
a[++cnt] = y;
if((n + x) / y < k) break; //写成乘法因为会越界
ll nxty = k * y - x;
x = y; y = nxty;
}
}
sort(a+1, a+1+cnt);
T = read();
while(T--)
{
n = read();
printf("%d\n", upper_bound(a+1, a+1+cnt, n)-a-1);
}
return 0;
}
C. 早该砍砍了
由于我的$dp$稳定输出qpow(2, n-1)，不会改了就直接交了个这个。。
关于正经的暴力做法，有效的覆盖最多有$n-1$次，最短的有效区间长度是$2$，每次最少“同化”一个，于是$dfs$并记录步数，每一步枚举$l$和$r$，$map$记录过程中的每一个状态。
code
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3007;
const int mod = 1e9 + 7;
int n, h[maxn], f[maxn][maxn], ans;
map<int, bool> mp;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
inline int getsum()
{
int ans = 0;
for(int i=1; i<=n; i++) ans = (ans << 1) + (ans << 3) + h[i];
return ans;
}
void dfs(int now)
{
int sum = getsum();
if(mp.find(sum) == mp.end())
{
mp[sum] = 1; ans++;
}
if(now == n-1) return;
int d[10];
for(int i=1; i<=n; i++) d[i] = h[i];
for(int i=1; i<=n; i++)
{
for(int j=2; i+j-1<=n; j++)
{
int mi = h[i];
for(int k=i+1; k<=i+j-1; k++) mi = min(mi, h[k]);
for(int k=i; k<=i+j-1; k++) h[k] = mi;
dfs(now + 1);
for(int k=i; k<=i+j-1; k++) h[k] = d[k];
}
}
}
void solve()
{
for(int i=1; i<=n; i++) f[n][i] = n - i + 1;
for(int i=n-1; i>=1; i--)
{
for(int j=1; j<=i; j++) f[i][j] = (f[i][j] + f[i+1][j]) % mod;
for(int j=i-1; j>=1; j--) f[i][j] = (f[i][j] + f[i][j+1]) % mod;
}
printf("%d\n", f[1][1]);
exit(0);
}
int main()
{
freopen("cut.in", "r", stdin);
freopen("cut.out", "w", stdout);
n = read(); bool sp = 1;
for(int i=1; i<=n; i++)
{
h[i] = read();
if(h[i] != i) sp = 0;
}
if(sp) solve();
dfs(0);
printf("%d\n", ans);
return 0;
}
鹤了一下……
把$i$看成时间，$f[i][j]$表示轮到$i$贡献的时候前缀的方案数，每一个点能贡献方案的区间是它作为最小值的区间，并且覆盖不可以跳跃。
从$l$开始如果$l$被覆盖，覆盖前和覆盖后增加的恰好是$f[i-1][l-1]$，再考虑$l+1$，有$l+1$是否被覆盖的情况，如果$l+1$被覆盖了还可以继续讨论$l$，方案数的增量就是$f[i-1][l]+f[i-1][l-1]$，发现可以求前缀和。
code
//任尘世繁华，唯有守护你的一切，才是我此生唯一的使命。
//——次元战争·红龙
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3007;
const int mod = 1e9 + 7;
int f[maxn][maxn], n, a[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void add(int &x, int y) {x += y; x = x >= mod ? x - mod : x;}
int main()
{
freopen("cut.in", "r", stdin);
freopen("cut.out", "w", stdout);
n = read(); for(int i=1; i<=n; i++) a[i] = read();
f[0][0] = 1;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=n; j++) f[i][j] = f[i-1][j];
int l = i, r = i;
for(l=i; l>=1 && a[l]>=a[i]; l--); l++;
for(r=i; r<=n && a[r]>=a[i]; r++); r--;
int now = l ? f[i][l-1] : 0;
for(int j=l; j<=r; j++) add(f[i][j], now), add(now, f[i-1][j]);
}
printf("%d\n", f[n][n]);
return 0;
}