A 解锁专家
一开始看到这个A题的时候我的想法是直接DFS进行暴力搜索（因为没有注意到是多组输入），于是代码成功的TLE了。但是这个代码是一个很好的对拍代码！
然后手动写了几个数据发现好像前后之间存在一定的关联，于是我就用我TLE的代码进行打表去观察数据了
打表代码：
void dfs(int k) {
if (k > n) {
cnt++;
return;
}
int pre = 0;
if (k > 0)
pre = k - 1;
if (vis[pre]) {
dfs(k+1);
}
else {
vis[k] = 1;
dfs(k+1);
vis[k] = 0;
dfs(k+1);
}
}
然后成功发现了规律其实就是 F[i] = F[i-1] + F[i-2] + 1，再注意下离线打表就可以了 LL f[105];
void pre() {
f[1] = 1;
f[2] = 2;
for (int i = 3;i <= 100; i++) {
f[i] = f[i - 1] + f[i - 2] + 1;
f[i] %= MOD;
}
}
int main() {
pre();
int n;
while (~scanf("%d",&n)) {
printf("%lld\n", f[n]);
}
return 0;
} B 麻烦的杰西
这个题应该是一个很有意思的题目。从题意来看我们很容易想得到我们应该找一个连续的区间，也就是找到左边界和右边界。但是我们如果采取暴力的方式去查找的话，那么这道题就会TLE （O(N^2)）
但是其实当前 a[i] 的左边界是和 a[i-1] 的左边界有关系的，我们其实就是在 a[i-1] 的基础上去更新 a[i] 。这样算法复杂度就是O(N)，有点类似于dp的思想。其实我们就是不断的向前去找就可以了。而对于右边界的话也是一样的，我们只要不断的向后去找就可以了。具体的还是看代码更好理解
int a[maxn],l[maxn],r[maxn];
int main() {
int n;
while (~scanf("%d",&n)) {
for (int i = 1;i <= n;i++) {
scanf("%d",&a[i]);
l[i] = 0;
r[i] = 0;
}
l[1] = 1;
r[n] = n;
for (int i = 2;i <= n;i++) {
int t = i-1;
if (a[i-1] >= a[i]) {
while (t - 1 >= 1 && a[t-1] >= a[i])
t = l[t-1];
l[i] = t;
}
else
l[i] = i;
}
for (int i = n-1;i >= 1;i--) {
int t = i+1;
if (a[t] >= a[i]) {
while (t + 1 <= n && a[t+1] >= a[i])
t = r[t+1];
r[i] = t;
}
else
r[i] = i;
}
LL ans = 0;
int height = 0;
for (int i = 1;i <= n;i++) {
LL sum = (LL)a[i]*(r[i]-l[i]+1);
if (sum > ans) {
height = a[i];
ans = sum;
}
}
printf("%d %lld\n",height,ans);
}
return 0;
} C 最大模数
其实就是一个二项式展开定理，如果把它展开了我们其实很容易发现答案其实就是 2 * (k * a) k = ( 1,3,5,7,9...(2*n-1) )
然后我们只要不断的去找其中最大的那个就好了，然后其中也存在一些循环节，如果出现重复的我们就直接停止搜索了
int b[maxn];
int main() {
LL a;
b[0] = 1;
b[1] = 3;
for (int i = 2;i < maxn;i++) {
b[i] = b[i-1] + 2;
if (b[i] > 1000000)
break;
}
while (~scanf("%lld",&a)) {
LL sum = a * a;
LL ans = 0;
LL cnt = 0;
for (int i = 0;i < maxn;i++) {
if (i == 0)
cnt = (2 * a * b[i]) % sum;
ans = std::max(ans,(2*a*b[i]) % sum);
if (i != 0 && ((2 * a * b[i]) % sum) == cnt)
break;
}
printf("%lld\n",ans);
}
return 0;
} 也算是一个规律题吧。我们其实只要发现 0 和 2 的相对位置是不会发生改变的，然后 1 都在第一个2 的前面 ，那么这题就过了
char ch[maxn];
int main() {
while (~scanf("%s",ch)) {
int len = strlen(ch);
int cnt0 = 0,cnt1 = 0;
for (int i = 0;i < len;i++) {
if (ch[i] == '1')
cnt1++;
}
for (int i = 0;i < len;i++) {
if (ch[i] == '0')
cnt0++;
if (ch[i] == '2') {
for (int j = 0;j < cnt0;j++)
printf("0");
cnt0 = 0;
for (int j = 0;j < cnt1;j++)
printf("1");
cnt1 = 0;
printf("2");
}
}
for (int i = 0;i < cnt0;i++)
printf("0");
printf("\n");
}
return 0;
} E 一步两步是魔鬼的步伐
典型的二分题目，一开始我想偏了，想成了贪心题目，结果贪到最后都没贪出来。 如果有人聚聚贪出来了，麻烦告诉我下思路
二分的话就是直接对答案进行二分，然后找到一个 符合题意 的最大的答案就好了
int a[maxn];
int L,N,M;
bool check(int k) {
int last = 0,cnt = 0;
for (int i = 1;i <= N+1;i++) {
if (a[i] - last >= k) {
last = a[i];
}
else
cnt++;
}
if (cnt <= M)
return true;
else
return false;
}
int main() {
while (~scanf("%d%d%d",&L,&N,&M)) {
for (int i = 1;i <= N;i++) {
scanf("%d",&a[i]);
}
a[N+1] = L;
std::sort(a+1,a+1+N);
int l = 0,r = L;
int ans = 0;
while (l <= r) {
int mid = (l + r ) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
printf("%d\n",ans);
}
return 0;
} F 参赛
就是一个模拟题，然后注意一下特殊的就是不能最大化的拆，因为不一定会有教练
G 数数有多少个水坑
简单的方向DFS
H 你相信爱情吗
这也是一个规律题吧？感觉只要想到了 GCD 的话那么这题就不难了
I 师姐我想要红包
简单的DFS没什么好说的了
J 试试划水
ans += cntz * cntu ，统计计数就好了
K 钟Sir的任务
暴力就好了
L JAJA_Xin的小心思
贪心
京公网安备 11010502036488号