WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Litsey o`quvchilar uchun 解题报告
Litsey o`quvchilar uchun 解题报告

这是一套比较基础的程序设计代码练习题,CF的GYM地址:http://codeforces.com/gym/101306

A. Palindrome Password

题意:给你一个只包含0-9的数位非递减字符串,让你求得符合要求的子串满足子串回文且长度尽可能的长,并且按照字典序输出所有可能情况。

题解:满足数位递增且又是回文,那么这个子串的每一位应该都是相同的。所以,我们只需要线性扫描一遍字符串,统计一下最长的相邻位相同子串的长度,然后再线性扫描一遍输出所有可能即可。

#include <cstdio>
#define LL long long
using namespace std;

const int Maxn=1e5;
int num[Maxn+5];
int n;

int main(){

    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%1d",&num[i]);

    int maxLen=0,nowLen=0,cnt=0;
    for (int i=1;i<=n;i++){
        if (i==1 || num[i]!=num[i-1]) nowLen=1; else nowLen++;
        if (maxLen<nowLen) {
            maxLen=nowLen;
            cnt=1;
        }else if (maxLen==nowLen) cnt++;
    }

    printf("%d\n",cnt);
    for (int i=1;i<=n;i++){
        if (i==1 || num[i]!=num[i-1]) nowLen=1; else nowLen++;
        if (maxLen==nowLen){
            for (int j=1;j<=maxLen;j++) printf("%d",num[i]);
            printf("\n");
        }
    }

    return 0;
}

B. Chocolate

题意:你有k个各种牌子的巧克力,要分给n个人类,m个火星人一人一个,其中需要注意的时火星人不要Mars牌子的巧克力.现在问你要满足所有人,最少要购买多少个巧克力。

题解:因为火星人对巧克力挑食,所以我们先分配Mars牌子的巧克力给人类,然后再将其他巧克力分配给剩余的人,不够就购买。

#include <cstdio>
#include <map>
#include <string>
#include <iostream>
using namespace std;

int ans;
int k,n,m;
int mNum,cNum;
string str;

int main(){
    //freopen("in.txt","r",stdin);

    mNum=cNum=0;
    scanf("%d%d%d",&k,&n,&m);
    for (int i=1;i<=k;i++){
        cin>>str;
        if (str=="Mars") mNum++; else cNum++;
    }

    if (n>=mNum) n-=mNum; else n=0;
    printf("%d\n",max(0,n+m-cNum));
    return 0;
}

C. Art Museum

题意:一共有n个星系,每个星系每天有一个开放时间[a_i, b_i) 。问同一时间最多有多少个星系开放。

题解:因为星系数量和时间点数量很少,所以直接暴力对每个小时统计这个时间开放的星系数量即可,然后扫描一下时间,找一个最大的即可。

#include <cstdio>
#include <iostream>

using namespace std;

const int Maxn=1e5;

int n;
int cnt[25];

int main(){
    //freopen("in.txt","r",stdin);

    scanf("%d",&n);

    for (int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        for (int j=l;j<r;j++) cnt[j]++;
    }

    int maxAns=0;
    for (int i=0;i<24;i++) maxAns=max(maxAns,cnt[i]);

    printf("%d\n",maxAns);
    return 0;
}

D. Translation

题意:有一个26大小写字母的自一一映射,现在给你一段英文,让你进行翻译。

题解:样例非常多,基本可以获得自一一映射的所有规则,然后直接翻译输出即可。

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

map<char,char> tran;

