#include <bits/stdc++.h>
using namespace std;
int T, n, a[200005], cha;
void docase(int t)
{
int cnt = 1, max_cnt = 1, cha;
cin >> n;
cin >> a[0];
for(int i=1;i<n;i++)
{
cin >> a[i];
if(i > 1 && a[i] - a[i-1] == cha)
{
cnt++;
max_cnt = max(max_cnt, cnt);
}
else
{
cnt = 2;
max_cnt = max(max_cnt, cnt);
cha = a[i] - a[i-1];
}
}
// Case #1: 4
cout << "Case #" << t+1 << ": " << max_cnt << endl;
}
int main()
{
cin >> T;
for(int i=0;i<T;i++)
docase(i);
return 0;
}
活动打卡代码
AcWing 3311. 最长算术
#include <bits/stdc++.h>
using namespace std;
int T, n, a[200005], cha;
void docase(int t)
{
int cnt = 1, max_cnt = 1, cha;
cin >> n;
cin >> a[0];
for(int i=1;i<n;i++)
{
cin >> a[i];
if(i > 1 && a[i] - a[i-1] == cha)
{
// 差不变则计数器加1
cnt++;
max_cnt = max(max_cnt, cnt);
}
else
{
// 差变了（不再是等差数列了），则计数器归2
cnt = 2;
max_cnt = max(max_cnt, cnt);
cha = a[i] - a[i-1];
}
}
cout << "Case #" << t+1 << ": " << max_cnt << endl;
}
int main()
{
cin >> T;
for(int i=0;i<T;i++)
docase(i);
return 0;
}
活动打卡代码
AcWing 691. 立方体IV
#include <bits/stdc++.h>
using namespace std;
int T, s, a[1005][1005], b[1005][1005];
int find(int y, int x)
{
if(b[y][x] != -1)
return b[y][x];
b[y][x] = 1;
if(y-1>=1 && a[y-1][x] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y-1, x) + 1);
if(y+1<=s && a[y+1][x] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y+1, x) + 1);
if(x-1>=1 && a[y][x-1] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y, x-1) + 1);
if(x+1<=s && a[y][x+1] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y, x+1) + 1);
//cout << b[y][x] << endl;
return b[y][x];
}
void docase(int t)
{
cin >> s;
for(int j=1;j<=s;j++)
for(int i=1;i<=s;i++)
cin >> a[j][i];
int mx = 0, mx_x=0, mx_y=0;
for(int j=1;j<=s;j++)
{
for(int i=1;i<=s;i++)
{
find(j, i);
if(mx == 0 || b[j][i] > mx || (b[j][i] == mx && a[j][i] < a[mx_y][mx_x]))
{
//cout << a[mx_y][mx_x] << "-";
mx = b[j][i];
mx_x = i;
mx_y = j;
//cout << a[mx_y][mx_x] << " " << mx << endl;
}
}
}
cout << "Case #" << t << ": " << a[mx_y][mx_x] << " " << mx << endl;
}
int main()
{
cin >> T;
for(int i=1;i<=T;i++)
{
for(int j=0;j<1005;j++)
for(int i=0;i<1005;i++)
b[j][i] = -1;
docase(i);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int T, s, a[1005][1005], b[1005][1005];
int find(int y, int x)
{
if(b[y][x] != -1)
return b[y][x];
b[y][x] = 1;
if(y-1>=1 && a[y-1][x] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y-1, x) + 1);
if(y+1<=s && a[y+1][x] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y+1, x) + 1);
if(x-1>=1 && a[y][x-1] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y, x-1) + 1);
if(x+1<=s && a[y][x+1] == a[y][x] + 1)
b[y][x] = max(b[y][x], find(y, x+1) + 1);
//cout << b[y][x] << endl;
return b[y][x];
}
void docase(int t)
{
cin >> s;
for(int j=1;j<=s;j++)
for(int i=1;i<=s;i++)
cin >> a[j][i];
int mx = 0, mx_x=0, mx_y=0;
for(int j=1;j<=s;j++)
{
for(int i=1;i<=s;i++)
{
find(j, i);
if(mx == 0 || b[j][i] > mx || (b[j][i] == mx && a[j][i] < a[mx_y][mx_x]))
{
//cout << a[mx_y][mx_x] << "-";
mx = b[j][i];
mx_x = i;
mx_y = j;
//cout << a[mx_y][mx_x] << " " << mx << endl;
}
}
}
cout << "Case #" << t << ": " << a[mx_y][mx_x] << " " << mx << endl;
}
int main()
{
cin >> T;
for(int i=1;i<=T;i++)
{
for(int j=0;j<1005;j++)
for(int i=0;i<1005;i++)
b[j][i] = -1;
docase(i);
}
return 0;
}
活动打卡代码
AcWing 4279. 笛卡尔树
#include <bits/stdc++.h>
using namespace std;
int n, a[100];
queue<pair<int, int>> q;
int main()
{
cin >> n;
for(int i=0;i<n;i++)
cin >> a[i];
// bfs
q.push({0, n-1});
while(!q.empty())
{
pair<int, int> p = q.front();
q.pop();
int le = p.first;
int ri = p.second;
if(le > ri)
continue;
// 找到最小的
int mi = a[le];
int mii = le;
for(int i=le;i<=ri;i++)
{
if(a[i] < mi)
{
mi = a[i];
mii = i;
}
}
cout << mi << " ";
// 左边构成左子树
q.push({le, mii-1});
// 右边构成右子树
q.push({mii+1, ri});
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, a[100];
queue<pair<int, int>> q;
int main()
{
cin >> n;
for(int i=0;i<n;i++)
cin >> a[i];
// bfs
q.push({0, n-1});
while(!q.empty())
{
pair<int, int> p = q.front();
q.pop();
int le = p.first;
int ri = p.second;
if(le > ri)
continue;
// 找到最小的
int mi = a[le];
int mii = le;
for(int i=le;i<=ri;i++)
{
if(a[i] < mi)
{
mi = a[i];
mii = i;
}
}
cout << mi << " ";
// 左边构成左子树
q.push({le, mii-1});
// 右边构成右子树
q.push({mii+1, ri});
}
return 0;
}
int cmp(int a, int b)
{
return (a%2) > (b%2);
}
class Solution {
public:
void reOrderArray(vector<int> &array) {
sort(array.begin(), array.end(), cmp);
}
};
活动打卡代码
AcWing 4273. 链表合并
#include <bits/stdc++.h>
using namespace std;
int head_a, head_b, n;
int val[100005], ne[100005];
vector<int> a, b, res;
int main()
{
cin >> head_a >> head_b >> n;
for(int i=0;i<n;i++)
{
int addr;
cin >> addr;
cin >> val[addr] >> ne[addr];
}
int pa = head_a;
while(pa != -1)
{
a.push_back(pa);
pa = ne[pa];
}
int pb = head_b;
while(pb != -1)
{
b.push_back(pb);
pb = ne[pb];
}
if(a.size() < b.size())
swap(a, b);
reverse(b.begin(), b.end());
for(int i=0,j=0;i<a.size();i++)
{
res.push_back(a[i]);
if(i % 2 == 1 && j < b.size())
res.push_back(b[j++]);
}
for (int i = 0; i < res.size(); i ++ )
{
printf("%05d %d ", res[i], val[res[i]]);
if (i == res.size() - 1)
printf("-1\n");
else
printf("%05d\n", res[i + 1]);
}
}
活动打卡代码
AcWing 4274. 后缀表达式
#include <bits/stdc++.h>
using namespace std;
int n;
string a[100];
int lc[100]; // 左孩子
int rc[100]; // 右孩子
int parent[100]; // 父节点
int root;
void dfs(int node)
{
if(node == -1)
return;
cout << "(";
if(lc[node] == -1 || rc[node] == -1)
{
cout << a[node];
dfs(lc[node]);
dfs(rc[node]);
}
else
{
dfs(lc[node]);
dfs(rc[node]);
cout << a[node];
}
cout << ")";
}
int main()
{
memset(parent, -1, sizeof(parent));
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i] >> lc[i] >> rc[i];
if(lc[i] != -1)
parent[lc[i]] = i;
if(rc[i] != -1)
parent[rc[i]] = i;
}
// 查找root节点
root = 1;
while(parent[root] != -1)
root = parent[root];
dfs(root);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n;
string a[100];
int lc[100]; // 左孩子
int rc[100]; // 右孩子
int parent[100]; // 父节点
int root;
void dfs(int node)
{
if(node == -1)
return;
cout << "(";
if(lc[node] == -1 || rc[node] == -1)
{
cout << a[node];
dfs(lc[node]);
dfs(rc[node]);
}
else
{
dfs(lc[node]);
dfs(rc[node]);
cout << a[node];
}
cout << ")";
}
int main()
{
memset(parent, -1, sizeof(parent));
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i] >> lc[i] >> rc[i];
if(lc[i] != -1)
parent[lc[i]] = i;
if(rc[i] != -1)
parent[rc[i]] = i;
}
// 查找root节点
root = 1;
while(parent[root] != -1)
root = parent[root];
dfs(root);
return 0;
}
