《A 填空问题》
试题 A：带宽
我觉得题目出错了，在计算机网络中带宽中的bps是bit/s 其中的单位M 是10^6 而不再是按照2^20来算了
但是答案不是这样的，奇怪！
试题 B ：纯质数
死亡原因：
没有把0设置为非质数
其余的主要是用线性筛筛出1~20210605中的质数就好啦
int solveB()
{
int t = 20210605;
vector<int> pr;
st[1] = true;
st[0] = true;
for (int i = 2; i <= t; i++)
{
if (!st[i])
pr.push_back(i);
for (int j = 0; j < pr.size() && i * pr[j] <= t; j++)
{
st[i * pr[j]] = true;
if (i % pr[j] == 0)
break;
}
}
int cnt = 0;
for (int i = 0; i < pr.size(); i++)
{
int prime = pr[i];
bool flag = true;
while (prime)
{
int g = prime % 10;
if (st[g])
{
flag = false;
break;
}
prime /= 10;
}
if (flag)
cnt++;
}
return cnt;
}
试题 C ：完全日期
死亡原因：
没有将特殊年：闰年的2月设置为29天（话说我喵的哪知道闰年是啥，虽然做题目的时候做到过）
闰年就是 能被400整除 或 能被4整除但不能被100整除的年份
int getDay(int year, int month)
{
// 判断大月
if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
{
return 31;
}
// 判断小月
if (month == 4 || month == 6 || month == 9 || month == 11)
{
return 30;
}
// 剩下的就是2月份 ，判断年份是否为闰年
if (year % 400 == 0)
{ // 能被400整除年份是世纪闰年
return 29;
}
if (year % 100 != 0 && year % 4 == 0)
{ // 除世纪闰年外，剩下的闰年都不能被100整除，但可以被4整除
return 29;
}
return 28; // 剩下的就都是平年且为2月了
}
int get(int t)
{
int res = 0;
while (t)
{
res += t % 10;
t /= 10;
}
return res;
}
int solveC()
{
int cnt = 0;
for (int year = 2001; year <= 2021; year++)
for (int month = 1; month <= 12; month++)
for (int i = 1; i <= getDay(year, month); i++)
{
int ans = get(year) + get(month) + get(i);
int gans = sqrt(ans);
if (gans * gans == ans)
cnt++;
}
return cnt;
}
试题 D：最小权值
死亡原因：
最开始就往贪心的方面想去了
应该先想一下暴力的
每个节点的权值都由左右子节点决定，明显可以递归，然后在递归中求最小值（dp）
ll solveD()
{
ll dp[2023];
for (int i = 2; i <= 2021; i++)
dp[i] = 1e18;
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= 2021; i++)
for (int j = 0; j <= i - 1; j++)
{
dp[i] = min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - j - 1] + j * j * (i - j - 1));
}
return dp[2021];
}
《F 123》
死亡原因：
基本想法我是想到了，但是在细节处理上出了问题
同时当时还没有想到用前缀和来算出各个行区间的和
解题思路：
我们可以将整个数列排除一个三角形
然后其有行和列，等下有利于讨论
我们被给出一个l和r
首先我们可以通过二分的方式得知 l和r所在的行（当时我写的时候是求出l和r前一行，于是就有很多细节要处理）
（因为每一行数的个数是++的关系，我们可以利用公式（n+1）*n/2 来求1~n行中的总共数的个数）
然后再算出l和r所在的列，即l和r指向的数
最后我们算出l这一行中要加上的数和r这一行中要加上的数（1.有细节）
然后算出l和r之间剩余的行中全部数的总和（2.咋快速算出来？）
来解决问题1：
我们咋快速算出l和r行中要加上的数？
设l的列为cowl,r的列为cowr
第l行总和 - 1~cowl-1的总和 = l行要加上的数
1~cowr的总和 = r行要加上的数
唯一要注意的细节是如果l和r在同一行时，上述算法多算了
要用第l行的总和 - 1~cowl-1的总和 - （第l行的总和-1~cowr的总和）来算
来解决问题2：
如果简单地：
for （int i=行1；i<=行2；i++)
ans+=(i+1)*i/2
会超时
我们可以用前缀和算出
第1~n行之前的数总和 pre[n]
然后用 pre[行2]-pre[行1-1] 得出上述的问题
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll h = 0, sum[10000002];
ll get(ll num)
{
return (num + 1) * num / 2;
}
int bin(ll tar)
{
ll l = 1, r = 1e8, ans = -1;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (get(mid) >= tar)
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return ans;
}
void solve()
{
ll l, r;
cin >> l >> r;
ll rowl = bin(l), rowr = bin(r);
/* cout << rowl << " " << rowr << endl; */
ll cowl = l - get(rowl - 1), cowr = r - get(rowr - 1);
/* cout << cowl << " " << cowr << endl; */
ll ans = 0;
if (rowr - rowl >= 1)
{
ans += get(rowl) - get(cowl - 1) + get(cowr);
/* cout << ans << endl; */
rowl++, rowr--;
if (rowl <= rowr)
ans += sum[rowr] - sum[rowl - 1];
}
else
ans += get(rowl) - get(cowl - 1) - (get(rowl) - get(cowr));
cout << ans << endl;
}
int main()
{
int t;
cin >> t;
for (ll i = 1; i <= 10000000; i++)
{
sum[i] = sum[i - 1] + get(i);
h += i;
if (h > 1e12)
break;
}
while (t--)
solve();
return 0;
}
《G 异或变换》
猜的有循环节，但是有个处理不知道优化
更多的就不会了，对于现在的我来说还是太难了
《H 二进制问题》
这个有两种写法都很不错：
1.纯数学
2.数位dp
首先来推荐学习数位dp的博客：
首先来看下数位dp是求解啥问题的：
在这里我们的区间是 1~N
条件是：数在二进制下共有K个1
一般数位dp都是有模板的，基本上dfs+记忆化搜索来解决
在这道问题中我们要解决的问题是：
1.我们是针对于二进制位数来枚举的，我们如何知道我们枚举的数没有超过（低于）给定范围？
巧妙的设计：
对于没有超过我们解决了，如何解决不低于？
利用前缀和思想：
求出0~r直接合法的数个数 - 求出0~l-1直接合法的数个数= l~r之间合法的数个数
这样就不用担心低于给定范围的问题了
同时还有一些其他参数：
对于这道题，我们写出数位dp的模板：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = (int)(log(1e18) / log(2)) + 1;
int k, cnt = 0;
// dp[pos][limit][zc]
int A[N];
ll dp[N][2][N];
ll dfs(int pos, int limit, int zc)
{
if (pos >= cnt)
return zc == k ? 1 : 0;
if (dp[pos][limit][zc] != -1)
return dp[pos][limit][zc];
ll ans = 0;
for (int i = 0; i <= (limit ? A[pos] : 1); i++)
ans += dfs(pos + 1, limit && (i == A[pos]), zc + i);
dp[pos][limit][zc] = ans;
return ans;
}
ll solve(ll num)
{
cnt = 0;
memset(A, 0, sizeof(A));
memset(dp, -1, sizeof(dp));
while (num)
{
A[cnt++] = num & 1;
num >>= 1;
}
reverse(A, A + cnt);
return dfs(0, 1, 0);
}
int main()
{
ll n;
cin >> n >> k;
if (k == 0)
cout << 0 << endl;
else
cout << solve(n) << endl;
return 0;
}
《J 异或三角》
也是一道数位dp的题目，但是更难（题目条件要仔细分析）
根据 a^b^c=0, 可以知道 a=b^c
a b c直接可以相等吗？
如果相等 a^b^c 的条件在满足 a,b,c可以构成三角形的条件下就不满足了
所以a,b,c之间不可以相等
a,b,c三条边要组成三角形那么 a+b>c a+c>b b+c>a
这里因为a,b,c不相等，我们设a为最大边进行分析
那么只要 a<b+c 即可了
a>b a>c
对于a,b,c二进制下的每一位进行分析可以得出
在a,b 或 a,c
二进制的前缀全部相同的情况下，第一次出现不同一定是(ai,bi)=(1,0)
(ai,ci)同理
如果 a=b^c
对于a,b,c上的每一位数有和变换？
（a,b,c）= (0,0,0) (0,1,1) (1,0,1) (1,1,0)
同时 b^c<b+c
因为^异或运算是不带进位的加法运算，所以当前仅当 （bi,ci）==(1,1)
出现过才有 b+c>b^c
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unistd.h>
using namespace std;
const int N = 32;
typedef long long ll;
int A[N], cnt = 0;
ll dp[N][2][8];
// 这里state是状态压缩后的值,其共有三个状态111
// 第一个状态是 a>b? 第二个状态 a>c? 第三个状态 是否存在过 (bi,ci)==(1,1)?
// 因为a^b^c==0所以我们可以推断出二进制下的每一位只有4种变换状态：
// (a,b,c)==(0,1,1) (0,0,0) (1,0,1) (1,1,0)
// dfs(pos,limit,state) 为何足以代表一个状态？
// 通过对题目的分析我们可以知道这道题对于一个合法的(a,b,c)只要求
// a>b a>c 存在(bi,ci)==(1,1)即可，这里我们用state描述了这三个条件
// 这里我们假设a是最大的边长，通过对题目的分析可知a,b,c不可能相同
// 然后其实我们这里是在枚举a二进制下的各个位
// 枚举a其实是在1~n的范围下枚举的，其实也就是数位dp的典型运用：求[l,r]内满足某条件的数的个数
// 然后通过固定a的位数来枚举 (b,c)的情况
// 因为a^b^c==0的条件 在ai固定的情况下(b,c)的状态是有限的，可枚举
ll dfs(int pos, int limit, int state)
{
if (pos >= cnt)
return state == 7;
if (dp[pos][limit][state] != -1)
return dp[pos][limit][state];
ll ans = 0;
// 注意这里 i <= limit ? A[pos] : 1 写法是错误的，一定要加上()
for (int i = 0; i <= (limit ? A[pos] : 1); i++)
{
int b = state >> 2 & 1, c = state >> 1 & 1;
// 这里因为我的判断所以是一定没有(ai,bi,ci)==(0,1,1)在条件a>b,a>c出现之前发生的
// ai==0
if (i == 0)
{
// (bi,ci)==(0,0)
ans += dfs(pos + 1, limit && (A[pos] == i), state);
if (b && c)
//(bi,ci)==(1,1)
ans += dfs(pos + 1, limit && (A[pos] == i), state | 1);
}
// ai==1
else
{
//(bi,ci)==(0,1)
ans += dfs(pos + 1, limit && (A[pos] == i), state | 4);
//(bi, ci) == (1, 0)
ans += dfs(pos + 1, limit && (A[pos] == i), state | 2);
}
}
dp[pos][limit][state] = ans;
return ans;
}
void solve(int num)
{
cnt = 0;
memset(A, 0, sizeof(A));
memset(dp, -1, sizeof(dp));
while (num)
{
A[cnt++] = num & 1;
num >>= 1;
}
reverse(A, A + cnt);
// 注意最后这里还要*3因为上面dfs只是假设a是最大,还有b,c最大的情况
cout << 3 * dfs(0, 1, 0) << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ll num;
cin >> num;
solve(num);
}
return 0;
}
《I 翻转括号序列》
太难了
但是有些思想我可以学：
1.当我写线段树的题目时，先考虑一下要打印出来的问题应该在线段树中用什么变量来表示和维护
针对于这个其他条件再考虑如何对这些变量作维护
2.我们可以将（设置为1，）设置为-1，
一个括号区间是否合法，可以表示成：
3.
4. 线段树对于区间操作只是用lazy标记进行延迟了同时对于处于整个区间的操作进行了整块操作而已，
如果最终还是要进入到这个区间的叶子节点
那么还是要实实在在地进行操作
好博客<-----
标签：return,int,ll,pos,蓝桥,杯国,2021,ans,dp From： https://www.cnblogs.com/cilinmengye/p/17400420.html