7月13日 Codeforces Round #496
题目链接:http://codeforces.com/contest/1005

A – Tanya and Stairways & B – Delete from the Left

过水,不多说。。。

C – Summarize to the Power of Two

思路:
$O(nlogn^2)$的比较暴力的做法,估计不是正解,水过去的QWQ

就是对于一个数$a[i]$,我们可以枚举所有的2的次幂,找到数组$a$在中是否有另一个数$a[j]$,使得它们和为2的次幂,这个可以用map维护。但是要注意一个细节就是a[i]本身是2的次幂,这个要特判一下。

代码:

#include <bits/stdc++.h>
#define MAXN 120005
using namespace std;

int n, a[MAXN], ans;
map<int, int> mmp;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        mmp[a[i]]++;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=30; j++)
            if(mmp.count((1<<j)-a[i]) && ((1<<j)!=a[i]*2 || mmp[a[i]]>1))
                {ans++; break;}
    printf("%d\n", n-ans);
}

D – D – Polycarp and Div 3

思路:
首先有一个引理:就是如果有一串长度大于3的数字它们和能被3整除,那么一定有一个连续字串的和也能被3整除。

这个比较显然,证明就不多说了。我们进行DP,根据上面的引理,每个$f[i]$会只从它前面的$f[i-1],f[i-2],f[i-3]$转移而来,所以就直接$O(n)$扫一遍就好了。(DP如何转移就看代码好了,比较简单)

代码:

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;

int n, cnt=1, ans, num[MAXN], f[MAXN][2];

int main()
{
    while(scanf("%1d", &num[cnt])!=EOF) cnt++;
    for(int i=1; i<cnt; i++) num[i]+=num[i-1];
    for(int i=1; i<cnt; i++)
        for(int j=max(i-3, 0); j<i; j++)
        {
            if((num[i]-num[j])%3==0) f[i][1]=max(f[i][1], f[j][1]+1);
            else f[i][1]=max(f[i][1], f[j][1]);
        }
    printf("%d\n", f[cnt-1][1]);
}

E1 – Median on Segments (Permutations Edition)

思路:
这题我的思路和题解的也不太一样。(其实是当时想一口气做出两个来,结果发现这个思路E2有BUG)

首先我们对于序列中数的大小是不关心的,只关系它与k的关系。所以可以把比k小的看成-1,比k大的看成1,然后维护前缀和,记为num[i]。我们同样记录k的位置pos,那么答案就是在pos两边有多少对i,j使得$num[i]=num[j]$或$num[i]=num[j]+1$。所以我们cnt数组记录在pos前$num[i]$的数量,对于pos后的$num[i]$就将$cnt[num[i]]$和$cnt[num[i]-1]$加入答案。

代码:

#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, k, pos=MAXN, a[MAXN], num[MAXN], cnt[MAXN*2];
LL ans;

int main()
{
    scanf("%d%d", &n, &k);
    cnt[n]=1;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i]==k) pos=i;
        if(a[i]<k) num[i]=-1;
        if(a[i]==k) num[i]=0;
        if(a[i]>k) num[i]=1;
        num[i]+=num[i-1];
        if(i<pos) cnt[num[i]+n]++;
    }
    for(int i=pos; i<=n; i++) ans+=cnt[n+num[i]], ans+=cnt[n+num[i]-1];
    printf("%lld\n", ans);
}

E2 – Median on Segments (General Case Edition)

思路:
这道题自然是没有想到的QWQ…..膜了下题解

由于直接求中位数为m的序列是不好求的,所以我们可以变一下,求中位数大于m的序列。那么答案就是做一个容斥,为中位数大于m的序列—中位数大于m+1的序列。

那么求中位数大于m的序列的做法和上一题我的做法有些相似。$num$是前缀和,$cnt$数组记录数量,由于长度为偶数时中位数是中间较小的那个,所以操作的顺序是不一样的。

代码:

#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, m, a[MAXN];
LL num, cnt[MAXN*2];

LL solve(int m)
{
    LL ans=0, add=0;
    memset(cnt, 0, sizeof(cnt));
    num=n; cnt[num]=1;
    for(int i=1; i<=n; i++)
    {
        if(a[i]<m) num--, add-=cnt[num];
        else add+=cnt[num], num++;
        ans+=add;
        cnt[num]++;
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    printf("%lld\n", solve(m)-solve(m+1));
}

F – Berland and the Shortest Paths

思路:
用BFS一遍处理出每个点深度,用个vector记录每个点连向父亲的边(可能有多个父亲)。因为每个点vector中存的边可以随便取,所以用dfs乱搞一下计算出答案。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#define MAXN 200005
using namespace std;

int n, m, k, ans, cnt=1, head[MAXN], dep[MAXN], temp[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

vector<int> pre[MAXN], path[MAXN];
queue<int> q;

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void bfs()
{
    memset(dep, 0x3f, sizeof(dep));
    q.push(1); dep[1]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dep[to]>dep[x]+1)
            {
                dep[to]=dep[x]+1;
                q.push(to);
            }
            if(dep[to]==dep[x]+1) pre[to].push_back(i);
        }
    }
}

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=0; i<m; i++) path[ans].push_back(temp[i]);
        ans++;
        return;
    }
    for(int i=0; i<pre[x].size(); i++)
    {
        temp[pre[x][i]/2-1]=1;
        dfs(x+1);
        if(ans==k) return;
        temp[pre[x][i]/2-1]=0;
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    bfs();
    dfs(2);
    printf("%d\n", ans);
    for(int i=0; i<ans; i++)
    {
        for(int j=0; j<m; j++) printf("%d", path[i][j]);
        printf("\n");
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注