5.1比赛总结加解题报告

比赛成绩很差很差..8道题竟然只水出来三道,还有好几道题目也是水题,但是由于英语的原因,没看懂题目意思,然后坑了.

英语是硬伤啊,要抓紧时间提升英语水平啊,以后的题目都是全英文的,无奈之.

这次比赛用的题目是codeforces上的第245号比赛题,不过题目的顺序给挪动了.

写写解题报告把..我还是按照codeforces上的顺序来把.

A.System Administrator

题目描述：

Polycarpus有两个操作,分别是ping a服务器和ping b服务器
每一次ping都返回一对x,y,且x,y满足 $x+y==10, 10> x,y>=0$
每一对x,y表示每一次ping操作发出的10个数据包里有x个成功返回,y个包丢失.
对服务器alive的定义是,对该服务器发出的所有数据包中有一半成功返回,则代表该服务器live,否则dead.

输入格式：

第一行一个整数n,表示操作的次数
以下n行表示n次操作,每行三个整数,
第一个表示操作的种类,如果为1则表示ping a,否则ping b
第二个表示x
第三个表示y

输出格式：

输出两行,分别是服务器a和b的状态,alive输出LIVE,dead输出DEAD

数据保证：

$2 \leq n \leq 10000$

这道题就是一个大水题..统计x个y的和与操作的次数.然后判断输出就ok了

#include <cstdio>
int main(int argc, char const *argv[])
{
    int tot, a, b, aget, bget;
    a = b = aget = bget = 0;
    scanf("%d", &tot);
    for(int i = 0; i < tot; ++i){
        int flag, x ,y;
        scanf("%d%d%d", &flag, &x, &y);
        if(flag == 1){ aget += x; a++;}
        else { bget += x; b++; }
    }
    if(aget*2 >= a*10){ printf("LIVE\n");}
    else { printf("DEAD\n"); }
    if(bget*2 >= b*10){ printf("LIVE\n");}
    else { printf("DEAD\n"); }
    return 0;
}

B. Internet Address

题目描述：

定义一个网址的标准格式如下：
<protocol>://<domain>.ru[/<context>]
protocol是协议类型,只有两种ftp和http
domain是域名,不为空,这里有坑
context是资源文本,可以为空,为空则没有/,否则有/
现给出一个没有标点的网址字符串,要求还原成标准格式
例如
给定输入 httpsunrux
那么输出 http://sun.ru/x

输入格式：

一行字符串

输出格式：

一行字符串,如果多解,输入任意一个解即可

数据保证：

输入字符串长度不超过50,一定有解

一样的水题,不过我还是坑了一次..因为可能输出domain为空的情况

#include <cstdio>
int main(int argc, char const *argv[])
{
    int p = 0;  char s[100]; gets(s);
    if(*s=='h'){ printf("http://");p = 4;   }
    else { printf("ftp://"); p = 3; }
    do { putchar(s[p++]);} 
    while(!(s[p]=='r'&&s[p+1]=='u'));
    //一开始这里用的while,然后坑了,改成do-while就好了
    printf(".%c%c", s[p], s[p+1]);
    if(s[p+=2]!='\0') { printf("/%s", s+p); }
    return 0;
}

C. Game with Coins

题目描述：

有n个箱子,每个箱子有a[i]个金币,每次操作可以选定一个数x(2*x+1<=n).
然后可以从第x个,第2*x个,第2*x+1个箱子里取走一枚金币.
问对于给定的n和{$a_1,a_2,\cdots\cdots,a_n$}最少要多少次能取完所有的箱子里的金币.
如果不能取完,输出-1,否则输出最少的次数.

输入格式：

第一行一个整数n,第二行n个整数,分别是a1,a2,······,an.

输出格式：

最少的次数或者-1

数据保证：

$1 \leq n \leq 100, 1 \leq ai \leq 1000$

解题的思路就是：贪心！！

首先判断不可能的情况,也就是输出-1的情况.
当n为偶数的时候,肯定无解,因为要求每一次的2x+1<=n,
当n是偶数的时候,第n个箱子是无法被取走金币的…

因为当$x=\frac{n}{2}$时,$ 2*x+1 = n+1 > n$.
当$x=\frac{n}{2}-1$时,$2*x+1 = n-1 < n$.
都无法等于n..

