这次CF感觉挺简单的,但是我思路不够宽
A. Fake NP
Tavak
and Seyyed are good friends. Seyyed
is very funny
and he told Tavak
to solve
the following problem
instead of longest-path.
You are
given l
and r. For all integers
from l
to r, inclusive, we wrote down all
of their
integer divisors except
1. Find
the integer that we wrote down
the maximum
number of times.
Solve
the problem
to show
that it's
not a NP problem.
Input
The
first line
contains two integers l
and r (
2 ≤ l ≤ r ≤
109).
Output
Print single
integer,
the integer that appears maximum
number of times in the divisors.
If there are multiple answers, print any
of them.
这题签到题,如果
l==r
,那么出现次数最多为1,如果
l!=r
那么出现次数最多的为0
int main() {
int l, r;
cin >> l >> r;
if (l == r) {
cout << l << endl;
}
else {
cout <<
2 << endl;
}
return 0;
}
B.
3-palindrome
time limit per test1
second
memory limit per test256 megabytes
inputstandard input
outputstandard output
In
the beginning of the new
year Keivan decided
to reverse his
name. He doesn't like palindromes, so he changed Naviek
to Navick.
He
is too selfish, so
for a
given n he wants
to obtain a
string of n
characters, each
of which
is either 'a', 'b'
or 'c',
with no palindromes
of length 3 appearing
in the string as a substring. For example,
the strings
"abc" and "abca" suit him,
while the string "aba" doesn't. He also want
the number of letters 'c'
in his
string to be
as little
as possible.
Input
The
first line
contains single
integer n (
1 ≤ n ≤
2·
105) —
the length of the string.
Output
Print
the string that satisfies all
the constraints.
If there are multiple answers, print any
of them.
这题题目要求输出满足条件的字符串,C经可能小,那么只用不断的输出aa,bb,即可
int main(){
int n;
cin >> n;
string fuck =
"aabb";
for(
int i =
0;i < n; i++){
putchar(fuck[i%
4]);
}
puts(
"");
return 0;
}
C. Find Amir
time limit per test1
second
memory limit per test256 megabytes
inputstandard input
outputstandard output
A few years ago Sajjad left his school
and register
to another
one due
to security reasons. Now he wishes
to find Amir,
one of his schoolmates
and good friends.
There are n schools numerated
from 1 to n. One can travel between
each pair
of them,
to do so, he needs
to buy
a ticket. The ticker between schools i
and j costs
and can be used multiple times. Help Sajjad
to find
the minimum cost he needs
to pay
for tickets
to visit all schools. He can start
and finish
in any school.
Input
The
first line contains a single
integer n (
1 ≤ n ≤
105) —
the number of schools.
Output
Print single
integer:
the minimum cost
of tickets needed
to visit all schools
题目要求输出最少的花费来经过全部学校,其中票可以复用。我们 先分析下,票的花费函数是这样的:
Cost=(i+j)mod(n+1)
那么第一种情况就是
i=1,j=n
,这样花费为0,然后i,j不断的向n/2逼近,保证每次消耗都是最少的。 以
1,2,3
为例
Cost1=(1+3)mod(1+3)
Cost2=(3+2)mod(1+3)
Cost=Cost1+Cost2
消耗就为1
int main()
{
int n;
cin>>n;
cout<<(n+
1)/
2-
1<<endl;
}
D. Minimum
number of steps
time limit per test1
second
memory limit per test256 megabytes
inputstandard input
outputstandard output
We have a
string of letters 'a'
and 'b'. We want
to perform
some operations
on it. On each step we choose one
of substrings
"ab" in the string and replace
it with the string "bba". If we have no
"ab" as a substring, our job
is done. Print
the minimum
number of steps we should perform
to make our job done modulo
109 +
7.
The
string "ab" appears
as a substring
if there
is a letter 'b' right
after the letter 'a' somewhere
in the string.
Input
The
first line
contains the initial
string consisting
of letters 'a'
and 'b' only
with length from 1 to 106.
Output
Print
the minimum
number of steps modulo
109 +
7.
这题是输出按照要求变换字符串所需的最小次数