首页 > > 程序设计 > C/C++ >

长乐国庆集训Day3

2019-10-08 08:47:18来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

长乐国庆集训Day3

T1 动态逆序对

题目

【题目描述】

给出一个长度为n的排列a（1~n这n个数在数列中各出现1次）。每次交换两个数，求逆序对数%2的结果。

逆序对：对于两个数a[i],a[j](i<j)，若a[i]>a[j]，则(a[i],a[j])为1个逆序对。

【输入格式】

第一行一个正整数n。

接下来一行n个数，表示给出的排列a。

接下来一行一个正整数q。

接下来q行，每行两个正整数i,j，表示交换a[i]和a[j]。

【输出格式】

输出共q行，表示每次交换后的逆序对数%2的结果。

【输入样例】

4
1 2 3 4
2
1 2
1 2

【输出样例】

1
0

【数据规模】

对于60%的数据：n,q≤100；

对于80%的数据：n,q≤1000；

对于100%的数据：n,q≤100000。

解析

先求出初始序列的逆序对总数对2取余的结果。

每次交换a[i]与a[j](i<j)，对于a[k]的影响如下：

  • 若k<i，a[k]依旧在a[i]与a[j]前面，所以a[k]与a[i]、a[j]产生的逆序对数不变；
  • 若k>j，同上，逆序对数不变；
  • 若i<k<j，如果a[i]<a[k]，则逆序对数+1，否则-1,；如果a[j]>a[k]，则逆序对数+1，否则-1，

而我们只需求出逆序对数对2取余的结果，可以发现，逆序对个数的奇偶性与k无关。

事实上，只需在每次交换位置时，令逆序对总数对2取余的结果^1即可（i=j时则不变）。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,q,a[100100],f[100100],temp;
void add(int x,int y)
{
    for(;x<=n;x+=(x&-x)) f[x]+=y;
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&-x)) ans+=f[x];
    return ans;
}
int main()
{
    //freopen("lyk.in","r",stdin);
    //freopen("lyk.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    q=read();
    for(int i=n;i>=1;i--)
    {
        temp+=ask(a[i]-1);
        add(a[i],1);
    }
    temp&=1;
    for(int i=1;i<=q;i++)
    {
        int x=read(),y=read();
        if(x!=y) temp^=1;
        cout<<temp<<endl;
    }
    return 0;
}
View Code

 

 

 

 

 

T2 树的统计

题目

【题目描述】

给出一棵n个点的满二叉树，根节点为1，第i个点的左右子节点分别为第2i,2i+1个点，第i个点的权值为a[i]。

有m个询问。对于每个询问给出x,d，求到点x的距离为d的所有点的点权和。如果不存在符合条件的点，输出0。

两点距离即两点间最短路径的边数。

保证最终答案在int范围内。

【输入格式】

第一行两个正整数n,m。

接下来n行每行一个正整数，第i行的数表示a[i]。

接下来m行每行两个整数x,d，表示一个询问。

【输出格式】

对于每个询问输出一行表示答案。

【输入样例】

7 3
13
7
2
9
5
6
8
1 3
4 2
3 1

【输出样例】

0
18
27

【数据规模】

对于80%的数据，n≤1023，m≤1000。

对于100%的数据，n≤131071，m≤100000，n=2t-1，1≤t≤17，a[i]≤30000。

解析

对于每个询问，用dfs搜索与点x距离为d的点，进行统计即可。

注意每个点之间的关系，访问父亲是x<<1，左儿子是x>>1，右儿子是x>>1+1，要特判一下左右儿子编号不能大于n，否则会RE。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
const int N=131073;
int n,m,a[N],dd,ans;
void dfs(int x,int d,int from)
{
    if(d>dd) return ;
    if(d==dd)
    {
        ans+=a[x];
        return ;
    }
    int y=x>>1;
    if(y>=1&&y!=from) dfs(y,d+1,x);
    y=x<<1;
    if(y<=n&&y!=from) dfs(y,d+1,x);
    if(y+1<=n&&y+1!=from) dfs(y+1,d+1,x);
}
int main()
{
    //freopen("dream.in","r",stdin);
    //freopen("dream.out","w",stdout);
    n=read(),m=read();
    a[1]=read();
    for(int i=2;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        dd=read(),ans=0;
        dfs(x,0,0);
        cout<<ans<<endl;
    }
    return 0;
}
View Code

 

 

 

 

 

T3 宣传栏

题目

