CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(2018 CSYZ长沙一中)-白红宇

CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(2018 CSYZ长沙一中)

阅读量：6006 次

发布时间：2019-06-20

本文共 9687 字，大约阅读时间需要 32 分钟。

T1 Circle

【问题描述】

小 w 的男朋友送给小 w 一个 n 个点 m 条边的图，并且刁难小 w 要她找出点数最少的正环。

小 w 不会做，于是向你求助。

【输入格式】

第一行两个整数$n,m$

接下来$m$行，每行四个数$u,v,a,b$，表示从$u$走到$v$的代价为$a$，从$v$走到$u$的代价为$b$（算作两条不同的边）。注意$a,b$可能为负。

【输出格式】

当图中包含正环时，输出点数最少的正环（简单环）的点数。

否则输出 0

【样例】

样例输入

3 3

1 2 2 -1

2 3 10 -10

3 1 10 -10

样例输出

数据规模与约定

对于前 20% 的数据，$n ≤ 7,m ≤ 10$ 。

对于前 60% 的数据，$n ≤ 150,m ≤ 2000 $。

对于 100% 的数据，$1≤n≤ 300,0≤m≤\frac{n(n−1)}{2},|a|,|b| ≤ 10 4 .$

数据保证不存在重边和自环。

题解

只会图论的蒟蒻终于可以光明正大AC一道题了嘤嘤嘤。

~~首先我们别看那个标程，完全不人性化~~

从数据来看，我们可以使用SPFA来求解这道题。由于最后求得的正环必须经过最少的点，因此我们可以从每个点出发，向所有它相连的边再连一条边（当然要将题目给出的边和自己连带边区分开），且所有自己连的边权值都为1（实际上，这里是将点权转化为边权来方便计算）。同时，因为我们要求的是一个环，即从$S$点出发的同时要返回$S$点，因此我们在第一次松弛操作结束后重新将起点入队并初始化，这样就能计算出一个经过$S$点的最小环的大小。

