1.27补题 回训练营
E 智乃的小球
题目描述
在一条无限长的水平直线上，有 n 个小球，每个小球的质量相同，体积可以忽略不计。这些小球初始时位于直线上的不同位置，并且每个小球有一个初始速度，速度为 -1 m/s 或 1 m/s。速度为 -1 m/s 表示小球向左运动，速度为 1 m/s 表示小球向右运动。
当两个小球相向而行并发生碰撞时，它们会发生完全弹性碰撞，即交换速度。现在，你需要编写一个程序来判断，在足够长的时间后，是否会发生第 k 对小球的碰撞，以及如果会发生，碰撞将在何时发生。
输入描述
第一行包含两个正整数 n 和 k，分别表示小球的个数和需要判断的第 k 对碰撞。 接下来 n 行，每行包含两个整数 pi 和 vi，分别表示第 i 个小球的初始位置和速度。
输出描述
如果会发生第 k 对碰撞，输出 “Yes”，并在下一行输出发生碰撞的时间，保留六位小数；如果不会发生第 k 对碰撞，输出 “No”。
示例输入
3 2
0 1
2 -1
4 1
示例输出
Yes
2.000000
解释：在这个例子中，第 1 和第 2 个小球在 t=1 时发生碰撞，第 2 和第 3 个小球在 t=2 时发生碰撞。因此，第 2 对碰撞发生的时间是 2 秒。
注意：由于实数的计算存在误差，当你的答案与标准答案的差的绝对值除以标准答案的绝对值的最大值不超过 10^-6 时，你的答案将被视为正确。
思路
把碰撞当相遇！！！
-
输入处理：读取小球的个数 n 和需要判断的碰撞次数 k，然后读取每个小球的初始位置和速度。
-
分类小球：根据小球的初始速度，将小球分为两组，一组向右运动，一组向左运动。
-
计算碰撞次数：对于每个向右运动的小球，计算它会在何时与每个向左运动的小球碰撞。我们可以通过比较它们的位置和速度来确定碰撞时间。
-
二分查找：由于碰撞时间随时间增加而单调增加，我们可以使用二分查找来确定第 k 次碰撞发生的时间。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a, b;
vector<int> c, d;
signed main()
{
cin >> a >> b;
for (int i = 0; i < a; i++)
{
int e, f;
cin >> e >> f;
if (f == 1)
{
c.push_back(e);
}
else
{
d.push_back(e);
}
}
sort(c.begin(), c.end());
sort(d.begin(), d.end());
int g = 0;
for (int q : c)
{
auto it = upper_bound(d.begin(), d.end(), q);
g += d.end() - it;
}
if (g < b)
{
cout << "No" << "\n";
return 0;
}
double l = 0, h = 1e17;
double m;
while (h - l > 1e-7)
{
m = (l + h) / 2;
int cnt = 0;
for (int q : c)
{
double qq = q + 2 * m;
auto ww = upper_bound(d.begin(), d.end(), qq);
cnt += ww - lower_bound(d.begin(), d.end(), q + 1);
}
if (cnt >= b)
{
h = m;
}
else
{
l = m;
}
}
cout << "Yes" << "\n";
cout << fixed << setprecision(6) << h << "\n";
return 0;
}
G 智乃与模数
题目描述
给定一个正整数 n，对于所有不大于 n 的正整数 i，计算 n 对 i 取余的结果，并将这些结果降序排序形成一个新的序列 a。现在，你需要计算这个序列 a 中前 k 项的和。
输入格式
输入包含一行，有两个正整数 n 和 k，其中 1 ≤ k ≤ n ≤ 10^9。
输出格式
输出一个整数，表示序列 a 中前 k 项的和。
示例输入
10 5
示例输出
12
解释： 当 n = 10 时，计算 n 对所有不大于 10 的正整数取余的结果，并降序排序得到的序列为 {4, 3, 2, 2, 1, 1, 0, 0, 0, 0}。序列中前 5 项的和为 4 + 3 + 2 + 2 + 1 = 12。
注意： 由于 n 的范围可能非常大，直接计算所有取余结果并排序可能会导致时间复杂度过高，因此需要考虑更高效的算法来解决这个问题。
思路
代码
#include <iostream>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
int n, k;
void solve() {
cin >> n >> k;
int l = 0, r = 1e9 + 1, kc = 0, val = 0;
while (l <= r) {
int m = (l + r) >> 1;
int cnt = 0;
for (int i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
int a = n - i * (n / i);
if (a < m) continue;
cnt += min(j - i + 1, (a - m) / (n / i) + 1);
}
if (cnt >= k) l = m + 1;
else {
kc = cnt;
val = m;
r = m - 1;
}
}
int ans = (k - kc) * (val - 1);
for (int i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
int a = n - i * (n / i);
int p = n / i;
if (a < val) continue;
int len = min((a - val) / p + 1, j - i + 1);
ans += (2 * a - p * (len - 1)) * len / 2;
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
K 智乃的逆序数
思路
代码
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<pair<int, int>> a;
vector<vector<int>> v;
int calc()
{
int ret = 0;
for (int i = 0; i < a.size(); ++i)
{
for (int j = i + 1; j < a.size(); ++j)
{
if (a[i] > a[j])++ret;
}
}
return ret;
}
void bsort()
{
for (int i = 0; i < a.size(); ++i)
{
for (int j = 0; j + 1 < a.size(); ++j)
{
if (a[j].first == a[j + 1].first)continue;
if (k > 0 && a[j].second < a[j + 1].second)
{
swap(a[j], a[j + 1]);
--k;
}
}
}
}
int main()
{
scanf("%d %d", &n, &k);
v.resize(n);
for (int i = 0; i < n; ++i)
{
int l;
scanf("%d", &l);
for (int j = 0; j < l; ++j)
{
int x;
scanf("%d", &x);
v[i].push_back(x);
}
}
sort(v.begin(), v.end(), [](const vector<int> &A, const vector<int> &B)
{
return A[0] < B[0];
});
for (int i = 0; i < n; ++i)
{
for (auto &j: v[i])
{
a.emplace_back(i, j);
}
}
k -= calc();
if (k < 0)
{
printf("No");
return 0;
}
bsort();
if (k > 0)
{
printf("No");
return 0;
}
printf("Yes\n");
for (int i = 0; i < a.size(); ++i)
{
printf("%d%c", a[i].second, " \n"[i + 1 == a.size()]);
}
return 0;
}
D 智乃的Notepad(Hard version)
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
示例1
输入
3 3 nowcoder nowdays now 1 3 1 2 3 3
3 3 nowcoder nowdays now 1 3 1 2 3 3
输出
16 16 3
16 16 3
示例2
输入
4 1 nowcoder nowdays days coder 1 4
4 1 nowcoder nowdays days coder 1 4
输出
34
34
思路
代码
#include<bits/stdc++.h>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ld eps=1e-8;
const int INF=0x3f3f3f3f;
const ll INFF=0x3f3f3f3f3f3f3f3f;
#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif
const int N=100005,M=1000006;
struct Node
{
int l,r;
int maxi;
}tr[4*N];
string s[N];
void pushup(Node &root,Node &left,Node &right)//Todo
{
root.maxi=max(left.maxi,right.maxi);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)//Todo
{
tr[u].maxi=s[l].size();
}
else
{
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int c)
{
if(tr[u].l>=l&&tr[u].r<=r)//Todo
{
tr[u].maxi+=c;
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,c);
if(r>mid) modify(u<<1|1,l,r,c);
pushup(u);
}
Node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)//Todo
{
return tr[u];
}
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else
{
Node res;
Node left=query(u<<1,l,r);
Node right=query(u<<1|1,l,r);
pushup(res,left,right);
return res;
}
}
typedef unsigned long long ull;
int qry_max[N];
int qry_num[N];
tuple<int,int,int> q[N];
int tr2[M];
int lowbit(int x)
{
return x&-x;
}
int query(int x)
{
int res=0;
while(x)
{
res+=tr2[x];
x-=lowbit(x);
}
return res;
}
void add(int x,int c)
{
while(x<M)
{
tr2[x]+=c;
x+=lowbit(x);
}
return ;
}
const int P=131;
int pos[M];
const ll mod=1e13+7;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
vector<pair<ull,char>> all;
for(int i=1;i<=n;i++)
{
cin>>s[i];
ull hs=0;
for(int j=0;j<s[i].size();j++)
{
hs*=P;
hs+=s[i][j]+j*100;
all.push_back({hs,s[i][j]});
}
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
debug(l,r);
q[i]={r,l,i};
qry_max[i]=query(1,l,r).maxi;
}
sort(q+1,q+m+1);
int idx=0;
for(int i=1;i<=m;i++)
{
auto [r,l,id]=q[i];
while(idx<r)
{
idx++;
ll hs=0;
for(int i=0;i<s[idx].size();i++)
{
hs*=P;
hs+=s[idx][i]+i*100;
int x=(lower_bound(all.begin(),all.end(),(pair<ull,char>){hs,s[idx][i]})-all.begin())+1;
if(pos[x])
{
add(pos[x],-1);
}
pos[x]=idx;
add(pos[x],1);
}
}
qry_num[id]=query(r)-query(l-1);
}
for(int i=1;i<=m;i++)
{
debug(qry_num[i],qry_max[i]);
int res=qry_num[i]*2-qry_max[i];
printf("%d\n",res);
}
}H 智乃与黑白树
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
示例1
输入
5 bwbwb 1 2 2 5 4 1 3 1
5 bwbwb 1 2 2 5 4 1 3 1
输出
3 1 6 0 0 4 0 6
3 1 6 0 0 4 0 6
思路
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct dp_node
{
long long dpb, dpw, sb, sw, val;
};
dp_node dp[MAXN];
void init_b(int root)
{
memset(&dp[root], 0, sizeof(dp_node));
dp[root].sb = 1;
}
void init_w(int root)
{
memset(&dp[root], 0, sizeof(dp_node));
dp[root].sw = 1;
}
void link(int root1, int root2)
{
dp[root1].val += dp[root2].val +
dp[root1].dpb * dp[root2].sw +
dp[root1].dpw * dp[root2].sb +
dp[root1].sw * (dp[root2].dpb + dp[root2].sb) +
dp[root1].sb * (dp[root2].dpw + dp[root2].sw);
dp[root1].dpw += dp[root2].dpw + dp[root2].sw;
dp[root1].dpb += dp[root2].dpb + dp[root2].sb;
dp[root1].sb += dp[root2].sb;
dp[root1].sw += dp[root2].sw;
}
void cut(int root1, int root2)
{
dp[root1].sw -= dp[root2].sw;
dp[root1].sb -= dp[root2].sb;
dp[root1].dpb -= dp[root2].dpb + dp[root2].sb;
dp[root1].dpw -= dp[root2].dpw + dp[root2].sw;
dp[root1].val -= dp[root2].val +
dp[root1].dpb * dp[root2].sw +
dp[root1].dpw * dp[root2].sb +
dp[root1].sw * (dp[root2].dpb + dp[root2].sb) +
dp[root1].sb * (dp[root2].dpw + dp[root2].sw);
}
vector<int> G[MAXN];
map<pair<int, int>, int> id;
int n;
pair<long long, long long> ans[MAXN];
char s[MAXN];
void dfs(int x, int fa)
{
if (s[x] == 'b')init_b(x);
else init_w(x);
for (auto &i: G[x])
{
if (i == fa)continue;
dfs(i, x);
link(x, i);
}
}
void dfs2(int x, int fa)
{
for (auto &i: G[x])
{
if (i == fa)continue;
cut(x, i);
if (id.find(make_pair(x, i)) != id.end())
{
ans[id[make_pair(x, i)]] = make_pair(dp[x].val, dp[i].val);
}
if (id.find(make_pair(i, x)) != id.end())
{
ans[id[make_pair(i, x)]] = make_pair(dp[i].val, dp[x].val);
}
link(i, x);
dfs2(i, x);
cut(i, x);
link(x, i);
}
}
int main()
{
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i < n; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
id[make_pair(u, v)] = i;
}
dfs(1, 0);
dfs2(1, 0);
for (int i = 1; i < n; ++i)
{
printf("%lld %lld\n", ans[i].first, ans[i].second);
}
return 0;
}
J 智乃画二叉树
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
输入描述
输出描述
示例1
输入
6 3 6 5 -1 -1 -1 2 1 3 -1 -1 -1 -1
6 3 6 5 -1 -1 -1 2 1 3 -1 -1 -1 -1
输出
************************ * __ * * /4 \ * * \__/ * * / \ * * / \ * * / \ * * __/ \__ * * /1 \ /3 \ * * \__/ \__/ * * __/ \__ \__ * */6 \ /5 \ /2 \* *\__/ \__/ \__/* ************************
************************ * __ * * /4 \ * * \__/ * * / \ * * / \ * * / \ * * __/ \__ * * /1 \ /3 \ * * \__/ \__/ * * __/ \__ \__ * */6 \ /5 \ /2 \* *\__/ \__/ \__/* ************************
思路
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3010;
char g[N][N];
int l[N],r[N];
int edge[110];
void solved(){
int n,k;
cin>>n>>k;
memset(g,' ',sizeof g);
int root=-1;
map<int,int>mp;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
l[i]=a;
r[i]=b;
mp[a]=mp[b]=1;
}
for(int i=1;i<=n;i++){
if(!mp[i]){
root=i;
break;
}
}
edge[0]=1;
for(int i=1,dd=3;i<=9;i++){
edge[i]=edge[i-1]+dd;
dd*=2;
}
int nn=1000,mm=1000;
auto drawNode=[&](int x,int y,int num){
g[x-1][y]=g[x-1][y+1]='_';
g[x][y-1]='/';
if(num<10)g[x][y]=num+'0';
else g[x][y+1]='0'+num%10,g[x][y]='0'+num/10;
g[x][y+2]='\\';
g[x+1][y-1]='\\';
g[x+1][y+2]='/';
g[x+1][y]=g[x+1][y+1]='_';
};
auto dfs=[&](auto&self,int u,int x,int y,int depth)->void{
if(u==-1)return;
drawNode(x,y,u);
if(l[u]!=-1){
int xx=x+2,yy=y-1;
for(int kk=0;kk<edge[depth];kk++){
g[xx][yy]='/';
xx++,yy--;
}
self(self,l[u],xx,yy-1,depth-1);
}
if(r[u]!=-1){
int xx=x+2,yy=y+2;
for(int kk=0;kk<edge[depth];kk++){
g[xx][yy]='\\';
xx++,yy++;
}
self(self,r[u],xx,yy,depth-1);
}
};
dfs(dfs,root,1003,1003,k-2);
int left=0,right=0,up=0,down=0;
for(int i=0;i<N-1;i++){
bool ok=false;
for(int j=0;j<N-1;j++){
if(g[j][i+1]!=' '){
left=i;
ok=true;
break;
}
}
if(ok)break;
}
for(int i=N-1;i>=1;i--){
bool ok=false;
for(int j=0;j<N-1;j++){
if(g[j][i-1]!=' '){
right=i;
ok=true;
break;
}
}
if(ok)break;
}
for(int i=0;i<N-1;i++){
bool ok=false;
for(int j=0;j<N-1;j++){
if(g[i][j+1]!=' '){
up=i;
ok=true;
break;
}
}
if(ok)break;
}
for(int i=N-1;i>=1;i--){
bool ok=false;
for(int j=0;j<N-1;j++){
if(g[i][j-1]!=' '){
down=i;
ok=true;
break;
}
}
if(ok)break;
}
for(int i=1;i<N;i++)g[i][left]=g[i][right]=g[up-1][i]=g[down+1][i]='*';
// cout<<left<<' '<<right<<"\n";
for(int i=up-1;i<=down+1;i++){
for(int j=left;j<=right;j++){
cout<<g[i][j];
}
cout<<"\n";
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
int T=1;
// cin>>T;
while(T--)
solved();
return 0;
}
I 智乃的兔子跳
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
示例1
输入
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
输出
1 2
1 2
示例2
输入
5 10 80 17 73 1
5 10 80 17 73 1
输出
3 7
3 7
备注:
兔子一开始就在胡萝卜的坐标也能得到分数
思路
代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
const int MAXN = 1e5+10;
#define PII pair<int, int>
using namespace std;
void IOS(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int n;
int a[MAXN];
inline int randint(int min, int max){
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int>dis(min, max);
return dis(gen);
}
int maxcnt;
void solve(int &p, int &k){
int l = randint(1, n);
int r = randint(1, n);
while(l == r) r = randint(1, n);
int t = abs(a[l] - a[r]);
if(t == 1) return ;
for(int i = 2; i * i <= t; i++){
if(t % i == 0){
while(t % i == 0) t /= i;
int cnt = 0;
for(int j = 1; j <= n; j++){
if((a[l] - a[j]) % i == 0) cnt++;
}
if(cnt > maxcnt){
maxcnt = cnt;
p = a[l]%i;
k = i;
}
}
}
if(t != 1){
int cnt = 0;
for(int j = 1; j <= n; j++){
if((a[l] - a[j]) % t == 0) cnt++;
}
if(cnt > maxcnt){
maxcnt = cnt;
p = a[l]%t;
k = t;
}
}
}
signed main(){
IOS();
cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
int p = a[0], k = 2;
if(n == 1){
cout<<a[1]%2<<" "<<2<<endl;
return 0;
}
int T = 100;
while(T--){
solve(p, k);
}
cout<<p<<" "<<k<<endl;
}