题解参考处
蚂蚁开会
模拟
分析
题目给出了起点和终点，且求的结果是整数点，那么计算出这条该直线的偏移量，把经过的每个整数点记录下来即可，出现超过两次的点即可作为会议点。
补充知识点
$dx’=dx/gcd(dx,dy)$
$dy’=dy/gcd(dx,dy)$
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int>P;
int n,ans;
map<P,int>mp;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0,x,y,xx,yy;i<n;i++)
{
cin>>x>>y>>xx>>yy;
int d=gcd(abs(xx-x),abs(yy-y));
int dx=(xx-x)/d,dy=(yy-y)/d;
int nx=x,ny=y;
while(nx!=xx||ny!=yy)
{
mp[{nx,ny}]++;
nx+=dx;
ny+=dy;
}
mp[{nx,ny}]++;
}
for(auto &w:mp)
{
if(w.second>=2)ans++;
}
cout<<ans;
return 0;
}
立定跳远
二分答案
分析
为何可以使用二分，因为此题的答案跳跃距离具有单调性，即当前这个 $ans$ 是可行解，那比 $ans$大的都是可行解，二分check函数最难写，从m上找突破口，在两块石头间可以需要增加多少检查点，即
$(ai-ai-1)/L-1$
为何-1？因为这里求出的是区间数，-1求出分隔出的检测点数。至于技能的使用，两倍的跳跃距离，本质是什么。本质是一定能跳过去，所以代换成可添加的检测点+1。
注意二分跳跃距离的时候，应该注意符合实际意义，最小值应该为1，不应为0（否则第一种检查下会RE）
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
int n,m,a[N];
int work(int a,int b)
{
if(a%b)
return a/b+1;
else return a/b;
}
bool check(int x)
{
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=work(a[i]-a[i-1],x)-1;
return cnt<=m;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
m++;
for(int i=1;i<=n;i++)cin>>a[i];
int l=1,r=1e18;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
cout<<l;
return 0;
}
最小字符串
贪心 双指针
分析
不需要咋分析，看代码吧
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m;
string a,b;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>a>>b;
sort(b.begin(),b.end());
int i=0,j=0;
for(;i<n;i++)
{
if(b[j]<a[i])
{
while(b[j]<a[i]&&j<m)
cout<<b[j++];
}
cout<<a[i];
}
while(j<m)cout<<b[j++];
return 0;
}
数位翻转
动态规划
分析
对于 $dp$ 数组的初始化和边界还不是很明白
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f3f3f3f3fll;
int n,m,a[N],dp[N][N][2];
//dp[i][j][0/1] 0是第i位不翻转，1是第i位翻转,恰好前i位共有j位翻转的最优情况
//dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i];
//dp[i][j][1]=max(dp[i-1][j-1][0],dp[i][j][1])+f[i];
//f[i]是第i位翻转二进制后的值
int f(int x)
{
int ans=0;
while(x)
{
ans=ans<<1|x&1;
x>>=1;
//不是很懂
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int j=0;j<=m;j++)
{
dp[0][j][0]=-INF-1;
dp[0][j][1]=-INF-1;
}
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
{
const int ff=f(a[i]);
dp[i][0][0]=dp[i-1][0][0]+a[i];
dp[i][0][1]=-INF-1;
for(int j=1;j<=m;j++)
{
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])+a[i];
dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+ff;
}
}
int ans=0;
for(int j=0;j<=m;j++)
ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
cout<<ans;
return 0;
}
数星星
组合数 树的概念
分析
题意理解上是理解错了，需要复习一下树的相关知识了。还有一个是这里组合数的求法与y总讲的不一样
代码
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, deg[N];
int l, r;
LL fac[N], inv[N], ans[N];
LL qmi(LL a, LL b, LL p)
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
void init()
{
fac[0] = inv[0] = 1;
for (int i = 1; i <= n; ++i)
{
fac[i] = fac[i - 1] * i % mod;
}
for (int i = 1; i <= n; ++i)
{
inv[i] = qmi(fac[i], mod - 2, mod);
}
}
LL C(int n, int m)
{
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
cin >> n;
init();
for (int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
++deg[a], ++deg[b];
}
cin >> l >> r;
ans[1] = n, ans[2] = n - 1;
for (int i = 1; i <= n; ++i)
{
if (deg[i] >= 2)
{
for (int j = 3; j <= deg[i] + 1; ++j)
{
ans[j] = (ans[j] + C(deg[i], j - 1)) % mod;
}
}
}
LL sum = 0;
for (int i = l; i <= r; ++i)
sum = (sum + ans[i]) % mod;
cout << sum << endl;
return 0;
}
组合数复习
小球放盒
小球放盒问题：$n$ 个不同的球放入 $r$ 个不同的盒子，不能有空盒
设有 $bi$ 的球，$i$ 属于 $[1,n]$ 从中取出 $bi$ , $bi$ 有两种选择：
（1）$bi$ 单独占一个盒子，其余盒子只能放在 $m-1$ 个盒子中，所以方案数：$f(n-1,m-1)$
(2) $bi$ 和别的球共占一个盒子，则是 $n-1$ 个球放 $m$ 个盒，$f(n-1,m)$ ,但 $bi$ 有 $m$ 个选择，所以 $m*f(n-1,m)$ 。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
//=n个不同的球分成r堆的种数*r
//第二类斯特林数
int n,m;
//一定注意球和盒数量相同才是一种方案
int f1(int n,int m)
{
if(m<=0||n<m)return 0;
else if(n==m)return 1;
else return f1(n-1,m-1)+f1(n-1,m)*m;
}
//排列->阶乘
int f2(int m)
{
if(m==1)return 1;
else return m*f2(m-1);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//球的组合+盒的排列
cin>>n>>m;
cout<<f1(n,m)*f2(m);
return 0;
}
