Codeforces 1030A. In Search of an Easy Problem(Codebait) [Codeforces Round

题面

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 nn people about their opinions. Each person answered whether this problem is easy or hard.

If at least one of these nn 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 nn (1n1001 \le n \le 100) — the number of people who were asked to give their opinions.

The second line contains nnintegers, each integer is either 00or 11. If ii-th integer is 00, then ii-th person thinks that the problem is easy; if it is11, thenii-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;
}

A. Magic Mirror(新手题,字符串处理) [2018 ACM-ICPC Jiaozuo Online Contest]

题面

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(1T100)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 1515.

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?

题解

题目大意

给出 TT个长度小于1515 的字符串,判断其是否与字符串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;
}

2018 ACM-ICPC Jiaozuo Online Contest [Personal Summary]

My Status

A B C D E F G H I J K
O Ø Ø Ø Ø Ø Ø Ø O Ø Ø

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

H. Ryuji doesn't want to study (树状数组) [2018 ACM-ICPC Xuzhou Online Contest]

题面

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]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]×L+a[l+1]×(L1)++a[r1]×2+a[r]a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r](LLis the length of [ $ l, r$ ] that equals torl+1r - l + 1).

Now Ryuji has qq questions, you should answer him:

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

  • If the question type is 22, Ryuji will change the iith book’s knowledge to a new value.

Input

First line contains two integers nnandqq (n,q100000n, q \le 100000).

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

Then in next qqline each line contains three integers a,b,ca, b, c, if a=1a = 1, it means question type is 11, and b,cb, crepresents [ l,rl , r]. if a=2a = 2, it means question type is22 , andb,cb, c means Ryuji changes thebbth book’s knowledge tocc .

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]×L+a[l+1]×(L1)++a[r1]×2+a[r]a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]

  • = k=lr(rl+1(kl))a[k]\sum\limits_{k=l}^{r}(r-l+1-(k-l)) \cdot a[k]
  • = k=lr(rk+1)a[k]\sum\limits_{k=l}^{r}(r-k+1) \cdot a[k]
  • = (r+1)k=lra[k]k=lrka[k](r+1)\sum\limits_{k=l}^{r}a[k]-\sum\limits_{k=l}^{r}k \cdot a[k]

又,题中所给两种操作分别为区间查询,单点修改;因此用树状数组直接维护 a[k]a[k]ka[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;
}

2018 ACM-ICPC Xuzhou Online Contest [Personal Summary]

My Status

A B C D E F G H I J K
Ø Ø Ø Ø Ø Ø Ø O Ø Ø Ø

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

2017 CCPC China-Hunan Invitional [Personal Summary]

My Status

A B C D E F G H I J K
Ø Ø Ø Ø Ø O Ø Ø Ø Ø Ø

Level

签到题:A

简单题:F

中等题:

难题:

Solution

A. Easy hh-index

unsolved

B. Higher hh-index

unsolved

C. Just hh-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

ACM Trick Points (持续更新)

函数

memset 赋值

我们在设计程序时经常会使用memset(array, val, sizeof(array))来初始化一个int数组array,因为memsetstring.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次式 (n \geq 1),则可将其 n$个根列出联立方程

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

证明

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

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

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

Attention Points

运算符优先级

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

加减 移位 比较大小 位与 异或 位或
+, - <<, >> >, <, ==, != & ^ 位或

vector 的 push_back 相关

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

阴险的出数据方式

POJ 3263

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

2018-安徽大学第十届大学生程序设计竞赛网络赛题解

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

阅读更多