7.30 SDUT 2020 Summer Team Contest 2nd for19 赛后反思及总结
今天是暑假集训参加的第二场组队训练赛
虽然因为疫情的原因我甚至不知道队员到底是长什么样子 QAQ
但是感觉互相之间还是比较有默契的
每个人都有比较擅长的部分 刚好可以互补
我在各算法方面比较欠缺 但是其他队员的存在恰好弥补了这一部分
自己也要加把劲
今日AC：6题
自认为AC的题中最难的是H - Hash Code Hacker
题目：According to Java standard library documentation, the hash code of String is computed as s [0]×31^( n -1) + s [1]×31^( n -2) + … + s [n -1]
Here s[i] is the i-th character of the string, n is the length of the string, and ^ indicates exponentiation.
Computation uses signed 32-bit integers in two’s complement form.
Heather is going to hack the servers of Not Entirely Evil Recording Company (NEERC). To perform an attack she needs k distinct query strings that have equal hash codes. Unfortunately, NEERC servers accept query string containing lower- and uppercase English letters only.
Heather hired you to write a program that generates such query strings for her.
Input
The single line of the input file contains integer k — the number of required query strings to generate
(2 ≤ k ≤ 1000).
Output
Output k lines. Each line should contain a single query string. Each query string should be non-empty and its length should not exceed 1000 characters. Query string should contain only lower- and uppercase
English letters. All query strings should be distinct and should have equal hash codes.
题目大意： 输出k组hash数相同的字符串
这题是队友lyb想的思路，我打的代码，zyz对代码进行优化。
这题关键点在于：
s [i]×31^( n -i-1) + s [i+1]×31^( n -i-1) =
s [i-1]×31^( n -i-1) + s [i+1+31]×31^( n -i-1)
所以只需要定一个长度为1000的初始字符串，每次输出改变其中相邻两个字母 (for循环)，相邻字母的前一位-1，后一位+31.
这里要注意的是：初始字符串要满足-1或者+31还是英文字母。
代码：#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; char s[1001]; int main() { freopen("hash.in","r",stdin); freopen("hash.out","w",stdout); int n; cin>>n; int i=-1; while(n--) { for(int k=0; k<1000; k++) { s[k]='B'; } if(i==-1) { cout<<s<<endl; i++; } else { for(int j=i; j<999; j++) { s[j]--; s[j+1]+=31; break; } cout<<s<<endl; i++; } } return 0; }
注：还有一个坑点就是没看到input file和output file的要求，wa了好几发T-T
最后还是要说，我算法方面真的鸡肋阿，要继续努力了QAQ！