search
HomeDatabaseMysql Tutorial第二十九次codeforces竞技结束 #293 Div 2

Problems # Name A Vitaly and Strings standard input/output 1 s, 256 MB x2731 B Tanya and Postcard standard input/output 2 s, 256 MB x2749 C Anya and Smartphone standard input/output 1 s, 256 MB x2299 D Ilya and Escalator standard input/out

Problems

第二十九次codeforces竞技结束 #293 Div 2

 

 

# Name    
A

Vitaly and Strings

standard input/output

1 s, 256 MB
第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 x2731
B

Tanya and Postcard

standard input/output

2 s, 256 MB
第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 x2749
C

Anya and Smartphone

standard input/output

1 s, 256 MB
第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 x2299
D

Ilya and Escalator

standard input/output

2 s, 256 MB
第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 第二十九次codeforces竞技结束 #293 Div 2 x1453

向来赛完不写解题报告就会时运Down,以后不敢了Q^Q

这场比赛是相对较为简单,容易想到思路,适宜冲紫名的一场,但可惜Pretest数据可能弱了些让大家过的太爽了于是FST就多了起来反而掉分现象普及。

那么,一个个来看看吧


A. Vitaly and Strings

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vitaly is a diligent student who never missed a lesson in his five years of studying in the university. He always does his homework on time and passes his exams in time.

During the last lesson the teacher has provided two strings s and t to Vitaly. The strings have the same length, they consist of lowercase English letters, string s is lexicographically smaller than string t. Vitaly wondered if there is such string that is lexicographically larger than string s and at the same is lexicographically smaller than string t. This string should also consist of lowercase English letters and have the length equal to the lengths of strings s and t.

Let's help Vitaly solve this easy problem!

Input

The first line contains string s (1?≤?|s|?≤?100), consisting of lowercase English letters. Here, |s| denotes the length of the string.

The second line contains string t (|t|?=?|s|), consisting of lowercase English letters.

It is guaranteed that the lengths of strings s and t are the same and string s is lexicographically less than string t.

Output

If the string that meets the given requirements doesn't exist, print a single string "No such string" (without the quotes).

If such string exists, print it. If there are multiple valid strings, you may print any of them.

Sample test(s)

input

a
c

output

b

input

aaa
zzz

output

kkk

input

abcdefg
abcdefh

output

No such string

Note

String s?=?s1s2... sn is said to be lexicographically smaller than t?=?t1t2... tn, if there exists such i, that s1?=?t1,?s2?=?t2,?... si?-?1?=?ti?-?1,?si?ti.


简单来说,给了两个字符串,问他们之间存在字典序夹在二者之间的字符串嘛?有的话随便输出一个,没有的话输出“No such string”,题目中已经告知了s一定字典序小于t,那么s的最后一位加一看看是不是和t一样不就行了嘛?一样就是不存在,不一样就输出咯?

嘿嘿,有坑哦~ 如果末位是z怎么办,如果末位是两个、三个……n个z怎么办呢?这不是数字可以9变成0然后进位哦~ 对了,我们自己用while写一个类似进位的操作不久好了嘛?

Code:

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

#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a) b;
}

