2024.6.9 【最后一天!!! 年年今日，灯明如昼。原火不灭，愿人依旧。】
Sunday 五月初四
A. 挖掘机
题目描述
今天，丧尸czy开着挖掘机去上学(……)。但是他发现他的mz满天下，所以一路上他碰到了好多他的mz。一开始他以1km/min的速度(=60km/h……)开着挖掘机前进。他发现他只会在恰好到达某一时刻或者到达某个距离遇到mz。每次遇到mz，czy都会毫不犹豫的把她们顺路捎走(_)。但是他实在是太虚了，以至于当有i个mz时他的速度下降到1/(i+1)。具体说，一开始czy以1km/min速度前进，有1个mz的时候速度变为1/2 km/min，有2个时变为1/3 km/min……以此类推。现在问题来了，给出每个mz在何时出现，请你算出czy到学校要多久。
输入输出格式
输入第一行2个数n，m，分别表示mz数和czy与学校的距离(km)
接下来2到n+1行由字符串与数字构成
Dist x表示在距离达到x km时出现一个mz
Time x表示在时间达到x min时出现一个mz
输出一个整数，表示到达学校的时间。如果不能整除，直接输出整数部分即可。
样例输入
2 20
Time 3
Dist 10
样例输出
47
数据范围
对于30%数据，n,m<=50
对于50%数据，n,m<=2000
对于100%数据，n,m<=200000,x<=10^9,保证输入的数字都是整数
//2024.6.9
//by white_ice
#include<bits/stdc++.h>
#include"fopen.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 200005;
itn st[oo],sp[oo];
int top1,top2;
int n,m;
char c[5];
signed main(){
fre();
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m ;
for (int x,i=1;i<=n;i++){
cin >> c;
cin >> x;
if (c[0]=='T')
st[++top1] = x;
else sp[++top2] = x;
}
sp[++top2] =m;
sort(st+1,st+top1+1);
sort(sp+1,sp+top2+1);
double out=0,p=0;
int cnt=1,ned=1;
//cout << top1 << top2;
for (itn i=1;i<=top2;i++){
while(ned<=top1){
if (out+cnt*(sp[i]-p)<=st[ned])
break;
p += (st[ned]-out)/cnt;
out=st[ned];
cnt++;
ned++;
}
out+=cnt*(sp[i]-p);
p=sp[i];
cnt++;
}
cout << (int)out;
return 0;
}
贪心加模拟，
就嗯模就行呗
B. 黑红树
题目背景
Mz们在czy的生日送他一个黑红树种子……czy种下种子，结果种子很快就长得飞快，它的枝干伸入空中看不见了……
题目描述
Czy发现黑红树具有一些独特的性质。
1、 这是二叉树，除根节点外每个节点都有红与黑之间的一种颜色。
2、 每个节点的两个儿子节点都被染成恰好一个红色一个黑色。
3、 这棵树你是望不到头的（树的深度可以到无限大）
4、 黑红树上的高度这样定义:h(根节点)=0，h[son]=h[father]+1。
Czy想从树根顺着树往上爬。他有p/q的概率到达红色的儿子节点，有1-p/q的概率到达黑色节点。但是他知道如果自己经过的路径是不平衡的，他会马上摔下来。一条红黑树上的链是不平衡的，当且仅当红色节点与黑色节点的个数之差大于1。
现在他想知道他刚好在高度为h的地方摔下来的概率的精确值a/b，gcd(a,b)=0。那可能很大，所以他只要知道a,b对K取模的结果就可以了。另外，czy对输入数据加密：第i个询问Qi真正大小将是给定的Q减上一个询问的第一个值a%K.
输入输出格式
第一行四个数p,q,T,k，表示走红色节点概率是p/q，以下T组询问，答案对K取模。
接下来T行，每行一个数 Q,表示czy想知道刚好在高度Q掉下来的概率（已加密）
输出T行，每行两个整数，表示要求的概率a/b中a%K和b%K的精确值。如果这个概率就是0或1，直接输出0 0或1 1（中间有空格）。
样例输入1
2 3 2 100
1
2
样例输入2
2 3 2 20
4
6
样例输出1
0 0
5 9
样例输出2
0 1
0 9
数据范围
对于30%数据,p,q<=5,T<=1000,K<=127,对于任意解密后的Q，有Q<=30
对于60%数据,p,q<=20,T<=100000,K<=65535,对于任意解密后的Q,有Q<=1000
对于100%数据,p,q<=100,T<=1000000, K<=1000000007,对于任意解密后的Q,有Q<=1000000 对于100%数据,有q>p,即0<= p/q<=1
//2024.6.9
//by white_ice
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define ll long long
constexpr int oo = 1000006;
ll p,q; ll t,k;
ll h1,h2; ll s1,s2;
ll h[oo]; ll f[oo];
ll a,b;
ll gcd(ll x,ll y){return (x%y)==0?y:gcd(y,x%y);}
int main(){
//fre();
cin >> p >> q >> t >> k;
// ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
h1 = 2*p*(q-p); h2 = q*q;
ll l = gcd(h1,h2);
h1 /= l; h2 /= l;
s1 = p*p*2+q*q-2*p*q; s2 = q*q;
l = gcd(s1,s2);
s1 /= l; s2 /= l;
h[0] = 1; f[0] = 1;
for(int i=1;i<=500000;i++)
h[i] = (h[i-1]*h1) % k,
f[i] = (f[i-1]*h2) % k;
ll x;
while(t--){
cin >> x;
x -= a;
if(x==0||(x&1)){
cout << "0 0\n";
a = 0;
continue;
}
else{
x /= 2;
a = (h[x-1]*s1)%k;
b = (f[x-1]*s2)%k;
cout << a%k << ' ' << b%k << '\n';
}
}
return 0;
}
概率DP，
不会
挺直白的DP，写就完了。
C. 藏宝图
题目背景
Czy爬上黑红树，到达了一个奇怪的地方……
题目描述
Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图刚好又是一颗树的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。
输入输出格式
输入数据第一行一个数T,表示T组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。
接下来n行,每行n个数，表示两两节点之间的距离。
输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。
样例输入
2
3
0 7 9
7 0 2
9 2 0
3
0 2 7
2 0 9
7 9 0
样例输出
Yes
1
Yes
3
样例解释:
第一棵树的形状是1--2--3。1、2之间的边权是7，2、3之间是2。
第二棵树的形状是2--1--3。2、1之间的边权是2，1、3之间是7。
数据范围
对于30%数据，n<=50,1<=树上的边的长度<=10^9。
对于50%数据，n<=600。
对于100%数据，1<=n<=2500,除30%小数据外任意0<=dist[i][j]<=10^9,T<=5
//2024.6.9
//by white_ice
#include <bits/stdc++.h>
#include"fopen.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 2503;
//========================================================================
int n;
//========================================================================
int d[oo],low[oo];
int dis[oo][oo],das[oo][oo];
bool vis[oo];
//========================================================================
struct nod{int v,head,nxt,w;}st[oo<<1];
int top=0;
void add(int x,int to,int w){st[++top].v=to;st[top].w=w;st[top].nxt=st[x].head;st[x].head=top;}
//========================================================================
void init(int n){
top=0;
memset(das,0,sizeof(das));
memset(d,0x7f7f,sizeof(d));
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(st,0,sizeof(st));
for (int i=1;i<=n;i++)
st[i].head = 0;
}
//========================================================================
void dfs(int x,int fa,int now){
for(int i=st[x].head;i;i=st[i].nxt){
int fom=st[i].v;
if(fa==fom)
continue;
das[now][fom]=das[now][x]+st[i].w;
dfs(fom,x,now);
}
}
//========================================================================
signed main(){
fre();
//========================================================================
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
//========================================================================
int t;
cin>>t;
while(t--){
cin>>n;
bool flag = 1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin >> x;
dis[i][j]=x;
if(i==j&&x!=0)
flag=0;
}
}
//========================================================================
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
if(dis[i][j]!=dis[j][i]){
flag=false;
break;
}
}
}
//========================================================================
if(flag){
init(n);
//========================================================================
d[1]=0;
for(int i=1;i<=n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&(x==0||d[j]<d[x]))
x=j;
}
vis[x]=1;
for(int y=1;y<=n;y++){
if(!vis[y]&&dis[x][y]<d[y]){
low[y]=x;
d[y]=dis[x][y];
}
}
}
//========================================================================
for(int i=2;i<=n;i++){
add(i,low[i],d[i]);
add(low[i],i,d[i]);
}
//========================================================================
for(int i=1;i<=n;i++)
dfs(i,-1,i);
//========================================================================
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]!=das[i][j]){
flag=false;
}
}
}
}
//========================================================================
if (!flag) cout << "No" << endl;
else{
double maxx=-1;
int num;
double tot=0;
for(int i=1;i<=n;i++){
double sum=0;
tot=0;
for(int j=st[i].head;j;j=st[j].nxt){
sum+=st[j].w;
tot++;
}
if(tot)
sum/=(tot*1.0);
if(sum>maxx){
maxx=sum;
num=i;
}
}
cout << "Yes"<< '\n' << num << '\n';
}
}
//========================================================================
return 0;
}
原题codeforces472D，题目强化版。给一个图中的点两两之间的距离，求是不是一棵树。如果是树求相连的边权平均值最大的那个点。
先不管它是不是树，跑最小生成树，算出在MST条件下的dist2数组。如果它是树，显然dist和dist2完全一样。如果不一样，这个图一定不是树。另外Kruskal会被卡。
第二问在第一问的条件下怎么搞都行了
Prim写了半天写的想si
D. 天神下凡
题目背景
Czy找到宝藏获得屠龙宝刀和神秘秘籍！现在他要去找经常ntr他的Jmars报仇……
题目描述
Czy学会了一招“堕天一击”，他对一个地点发动堕天一击，地面上就会留下一个很大的圆坑。圆坑的周围一圈能量太过庞大，因此无法通过。所以每次czy发动技能都会把地面分割。Jmars拥有好大好大的土地，几十眼都望不到头，所以可以假设土地的大小是无限大。现在czy对他发动了猛烈的攻击，他想知道在泽宇攻击之后他的土地被切成几份了?
Czy毕竟很虚，因此圆心都在x坐标轴上。另外，保证所有圆两两之间不会相交。
输入输出格式
输入第一行为整数n，表示czy放了n次堕天一击。
接下来n行，每行两个整数x[i]，r[i]。表示在坐标（x[i] , 0）放了一次堕天一击，半径为r[i]。
输出一行，表示地面被分割成几块。
样例输入
4
7 5
-9 11
11 9
0 20
样例输出
6
数据范围
对于30%数据，n<=5000
对于100%数据，1<=n<=300000,-109<=x[i]<=109,1<=r[i]<=10^9.
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int _ =320031;
struct sta{
LL ld,rd;
}stk[_];
int n,top;
struct cir{
LL o,r;
}c[_];
bool operator == (cir a,cir b){
return (a.o==b.o)&(a.r==b.r);
}
bool cmp(cir a,cir b){
if(a.o-a.r!=b.o-b.r){
return a.o-a.r<b.o-b.r;
}
return a.o+a.r>b.o+b.r;
}
int main(){
freopen("god.in","r",stdin);
freopen("god.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(register int i=1;i<=n;++i){
cin>>c[i].o>>c[i].r;
}
sort(c+1,c+n+1,cmp);
register int ans=1;
for(register int i=1;i<=n;++i){
if(c[i]==c[i-1])continue;
++ans;
register LL ld=c[i].o-c[i].r,rd=c[i].o+c[i].r;
while(top){
if(stk[top].ld==ld&&stk[top].rd==rd){
top--;
++ans;
break;
}
if(stk[top].ld==ld){
stk[top].ld=rd;
break;
}
if(ld>=stk[top].rd||(ld>stk[top].ld&&rd<stk[top].rd)){--top;}
else break;
}
stk[++top].ld=ld,stk[top].rd=rd;
}
cout<<ans;
}
//代码转自https://blog.csdn.net/JH_2002/article/details/80636247
解释一下题意，
其实就是一条线上，给定n个x，r
求这些个⚪，
将平面分割成了多少块。
一般来说一个圆就是一个贡献
如果一个圆被几个圆内切了，也就是说，从一个范围[l,r]的圆说,如果有若干个[l,p1],[p1,p2],....,[pn,r]的圆，那么会产生额外的贡献。
我们的目标是找到额外的贡献与不重叠的圆的数量
之后用栈做维护就可以了。
标签：oo,czy,2024.6,int,ll,样例,long From： https://www.cnblogs.com/white-ice/p/18239795