M_sea

Codeforces Beta Round #10 题解
传送门[A] Power Consumption Calculation题意有一台电脑,在活跃状态下,每秒钟耗能p...
扫描右侧二维码阅读全文
12
2018/08

Codeforces Beta Round #10 题解

传送门

[A] Power Consumption Calculation

题意

有一台电脑,在活跃状态下,每秒钟耗能p1,在没人碰之后的t1秒后,进入休息状态,每秒钟耗能p2,如果再有t3秒没人碰的话,就会进入睡眠状态,每秒钟耗能p3

给你这个人碰电脑的区间时间,问你这台电脑的耗能是多少。

算法

纯模拟。 注意细节。

[B] Cinema Cashier

题意

有一个k*k的电影院。有n波人依次到来。

每一波人都必须坐在同一行,代价为abs(x-zx)+abs(y-zy)。(zx、zy为中心的坐标)

你需要给他们安排座位,使得代价最小。如果代价一样,就坐左前方。

求安排的方案。

算法

纯模拟。

每次暴力找到能坐的代价最小的一排位置,然后标记一下。

如果找不到就输出-1。

代码

#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;
}

bool a[110][110];

int main() {
    int n=read(),k=read();
    int xc=(k+1)/2,yc=(k+1)/2;
    while (n--) {
        int x=read();
        int X,Y,Min=2147483647;
        for (re int i=1;i<=k;i++)
            for (re int j=1;j<=k-x+1;j++) {
                bool f=1; int s=0;
                for (re int t=j;t<j+x;t++) {
                    if (a[i][t]) { f=0; break; }
                    s+=abs(i-xc)+abs(t-yc);
                }
                if (f&&s<Min) Min=s,X=i,Y=j;
            }
        if (Min==2147483647) puts("-1");
        else {
            for (re int i=Y;i<Y+x;i++) a[X][i]=1;
            printf("%d %d %d\n",X,Y,Y+x-1);
        }
    }            
    return 0;
}

[C] Digital Root

题意

定义函数s(x),s(x)的值等于x各数位上的数值之和,定义函数d(x),当s(x)<=9时d(x)=s(x),否则d(x)=d(s(x)),举例来说,d(6543)=d(6+5+4+3)=d(18)=9

现在给定一上限N,求在[1.N]内任取A,B,C满足A*B!=C且d(C)=d(d(A)⋅d(B))的组数。

算法

首先要知道一个叫做数字根的东西,就是题目里说$d()$。

其实,
$d(x)=\begin{cases}x\%9,\quad x\%9\neq0\\9,\qquad\ \ x\%9=0 \end{cases} $

我们把$9$看做$0$,那么

$d(x)=x\%9$

那么先处理出$d(a)\cdot d(b)=d(c)$的部分,然后处理出$a\cdot b=c$的部分,两者相减即为答案。

后一部分很容易求出,即1~n的约数个数和,记为$ans2$。

考虑每一个数的贡献,即:

$ans2=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$

前一部分也不难。在求$ans2$时,顺便求出一个数组$a[]$,$a[i]$表示$[1,n]$内有多少个数的$d()$为$i$。

那么枚举$d(a)$和$d(b)$,求出$d(c)$,再计数。

记第二部分的答案为$ans1$,则:

$ans1=\sum_{i=0,j=0}^{8}a[i]\times a[j]\times a[(i+j)\%9]$

最终的答案为$ans1-ans2$。

(然而我的程序里$ans1$和$ans2$是反过来的)

代码

#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 a[10];

mainint main() {
    int n=read();
    int ans1=0,ans2=0;
    for (re int i=1;i<=n;i++) a[i%9]++,ans1+=n/i;
    for (re int i=0;i<9;i++)
        for (re int j=0;j<9;j++)
            ans2+=a[i]*a[j]*a[(i*j)%9];
    printf("%I64d\n",ans2-ans1);
    return 0;
}

[D] LCIS

题意

求两个序列的LCIS。

算法

这是很经典的DP题了吧。

详细讲解

代码

#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 f[510][510];
int pre[510][510];
int a[510],b[510];
int n,m;

inline void Print(int p) {
    if (!p) return;
    Print(pre[n][p]);
    printf("%d ",b[p]);
}

int main() {
    n=read(); for (re int i=1;i<=n;i++) a[i]=read();
    m=read(); for (re int i=1;i<=m;i++) b[i]=read();
    
    int t=0; //t表示最长LCIS结尾位置 
    for (re int i=1;i<=n;i++) {
        t=0;
        for (re int j=1;j<=m;j++) {
            f[i][j]=f[i-1][j]; pre[i][j]=pre[i-1][j];
            if (a[i]==b[j]&&f[i-1][t]+1>f[i][j]) {
                f[i][j]=f[i-1][t]+1;
                pre[i][j]=t;
            }
            if (b[j]<a[i]&&f[i-1][j]>f[i-1][t]) t=j;
        }
    }
    int pos=0;
    for (re int i=1;i<=m;i++)
        if (f[n][i]>f[n][pos]) pos=i;
    printf("%d\n",f[n][pos]);
    Print(pos);
    
    return 0;
}

[E] Greedy Change

又一道题解都看不懂的题。

(我想放yyb那张说题目毒瘤的图)

最后修改:2019 年 05 月 26 日 10 : 23 PM

发表评论