文档章节

【codeforces】Codeforces Round #372 (Div. 2)

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 2944
阅读 3
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

B

题目大意

给定一个字符串,他忘了其中的一些个字母是什么,求问能否修改‘?’处的字母使得存在一个 长度为26的字串 其中正好有26个字母,如果可以,输出一组解


……好难
做题的时候没看到长度为26然后WA了还不知所踪……还是要好好审题
恩恩
我选择题解


第一种做法

注意到当且仅当存在一段长度为26的字符串,在这个字串里每个字符出现次数 <= 1,那么就是有解的

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
bool can(int x)
{
    for(int i = 0;i < 26;i ++)
        if(tong[c[x - i] - 'A'] > 1)
            return false;
    return true;
}
void fillall()
{
    for(int i = 0;i < n;i ++)
        if(c[i] == '?')
            c[i] = 'A';
    return;
}
int main()
{
    gets(c);
    n = strlen(c);
    if(n < 26)
    {
        puts("-1");
        return 0;
    }
    for(int i = 0;i < 25;i ++)
        if(isalpha(c[i]))
            tong[c[i] - 'A'] ++;
    for(int i = 25;i < n;i ++)
    {
        if(isalpha(c[i - 26]))
            tong[c[i - 26] - 'A'] --;
        if(isalpha(c[i]))
            tong[c[i] - 'A'] ++;
        if(can(i))
        {
            int cha = 0;
            while(tong[cha])
                cha ++;
            for(int j = i - 25;j <= i;j ++)
            {
                if(!isalpha(c[j]))
                    c[j] = cha + 'A',tong[cha] ++;
                while(tong[cha])
                    cha ++;
            }
            fillall();
            puts(c);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

好吧……访问负数内存不会越界……
不过还是别这样打……
看官方的

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 10000;
int cnt[27];
string s; int n;

bool valid()
{
    for(int i = 0; i < 26; i++)
    {
        if(cnt[i] >= 2) return false;
    }
    return true;
}

void fillall()
{
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '?') s[i] = 'A';
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.length();
    if(n < 26) {cout << -1; return 0;}
    for(int i = 25; i < n; i++)
    {
        memset(cnt, 0, sizeof(cnt));
        for(int j = i; j >= i - 25; j--)
        {
            cnt[s[j]-'A']++;
        }
        if(valid())
        {
            //cout << "GG " << i << '\n';
            int cur = 0;
            while(cnt[cur]>0) cur++;
            for(int j = i - 25; j <= i; j++)
            {
                if(s[j] == '?')
                {
                    s[j] = cur + 'A';
                    cur++;
                    while(cnt[cur]>0) cur++;
                }
            }
            fillall();
            cout << s;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

第二种做法

……md没区别……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
bool can(int x)
{
    for(int i = 0;i < 26;i ++)
        if(tong[c[x - i] - 'A'] > 1)
            return false;
    return true;
}
void fillall()
{
    for(int i = 0;i < n;i ++)
        if(c[i] == '?')
            c[i] = 'A';
    return;
}
int main()
{
    gets(c);
    n = strlen(c);
    if(n < 26)
    {
        puts("-1");
        return 0;
    }
    for(int i = 0;i < 26;i ++)
        if(isalpha(c[i]))
            tong[c[i] - 'A'] ++;
    if(can(25))
    {
        int cha = 0;
        while(tong[cha])
            cha ++;
        for(int j = 0;j <= 25;j ++)
        {
            if(!isalpha(c[j]))
                c[j] = cha + 'A',tong[cha] ++;
            while(tong[cha])
                cha ++;
        }
        fillall();
        puts(c);
        return 0;
    }
    for(int i = 26;i < n;i ++)
    {
        if(isalpha(c[i - 26]))
            tong[c[i - 26] - 'A'] --;
        if(isalpha(c[i]))
            tong[c[i] - 'A'] ++;
        if(can(i))
        {
            int cha = 0;
            while(tong[cha])
                cha ++;
            for(int j = i - 25;j <= i;j ++)
            {
                if(!isalpha(c[j]))
                    c[j] = cha + 'A',tong[cha] ++;
                while(tong[cha])
                    cha ++;
            }
            fillall();
            puts(c);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

第三种做法

考虑到我们将大量时间(26)用在了判断这个字串是否合适上,所以我们做出一些改动,我们不再扫描一遍得到判断,而是通过记录当前区间内的种类数来直接进行判断
新开一个变量表示种类数,如果桶里面减没了就–如果新加入的不在桶里那就++

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
int z; 
bool can(int x)
{
    return z == 26;
}
void fillall()
{
    for(int i = 0;i < n;i ++)
        if(c[i] == '?')
            c[i] = 'A';
    return;
}
int main()
{
    gets(c);
    n = strlen(c);
    if(n < 26)
    {
        puts("-1");
        return 0;
    }
    for(int i = 0;i < 26;i ++)
        if(isalpha(c[i]))
            z += !tong[c[i] - 'A'],tong[c[i] - 'A'] ++;
        else
            z ++;
    if(can(25))
    {
        int cha = 0;
        while(tong[cha])
            cha ++;
        for(int j = 0;j <= 25;j ++)
        {
            if(!isalpha(c[j]))
                c[j] = cha + 'A',tong[cha] ++;
            while(tong[cha])
                cha ++;
        }
        fillall();
        puts(c);
        return 0;
    }
    for(int i = 26;i < n;i ++)
    {
        if(isalpha(c[i - 26]))
            z -= !(-- tong[c[i - 26] - 'A']);
        if(isalpha(c[i]))
            z += !(tong[c[i] - 'A'] ++);
        if(c[i] == '?')
            z ++;
        if(c[i - 26] == '?')
            z --;
        if(can(i))
        {
            int cha = 0;
            while(tong[cha])
                cha ++;
            for(int j = i - 25;j <= i;j ++)
            {
                if(!isalpha(c[j]))
                    c[j] = cha + 'A',tong[cha] ++;
                while(tong[cha])
                    cha ++;
            }
            fillall();
            puts(c);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

代码依旧丑的要死……
╮(╯▽╰)╭

现在看来这个题还挺日常的……
QAQ
总的来说就是 O(26|S|)O(|S|2)

D

题目大意

现在有一张n个点m条边的无向图,有一些边的权重是不一定的现在问你是否存在一种方案,使得从s跑到e的最短路恰好为L,输出一张图


首先来确定是否存在可行解,将权重不一定的边称之为 可变边
比较显然的结论是
1、如果不考虑可变边,从s到t的最短路小于L的话,那么输出NO

接下来是翻译题解
2、将所有可变边的权值赋为1,显然,这是在所有可以从原图变化而来的图中从s到e的最短路最短的一张图,如果这张图从s到e的最短路仍然大于L,那么输出NO

3、如果不属于以上两种情况,那么我们就可以通过分配权值使得从s到e的最短路长度恰好为L
为什么?

First, consider all paths from s to e that has at least one 0 weight edge, as changing weights won’t affect the other paths.
好吧上面那句话不懂什么意思……我继续了
现在,我们重复这个算法,首先,将所有的可变边的权值赋为1,然后,将所有的路径按长短递增排序,如果最短路的长度是L,那么我们就可以输出结果了。否则,使最短路中的某一条可变边的权值增加1,那么就会有一些路径他们的权值会增加1。不难看出,通过重复这个算法就可以使得最短路的长度恰好为L

//嗯……还好理解
现在我们仍然需要找到一个有效的分配方案,我们可以用一个和刚刚我们证明的算法类似的算法。
将所有的边的权值增加1,然后我们先找到并且保存最短路的路径,注意,如果这条路径上没有可变边那么它的长度一定是大于等于L的(由1得),也就是说要么我们已经找到了答案要么最短路里有可变边并且它的长度小于L(否则我们就已经得到了答案)
从现在开始,无论我们何时向一条可变边上分配权值(在赋值为1之后),我们就称这条边为 钦定的
现在, 钦定所有不在最短路上的可变边的权值为INF (INF可以定义为任何大于L的值),然后我们就可以找到那条从s到e的最短路,然后将一条没有钦定的边的权值修改为使得这条最短路的长度恰好为L,然后我们就不再碰这条边了。然后重复这个算法直到找到解(不是只钦定一条边就行么?)
如上
代码(WA)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL MAXN = 1000 + 5;
const LL MAXM = 10000 + 5;
const LL INF = 1e18;
struct edge
{
    LL f,t,v;
    bool is_0,is_qd;
}l[MAXM << 1];
LL first[MAXN],next[MAXM << 1],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(LL f,LL t,LL v,bool zer0)
{
    l[++tot] = (edge){f,t,v,zer0,false};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
struct zt
{
    LL u,v;
    bool operator < (const zt &b)const
    {
        return v > b.v;
    }
};
priority_queue <zt> q;
LL dis[MAXN],done[MAXN];
LL last[MAXN];
void dij(LL s,LL e)
{
    memset(dis,0x3f,sizeof(dis));
    memset(done,0,sizeof(done));
    while(!q.empty())
        q.pop();
    dis[s] = 0;
    q.push((zt){s,0});
    while(!q.empty())
    {
        zt x = q.top();
        q.pop();
        LL u = x.u;
        if(done[u])
            continue;
        done[u] = true;
        if(u == e)
            return;
        for(int i = first[u];i != -1;i = next[i])
        {
            LL v = l[i].t;
            if(dis[v] > dis[u] + l[i].v)
            {
                dis[v] = dis[u] + l[i].v;
                q.push((zt){v,dis[v]});
            }
        }
    }
    return;
}
LL dist[MAXN];
void dij_remember(int s,int e)
{
    memset(dist,0x3f,sizeof(dist));
    memset(done,0,sizeof(done));
    while(!q.empty())
        q.pop();
    dist[s] = 0;
    q.push((zt){s,0});
    last[s] = -1;
    while(!q.empty())
    {
        zt x = q.top();
        q.pop();
        LL u = x.u;
        if(done[u])
            continue;
        done[u] = true;
        if(u == e)
            return;
        for(int i = first[u];i != -1;i = next[i])
        {
            LL v = l[i].t;
            if(dist[v] > dist[u] + l[i].v)
            {
                dist[v] = dist[u] + l[i].v;
                last[v] = i;
                q.push((zt){v,dist[v]});
            }
        }
    }
    return;
}
LL another(LL x)
{
    if(x & 1)
        return x + 1;
    else
        return x - 1;
}
LL n,m,L,s,e;
LL f,t,v;
int main()
{
    init();
    scanf("%I64d %I64d %I64d %I64d %I64d",&n,&m,&L,&s,&e);
    for(int i = 1;i <= m;i ++)
    {
        bool flag = false;
        scanf("%I64d %I64d %I64d",&f,&t,&v);
        if(!v)
            v = INF,flag = true;
        build(f,t,v,flag);
        build(t,f,v,flag);
    }
    dij(s,e);
    if(dis[e] < L)
    {
        puts("NO");
        return 0;
    }
    for(int i = 1;i <= tot;i ++)
        if(l[i].is_0)
            l[i].v = 1;
    dij_remember(s,e);
    if(dist[e] > L)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    LL k = last[e];
    while(~k)
    {
        if(l[k].is_0)
            l[k].is_qd = l[another(k)].is_qd = true;
        k = last[l[k].f];
    }
    for(int i = 1;i <= tot;i ++)
        if(l[i].is_0 && !l[i].is_qd)
            l[i].v = l[another(i)].v = INF;
    k = last[e];
    for(int i = 1;i <= tot;i ++)
    {
        if(l[i].is_qd)
        {
            l[i].v = l[another(i)].v = INF;
            dij(s,e);
            if(dis[e] > L)
            {
                l[i].v = l[another(i)].v = L - dist[e] + 1;
                break;
            }
            else
                l[i].v = l[another(i)].v = 1;
        }
    }
    for(int i = 1;i <= tot;i += 2)
        printf("%I64d %I64d %I64d\n",l[i].f,l[i].t,l[i].v);
    return 0;
}

A:停停停停停!这是不对的!你不碰这条边的时候不能把它重置成1而是要让它是INF!!

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

哦哦哦好像是这样……我说怎么总是WA on 22……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL MAXN = 1000 + 5;
const LL MAXM = 10000 + 5;
const LL INF = 1e18;
struct edge
{
    LL f,t,v;
    bool is_0,is_qd;
}l[MAXM << 1];
LL first[MAXN],next[MAXM << 1],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(LL f,LL t,LL v,bool zer0)
{
    l[++tot] = (edge){f,t,v,zer0,false};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
struct zt
{
    LL u,v;
    bool operator < (const zt &b)const
    {
        return v > b.v;
    }
};
priority_queue <zt> q;
LL dis[MAXN],done[MAXN];
LL last[MAXN];
void dij(LL s,LL e)
{
    memset(dis,0x3f,sizeof(dis));
    memset(done,0,sizeof(done));
    while(!q.empty())
        q.pop();
    dis[s] = 0;
    q.push((zt){s,0});
    while(!q.empty())
    {
        zt x = q.top();
        q.pop();
        LL u = x.u;
        if(done[u])
            continue;
        done[u] = true;
        if(u == e)
            return;
        for(int i = first[u];i != -1;i = next[i])
        {
            LL v = l[i].t;
            if(dis[v] > dis[u] + l[i].v)
            {
                dis[v] = dis[u] + l[i].v;
                q.push((zt){v,dis[v]});
            }
        }
    }
    return;
}
LL dist[MAXN];
void dij_remember(int s,int e)
{
    memset(dist,0x3f,sizeof(dist));
    memset(done,0,sizeof(done));
    while(!q.empty())
        q.pop();
    dist[s] = 0;
    q.push((zt){s,0});
    last[s] = -1;
    while(!q.empty())
    {
        zt x = q.top();
        q.pop();
        LL u = x.u;
        if(done[u])
            continue;
        done[u] = true;
        if(u == e)
            return;
        for(int i = first[u];i != -1;i = next[i])
        {
            LL v = l[i].t;
            if(dist[v] > dist[u] + l[i].v)
            {
                dist[v] = dist[u] + l[i].v;
                last[v] = i;
                q.push((zt){v,dist[v]});
            }
        }
    }
    return;
}
LL another(LL x)
{
    if(x & 1)
        return x + 1;
    else
        return x - 1;
}
LL n,m,L,s,e;
LL f,t,v;
int main()
{
    init();
    scanf("%I64d %I64d %I64d %I64d %I64d",&n,&m,&L,&s,&e);
    for(int i = 1;i <= m;i ++)
    {
        bool flag = false;
        scanf("%I64d %I64d %I64d",&f,&t,&v);
        if(!v)
            v = INF,flag = true;
        build(f,t,v,flag);
        build(t,f,v,flag);
    }
    dij(s,e);
    if(dis[e] < L)
    {
        puts("NO");
        return 0;
    }
    for(int i = 1;i <= tot;i ++)
        if(l[i].is_0)
            l[i].v = 1;
    dij_remember(s,e);
    if(dist[e] > L)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    LL k = last[e];
    while(~k)
    {
        if(l[k].is_0)
            l[k].is_qd = l[another(k)].is_qd = true;
        k = last[l[k].f];
    }
    for(int i = 1;i <= tot;i ++)
        if(l[i].is_0 && !l[i].is_qd)
            l[i].v = l[another(i)].v = INF;
    k = last[e];
    for(int i = 1;i <= tot;i ++)
    {
        if(l[i].is_qd)
        {
            l[i].v = l[another(i)].v = INF;
            dij(s,e);
            if(dis[e] > L)
            {
                l[i].v = l[another(i)].v = 1;
                dij(s,e);
                l[i].v = l[another(i)].v = L - dis[e] + 1;
                break;
            }
        }
    }
    for(int i = 1;i <= tot;i += 2)
        printf("%I64d %I64d %I64d\n",l[i].f,l[i].t,l[i].v);
    return 0;
}

P.S
如果 n,m100000 呢?我们能做的更好么?

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
Codeforces Round #500 (Div. 2) BC

CodeForces 1013B And CodeForces 1013C Photo of The Sky B 可以发现只有一次与操作是有意义的,所以答案只有-1,0,1,2四种情况 2 #define show(a) cout << #a << " = " << a << endl; 3 ......

cjc7373
2018/07/30
0
0
Codeforces Round #510 (Div. 2) A - Benches

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82757408 Codeforces Round #510 (Div. 2) A - Ben...

bryce1010
2018/09/18
0
0
【水题】Codeforces Round #510 (Div. 2) B. Vitamins

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82757470 Codeforces Round #510 (Div. 2) B. Vita...

bryce1010
2018/09/18
0
0
Codeforces积分系统介绍

一、艾洛积分系统(Elo Ranking System) 请参考 https://blog.csdn.net/haishu_zheng/article/details/80480284 二、Codeforces积分系统 类似于艾洛积分系统,但是具体算法没公布。 详情请参考...

海天一树X
2018/05/28
0
0
Educational Codeforces Round 72 (Rated for Div. 2)-D. Coloring Edges-拓扑排序

Educational Codeforces Round 72 (Rated for Div. 2)-D. Coloring Edges-拓扑排序 【Problem Description】 给你一个有向图,给用最少的颜色给每条边染色,要保证不存在一个环中的所有边都是...

__Simon
09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx反向代理+负载均衡+服务器宕机解决办法

反向代理 作用:保证系统安全,不暴露服务器IP,利用nginx服务器,利用内网ip进行访问,避免出现攻击服务器的情况 启动本地tomact,127.0.0.1:8080可以访问到tomcat管理页面 效果:通过 bbs....

Jack088
11分钟前
2
0
返回IEnumerable 与IQueryable相比 [关闭]

返回IQueryable<T>与IEnumerable<T>之间有什么区别? IQueryable<Customer> custs = from c in db.Customerswhere c.City == "<City>"select c;IEnumerable<Customer> custs = from c i......

技术盛宴
18分钟前
2
0
开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后,就得到了广大开发者的密切关注。Knative 在 Kubernetes 之上提供了一套完整的应用 Serverless 编排服务,让应用开发...

阿里巴巴云原生
22分钟前
2
0
解密淘宝推荐实战,打造 “比你还懂你” 的个性化APP

手淘推荐简介 手淘推荐的快速发展源于2014年阿里“All in 无线”战略的提出。在无线时代,手机屏幕变小,用户无法同时浏览多个视窗,交互变得困难,在这样的情况下,手淘借助个性化推荐来提升...

阿里云官方博客
25分钟前
2
0
内核程序中进程的pid,handle,eprocess之间相互转换的方法

在内核程序开发中,我们常常需要取得某进程的pid或句柄,或者需要检索进程的eprocess结构,很多API函数需要的参数也不同,所以掌握pid<->handle<->eprocess相互转换的方法会大大提高我们的开...

simpower
26分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部