其次是最优策略：
每次都取$x=\frac{n}{2}$直到第n个和第n-1个箱子里的金币空了之后,x减一.

这样做的好处是,可以尽快的把最后的箱子清空,并且尽可能多的减少前面的箱子里的金币.

具体实现如下：

#include <cstdio>
#define  max(i,j) ({int _ = (i), __ = (j); _ > __ ? _ : __;})
#define  MAX_LEN 111

int main(int argc, char const *argv[])
{
    int n, ans = 0, a[MAX_LEN]={0};
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){    scanf("%d", a+i); }
    if(n<3 || n%2==0){ printf("-1"); } 
    else {
        for(int i = n/2; i > 0; --i){
            int tmp  = max(a[i*2],a[i*2+1]);
            a[i*2+1] = max(0,a[i*2+1]-tmp);
            a[i*2]   = max(0,a[i*2]-tmp);
            a[i]     = max(0,a[i]-tmp);
            ans += tmp;
        }
        ans += a[1];
        printf("%d", ans);
    }
    return 0;
}

D. Restoring Table

题目描述：

Polycarpus 由一个数列a经过一种运算后得到了一个矩阵b,然后他把数列给忘记了..- 现在只有矩阵,要求根据矩阵还原数列！
数列到矩阵的转化运算如下：

1 2	if(i!=j) { b[i][j] = a[i]&a[j]; } if(i==j) { b[i][j] =-1; }

输入格式：

第一行一个整数n.
接下来是一个n*n的矩阵.
第i+1行第j列表示矩阵的第i行第j列的元素$a_{i,j}$.

输出格式：

一行整数,表示{$a_1,a_2,\cdots\cdots,a_n$},多解输出任意解

数据保证：

矩阵的第i行第i列一定是-1,一定有解,$0 \leq a[i]\leq 10^9,1 \leq n\leq100$

这道题考察了位运算的知识
具体的思路就是：a[i] = a[i] | b[i][j]; a[j] = a[j] | b[i][j];
当然i不能等于j,也就是说-1必须跳过..这道题我似乎是直接AC..
下面是具体代码.

#include <cstdio>
#define  MAX_LEN 111

int main(int argc, char const *argv[])
{
    int n, x, ans[MAX_LEN] = {0};
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            scanf("%d", &x);
            if(x!=-1){
                ans[i] |= x;
                ans[j] |= x;
            }
        }
    }
    for(int i = 0; i < n; ++i){
        printf("%d ", ans[i]);
    }
    return 0;
}

E. Mishap in Club

题目描述：

根据一个club的进出记录,+表示进入一个人,-表示出去一个人
要求算出能判断出的最少人数.

输入格式：

一行字符串,只包含’+’和’-‘

输出格式：

可能的最少的人数

数据保证：

输入字符串长度不超过300

呃呃呃这个题目描述不好描述,英文不好,本来是一道水题的.硬生生的被英语坑了.没读懂题目.赛后,在同学的翻译下才弄明白意思.

解题思路：

记录两个变量,分别表示club外面的人数和里面的人数
根据题意,一开始是未知的,所以初始化为0,然后：

如果进来了人,判断外面是否有人,有人的话就把外面的人数减一,否则答案ans加1,无论外面是否有人,里面人数加1；
如果出去了人,判断里面是否有人,有人则里面人数减一,否则答案ans加1,无论里面是否有人,外面人数加1.

最后输出ans

#include <cstdio>
#define abs(x) ({(x)<0?-(x):(x);})
#define max(i,j) ({int _ = (i), __ = (j); _ > __ ? _ : __;})

int main(int argc, char const *argv[])
{
    char ch; 
    int inside = 0, outside = 0, ans = 0;
    while(scanf("%c", &ch) != EOF && (ch == '-'||ch=='+')){
        if(ch == '+') { 
            inside++;
            if(outside>0) { outside--; }
            else { ans++; }
        }else {
            outside++;
            if(inside>0) { inside--; }
            else { ans++; }
        }
    }
    printf("%d", ans);
    return 0;
}

F. Log Stream Analysis

题目描述：

一条warning日志的标准格式是这样的..

