@toc
官方题目链接：
https://www.lanqiao.cn/courses/2786/learning/?id=70881
第1题——平方序列 （5分）
- 题目：
- 思路：
2x^2 = 2019^2+y^2, 从2020开始枚举x, 用公式算出y，如果是个正数就是最小的。
- 答案为7020
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int x = 2020; x <= 9999; x++){
int y2 = 2*x*x-2019*2019;
int y = sqrt(y2);
if(y*y==y2){
cout<<x+y<<"\n";
return 0;
}
}
return 0;
}
第2题——质数拆分 （5分）
- 题意：
- 思路：
先把1-2019的质数都筛出来，然后作为体积Vi，跑容量为2019的背包。
fij表示到第i个素数为止，拼成j的方法数。
记得不开ll会爆。
答案是55965365465060
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 5050; //线性筛 LL vis[maxn], primes[maxn], cnt; void get_primes(int n){ for(int i = 2; i <= n; i++){ if(!vis[i])primes[++cnt]=i; for(int j = 1; primes[j] <= n/i; j++){ vis[primes[j]*i] = 1; if(i%primes[j]==0)break; } } } LL f[maxn][maxn]; int main(){ get_primes(maxn-10); f[0][0] = 1; for(LL i = 1; i <= cnt; i++){ for(LL j = 0; j <= 2019; j++){ f[i][j] = f[i-1][j]; if(j>=primes[i])f[i][j] += f[i-1][j-primes[i]]; } } cout<<f[cnt][2019]; return 0; }
第3题——拼接 （10分）
- 题目
- 思路：
找规律，发现除了沿右边界分割的情况，右上角那一个必选。
然后第一行可以选1-7的格子，第二行能选1-6，后面依次类推
且右端一定靠近对角线，下一行不能多余上一行，上下两行要连续。
然后dfs
所以答案是128
#include<bits/stdc++.h> using namespace std; int a[50], n = 7; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int ans = 1; void dfs(int cur, int now){ if(cur>=n || now==0){ ans++; for(int i = 1; i <= n; i++)cout<<a[i]<<' '; cout<<"\n"; return ; } for(int i = 0; i<now && i<=n-cur; i++){ a[cur+1] = i; dfs(cur+1, i); a[cur+1] = 0; } } int main(){ for(int i = 1; i <= n; i++){ memset(a,0,sizeof(a)); a[1] = i; dfs(1,i); } cout<<ans; return 0; }
第4题——求值 （10分）
- 题意：
- 思路
数字有点小，，才100，暴力枚举每个数，求约数个数，第一个有100个约数的数肯定很小呀，然后输出就好了 答案是45360
#include<bits/stdc++.h> using namespace std; int main(){ for(int i = 100; ;i++){ int cnt = 0; for(int j = 1; j <= i; j++){ if(i%j==0)cnt++; } if(cnt==100){ cout<<i<<"\n"; return 0; } } return 0; }
第5题——路径计数 （15分）
- 题意：
- 思路：
直接0，0开始往外dfs走12步看看有没有回来即可。
对于自交的情况，因为走过的路不会往回走，所以不需要考虑。
！！！但是有一个特判没考虑到，因为vis是回溯当前的点不能走，但是我往右走一步可以直接往回走到起点，这个时候vis是不会影响到原点的，所以会炸，要减去这两个值。
所以答案是206
#include<bits/stdc++.h> using namespace std; int ans = 0; int ok = 0; int dx[] = {0,0,-1,1}; int dy[] = {1,-1,0,0}; int vis[10][10]; void dfs(int x, int y, int s){ if(s>12)return ; if(x==0 && y==0){ ok++; if(ok==2 && s<=12){ ok = 1; ans++; return ; } } for(int i = 0; i < 4; i++){ int nx = x+dx[i], ny = y+dy[i]; if(nx>=0&&nx<=7&&ny>=0&&ny<=7 && vis[nx][ny]==0){ vis[nx][ny] = 1; dfs(nx,ny,s+1); vis[nx][ny] = 0; } } } int main(){ dfs(0,0,0); cout<<ans-2<<"\n"; return 0; }
第6题——最优包含 （15分）
- 题意：
- 思路：给出字符串S和T，求S修改多少个字母能包含T。
- 类似于LCS，令fi表示S串前i个字符,包含T串前j个字符所需要的最小修改次数。
分四种情况转移。反正nm范围小，随便操作。
#include<bits/stdc++.h>
using namespace std;
int f[1010][1010];
int main(){
string a, b; cin>>a>>b;
int n = a.size(), m = b.size();
a = "0"+a, b = "0"+b;
memset(f,0x3f,sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++){
f[i][0] = 0;
for(int j = 1; j <= m; j++){
f[i][j] = f[i-1][j]; //s[i-1]改到t[j]的最值，不用s[i]这个字符
if(a[i]==b[j])f[i][j] = min(f[i][j], f[i-1][j-1]);//s[i-1]改到t[j-1]，s[i]与t[j]配对
else f[i][j] = min(f[i][j], f[i-1][j-1]+1);//修改一个，增加一次次数
}
}
cout<<f[n][m]<<"\n";
return 0;
}
第7题——排列数 （20分）
- 题意：
- 思路：
求1-n的排列中，有多少个是k单调的，k单调指的是有k-1个数比两边的大或小。
dp，记f(i,j)表示第i个数，j个折点的方案数。
- 转移时考虑将第i个数放入1~i-1的排列中，对折点数量的影响。
分类讨论插入的情况。
如果插入单调序列中，折点数量+2，波峰和波谷各一个。
如果插入波峰或波谷的两端，折点数量不变。
如果插入波峰或波谷的重心，折点数量+2。
如果插入区间端点(0或i-1)，折点数量+1。
- 所以
f[i][j]=f[i−1][j]∗x+f[i−1][j−1]∗y+f[i−1][j−2]∗z
x,y,z分别为放弃后折点数量+0，+1，+2的方案数。
所以f[i][j]=f[i−1][j]∗j+f[i−1][j−1]∗2+f[i−1][j−2]∗(i−j).
#include<bits/stdc++.h>
using namespace std;
const int mod = 123456;
int f[550][550];
int main(){
int n, k; cin>>n>>k;
f[1][1] = 1; f[2][1] = 2;
for(int i = 3; i <= n; i++){
for(int j = 1; j<=k && j<=i; j++){
f[i][j] = (f[i][j]+f[i-1][j]*j%mod+f[i-1][j-1]*2%mod)%mod;
if(j>1)f[i][j] = (f[i][j]+f[i-1][j-2]*(i-j))%mod;
}
}
cout<<f[n][k]<<"\n";
return 0;
}
第8题——解谜游戏 （20分）
- 题意：
- 思路：多组样例，每次三个字符串，可以旋转或者交换内外圈0点，求能否外圈绿色，中圈红色，内圈黄色。
- 模拟转圈的过程，可以发现，内圈转完4次（转完一圈），中圈转半圈，大圈转三分之一圈，那么可以知道，内圈0号位置对应中圈有两个位置（0号和4号），外圈有三个位置（0号、4号、8号，即可以发生换圈位置的情况）。
可以分成四个组，只有在组内才能发生跨圈的操作，所以只要每个的条件都满足1个Y、2个R、3个G就可以达成目标输出YES。
#include<bits/stdc++.h> using namespace std; int main(){ int T; cin>>T; while(T--){ string a, b, c; cin>>a>>b>>c; //外，中，内 int z[200] = {0}, ok = 1; for(int i = 0; i < 4; i++){ //四组 z[c[(i+4)%4]-'A']++;//内 z[b[(i+4)%4]-'A']++;//中 z[b[(i+4)%8]-'A']++; z[a[(i+4)%4]-'A']++;//外 z[a[(i+4)%12]-'A']++; z[a[(i+8)%12]-'A']++; if(z['R'-'A']==2 && z['G'-'A']==3 && z['Y'-'A']==1){ memset(z,0,sizeof(z)); }else{ // cout<<z['R'-'A']<<" "<<z['G'-'A']<<"\n"; ok = 0; break; } } if(ok==1)cout<<"YES\n"; else cout<<"NO\n"; } return 0; }
第9题——第八大奇迹 （25分）
- 题意：
【样例输入】
10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10
【样例输出】
0
30
10
20
- 思路：
1-1e5的数组，初始为0，单点修改，查询区间第8大的值。
emmm，众所周知的动态区间第k小问题。
静态主席树：可持久化权值线段树。×
动态主席树：树套树。√
- 主席树或者线段树维护10个节点（区间最大的8个值，每次更新从左右子树排序过的最大的8个值pushup）吧，虽然板子不好敲，但还是挺板的
所以我选线段树（）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int val[maxn<<2][8], sum[maxn<<2];//区间长度
//线段树
#define lch (p<<1)
#define rch (p<<1|1)
void pushup(int p){
//按从大到小合并左右区间到当前区间（类似于归并）
int a = 0, b = 0, cc = 0;
while(a < sum[lch] && b < sum[rch] && cc < 8){
if(val[lch][a] > val[rch][b]){
val[p][cc++] = val[lch][a++];
}else{
val[p][cc++] = val[rch][b++];
}
}
while(a<sum[lch] && cc < 8)val[p][cc++] = val[lch][a++];
while(b<sum[rch] && cc < 8)val[p][cc++] = val[rch][b++];
sum[p] = min(8, sum[lch]+sum[rch]);
}
void add(int p, int l, int r, int x, int v){
if(l==r){
val[p][0] = v;
sum[p] = 1;
return ;
}
int mid = l+r>>1;
if(x <= mid){
add(lch, l, mid, x, v);
}else{
add(rch, mid+1, r, x, v);
}
pushup(p);
}
int tmp[100];
void merge(int kk[], int k1[], int k2[]){
int a = 0, b = 0, cc = 0;
while(a < 8 && b < 8){
if(k1[a]>=k2[b])tmp[cc++]=k1[a++];
else tmp[cc++]=k2[b++];
}
while(a<8)tmp[cc++]=k1[a++];
while(b<8)tmp[cc++]=k2[b++];
for(int i = 0; i < 8; i++)kk[i]=tmp[i];
}
int* query(int p, int l, int r, int ql, int qr){
if(ql<=l && r<=qr)return val[p];
int mid = l+r>>1;
if(qr <= mid)return query(lch, l, mid, ql, qr);
else if(ql>mid)return query(rch, mid+1, r, ql, qr);
int* k1 = query(lch, l, mid, ql, qr);
int* k2 = query(rch, mid+1, r, ql, qr);
int* kk = new int[9];
merge(kk, k1, k2);
return kk;
}
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= m; i++){
string op; cin>>op;
if(op=="C"){
int p, x; cin>>p>>x;
add(1,1,n,p,x);
}else{
int a, b; cin>>a>>b;
cout<<query(1,1,n,a,b)[7]<<"\n";
}
}
return 0;
}
```
第10题——燃烧权杖 （25分）
- 题意：
2个英雄，k个士兵，k+2个人都有血槽。
随机选择一个人扣10点血，直到出现死英雄为止。
求死的英雄是敌方的概率。
输出答案%p
- 思路：
因为只跟英雄有关系，所以可以忽视小兵的存在。
变成了每次自己或地方英雄随机扣血10滴谁先挂，满足二项分布。
- 留着占坑待填吧，暂时不会了。
50分做法可以参考一下别的大佬的题解，但是下午和明天都有期末考试的我已经不想看了
