首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【Mutual Training for Wannafly Union #1 】

【Mutual Training for Wannafly Union #1 】

作者头像
饶文津
发布2020-06-02 11:11:23
3370
发布2020-06-02 11:11:23
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

A.Phillip and Trains

CodeForces 586D

题意:过隧道,每次人可以先向前一格,然后向上或向下或不动,然后车都向左2格。问能否到达隧道终点。

题解:dp,一开始s所在列如果前方为'.'则dp[i]=1。r[i]代表上一次的dp[i]值。

如果该行当前可行,那么它就可以更新它上下两行(如果有),必须用r[i]去更新。

再判断每行在当前时间是否会发生撞车:看看位置 i+t*2,i+t*2+1,i+t*2+2 是否有车。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
int t,n,k,dp[5],r[5];
char s[4][101];
bool ck(int i,int j){//j行i列不可行
    return i<n&&s[j][i]!='.';
}
int main() {
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=3;i++){
            scanf("%s",s[i]);
            r[i]=dp[i]=s[i][1]=='.'&&s[i][0]=='s';
        }
        for(int t=0,i=1;i<n;i++,t++){
            for(int j=1;j<=3;j++)if(!ck(i+t*2,j)){
                dp[j+1]=max(r[j],dp[j+1]);
                dp[j-1]=max(r[j],dp[j-1]);
            }
            for(int j=1;j<=3;r[j]=dp[j],j++)
            if(ck(i+t*2,j)||ck(i+t*2+1,j)||ck(i+t*2+2,j))
                dp[j]=0;
        }
        if(dp[1]||dp[2]||dp[3])puts("YES");
        else puts("NO");
    }
    return 0;
}

B - Mr. Kitayuta's Gift

CodeForces 505A

题意:插入一个字符是否能使字符串变成回文串。

题解:长度10,可以暴力枚举所有位置所有字母。我是用O(n)的算法。代码写得比较奇怪。

#include<cstdio>
#include<cstring>
char s[15];
int main(){
    scanf("%s",s);
    int len=strlen(s),i=0,j;
    for(;i<len/2&&s[i]==s[len-i-1];i++);
    if(s[i]!=s[len-i-1]){//如果有不同的
        for(j=i;j<len/2&&s[j]==s[len-j-2];j++);
        //尝试在i前面插入一个s[len-i-1]后是否变成回文
        if(j==len/2) printf("%.*s%c%s",i,s,s[len-i-1],s+i);
        else{
//尝试在len-i-1后面插入一个s[i]是否变成回文
            for(j=i+1;j<=len/2&&s[j]==s[len-j];j++);
            if(j>len/2)
                printf("%.*s%c%s",len-i,s,s[i],s+len-i);
            else printf("NA");
        }
    }else printf("%.*s%c%s",len/2,s,s[len/2],s+len/2);
    //本身是回文,只要中间插入一个s[len/s]
    return 0;
}    

D - Vasya and Chess

CodeForces 493D

题意:n*n的棋盘,白棋先动,可以走没走过的位置或吃黑棋,八方向。如果最后谁先不能走就输了。求白棋能否胜利,若能输出她的第一步。

题解:如果n是奇数,白棋走了,黑棋对称着走就可以了。所以黑棋必胜。n是偶数,白棋右走一步后,相当于奇数棋盘的后手了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    if(n%2){
        printf("black");
    }else
        printf("white\n1 2");
    return 0;
}

E - Bishops Alliance

Gym 101147F

题意:n*n的棋盘上有m个主教,告诉你每个主教的x,y坐标,和p值。你可以选取一些主教,使得选择的任意两个主教i和主教j之间满足:在同一对角线上,且dis(i,j)≥p_i^2+p_j^2+C,C是告诉你的一个常数,dis(i,j)=|x_i-x_j|+1。问最多可以选取多少个主教。

题解:

dp。对于一条对角线上的点按x排序后,dp[i]表示第i个点为最后一个选的点,最多可以取多少个点。

