假算法基础集训营名副其实。

只会5题的我真是菜爆了qwq。

所以写完5题还剩下1h就来写题解是不是没救了啊

这场的题解按难度排序...(其实就是我过题的顺序)

顺序是DJGHC。

赛后吐槽:

A到底卡什么啊
B这么毒瘤的大模拟咋写啊
我居然还有前50,手速果然重要
想中牛可乐qwq

D

做法:模拟

按题意模拟...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
int n;
int a[N];
ll ans = 0;
 
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {scanf("%d", &a[i]); if(a[i] < 60) ans += 400;}
    printf("%lld\n", ans);
}

J

做法:贪心

因为可以把复习时间拆开,所以直接按开始考试的时间排序一波。
然后假装我们可以篡改考试时间,复习完了就让他考试(也就是+2h)
每次考试前看复习时间有没有超过考试的开始时间就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define N 100010
int n;
struct Node {
    ll a, b;
}a[N];
 
bool cmp(Node a, Node b) {
    return a.b < b.b;
}
 
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i].a);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i].b);
    sort(a + 1, a + n + 1, cmp);
    ll cnt = 0;
    for(int i = 1; i <= n; ++i) {
        cnt += a[i].a;
        if(cnt > a[i].b) return puts("NO"), 0;
        cnt += 2;
   //     printf("%lld\n", cnt);
    }
    puts("YES");
    return 0;
}

G

做法:dp

不知道这题的std是啥...赛后看看。
其实这题有原题的...原题:LGOJP2758
其实就是按原题那个做法搞一波,然后看看dp出来的结果会不会小于等于2即可

\(f[i][j]\)表示前\(i\)个字符变成结果串的前\(j\)个字符要变换多少次。
那么删除即为\(f[i][j]=min(f[i-1][j]+1)\)
插入即为\(f[i][j]=min(f[i][j-1]+1)\)
替换即为\(f[i][j]=min(f[i-1][j-1]+1)\)
初始化边界为\(f[0][i]=f[i][0]=i\)

#include <bits/stdc++.h>
using namespace std;

#define N 2010
int f[N][N];
char s[N], t[N];
//第一个串到i,第二个串到j最小操作次数 

int main() {
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    for(int i = 1; i <= n; ++i) f[i][0] = i;
    for(int i = 1; i <= m; ++i) f[0][i] = i;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(s[i] == t[j]) {f[i][j] = f[i - 1][j - 1]; continue;} //正好相等就不管 
            f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1; 
            //删除,插入,替换 
        }
    }
    if(f[n][m] <= 2) puts("YES");
    else puts("NO");
}

至于这题的LCS做法错在哪里?
事实上就是因为LCS没办法考虑位置。
这里给一组hack数据:
abxyabcd
ababxycd
实际上是no但是LCS做法会输出yes

H

做法:数论

考虑怎么让一个数有超过10个因数,显然只要有4个质因子就够了。
然后任意两个数都互质这意味着所有数没有相同的质因子。
而题目给的因数是\(x*y\)的,这意味着每个数只要有两个质因子就够了。
于是我们预处理出前4000个素数,每两个丢在一起,让他们组成一个数。
注意要尽量平均不然会超过题目的要求。如:第1个和第4000个组合在一起。
那么这题就做完了。
我忘记把freopen删掉居然被罚时了QAQ
(代码里到6000跳是没有必要的不过懒得改了)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e8 + 10;
bool vis[N];
ll p[8000], ans[3000];
int n; 

int main() {
//  freopen("ans.out", "w", stdout);
    int cnt = 0;
    for(ll i = 2; i <= (ll)1e8; ++i) {
        if(cnt > 6000) break;
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && i * p[j] <= (ll)1e8; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
    for(int i = 1; i <= 2000; ++i) ans[i] = 1;
    for(int i = 1; i <= 2000; ++i) {
        ans[i] *= p[i];
    }
    int qwq = 2000;
    for(int i = 2000; i; --i) {
        ans[i] *= p[++qwq];
    }
    for(int i = 1; i <= 2000; ++i) printf("%lld ", ans[i]);
}

C

做法:数论(找规律)

其实这个是我弃赛了之后水QQ被一个大佬点醒了这题的思路,并且研究了一波样例解释才会的。
我写这种脑洞题是真的菜。

1=1
2=2
3=1+2
4=6-2
5=6-1
6=6
7=6+1
8=6+2
9=6+2+1
10=11-1
11=11
12=11+1
13=11+2
14=11+2+1
15=11+6-2
16=11+6-1
17=11+6
18=11+6+1
19=11+6+2
20=11+6+2+1

并且采用人脑+草稿纸将它继续推下去
研究一下这个可能会发现一些奇奇怪怪的规律
\(3^0,3^1,3^2...\)这个数列的前缀和中的数会影响答案
(即\(1,4,13,40...\)
即1的答案是1,2-3的答案是2,4-12的答案是3,13-39的答案是4
没人提醒完全想不到这个结论(我好菜啊)
数论还是要加强qwq
证明我是不会证的,这个结论就是猜出来的...证明之后放std的证明吧

官方题解证明:

什么?你说\(n<=10^{1000}\)
人生苦短我用python

a = 0
b = 0
c = 1
n = int(input())
while b < n :
    a = a + 1
    b = b + c
    c = c * 3
print(a)

其他题真的写不动了,只能靠手速混在第一页混日子过。

官方题解