M_sea

Codeforces Beta Round #5
传送门[A] Chat Servers Outgoing Traffic题意维护一个聊天室,有三种命令:加入、退出...
扫描右侧二维码阅读全文
08
2018/08

Codeforces Beta Round #5

传送门

[A] Chat Servers Outgoing Traffic

题意

维护一个聊天室,有三种命令:加入、退出、发送消息。

加入和退出不会发送流量,但发送消息会向在线的每个人发送l字节的流量。

问共发出了多少流量。

算法

STL大法吼。

map暴力维护一下即可。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int sum;
string s;

int main() {
    int ans=0;
    while (getline(cin,s)) {
        if (s[0]=='+') sum++;
        else if (s[0]=='-') sum--;
        else {
            int l=s.length();
            for (re int i=0;i<l;i++)
                if (s[i]==':') { ans+=(sum*(l-i-1)); break; }
        }
    }
    printf("%d\n",ans);
    return 0;
}

[B] Center Alignment

题意

给出n行文本,要求实现居中对齐。

若无法完美的居中,那么第一次向左微调、第二次向右微调,以此类推。

算法

乱搞。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

string s[1010];
int l[1010];
int n,MaxLen=-1;

int main() {
    while (getline(cin,s[n+1])) ++n,l[n]=s[n].length(),MaxLen=max(MaxLen,l[n]);
    for (re int i=1;i<=MaxLen+2;i++) putchar('*'); putchar('\n');
    bool f=1; //Left
    for (re int i=1;i<=n;i++) {
        putchar('*');
        int left=MaxLen-l[i];
        if (left&1) {
            if (f) {
                for (re int j=1;j<=left/2;j++) putchar(' ');
                cout<<s[i];
                for (re int j=1;j<=left/2+1;j++) putchar(' ');
            }
            else {
                for (re int j=1;j<=left/2+1;j++) putchar(' ');
                cout<<s[i];
                for (re int j=1;j<=left/2;j++) putchar(' ');
            }
            f=!f;
        }
        else {
            for (re int j=1;j<=left/2;j++) putchar(' ');
            cout<<s[i];
            for (re int j=1;j<=left/2;j++) putchar(' ');
        }
        putchar('*');
        putchar('\n');
    }
    for (re int i=1;i<=MaxLen+2;i++) putchar('*');
    return 0;
}

[C] Longest Regular Bracket Sequence

题意

给出一个括号序列,求出最长合法子串和它的数量。 合法的定义:这个序列中左右括号匹配。

算法

拿样例一作解释:

)((())))(()())

我们要把它搞成这个样子:

01111110111111

即:把能匹配的都搞成1。

那么求最长的1就行了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

char s[1000010];
int a[1000010];
int f[1000010];
stack<int> sta;

int main() {
    scanf("%s",s+1);
    int l=strlen(s+1),t=0;
    for (re int i=1;i<=l;i++) {
        if (s[i]=='(') { sta.push(i); }
        else if (!sta.empty()) { a[i]=1,a[sta.top()]=1; sta.pop(); }
    }
    int Max=-1,sum=0;
    for (re int i=1;i<=l;i++) {
        if (a[i]==0) f[i]=0;
        else f[i]=f[i-1]+1;
        Max=max(Max,f[i]);
    }
    for (re int i=1;i<=l;i++)
        if (f[i]==Max) sum++;
    if (Max==0) printf("0 1\n");
    else printf("%d %d\n",Max,sum);
    return 0;
}

[D] Follow Traffic Rules

题意

有一条长度为l的路,全程限速为v。在离起点d的地方有一个路口,限速为w。你的加速度为a,求走完这条路的最短时间。

算法

毒瘤物理题。

用物理必修一里的那一堆公式分类讨论搞搞即可。

(对我这种新初三蒟蒻不友好的题目)

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline double GetTime(double v1,double v2,double a,double l){
    double t=0.0;
    double s=(v2*v2-v1*v1)/2/a;
    if (s>=l) t=(-v1+sqrt(v1*v1+2*a*l))/a;
    else {
        double t1=(v2-v1)/a;
        double t2=(l-(v2*v2-v1*v1)/2/a)/v2;
        t=t1+t2;
    }
    return t;
}

int main() {
    double a,v,l,d,w; cin>>a>>v>>l>>d>>w;
    double s=v*v/2/a;
    if (w>=v) printf("%.12f\n",GetTime(0,v,a,l));
    else {
        double s1=w*w/2/a;
        if (s1>=d) printf("%.12f\n",GetTime(0,v,a,l));
        else {
            double t11=sqrt((2*a*d+w*w)/2/a/a);
            double t1;
            if (t11*a<=v) t1=2*t11-w/a;
            else {
                double s11=v*v/2/a;
                double s12=(v*v-w*w)/2/a;
                  t1=v/a+(v-w)/a+(d-s11-s12)/v;
            }
            double t2=GetTime(w,v,a,l-d);
            double t=t1+t2;
            printf("%.12f\n",t);
        }
    }
    return 0;
}

[E] Bindian Signalizing

题意

有一个环上有n座山,每座山的高度为h[i]。

山A、B能互相看见定义为在$\overset{\frown}{AB}$上(优弧劣弧皆可),没有比A、B中矮的那座山更高的山。

求有多少对山能互相看见。

算法

一个环,考虑破环为链。以最高的为第一座山,最后再补上一个最高的。

设$l[i]$表示i左边最高的山,$r[i]$表示i右边最高的山。

显然$i$与$l[i]$能互相看见,$i$与$r[i]$能互相看见。

再维护一个$cnt[]$,$cnt[i]$表示$i$右边的山到$r[i]$中和$i$一样高的山的个数。

那么显然,每座山至少能看见$cnt[i]+2$座山。

但当$l[i]=1$且$r[i]=n+1$时,实际上为一组,所以为$cnt[i]+1$座山。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int t[1000010],h[1000010];
int l[1000010],r[1000010];
int cnt[1000010];

mainint main() {
    int n=read(),p=1;
    for (re int i=1;i<=n;i++) t[i]=read();
    for (re int i=2;i<=n;i++)
        if (t[i]>t[p]) p=i;
    for (re int i=1;i<=n+1;i++) h[i]=t[(i+p-2)%n+1];
    
    for (re int i=2;i<=n+1;i++) {
        l[i]=i-1;
        while (l[i]>1&&h[i]>=h[l[i]]) l[i]=l[l[i]];
    }
    for (re int i=n;i>=1;i--) {
        r[i]=i+1;
        while (r[i]<=n&&h[i]>h[r[i]]) r[i]=r[r[i]];
        if (r[i]<=n&&h[i]==h[r[i]]) { cnt[i]=cnt[r[i]]+1; r[i]=r[r[i]]; }
    }
    
    int ans=0;
    for (re int i=1;i<=n;i++) {
        ans+=cnt[i];
        if (h[i]<h[1]) {
            ans+=2;
            if (l[i]==1&&r[i]==n+1) ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 05 PM

发表评论