“2012-MM-DD HH:MM:SS:MESSAGE” (没有引号).

现在给一个日志文件,要求计算出第一次出现持续n秒的warning数量大于等于m的时间..

输入格式：

第一行两个整数n和m,然后是若干行日志

输出格式：

输出一行时间：2012-MM-DD HH:MM:SS
表示第一次满足要求的时刻(the first moment).
如果无解则输出-1.

数据保证：

$1 \leq n,m \leq 10000$,字符串长度不超过$5* 10^6$.

一开始没看懂题目意思..天坑！！又是英语..

解题思路：

首先可以肯定的是,MESSAGE无用的,
其次每次读入一条warning,需要把时间全部转化成秒,要考虑月份,年份是确定的2012
维护一个队列,把转化成秒的当前时间加入到队尾：
然后判断队首时间加上n是否小于等于当前时间

如果小于等于,则把队首元素出队,否则队首元素不出队
循环输入直到队列为空或者条件不满足.

然后判断队列的长度len是否大于等于m

如果大于等于m,则输出当前时间,结束算法！
循环知道上面的条件满足或者输入结束.

如果warning全部读完了,队列的长度都没有满足大于等于m的条件,则输出-1
详细代码在下面.

#include <cstdio>
#define MAX_LEN 11111111

int  mon[13] = {0,31,60,91,121,152,182,213,244,274,305,335,366};
int  n, m, head, tail;
int  queue[MAX_LEN];
char s[MAX_LEN];

int main(int argc, char const *argv[])
{
    scanf("%d%d\n", &n, &m);
    int month, days, hour, minute, second, current;
    while(scanf("2012-%d-%d %d:%d:%d: ", &month, &days, &hour, &minute, &second)!=EOF){
        current = (mon[month-1]+(days-1))*86400+hour*3600+minute*60+second;
        queue[tail++] = current;
        for(;head<tail && queue[head] <= current-n; ++head);
        if(tail-head >= m){
            printf("2012-%02d-%02d %02d:%02d:%02d\n", month, days, hour, minute, second);
            return 0;
        }
        gets(s);
    }
    printf("-1\n");
    return 0;
}

G. Suggested Friends

题目描述：

给一个朋友关系网,朋友关系是相互的,计算每个人的推荐朋友数量（ps：这让我想起了facebook）.
用户y能被推荐给用户x需要满足以下条件：

x != y
x和y不是朋友
用户y拥有最多的和x相同的朋友.

(hint：如果用户z（同样满足条件1和条件2）和用户x有1个共同朋友,而y与x有两个共同朋友,则y应该被推荐给x,而z不会被推荐)

输入格式：

第一行一个整数m,表示朋友关系的数量
下n行每行两个用空格隔开的字符串,表示两个用户的名字,同时这两个用户是朋友关系

输出格式：

对于每一个用户,输出一行,
每一行由用户名字加该用户的推荐朋友数量,名字和推荐朋友数用空格隔开

数据保证：

$1 \leq m \leq 5000$,每个用户在输入中至少出现一次.

解题思路：

在图上面用暴力算法.
把输入的关系网抽象成一个图,用临接表把图存下来.
然后对于每一个用户x,计算他的推荐朋友数量.
计算方法是这样的：

遍历当前用户x的每一个朋友,打上标记.
然后再遍历每一个除自己外没有标记用户y.
计算他的朋友列表里被标记的朋友的数量.
这个数量就是当前用户x和用户y的共同好友数量.

取最大的共同好友数量的用户个数为当前用户的推荐朋友数量,输出！

考虑时间复杂度和空间复杂度：

时间复杂度是搜索算法和图算法必须考虑的问题.
空间复杂度则是图算法必须考虑的问题.
该算法的时间复杂度是$O(n^2)$.n是用户数量,最大是m的两倍.因此不会超时.
空间复杂度,临接表够节省了,一般用了临接表的图不会爆空间的了.
下面是详细代码.

#include <cstdio>
#include <cstring>
#define  MAX_NUM 11111

struct adj{
    int point;
    adj *next;
} _adj[MAX_NUM*2], *pbuf=_adj;

int  personnum;
adj* head[MAX_NUM];
char name[MAX_NUM][22];

