1. 2023/3/20：
1.python3的dfs
1 n, p = map(int, input().split())
2
3
4 def change_to_num(lst): # 将一个列表转化成一个数字
5 x = 0
6 for i in range(len(lst)):
7 x += lst[i] * 10 ** (len(lst) - 1 - i)
8 return x
9
10
11 l = []
12
13
14 def change_to_lst(num):
15 tmp = []
16 while num > 0:
17 tmp.append(num % 10)
18 num //= 10
19 return tmp
20
21
22 l = change_to_lst(n)
23
24 l = l[::-1]
25
26 m = 0
27
28
29 def flush_max(lst):
30 global m
31 if change_to_num(lst) % p == 0:
32 if change_to_num(lst) > m:
33 m = change_to_num(lst)
34
35
36 def dfs(lst, cnt): # 传入列表和位数
37 global m
38 if cnt >= len(lst):
39 return m
40 if 0 < lst[cnt] < 9:
41 lst[cnt] += 1 # 加一操作
42 flush_max(lst)
43 dfs(lst, cnt + 1)
44 lst[cnt] -= 1 # 不变操作
45 flush_max(lst)
46 dfs(lst, cnt + 1)
47 lst[cnt] -= 1 # 减一操作
48 flush_max(lst)
49 dfs(lst, cnt + 1)
50 elif lst[cnt] == 0:
51 flush_max(lst)
52 dfs(lst, cnt + 1)
53 lst[cnt] += 1
54 flush_max(lst)
55 dfs(lst, cnt + 1)
56 else:
57 flush_max(lst)
58 dfs(lst, cnt + 1)
59 lst[cnt] -= 1
60 flush_max(lst)
61 dfs(lst, cnt + 1)
62 return m # 每一个递归搜索树都有一个返回值
63
64
65 if (dfs(l, 0)) == 0:
66 print(-1)
67 else:
68 print(dfs(l, 0))
2.跳跳
题目链接：跳跳 - Problem - Daimayuan Online Judge
如果需要掌握最少的魔法阵方法数目，每次移动的距离就得最少，这样就可以遍历地图上最多的点，所以每次移动的距离就是x1-x2 和 y1-y2 分别除以他俩的最大公因数，这样能保证每一步走的路程是最小的。set可以保证去重。
但是要注意的是，两个负数的公因数也是负数，所以负数除以负数依旧是正数，所以最后还需要用set去重后的size()*2才是最后走的掌握最少的魔法阵数量
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=510;
4 typedef pair<int,int> PII;
5 set <PII> s;
6 struct point{
7 int x;
8 int y;
9 }p[N];
10 int gcd(int a,int b)
11 {
12 if(b==0)return a;
13 return gcd(b,a%b);
14 }
15 inline void solve()
16 {
17 int n;
18 cin>>n;
19 for(int i=1;i<=n;i++)
20 cin>>p[i].x>>p[i].y;
21 for(int i=1;i<=n;i++)
22 for(int j=1;j<=n;j++)
23 {
24 if(i==j)continue;
25 int dx=p[i].x-p[j].x;
26 int dy=p[i].y-p[j].y;
27 if(dx==0 && dy!=0)s.insert({0,1});
28 else if(dx!=0 && dy==0)s.insert({1,0});
29 else{
30 int x=gcd(dx,dy);
31 s.insert({dx/x,dy/x});
32 }
33 }
34 cout<<s.size()*2<<endl;
35 }
36 signed main()
37 {
38 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
39 solve();
40 return 0;
41 }
3.异或和或
题目链接：异或和或 - Problem - Daimayuan Online Judge
此题打表找找规律即可，会发现str1和str2在长度相同的情况下，全为‘0’,或者都不全为‘0’就输出YES，时间复杂度O(n^2)
这个题更像是一个脑筋急转弯，长度不相等，一定是NO
1 #include <bits/stdc++.h>
2 using namespace std;
3 int t;
4 inline void solve()
5 {
6 cin>>t;
7 while(t--)
8 {
9 string s,t;
10 cin>>s>>t;
11 if(s.length()!=t.length())
12 {
13 cout<<"NO"<<endl;
14 continue;
15 }
16 bool f_s=false;
17 for(int i=0;i<s.length();i++)
18 if(s[i]=='1')
19 {
20 f_s=true;
21 break;
22 }
23 bool f_t=false;
24 for(int j=0;j<s.length();j++)
25 if(t[j]=='1')
26 {
27 f_t=true;
28 break;
29 }
30 if(f_t == f_s)cout<<"YES"<<endl;
31 else cout<<"NO"<<endl;
32 }
33 }
34 signed main()
35 {
36 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
37 solve();
38 return 0;
39 }
2. 2023/3/21：
1.01序列
题目链接：01序列 - Problem - Daimayuan Online Judge
我们当然可以暴力的遍历字串，但是需要O(n^2)的时间复杂度，肯定会超时，所以此处运用了类似于前缀和的思想，因为数列只有01，所以其实是求区间和是k的序列的总数量。
f[i]表示1~i数位的区间和，类似于前缀和 cnt[i]表示区间和为i的总数量
注意要初始化cnt[0]=1，要不区间和恰好等于前缀和的情况算不进去。
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 const int N=1e6+10;
5 LL cnt[N],f[N];//cnt[i]表示区间和为i的数量有多少 ，f[i]表示第一位到第i位总长度的区间和
6 LL res;
7 inline void solve()
8 {
9 int k;
10 string str;
11 cin>>k>>str;
12 str="$"+str;
13 for(int i=1;i<str.size();i++)
14 f[i]=f[i-1]+(str[i]-'0');
15 cnt[0]=1;
16 for(int i=1;i<str.size();i++)
17 {
18 if(f[i]>=k) res+=cnt[f[i]-k];
19 cnt[f[i]]++;
20 }
21 cout<< res <<endl;
22 }
23 signed main()
24 {
25 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
26 solve();
27 return 0;
28 }
2.出栈序列判断
题目链接：出栈序列判断 - Problem - Daimayuan Online Judge
简单的模拟，用栈
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10;
4 int n;
5 int a[N];
6 stack <int> st;
7 inline void solve()
8 {
9 scanf("%d",&n);
10 for(int i=1;i<=n;i++)
11 scanf("%d",&a[i]);
12 int cnt=1;
13 for(int i=1;i<=n;i++)
14 {
15 st.push(i);
16 printf("push %d\n",i);
17 while(!st.empty() && st.top()==a[cnt])//一定要先判断栈是否为空，否则如果空栈并且a[cnt]=null，会发生错误
18 {
19 st.pop();
20 cnt++;
21 printf("pop\n");
22 }
23 }
24 while(!st.empty())
25 {
26 st.pop();
27 printf("pop\n");
28 }
29
30 }
31 signed main()
32 {
33 solve();
34 return 0;
35 }
3.序列维护
emm，本来想用数组模拟，但是数组模拟的例如添加操作不是添加的插入第k个数后面的数，而是插入的是下标是k的数后面的数，其实有一定的歧义
所以果断用vector，其中insert和erase可以实现插入和删除，然后询问直接输出下标即可，注意不要越界
1 #include <bits/stdc++.h>
2 #define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
3 //STL vector支持在中间插入的操作
4 using namespace std;
5 int m;
6 vector<int> v;
7 inline void solve()
8 {
9 cin>>m;
10 int x,y;
11 while(m--)
12 {
13 string s;
14 cin>>s;//呃，刚开始把s输入放外面去了，我是dinner
15 if(s=="insert")
16 {
17 cin>>x>>y;
18 v.insert(v.begin()+x,y);
19 }
20 else if(s=="delete")
21 {
22 cin>>x;
23 v.erase(v.begin()+x-1);
24 }
25 else//询问操作
26 {
27 cin>>x;
28 cout<<v[x-1]<<endl;
29 }
30 }
31 }
32 signed main()
33 {
34 io;
35 solve();
36 return 0;
37 }
4.网格判断
题目链接：网格判断 - Problem - Daimayuan Online Judge
emm，签到题
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=30;
4 char p[N][N];
5 int n;
6 signed main()
7 {
8 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
9 //solve();
10 cin>>n;
11 for(int i=0;i<n;i++)
12 for(int j=0;j<n;j++)
13 cin>>p[i][j];
14 for(int i=0;i<n;i++)//判断每一行是否黑白块数量相同
15 {
16 int a=0,b=0;
17 for(int j=0;j<n;j++)
18 {
19 if(p[i][j]=='W')a++;
20 else b++;
21 }
22 if(a!=b)
23 {
24 cout<< 0 <<endl;
25 return 0;
26 }
27 }
28 for(int i=0;i<n;i++)//判断每一列黑白块数量是否相同
29 {
30 int a=0,b=0;
31 for(int j=0;j<n;j++)
32 {
33 if(p[j][i]=='W')a++;
34 else b++;
35 }
36 if(a!=b)
37 {
38 cout<< 0 <<endl;
39 return 0;
40 }
41 }
42 for(int i=0;i<n;i++)//判断是否每行有三个连续相同颜色的
43 {
44 for(int j=1;j<n-1;j++)
45 {
46 if(p[i][j]==p[i][j-1] && p[i][j]==p[i][j+1])
47 {
48 cout<< 0 <<endl;
49 return 0;
50 }
51 }
52 }
53 for(int i=0;i<n;i++)//判断是否每列有三个连续相同颜色的
54 {
55 for(int j=1;j<n-1;j++)
56 {
57 if(p[j][i]==p[j-1][i] && p[j][i]==p[j+1][i])
58 {
59 cout<< 0 <<endl;
60 return 0;
61 }
62 }
63 }
64
65 cout<< 1 <<endl;
66 return 0;
67 }
3. 2023/3/22：
1.删删
题目链接：删删 - Problem - Daimayuan Online Judge
由于鄙人没看到必须删除相同相同相同的字符！！！！！捏麻麻的
暴力做法，枚举26个字符，在其中利用双指针，分别左右扫过来，如果左右指针所指字符都不一样，并且无法这俩字符都不是我要枚举删的字符（删不掉），那么一定不回文！！可以接着枚举下一个了
参考：
枚举26个字符，假设这个字符就是这个字符串要删除的字符，然后双指针跑字符串，当两边不一样时就判断两边有没有那边是我们当前枚举的字符，如果有就跳过他，操作数++然后继续双指针跑字符串，如果两边都没有我们当前枚举的字符，说明这个字符不能把字符串变成回文，我们去枚举下一个字符，如果有字符可以把字符串变成回文，那就把操作数记录下来，并维护最小值。最后如果所有字符都不能把字符串变成回文那就输出-1，反之输出最小的操作数。
1 #include <bits/stdc++.h>
2 using namespace std;
3 int T;
4 inline void solve()
5 {
6 int n;
7 string s;
8 cin>>n>>s;
9 int res=n+1; //一直维护更新即可
10 for(int i=0;i<26;i++)
11 {
12 int l=0,r=n-1,cnt=0;//cnt记录要删除字符的数量
13 char c='a'+i;
14 for(int i=0;i<n;i++)
15 {
16 while(l<=r)
17 {
18 if(s[l]==s[r])l++,r--;
19 else if(s[l]==c)l++,cnt++;
20 else if(s[r]==c)r--,cnt++;
21 else
22 {
23 cnt=n+1;
24 break;
25 }
26 }
27 res=min(res,cnt);
28 }
29 }
30 if(res==n+1)cout<< -1 <<endl;
31 else cout<< res <<endl;
32 }
33 signed main()
34 {
35 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
36 cin>>T;
37 while(T--) solve();
38 return 0;
39 }
2.快快变大
题目链接：快快变大 - Problem - Daimayuan Online Judge
区间dp，就是合并石子这道题，dp一般是先枚举区间，然后枚举起点，终点等于起点＋长度-1，第三维枚举分边界线k，把整个区间分为[i,k]和[k+1,j]，所以k最大的范围就是j-1，因为至少要保证两个区间才可以合并。
这道题可以提前预处理下区间i~j的阶乘
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 //区间dp
5 const int N=1010;
6 const int MOD=1000003;
7 LL f[N][N],dp[N][N],a[N];//f[i][j]表示i到j的阶乘,dp[i][j]表示i到j的最大分数
8 inline void solve()
9 {
10 int n;
11 cin>>n;
12 for(int i=1;i<=n;i++) cin>>a[i];
13 for(int i=1;i<=n;i++)//dp预处理阶乘
14 {
15 f[i][i-1]=1;
16 for(int j=i;j<=n;j++)
17 {
18 f[i][j]=(f[i][j-1]*a[j])%MOD;
19 }
20 }
21 for(int len=2;len<=n;len++)//长度是1就不用合并了
22 {
23 for(int i=1;i+len-1<=n;i++)
24 {
25 int j=i+len-1;
26 for(int k=i;k<j;k++)//把区间分成i~k和k+1~j 因为最少要分成两个区间，所以上界是j-1
27 {
28 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + (f[i][k]-f[k+1][j])* (f[i][k] - f[k + 1][j]));
29 }
30 }
31 }
32 cout<<dp[1][n]<<endl;
33 }
34 signed main()
35 {
36 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
37 solve();
38 return 0;
39 }