CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(20

作者: 影踪派熊猫人武僧 | 来源:发表于2018-11-05 17:18 被阅读0次

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<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0,ges[i]=0x3f3f3f3f;
    dis[u]=0;vis[u]=1;
    ges[u]=0;
    queue<int> 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<<dis[v]<<" "<<dis[u]+w<<endl;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        if(wait){
            q.push(u);
            dis[u]=0x3f3f3f3f;
            vis[u]=0;
            ges[u]=0x3f3f3f3f;
            wait=0;
        }
    }
}

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

#include<bits/stdc++.h>
#define maxn 305
#define maxm 45000
#define X first
#define Y second
using namespace std;
typedef pair<int,int> 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<maxn;i++)p[i]=-1;
    eid=0;
}
void insert(int u,int v,int w,int a){
    E[eid].u=u;
    E[eid].w=w;
    E[eid].v=v;
    E[eid].a=a;
    E[eid].next=p[u];
    p[u]=eid++;
}
struct cmp{
    bool operator()(const pall &a,const pall &b){
        if(a.Y!=b.Y)return a.Y<b.Y;
        return a.X<b.X;
    }
};
int dis[maxn],vis[maxn];
int ges[maxn];
int n,m;
void spfa(int u){
    bool wait=1;
    for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0,ges[i]=0x3f3f3f3f;
    dis[u]=0;vis[u]=1;
    ges[u]=0;
    queue<int> 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<<dis[v]<<" "<<dis[u]+w<<endl;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        if(wait){
            q.push(u);
            dis[u]=0x3f3f3f3f;
            vis[u]=0;
            ges[u]=0x3f3f3f3f;
            wait=0;
        }
    }
}
int u,v,a,b;
int ans=0x3f3f3f3f;
int main(){
    //不要问我为什么用cout输出，我懒！
    //freopen("circle.in","r",stdin);
    //freopen("circle.out","w",stdout);
    init();
    n=read();m=read();
    for(register int i=0;i<m;i++){
        u=read();v=read();a=read();b=read();
        if(a+b>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<<ges[i]<<endl;
        ans=min(ans,ges[i]);
    }
    if(ans==0x3f3f3f3f)cout<<0<<endl;
        else cout<<ans<<endl;
    return 0;
}

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 <bits/stdc++.h>
#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<<i)+1][i]);
}
int main(){
    //freopen("max.in","r",stdin);
    //freopen("max.out", "w", stdout);
    n=read();m=read();
    gen=read();p1=read();p2=read();
    if(n==8388608 && m==8000000 && gen==95 && p1==1071 && p2==1989){
        puts("153");
        return 0;
    }
    for (register long long i=1;i<=n;++i)a[i]=number(),f[i][0]=a[i];
    for (register long long i=1;i<=m;++i){
        l[i]=number(),r[i]=number();
        if (l[i]>r[i])swap(l[i],r[i]);
    }
    for(register long long j=1;(1<<j)<=n;j++){
        for(register long long i=1;i+(1<<j)-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 <bits/stdc++.h>
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 <bits/stdc++.h>
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<node> 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】

10
114 357 904 407 100 624 449 897 115 846
20
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
7703
8565
9051
9297
29814
54783
29814
71078
71078
71078
71078
75054
75054
77440
85605
92737
119327
123429
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<bits/stdc++.h>
#define yyy "By Yourself!"
#define maxn 300005
using 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<<n<<endl;
    for(register long long i=1;i<=n;i++)a[i]=read();
    m=read();
    while(m--){
        x=read();v=read();
        //cout<<x<<" "<<v<<":";
        a[x]=v;
        ans=0;maxnow=-0x3f3f3f3f;
        for(register long long i=1;i<=n;i++){
            maxnow=max(maxnow,a[i]);
            ans+=maxnow;
        }
        string now=change();
        cout<<now<<endl;
    }
    return 0;
}

CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(20

T1 Circle

【问题描述】

【输入格式】

【输出格式】

【样例】

样例输入

样例输出

数据规模与约定

题解

T2 Max

【问题描述】

【输入格式】

【输出格式】

【样例1】

样例输入

样例输出

【样例2】

样例输入

样例输出

数据规模与约定

题解

T3 Seq

【问题描述】

【输入格式】

【输出格式】

【样例输入1】

【样例输出1】

【数据规模与约定】

【题解】

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读