int main()
{
	string s,t; cin>>s>>t;
	int l=s.length()-1;
	while(s[l]=='z')
	{
		s[l]='a';
		l--;
	}
	s[l]=s[l]+1;
	if(s==t) cout<br>

<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<h2 id="B-Tanya-and-Postcard">B. Tanya and Postcard</h2>
<p>
</p>
<p>
time limit per test</p>
2 seconds
<p>
</p>
<p>
memory limit per test</p>
256 megabytes
<p>
</p>
<p>
input</p>
standard input
<p>
</p>
<p>
output</p>
standard output

<p>
</p>
<p>
Little Tanya decided to present her dad a postcard on his Birthday. She has already created a message — string <span><em>s</em></span> of length <span><em>n</em></span>,
 consisting of uppercase and lowercase English letters. Tanya can't write yet, so she found a newspaper and decided to cut out the letters and glue them into the postcard to achieve string <span><em>s</em></span>.
 The newspaper contains string <span><em>t</em></span>, consisting of uppercase and lowercase English letters. We know that the length of string <span><em>t</em></span> greater
 or equal to the length of the string <span><em>s</em></span>.</p>
<p>
The newspaper may possibly have too few of some letters needed to make the text and too many of some other letters. That's why Tanya wants to cut some <span><em>n</em></span> letters
 out of the newspaper and make a message of length exactly <span><em>n</em></span>, so that it looked as much as possible like <span><em>s</em></span>.
 If the letter in some position has correct value and correct letter case (in the string <span><em>s</em></span> and in the string that Tanya will make), then she shouts joyfully
 "<span>YAY!</span>", and if the letter in the given position has only the correct value but it is in the wrong case, then the girl says "<span>WHOOPS</span>".</p>
<p>
Tanya wants to make such message that lets her shout "<span>YAY!</span>" as much as possible. If there are multiple ways to do this, then her second priority is to maximize
 the number of times she says "<span>WHOOPS</span>". Your task is to help Tanya make the message.</p>

<p>
</p>
<p>
Input</p>
<p>
The first line contains line <span><em>s</em></span> (<span>1?≤?|<em>s</em>|?≤?2·10<span>5</span></span>),
 consisting of uppercase and lowercase English letters — the text of Tanya's message.</p>
<p>
The second line contains line <span><em>t</em></span> (<span>|<em>s</em>|?≤?|<em>t</em>|?≤?2·10<span>5</span></span>),
 consisting of uppercase and lowercase English letters — the text written in the newspaper.</p>
<p>
Here <span>|<em>a</em>|</span> means the length of the string <span><em>a</em></span>.</p>

<p>
</p>
<p>
Output</p>
<p>
Print two integers separated by a space:</p>
<ul>
<li>
the first number is the number of times Tanya shouts "<span>YAY!</span>" while making the message,</li>
<li>
the second number is the number of times Tanya says "<span>WHOOPS</span>" while making the message.</li>
</ul>

<p>
</p>
<p>
Sample test(s)</p>
<p>
</p>
<p>
</p>
<p>
input</p>
<pre class="brush:php;toolbar:false">AbC
DCbA

output

3 0

input

ABC
abc

output

0 3

input

abacaba
AbaCaBA

output

3 4


说有一个小盆友他在报纸上剪下字来拼一个明信片,如果和自己想的字符一样而且大小写也一样了她就说“YAY”,如果字符一样大小写不一样她就说“Whoops”

要求YAY最多的情况中Whoops最多时的两者数量。

简单的说,给定两个字符串,问在第二个字符串中有多少个a中的严格区分大小写字符,排除掉这些字符后不严格区分大小写的有多少个。

因为字符串不长,可以暴力枚举。

先读一遍s得知需要哪些东西(这里想想我当时为啥hash呢,map简直轻松愉快呀,读者可以试试使用map mp,然后mp[a]++这样的操作,会比起数组hash来惬意的多),然后在t中找,严格区分大小写的数完记得减掉,然后再找一次不区分大小写的,输出两个数字即可。

Code:

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

#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a) b;
}

int cntl[26]={0},cntu[26]={0};	//cnt
int nedl[26]={0},nedu[26]={0};	//need

