第二十八次codeforces竞技结束 #291 Div 2

# Name A Chewbaсca and Number standard input/output 1 s, 256 MB x3704 B Han Solo and Lazer Gun standard input/output 1 s, 256 MB x2790 C Watto and Mechanism standard input/output 3 s, 256 MB x895 D R2D2 and Droid Army standard input/outpu

 

 

#	Name
A	Chewbaсca and Number standard input/output 1 s, 256 MB		x3704
B	Han Solo and Lazer Gun standard input/output 1 s, 256 MB		x2790
C	Watto and Mechanism standard input/output 3 s, 256 MB		x895
D	R2D2 and Droid Army standard input/output 2 s, 256 MB		x744

这次在C题上纠结的有点多了浪费了不少时间……

Codeforces Round #291 (Div. 2)

A. Chewbaсca and Number

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Luke Skywalker gave Chewbacca an integer number x. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digit t means replacing it with digit 9?-?t.

Help Chewbacca to transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits. The decimal representation of the final number shouldn't start with a zero.

Input

The first line contains a single integer x (1?≤?x?≤?1018) — the number that Luke Skywalker gave to Chewbacca.

Output

Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.

Sample test(s)

input

27

output

22

input

4545

output

4444

关于这道题我只想说“哈哈哈哈哈哈我居然WA了4次哈哈哈哈…… ”

其实读题真的是很重要的事情，The number shouldn't contain leading zeroes 意思是，数字不含前导零…… 没看见……

题意是说，给你一个数字，你可以将其中任意数位的数字变成（9-当前数字），需要获得一个最小的数（但是不含前导零！）。

所以基本上就是一个把大于等于5的都变成9和当前数字的差，然后注意首位如果是0请改成9，即可…… 叹气，不审题害死人呐

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;	cin>>s;
	for(int i=0;i<s.length int now="s[i]-'0';" if cout else return><br>

<p>
</p>
<h2 id="B-Han-Solo-and-Lazer-Gun">B. Han Solo and Lazer Gun</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>
There are <span><em>n</em></span> Imperial stormtroopers on the field. The battle field is a plane with Cartesian coordinate system. Each stormtrooper is associated with his
 coordinates <span>(<em>x</em>,?<em>y</em>)</span> on this plane.</p>
<p>
Han Solo has the newest duplex lazer gun to fight these stormtroopers. It is situated at the point <span>(<em>x</em><span>0</span>,?<em>y</em><span>0</span>)</span>.
 In one shot it can can destroy all the stormtroopers, situated on some line that crosses point <span>(<em>x</em><span>0</span>,?<em>y</em><span>0</span>)</span>.</p>
<p>
Your task is to determine what minimum number of shots Han Solo needs to defeat all the stormtroopers.</p>
<p>
The gun is the newest invention, it shoots very quickly and even after a very large number of shots the stormtroopers don't have enough time to realize what's happening and change their location.</p>

<p>
</p>
<p>
Input</p>
<p>
The first line contains three integers <span><em>n</em></span>, <span><em>x</em><span>0</span></span> и <span><em>y</em><span>0</span></span> (<span>1?≤?<em>n</em>?≤?1000</span>, <span>?-?10<span>4</span>?≤?<em>x</em><span>0</span>,?<em>y</em><span>0</span>?≤?10<span>4</span></span>)
 — the number of stormtroopers on the battle field and the coordinates of your gun.</p>
<p>
Next <span><em>n</em></span> lines contain two integers each <span><em>x</em><span><em>i</em></span></span>, <span><em>y</em><span><em>i</em></span></span> (<span>?-?10<span>4</span>?≤?<em>x</em><span><em>i</em></span>,?<em>y</em><span><em>i</em></span>?≤?10<span>4</span></span>)
 — the coordinates of the stormtroopers on the battlefield. It is guaranteed that no stormtrooper stands at the same point with the gun. Multiple stormtroopers can stand at the same point.</p>

<p>
</p>
<p>
Output</p>
<p>
Print a single integer — the minimum number of shots Han Solo needs to destroy all the stormtroopers.</p>

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

output

2

input

2 1 2
1 1
1 0

output

1

Note

Explanation to the first and second samples from the statement, respectively:

这道题比起A对于参赛者而言倒是最简单AC的一个，告诉你雷射炮的坐标和敌人的坐标，问你多少枪能把他们全干掉。

题意解析的话大概是这么个情况，从炮台坐标开始画多少条直线能穿透所有已知点。

再优化一下就相对坐标系一下，就是把炮台所在点视为原点，那么斜率相同的（没有斜率的也互相称作相同）即为在同一次攻击内被干掉。

一旦有除法要考虑精度浮点数判断相等的时候就很头疼，于是我用了分数表示斜率的方法，用map存一个来代表 n/m 这样一个分数的斜率，化为最简分数即可。

我的这种方法需要考虑到的为以下问题：

1、 其中有一个为0的时候，因为0和非0数组成的分数，要么就是无斜率的0分母斜率，要么就是求最大公约数没办法把各种分之0化为相同的。于是一旦遇到一个为0，另一个为非0，我们就把他变成 0/1 和 1/0 的形式存即可。

2、 都为0的时候，您是不是怎么打都会死……

3、 这里我用的是map，很棒的STL，如果有不懂的可以这么理解，map是一个数组，但是下标可以为任何的东西，此处我用的下表是点对，就是分数。m[make_pair(a,b)]就是下标为的意思。

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;
}