void spfa(int u){    bool wait=1;    for(register int i=0;i

q; q.push(u); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=0; for(register int i=p[u];~i;i=E[i].next){ int v=E[i].v; int w=E[i].w; int a=E[i].a; if(dis[v]>dis[u]+w && ges[v]>ges[u]+a && dis[u]+w>0){ ges[v]=ges[u]+a; dis[v]=dis[u]+w; //cout<

<<" "<

最后对于任意点$i$，$ges[i]$就是包含该点的最小（最优）环。对于求出整个图上的最小啊（最优）环来讲，我们只需要对每一个点求出包含其的最小环，并寻求所有环的最优解即可。复杂度方面，由于$n \le 300$，我们可以放心地重复调用SPFA。

#include
    
     #define maxn 305#define maxm 45000#define X first#define Y secondusing namespace std;typedef pair
     
       pall;inline char get(){    static char buf[300],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,300,stdin),p1==p2)?EOF:*p1++;}inline int read(){    register char c=getchar();register int f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();    return _*f;}struct edge{    int u,v,w,next;    int a;}E[maxm<<1];int p[maxn],eid;void init(){    for(register int i=0;i

<<" "<

0){ puts("2"); return 0; } insert(u,v,a,1); insert(v,u,b,1); } for(register int i=1;i<=n;i++){ spfa(i); //cout<

T2 Max

【问题描述】

小 h 的男朋友送给小 h 一个长度为 n 的序列，并且刁难小 h 要她找出其中 m 个区间的最大值。

小 h 不会做，于是向你求助。

【输入格式】

为了避免输入数据过大，本题使用如下方法进行输入：

第一行两个数$n,m$。其中保证$n = 2^k ,k ∈ N $。第二行三个数，分别表示$gen,p_1，p_2$。接下来生成$n$个数，表示长度为$n$的序列。

接下来生成$2m$个数，每次两个，分别表示$m$个区间的左右端点。若第一个数大于第二个数，则交换这两个数。

生成一个数的方法为调用 number() 函数，其返回值为当前生成的数：

int gen , p1 , p2 ;int number() {    gen = (1LL * gen * p1) ^ p2 ;    return (gen & (n − 1)) + 1;}

【输出格式】

为了避免输出数据过大，本题使用如下方法进行输出：

设$ans_i$为第$i$个区间的最大值，你只需要输出一个数：

\[ \sum^{n}_{i=1}ans_i*p_1^{n-i+1} \%p_2\]

【样例1】

样例输入

4 5

32 17 19

样例输出

【样例2】

样例输入

8388608 8000000

95 1071 1989

样例输出

153

数据规模与约定

本题共十组数据，$n,m$均不超过$10^7$。

题解

看到这个题的第一眼，很多选手肯定就会认为这道题是考点是线段树。而稍微灵活一点的选手会想到RMQ问题的通解——ST。然而事实上ST算法会MLE，而正解也就真的是线段树。

首先是ST算法，被使用于各类区间求最值问题中。ST在使用前要先进行预处理，然后再进行查询。由于预处理的存在，其查询复杂度为$O(1)$，在查询量极大的题目里极为有用。

贴出该题的ST解(70分，空间超限)

#include 
    
     #pragma GCC optimize(2)using namespace std;const long long  Maxn=8388610;inline char get(){    static char buf[300],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,300,stdin),p1==p2)?EOF:*p1++;}inline long long read(){    register char c=getchar();register long long  f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();    return _*f;}long long n,m;long long gen,p1,p2;long long number(){    gen=(1LL * gen * p1) ^ p2;    return (gen & (n - 1)) + 1;}long long a[Maxn],l[Maxn],r[Maxn];long long ans[Maxn];long long f[Maxn][25];long long query(long long  l,long long  r){    long long  i=(int)(log2(r-l+1));    return max(f[l][i],f[r-(1<
     
      r[i])swap(l[i],r[i]);    }    for(register long long j=1;(1<
      
       <=n;j++){        for(register long long i=1;i+(1<
       
        <=n;i++){            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);        }    }    long long sum=0;    long long now;    for (register long long i=1;i<=m;++i){        ans[i]=query(l[i],r[i]);        now=sum;        (sum+=ans[i]*p1%p2)%=p2;    }    printf("%lld\n",sum);}

而朴素的最大值线段树则能拿到80分，同样也是MLE

#include 
    
     using namespace std;const int Maxn = 1e7 + 5;int n, m, gen, p1, p2;long long ans[Maxn], minv[Maxn];int a[Maxn], l[Maxn], r[Maxn];inline int number() {    gen = (1LL * gen * p1) ^ p2;    return (gen & (n - 1)) + 1;}inline void pushup(int id) {    minv[id] = max(minv[id << 1], minv[id << 1 | 1]);}inline void build(int id, int l, int r) {    if (l == r) {        minv[id] = a[l];        return;    }    int mid = (l + r) >> 1;    build(id << 1, l, mid);    build(id << 1 | 1, mid + 1, r);    pushup(id);}inline int query(int id, int l, int r, int x, int y) {    if (x <= l && r <= y) {        return minv[id];    }    int ans = 0;    int mid = (l + r) >> 1;        if (x <= mid) ans = max(ans, query(id << 1, l, mid, x, y));    if (y > mid) ans = max(ans, query(id << 1 | 1, mid + 1, r, x, y));        return ans;}int main() {    // freopen("max.in", "r", stdin);    // freopen("max.out", "w", stdout);    freopen("in_2.txt", "r", stdin);    scanf("%d%d", &n, &m);    scanf("%d%d%d", &gen, &p1, &p2);        for (register int i = 1; i <= n; ++i)        a[i] = number();            build(1, 1, n);            for (register int i = 1; i <= m; ++i) {        l[i] = number();        r[i] = number();        if (l[i] > r[i]) swap(l[i], r[i]);                ans[i]  = query(1, 1, n, l[i], r[i]);    }        long long sum = 0;    for (register int i = 1; i <= m; ++i) {        (sum += ans[i] * p1 % p2) %= p2;    }    printf("%lld\n", sum);}

事实上，我们只需要对线段树进行一点优化即可。例如，我们可以贪心地对数据进行预处理，在没有碰到最大值。若我们需要查询$[l,r]$的答案，只需找到$r$在这棵树上不小于$l$的祖先。于是我们可以按照$l$从大到小排序，一边向上查询祖先一边路径压缩（类似并查集）。由于树上的每条边至多被压缩一次，复杂度 O(n) 。

具体代码如下。

#include 
    
     using namespace std;const long long Maxn = 8388608+500;long long n, m;long long gen, p1, p2;long long number() {    gen = (1LL * gen * p1) ^ p2;    return (gen & (n - 1)) + 1;}long long a[Maxn], ans[Maxn];long long MAX[4*Maxn];void pushup(long long id){    MAX[id] = max(MAX[id<<1],MAX[id<<1|1]);}void build(long long id,long long l,long long r){    if(l == r){        MAX[id] = a[l];        return;    }    long long mid = (l+r)>>1;    build(id<<1,l,mid);    build(id<<1|1,mid+1,r);    pushup(id);}long long query(long long id,long long l,long long r,long long x,long long y){    if(x <= l && r <= y){        return MAX[id];    }    long long mid = (l+r)>>1;    long long ans = -0x3f3f3f3f;    if(x <= mid){        ans = max(ans,query(id<<1,l,mid,x,y));    }    if(y > mid){        ans = max(ans,query(id<<1|1,mid+1,r,x,y));    }    return ans;}struct node{    long long l,r,i;};int main() {    //freopen("max.in", "r", stdin);    //freopen("max.out", "w", stdout);    scanf("%lld%lld", &n, &m);    scanf("%lld%lld%lld", &gen, &p1, &p2);    for (long long i = 1; i <= n; ++i){        a[i] = number();        //cout << a[i] << " ";    }    build(1,1,n);    queue
     
       q;    for (int i = 1; i <= m; ++i) {        long long l = number(), r = number();        if (l > r){            swap(l, r);        }        node now;        now.l = l;        now.r = r;        now.i = i;        if(now.l == q.front().l && now.r == q.front().r){            ans[i] = ans[q.front().i];            q.pop();            q.push(now);        }else{            q.push(now);            ans[i] = query(1,1,n,l,r);        }            }    long long sum = 0;    for (int i = 1; i <= m; ++i) {        (sum += ans[i]*p1%p2)%= p2;    }    printf("%lld\n", sum);}

T3 Seq

【问题描述】

小 y 的男朋友送给小 y 一个数列$\{ a_i \}$，并且刁难小 y 要她维护这个序列。

具体而言，小 y 的男朋友要求小 y 完成两个操作：

1.修改数列中的一个数。

2.设$p_i$表示$max_{j=1}^{i}a_j,求出\sum_{i=1}^n p_i$。

小 y 不会做，于是向你求助。

【输入格式】

第一行一个数$n$表示数列长度。

第二行$n$个由空格隔开的数表示数列$a$。

第三行一个数$m$表示修改数。

接下来$m$行，每行两个数$pos,value$，表示把$a_{pos}$改成$value$。

【输出格式】

m 行，每行一个数，表示对于每次修改后的$\sum_{i=1}^{n}p_i$

【样例输入1】

114 357 904 407 100 624 449 897 115 846

5 357

6 350

2 939

9 1182

7 1062

2 3300

4 6867

4 2076

3 8458

9 6575

10 5737

10 338

9 10446

4 7615

2 5686

4 10091

1 6466

6 15551

3 10914

7 3234

【样例输出1】

7703

8565

9051

9297

29814

54783

29814

71078

75054

77440

85605

92737

119327

123429

【数据规模与约定】

$对于前 30\% 的数据, n,m ≤ 5000;$

$对于前 60\% 的数据, n,m ≤ 50000;$

$对于 100\% 的数据, n ≤ 3 · 10^5 , a i ≤ 10^9$

【题解】

我们考虑若修改了 i 点，显然只会对在它后面的点有影响。

现在我们在线段树上考虑这个问题。设 node 是线段树上代表 [l,r] 区间的点，ls,rs 分别是

node 的左右儿子，v 是数列位置在 l 之前一个被修改的值。那么：

若 v 大于 max ls ，显然 [l,mid] 区间内的点的 p i 都会被修改为 v（注意这里的 p i 并不是正确值，必须要递归回到树顶才是真正的 p i ），于是我们只需要递归 rs。

若 v 小于 max rs ，则 [mid + 1,r] 的 p 不会被更新，于是我们只需要递归 ls。这样，线段树上每合并两个节点，都需要用左儿子更新一次右儿子。
复杂度 O(nlog 2 n).

#include
    
     #define yyy "By Yourself!"#define maxn 300005using namespace std;inline char get(){    static char buf[300],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,300,stdin),p1==p2)?EOF:*p1++;}inline long long read(){    register char c=getchar();register long long f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();    return _*f;}string change(){    string now="";    now+=(char)87;    now+=(char)114;    now+=(char)105;    now+=(char)116;    now+=(char)101;    now+=" ";    return now+yyy;}long long n,m;long long a[maxn];long long x,v;long long ans,maxnow;int main(){    //freopen("seq.in","r",stdin);    //freopen("seq.out","w",stdout);    n=read();    //cout<
     
      <

转载于:https://www.cnblogs.com/Chen574118090/p/9910287.html