void init(){
tran.clear();
tran['I']='v';
tran['u']='p';
tran['V']='V';
tran['E']='Z';
tran['J']='z';
tran['x']='B';
tran['T']='N';
tran['X']='t';
tran['s']='L';
tran['U']='S';
tran['v']='C';
tran['O']='u';
tran['H']='b';
tran['h']='W';
tran['n']='m';
tran['g']='a';
tran['y']='o';
tran['Z']='c';
tran['K']='I';
tran['f']='Y';
tran['A']='n';
tran['Y']='e';
tran['m']='A';
tran['a']='P';
tran['q']='q';
tran['o']='x';
tran['l']='D';
tran['M']='s';
tran['N']='h';
tran['t']='R';
tran['G']='k';
tran['Q']='M';
tran['i']='G';
tran['b']='g';
tran['w']='J';
tran['d']='f';
tran['j']='H';
tran['P']='r';
tran['r']='F';
tran['C']='U';
tran['p']='Q';
tran['e']='T';
tran['k']='j';
tran['F']='X';
tran['W']='O';
tran['z']='w';
tran['L']='d';
tran['a']='P';
tran['y']='o';
tran['S']='l';
tran['B']='y';
tran['a']='P';
tran['P']='r';
tran['y']='o';
tran['b']='g';
tran['R']='i';
tran['M']='s';
tran['g']='a';
tran['z']='w';
tran['Y']='e';
tran['M']='s';
tran['y']='o';
tran['n']='m';
tran['Y']='e';
tran['C']='U';
tran['A']='n';
tran['R']='i';
tran['S']='l';
tran['c']='E';
tran['a']='P';
tran['r']='F';
tran['s']='L';
tran['D']='K';
}

int n;
string str;

bool vis[255];

int main(){
    init();
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        cin>>str;
        int len=str.length();
        for (int j=0;j<len;j++) {
            printf("%c",tran[str[j]]);
        }
        if (i!=n) printf(" "); else printf("\n");
    }
    return 0;
}

E. Secret Passage

题意:坏人5分钟前从(0,0)出发去(n,m),好人现在从(0,0)出发去(n,m)。地图上有一些障碍物,两方都不能穿越,但是好人知道一些秘密通道可以穿越一些障碍物,现在问你好人能够先于坏人到达目的地。

题解:我们使用BFS求得从(0,0)到(n,m)使用秘密通道与不使用秘密通道的时间并进行比较即可。

#include <cstring>
#include <cstdio>
#include <queue>
#include <cstdlib>
#define mp(x,y) make_pair(x,y)
using namespace std;

const int Maxn=550;

int n,m,k;
int p[Maxn+5][Maxn+5];


inline int read(){
    char x=getchar();
    while(!(x=='.' || x=='x')) x=getchar();
    if (x=='.') return 2; else return 0;
}

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
bool vis[Maxn+5][Maxn+5];
int dis[Maxn+5][Maxn+5];
queue<pair<int,int> > que;

inline int bfs(bool flag){
    while(!que.empty()) que.pop();
    memset(dis,0,sizeof(dis));
    memset(vis,false,sizeof(vis));
    que.push(mp(1,1));
    vis[1][1]=true;

    while(!que.empty()){
        int x=que.front().first,y=que.front().second;que.pop();
        //printf("%d %d\n",x,y);
        for (int k=0;k<4;k++){
            //system("pause");
            int tx=x+dx[k],ty=y+dy[k];
            if (!(1<=tx && tx<=n && 1<=ty && ty<=m)) continue;
            if (vis[tx][ty]) continue;
            if (p[tx][ty]==0) continue;
            if (!flag && p[tx][ty]==1) continue;
            vis[tx][ty]=true;
            dis[tx][ty]=dis[x][y]+1;
            if (tx==n && ty==m) {
                //printf("%d\n",dis[tx][ty]);
                return dis[tx][ty]+(flag?5:0);
            }
            que.push(mp(tx,ty));
        }
    }
    //printf("Failed\n");
    return -1;
}

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) p[i][j]=read();
    for (int i=1;i<=k;i++){
        int x,y;scanf("%d%d",&x,&y);x++;y++;
        //printf("%d %d\n",x,y);
        p[x][y]=1;
    }
    int mAns=bfs(true);
    int tAns=bfs(false);
    if (mAns==-1 || (tAns!=-1 && mAns>=tAns)) puts("NO"); else puts("YES");
    return 0;
}