【题目描述】

有一个大型的矩形宣传栏，高和宽分别为h和m。宣传栏是用来张贴告示的地方，最初，宣传栏是空的，但此后告示将一张一张的被放上去。

有n张告示，每张告示的高都是一个单位长度，第i张贴上的告示宽度为w[i]。

每次张贴时，总是将告示贴在可以张贴且最高的地方，如果有多个可行的地方，则选择最左边张贴。

给定宣传栏的高和宽，你的任务是找出每个告示张贴在第几行。

【输入格式】

第一行为三个整数，h，m和n(1≤m≤109;1≤h≤n≤200000)，表示宣传栏的尺寸和张贴的告示个数。

接下来n行表示w[i]（1≤w[i]≤109）。

【输出格式】

每行一个整数表示答案。如果第i个告示没地方贴，输出-1。

【输入样例】

3 5 5
2
4
3
3
3

【输出样例】

1
2
1
3
-1

【数据规模】

对于20%的数据，n=1。

对于40%的数据，n,m≤500。

对于70%的数据，n≤2000。

对于90%的数据，n≤50000。

对于100%的数据，n≤200000。

解析

用c[i]表示第i行还剩多少长度。

用线段树维护c[i]的区间最大值即可。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int h,m,n,c[800100];
int w;
void build(int p,int l,int r)
{
    c[p]=m;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
}
int ask(int p,int l,int r)
{
    if(l==r)
    {
        c[p]-=w;
        return l;
    }
    int mid=(l+r)>>1;
    if(c[p*2]>=w)
    {
        int temp=ask(p*2,l,mid);
        c[p]=max(c[p*2+1],c[p*2]);
        return temp;
    }
    else
    {
        int temp=ask(p*2+1,mid+1,r);
        c[p]=max(c[p*2+1],c[p*2]);
        return temp;
    }
}
int main()
{
    //freopen("billboard.in","r",stdin);
    //freopen("billboard.out","w",stdout);
    h=read(),m=read(),n=read();
    build(1,1,h);
    for(int i=1;i<=n;i++)
    {
        w=read();
        if(w>c[1])
        {
            cout<<"-1"<<endl;
            continue;
        }
        cout<<ask(1,1,h)<<endl;
    }
    return 0;
}
View Code

 

 

 

 

 

T4 种树

题目

【题目描述】

你要在一条无穷长的马路上种树。

你想种3种树，分别是草莓树，西瓜树，土豆树。

给定3个正整数A,B,C，你可以选择3个整数x,y,z，然后：

  • 在位置 … , x-2A , x-A , x , x+A , x+2A , … 分别种1棵草莓树。
  • 在位置 … , y-2B , y-B , y , y+B , y+2B , … 分别种1棵西瓜树。
  • 在位置 … , z-2C ,z-C , z , z+C , z+2C , … 分别种1棵土豆树。

你想要最大化最近的两棵树的距离，请你输出这个最大距离。

【输入格式】

每个测试点多组测试数据。

每组数据输入一行A,B,C。

没给出数据组数，你可以这样输入：

while (scanf(“%d%d%d”, &A, &B, &C) == 3)

{

       ……

}

【输出格式】

对于每个询问输出一行表示答案。

【输入样例】

1 5 8
3 3 6
2000 2000 2000
999 999 999
233 233 233
100 100 100
40 30 20

【输出样例】

0
1
666
333
77
33
5

【数据规模】

对于100%的数据，1≤A,B,C≤2000。

解析

先用solve函数求出三树两两之间最小距离的最小值，然后再找到最大的即可。

证明过程比较麻烦，本蒟蒻数论不太好，就不给出详细证明了。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int a,b,c,x,y,z,ans;
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int solve(int a,int b,int x,int y)
{
    int g=gcd(a,b);
    int t=(x-y)%g;
    if(t<0) t+=g;
    return min(t,g-t);
}
int main()
{
    while(cin>>a>>b>>c)
    {
        ans=0;
        for(y=0;y<b;y++)
            for(z=0;z<c;z++)
            {
                int temp;
                temp=min(solve(a,b,0,y),min(solve(b,c,y,z),solve(a,c,0,z)));
                ans=max(ans,temp);
            }
        cout<<ans<<endl;
    }
    return 0;
}
View Code

 


原文链接:https://www.cnblogs.com/I-Love-You-520/p/11619429.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：【题解】洛谷 P1083 借教室

下一篇：长乐国庆集训Day5-2

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签