int main()
{
	int yay=0,whoops=0;
	string s,t; cin>>s>>t;
	for(int i=0;i<s.length if nedu else nedl for i="0;i<t.length();i++)" cntu cntl int p="min(nedl[i],cntl[i]);" cout return><br>

<p>
</p>
<h2 id="C-Anya-and-Smartphone">C. Anya and Smartphone</h2>
<p>
</p>
<p>
time limit per test</p>
1 second
<p>
</p>
<p>
memory limit per test</p>
256 megabytes
<p>
</p>
<p>
input</p>
standard input
<p>
</p>
<p>
output</p>
standard output

<p>
</p>
<p>
Anya has bought a new smartphone that uses <span>Berdroid</span> operating system. The smartphone menu has exactly <span><em>n</em></span> applications,
 each application has its own icon. The icons are located on different screens, one screen contains <span><em>k</em></span> icons. The icons from the first to the <span><em>k</em></span>-th
 one are located on the first screen, from the <span>(<em>k</em>?+?1)</span>-th to the <span>2<em>k</em></span>-th
 ones are on the second screen and so on (the last screen may be partially empty).</p>
<p>
Initially the smartphone menu is showing the screen number <span>1</span>. To launch the application with the icon located on the screen <span><em>t</em></span>,
 Anya needs to make the following gestures: first she scrolls to the required screen number <span><em>t</em></span>, by making <span><em>t</em>?-?1</span> gestures
 (if the icon is on the screen <span><em>t</em></span>), and then make another gesture — press the icon of the required application exactly once to launch it.</p>
<p>
After the application is launched, the menu returns to the first screen. That is, to launch the next application you need to scroll through the menu again starting from the screen number <span>1</span>.</p>
<p>
All applications are numbered from <span>1</span> to <span><em>n</em></span>. We know a certain
 order in which the icons of the applications are located in the menu at the beginning, but it changes as long as you use the operating system. <span>Berdroid</span> is intelligent system, so it changes the
 order of the icons by moving the more frequently used icons to the beginning of the list. Formally, right after an application is launched, Berdroid swaps the application icon and the icon of a preceding application (that is, the icon of an application on
 the position that is smaller by one in the order of menu). The preceding icon may possibly be located on the adjacent screen. The only exception is when the icon of the launched application already occupies the first place, in this case the icon arrangement
 doesn't change.</p>
<p>
Anya has planned the order in which she will launch applications. How many gestures should Anya make to launch the applications in the planned order?</p>
<p>
Note that one application may be launched multiple times.</p>

<p>
</p>
<p>
Input</p>
<p>
The first line of the input contains three numbers <span><em>n</em>,?<em>m</em>,?<em>k</em></span> (<span>1?≤?<em>n</em>,?<em>m</em>,?<em>k</em>?≤?10<span>5</span></span>) — the
 number of applications that Anya has on her smartphone, the number of applications that will be launched and the number of icons that are located on the same screen.</p>
<p>
The next line contains <span><em>n</em></span> integers, permutation <span><em>a</em><span>1</span>,?<em>a</em><span>2</span>,?...,?<em>a</em><span><em>n</em></span></span> — the
 initial order of icons from left to right in the menu (from the first to the last one), <span><em>a</em><span><em>i</em></span></span> — 
 is the id of the application, whose icon goes <span><em>i</em></span>-th in the menu. Each integer from <span>1</span> to <span><em>n</em></span> occurs
 exactly once among <span><em>a</em><span><em>i</em></span></span>.</p>
<p>
The third line contains <span><em>m</em></span> integers <span><em>b</em><span>1</span>,?<em>b</em><span>2</span>,?...,?<em>b</em><span><em>m</em></span>(1?≤?<em>b</em><span><em>i</em></span>?≤?<em>n</em>)</span> — the
 ids of the launched applications in the planned order. One application may be launched multiple times.</p>

<p>
</p>
<p>
Output</p>
<p>
Print a single number — the number of gestures that Anya needs to make to launch all the applications in the desired order.</p>

<p>
</p>
<p>
Sample test(s)</p>
<p>
</p>
<p>
</p>
<p>
input</p>
<pre class="brush:php;toolbar:false">8 3 3
1 2 3 4 5 6 7 8
7 8 1

output

7

input

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

output

8

Note

In the first test the initial configuration looks like (123)(456)(78), that is, the first screen contains icons of applications 1,?2,?3, the second screen contains icons 4,?5,?6, the third screen contains icons 7,?8.

After application 7 is launched, we get the new arrangement of the icons — (123)(457)(68). To launch it Anya makes 3gestures.

After application 8 is launched, we get configuration (123)(457)(86). To launch it Anya makes 3 gestures.

After application 1 is launched, the arrangement of icons in the menu doesn't change. To launch it Anya makes 1 gesture.

In total, Anya makes 7 gestures.


说有个智能手机,上面有n个APP,我要点其中的m个,每页最多可以放k个APP。

点击某个APP需要的手势的个数其实就是(pos/k)+(pos%k==0?0:1),即这个APP当前所在的位置除以每页最多放置的APP数,向上取整,因为我们需要滑动(当前所在页数-1)+点击1次=当前所在页数。

然后就是每次点击要前移一位的实现了:

if(pos>1)
		{
			int t=fdnum[pos-1];
			fdnum[pos-1]=now;
			fdpos[now]=pos-1;
			fdnum[pos]=t;
			fdpos[t]=pos;
		}

我用的方法是:数组1:每个位置对应当前位置的APP编号,数组2:每个APP编号当前所在的位置,然后借助临时变量t进行swap操作。

当然别忘了他就在第一页的时候不用和前一个调换位置哦。

然后,坑来了——

孩子们永远是那句话……int不是好东西啊,LL大法好啊,动不动int就溢出了烦不烦呢!明明就前300可以紫名了你就是不开心溢出让我FST,叹气……

Code:

#include <map>
#include <cmath> 
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a) b;
}