F. Wifi Trees

题意:有n棵WIFI树和m个火星人,一个火星人需要一颗专属的氧气树才能存活。现在我们要将若干颗WIFI树改为氧气树,每个活着的火星人的快乐值为当前所有WIFI树的信号速度之和乘x,问所有活着的火星人最大的快乐值之和是多少?

题解:假设当前改造p个WIFI树,那么总收益为min(m, p)\cdot (n-p) \cdot x。分情况讨论,当m>p时,p=\frac{n}{2}取极值,否则再p=m处取极值。

#include <cstdio>
#define LL unsigned long long
using namespace std;

LL n,m,x;

inline void solve(int T){
    scanf("%I64u%I64u%I64u",&n,&m,&x);
    if (n/2LL>=m)
        printf("%I64u %I64u\n",m,(LL)(n-m)*(LL)m*(LL)x);
    else
        printf("%I64u %I64u\n",n/2LL,(LL)(n-n/2LL)*(LL)(n/2LL)*(LL)x);
}

int main(){
    //freopen("in.txt","r",stdin);
    int T=0;
    scanf("%d",&T);
    for (int i=1;i<=T;i++) solve(i);
    return 0;
}

G. Pick Your Team

题意:n个选手,两队轮流pick,每队实力为选择选手的实力之和。好在你知道对方队伍选择人物的倾向列表。问如果你足够机智,那么你队与他队最大实力之差是多少。

题解:因为知道对方会怎么选择了,所以我们不着急一上来就选择实力最强的人,我们尽可能的剩给对方实力最弱的人即可。所以我们从实力强往实力弱枚举,如果当前这个选手在对方实力列表的第c位,且从开头到这个元素我们已经选择了k个选手。如果\frac{c-1}{2}\geq k,那么我们就可以选择这个选手,同时再check一下会不会影响之前的其他选择。如果可以选择,而且不会影响,则选择它,否则放弃。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;

const int Maxn=100;

int n;
struct StudentNode{
    int pwe;
    int idx;
};
StudentNode st[Maxn+5];
int order[Maxn+5];
bool vis[Maxn+5];
inline bool cmp(StudentNode a,StudentNode b){return a.pwe>b.pwe;}

LL Ans;

int main(){
    //freopen("in.txt","r",stdin);

    scanf("%d",&n);
    for (int i=1;i<=n;i++) st[i].idx=i;
    for (int i=1;i<=n;i++) scanf("%d",&st[i].pwe);
    for (int i=1;i<=n;i++) scanf("%d",&order[i]);
    sort(st+1,st+n+1,cmp);
    memset(vis,0,sizeof(vis));

    Ans=0;
    for (int i=1;i<=n;i++){
        bool flag=true;
        int pos=0,cnt=0;
        for(pos=1;order[pos]!=st[i].idx;pos++) if (vis[order[pos]]) cnt++;
        if ((pos-1)/2<cnt) flag=false;
        cnt++;
        for (pos=pos+1;pos<=n && flag;pos++)
            if (vis[order[pos]]){
                if ((pos-1)/2<cnt) flag=false;
                cnt++;
            }
        if (flag) {
            //printf("%d\n",st[i].pwe);
            Ans+=st[i].pwe;
            vis[st[i].idx]=true;
        }else Ans-=st[i].pwe;
    }

    printf("%I64d\n",Ans);
    return 0;
}

相关PPT:
解题报告
动态规划选讲

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Litsey o`quvchilar uchun 解题报告
这是一套比较基础的程序设计代码练习题,CF的GYM地址:http://codeforces.com/gym/101306 A. Palindrome Password 题意:给你一个只包含0-9的数位非递减字符串,让你求得符合要求的子串…
扫描二维码继续阅读
2018-08-05
<--! http2https -->