首页 > 代码库 > codeforces Technocup 2017 - Elimination Round 2/Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) 题解

codeforces Technocup 2017 - Elimination Round 2/Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) 题解

久违的下午场,打了一场状态不错一下rank12涨了207~~~

A. Interview with Oleg

题意:

给你一个长度不超过100的串,把其中ago开头后面不接或者接gogogo。。。的部分全部变成***

思路:

水水,扫

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=5e5+10;
char s[110];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    int p=1;
    while(p<=n)
    {
        if(p<=n-2&&s[p]==o&&s[p+1]==g&&s[p+2]==o)
        {
            printf("***");
            p=p+3;
            while(p<n&&s[p]==g&&s[p+1]==o) p+=2;
            continue;
        }
        printf("%c",s[p]);
        p++;
    }
    return 0;
}
View Code

B. Spotlights

题意:

给你一个1000*1000的01矩阵,在0的地方可以四向看,只要能看到1,ans就+1

思路:

预处理行和列的前缀和,当时脑子短路,直接四个数组记得。。用两个数组然后行/列末减当前位置就可以判断后面的了

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e3+10;
int n,m;
int mp[N][N];
int sum[N][N],sum2[N][N],sum3[N][N],sum4[N][N];
int dfs(int x,int y)
{
    int ret=0;
    if(x>0&&sum2[x-1][y]) ret++;
    if(x<n&&sum4[x+1][y]) ret++;
    if(y>0&&sum[x][y-1])ret++;
    if(y<m&&sum3[x][y+1])ret++;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&mp[i][j]);
            sum[i][j]=sum[i][j-1]+mp[i][j];
            sum2[i][j]=sum2[i-1][j]+mp[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            sum3[i][j]=sum3[i][j+1]+mp[i][j];
            sum4[i][j]=sum4[i+1][j]+mp[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]==1) continue;
            ans+=dfs(i,j);
        }
    }
    printf("%d\n",ans);
    return 0;
}
View Code

C. Road to Cinema

题意:

给你n(2e5)辆车,k(2e5)个加油站,路程长度(1e9)和用时(1e9),

每辆车有花费(1e9)和油量(1e9)

每个加油站有个坐标(1e9),在加油站可以不用花费时间免费加满油,

有两种行进方式,正常方式是1公里耗2分钟和1升油,快速方式是1公里耗1分钟和2升油,

问你在规定用时内走完路程的最小花费,如果不能在规定时间内到达输出-1

思路:

容易看出,油量和耗时是反比例关系的,这样就可以二分最小的油量,然后扫一遍把油量大于等于这个值的花费里取最小值

当时没想好,追求速度,给车排了序。。还算说得过去吧~

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9;
const int N=2e5+10;
int n,k,s,t;
struct wq
{
    int c,v;
}a[N];
int g[N];
bool cmp(wq a,wq b)
{
    if(a.v!=b.v) return a.v<b.v;
    return a.c<b.c;
}
bool fun(int u)
{
    int now=0;
    LL tim=0;
    for(int i=0;i<=k;i++)
    {
        LL dis=g[i]-now;
        now=g[i];
        if(dis>u) return 0;
        if(u>=dis*2) tim+=dis;
        else tim=tim+3*dis-u;
        if(tim>t) return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&s,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].c,&a[i].v);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&g[i]);
    }
    g[0]=s;
    sort(g,g+k+1);
    sort(a+1,a+n+1,cmp);
    int l=1,r=mod,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(!fun(mid)) l=mid+1;
        else r=mid-1;
    }
    ans=l;
    if(a[n].v<ans) printf("-1\n");
    else
    {
        int pos=n,ret=inf;
        while(a[pos].v>=ans)
        {
            ret=min(ret,a[pos].c);
            pos--;
        }
        printf("%d\n",ret);
    }
    return 0;
}
View Code

D. Sea Battle

题意:

给你一个长度为n(2e5)的01串,1代表炮弹打过的地方,0代表没有打过

给你船的数量(n)和船长(n),表示这个区域内船的信息

问你至少要再打多少炮才能必中船?并输出打的位置(spj)

思路:

也就是让这个区域放不下这么多条船了

先扫一遍求一个当前区域能放的最大船数,然后这个值与船数-1做差即为开炮的数量