map<int> fdpos,fdnum; //num->pos & pos->num

int main()
{
	fdpos.clear();
	fdnum.clear();
	long long ans=0; // LL大法好……
	int n,m,k;	cin>>n>>m>>k;
	for(int i=1;i1)
		{
			int t=fdnum[pos-1];
			fdnum[pos-1]=now;
			fdpos[now]=pos-1;
			fdnum[pos]=t;
			fdpos[t]=pos;
		}
	}
	cout<br>

<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<h2 id="D-Ilya-and-Escalator">D. Ilya and Escalator</h2>
<p>
</p>
<p>
time limit per test</p>
2 seconds
<p>
</p>
<p>
memory limit per test</p>
256 megabytes
<p>
</p>
<p>
input</p>
standard input
<p>
</p>
<p>
output</p>
standard output

<p>
</p>
<p>
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor.</p>
<p>
Let's assume that <span><em>n</em></span> people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person
 in the queue enters the escalator with probability <span><em>p</em></span>, or the first person in the queue doesn't move with probability <span>(1?-?<em>p</em>)</span>,
 paralyzed by his fear of escalators and making the whole queue wait behind him.</p>
<p>
Formally speaking, the <span><em>i</em></span>-th person in the queue cannot enter the escalator until people with indices from <span>1</span> to <span><em>i</em>?-?1</span> inclusive
 enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number
 of people standing on the escalator after <span><em>t</em></span> seconds.</p>
<p>
Your task is to help him solve this complicated task.</p>

<p>
</p>
<p>
Input</p>
<p>
The first line of the input contains three numbers <span><em>n</em>,?<em>p</em>,?<em>t</em></span> (<span>1?≤?<em>n</em>,?<em>t</em>?≤?2000</span>, <span>0?≤?<em>p</em>?≤?1</span>).
 Numbers <span><em>n</em></span> and <span><em>t</em></span> are integers, number <span><em>p</em></span>is
 real, given with exactly two digits after the decimal point.</p>

<p>
</p>
<p>
Output</p>
<p>
Print a single real number — the expected number of people who will be standing on the escalator after <span><em>t</em></span> seconds. The absolute or relative error mustn't
 exceed <span>10<span>?-?6</span></span>.</p>

<p>
</p>
<p>
Sample test(s)</p>
<p>
</p>
<p>
</p>
<p>
input</p>
<pre class="brush:php;toolbar:false">1 0.50 1

output

0.5

input

1 0.50 4

output

0.9375

input

4 0.20 2

output

0.4


没错这就是个DP……

啊对了题意啊题意……

有个无限长的电梯,有n个人一列纵队在排队上电梯,每个人只能在前头都没人了的时候才能上电梯,每秒钟,有p的概率排在第一的人上了电梯,问:t秒后,电梯上人数的数学期望……

数学你好……概率学啦……

用dp[i][j]来表示当i个人排队时在第t秒电梯上人数的数学期望。

那么我们知道dp[i][j]应该等于

当[(i-1个人,j-1秒)时的期望+1] * p (这个人上去了)

