总体学习情况
这周的强度还是很大的,二分和简单数据结构的牛客题单还没有刷完，想着把补题放到第一位，然后后面慢慢补上那些没有做的题，比赛打得还是依旧很拉，不过没有关系，太阳照常升起，总会赢的。
知识点模块
1.Floyd算法用来求两点到达的最小代价，复杂度是O（n3）
其实代码并不难记，可以说板子很好背了，用这个知识点有些题目套板子就秒了。
//floyd算法计算到达两点的最小代价
for(int k=0;k<=n;k++)//n是节点数
{
for(int i=0;i<n;i++)//每加一个节点都要枚举图看看有没有可以被更新的
{
for(int j=0;j<n;j++) if(dp[i][j]>dp[i][k]+dp[k][j]) dp[i][j]=dp[i][k]+dp[k][j];
}
}
2.快速幂的模板再度复习了一下
int ksm(int a,int n)//a为底数，n为次方
{
int res=1;
while(n>0)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}//快速幂模版
3.同样又遇见了输出结果分数mod998244353
a/b==a%mod*ksm(b,mod-2)%mod
4.对于二进制枚举的使用会比刚学更加熟悉了
举例来讲解一下核心的代码
题目会给我们k个选择，每个选择中有两个选项，让我们选A还是选B，0为选A，1为选B
for(int i=0;i<(1<<k);i++)//i代表的是选择情况，比如当k=3时，1是001，
//001 每个数位上代表着对每个人选择第一个数或第二个数，0代表选第一个，1代表选第二个
{
for(int j=0;j<k;j++)
{
if((i>>j)&1) //i>>j想象成把一位数往右挪 &1判断数位上是0还是1
else ;
}
//添加所需要的条件代码
maxx=max(ans,maxx);
}
5.原来一个有n位数的数字如果每个数位上加起来的和是3的倍数，那么这个数就是3的倍数
有时候甚至怀疑自己小学数学没有学好
那么如果遇到这种题型
给你一个n位数，让你判断最少去掉几位能够让这个数为3的倍数
我们就可以采取一下的策略
- 让每位数对3取余，存入cnt【1】，cnt【2】
- 将每个数位加起来得到sum，sum对3取余，看余1还是余2
- 分类讨论需要删几位（并不麻烦）
举个样例代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
题目链接http://162.14.124.219/contest/1007/problem/I
void solve()
{
int n;
cin>>n;
if(n%3==0)
{
cout<<0;
return;
}
if(n<=10){
if(n%3!=0){
cout<<-1;
return ;
}
}
int sum=0;//所有数位的数加起来总和
int tt=0;//总共有几位数
int cnt[5]={0};
while(n)
{
int p=n%10;//每个数位上的数
cnt[p%3]++;
sum+=n%10;
n/=10;
tt++;
}
//等价1就是与3取余为1的数1 4 7
//等价2就是2 5 8
if(sum%3==1)
{
//删除数一定要考虑数位是否是足够的
if(cnt[1]>=1&&tt>1) cout<<1; //当总和取余3为1，只需要删掉一个等价1的数即可
else if(cnt[2]>=2&&tt>2) cout<<2;//没有一个等价1 就删俩个等价2
else cout<<-1;
}else if(sum%3==2)//同理
{
if(cnt[2]>=1&&tt>1) cout<<1;
else if(cnt[1]>=2&&tt>2) cout<<2;
else cout<<-1;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
6.可以总结出一类题型，就是题目大概为，让你找三个数是否能够组成什么数或满足什么条件
这类题有几个特征，一个是让你明显的看出可以暴力，又让你知道这个复杂度过不去，于是一般的解法就是降为两层循环，然后寻找这两个数与第三个数的相互制约的条件
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b?lang=en
https://atcoder.jp/contests/tenka1-2017-beginner/tasks/tenka1_2017_c?lang=en
这两道题就是类似的
7.其实对一些区间进行相应的操作的模拟很重要，这感觉也是基本功的一部分
比如这一题D - Equal Cut
我们如何实现对区间切三刀的模拟
void solve()
{
int n; cin>>n;
vector<int>ve(n+1);for(int i=1;i<=n;i++) cin>>ve[i];
for(int i=1;i<=n;i++) sum[i]=ve[i]+sum[i-1];
//枚举第二刀把其分为L R区间
int l=1,r=3;
int ans=1e9;
for(int i=2;i<=n-2;i++)//总共有n个元素第二刀最多切到n-2
{
while(l+1<i&&abs(js(1,l)-js(l+1,i))>=abs(js(1,l+1)-js(l+2,i))) l++;
//相当于你在L这个区间 找位置切，直到找到L里左右区间差值最小
//差值最小能够保证我们前面有一个使减数尽量大的区间
while(r+1<n&&abs(js(i+1,r)-js(r+1,n))>=abs(js(i+1,r+1)-js(r+2,n))) r++;
//在R区间是同理的
set<int>se;
//set自动从小到大排序
se.insert(js(1,l));
se.insert(js(l+1,i));
se.insert(js(i+1,r));
se.insert(js(r+1,n));
ans=min(ans,abs(*se.begin()-*prev(se.end())));//prev用来获取最后一个值的地址
}
cout<<ans<<endl;
}
8.多从数与数的性质来思考问题，而不是总是举出很多样例来试
比如D - DivRem Number
就是运用被除数=除数×商+余数，并且考虑一下范围，想到了这个题就变得很简单了
void solve()
{
int n; cin>>n;
int ans=0;
//被除数=除数*商+余数，因为题目中的商和余数相等
//我们假设商和余数为x，n=m*x+x;
//所以m=n/x-1
//所以我们枚举余数 又因为除数大于余数 所以m>x;所以n=m*（x+1）>x*(x+1)
//所以枚举的范围（x+1）*x<n
for(int x=1;x*(x+1)<n;x++)
{
if(n%x==0) ans+=(n/x-1);//这里取余的原因是 因为一定要满足n=m*(x+1)这个等式，
//这个点很细 因为并不是枚举的每个x都满足这个等式
}
cout<<ans;
}