int  find(char const *s);
void link(int a, int b);

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        char s[20];
        scanf("%s", s);
        int x = find(s);
        scanf("%s", s);
        int y = find(s);
        link(x,y);
        link(y,x);
    }
    printf("%d\n", personnum);
    for(int i=0; i<personnum; ++i){
        bool vis[MAX_NUM] = {false};
        int  ans = 0, maxfriendnum = 0;
        for(adj* p = head[i]; p!=NULL; p=p->next){
            vis[p->point] = true;
        }
        for(int j = 0; j<personnum; ++j){
            int curfriendnum = 0;
            if(i==j || vis[j]) { continue; }
            for(adj* p = head[j]; p!=NULL; p=p->next){
                if(vis[p->point]){ curfriendnum++; }
            }
            if(curfriendnum==maxfriendnum) { ans++; }
            else if(curfriendnum>maxfriendnum){
                maxfriendnum = curfriendnum;
                ans = 1;
            }
        }
        printf("%s %d\n", name[i], ans);
    }
    return 0;
}

int find(char const *s)
{
    int ans = 0;
    for(; ans<personnum && strcmp(name[ans],s)!=0; ++ans);
    if(ans==personnum) { strcpy(name[personnum++],s); }
    return ans;
}

void link(int a, int b)
{
    if(head[a]==NULL) {
        head[a] = pbuf;
    } else {
        pbuf->next    = head[a]->next;
        head[a]->next = pbuf;
    }
    pbuf++->point = b;
}

H. Queries for Number of Palindromes

题目描述：

给定一个字符串s和n组询问,询问字符串的子串s(l,r)有多少个回文子串.

输入格式：

第一行一个字符串s,第二行一个整数n.
以下n行,每行两个整数,表示询问的字串的区间.

输出格式：

对于每一个询问,输出一行一个整数,表示字串区间内的回文字串数量.

数据保证：

字符串只由小写英文字母构成,长度不超过5000,$1 \leq n \leq 10^6$

解题思路：DP！！！

区间DP.
可惜考试的时候我没有把转移方程想出来（神啊,原谅我这个DP渣吧）.
后来自己想出来了答案.思路如下图.

状态设计：用$f\left(i,j\right)$来表示区间$(i,j)$的答案.
转移方程：$f(i,j) = f(i+1,j)+f(i,j-1)-f(i+1,j-1)+is(i,j)$;

$is(i,j)$表示$s(l,r)$是否是回文串,如果是$is(i,j)==1$,否则$is(i,j)==0$;
可以看到,初始条件为$f(i,i) = 1$；因此只需要构造$is(i,j)$.
$is(i,j)$的构造方法:
- 首先每一个$is(i,i)=1$；然后枚举长度 $l$ 从 1 到 $len(s)$
- 则is(i,i+l)=(l==1\|\|is(i+1,i+l-1))\&\&s(i)==s(i+l);

然后一重循环枚举长度一重循环枚举起点,就可以完美的转移状态了.长度$l$从1开始枚举.
根据转移方程,等号右边的f都是长度为j-i-1的.
因此,从长度短的转移到长度长的,是不会漏掉状态的.
下面是详细代码.

#include <cstdio>
#include <cstring>
#define MAX_LEN 5555

int  ans[MAX_LEN][MAX_LEN];
bool is[MAX_LEN][MAX_LEN];

int main(int argc, char const *argv[])
{
    char s[MAX_LEN];
    scanf("%s", s);
    int len = strlen(s);
    for(int i = 0; i < len; ++i){
        ans[i][i] = is[i][i] = true;
    }
    for(int l = 1; l <= len; ++l){
        for(int i = 0; i < len-l; ++i){
            int j = i+l;
            if((l==1||is[i+1][j-1])&&s[i]==s[j]){
                is[i][j] = true;
            }
        }
    }
    for(int l = 1; l <= len; ++l){
        for(int i = 0; i < len-l; ++i){
            int j = i+l;
            ans[i][j] = ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1]+is[i][j];
        }
    }
    int n, l, r;
    scanf("%d", &n);
    while(n--){
        scanf("%d%d", &l, &r);
        printf("%d\n", ans[l-1][r-1]);
    }
    return 0;
}