加上 当[(i个人,j-1秒)时的期望 * (1-p) (这个人没上去)

具体的看看代码吧

Code:

#include<bits>
double dp[2005][2005];
int main()
{
	int n,t,i;
	double p;
	scanf("%d%lf%d",&n,&p,&t);
	for(i=1;i<br>
<br>

<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>


</bits>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Explain the InnoDB Buffer Pool and its importance for performance.Explain the InnoDB Buffer Pool and its importance for performance.Apr 19, 2025 am 12:24 AM

InnoDBBufferPool reduces disk I/O by caching data and indexing pages, improving database performance. Its working principle includes: 1. Data reading: Read data from BufferPool; 2. Data writing: After modifying the data, write to BufferPool and refresh it to disk regularly; 3. Cache management: Use the LRU algorithm to manage cache pages; 4. Reading mechanism: Load adjacent data pages in advance. By sizing the BufferPool and using multiple instances, database performance can be optimized.

MySQL vs. Other Programming Languages: A ComparisonMySQL vs. Other Programming Languages: A ComparisonApr 19, 2025 am 12:22 AM

Compared with other programming languages, MySQL is mainly used to store and manage data, while other languages ​​such as Python, Java, and C are used for logical processing and application development. MySQL is known for its high performance, scalability and cross-platform support, suitable for data management needs, while other languages ​​have advantages in their respective fields such as data analytics, enterprise applications, and system programming.

Learning MySQL: A Step-by-Step Guide for New UsersLearning MySQL: A Step-by-Step Guide for New UsersApr 19, 2025 am 12:19 AM

MySQL is worth learning because it is a powerful open source database management system suitable for data storage, management and analysis. 1) MySQL is a relational database that uses SQL to operate data and is suitable for structured data management. 2) The SQL language is the key to interacting with MySQL and supports CRUD operations. 3) The working principle of MySQL includes client/server architecture, storage engine and query optimizer. 4) Basic usage includes creating databases and tables, and advanced usage involves joining tables using JOIN. 5) Common errors include syntax errors and permission issues, and debugging skills include checking syntax and using EXPLAIN commands. 6) Performance optimization involves the use of indexes, optimization of SQL statements and regular maintenance of databases.

MySQL: Essential Skills for Beginners to MasterMySQL: Essential Skills for Beginners to MasterApr 18, 2025 am 12:24 AM

MySQL is suitable for beginners to learn database skills. 1. Install MySQL server and client tools. 2. Understand basic SQL queries, such as SELECT. 3. Master data operations: create tables, insert, update, and delete data. 4. Learn advanced skills: subquery and window functions. 5. Debugging and optimization: Check syntax, use indexes, avoid SELECT*, and use LIMIT.

MySQL: Structured Data and Relational DatabasesMySQL: Structured Data and Relational DatabasesApr 18, 2025 am 12:22 AM

MySQL efficiently manages structured data through table structure and SQL query, and implements inter-table relationships through foreign keys. 1. Define the data format and type when creating a table. 2. Use foreign keys to establish relationships between tables. 3. Improve performance through indexing and query optimization. 4. Regularly backup and monitor databases to ensure data security and performance optimization.

MySQL: Key Features and Capabilities ExplainedMySQL: Key Features and Capabilities ExplainedApr 18, 2025 am 12:17 AM

MySQL is an open source relational database management system that is widely used in Web development. Its key features include: 1. Supports multiple storage engines, such as InnoDB and MyISAM, suitable for different scenarios; 2. Provides master-slave replication functions to facilitate load balancing and data backup; 3. Improve query efficiency through query optimization and index use.

The Purpose of SQL: Interacting with MySQL DatabasesThe Purpose of SQL: Interacting with MySQL DatabasesApr 18, 2025 am 12:12 AM

SQL is used to interact with MySQL database to realize data addition, deletion, modification, inspection and database design. 1) SQL performs data operations through SELECT, INSERT, UPDATE, DELETE statements; 2) Use CREATE, ALTER, DROP statements for database design and management; 3) Complex queries and data analysis are implemented through SQL to improve business decision-making efficiency.

MySQL for Beginners: Getting Started with Database ManagementMySQL for Beginners: Getting Started with Database ManagementApr 18, 2025 am 12:10 AM

The basic operations of MySQL include creating databases, tables, and using SQL to perform CRUD operations on data. 1. Create a database: CREATEDATABASEmy_first_db; 2. Create a table: CREATETABLEbooks(idINTAUTO_INCREMENTPRIMARYKEY, titleVARCHAR(100)NOTNULL, authorVARCHAR(100)NOTNULL, published_yearINT); 3. Insert data: INSERTINTObooks(title, author, published_year)VA

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment