欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

泉五培训Day2

程序员文章站 2022-03-04 08:45:26
T1 旅游 题目 【题目描述】 幻想乡有n个景点(从1开始标号),有m条双向的道路连在景点之间,每条道路有一个人气值d,表示这条道路的拥挤程度。小G不会经过那些人气值大于x的道路,她想知道有多少对景点(a, b)满足她能够从景点a到达景点b。 (a, b)和(b,a)算不同点对,要算两次。 【输入格 ......

t1 旅游

题目

【题目描述】

幻想乡有n个景点(从1开始标号),有m条双向的道路连在景点之间,每条道路有一个人气值d,表示这条道路的拥挤程度。小g不会经过那些人气值大于x的道路,她想知道有多少对景点(a, b)满足她能够从景点a到达景点b。

(a, b)和(b,a)算不同点对,要算两次。

【输入格式】

第一行一个数test,表示有test组数据。

对于每组数据,第一行有三个数n, m, q,q表示有q个询问。

接下来m行,每行三个数x, y, d,表示有一条连接x, y人气值为d的道路。

最后q行,每行一个询问x。

【输出格式】

对于每组数据,你需要输出q行,依次回答所有询问。

【输入样例】

1

5 5 3

2 3 6334

1 5 15724

3 5 5705

4 3 12382

1 3 21726

6000

10000

13000

【输出样例】

2

6

12

【数据规模】

对于前10%的数据,n <=200。

对于前40%的数据,n <=500, m <= 2000, q <= 100, d <= 1000。

对于前100%的数据:

1 <= n <= 20000, 1 <= m <= 10^5, 1 <= d<= 10^5, q <= 5000。

解析

先将边按边权排序,再依次加入图中,再用并查集维护图的连通性,把询问混入边中排序即可。

值得注意的是(a,b)不同于(b,a),因此计算时得乘2。

code

泉五培训Day2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int test,n,m,q,md=0,fa[30000],s[30000],ans[200000];
struct rec{
    int x,y,z;
}edge[200000];
bool cmp(rec a,rec b)
{
    return a.z<b.z;
}
int get(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
void find()
{
    for(int i=1;i<=m;i++)
    {
        int x=get(edge[i].x);
        int y=get(edge[i].y);
        if(x!=y)
        {
            fa[x]=y;
            ans[edge[i].z]+=s[x]*s[y]*2;
            s[y]+=s[x];
        }
    }
}
int main()
{
    cin>>test;
    while(test--)
    {
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++)
        {
            cin>>edge[i].x>>edge[i].y>>edge[i].z;
            md=max(md,edge[i].z);
        }
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            s[i]=1;
        }
        sort(edge+1,edge+m+1,cmp);
        memset(ans,0,sizeof(ans));
        find();
        for(int i=2;i<=md;i++) ans[i]+=ans[i-1];
        for(int i=1;i<=q;i++)
        {
            int qu;
            cin>>qu;
            cout<<ans[qu]<<endl;
        }
    }
    return 0;
}
view code

 

 

 

 

 

 

t2 序列

题目

【题目描述】

给出一个序列a(a_1a1a_2a2,...,a_nan)。有一些操作,每个操作给定三个正整数l,r,k,表示将区间[l,r]内的每个元素的值都减k。

你要告诉我,在第几次操作后,序列中第一次出现一个值为负的元素。

【输入格式】

第一行有二个整数n,m,描述序列大小和操作数。

接下来一行n个非负整数,描述a_1a1,a_2a2,...,a_nan

接下来m行,每行3个正整数l,r,k,描述一个操作。

【输出格式】

输出一行一个整数,描述答案。

如果序列中从未出现值为负的元素,输出-1。

【输入样例】

4 3

2 5 4 3

1 3 2

2 4 3

2 4 4

【输出样例】

2

【数据范围】

对于20%的数据,n,m≤1000。

对于40%的数据,n,m≤10^5

对于100%的数据,n,m≤2x10^6,所有输入数据不超过10^9

注意读入优化。

 解析

因为数据量太大,所以暴力的话只能拿部分分。

先将原序列a差分,得到一个新序列b,其中bi=ai-ai-1

在a上的区间修改便成了在b上的单点修改。

先将所有操作有序加入一个栈中,再按从1到n的顺序计算ai的值。

如果ai为负数,就退掉栈顶的操作。

最后的答案即为栈内元素数量+1。

code

泉五培训Day2
#include <iostream>
#include <cstdio>
using namespace std;
int read()    //快读 
{
    char c=getchar();int x=0,f=1;
    while(c<48 || c>57){if(c=='-') f=-1;c=getchar();}
    while(c>=48 && c<=57){x=x*10+c-48;c=getchar();}
    return x*f;
}
struct abc{
    int l,r,z;
}p[2000001];
int n,m,a[2000001],b[2000001],zz,mm;
int main()
{
    n=read();m=read();
    mm=m;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=m;i++) 
    {
        p[i].l=read();p[i].r=read();p[i].z=read();
        b[p[i].l]-=p[i].z;
        b[p[i].r+1]+=p[i].z;
    }
    for(int i=1;i<=n;i++) 
    {
        zz+=b[i];
        while(zz<0&&m>0)
        {
            if(p[m].l<=i) zz+=p[m].z;
            if(p[m].r<i) zz-=p[m].z;
            b[p[m].l]+=p[m].z;b[p[m].r+1]-=p[m].z;
            m--;
        }
    }
    if(mm!=m) cout<<m+1;
    else cout<<-1;
    return 0;
}
view code

 

 

 

 

 

 

t3 最大公约数

题目

【问题描述】

    给定一个正整数,在[1,n]的范围内,求出有多少个无序数对(a,b)满足gcd(a,b)=a xor b。

【输入格式】

    输入共一行,一个正整数n。

【输出格式】

    输出共一行,一个正整数表示答案。

【输入输出样例】

gcd.in

gcd.out

3

1

解释:只有(2,3)满足要求

【数据范围】

对于30%的数据满足n<=1000

对于60%的数据满足n<=10^5

对于100%的数据满足n<=10^7

 解析

很显然,a=b时肯定是无解的,所以我们不妨设a>b。

则gcd(a,b)<=a-b,a xor b>=a-b,显然有c=a-b。

枚举c,a=i*c,因为gcd(a,a-c)=c,所以只需判断a xor c=a-c即可。

code

泉五培训Day2
#include <iostream>
#include <cstdio>
using namespace std;
int n,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
            if(((i*j)^i)==i*j-i)
                ans++;
    cout<<ans;
    return 0;
}
view code