Problem A:
1 second
256 megabytes
standard input
standard output
Bizon the Champion is called the Champion for a reason.
Bizon the Champion has recently got a present — a new glass cupboard with n shelves
and he decided to put all his presents there. All the presents can be divided into two types: medals and cups. Bizon the Champion has a1 first
prize cups, a2 second
prize cups and a3third
prize cups. Besides, he has b1 first
prize medals, b2 second
prize medals and b3 third
prize medals.
Naturally, the rewards in the cupboard must look good, that's why Bizon the Champion decided to follow the rules:
- any shelf cannot contain both cups and medals at the same time;
- no shelf can contain more than five cups;
- no shelf can have more than ten medals.
Help Bizon the Champion find out if we can put all the rewards so that all the conditions are fulfilled.
The first line contains integers a1, a2 and a3 (0 ≤ a1, a2, a3 ≤ 100).
The second line contains integers b1, b2 and b3 (0 ≤ b1, b2, b3 ≤ 100).
The third line contains integer n (1 ≤ n ≤ 100).
The numbers in the lines are separated by single spaces.
Print "YES" (without the quotes) if all the rewards can be put on the shelves in
the described manner. Otherwise, print "NO" (without the quotes).
1 1 1
1 1 1
4
YES
1 1 3
2 3 4
2
YES
1 0 0
1 0 0
1
NO
传送门:点击打开链接
解题思路:
求出放置全部奖杯和奖牌须要的最少架子的数目num,和n进行比較。
代码:
#include <cstdio>
#include <cmath> int main()
{
int a1, a2, a3, b1, b2, b3, n;
scanf("%d%d%d%d%d%d%d", &a1, &a2, &a3, &b1, &b2, &b3, &n);
int num = ceil((a1 + a2 + a3) * 1.0 / 5) + ceil((b1 + b2 + b3) * 1.0 / 10);
printf("%s\n", num <= n ? "YES" : "NO");
return 0;
}
Problem B:
1 second
256 megabytes
standard input
standard output
Bizon the Champion isn't just a bison. He also is a favorite of the "Bizons" team.
At a competition the "Bizons" got the following problem: "You are given two distinct words (strings of English letters), s and t.
You need to transform word s into word t".
The task looked simple to the guys because they know the suffix data structures well. Bizon Senior loves suffix automaton. By applying it once to a string, he can remove from this string any single character. Bizon Middle knows suffix array well. By applying
it once to a string, he can swap any two characters of this string. The guys do not know anything about the suffix tree, but it can help them do much more.
Bizon the Champion wonders whether the "Bizons" can solve the problem. Perhaps, the solution do not require both data structures. Find out whether the guys can solve the problem
and if they can, how do they do it? Can they solve it either only with use of suffix automaton or only with use of suffix array or they need both structures? Note that any structure may be used an unlimited number of times, the structures may be used in any
order.
The first line contains a non-empty word s.
The second line contains a non-empty word t. Words s and t are
different. Each word consists only of lowercase English letters. Each word contains at most 100 letters.
In the single line print the answer to the problem. Print "need tree" (without
the quotes) if word s cannot be transformed into word teven
with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print
"array" (without the quotes) if you need only the suffix array to solve the problem. Print "both"
(without the quotes), if you need both data structures to solve the problem.
It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix
automaton.
automaton
tomat
automaton
array
arary
array
both
hot
both
need
tree
need tree
传送门:点击打开链接
解题思路:
假设串A中包括串B的全部字母,而且这些字母在串A和串B中排列顺序同样,输出“automaton”,否则,假设串A中包括串B的全部字母,我们在这样的情况下在进行讨论,假设A和B的长度相等,输出“array”,假设A比B长。输出“both”,否则输出“need tree”。
代码:
#include <cstring>
#include <string>
#include <iostream>
using namespace std; const int MAXN = 105;
int vis[MAXN]; bool cmpa(string stra, string strb)
{
memset(vis, 0, sizeof(vis));
int lena = stra.length();
int lenb = strb.length();
int k = 0;
for(int i = 0; i < lenb; i++)
{
bool flag = true;
for(int j = k; j < lena; j++)
{
if(!vis[j] && strb[i] == stra[j])
{
vis[j] = 1;
k = j + 1;
flag = false;
break;
}
}
if(flag) return false;
}
return true;
} bool cmpb(string stra, string strb)
{
memset(vis, 0, sizeof(vis));
int lena = stra.length();
int lenb = strb.length();
for(int i = 0; i < lenb; i++)
{
bool flag = true;
for(int j = 0; j < lena; j++)
{
if(!vis[j] && strb[i] == stra[j])
{
vis[j] = 1;
flag = false;
break;
}
}
if(flag) return false;
}
return true;
} int main()
{
string stra, strb;
cin >> stra >> strb;
int lena = stra.length();
int lenb = strb.length();
if(cmpa(stra, strb))
{
cout << "automaton" << endl;
}
else if(cmpb(stra, strb))
{
if(lena == lenb)
{
cout << "array" << endl;
}
else if(lena > lenb)
{
cout << "both" << endl;
}
else
{
cout << "need tree" << endl;
}
}
else
{
cout << "need tree" << endl;
}
return 0;
}
Problem C:
1 second
512 megabytes
standard input
standard output
Bizon the Champion isn't just attentive, he also is very hardworking.
Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical
planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th
plank has the width of 1 meter and the height of ai meters.
Bizon the Champion bought a brush in the shop, the brush's width is 1 meter.
He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint
the fence? Note that you are allowed to paint the same area of the fence multiple times.
The first line contains integer n (1 ≤ n ≤ 5000) —
the number of fence planks. The second line contains n space-separated integersa1, a2, ..., an (1 ≤ ai ≤ 109).
Print a single integer — the minimum number of strokes needed to paint the whole fence.
5
2 2 1 2 1
3
2
2 2
2
1
5
1
传送门:点击打开链接
解题思路:
递归,贪心。粉刷篱笆。我们能够水平方向粉刷(仅仅能刷到连续的部分)。也能够竖直方向粉刷。按水平方向粉刷的话。刷的最少次数是min(a1,a2,a3,...,an-1);按竖直方向刷的话最少次数是这段连续篱笆的长度n。按上述方式刷完之后,必定会产生高度为0的篱笆(被所有刷过了)。我们把这种篱笆作为切割点,分成左半部分,和右半部分,两部分各是一段连续的篱笆。依次类推。
一个错误的思路:每次刷的时候找全部篱笆高度的最大值h,和最长的连续篱笆的长度len,刷的时候取max(h。len),最多刷n次,算法复杂度O(n2)。
这样做的话。可能会使得篱笆变得分散,导致终于粉刷的次数变多。
反例:
3
1 10 1
错误的代码:
#include <cstdio>
#include <algorithm>
using namespace std; const int MAXN = 5010;
int n, ans = 0, a[MAXN]; int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
while(true)
{
int maxv = *max_element(a, a + n);
int maxh = -1, tmp = 0, first = 1;
int s = 0, t = 0, ts = 0, tt = 0;
for(int i = 0; i < n; i++)
{
if(a[i])
{
if(first)
{
ts = i;
first = 0;
}
tt = i;
tmp++;
if(i == n - 1)
{
if(tmp > maxh)
{
maxh = tmp;
s = ts;
t = tt;
}
}
}
else
{
if(tmp > maxh)
{
maxh = tmp;
s = ts;
t = tt;
}
tmp = 0;
first = 1;
}
}
if(maxv > maxh)
{
*max_element(a, a + n) = 0;
}
else
{
for(int i = s; i <= t; i++)
{
a[i]--;
}
}
ans++;
if(0 == *max_element(a, a + n)) break;
}
printf("%d\n", ans);
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
using namespace std; const int MAXN = 5010;
int n, a[MAXN]; int solve(int l, int r)
{
if(l > r) return 0;
int minh = *min_element(a + l, a + r + 1);
int ret = r - l + 1, tot = minh;
if(ret < minh)
{
for(int i = l; i <= r; i++)
a[i] = 0;
return ret;
}
else
{
for(int i = l; i <= r; i++)
a[i] -= minh;
int t = min_element(a + l, a + r + 1) - a;
tot += solve(l, t - 1) + solve(t + 1, r);
}
return min(ret, tot);
} int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("%d\n", solve(0, n - 1));
return 0;
}
Problem D:
1 second
256 megabytes
standard input
standard output
Bizon the Champion isn't just charming, he also is very smart.
While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication
table, where the element on the intersection of the i-th row and j-th
column equals i·j (the rows and columns of the table are numbered
starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always
answered correctly and immediately. Can you repeat his success?
Consider the given multiplication table. If you write out all n·m numbers
from the table in the non-decreasing order, then the k-th number you write out is called the k-th
largest number.
The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).
Print the k-th largest number in a n × m multiplication
table.
2 2 2
2
2 3 4
3
1 10 5
5
传送门:点击打开链接
解题思路:
二分。须要求的是n*m乘法表中第k大的数。我们能够对这个数ans进行二分查找,区间是[1, n * m],对于每个可能的ans,我们求出比他小的数的个数sum += min((mid - 1) / i, m);(i = 1,2,3,..,n),记录下小于k的最大的mid。即为我们所求的ans。
代码:
#include <cstdio> inline long long min(long long a, int b)
{
if(a < b) return a;
return b;
} int main()
{
int n, m;
long long k, ans, l, r, sum, mid;
scanf("%d%d%I64d", &n, &m, &k);
l = 1, r = 1ll * n * m;//r = (long long)n * m;
while(l <= r)
{
mid = (l + r) >> 1;
sum = 0;
for(int i = 1; i <= n; i++)
sum += min((mid - 1) / i, m);
if(sum < k)
l = mid + 1, ans = mid;
else
r = mid - 1;
}
printf("%I64d\n", ans);
return 0;
}
Codeforces Round #256 (Div. 2) 题解的更多相关文章
-
Codeforces Round #182 (Div. 1)题解【ABCD】
Codeforces Round #182 (Div. 1)题解 A题:Yaroslav and Sequence1 题意: 给你\(2*n+1\)个元素,你每次可以进行无数种操作,每次操作必须选择其 ...
-
Codeforces Round #608 (Div. 2) 题解
目录 Codeforces Round #608 (Div. 2) 题解 前言 A. Suits 题意 做法 程序 B. Blocks 题意 做法 程序 C. Shawarma Tent 题意 做法 ...
-
Codeforces Round #525 (Div. 2)题解
Codeforces Round #525 (Div. 2)题解 题解 CF1088A [Ehab and another construction problem] 依据题意枚举即可 # inclu ...
-
Codeforces Round #528 (Div. 2)题解
Codeforces Round #528 (Div. 2)题解 A. Right-Left Cipher 很明显这道题按题意逆序解码即可 Code: # include <bits/stdc+ ...
-
Codeforces Round #466 (Div. 2) 题解940A 940B 940C 940D 940E 940F
Codeforces Round #466 (Div. 2) 题解 A.Points on the line 题目大意: 给你一个数列,定义数列的权值为最大值减去最小值,问最少删除几个数,使得数列的权 ...
-
Codeforces Round #677 (Div. 3) 题解
Codeforces Round #677 (Div. 3) 题解 A. Boring Apartments 题目 题解 简单签到题,直接数,小于这个数的\(+10\). 代码 #include &l ...
-
Codeforces Round #665 (Div. 2) 题解
Codeforces Round #665 (Div. 2) 题解 写得有点晚了,估计都官方题解看完切掉了,没人看我的了qaq. 目录 Codeforces Round #665 (Div. 2) 题 ...
-
Codeforces Round #160 (Div. 1) 题解【ABCD】
Codeforces Round #160 (Div. 1) A - Maxim and Discounts 题意 给你n个折扣,m个物品,每个折扣都可以使用无限次,每次你使用第i个折扣的时候,你必须 ...
-
Codeforces Round #383 (Div. 2) 题解【ABCDE】
Codeforces Round #383 (Div. 2) A. Arpa's hard exam and Mehrdad's naive cheat 题意 求1378^n mod 10 题解 直接 ...
随机推荐
-
Microsoft AzureStorageAccount for Powershell
使用Powershell 创建的存储账户,注意StorageAccountName只能使用小写字母以及数字, -Location参考http://www.cnblogs.com/SignalTips/ ...
-
HDU_2052——画矩形
Problem Description Give you the width and height of the rectangle,darw it. Input Input contains a ...
-
Oracle表连接总结
1 简述 1) 两个表的连接,是通过将一个表中的一列或者多列同另一个表中的列链接而建立起来的.用来连接两张表的表达式组成了连接条件.当连接成功后,第二张表中的数据就同第一张表连接起来了,并形成了复合结 ...
-
Xenomai 3 和 PREEMPT_RT 有哪些优势相比,
Q: 我可以在我的开发板PREEMPT_RT直接在内核环境中执行POSIX应用, 使用Xenomai3 这是什么原因它? A:假设你的应用程序已经完全是POSIX,而且性能也满足,则,而且也没有理由去 ...
-
sql server 删除大量数据的一次坑爹之旅
数据库有1kw数据不在使用了,影响读写速度,于是要删除掉 使用delete语句 意外发生,持续了半个小时后,依然不见结束的迹象 于是强行结束(停止了服务) 再打开服务后,数据库显示 [正在恢复] 百度 ...
-
Spring 配置 定时任务
官档地址:https://docs.spring.io/spring/docs/5.1.4.RELEASE/spring-framework-reference/integration.html#sc ...
-
<;操作系统>;进程和线程
进程 定义: 一个正在执行的程序: 一个正在计算机上执行的程序实例; 能分配给处理器并由处理器执行的实体: 一个由一组执行指令,一个当前状态和一组相关的系统资源表征的活动单元. 进程的基本元素:程序代 ...
-
vue 非父子组件传值
/*非父子组件传值 1.新建一个js文件 然后引入vue 实例化vue 最后暴露这个实例 2.在要广播的地方引入刚才定义的实例 3.通过 VueEmit.$emit('名称','数据') 4.在接收收 ...
-
CRC8算法DELPHI源码
unit Crc8; interface Uses Classes, Windows; Function Crc_8n(p : array of BYTE; len : BYTE) : Byte; i ...
-
NATS_12:NATS Streaming详解
NATS Streaming NATS Streaming是一个以NATS为驱动的数据流系统且它的源码也是由Golang语言编写的.其中NATS Streaming服务是一个可执行的文件名为:nats ...