dis(i,j)=x_i-x_j+1\geq p_i^2+p_j^2+C\ (j<i)

移项后得

x_i-p_i^2-C+1\geq x_j+p_j^2 \tag1\ (j<i)

将该对角线上每个点的x-p^2-C+1,x+p^2离散化一下。那么dp[i]=dp[j]+1,dp[j]是j 满足(1)的最大的dp值。

所以用树状数组维护一下。

pos(v)表示v是离散后第几大的,qry(x)为最大的dp[j],其中j满足x_j+p_j^2在前x个离散后的值中,且j<i。

所以dp[i]=qry(pos(x_i-p_i^2-c+1))+1

每次求完dp[i],再update(pos(x+p2),dp[i]),就可以保证qry(x)的j一定<i。

update函数即更新 前x个的最大dp值(x大于等于pos(x+p2))。

#include<bits/stdc++.h>
#define N 270005
#define ll long long
using namespace std;
vector<pair<int,ll> >dia[N],rdia[N];
int n,m,c,len;
int s[N];
ll z[N];
int lowbit(int x){return x&(-x);}
int qry(int x){
    int ans=0;
    for(;x;x-=lowbit(x))ans=max(ans,s[x]);
    return ans;
}
void update(int x,int v){
    for(;x<N;x+=lowbit(x))s[x]=max(s[x],v);
}
int pos(ll v){
    return lower_bound(z,z+len,v)-z;
}
int solve(vector<pair<int,ll> > &v){
    if(!v.size())return 0;
    len=0;
    for(int i=0;i<v.size();i++){
        ll x=v[i].first,p2=v[i].second;
        z[len++]=x-p2-c+1;
        z[len++]=x+p2;
    }
    z[len++]=-1e18;
    sort(z,z+len);
    len=unique(z,z+len)-z;
    sort(v.begin(),v.end());
    for(int i=0;i<=len;i++)s[i]=0;
    int ans=0,dp;
    for(int i=0;i<v.size();i++){
        ll x=v[i].first,p2=v[i].second;
        dp=qry(pos(x-p2-c+1))+1;
        ans=max(ans,dp);
        update(pos(x+p2),dp);
    }
    return ans;
}
int main(){
    freopen("bishops.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&c);
        for(int i=0;i<=2*n;i++)
            dia[i].clear(),rdia[i].clear();
        for(int i=0;i<m;i++){
            int x,y;ll p;
            scanf("%d %d %I64d",&x,&y,&p);
            dia[x+y].push_back(make_pair(x,p*p));
            rdia[x-y+n].push_back(make_pair(x,p*p));
        }
        int ans=0;
        for(int i=0;i<=2*n;i++){
            ans=max(ans,solve(dia[i]));
            ans=max(ans,solve(rdia[i]));
        }
        printf("%d\n",ans);
    }
    return 0;
}

F - Guess a number!

CodeForces 416A

题意:四种猜数字方式和两种回答:>=/<=/>/< d Y/N ,给出多个这样的问答,求任意一个符合条件的数字。

题解:二分,改变l的条件是有'>',回答是Y,或者有<回答是N,可以异或一下。然后是开区间还是闭区间,就看是否有'=',回答是Y,或者没有'=',回答是N,也可以异或一下。注意l和r的初始值。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 2000000000
char s[10];
int n,ans,d,l=-inf,r=inf;
void work(int i,int j){
    if(i)l=max(l,d+j);
    else r=min(r,d-j);
}
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%s %d %c",s,&d,&s[2]);
        work((s[0]=='>')^(s[2]=='N'),(s[1]=='=')^(s[2]=='Y'));
        if(l>r)ans=-1;
    }
    if(ans==-1)printf("Impossible");
    else printf("%d",l);
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-11-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • A.Phillip and Trains
  • B - Mr. Kitayuta's Gift
  • D - Vasya and Chess
  • E - Bishops Alliance
  • F - Guess a number!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档