# 2023-2024-1寒假训练题解
## A K好数(动态规划)
### 思路
优先考虑暴力，发现数据范围 对于100%的数据，1 <= K,L <= 100。最大的数是 $100^{100}$ 超过long long 直接排除暴力。再看到题目中有取模并且题目要求满足啥啥啥的个数，可以考虑用动态规划。
动态规划基本思路：
1.dp数组如何定义 2.如何转移 3.如何初始化 4.如何求答案
dp数组要能表示所有状态
dp数组定义: $dp_{ij}$ 代表从左到右遍历到第 $i$ 位当前数字是 $j$ 时所满足条件的个数。
根据题目要求转移，"相邻的两位都不是相邻的数字"，也就是这两个数的差的绝对值不能为1
假设当前数是 $j$ 前一位数是 $p$ 那么转移条件就是 $|j-p|\neq1$
转移：$dp_{ij}=dp_{ij}+dp_{i-1p}(abs(j-p)\neq1)$ $(2\leq i \leq L)(0\leq j,p<k)$
初始化：$dp_{1i}=1(1\leq i<k)$ 不从0开始是因为要考虑是否有前导0。
求答案 $ans=dp_{Li}(0\leq i<k)$ 加上最后一位所有情况。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=0,mod=1e9+7;
//2023 by YZT
void solve()
{
int k,n;
cin>>k>>n;
vector< vector<ll> >dp(n+1,vector<ll>(k+1));
for(int i=1;i<k;i++)
dp[1][i]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<k;j++)
{
for(int p=0;p<k;p++)
{
if(abs(j-p)==1)continue;
dp[i][j]=(dp[i][j]+dp[i-1][p])%mod;
}
}
}
ll ans=0;
for(int i=0;i<k;i++)
ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## B 安慰奶牛(最小生成树)
### 题意
从某点出发，遍历所有结点，然后回到起点，花费的最短时间是多少。其中时间花费除了在边上，在结点上也需要花费时间。
### 思路
看到题目，遍历所有点所要的代价最小，很容易想到用最小生成树去解决，但这道题不只有边权，还有每个节点上的代价，又因为要回到起点，所以每条边要走两遍。最小生成树是根据一个权值来排序的，那这么多条件如何转换成一个权值呢？我们知道每条边一定是要走两次的，而每走过一条边，那么必定会经过这条边连接的两个结点。于是，我们能否把每条边的权值更新为本身的二倍再加上他所连接的两个结点的权值呢？答案是肯定的。这样，我们就可以直接在最小生成树的结果加一个最小结点的权值即可。
### 代码
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;//(1ll<<63)-1
//2023 by YZT
struct node{
int x,y,w;
}e[N];
int fa[N];
int find(int x)
{
if(x==fa[x])
return x;
else return fa[x]=find(fa[x]);
}
bool cmp(node A,node B)
{
return A.w<B.w;
}
void solve()
{
int n,p;
cin>>n>>p;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
fa[i]=i;
}
for(int i=0;i<p;i++)
{
int x,y,w;
cin>>x>>y>>w;
w=w*2+a[x]+a[y];
e[i].x=x;e[i].y=y;e[i].w=w;
}
int ans=0;
sort(e,e+p,cmp);
for(int i=0;i<p;i++)
{
int xx=find(e[i].x);
int yy=find(e[i].y);
if(xx!=yy)
{
fa[xx]=yy;
ans+=e[i].w;
}
}
int mn=1e9;
for(int i=1;i<=n;i++)
mn=min(mn,a[i]);
cout<<ans+mn<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## C 十六进制转八进制
### 思路
观察到每一位16进制的数可以转化为4位2进制的数，一位8进制的数可以转化为3位2进制的数，由此，可以得到，先将16进制的数先转化为2进制的数，再将2进制数转化为8进制数。
### 代码
```cpp
#include<iostream>
#include<math.h>
#include<map>
using namespace std;
//思路：100000位的十六进制数，这么大的数不好直接处理，以二进制字符串转换为八进制即可
int main(){
int n;
cin>>n;
while(n--){
string s;
cin>>s;
int len1 = s.length();
string res1="";
//将16进制转换为二进制字符串
for (int i=0;i<len1;i++){
switch(s[i]){
case '0': res1 += "0000"; break;
case '1': res1 += "0001"; break;
case '2': res1 += "0010"; break;
case '3': res1 += "0011"; break;
case '4': res1 += "0100"; break;
case '5': res1 += "0101"; break;
case '6': res1 += "0110"; break;
case '7': res1 += "0111"; break;
case '8': res1 += "1000"; break;
case '9': res1 += "1001"; break;
case 'A': res1 += "1010"; break;
case 'B': res1 += "1011"; break;
case 'C': res1 += "1100"; break;
case 'D': res1 += "1101"; break;
case 'E': res1 += "1110"; break;
case 'F': res1 += "1111"; break;
}
}
//二进制字符串每四个数就是一个16进制数，每3个数就是一个8进制数，这里可能存在缺0的情况，需要补充
int len2=res1.length() ;
switch(len2%3){
case 1: res1 = "00"+res1; break;
case 2: res1 = "0"+res1; break;
}
//此时的res1就是一个合法的二进制表示8进制的字符串了,下面开始生成八进制字符串了
string res2="";
len2=res1.length();
for (int i=0;i<len2;i+=3){
string t = res1.substr(i,3);
// 避免因为000带来导致转为为八进制时候有前导0
if (i==0&&t=="000") res2+="";
else res2 += (4*((t[0])-'0')+ 2*((t[1])-'0' )+ ((t[2])-'0'))+'0';
}
cout<<res2<<endl;
}
return 0;
}
```
## D 金属采集(树形dp)
### 思路
一道很典型的树形dp。
动态规划基本思路：
1.dp数组如何定义 2.如何转移 3.如何初始化 4.如何求答案
dp数组定义要包含所有状态, $dp_{ij}$ 代表以 $i$ 为根的子树分配 $j$ 个机器人采集这个子树所有节点所要的最少能量。很容易就能想到答案就是 $dp_{sk}$。然后是如何转移：
$$
dp_{uj}=\begin{cases}
dp_{uj}+dp_{v0}+w*2 & m=0\\
min(dp_{uj},dp_{u,j-m}+dp_{vm}+w*m) & 1\leq m \leq j\\
\end{cases}
$$
dp的转移要考虑所有的情况,当 $m=0$ （m为儿子子树中分配的机器人数）时意味着儿子子树中没有停留机器人，最少就是过去一个机器人再回来，花费是 $2*w$;其他情况过去几个机器人就是走了几遍这条边花费就是 $w*m$。
初始化:dfs到叶子节点时，机器人就可以停下了所以 $dp_{ij}=0$。
### 代码
~~~cpp
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;//(1ll<<63)-1
//2023 by YZT
vector<pair<int,int> >e[N];
int dp[N][15];
int n,s,k;
void dfs(int u,int fa)
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i].first,w=e[u][i].second;
if(v==fa)continue;
dfs(v,u);
for(int j=k;j>=0;j--)//顺序遍历会影响后面的状态
{
dp[u][j]+=dp[v][0]+w*2;//m=0
for(int m=1;m<=j;m++)
dp[u][j]=min(dp[u][j],dp[u][j-m]+dp[v][m]+w*m);
}
}
}
void solve()
{
cin>>n>>s>>k;
for(int i=0;i<n-1;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(s,0);
cout<<dp[s][k]<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
~~~
## E 集合运算(模拟,stl)
### 思路
利用map模拟。
### 代码
~~~cpp
#include<bits/stdc++.h>
using namespace std;
int n, m, a;
map<int, int> mp;
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a; mp[a] = 1; // 等于1代表只有集合a有这个数
}
cin >> m;
for(int i = 0; i < m; i++) {
cin >> a;
if(mp[a]) mp[a] = 3; // 等于3代表集合a和集合b都有这个数
else mp[a] = 2; // 等于2代表只有集合b有这个数
}
for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
if(it->second == 3) cout << it->first << " ";
}
cout << endl;
for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
cout << it->first << " ";
}
cout << endl;
for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
if(it->second == 1) cout << it->first << " ";
}
}
~~~
## F瓷砖铺放(递归)
### 思路
首先看数据范围 $n\leq 10$ 很容易想到暴力搜索。题意就是给你一个数 $n$ 让你求有多少种方法通过只使用 $1$ 和 $2$ 来凑出 $n$。可以抽象为一棵树树顶是 $n$ 。从 $n$ 开始往下走，每次都有两个分支一个是减去1一个是减去2，走到底之后只有刚好减完了才算一种方法
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=0,mod=1e9+7;
//2023 by YZT
int ans;
void dfs(int x)
{
if(x<0)return;
if(x==0)ans++;
dfs(x-1);
dfs(x-2);
}
void solve()
{
int n;
cin>>n;
dfs(n);
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## G 矩形面积交
### 思路
判断位置，分类讨论位置得到相交矩形的长和宽即可
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
const int N=1e5+5,mod=1e9+7,INF=0x3f3f3f3f,P=998244353;
const double pi=acos(-1.0),E=exp(1),esp=1e-10;
void solve()
{
double ax,ay,bx,by,cx,cy,dx,dy;
cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy;
double l,h;
if(ax>bx)
swap(ax,bx);
if(ay>by)
swap(ay,by);
if(cx>dx)
swap(cx,dx);
if(cy>dy)
swap(cy,dy);
//cout<<ax<<' '<<ay<<' '<<bx<<' '<<by<<'\n';
//cout<<cx<<' '<<cy<<' '<<dx<<' '<<dy<<'\n';
if(ax<=cx&&bx>=dx)
l=dx-cx;
else if(ax>=cx&&bx<=dx)
l=bx-ax;
else if(ax<=cx&&bx>=cx)
l=bx-cx;
else if(ax<=dx&&bx>=dx)
l=dx-ax;
else
l=0;
if(ay<=cy&&by>=dy)
h=dy-cy;
else if(ay>=cy&&by<=dy)
h=by-ay;
else if(ay<=cy&&by>=cy)
h=by-cy;
else if(ay<=dy&&by>=dy)
h=dy-ay;
else
h=0;
cout<<fixed<<setprecision(2)<<l*h<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
```
## H 完美的代价(回文串，贪心，双指针)
### 思路
看题先看数据范围，一看 $N\leq 8000$ 说明时间复杂度可以在 $O(n^2)$ 之内通过。
然后再看题目，题意：每次能执行相邻的字符交换，求让其字符串成为一个回文串要用到的最少的交回文串需要注意的是长度是奇数还是偶数，如果长度是奇数说明只能存在一种个数为奇数字符，如果是偶数就不能存在个数为奇数的字符。如果这些条件都不能满足，那就可以愉快的输出 $Impossible$ 了。如果能构成回文串那么如何用最少的交换次数构成回文串呢，可以贪心的根据一半来配对另一半，配对的时候就把离一端最近的给他换过去，例如 $mamad$ 左边第一个是 $m$ 然后需要把最后一位也变成 $m$ 就要找到离最后一位最近的一个 $m$ 给他换过去，然后再往中间走慢慢配对。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=0,mod=1e9+7;
//2023 by YZT
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
vector<int>cnt(501,0);
for(int i=0;i<n;i++)
{
cnt[s[i]]++;
}
int k=0;
for(int i=0;i<500;i++)
{
k+=(cnt[i]&1);
}
if(k>=2)
{
cout<<"Impossible"<<endl;
return;
}
int ans=0;
int now=n;
for(int l=0;l<(n+1)/2;l++)
{
int r;
for(r=now-1;r>l;r--)
{
if(s[l]==s[r])
{
while(r<now-1)
{
swap(s[r],s[r+1]);
r++;
ans++;
}
now--;
break;
}
}
if(l==r)
ans+=abs((n-1)/2-l);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## I Sine之舞
### 思路
真没什么好说的，找规律模拟即可
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const int N=1e5+5,mod=1e9+7,INF=0x3f3f3f3f,P=998244353;
const double pi=acos(-1.0),E=exp(1),esp=1e-10;
void solve()
{
int n;
cin>>n;
vector<string>a(n+1);
for(int i=1;i<=n;i++)
{
a[i]="sin(1";
for(int j=2;j<=i;j++)
{
if(j%2==0)
a[i]+="-";
else
a[i]+="+";
a[i]+="sin(";
a[i]+=j+'0';
}
for(int j=1;j<=i;j++)
a[i]+=")";
}
string res="";
for(int i=1;i<n;i++)
res+="(";
for(int i=1;i<n;i++)
{
res+=a[i]+"+";
res+='0'+n-i+1;
res+=")";
}
res+=a[n]+"+1";
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
```
## J 回型取数(模拟)
### 思路：
从(1,1)点开始，设定上下左右四边的边界，依次以向下，向右，向上，向左进行取值，并每次完成一次取值就需进行改动以维护边界
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define nl "\n"
using namespace std;
int arr[300][300];
void solved(){
int i,j;
}
int main() {
//cout << fixed;
//cout.precision(18);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
int n,m;
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) cin>>arr[i][j];
}
int x=1,y=1,cnt=1,f=0;
int a=1,b=n,c=2,d=m;
vector<int>ans;
while(1){
if(cnt&1){
if(!f){
if(x<=b){
while(x<=b){
ans.push_back(arr[x][y]);
x++;
}
x--;
y++;
b--;
}
else break;
}
else{
if(x>=a){
while(x>=a){
ans.push_back(arr[x][y]);
x--;
}
x++;
y--;
a++;
}
else break;
}
f^=1;
}
else{
if(f){
if(y<=d){
while(y<=d){
ans.push_back(arr[x][y]);
y++;
}
x--;
y--;
d--;
}
else break;
}
else{
if(y>=c){
while(y>=c){
ans.push_back(arr[x][y]);
y--;
}
x++;
y++;
c++;
}
else break;
}
}
cnt++;
}
for(i=0;i<ans.size();i++) cout<<ans[i]<<" ";
}
//system("pause");
return 0;
}
```
## K 方格取数
### 思路
考虑dp，设$f[i][j][a][b]$表示以第一条路径走到$（i,j）$,第二条路径走到$(a,b)$得到的最大权值状态转移方程为$f[i][j][a][b]=max(max(f[i-1][j][a-1][b],f[i-1][j][a][b-1]),max(f[i][j-1][a-1][b],f[i][j-1][a][b-1]))+v[i][j]+v[a][b]$，但当$a=i$且$b=j$时$f[i][j][a][b]$要减去$(i,j)$处的权值。
### 代码
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const int N=1e5+5,mod=1e9+7,INF=0x3f3f3f3f,P=998244353;
const double pi=acos(-1.0),E=exp(1),esp=1e-10;
int f[11][11][11][11];
void solve()
{
int n;
cin>>n;
vector<vector<int> >v(n+1,vector<int>(n+1));
while(1)
{
int x,y,val;
cin>>x>>y>>val;
if(x==0)break;
v[x][y]=val;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int a=1;a<=n;a++)
for(int b=1;b<=n;b++)
{
f[i][j][a][b]=max(max(f[i-1][j][a-1][b],f[i-1][j][a][b-1]),max(f[i][j-1][a-1][b],f[i][j-1][a][b-1]))+v[i][j]+v[a][b];
if(i==a&&j==b)f[i][j][a][b]-=v[i][j];
}
cout<<f[n][n][n][n]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
```
## L 阶乘计算
### 思路
定义一设置存储数的每一位数字，将现数组中的每一位数字与相乘数中的每一位数字相乘，并维护进位的大小，最后将答案反向输出
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ll N = 2e5 + 10;
#define nl "\n"
using namespace std;
int nums[N];
void solved(){
int i,j;
}
int main() {
cout << fixed;
cout.precision(2);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
int n;
cin>>n;
nums[1]=1;
int up=0;
for(i=2;i<=n;i++){
for(j=1;j<=3000;j++){
int x=(nums[j])*i+up;
up=x/10;
nums[j]=x%10;
}
}
for(i=3000;i>=1;i--){
if(nums[i]) {
for (j = i; j >= 1; j--)
cout << nums[j];
break;
}
}
}
//system("pause");
return 0;
}
```
## M 2n皇后问题
### 思路
没写过八皇后的建议现在洛谷写一下八皇后（深度优先搜索的经典题）
本题与八皇后的区别不大，就是多了一种不同的皇后以及有一部分的位置不能放皇后，和八皇后一样递归放完一种皇后在递归放另外一种皇后即可。
### 代码
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const int N=1e5+5,mod=1e9+7,INF=0x3f3f3f3f,P=998244353;
const double pi=acos(-1.0),E=exp(1),esp=1e-10;
int mp[9][9],n,ans=0,vis[9][9],a[2][10],b[2][20],c[2][20];
void dfs(int x,int k)
{
if(x==n+1)
{
if(!k)
dfs(1,1);
else
ans++;
return ;
}
for(int i=1;i<=n;i++)
{
if(mp[x][i]==0||vis[x][i]||a[k][i]||b[k][x+i]||c[k][i-x+n])continue;
vis[x][i]=1;a[k][i]=1;b[k][x+i]=1;c[k][i-x+n]=1;
dfs(x+1,k);
vis[x][i]=0;a[k][i]=0;b[k][x+i]=0;c[k][i-x+n]=0;
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
dfs(1,0);
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
```
## N 校门外的树
### 思路
直接前缀即可，虽然暴力也能过
### 代码
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const int N=50+5,mod=1e9+7,INF=0x3f3f3f3f,P=998244353;
const double pi=acos(-1.0),E=exp(1),esp=1e-10;
void solve()
{
int n,m;
cin>>n>>m;
vector<int>a(n+2);
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
a[l]+=1;
a[r+1]-=1;
}
int ans=n+1;
for(int i=1;i<=n;i++)
{
a[i]+=a[i-1];
if(a[i])
ans--;
}
if(a[0])ans--;
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
```
## O 数列（递归）
### 思路
由题目进行推演可得到一下公式
$a_1=1$
$a_2=k$
$a_3=a_1+a_2$
$a_4=k^2$
$a_5=a_1+a_4$
$a_6=a_2+a_4$
$a_7=a_3+a_4$
$a_8=k^3$
$....$
因此可用递归得到答案
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define nl "\n"
using namespace std;
void solved(){
int i,j;
}
ll qpow(ll base, int power) {
ll result= 1;
while (power > 0) {
if (power & 1) {
result = result * base;
}
power >>= 1;
base = (base * base);
}
return result;
}
bool check(ll x){
int num=log2(x);
ll res=qpow(2,num);
return res==x;
}
ll get(int k,int n){
if(n==1) return 1;
if(n==2) return k;
if(check(n)){
int num=log2(n);
ll res=qpow(k,num);
return res;
}
int num=log2(n);
int other=n-qpow(2,num);
ll res=qpow(k,num)+get(k,other);
return res;
}
int main() {
//cout << fixed;
//cout.precision(18);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
int k,n;
cin>>k>>n;
if(n==1) cout<<1;
else if(n==2) cout<<k;
else{
ll ans=get(k,n);
cout<<ans;
}
}
//system("pause");
return 0;
}
```
## P Car的旅行路线(Floyd最短路)
### 思路
先说这个题目给的样例是错的,应该是
```
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
```
```
47.5
```
一看题目知道1.有图 2.要求一点到另一点的最小花费。可以想到用最短路算法，那么用哪个算法呢，看一下数据范围 $S\leq100$ 说明$O(n^3)$肯定可以过，显然就可以用 $Floyd$ 算法了。跑最短路之前需要建图，而建图就是这个题目的难点。
**(1)需要找到矩形的第四个点。**
我们可以让矩形的中点作为桥梁求出第四个点，已知 $A,B,C$ ,假设 $P$ 是矩形的中点,$BC$ 和 $AD$ 是对角线,根据中点公式可以得到
$$
\begin{cases}
x_P=\frac{x_A+x_D}{2}\\
x_P=\frac{x_B+x_C}{2}
\end{cases}
$$
$$
\begin{cases}
y_P=\frac{y_A+y_D}{2}\\
y_P=\frac{y_B+y_C}{2}
\end{cases}
$$
所以可以得到
$$
\begin{cases}
x_D=x_B+x_C-x_A\\
y_D=y_B+y_C-y_A
\end{cases}
$$
再用勾股定理判断一下哪两个点构成对角线，就可以求出第四个点了。
**(2)建图**
我们发现一个城市里面有四个点，我们可以把他们全都标号，例如第 $1$ 个城市的四个点标 $1,2,3,4$ 第 $2$ 个城市标 $5,6,7,8$ 以此类推。第 $i$ 个城市和标号的关系就是 $(i-1)*4+j$ 其中 $j$ 代表这个城市中的第几个点，例如第一个点就是 $(i-1)*4+1$。如果一个点的编号是 $i$ 那么城市编号就是 $\lfloor (i-1)/4 \rfloor$ 。
最后因为城市内各点之间只能通过高铁，各城市之间只能通过飞机，只需要在给数组赋初值的时候判断一下就好了，具体实现看代码。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=405,mod=1e9+7;
const ll inf=1ll<<60;
//2024 by YZT
double get(double x1,double y1,double x2,double y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
void solve()
{
int s,A,B;
double t;
cin>>s>>t>>A>>B;
vector<vector<double> >dp(N,vector<double>(N,inf));
vector<double>x(N),y(N),T(N);
for(int i=1;i<=s;i++)
{
for(int j=1;j<=3;j++)
cin>>x[(i-1)*4+j]>>y[(i-1)*4+j];
cin>>T[i];
int a=(i-1)*4+1,b=(i-1)*4+2,c=(i-1)*4+3;
double dab=get(x[a],y[a],x[b],y[b]);
double dac=get(x[a],y[a],x[c],y[c]);
double dbc=get(x[b],y[b],x[c],y[c]);
if(dab+dac==dbc)
{
x[i*4]=x[b]+x[c]-x[a];
y[i*4]=y[b]+y[c]-y[a];
}
if(dab+dbc==dac)
{
x[i*4]=x[a]+x[c]-x[b];
y[i*4]=y[a]+y[c]-y[b];
}
if(dbc+dac==dab)
{
x[i*4]=x[b]+x[a]-x[c];
y[i*4]=y[b]+y[a]-y[c];
}
}
for(int i=1;i<=s*4;i++)
{
for(int j=1;j<=s*4;j++)
{
if(i==j)
dp[i][j]=0;
else
{
double val=sqrt(get(x[i],y[i],x[j],y[j]));
if((i-1)/4==(j-1)/4)
{
dp[i][j]=T[(i-1)/4+1]*val;
}
else
{
dp[i][j]=t*val;
}
}
}
}
for(int k=1;k<=s*4;k++)
{
for(int i=1;i<=s*4;i++)
{
for(int j=1;j<=s*4;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
double ans=inf;
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
ans=min(ans,dp[(A-1)*4+i][(B-1)*4+j]);
}
}
cout<<fixed<<setprecision(1)<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## Q 一元三次方程求解（暴力）
### 思路
从-100.0到100.0进行循环，每次加0.01，如果方程的结果满足则输出，并将x加上0.99
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define nl "\n"
using namespace std;
void solved(){
int i,j;
}
int main() {
cout << fixed;
cout.precision(2);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
double a,b,c,d;
cin>>a>>b>>c>>d;
int cnt=0;
for(double x=-100.0;x<=100.0;x+=0.01){
if(fabs(a*x*x*x+b*x*x+c*x+d)<0.01){
cnt++;
cout<<x<<" ";
x+=0.99;
}
if(cnt==3) break;
}
}
//system("pause");
return 0;
}
```
## R Hanoi问题
### 思路
就是汉诺塔问题，题目中说到的可以一次拿起m个，就是将n个石块的问题转化为了(n + m - 1) / m个石块的问题;
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
//using ll = long long;
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
IOS
int n, m, i, j;
cin >> n >> m;
i = n / m;
j = n % m;
if (j != 0)
i++;
cout << pow(2, i) - 1;
}
```
## S 数组排序去重(模拟)
### 思路
stl中set有排序去重功能可以很好地实现题目要求。你也可以对数组用sort和unique函数实现同样的结果。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=0,mod=1e9+7;
//2023 by YZT
void solve()
{
set<int>s;
for(int i=0;i<10;i++)
{
int x;
cin>>x;
s.insert(x);
}
for(set<int>::iterator it=s.begin();it!=s.end();it++)
cout<<*it<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
```
## T 接水问题
### 思路
模拟，每次将下一个人放到当前用时最短的水龙头的位置。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
//using ll = long long;
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
IOS
int n, m;
cin >> n >> m;
int s[20000] = {0};
for (int i = 0; i < n; i++)
cin >> s[i];
int *t = (int *)malloc(sizeof(int) * m);
if (n < m)
{
sort(s, s + n, greater<int>());
cout << s[0];
}
else
{
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 0; i < m; i++)
{
q.push(s[i]);
}
for (int i = m; i < n; i++)
{
int x = q.top();
q.pop();
x += s[i];
q.push(x);
}
while(q.size() != 1)
{
//cout << q.top();
q.pop(); //TODO
}
cout << q.top();
}
}
```
## U Hankson的趣味题
### 思路
首先由最大公因数和最小公倍数的性质可知，令 p=a0/a1,q=b1/b0，它们与X的公因数为1，并且x也是b1(最小公倍数)的一个因子，
所以 令x从1到sqrt(b1)中是b1(最小公倍数)的一个因子,除此外还有b1/x ,也可能是其中一个因子
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2e5 + 100;
void solve()
{
ll a0, a1, b0, b1;
cin >> a0 >> a1 >> b0 >> b1;
int ans = 0;
for (ll x = 1; x * x <= b1; x++)
{
if (b1 % x == 0)
{
if (__gcd(x, a0) == a1 and x / __gcd(x, b0)*b0 == b1)ans++;
ll y = b1 / x;
if (y == x)continue;
if (__gcd(y, a0) == a1 and y / __gcd(y, b0)*b0 == b1)ans++;
}
}
cout << ans << endl;
}
int main()
{
IOS
int T = 1;
cin >> T;
while (T--)
solve();
}
```
## V 和最大子序列(贪心,dp)
### 思路
这是一道很经典的题目，主要来讲一下dp的写法。
动态规划基本思路：
1.dp数组如何定义 2.如何转移 3.如何初始化 4.如何求答案
* dp数组的定义: $dp_i$ 代表以第 $i$ 个数为结尾的最大连续子序列和。
* 如何转移：讨论所有情况，发现有两种，一种是把第 $i$ 个数接在第 $i-1$ 个数后面，当前值就是 $dp_{i-1}+a_i$，第二种情况是不接在后面，当前值就是 $a_i$。对于两种情况取最大值转移救出来了 $dp_i=max(dp_{i-1}+a_i,a_i)$ 。
* 求答案就是遍历所有情况取最大值，$ans=max(ans,dp_i)(1\leq i \leq n)$。因为有负数所以要把 $ans$ 的初始值设为负无穷。
### 代码
~~~cpp
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=0,mod=1e9+7;//(1ll<<63)-1
//2023 by YZT
void solve()
{
int n;
cin>>n;
vector<int>a(n+1),dp(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=-1e9;
for(int i=1;i<=n;i++)
{
dp[i]=max(dp[i-1]+a[i],a[i]);
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
~~~
## W 最大乘积
### 思路
一道简单的dp,就是枚举每一种可能出现的情况，只是需要考虑到必须时刚好m个数。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
//using ll = long long;
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2e5 + 100;
int n, m;
int s[20] = {0};
int ans = 0, t = 0;
void dfs(int pos, int cnt, int re)
{
if (pos > n)
{
if (cnt == m)
ans = max(ans, re);
return;
}
if (cnt > m)
return;
dfs(pos + 1, cnt + 1, re * s[pos]);
dfs(pos + 1, cnt, re);
}
void solve()
{
ans = -1e9 - 100;
for (int i = 0; i < 20; i++)
s[i] = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
dfs(1, 0, 1);
cout << ans << endl;
}
int main()
{
IOS
int T = 1;
cin >> T;
while (T--)
solve();
}
```
## Y 最长字符串（排序）
### 思路
录入每个字符串，构建自定义函数进行排序，得到答案
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define nl "\n"
using namespace std;
void solved(){
int i,j;
}
bool cmp(string a,string b){
return a.size()>b.size();
}
int main() {
//cout << fixed;
//cout.precision(18);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
vector<string>str;
string s;
while(cin>>s){
str.push_back(s);
}
sort(str.begin(),str.end(),cmp);
cout<<str[0];
}
//system("pause");
return 0;
}
```
## Z 筛选号码
### 思路
约瑟夫环（模拟即可）
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N=20,mod=1e9+7;
void solve()
{
int n;
cin>>n;
vector<int>a;
for(int i=1;i<=n;i++)
a.push_back(i);
int p=0,cnt=0;
while(a.size()>1)
{
cnt++;
if(cnt%3==0)
{
cnt=0;
a.erase(a.begin()+p);
p--;
}
p++;
p%=a.size();
}
cout<<a[0]<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
while(T--) {
solve();
}
return 0;
}
```
## AA 打水问题（排序）
### 思路
先将等待时间最久的k人作为第一个取水的，再将其余人进行升序排序，依次对k个取水口进行取水，每个人的等待时间都需加上前面人的时间
### 代码
```cpp=
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ll N = 2e5 + 10;
#define nl "\n"
using namespace std;
void solved(){
int i,j;
}
vector<int>sum[1010],now(1010,0);
int main() {
cout << fixed;
cout.precision(2);
//cout.flush();
int i, j, T;
T=1;
//cin>>T;
while(T--) {
//solved();
int n,k;
cin>>n>>k;
priority_queue<int>q;
for(i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);
}
if(q.size()<=k){
cout<<0;
return 0;
}
for(i=1;i<=k;i++){
q.pop();
sum[i].push_back(0);
if(q.empty()) break;
}
priority_queue<int,vector<int>,greater<int> >qt;
while(!q.empty()){
qt.push(q.top());
q.pop();
}
while(!qt.empty()){
for(i=1;i<=k;i++){
sum[i].push_back(sum[i].back()+qt.top()+now[i]);
now[i]+=qt.top();
qt.pop();
if(qt.empty()) break;
}
}
ll ans=0;
for(i=1;i<=k;i++) {
ans+=sum[i].back();
}
cout<<ans;
}
//system("pause");
return 0;
}
```
## AB 新生舞会(模拟)
### 思路
可以用 $map$ 模拟一下对应的关系。
### 代码
```cpp=
//2024 by YZT
map<string,char>mp;
void solve()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string s;
string x;
char y;
cin>>s>>x>>y;
mp[s]=mp[x]=y;
}
int q;
cin>>q;
while(q--)
{
string a,b;
cin>>a>>b;
cout<<(mp[a]==mp[b]?'N':'Y')<<endl;
}
}
```
## AC 促销购物
### 思路
动态规划 完全背包 变形
### 代码
```cpp
#include <stdio.h>
#include <string.h>
long int bj(long int a, long int b)
{
return a < b ? a : b;
}
int main()
{
long int s, i, j, j1, b, ans = 0, dans = 0, b1, b2, b3, b4, b5;
long int sn[101];//sn[i]第i种促销种类的物品数
long int c[101][7], k[101][7], p[101], xc[7] = {0}, xp[7] = {0}, xk[7] = {0};
long int dp[6][6][6][6][6];//dp[2][3][4][1][0]代表 当前第 1~5 个物品 分别 购2 3 4 1 0 件所需最少钱
long h[6] = {0}; //h[i] 表示 i 号商品促销数量
long sbh[1001] = {0}; //标号表 链接 促销序号和需买序号的桥梁
scanf("%ld", &s);
for (i = 1; i <= s; i++)
{
scanf("%ld", &sn[i]);
for (j = 1; j <= sn[i]; j++)
scanf("%ld%ld", &c[i][j], &k[i][j]);
scanf("%ld", &p[i]);
}
scanf("%ld", &b);
for (i = 1; i <= b; i++)
scanf("%ld%ld%ld", &xc[i], &xk[i], &xp[i]);
for (j = 1; j <= b; j++) //初始化需求物品的数量 sbh[i] 代表需求品序号 存 需求数量
sbh[xc[j]] = j;
for (b1 = 0; b1 <= xk[1]; b1++)
for (b2 = 0; b2 <= xk[2]; b2++)
for (b3 = 0; b3 <= xk[3]; b3++)
for (b4 = 0; b4 <= xk[4]; b4++)
for (b5 = 0; b5 <= xk[5]; b5++)
if (b1 * xp[1] + b2 * xp[2] + b3 * xp[3] + b4 * xp[4] + b5 * xp[5])dp[b1][b2][b3][b4][b5] = b1 * xp[1] + b2 * xp[2] + b3 * xp[3] + b4 * xp[4] + b5 * xp[5];
//初始化 原价购买
dp[0][0][0][0][0] = 0;
for (i = 1; i <= s; i++)
{
for (j = 1; j <= sn[i]; j++)
if (xk[sbh[c[i][j]]] < k[i][j])break; //当前促销品 促销量大于需量 或者 促销品不需要 则不能选择此促销种类
if (j < sn[i])continue;
for (j = 1; j <= sn[i]; j++)
h[sbh[c[i][j]]] = k[i][j];
for (b1 = h[1]; b1 <= xk[1]; b1++)
for (b2 = h[2]; b2 <= xk[2]; b2++)
for (b3 = h[3]; b3 <= xk[3]; b3++)
for (b4 = h[4]; b4 <= xk[4]; b4++)
for (b5 = h[5]; b5 <= xk[5]; b5++)
dp[b1][b2][b3][b4][b5] = bj(dp[b1][b2][b3][b4][b5], dp[b1 - h[1]][b2 - h[2]][b3 - h[3]][b4 - h[4]][b5 - h[5]] + p[i]);
for (j = 1; j <= sn[i]; j++)
h[sbh[c[i][j]]] = 0;
}
ans = dp[xk[1]][xk[2]][xk[3]][xk[4]][xk[5]];
printf("%ld\n", ans);
return 0;
}
```
## AD 凶手
### 思路
遍历每一个人是凶手的可能，当符合三个人说真话时，直接输出当前的可能的凶手。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
for(int i=1;i<=6;i++)//i表示凶手是谁，1、2、3、4、5、6分别表示凶手是A、B、C、D、E、F
{
int cnt=0;//表示说真话的人数
if(i!=1)//A说真话
cnt++;
if(i==1||i==3)//B说真话
cnt++;
//C说的一定是假话
if(i!=6)//D说真话
cnt++;
if(i!=1&&i!=3&&i!=6)//E说真话
cnt++;
if(i==6)//F说真话
cnt++;
if(cnt==3)//只有一半人说真话
{
if(i==1)
cout<<"A"<<endl;
if(i==2)
cout<<"B"<<endl;
if(i==3)
cout<<"C"<<endl;
if(i==4)
cout<<"D"<<endl;
if(i==5)
cout<<"E"<<endl;
if(i==6)
cout<<"F"<<endl;
}
}
return 0;
}
```
## AE 卡勒沃夫之弱水路三千(提高型)(拓扑排序)
### 思路
拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。拓扑排序通常用来“排序”具有依赖关系的任务。
根据题目给的依赖关系输出拓扑排序序列。
### 代码
```cpp
//2024 by YZT
map<string,vector<string> >e;
map<string,int>ind;
set<string>st;
vector<string>ans;
void solve()
{
int n;
cin>>n;
e.clear();
ind.clear();
st.clear();
ans.clear();
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
st.insert(a);
st.insert(b);
ind[b]++;
e[a].push_back(b);
}
string root;
for(set<string>::iterator it=st.begin();it!=st.end();it++)
if(ind[*it]==0)
root=*it;
queue<string>q;
q.push(root);
while(!q.empty())
{
string s=q.front();
q.pop();
cout<<s<<" ";
for(int i=0;i<e[s].size();i++)
{
string y=e[s][i];
if(--ind[y]==0)
q.push(y);
}
}
cout<<endl;
}
```
## AF 题目 2 密码锁(BFS爆搜)
### 思路
第一眼看见数据范围这么小可以考虑暴力搜索。
暴力枚举交换哪一位。
### 代码
```cpp
//2024 by YZT
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
queue<pair<string,int> >q;
q.push({s,0});
map<string,bool>mp;
while(!q.empty())
{
pair<string,int>now=q.front();
q.pop();
if(now.first.find("2012")!=-1)
{
cout<<now.second<<endl;
return;
}
if(mp.count(now.first))continue;
mp[now.first]=1;
for(int i=0;i<now.first.size()-1;i++)
{
swap(now.first[i],now.first[i+1]);
q.push({now.first,now.second+1});
swap(now.first[i],now.first[i+1]);
}
}
cout<<-1<<endl;
}
```
## AG 身份证排序(排序)
### 思路
根据题意自定义排序。
### 代码
```cpp
//2024 by YZT
bool cmp(string a,string b)
{
string A=a.substr(6,8);
string B=b.substr(6,8);
if(A==B)
return a>b;
return A>B;
}
void solve()
{
int n;
cin>>n;
vector<string>a(n);
for(int i=0;i<n;i++)
cin>>a[i];
sort(a.begin(),a.end(),cmp);
for(int i=0;i<n;i++)
cout<<a[i]<<endl;
}
```
## AH 士兵排队问题(拓扑排序)
### 思路
拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。拓扑排序通常用来“排序”具有依赖关系的任务。
根据题目给的依赖关系输出拓扑排序序列。
### 代码
```cpp
//2024 by YZT
void solve()
{
string s;
map<char,int>ind;
vector<char>e[300];
while(cin>>s)
{
char x=s[0],y=s[2];
if(!ind.count(x))
ind[x]=0;
e[x].push_back(y);
ind[y]++;
}
queue<char>q;
string ans="";
int cnt=0;
for(map<char,int>::iterator it=ind.begin();it!=ind.end();it++)
{
if(it->second==0)
q.push(it->first);
}
while(!q.empty())
{
char x=q.front();
q.pop();
ans+=x;
for(int i=0;i<e[x].size();i++)
{
char y=e[x][i];
if(--ind[y]==0)
q.push(y);
}
}
if(ans.size()!=ind.size())
cout<<"No Answer!"<<endl;
else
cout<<ans<<endl;
}
```
## AI 聪明的美食家(最长不下降子序列,dp)
### 思路
状态定义：$dp_i$ 表示以第 $i$ 个元素为结尾的最长不下降子序列长度。
初始化：$dp_i=1(1 \leq i \leq n)$因为只有一个元素。
转移：$dp_i=max(dp_i,dp_j+1)$ $(1 \leq j < i,a_j \leq a_i)$ 可以从前面不比它大的地方转移。
求答案 $ans=max(ans,dp_i)(1 \leq i \leq n)$
时间复杂度 $O(n^2)$ 可以通过此题。
### 代码
```cpp
//2024 by YZT
void solve()
{
int n;
cin>>n;
vector<int>a(n+1),dp(n+1);
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[i]>=a[j])
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
```
## AJ 陶陶摘苹果2
### 思路
模拟一下题目要求，如果苹果高度大于陶陶所能伸到的最大高度说明这个苹果就是不能摘到的。
### 代码
```cpp
//2024 by YZT
void solve()
{
int n,m;
cin>>n>>m;
int ans=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(x>m+30)
ans++;
}
cout<<ans<<endl;
}
```
## AK 质因数2(分解质因数)
### 思路
分解质因数模板。
### 代码
```cpp
//2024 by YZT
void solve()
{
int n;
cin>>n;
int cnt=0;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
while(n%i==0)
n/=i,cout<<i<<" ",cnt++;
}
}
if(n>1)cout<<n,cnt++;
cout<<endl;
cout<<cnt<<endl;
}
```
## AL 字符串跳步
### 思路
模拟一下题目要求。
### 代码
```cpp
//2024 by YZT
void solve()
{
char s[100005];
cin>>s;
int start,step;
cin>>start>>step;
for(int i=start;s[i];i+=step)
cout<<s[i];
}
```
## AM 林丹大战李宗伟
### 思路
模拟一下题目要求,当一方得分达到21分时，只要该方与对方分差超过1分，该方即胜出。
### 代码
```cpp
//2024 by YZT
void solve()
{
int x,a=0,b=0;
while(cin>>x)
{
if(x)
b++;
else
a++;
if(abs(a-b)>1 and (a==21 or b==21))
{
cout<<(a>b?0:1)<<endl;
return;
}
}
}
```
## AN 最长滑雪道
### 思路
通过数据量可以得知，可以直接dfs遍历所有的点
同时，为节省时间，我们可以将以及遍历过的点存在的最长的滑雪道通过数组存储下来进行下一次的遍历。
### 代码
```cpp
#include<iostream>
using namespace std;
int dp[15][15], field[15][15];
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int R, C;
bool check(int a,int b,int c,int d) {
if (c >= 0 && c < R && d>=0 && d < C)
if (field[a][b] > field[c][d])
return true;
return false;
}
int dfs(int x, int y) {
//if (dp[x][y] != -1) //之前访问过
// return dp[x][y];
dp[x][y] = 1;
for (int i = 0; i < 4; i++) {
if (check(x, y, x + dir[i][0], y + dir[i][1])) {
dp[x][y] = max(dp[x][y], dfs(x + dir[i][0], y + dir[i][1])+1);
}
}
return dp[x][y];
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++)for (int j = 0; j < C; j++) {
cin >> field[i][j];
//dp[i][j] = -1;
}
for (int i = 0; i < R; i++)for (int j = 0; j < C; j++) dfs(i,j);
int max_len;
for (int i = 0; i < R; i++)for (int j = 0; j < C; j++)max_len = max(max_len, dp[i][j]);
cout << max_len;
return 0;
}
```
## AO 扫地机器人 （模拟）
### 思路
模拟机器人扫地区域
首先设定一个机器人可活动的区间大小 Q ,
则 Q 的最小范围应是 N / K 或者 第一个机器人的下标
由于要模拟扫地区域 我们可以设定一个 左边界 L 使 L 左边的区域都已经被清扫过
遍历所有机器人 并根据当前区间的大小更新左边界
每个机器人先向左 寻找是否有未清扫的区域。
若 机器人向左 可以扫到的 最大区域 未到达边界处 说明当前区间不满足条件
如果满足条件 根据机器人清扫区间更新边界 L
当机器人出现在边界左边时 ( L : 边界 ， i : 当前机器人的下标 ， Q : 区间大小 )
L = i + Q -1
当机器人出现在边界右边时
L = i + Q - ( i - L)
ps:: 用二分也行，会更快。
### 代码
~~~cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int n , k;
int a[100005];
bool f(int l, int Q){ // l 左边界 Q 区间大小
for(int i = 0; i < k; i++){
if(a[i] - Q <= l){ // 若 当前机器人的下标 减去 区间大小 <= 左边界的时候 说明可以继续 否则退出
if(a[i] <= l) l = a[i] + Q -1; // 若机器人 在左边界内 边界就该等于机器人向右所能扫到的最远点
else l = a[i] + Q - (a[i] - l );
} else return false;
}
if(l < n) return false; // 遍历完机器人 若左边界小于 n 则说明没有全部清扫
return true;
}
int main(){
cin >> n >>k;
for(int i = 0; i < k; i++)
scanf("%d",&a[i]);
sort(a,a+k);
int Q; // 区间大小
Q = (n/k) >= a[0] ? n/k : a[0]; // 区间初始化 最小可能的区间
for(; Q <= n; Q++){
int l = 0; // 左边界 初始为 0
if(f(l,Q)) break;
}
cout << 2*(Q-1); // 步数 = (区间大小 - 1) * 2
return 0;
}
~~~
## AP 单词分析 （暴力计数）
### 思路
定义一个数组用于计算每个字符出现的次数，在定义一个 mx 用于判断最大出现的次数，最后for循环遍历判断输出即可。
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
// 万恶的long long;
void solve(){
string s; cin >> s;
vector<int> sum(26 , 0);
int mx = 0;
for(int i = 0 ; i < s.size() ; i++){
sum[s[i] - 'a']++;
mx = max(sum[s[i] - 'a'] , mx);
}
for(int i = 0 ; i < 26 ; i++){
if(sum[i] == mx){
cout << (char)(i + 'a') << '\n' << mx << '\n';
return ;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AQ 作物杂交 （搜索）
### 思路
我们改如何存储每种作物的所有杂交方案呢？
我开始想到是用二维数组存储，定义一个足够大的数组int hybrid[2005][2005]，存储所有杂交方案，如A + B->C，转换为hybrid[A][B] = C.
但是使用这种存储方案的的话，我想不到该如何去得到一种种子的最短杂交时间，因为目标种子是数组所存的值，我们需要的是通过目标种子的标号能够得到能够杂交出该种子的所有杂交方案！
所以这种方案肯定是不行的。
我又想出来一种通过二维向量（vector）来存储的办法。
定义一个二维向量vector< vector<parent> >hybrid(2005);存储每种作物的所有杂交方案
定义一个结构体存储杂交方案
struct parent //存储杂交方案
{
int x;
int y;
};
每次输入一个能杂交出 x 作物的杂交方案（parent类型存储）就存入hybrid[x] 中。
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
struct parent //存储杂交方案
{
int x;
int y;
};
int n, m, k, t, tmp;
long long plant_time[2005];//每种作物的种植时间
bool flag[2005];//标记是否出现了该作物
long long min_hybrid_time[2005];//杂交出每种作物的最短时间
vector< vector<parent> >hybrid(2005);//存储每种作物的所有杂交方案
long long solve(int now)
{
if (flag[now])//若是已有杂交出该种作物的最短时间
return min_hybrid_time[now];//直接返回即可
for (int i = 0; i < hybrid[now].size(); i++)//对能够杂交出当前作物的方案都尝试一下
{
parent tmp = hybrid[now][i];//能够杂交出当前作物的第i种方案
//当前作物的最短杂交时间是 杂交出该作物的所有方案 中的最短时间
//而每种方案的最短时间是种植其‘父母’作物所需要的时间 + 其父母作物杂交所需的的最短时间（=两者杂交所需时间中的最大值)
min_hybrid_time[now] = min(min_hybrid_time[now], max(plant_time[tmp.x], plant_time[tmp.y]) + max(solve(tmp.x), solve(tmp.y)));
}
flag[now] = true;//标记已经找到最短杂交时间
return min_hybrid_time[now];//返回最短杂交时间
}
int main()
{
cin >> n >> m >> k >> t;
memset(min_hybrid_time, 0x3f, sizeof(min_hybrid_time));//杂交出每种作物的最短时间初始化为最大值
memset(flag, false, sizeof(flag));//作物标记初始化
//注意作物的下标从1开始！！！
for (int i = 1; i <= n; i++)//输入种植时间
cin >> plant_time[i];
for (int i = 0; i < m; i++)//输入初始种子数据
{
cin >> tmp;
flag[tmp] = true;//标记已经有了最短杂交时间
min_hybrid_time[tmp] = 0;//最短杂交时间 = 0，因为不需要杂交
}
for (int i = 0; i < k; i++)//输入所有杂交方案
{
parent temp;
cin >> temp.x >> temp.y >> tmp;
hybrid[tmp].push_back(temp);//存储杂交方案
}
solve(t);//递归求解
cout << min_hybrid_time[t] << endl;//输出杂交出目标作物的最短时间
return 0;
}
~~~
## AR 数字三角形 （DP）
### 思路
从上向下推 状态转移方程:$$a[i][j] = max(a[i - 1][j], a[i - 1][j - 1]) +a[i][j];$$
仔细思考要使左右步数相同，即最终必走到最后一行中间。
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
// 万恶的long long;
void solve(){
int n; cin >> n;
vector<vector<int> > a(n + 1 , vector<int>(n + 1 , 0));
for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= i ; j++){
if(j == 1) a[i][j] += a[i - 1][j];
else if(j == i) a[i][j] += a[i - 1][j - 1];
else a[i][j] += max(a[i - 1][j] , a[i - 1][j - 1]);
}
}
if(n & 1) cout << a[n][(n + 1) / 2] << '\n';
else cout << max(a[n][n / 2] , a[n][n / 2 + 1]) << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AS 外卖店优先级 （暴力 + 优化）
### 思路
根据题意很容易的想到是大模拟，所以我们即根据有多少条订单信息去遍历每个外卖店是否处于优先缓存条种，并且将每条信息按时间顺序先排序，在定义一个score记录每个外卖店的优先即，定义一个pre数组记录每个外卖店的上一次接单是什么时候，最后遍历判断即可。
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
// 万恶的long long;
int n , m , t;
int cmp(pair<int , int> A , pair<int , int> B){
if(A.fi == B.fi) return A.se < B.se;
return A.fi < B.fi;
}
void solve(){
cin >> n >> m >> t;
vector<pair<int , int> > ar;
for(int i = 0 ; i < m ; i++){
int ts , id; cin >> ts >> id;
pair<int , int> p(ts , id);
ar.pb(p);
}
sort(ar.begin() , ar.end() , cmp);
// for(int i = 0 ; i < m ; i++) cout << ar[i].fi << ' ' << ar[i].se << '\n';
//
// cout << '\n';
int cnt = 0;
vector<int> score(n + 1 , 0) , pre(n + 1 , 0);
vector<int> vis(n + 1 , 0);
for(int i = 0 ; i < m ; i++){
if(ar[i].fi != pre[ar[i].se]) score[ar[i].se] = max(0 , score[ar[i].se] - (ar[i].fi - pre[ar[i].se] - 1));
if(score[ar[i].se] < 4) vis[ar[i].se] = false;
score[ar[i].se] += 2;
if(score[ar[i].se] > 5) vis[ar[i].se] = true;
pre[ar[i].se] = ar[i].fi;
}
for(int i = 1 ; i <= n ; i++){
if(pre[i] != t) score[i] -= (t - pre[i]);
if(score[i] < 4) vis[i] = false;
if(vis[i]) cnt++;
}
cout << cnt << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AT 等差数列 （数学）
### 思路
for循环找出最小差值 通过数组中 （最大数-最小数） / 差值 + 1 得到最少的项数
当然这里得注意玩意数组中的数都是一样的，则最小差值将会为0，程序将会报错
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
// 万恶的long long;
void solve(){
int n; cin >> n;
vector<int> a(n);
for(int i = 0 ; i < n ; i++) cin >> a[i];
sort(a.begin() , a.end());
if(a[n - 1] == a[0]){ cout << n << '\n'; re }
int d = inf;
for(int i = 1 ; i < n ; i++){
d = min(d , a[i] - a[i - 1]);
}
cout << (a[n - 1] - a[0]) / d + 1 << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AU 赢球票 （枚举）
### 思路
枚举所有情况 判断最多能赢多少张球票
主要是所有情况的终止条件你如何去找
我这里用的是当你的计数不能大于当前数组的最大值和总赢球票数不能大于等于总球票
当然如果你能想到更好的终止条件也是可以的
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
void solve(){
int n; cin >> n;
vector<int> a(n);
for(int i = 0 ; i < n ; i++) cin >> a[i];
int mx = 0;
int mxx = *max_element(a.begin() , a.end());
int summ = accumulate(a.begin() , a.end() , 0);
for(int i = 0 ; i < n ; i++){
int cur = i , ji = 1 , sum = 0;
vector<int> vis(n , 0);
while(sum < summ && ji <= mxx){
if(vis[cur % n]){cur++; continue; }
if(a[cur % n] == ji){
sum += ji , ji = 1;
vis[cur % n] = 1;
}
else {
ji++;
}cur++;
}
mx = max(mx , sum);
}
cout << mx << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AV 卡片换位（bfs）
### 思路
根据题意，要求最少步数，不难想到bfs，题中说明只要求A、B位置互换，且只有一个空白格，并且数据量很小，所以我们可以直接设置一个六维数组来来记录每一次A、B、空白格的状态，确保这个状态是唯一的。并且定义一个结构体用于记录空白格的坐标和所走步数和A、B坐标。在定义一个check函数用于判断是否A、B互换位置了。
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
string s[2];
int d[4][2] = {1 , 0 , 0 , 1 , -1 , 0 , 0 , -1};
int vis[2][3][2][3][2][3];
int sx , sy , ex , ey , x , y;
struct node{
int Sx , Sy , Ex , Ey , X , Y , cnt;
};
int check(int ax , int ay , int bx , int by){
return (ax == ex && ay == ey && bx == sx && by == sy);
}
void bfs(){
queue<node> q;
node p = {sx , sy , ex , ey , x , y , 0};
q.push(p);
vis[x][y][sx][sy][ex][ey] = 1;
while(!q.empty()){
node t = q.front(); q.pop();
for(int i = 0 ; i < 4 ; i++){
int xx = d[i][0] + t.X , yy = d[i][1] + t.Y;
if(xx < 0 || xx > 1 || yy < 0 || yy > 2 || vis[xx][yy][t.Sx][t.Sy][t.Ex][t.Ey]) continue;
p.X = xx , p.Y = yy , p.cnt = t.cnt + 1;
p.Sx = t.Sx , p.Sy = t.Sy , p.Ex = t.Ex , p.Ey = t.Ey;
if(xx == t.Sx && yy == t.Sy){
p.Sx = t.X , p.Sy = t.Y;
}
else if(xx == t.Ex && yy == t.Ey){
p.Ex = t.X , p.Ey = t.Y;
}
vis[p.X][p.Y][p.Sx][p.Sy][p.Ex][p.Ey] = 1;
if(p.Sx == ex && p.Sy == ey && p.Ex == sx && p.Ey == sy){
cout << p.cnt << '\n';
return;
}
q.push(p);
}
}
}
void solve(){
for(int i = 0 ; i < 2 ; i++){
getline(cin , s[i]);
for(int j = 0 ; j < 3 ; j++){
if(s[i][j] == 'A') sx = i , sy = j;
else if(s[i][j] == 'B') ex = i , ey = j;
else if(s[i][j] == ' ') x = i , y = j;
}
}
bfs();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AW 小朋友崇拜圈 （递归）
### 思路
判断环 找出最多数量的那个环
### 代码
~~~cpp=
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e5 + 10;
int n;
vector<int> ar[N];
int vis[N];
int ti[N];
int t , ans;
void dfs(int fa){
if(vis[fa]){
ans = max(ans , t - ti[fa] + 1);
return;
}
t++;
vis[fa] = 1;
ti[fa] = t;
dfs(ar[fa][0]);
}
void solve(){
cin >> n;
for(int i = 1 ; i <= n ; i++){
int u; cin >> u;
ar[i].pb(u);
}
for(int i = 1 ; i <= n ; i++){
if(!vis[i]){
memset(ti , 0 , sizeof ti);
t = 0;
dfs(i);
//cout << i << ' ' << ans << '\n';
}
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
~~~
## AX 缩位求和 （模拟）
### 思路
水题 不断地按照题目意思去转换
### 代码
```cpp=
#include<bits/stdc++.h>
using namespace std;
void solve(){
string s; cin >> s;
int t = 0;
while(s.size() > 1){
t = 0;
for(int i = 0 ; i < s.size() ; i++){
t += (s[i] - '0');
}
string tem;
while(t){
tem = char(t % 10 + '0') + tem;
t /= 10;
}s = tem;
}
cout << s << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--){
solve();
}
return 0;
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
