LibreOJ β Round #2

这套题目真的不错，难度区分还是挺好的，后面的题目恕我愚笨，搞不定。

先看看前面几个吧～～～

A. 模拟只会猜题意

内存限制：256 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统 评测方式：文本比较

 

题目描述

给定一个长度为 nnn 的序列 AAA 。

定义 f(l,r)=∑i=lrAif(l,r)=sum_{i=l}^{r} A_{i}f(l,r)=∑​i=l​r​​A​i​​。

询问 mmm 次，每次询问一个数字 xxx，请求出所有满足 r−l+1≥xr-l+1 ge xr−l+1≥x 区间 [l,r][l,r][l,r] 中最大的 f(l,r)f(l,r)f(l,r)。

输入格式

第一行两个数，表示 nnn 和 mmm 。
之后 nnn 个数，表示序列 AAA。
之后 mmm 行每行一个数 xxx，表示询问 xxx 。

输出格式

输出 mmm 行，每行一个答案，表示最大的 f(l,r)f(l,r)f(l,r) 。

样例

样例输入

5 5
1 2 3 4 5
1
2
3
4
5

样例输出

15
15
15
15
15

数据范围与提示

枚举起点和终点，刷新区间的最优值，就是长度为x的最优值，然后dp推一下，就是>=x的最优质。

做到了O(1)的询问。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+5;
int sum[maxn];
int ans[maxn];
int a[maxn];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(ans,-0x3f3f3f3f,sizeof(ans));
    for(int i = 1; i<=n; i++) scanf("%d",&a[i]);

    for(int i = 1; i<=n; i++) sum[i] = sum[i-1] + a[i];

    for(int i = 1; i<=n; i++) {
        for(int j = 0; j<i; j++) {
            ans[i-j] = max(ans[i-j],sum[i]-sum[j]);
        }
    }

    for(int i = n-1; i >=1 ; i--)
        ans[i] = max(ans[i],ans[i+1]);

    for(int i = 0; i < m; i++) {
        int x;
        scanf("%d",&x);
        printf("%d
",ans[x]);
    }

    return 0;
}

B. 贪心只能过样例

内存限制：256 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统 评测方式：文本比较

 

题目描述

一共有 nnn个数，第 iii 个数 xix_ix​i​​ 可以取 [ai,bi][a_i , b_i][a​i​​,b​i​​] 中任意值。
设 S=∑xi2S = sum{{x_i}^2}S=∑x​i​​​2​​，求 SSS 种类数。

输入格式

第一行一个数 nnn。
然后 nnn 行，每行两个数表示 ai,bia_i,b_ia​i​​,b​i​​。

输出格式

输出一行一个数表示答案。

样例

样例输入

5
1 2
2 3
3 4
4 5
5 6

样例输出

26

数据范围与提示

1≤n,ai,bi≤1001 le n , a_i , b_i le 1001≤n,a​i​​,b​i​​≤100

分析：

可以考虑像多重背包一样，最后枚举和。

有一个优化的方案，bitset，想法很奇妙，不停的右移前一步的结果，如果出现相同的，只会产生移动到同一位置。然后数1的个数。

学一下bitset的使用。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;

bitset<maxn> ans[105];

int main()
{
    int n;
    scanf("%d",&n);

    ans[0] = 1;
    for(int i = 1; i <= n; i++) {
        int l,r;
        scanf("%d%d",&l,&r);
        for(int j = l; j <= r; j++)
            ans[i] = ans[i] | ans[i-1]<<(j*j);
    }

    int cnt = 0;
    for(int i = 0; i <=1e6; i++)
        if(ans[n][i]==1) cnt++;
    printf("%d
",cnt);

    return 0;
}

bitset使用：

一,定义和初始化

 bitset<n> b;                           //b有n位,每位都为0;

 bitset<n> b(u);                       //b是unsigned long型u的副本

 bitset<n> b(s);                       //b是string对象s中含有n位字符串的副本

 bitset<n> b(s, pos, n);             //b是s中从pos位置开始的n个位置的副本

 bitset<n> b(s,pos);                 //b从s的pos位置开始取值到s末尾(注取的值从b的右端开始)

　注：①n定义的位数在初始化时按初始值填充,赋值超出的范围舍去,空余的以零填充.

         ②bitset从string对象读入位集时按从右到左的顺序.

二,操作

 b.any();                                 //查找b是否存在1?

 b.none();                               //b中不存在1吗?

 b.count();                              //b中1的个数

 b.size();                                //b的位数

 b[pos];                                 //访问b中pos处的数值

 b.test(pos);                          //检测b中pos处是否为1

 b.set();                                //把b中所有位 置为1

 b.set(pos);                           //把b中pos位置为1

 b.reset();                             //把b中所有位置为0

 b.reset(pos);                         //把b中pos位置为0

 b.flip();                                //b中所有二进制位取反

 b.flip(pos);                           //b中在pos处的二进制位取反

 b.to_ulong;                           //返回一个同值得unsigned long值

 os << b;                              //把b中位集输出

C. DP 一般看规律

内存限制：512 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统 评测方式：文本比较

 

题目描述

给定一个长度为 nnn 的序列 aaa，一共有 mmm 个操作。
每次操作的内容为：给定 x,yx,yx,y，序列中所有 xxx 会变成 yyy。

同时我们有一份代码：

int ans = 2147483647;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (a[i] == a[j])
            ans = std::min(ans, j - i);
    }
}
std::cout << ans << std::endl;

请在每次修改后输出代码运行的结果。

输入格式

第一行两个数，表示 n,mn,mn,m。
第二行 nnn 个数，表示 a1,a2,⋯,ana_1,a_2,cdots, a_na​1​​,a​2​​,⋯,a​n​​。
然后 mmm 行每行两个数 xxx 和 yyy，表示序列中所有 xxx 会变成 yyy。

输出格式

对于每次修改，输出答案。

样例

样例输入

5 10
2 7 6 3 8 
6 1
7 1
1 3
5 6
1 7
9 5
1 10
7 6
7 5
3 9

样例输出

2147483647
1
1
1
1
1
1
1
1
1

数据范围与提示

1≤n,m≤1000001le n , m le 1000001≤n,m≤100000

每个出现的数字绝对值在 int 范围内。

竟然让我想到做法了，就是值：位置。

全部把某一个数变成某一个数，就是合并区间。

刚开始map<int,vector<int> > mp;但是时间复杂度到爆炸。大佬们是map<int,set<int> > mp;

可以发现合并后答案只会减小，插入一个数，只可能影响到前后两个数。合并的时候是启发式合并。

#include <bits/stdc++.h>

using namespace std;

int n,m;

map<int,set<int> > mp;
int ans = 2147483647;

void insert(int v,int p) {
    auto it = mp[v].lower_bound(p);
    if(it!=mp[v].end()) ans = min(ans,*it-p);
    if(it!=mp[v].begin()) ans = min(ans,p-*--it);
    mp[v].insert(p);
}



int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);

    int v;
    for(int i = 1; i<=n; i++) {
        scanf("%d",&v);
        insert(v,i);
    }

    int x,y;
    for(int z = 1; z<=m; z++) {
        scanf("%d%d",&x,&y);
        if(x==y) {
            printf("%d
",ans);
            continue;
        }
        if(mp[x].size()>mp[y].size()) swap(mp[x],mp[y]);
        for(auto it = mp[x].begin(); it!=mp[x].end(); ++it) {
            insert(y,*it);
        }
        mp[x].clear();
        printf("%d
",ans);
    }

    return 0;
}