D-医生
二进制、dfs、’状压’
思路：
首先能想到将 $01$ 字符串处理为对应的 $10$ 进制来做，但是没想到用 $dfs$ 来实现，反而用了更麻烦的哈希去做。
步骤：
- 将每个病人和药处理
string s;
cin>>s;
int k=0;
for(char c:s)k=(k<<1)|c-'0';
a[i]=k;
- $dfs$ 应该有三种状态，病人当前状态，当前用药，当前用药数量
代码：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e4+10;
int n,m,k,a[N],b[N];
string s;
int ans=0x3f3f3f3f;
void dfs(int u,int st,int cnt)
{
if(st==(1<<m)-1)//一共有m位状态，从0到m位都为1用2^m-1
{
ans=min(ans,cnt);
return;
}
if(u==k)return;
dfs(u+1,st,cnt);
dfs(u+1,st|b[u],cnt+1);
}
signed main()
{
ios
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>s;
int z=0;
for(char c:s)z=(z*2)+(!(c-'0'));//for(auto c:s)z=z*2+(!(c-'0'));//这样患病的，0即为患病，1是正常。
a[i]=z;
}
cin>>k;
for(int i=0;i<k;i++)
{
cin>>s;
int z=0;
for(char c:s)z=(z*2)+((c-'0'));
b[i]=z;
}
for(int i=0;i<n;i++)
{
ans=50;
dfs(0,a[i],0);
if(ans==50)ans=-1;
cout<<ans<<endl;
}
return 0;
}
过了80的代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int>a(n);
string s;
for(int i=0;i<n;i++)
{
cin>>s;
int k=0;
for(char c:s)k=(k<<1)|(c-'0');
a[i]=k;
}
int k;
cin>>k;
vector<int>b(n);
for(int i=0;i<k;i++)
{
cin>>s;
int kk=0;
for(char c:s)kk=(kk<<1)|(c-'0');
b[i]=kk;
}
int sn=0;
if(m<=20)sn=(1<<m);
vector<int>c((m<=20)?(1<<m):0,k+1);
for(int i=0;i<(1<<k);i++)
{
int kk=0,cnt=0;
for(int j=0;j<k;j++)
{
if(i&(1<<j))
{
kk|=b[j];
cnt++;
}
}
if(m<=20)
if(cnt<c[i])c[i]=cnt;
}
unordered_map<int,int>mp;
for(int x:a)
{
if(mp.find(x)!=mp.end())continue;
int res=k+1;
for(int i=0;i<(1<<k);i++)
{
int kk=0,cnt=0;
for(int j=0;j<k;j++)
{
if(i&(1<<j))
{
kk|=b[j];
cnt++;
}
if((kk&x)==x)
if(cnt<res)res=cnt;
}
}
mp[x]=(res<=k)?res:-1;
}
for(int x:a)cout<<mp[x]<<'\n';
return 0;
}
E、F-降温
边界类贪心
分析:
分别去最大化寒潮次数和最小化寒潮次数的去处理每天的气温，实际是只能处理未知值。
代码：
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef pair<int,int>P;
const int N=1e5+10,q=-999;
int a[N],b[N];
int main()
{
ios
int n,x;
cin>>n>>x;
//vector<int>a(n),b(n);
//for(int w:a)cin>>w;
//memset(b,sizeof a,)
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
//是基于原始的x数组，然后a是最大化次数，b最小化次数
if(a[0]==q)
{
a[0]=50;
b[0]=-50;
}
int res=0,ans=0;
for(int i=1;i<n;i++)
{
if(a[i]==q)
{
if(a[i-1]-x<-50)a[i]=50;
else a[i]=a[i-1]-x;
b[i]=max(-50,b[i-1]-x+1);
}
if(a[i-1]-a[i]>=x)res++;
if(b[i-1]-b[i]>=x)ans++;
}
cout<<res<<' '<<ans;
return 0;
}
小白月赛C-冰冰的异或
打表找规律
分析：
应该多打表的，除去特判，分好几组来找规律。
代码：
//MEX是最小的未出现的值
//打表找规律，除了1和2，刚好是2的幂次，这个[1,n]的i^j的结论记住
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
void solve()
{
//n=1时，1^1=0,只能是1
//n=2时，a^b=b^a,1^2=3,所以1
//n=3,n=4,……n=7,答案都是8
//n=8,……15答案都是16，所以刚好是>=n的2的幂次
int n;
cin>>n;
if(n<=2)cout<<1<<endl;
else
{
int k=1;
while(true)
{
if(k>=n)
{
cout<<k<<endl;
return;
}
k<<=1;
}
}
}
signed main()
{
ios
int t;
cin>>t;
while(t--)solve();
return 0;
}
D-冰冰的分界线
分析：
这道题的核心在于计算二维平面上不同分界线的数量。题目描述了如何定义这些分界线，并要求我们找出这些分界线中唯一的情况。以下是对题意和代码的详细讲解。
题目意思
- 平面上有多个朋友的坐标，这些朋友邀请
fresh_boy去他们的位置，而fresh_boy自己也有一个坐标。 - 分界线定义：对于任意两个朋友
A和B，fresh_boy可以通过一条直线（称为分界线）将这两个点分开。如果fresh_boy到A的距离等于到B的距离，则fresh_boy与A和B之间的点的集合会形成一条分界线。 - 目标：找到不同的分界线数量。两个分界线相同当且仅当它们完全重合。
解题思路
- 计算每对朋友的分界线：对于每一对朋友
A和B，可以通过几何方法计算分界线的斜率和截距。这里的分界线是fresh_boy和A、B的中垂线。 - 唯一标识每条分界线：使用斜率
k和截距b来唯一标识分界线(k, b)。如果两条分界线的k和b相同，则认为它们是同一条分界线。 - 结果：统计不同
(k, b)对的数量，即不同分界线的数量。
代码讲解
#include <bits/stdc++.h>
int T = 1; using ll = long long;
const int mod = 1e9+7;
using namespace std;
const int N = 1003;
int n;
ll x[N],y[N];
T是测试用例的数量。mod是一个大质数，用于实现模运算，防止整数溢出。N是数组x和y的最大大小，即最多支持 1000 个朋友的坐标。x和y是分别存储每个朋友的横坐标和纵坐标的数组。
ll qmi(ll a, ll b, ll p) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans % p;
}
qmi是快速幂算法，用于计算(a^b) % p。- 在代码中，这个函数用于计算模逆（即
a^(p-2) % p），因为在模p下，a^(p-2)是a的逆元，可以用来避免除法。
pair<ll,ll> uuz(ll x1, ll y1, ll x2, ll y2) {
ll k;
if(y1 == y2) k = 1e18; // 特判斜率不存在的情况
else if(x1 == x2) k = 0;
else k = (x1 - x2) * qmi(y2 - y1, mod - 2, mod) % mod;
ll b = (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1) * qmi(2 * (y2 - y1), mod - 2, mod) % mod;
return {k, b};
}
uuz函数用于计算给定两点A(x1, y1)和B(x2, y2)的分界线参数(k, b)，其中k是斜率，b是截距。- 特殊情况：
- 如果
y1 == y2，则两点在同一水平线上，这样的直线无法定义有效的斜率，因此k被设为1e18（一个很大的值）表示特殊情况。 - 如果
x1 == x2，表示两点在同一垂直线上，这样的中垂线斜率为0。 -
其他情况使用
(x1 - x2) * qmi(y2 - y1, mod - 2, mod) % mod来计算k，模逆运算避免了除法。 -
截距
b的计算利用了中垂线的性质，表达式为(y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1) * qmi(2 * (y2 - y1), mod - 2, mod) % mod。
void sol() {
cin >> n;
for(int i = 1; i <= n; i++) { cin >> x[i]; }
for(int i = 1; i <= n; i++) { cin >> y[i]; }
map<pair<ll, ll>, int> mp;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
auto [k, b] = uuz(x[i], y[i], x[j], y[j]);
if(k == 1e18) mp[{k, x[i] + x[j]}]++;
else mp[{k, b}]++;
}
}
cout << mp.size() << '\n';
}
sol函数是解决每个测试用例的主函数。- 读取每个朋友的坐标并存储在
x和y数组中。 - 使用双重循环遍历每对朋友，计算他们的分界线参数
(k, b)。 map用于记录不同的(k, b)对，以统计不同分界线的数量。- 如果
k == 1e18，则这是一个特殊情况（水平线），用x[i] + x[j]作为唯一标识。 - 否则，将
(k, b)存入map中。 - 最后，输出
map.size()，即不同分界线的数量。
int main() {
cin >> T;
while(T--) { sol(); }
return 0;
}
main函数负责读取测试用例数量T，并执行每个测试用例的sol函数。
总结
- 这段代码通过双重循环和
map，利用几何性质计算并统计二维平面上不同分界线的数量。 - 通过模逆和特判斜率的处理，确保代码的鲁棒性和精度。
这行代码的目的是计算两点(x1, y1)和(x2, y2)所构成的直线的斜率k，并利用模逆运算来避免除法，从而保证计算结果在模数mod的范围内。由于直接除法在模运算下不适用，我们需要通过乘以模逆来实现。
下面我们一步步解释这行代码，并通过一个例子来说明。
1. 背景知识
在平面几何中，给定两个点 (x1, y1) 和 (x2, y2)，它们构成的直线的斜率 k 计算公式为：
[
k = \frac{y2 - y1}{x2 - x1}
]
2. 使用模逆运算的原因
由于程序在很多地方使用 mod（通常是大质数，比如 1e9+7）来防止整数溢出，因此我们需要在模 mod 的范围内计算斜率。
除法在模运算中是不能直接进行的，因此在这里采用模逆运算。根据费马小定理，如果 p 是质数，那么对于任意不为 0 的整数 a，都有：
$[
a^{p-1} \equiv 1 \ (\text{mod } p)
]$
因此，a 的模逆可以表示为 a^(p-2) % p。在这里，我们要将分母 y2 - y1 的模逆算出，然后用乘法代替除法。
3. 代码解释
k = (x1 - x2) * qmi(y2 - y1, mod - 2, mod) % mod;
这个表达式的含义是：
- 先计算 (x1 - x2)，这是斜率的分子。
- 然后使用 qmi(y2 - y1, mod - 2, mod) 来计算 (y2 - y1) 的模逆。qmi 函数的作用是计算 (y2 - y1)^(mod-2) % mod，从而得到 y2 - y1 在模 mod 下的模逆。
- 最后，将这两个值相乘，再对 mod 取模，得到最终的 k 值。
4. 例子说明
假设我们有两个点 (x1, y1) = (2, 3) 和 (x2, y2) = (5, 7)，并且 mod = 1e9+7。
-
计算分子：
x1 - x2 = 2 - 5 = -3，为了避免负数影响，我们可以先将其转换为正数形式，即-3 % mod = 1e9+4。 -
计算分母的模逆：
y2 - y1 = 7 - 3 = 4。- 接下来，我们需要计算
4的模逆，即4^(mod-2) % mod。 -
假设
mod = 1e9+7，则我们计算4^(1e9+5) % (1e9+7)，这就是qmi(4, mod-2, mod)的作用。 -
计算斜率
k： - 假设
4^(mod-2) % mod的计算结果是v（这是模逆）。 - 然后，
k = (1e9+4) * v % mod，这就是斜率的值。
小结
通过这种方式，我们在不使用除法的情况下计算了模数下的斜率 k。这在处理大数和防止溢出时非常有效，也符合题目对精度和数据范围的要求。
这段代码的目的是计算两点 (x1, y1) 和 (x2, y2) 的中垂线的截距 b。其中中垂线的定义是通过这两点的中点且垂直于这两点的连线的直线。因此，b 是这条中垂线在模 mod 下的截距。
背景知识
给定两个点 (x1, y1) 和 (x2, y2)，中垂线是与两点连线垂直且过这两点的中点的直线。
1. 中点坐标
首先，(x1, y1) 和 (x2, y2) 的中点坐标为：
$[
\left( \frac{x1 + x2}{2}, \frac{y1 + y2}{2} \right)
]$
2. 垂直于连线的斜率
两点 (x1, y1) 和 (x2, y2) 构成的直线的斜率 k 是：
$[
k = \frac{y2 - y1}{x2 - x1}
]$
而中垂线与这条直线垂直，因此中垂线的斜率为 -1/k，即：
$[
\text{中垂线的斜率} = -\frac{x2 - x1}{y2 - y1}
]$
（如果 y2 = y1，说明这条直线是水平的，此时中垂线是垂直的，处理稍有不同。）
3. 使用中点和斜率求截距
中垂线经过中点 ( (x1 + x2) / 2, (y1 + y2) / 2 )，设中垂线的方程为：
$[
y = -\frac{x2 - x1}{y2 - y1} \cdot x + b
]$
将中点代入方程求 b（截距）：
$[
\frac{y1 + y2}{2} = -\frac{x2 - x1}{y2 - y1} \cdot \frac{x1 + x2}{2} + b
]$
整理得：
$[
b = \frac{y1^2 - y2^2 + x1^2 - x2^2}{2(y2 - y1)}
]$
代码解释
现在我们来看代码中如何实现上述计算：
ll b = (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1) * qmi(2 * (y2 - y1), mod - 2, mod) % mod;
y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1：这部分相当于分子y1^2 - y2^2 + x1^2 - x2^2。qmi(2 * (y2 - y1), mod - 2, mod)：这是分母2(y2 - y1)的模逆。由于我们无法直接进行除法，因此使用快速幂函数qmi来计算模逆，以避免除法。
例子说明
假设我们有两个点 (x1, y1) = (1, 3) 和 (x2, y2) = (4, 7)，且 mod = 1e9+7。
-
计算分子：
$[ y2^2 - y1^2 + x2^2 - x1^2 = 7^2 - 3^2 + 4^2 - 1^2 = 49 - 9 + 16 - 1 = 55 ]$ -
计算分母的模逆：
- 分母是
2 * (y2 - y1) = 2 * (7 - 3) = 8。 -
使用快速幂计算
8^(mod-2) % mod，得到8的模逆v（假设结果为v）。 -
计算截距
b： - 通过
(分子 * 分母的模逆) % mod计算最终的b值：
$[ b = (55 * v) \% mod ]$
这样我们就得到了中垂线在模 mod 下的截距 b。