然后就在每个船的位置的最右端开一炮就好了,直到符合条件

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int n,a,b,k;
char s[N];
int main()
{
    scanf("%d%d%d%d",&n,&a,&b,&k);
    scanf("%s",s+1);
    int now=0,p=1;
    while(p<=n-b+1)
    {
        if(s[p]==1) {p++;continue;}
        int f=0;
        for(int i=p;i<p+b;i++)
            if(s[i]==1)
            {
                f=i;
                break;
            }
        if(!f) now++,p+=b;
        else p=f+1;
    }
    now=now-a+1;
    printf("%d\n",now);
    p=1;
    while(now--)
    {
        while(s[p]==1) p++;
        int f=0;
        for(int i=p;i<p+b;i++)
            if(s[i]==1)
            {
                f=i;
                break;
            }
        if(!f)
        {
            printf("%d ",p+b-1);
            p+=b;
            continue;
        }
        else
        {
            p=f+1;
            now++;
        }
    }
    return 0;
}
View Code

E. Subordinates

题意:

这题题意好难读啊(其实是英语弱233)

意思就是有n(2e5)个人和chief的位置s,然后给出你每个人的上司的数量,除了chief,每个人都有一个直接上司

问你最少改动多少个数使得这个数列是正确的

思路:

每个人都有直接上司也就是说,可以把关系看成一颗n叉树,树根为chief,然后每一层都至少有一个人

这样看就好办多了,先要把chief给确定,0只有1个而且要是s位置上,然后把大的数一直往前填小数的空档,直到形成一个连续的数列

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9;
const int N=2e5+10;
int vis[N];
int a[N];
int main()
{
    int n,s;
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]++;
    int ans=0;
    if(a[s]!=0)
    {
        vis[a[s]]--;
        ans++;
        a[s]=0;
        vis[0]++;
    }
    int p=1;
    while(vis[p]) p++;
    while(vis[0]>1)
    {
        ans++;
        vis[0]--;
        vis[p]++;
        while(vis[p]) p++;
    }
    int ed=n;
    while(ed>p)
    {
        while(ed>=0&&!vis[ed]) ed--;
        if(ed>p)
        {
            ans++;
            vis[ed]--;
            vis[p]++;
            while(vis[p]) p++;
        }
        while(ed>=0&&!vis[ed]) ed--;
    }
    printf("%d\n",ans);
    return 0;
}
View Code

F. Financiers Game

题意:

这道题场上没人过,我做完E只剩不到20分钟了,结果题没读出来- -

过后我花了好长时间才弄懂了样例,他说的意思简直。。。。。。

就是说有一个长度为4000的数列,两个人从这个数列中取数,

第一个人从左向右取,第二个人从右向左取,一开始只能取1或2个,然后下一次要跟上一次的人取得相同或多取一个

直到取完或者不够取就结束了,两个人博弈,第一个人要让两个人取得的值前者-后者最大,后者要让这个值最小,问你最后这个值为多少?

思路:

一个简单的博弈dp吧,可惜当时没有读出来,不然或许(此处省略一万字)。。。

就是一直向下枚举情况一直到最后一步,然后会有个固定的结果,然后返回上层,一般会有两个结果(k或k+1),然后根据当前人来选取最优的一个结果向上返回就可以了

注意要记忆化一下

技术分享
/* ***********************************************
Author        :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d\n",a)
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
template<class T>inline void rd(T &x)
{
    char c=getchar();
    x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-0;
        c=getchar();
    }
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9;
const int N=4e3+10;
const int M=100;
int n,dp[N][M][M][2],a[N];
int dfs(int l,int r,int k,int who)
{
    int &ret=dp[l][r-l][k][who];
    if(ret!=inf) return ret;
    if(!who)
    {
        if(l+k-1<=r)
        {
            ret=dfs(l+k,r,k,who^1)+a[l+k-1]-a[l-1];
            if(l+k<=r) ret=max(ret,dfs(l+k+1,r,k+1,who^1)+a[l+k]-a[l-1]);
        }
        else ret=0;
    }
    else
    {
        if(l+k-1<=r)
        {
            ret=dfs(l,r-k,k,who^1)-a[r]+a[r-k];
            if(l+k<=r) ret=min(ret,dfs(l,r-k-1,k+1,who^1)-a[r]+a[r-k-1]);
        }
        else ret=0;
    }
    return ret;
}
int main()
{
    memset(dp,inf,sizeof(dp));
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]),a[i]+=a[i-1];
    printf("%d\n",dfs(1,n,1,0));
    return 0;
}
View Code

 

codeforces Technocup 2017 - Elimination Round 2/Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) 题解