int x[1001]={0};
int y[1001]={0};
map<pair>,int> m;

int main()
{
	int n;	cin>>n;
	cin>>x[0]>>y[0];
	for(int ni=1;ni<br>
<br>


<p>
</p><p>
</p><p>
</p><p>
</p><p>
</p><p>
</p><h2 id="C-Watto-and-Mechanism">C. Watto and Mechanism</h2>
<p>
</p><p>
time limit per test</p>
3 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>
Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with <span><em>n</em></span> strings.
 Then the mechanism should be able to process queries of the following type: "Given string <span><em>s</em></span>, determine if the memory of the mechanism contains string <span><em>t</em></span> that
 consists of the same number of characters as <span><em>s</em></span> and differs from <span><em>s</em></span> in
 exactly one position".</p>
<p>
Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of <span><em>n</em></span> initial lines and <span><em>m</em></span> queries.
 He decided to entrust this job to you.</p>

<p>
</p><p>
Input</p>
<p>
The first line contains two non-negative numbers <span><em>n</em></span> and <span><em>m</em></span> (<span>0?≤?<em>n</em>?≤?3·10<span>5</span></span>, <span>0?≤?<em>m</em>?≤?3·10<span>5</span></span>)
 — the number of the initial strings and the number of queries, respectively.</p>
<p>
Next follow <span><em>n</em></span> non-empty strings that are uploaded to the memory of the mechanism.</p>
<p>
Next follow <span><em>m</em></span> non-empty strings that are the queries to the mechanism.</p>
<p>
The total length of lines in the input doesn't exceed <span>6·10<span>5</span></span>.
 Each line consists <span>only</span> of letters <span>'a'</span>, <span>'b'</span>,<span>'c'</span>.</p>

<p>
</p><p>
Output</p>
<p>
For each query print on a single line "<span>YES</span>" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "<span>NO</span>"
 (without the quotes).</p>

<p>
</p><p>
Sample test(s)</p>
<p>
</p><p>
</p><p>
input</p>
<pre class="brush:php;toolbar:false">2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

output

YES
NO
NO

题意的话是在说，先给你n个字符串，然后进行m次询问，每次询问一个字符串，问之前给出的n个字符串内有没有字符串可以在刚好改动一个字母的情况下获得当前字符串。

这道题，出题人给的解题方法是Hash，我个人原先的想法是字典树建一棵树，每次询问从root开始向下找目标节点，有一次非相同机会，如果找不到已有节点则使用，并在当前节点bfs，但这种方法有问题，比如在某节点其实应该认作不同，但字典树中刚好有另一个字符串的此位置有这个字母，就这辈子都找不到了……果然不能这样。那么Hash应该怎么做呢？

解题报告是这么说的：

While adding a string to the set, let's count its polynomial hash and add it to an array. Then let's sort this array. Now, to know the query answer, let's try to change every symbol in the string and check with binary search if its hash can be found in the array (recounting hashes with O(1) complexity). If the hash is found in the array, the answer is "YES", otherwise "NO".

简单的说，hash，排序，询问的字符串每个字母都变，找hash是否存在。over

Code：

#include <bits>
typedef long long int lnt;
typedef double dou;
using namespace std;
#define N 600514
int nx[N*2][3],spt;
int newnode(){
	for(int i=0;i >mp[3];
int n,m;
char s[N];
int r1,r2;
int st1[N],t1;
int st2[N],t2;
int solve(){
	if(scanf("%d %d",&n,&m)==EOF)return 0;
	spt=1;
	r1=newnode();
	r2=newnode();
	for(int i=0;i<n scanf add int l="0;for(;s[l];l++);" for j="0;j+j<l;j++)swap(s[j],s[l-1-j]);" mp>(st1[j],st2[t1-2-j]));
		}
	}
	////////////////////
	for(int i=0;i<m scanf add int l="0;for(;s[l];l++);" for j="0;j+j<l;j++)swap(s[j],s[l-1-j]);" flag="0;" a="s[l-1-j]-'a';" if>(st1[j],st2[t1-2-j]))!=mp[0].end()){flag=1;break;}
			if(a!=1&&mp[1].find(pair<int>(st1[j],st2[t1-2-j]))!=mp[1].end()){flag=1;break;}
			if(a!=2&&mp[2].find(pair<int>(st1[j],st2[t1-2-j]))!=mp[2].end()){flag=1;break;}
		}
		puts(flag?"YES":"NO");
	}
	mp[0].clear();
	mp[1].clear();
	mp[2].clear();
	return 1;
}
int main(){
	while(solve());
	return 0;
}</int></int></m></n></bits>

