1007
期望290
实际250
A大地魂力
奶牛贝西认为，要改变世界， 就必须吸收大地的力量，贝西把大地的力量称为魂力。要吸取大
地的魂力就需要在地上开出洞穴来。
大地可以看成一个数轴， 农夫约翰将不断地在大地上的选一个整数点来开一个洞穴，这个洞穴能
分别从他左右两边第一个已经开出的洞穴吸取大地之魂力， 吸取到的魂力数量等于对应洞穴的坐
标。如果某一个方向没有洞穴，那么这个洞穴就无法从这个方向吸收大地之魂力。约翰可以在一个
坐标点上开多个洞穴，每次吸收的大地之魂的数量都会累加。
现在按时间先后给出约翰的开洞的操作序列，约翰想知道他一共能吸收多少大地之魂。 结果可能
很大， 你只需要告诉他模 109+7 之后的结果。
解释：
操作序列为 4 5 2 3 5
操作1：坐标4位置打洞，吸取魂力0
操作2：坐标5位置打洞，吸取魂力4
操作3：坐标2位置打洞，吸取魂力4
操作4：坐标3位置打洞，吸取魂力6
操作5：坐标5位置打洞，吸取魂力4
总魂力18
(n<=6000000 A,B,C,X1<=10^9+7)
解
我首先想到了set求前驱和后继 时间复杂度(O(n*log_2^n)) 但set常数太大...
然后我就想到了利用链表（(list)）
对于插入操作 类似于莫队的做法 左右更新 直到这个地方已经被标记过了
看似会超时 但是更新的区间每次都在减少 所以实际上是比((log_2 ^n )) 要小的
然后就有90分
code:
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 6000010
#define ll long long
bool nam[maxnn];
int l[maxnn],r[maxnn];
#define inf 1000000007
ll n,A,B;
int a[maxnn];
ll x;
ll C;
char buf[1<<20],*p1,*p2;
#define GC() getchar()
inline ll R() {
char t;
ll x=0;
t=GC();
while(!isdigit(t)) t=GC();
while(isdigit(t)) x=x*10+t-48,t=GC();
return x;
}
void FIE()
{
freopen("asoul.in","r",stdin);
freopen("asoul.out","w",stdout);
}
int main() {
FIE();
n=R();
A=R();
B=R();
C=R();
x=R();
C%=inf;
a[1]=(x%n)+1;
ll ans=0;
for(int i=2; i<=n; i++) {
x=((A*((x*x)%inf))%inf+(B*x)%inf+C)%inf;
a[i]=(x%n)+1;
}
for(int i=1; i<=n; i++) {
ans=(ans+l[a[i]])%inf;
ans=(ans+r[a[i]])%inf;
if(nam[a[i]])continue;
nam[a[i]]=true;
int d=a[i]-1;
while(!nam[d]&&d>=0) {
l[d]=a[i];
d--;
}
if(d>=0&&nam[d]) l[d]=a[i];
int re=a[i]+1;
while(!nam[re]&&re<=n) {
r[re]=a[i];
re++;
}
if(nam[re]) r[re]=a[i];
}
printf("%lld",ans);
}
下面说正解
查询一个点左边和右边最近的值 我们自然而然就想到了链表操作
从前往后讨论等价于从后往前讨论
然后就可以利用链表的删除和添加的操作 具体看代码
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 6000010
#define ll long long
bool nam[maxnn];
int L[maxnn],R[maxnn];
#define inf 1000000007
ll n,A,B;
int a[maxnn];
ll x;
ll C;
char buf[1<<20],*p1,*p2;
int cnt[maxnn];
#define GC() getchar()
inline ll r() {
char t;
ll x=0;
t=GC();
while(!isdigit(t)) t=GC();
while(isdigit(t)) x=x*10+t-48,t=GC();
return x;
}
void FIE()
{
freopen("asoul.in","r",stdin);
freopen("asoul.out","w",stdout);
}
int main() {
//FIE();
n=r();
A=r();
B=r();
C=r();
x=r();
C%=inf;
a[1]=(x%n)+1;
ll ans=0;
ll las=0;
cnt[a[1]]++;
for(int i=2; i<=n; i++) {
x=((A*((x*x)%inf))%inf+(B*x)%inf+C)%inf;
a[i]=(x%n)+1;
cnt[a[i]]++;
}
for(int i=1;i<=n;i++)
{
if(cnt[i])
{
R[las]=i;
L[i]=las;
las=i;
}
}
R[0]=0;
for(int i=n;i>=0;i--){
cnt[a[i]]--;
ans=(ans+L[a[i]])%inf;
ans=(ans+R[a[i]])%inf;
if(cnt[a[i]]>0)
{
continue;
}
R[L[a[i]]]=R[a[i]];
L[R[a[i]]]=L[a[i]];
}
printf("%lld",ans%inf);
}
B蒜头君的树
问题描述
蒜头君有一棵有根树，树的每一边都有边权，蒜头君想知道任意两点间最短距离之和为多少。 另外，由于各种原因，蒜头君的树的边的边权会发生若干次改变，蒜头君想让你告诉他，每一 次改变后，任意两点间最短距离之和为多少？
解
此题没有问你两个点的距离 说明需要考虑怎样得到两两点间的距离和
两两点对有(C(2,n)) 对
画图可知我们需要考虑每条边的贡献
每条边的贡献为 $size[u] imes (n-size[v]) imes le[i] (
考虑更新边的权值就只需要deta一下就行了
时间复杂度)O(N)$；
code：
#include<bits/stdc++.h>
using namespace std;
#define maxnn 200010
#define ll long long
ll ans=0;
int size[maxnn];
int n;
#define GC() getchar()
int las[maxnn],en[maxnn],le[maxnn],tot,nex[maxnn];
int f[maxnn];
int dis[maxnn];
inline int R() {
char t;
int x=0;
t=GC();
while(!isdigit(t)) t=GC();
while(isdigit(t)) x=x*10+t-48,t=GC();
return x;
}
void add(int a,int b,int c)
{
en[++tot]=b;
nex[tot]=las[a];
las[a]=tot;
le[tot]=c;
}
void dfs(int v,int fa,int l){
dis[v]=l;
f[v]=fa;
size[v]=1;
for(int i=las[v];i;i=nex[i])
{
int u=en[i];
if(u!=fa)
{
dfs(u,v,le[i]);
size[v]+=size[u];
ans=ans+(1LL*(n-size[u])*le[i]*size[u]);
}
}
}
void FIE()
{
freopen("bileage.in","r",stdin);
freopen("bileage.out","w",stdout);
}
int main()
{
FIE();
n=R();
int F,x;
for(int i=1;i<n;i++)
{
F=R();x=R();
add(i+1,F,x);
add(F,i+1,x);
}
dfs(1,0,0);
printf("%lld
",ans);
int m;
m=R();
int A,C;
while(m--)
{
A=R();
C=R();
ans=ans-(1LL*(1LL*(n-size[A])*dis[A])*size[A]);
dis[A]=C;
ans=ans+(1LL*(1LL*(n-size[A])*dis[A])*size[A]);
printf("%lld
",ans);
}
}
C 对抗赛
问题描述:
某校有n只信竞队伍，队伍编号1到n，每只队伍都有一定数量的队员，队伍中每个人都有一个CF积分，积分越高，意味着竞技水平越高。
有时候队伍间会举行一场对抗赛，对抗赛由两只队伍参赛，老师在参赛的每只队伍中都随机挑选一个队员出来，然后两个人打一场CF比赛，众所周知，CF积分高的那一位选手一定会获胜。如果参赛选手的CF积分相同，则两人获胜的概率相同。
现在老师向你提出了一些询问，如果X和Y号队伍进行对抗，获胜队员的CF积分的期望值是多少？
输入格式:
第一行，一个整数N
接下来N行，其中第i行，第一个整数Ci，表示i号队伍的队员数量，接下来Ci个整数，表示这只队伍每个队员的CF积分。
接下一行，一个整数M，表示询问数量
接下来M行，每行两个整数X和Y，表示一场对抗赛参赛队伍的编号。
输出格式:
M行，每行一个整数，对应一次询问的答案，保留4个小数位。
样例输入:
3
3 1 2 3
3 1 2 3
1 4
2
1 2
1 3
样例输出:
2.4444
4.0000
提示
样例解释：
对于第一个查询，可能的对抗情况是 (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)。
每种对抗发生的概率都是1/9 ，每种对抗获胜的者的CF积分分别时1，2，3，2，2，3，3，3，3
这样期望就是 (1+2+3+2+2+3+3+3+3)/9 = 22/9
第二个查询：不管怎么对抗都是CF积分为4的队员获胜。
数据范围： 设T表示信竞队员的总人数。
对于10%的数据：Ci=1
对于30%的数据：T<=100,M<=100
对于60%的数据：T<=2500,M<=5000
对于100%的数据：T<=40000,M<=40000, Ci>0, 0<=CF积分<=1000000
解：
其实很好想
排序+暴力的时间复杂度是(O(M imes size)) 可以过60%的分
然后怎么办？
注意到 (T<=40000,M<=40000)
说明要么n很大 size很log2 要么n很小 size很大
- n很大 size很小
log2 很小 直接暴力即可 - 要么n很小 size很大
询问一定有重复 利用map保存下来即可
考试的时候我居然想利用随机函数 随机两个点进行打表操作 都没有想到边算边存...
我的40分啊
第二种做法是
这是两个有序的序列
双指针啊！！！ 我在干嘛？？
code：
//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int m;
typedef pair<ll,ll > P;
map<P,double > K;
vector<ll > Q[40005];
vector<long long > sum[40005];
void FIE() {
freopen("dualmeet.in","r",stdin);
freopen("dualmeet.out","w",stdout);
}
vector<ll >::iterator it;
int main() {
//FIE();
cin>>n;
ll y,z;
for(int i=1; i<=n; i++) {
scanf("%lld",&y);
while(y--) {
scanf("%lld",&z);
Q[i].push_back(z);
}
sort(Q[i].begin(),Q[i].end());
for(int j=0; j<Q[i].size(); j++) {
if(j==0) {
sum[i].push_back(1LL*Q[i][0]);
continue;
}
sum[i].push_back(sum[i][j-1]+1LL*Q[i][j]);
}
}
srand(time(0));
int cnt=40000;//随机打表
while(cnt--) {
int y=rand()%n+1;
int z=rand()%n+1;
while(y==z) z=rand()%n+1;
if(K.count(make_pair(y,z))) {
continue;
}
if(Q[y].size()>Q[z].size()) swap(y,z);
int d=Q[y].size();
double ans=0;
for(int i=0; i<d; i++) {
it=upper_bound(Q[z].begin(),Q[z].end(),Q[y][i]);
if(it==Q[z].end()) {
ans+=Q[y][i]*(Q[z].size());
continue;
}
int r=upper_bound(Q[z].begin(),Q[z].end(),Q[y][i])-Q[z].begin();
{
ans+=(r)*Q[y][i];
if(r-1<0)
ans+=sum[z][Q[z].size()-1];
else
ans+=sum[z][Q[z].size()-1]-sum[z][r-1];
continue;
}
}
K[make_pair(y,z)]=ans;
K[make_pair(z,y)]=ans;
}
scanf("%lld",&m);
while(m--) {
scanf("%lld%lld",&y,&z);
if(K.count(make_pair(y,z))) {
printf("%.4lf
",K[make_pair(y,z)]/(1LL*Q[z].size()*Q[y].size()));
continue;
}
if(Q[y].size()>Q[z].size()) swap(y,z);
int d=Q[y].size();
double ans=0;
for(int i=0; i<d; i++) {
it=upper_bound(Q[z].begin(),Q[z].end(),Q[y][i]);
if(it==Q[z].end()) {
ans+=Q[y][i]*(Q[z].size());
continue;
}
int r=upper_bound(Q[z].begin(),Q[z].end(),Q[y][i])-Q[z].begin();
{
ans+=(r)*Q[y][i];
if(r-1<0)
ans+=sum[z][Q[z].size()-1];
else
ans+=sum[z][Q[z].size()-1]-sum[z][r-1];
continue;
}
}
K[make_pair(y,z)]=ans;
K[make_pair(z,y)]=ans;
printf("%.4lf
",ans/(1LL*Q[z].size()*Q[y].size()));
}
}