# 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 #include #include #include #include #include #include #include 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
b. han solo and lazer gun
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
there are n imperial stormtroopers on the field. the battle field is a plane with cartesian coordinate system. each stormtrooper is associated with his coordinates (x,?y) on this plane.
han solo has the newest duplex lazer gun to fight these stormtroopers. it is situated at the point (x0,?y0). in one shot it can can destroy all the stormtroopers, situated on some line that crosses point (x0,?y0).
your task is to determine what minimum number of shots han solo needs to defeat all the stormtroopers.
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.
input
the first line contains three integers n, x0 и y0 (1?≤?n?≤?1000, ?-?104?≤?x0,?y0?≤?104) — the number of stormtroopers on the battle field and the coordinates of your gun.
next n lines contain two integers each xi, yi (?-?104?≤?xi,?yi?≤?104) — 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.
output
print a single integer — the minimum number of shots han solo needs to destroy all the stormtroopers.
sample test(s)
input
4 0 01 12 22 0-1 -1
output
2
input
2 1 21 11 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 #include #include #include #include #include #include #include #include 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,int> m;int main(){ int n; cin>>n; cin>>x[0]>>y[0]; for(int ni=1;ni
c. watto and mechanism
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 n strings. then the mechanism should be able to process queries of the following type: given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position.
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 n initial lines and m queries. he decided to entrust this job to you.
input
the first line contains two non-negative numbers n and m (0?≤?n?≤?3·105, 0?≤?m?≤?3·105) — the number of the initial strings and the number of queries, respectively.
next follow n non-empty strings that are uploaded to the memory of the mechanism.
next follow m non-empty strings that are the queries to the mechanism.
the total length of lines in the input doesn't exceed 6·105. each line consists only of letters 'a', 'b','c'.
output
for each query print on a single line yes (without the quotes), if the memory of the mechanism contains the required string, otherwise print no (without the quotes).
sample test(s)
input
2 3aaaaaacacacaaabaaccacacccaaac
output
yesnono
题意的话是在说，先给你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 typedef long long int lnt;typedef double dou;using namespace std;#define n 600514int 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='0'&&ch> n >> m >> k; for (int i = 1; i