Educational Codeforces Round 15 - ABC

A. Maximum Increase

题意:
找 最长的 连续的严格上升的子序列,输出它的长度。

解题:
因为要求连续,所以一边扫一遍统计就可以。
事后觉得我写的麻烦了些o(╯□╰)o。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int a[100010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int s=0,e=0,ans = 1;
    for(int i=1;i<n;i++){
        if(a[i]>a[i-1])
        {
            e++;
            ans = max(e-s+1,ans);
        }
        else
        {
            s=i;e=i;
        }
    }
    printf("%d\n",ans);
    return 0;
}

B. Powers of Two

题意:
给定长度为 n 的序列,找出有多少对数相加的和 属于 2 的 x 次幂 。

解题:

先预处理出 2的 x 次幂放在数组, 序列另用一个 map 容器存并记录个数。
然后用 2的 x 次幂 减去序列各元素 ,查找 map 容器里是否有与之对应的数出现。
出现的次数就是对数。
需要注意,如果差和减数一样,则要减 1,即它自己。
最后答案 除 2,因为如果存在满足条件的数,两两之间会又算一遍 。

(写的时候蠢蠢的之前没注意看数据范围= =,结果都懂得...)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
#define ll __int64
using namespace std;
map<ll,int>m;
ll a[100010];
int main()
{
    ll e[50]={1,1};
    int cnt=0;
    for(int i=1;i<50;i++)
    {
        if((e[i-1]*2) > (1e9+1e9) ) break;
        e[i] = e[i-1]*2 ;cnt++;
    }
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%I64d",&a[i]);
        m[a[i]]++;
    }
    sort(a,a+n);
    ll ans = 0;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<n;j++){
            if(a[j] >= e[i]) break;
            ll x = e[i]-a[j];
            if(x==a[j]) ans += ( m[x]- 1 );
            else ans += m[x];
        }
    }
    cout<<ans/2<<endl;
}

C. Cellular Network

题意:
n 个城市, m 个塔,在一条直线上,每个塔可以给附近的城市提供网络,
求所有城市都能够覆盖网络的情况下,塔与城市间的最短的距离。
第一行输入 n ,m ;表示城市与塔的数量;
随后 n 个数 与 m 个数, 表示城市和塔的坐标。

解题:
扫一遍城市的坐标,二分找到离此城市最近的那座塔,(就是跟此城市坐标最近的一个数),
这样得到的距离是最近的,不断更新即可。

不知道是我自己问题还是二分就这样 o(╯□╰)o ,自己二分找到的总是第一个大于或等于城市坐标的数,
所以还要和前一个位置的数再比一下。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#define ll __int64
using namespace std;
const int maxn = 100010;
int n,m;
ll c[maxn],t[maxn], dis = 0;;
int main()
{
    t[0] = -1e9;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%I64d",&c[i]);
    for(int i=1;i<=m;i++)
        scanf("%I64d",&t[i]);
    ll ans = 0;
    for(int i=0;i<n;i++){
        int l = 1, r = m;
        while(l<r){
            int mid = (l+r)/2;
            if(t[mid]>=c[i]) r=mid;
            else l = mid+1;
        }
        ll a2 = abs(t[l] - c[i]);
        if(l-1>0){
            ll a1 = abs(t[l-1]-c[i]);
            ans = max(ans, min(a1,a2));
        }
        else ans = max(ans, a2);
    }
    cout<<ans<<endl;
    return 0;
}
时间: 07-28

Educational Codeforces Round 15 - ABC的相关文章

Codeforces Educational Codeforces Round 15 C. Cellular Network

C. Cellular Network time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line

Educational Codeforces Round 15 套题

这套题最后一题不会,然后先放一下,最后一题应该是大数据结构题 A:求连续最长严格递增的的串,O(n)简单dp #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <vector> usi

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Educational Codeforces Round 26 D. Round Subset(dp)

题目链接:Educational Codeforces Round 26 D. Round Subset 题意: 给你n个数,让你选其中的k个数,使得这k个数的乘积的末尾的0的个数最大. 题解: 显然,末尾乘积0的个数和因子2和因子5的个数有关. 然后考虑dp[i][j]表示选i个数,当前因子5的个数为j时,能得到因子2最多的为多少. 那么对于每个数,记录一下因子2和5的个数,做一些01背包就行了. 1 #include<bits/stdc++.h> 2 #define mst(a,b) me

Educational Codeforces Round 23 F. MEX Queries(线段树)

题目链接:Educational Codeforces Round 23 F. MEX Queries 题意: 一共有n个操作. 1.  将[l,r]区间的数标记为1. 2.  将[l,r]区间的数标记为0. 3.  将[l,r]区间取反. 对每个操作,输出标记为0的最小正整数. 题解: hash后,用线段树xjb标记一下就行了. 1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<&l

Educational Codeforces Round 23 D. Imbalanced Array(单调栈)

题目链接:Educational Codeforces Round 23 D. Imbalanced Array 题意: 给你n个数,定义一个区间的不平衡因子为该区间最大值-最小值. 然后问你这n个数所有的区间的不平衡因子和 题解: 对每一个数算贡献,a[i]的贡献为 当a[i]为最大值时的 a[i]*(i-l+1)*(r-i+1) - 当a[i]为最小值时的a[i]*(i-l+1)*(r-i+1). 计算a[i]的l和r时,用单调栈维护.具体看代码,模拟一下就知道了. 然后把所有的贡献加起来.

Educational Codeforces Round 25 F. String Compression(kmp+dp)

题目链接:Educational Codeforces Round 25 F. String Compression 题意: 给你一个字符串,让你压缩,问压缩后最小的长度是多少. 压缩的形式为x(...)x(...)  x表示(...)这个出现的次数. 题解: 考虑dp[i]表示前i个字符压缩后的最小长度. 转移方程解释看代码,这里要用到kmp来找最小的循环节. 当然还有一种找循环节的方式就是预处理lcp,然后通过枚举循环节的方式. 这里我用的kmp找的循环节.复杂度严格n2. 1 #inclu

Educational Codeforces Round 23 E. Choosing The Commander (trie)

题目链接: Educational Codeforces Round 23 E. Choosing The Commander 题意: 一共有n个操作. 1.  插入一个数p 2.  删除一个数p 3.  询问有多少个数 使得 x^p<l 题解: 对于前两种操作用01trie就能解决. 对于对三个操作,我们考虑在trie上搜索. 1.  当l的bit位是1时,那边bit位是p的字数全部的数都会小于l,(因为p^p=0) 2.  当l的bit为是0时,那边只能向bit位是p的子树中搜. 这样算下来

Educational Codeforces Round 22 E. Army Creation(主席树)

题目链接:Educational Codeforces Round 22 E. Army Creation 题意: 给你n个数和一个数k,然后有q个询问. 每个询问 有一个区间[l,r],问你这个区间内在满足每一种数不超过k的情况下,最大能选多少个数出来. 强制在线. 题解: 一看就要用到主席树,和主席数求区间内有多少不同的数的个数处理方法相同. 依次将每个数插入,当这个数出现的个数等于k了,就把最前面的那个数删掉. 然后询问就访问root[r]就行了. 第一次写完数据结构没有调试一遍过样例,一