题面

Description

When preparing a tournament, Codeforces coordinators try treir best to make the first problem as easy as possible. This time the coordinator had chosen some problem and asked $n$ people about their opinions. Each person answered whether this problem is easy or hard.

If at least one of these $n$ people has answered that the problem is hard, the coordinator decides to change the problem. For the given responses, check if the problem is easy enough.

Input

The first line contains a single integer $n$ ($1 \le n \le 100$) — the number of people who were asked to give their opinions.

The second line contains $n$integers, each integer is either $0$or $1$. If $i$-th integer is $0$, then $i$-th person thinks that the problem is easy; if it is$1$, then$i$-th person thinks that the problem is hard.

Output

Print one word: “EASY” if the problem is easy according to all responses, or “HARD” if there is at least one person who thinks the problem is hard.

You may print every letter in any register: “EASY”, “easy”, “EaSY” and “eAsY” all will be processed correctly.

Sample Input 1

1
2

3
0 0 1

Sample Output 1

1

HARD

Sample Input 2

1
2

1
0

Sample Output 2

1

EASY

题解

题目大意

给你一个大小为n的数组，元素只有0和1，如果数组中存在元素为1，则输出HARD，否则输出EASY，并且每个字母大小写随便

分析

直接根据题意模拟，真·签到题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    while(cin >> n) {
        bool isone = false;
        for(int i = 1; i <= n; i++) {
            int a = 0;

            cin >> a;
            if(a == 1) {
                isone = true;
            }
        }

        if(isone) cout << "HARD" << endl;
        else cout << "EASY" << endl;
    }

    return 0;
}

My Status

Level

全场几乎都是签到，然而我还是很菜

Solution

A. In Search of an Easy Problem

solution

B. Vasya and Cornfield

solution

C. Vasya and Golden Ticket

solution

D. Vasya and Triangle

solution

E. Vasya and Good Sequences

unsolved

F. Putting Boxes Together

unsolved

G. Linear Congruential Generator

unsolved

题面

Description

Jessie has a magic mirror.

Every morning she will ask the mirror: ‘Mirror mirror tell me, who is the most beautiful girl in the world?’ If the mirror says her name, she will praise the mirror: ‘Good guy!’, but if the mirror says the name of another person, she will assail the mirror: ‘Dare you say that again?’

Today Jessie asks the mirror the same question above, and you are given a series of mirror’s answers. For each answer, please output Jessie’s response. You can assume that the uppercase or lowercase letters appearing anywhere in the name will have no influence on the answer. For example, ‘Jessie’ and ‘jessie’ represent the same person.

Input

The first line contains an integer $T(1 \le T \le 100)$, which is the number of test cases.

Each test case contains one line with a single-word name, which contains only English letters. The length of each name is no more than $15$.

Output

For each test case, output one line containing the answer.

Sample Input

1
2
3

2
Jessie
Justin

Sample Output

1
2

Good guy!
Dare you say that again?

题解

题目大意

给出 $T$个长度小于$15$ 的字符串，判断其是否与字符串Jessie相等（忽略大小写）。

分析

完全的新生级签到题，读入字符串后将每个字符都转为小写，之后判断是否与jessie相等即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;

const int MAXN = 20;
char name[MAXN];

int main() {
    int t = 0;
    scanf("%d", &t);

    while(t--) {
        scanf("%s", name);

        int len = (int)strlen(name);
        for(int i = 0; i < len; i++)
            name[i] = tolower(name[i]);
        
        if(!strcmp(name, "jessie")) printf("Good guy!\n");
        else printf("Dare you say that again?\n");
    }
    
    return 0;
}

My Status

Level

签到题：
A, I
简单题：

中等题：

难题：

Solution

A. Magic Mirror

solution: http://www.bofc.tech/index.php/archives/141/

B. Mathematical Curse

unsolved

C. Password

unsolved

D. Sequence

unsolved

E. Jiu Yuan Wants to Eat

unsolved

F. Modular Production Line

unsolved

G. Give Candies

unsolved

H. String and Times

unsolved

I. Save the Room

solution:

J. Participate in E-sports

unsolved

K. Transport Ship

unsolved

L. Poor God Water

unsolved

题面

Description

Ryuji is not a good student, and he doesn’t want to study. But there are n books he should learn, each book has its knowledge $a[i]$.

Unfortunately, the longer he learns, the fewer he gets.

That means, if he reads books from ll to rr, he will get $a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]$($L$is the length of [ $ l, r$ ] that equals to$r - l + 1$).

Now Ryuji has $q$ questions, you should answer him:

• If the question type is $1$, you should answer how much knowledge he will get after he reads books [ $l, r$ ].

• If the question type is $2$, Ryuji will change the $i$th book’s knowledge to a new value.

Input

First line contains two integers $n$and$q$ ($n, q \le 100000$).

The next line contains n integers represent $a[i]$ $(a[i]≤1e9)$ .

Then in next $q$line each line contains three integers $a, b, c$, if $a = 1$, it means question type is $1$, and $b, c$represents [ $l , r$]. if $a = 2$, it means question type is$2$ , and$b, c$ means Ryuji changes the$b$th book’s knowledge to$c$ .

Output

For each question, output one line with one integer represent the answer.

Sample Output

1
2
3
4
5

5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5

Sample Output

1
2

10
8

分析

注意到题中公式可进行如下变形：

$a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]$

• = $\sum\limits_{k=l}^{r}(r-l+1-(k-l)) \cdot a[k]$
• = $\sum\limits_{k=l}^{r}(r-k+1) \cdot a[k]$
• = $(r+1)\sum\limits_{k=l}^{r}a[k]-\sum\limits_{k=l}^{r}k \cdot a[k]$

