A
答案: $2048$
进制转换
将 $2022$ 转化为二进制为 $11111100110$ ,取比其多一位的二进制数只有最高位为 $1$,即 $100000000000$ ,转化为十进制就是 $2048$ (进制转换的代码应该熟记于心的啊)
C++ 代码
//p进制(2~36)转为十进制
int p_to_ten(char s[], int p)
{
//s[]为顺序存储的p进制字符串
int x = 0;
for (int i = 0; s[i]; i++)
{
x *= p;
if (s[i] >= 'A' && s[i] <= 'Z') x += (s[i] - 'A' + 10);
else x += (s[i] - '0');
}
return x;
}
char s[];
int len;
//十进制转为p进制
void ten_to_p(int x, int p)
{
int tmp = 0;
do{
tmp = x % p;
if (tmp < 10) s[len++] = '0' + tmp;
else s[len++] = 'A' + tmp - 10;
x /= p;
}while(x);
//s[]中从len-1到0倒序存储
}
B
答案: $26390$
模拟,日期处理
C++ 代码
int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int y) //判断闰年
{
return (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0));
}
int cnt(int y, int m, int d)
{
int ans = d;
for (int i = 1949; i < y; i++) //加年
{
if (check(i)) ans += 366;
else ans += 365;
}
for (int i = 0; i < m; i++) //加月
{
ans += mon[i];
}
if (m > 2 && check(y)) ans++;
return ans;
}
void solve()
{
cout << cnt(2022, 1, 1) - cnt(1949, 10, 1) << endl;
}
C
答案: $1038$
也是进制转换
C++ 代码
int p_to_ten(string s, int p)
{
int x = 0;
for (int i = 0; i < s.size(); i++)
{
x *= p;
if (s[i] >= 'A' && s[i] <= 'Z') x += (s[i] - 'A' + 10);
else x += (s[i] - '0');
}
return x;
}
bool check(int x)
{
int y = p_to_ten(to_string(x), 16);
return y % x == 0;
}
void solve()
{
for (int i = 10; ; i++)
{
if (check(i))
{
cout << i << endl;
break;
}
}
}
D
答案: $592$
线性DP
基础的线性DP问题,参考摘花生那道题,至于说题目的那个怎么读入,可以复制进一个txt文件,然后读取txt文件。
用 $a[i][j]$ 表示第 $i$ 行第 $j$ 列的数值, $f[i][j]$ 表示走到第 $i$ 行 第 $j$ 列时数字和的最大值,则能够得到状态方程为
$f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j]$
C++ 代码
const int N = 65;
char s[N][N];
int f[N][N];
void solve()
{
ifstream cin("4.in");
for (int i = 1; i <= 30; i++) cin >> s[i] + 1;
for (int i = 1; i <= 30; i++)
for (int j = 1; j <= 60; j++)
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (s[i][j] - '0');
cout << f[30][60] << endl;
}
E
答案: $33$
01背包问题变形
把1到2022所有素数都筛出来,这里是填空题,随便怎么筛都可以,最后筛出来306个素数,至于筛素数,这里如果不会的话就试除法筛就可以,然后就是01背包求最大物品数量,这里就不把闫氏DP分析法写一遍了
C++ 代码
const int N = 2030;
bool st[N];
int v[N], f[N][N];
vector<int> prime;
int cnt;
void solve()
{
getPrime(2022); //筛素数
for (auto& c : prime)
{
v[++cnt] = c;
}
for (int i = 1; i <= 306; i++)
for (int j = 2022; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + 1);
cout << f[2022] << endl;
}
F
模拟
C++ 代码
typedef long long LL;
LL t, c, s;
void solve()
{
cin >> t >> c >> s;
cout << (s - c) * t / c;
}
G
集合判重
C++ 代码
const int N = 110;
unordered_set<string> st;
int n;
string s[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
}
for (int i = 1; i <= n; i++)
{
if (!st.count(s[i])) cout << s[i] << endl;
st.insert(s[i]);
}
}
H
双指针
枚举原串中最长的回文后缀,将此时的前缀翻转后接在原字符串后即可,但注意前缀可能为空
C++ 代码
bool check(string s)
{
int i = 0, j = s.size() - 1;
while (i < j)
{
if (s[i] != s[j]) return false;
i++, j--;
}
return true;
}
void solve()
{
cin >> s;
int n = s.size();
for (int i = 0, j = n; i < n; i++, j--)
{
string temp = s.substr(i, j);
if (check(temp))
{
string s1 = s.substr(0, i);
string s2 = s1;
if (s1.size())
{
reverse(s2.begin(), s2.end());
cout << s1 + temp + s2 << endl;
}
else cout << temp << endl;
}
}
}
I
搜索(如果数据量更大就需要用上前缀和)
搜索的起始点可以直接去掉最外圈,只搜2~n-1行的2~m-1列,至于后面那个函数叫dfs(实际跟dfs没关系)只是函数写顺手了,有点像深搜的思路,要注意的是四个方向都搜到了和中心相同字母才算是一个’X’
C++ 代码
typedef pair<int,int> PII;
const int N = 110;
int n, m;
char p[N][N];
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
bool check(int x, int y)
{
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
bool bfs(int x, int y, char c, int s)
{
int cnt = 0;
for (int i = 0; i < 4; i++)
{
int xt = x + s * dx[i], yt = y + s * dy[i];
if (check(xt, yt))
{
if (p[xt][yt] != c) return false;
cnt++;
}
}
if (cnt == 4) return true;
else return false;
}
int dfs(int x, int y)
{
int s = 1;
while (bfs(x, y, p[x][y], s)) s++;
return s - 1;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> p[i] + 1;
}
int ans = 0;
for (int i = 2; i <= n - 1 ; i++)
{
for (int j = 2; j <= m - 1; j++)
{
ans += dfs(i, j);
}
}
cout << ans << endl;
}
J
树状数组/归并排序/线段树
这里就给出树状数组的解法。
考虑每个后缀中的第一个元素应该被交换几次才能满足升序,第一种情况就是已经升序,不需要交换,第二种情况就是后面小于其的数都要与其交换。从前往后枚举每一个后缀,就可以计算出逆序对的数量。树状数组可以在 $O(n log 2k)$ 的时间复杂度求出逆序对的数量(其中k为数组中最大值与最小值的差值),在本题中比$O(n log n)$的归并排序要快,记得要来long long,至于我的代码中为什么没有写成long long,是因为我写了这行代码:
#define int long long
但此时注意一下,main函数的返回值必须是int,main函数这样改写就可以了
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
/*......*/
return 0;
}
适合不确定是否开long long的情况下。
有必要提醒一下,在数据量比较大的情况下,cin和cout会很慢,会部分数据导致超时,如果不愿意写scanf和printf的可以在main函数前面开头加上上面那几行代码,但加上后就不要再使用scanf和printf。
C++ 代码
const int N = 1e6 + 10;
int n, a[N], tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
{
tr[i] += c;
}
}
int sum(int x)
{
int ans = 0;
for (int i = x; i; i -= lowbit(i))
{
ans += tr[i];
}
return ans;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int ans = 0;
for (int i = n; i; i--)
{
ans += sum(a[i] - 1) * a[i];
add(a[i], 1);
}
cout << ans << endl;
}