字典树的话其实也是行得通的，建立字典树进行dfs即可（我比赛的时候为啥要用bfs……哭）

Code：

#include<bits>
const int maxnode=6e5+100;
const int sigma_size=3;
using namespace std;
int n,m;
int ch[maxnode][sigma_size],val[maxnode];
int sz;
void init(){
    memset(ch,0,sizeof ch);
    memset(val,0,sizeof(val));
    sz=1;
}
void insert(char *s)
{
    int u=0,l=strlen(s);
    for(int i=0; i<l int c="s[i]-'a';" if ch u="ch[u][c];" val char s bool dfs rt p d l>1) return false;
    if(p==l){
        if(d==1&&val[rt]) return true;
        return false;
    }
    for(int i=0;i<sigma_size if return true false int main init scanf for i="0;" insert printf else><br>
<br>

<p><br>
</p>

<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<h2 id="D-R-D-and-Droid-Army">D. R2D2 and Droid Army</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>
An army of <span><em>n</em></span> droids is lined up in one row. Each droid is described by <span><em>m</em></span> integers <span><em>a</em><span>1</span>,?<em>a</em><span>2</span>,?...,?<em>a</em><span><em>m</em></span></span>,
 where <span><em>a</em><span><em>i</em></span></span>is
 the number of details of the <span><em>i</em></span>-th type in this droid's mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He has <span><em>m</em></span> weapons,
 the <span><em>i</em></span>-th weapon can affect all the droids in the army by destroying one detail of the <span><em>i</em></span>-th
 type (if the droid doesn't have details of this type, nothing happens to it).</p>
<p>
A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at most <span><em>k</em></span>shots. How many shots from the weapon of what type
 should R2-D2 make to destroy the sequence of consecutive droids of maximum length?</p>

<p>
</p>
<p>
Input</p>
<p>
The first line contains three integers <span><em>n</em>,?<em>m</em>,?<em>k</em></span> (<span>1?≤?<em>n</em>?≤?10<span>5</span></span>, <span>1?≤?<em>m</em>?≤?5</span>, <span>0?≤?<em>k</em>?≤?10<span>9</span></span>)
 — the number of droids, the number of detail types and the number of available shots, respectively.</p>
<p>
Next <span><em>n</em></span> lines follow describing the droids. Each line contains <span><em>m</em></span> integers <span><em>a</em><span>1</span>,?<em>a</em><span>2</span>,?...,?<em>a</em><span><em>m</em></span></span> (<span>0?≤?<em>a</em><span><em>i</em></span>?≤?10<span>8</span></span>),
 where <span><em>a</em><span><em>i</em></span></span> is
 the number of details of the <span><em>i</em></span>-th type for the respective robot.</p>

<p>
</p>
<p>
Output</p>
<p>
Print <span><em>m</em></span> space-separated integers, where the <span><em>i</em></span>-th
 number is the number of shots from the weapon of the <span><em>i</em></span>-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum
 length.</p>
<p>
If there are multiple optimal solutions, print any of them.</p>
<p>
It is not necessary to make exactly <span><em>k</em></span> shots, the number of shots can be less.</p>

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

output

2 2

input

3 2 4
1 2
1 3
2 2

output

1 3

Note

In the first test the second, third and fourth droids will be destroyed.

In the second test the first and second droids will be destroyed.

关于D……没来的及看，当时卡C太狠了，但是似乎是个队列的问题，先存个代码和解题报告备看

To destroy all the droids on a segment of l to r, we need to make sum_m(Max_r cnt[i][j])  shots, where cnt[i][j] — number of j-type details in i-th droid. Let's support two pointers — on the beginning and on the end of the segment, which we want to destroy all the droids on. If we can destroy droids on current segment, let's increase right border of the segment, otherwise increase left border, updating the answer after every segment change. Let's use a queue in order to find the segment maximum effectively.

Code：

#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define ls rt > 1
#define LL long long
#define ULL unsigned long long
#define pii pair <ll ll>

using namespace std;

const int N = 100005, mod = 1e9 + 7, M = 100;
int n, m, k;
int q[N][6], a[N][6], r[6], f[6], e[6];

inline void inq (int id, int x) {
    while (f[id] = a[q[e[id]][id]][id]) e[id]--;
    q[++e[id]][id] = x;
}

inline void outq (int id, int x) {
    if (q[f[id]][id]  k;
}

inline int read() {
    int x=0; char ch=getchar();
    while(ch'9'){ch=getchar();}
    while(ch>='0'&&ch> n >> m >> k;
    for (int i = 1; i <br>
<br>

<p><br>
</p>


</ll></cstdlib></cmath></cstdio></iostream></algorithm></bitset></stack></set></map></vector></cstring>