又，题中所给两种操作分别为区间查询，单点修改；因此用树状数组直接维护 $a[k]$和$k \cdot a[k]$ 的值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

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

typedef long long ll;
#define LOWBIT(x) ((x) & -(x))

const int MAXN = 1e5 + 10;
ll a[MAXN];
ll c[MAXN], mc[MAXN];

ll ask(ll* ar, int x) {
    ll ans = 0;
    for( ; x; x -= LOWBIT(x)) ans += ar[x];
    return ans;
}

void add(ll* ar, int x, ll y, int n) {
    for( ; x <= n; x += LOWBIT(x)) ar[x] += y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0, q = 0;
    while(cin >> n >> q) {
        for(int i = 1; i <= n; i++)
            cin >> a[i];

        for(int i = 1; i <= n; i++)
            add(c, i, a[i], n);
        for(int i = 1; i <= n; i++)
            add(mc, i, a[i] * (ll)i, n);

        for(int i = 1; i <= q; i++) {
            int p = 0, l = 0, r = 0;
            cin >> p >> l >> r;

            if(p == 1) {
                cout << (ll)(r + 1) * (ask(c, r) - ask(c, l - 1)) - (ask(mc, r) - ask(mc, l - 1)) << endl;
            }
            else if(p == 2) {
                ll l_c = ask(c, l) - ask(c, l - 1);
                ll l_mc = ask(mc, l) - ask(mc, l - 1);

                add(c, l, (ll)r - l_c, n);
                add(mc, l, (ll)r * (ll)l - l_mc, n);
            }
        }
    }

    return 0;
}

My Status

Level

签到题：
H
简单题：

中等题：

难题：

Solution

A. Hard to prepare

unsolved

B. BE, GE or NE

unsolved

C. Cacti Lottery

unsolved

D. Easy Math

unsolved

E. End Fantasy VIX

unsolved

F. Features Track

unsolved

G. Trace

unsolved

H. Ryuji doesn’t want to study

solution: http://www.bofc.tech/index.php/archives/137/

I. Characters with Hash

unsolved

J. Maze Designer

unsolved

K. Morgana Net

unsolved

My Status

Level

签到题：A

简单题：F

中等题：

难题：

Solution

A. Easy $h$-index

unsolved

B. Higher $h$-index

unsolved

C. Just $h$-index

unsolved

D. Circular Coloring

unsolved

E. From Tree to Graph

unsolved

F. Sorting

Solution: http://www.bofc.tech/index.php/archives/124/

G. String Transformation

unsolved

H. Infinity

unsolved

I. Longest Increasing Subsequence

unsolved

J. Vertex Cover

unsolved

K. 2018

unsolved

比赛训练个人记录

2017 CCPC China-Hunan Invitional
2018 ACM-ICPC Shenyang Online Contest
2018 ACM-ICPC Xuzhou Online Contest
2018 ACM-ICPC Jiaozuo Online Contest
Codeforces Round #512 (Div. 2)

每日训练记录

2018.9.3

做/补题列表：

A. An Olympian Math Problem (数论) 2018 ACM-ICPC Nanjing Online Contest

学习内容：

2018.9.4

做/补题列表：

POJ.2559 Largest Rectangle in a Histogram (单调栈)

学习内容：

函数

memset 赋值

我们在设计程序时经常会使用memset(array, val, sizeof(array))来初始化一个int数组array，因为memset是string.h中的函数所以其填充对象也是字节，会将数值val（或者是字符val）填充到array的每个字节上，因此用memset只能赋值出每字节都相同的int。

因此，我们如果想要将某个数组初始化为INF，则能赋值出的最大数值为0x7fffffff。但是为了避免加法算术溢出或其他判断，我们通常选择将数组的每个int初始化为0x3f3f3f3f。这个数值满足以下两个条件：

1. 整数的两倍不超过0x7fffffff（即INT_MAX）。
2. 整数的每8位都相同（恰好可以用memset填充）。

因此我们通常使用memset(array, 0x3f, sizeof(array))来初始化int数组。

scanf 读取数组元素

输入括号需要来回切换光标，十分麻烦…如果不想输入类似&a[i]的符号，可以使用指针形式来简化输入: scanf("%d", a + i);

这个方法也适合在读入字符串时将其存储在并非数组开头的位置。

数学

余式定理

对多项式$P(x) $，有$\frac{P(x)}{x-a}$之余式为$ P(a)$。

更一般地，假设对于多项式除法$\frac{P(x)}{M(x)}=Q(x)+R(x) $，其中商是$Q(x) $，余式是$R(x) $，若$ M(x)$是n次式$ (n \geq 1)$，则可将其$ n$个根列出联立方程

$\\P(a)=R(a) \\P(b)=R(b) \\P(c)=R(c) \\ \cdots$

证明

考虑$\frac{P(x)}{x-a}=Q(x)+R(x)$。

由除法定理有$P(x)=(x-a)Q(x)+R(x) $。且因为$x-a $是1次式，故$ R(x)$为常数，记为$ r$。

此时代入$x=a $，可得$ P(a)=r$。证毕。

Attention Points

运算符优先级

一些运算符的优先级由高到低如下表所示，最需要注意的点是：大小关系比较运算符的优先级高于“位与”“位或”“位非”运算符。

vector 的 push_back 相关

在没有显式为某个vector分配空间时，绝不能用下标访问其元素而应使用push_back。

阴险的出数据方式

POJ 3263

一条关系$ (A_{i}, B_{i})$ 可能会输入多次（即输入重边），刻意影响区间操作。

总的来说，这场比赛的题还是比较水的，至少难度什么的甚至没法和热身赛相比。然而这场比赛中不乏需要注意的细节问题，比如unsigned long long出现了好几次什么的。。。在这上面栽了一把。C、H题的分析仍存在问题（还是我菜）。。。暂时不列出。