2020.11.25
考场改了代码忘了往文件夹里放，，，
光荣爆零
最长上升子序列可以用树状数组解决
树状数组记得离散化
暴力可以打表找规律
组合数的结论题往卡特兰数上靠一下
2020.11.19
(u1s1)没挂分舒服极了
但是改题的时候遇到一些磕磕绊绊
总结
ZYB玩字符串
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
const int ss = 700;
const unsigned long long base = 233;
unsigned long long ha1[ss], ha2[ss], power[ss];
char ch[ss], cpy[ss], b[ss], ass[ss];
inline bool check(register char *a, register char *b){
memcpy(ass, a, sizeof a);
register int n = strlen(a + 1), len = strlen(b + 1);
memset(ha2, 0, sizeof ha2);
for(register int i = 1; i <= len; i++)
ha2[i] = ha2[i - 1] * base + b[i];
while(n){
register bool flag = 0;
for(register int l = 1; l + len - 1 <= n; l++){
flag = 0;
memset(ha1, 0, sizeof ha1);
for(register int i = 1; i <= n; i++)
ha1[i] = ha1[i - 1] * base + a[i];
register int r = l + len - 1;
register unsigned long long tmp = ha1[r] - ha1[l - 1] * power[r - l + 1];
if(tmp == ha2[len]){
flag = 1;
register int cnt = 0;
memset(ass, 0, sizeof ass);
for(register int i = 1; i <= l - 1; i++)
ass[++cnt] = a[i];
for(register int i = r + 1; i <= n; i++)
ass[++cnt] = a[i];
n -= len;
memcpy(a, ass, sizeof ass);
break;
}
}
if(!flag) break;
}
if(n) return 0;
return 1;
}
signed main(){
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
register int T = read();
power[0] = 1;
for(register int i = 1; i <= 605; i++)
power[i] = power[i - 1] * base;
while(T--){
string ans1, ans2;
scanf("%s", ch + 1);
register int n = strlen(ch + 1);
memcpy(cpy, ch, sizeof ch);
register bool flag = 0;
for(register int len = 1; len <= n; len++){
if(flag) break;
for(register int i = 1; i + len - 1 <= n; i++){
if(flag) break;
memcpy(ch, cpy, sizeof cpy);
memset(b, 0, sizeof b);
register int num = 0;
for(register int j = i; j <= i + len - 1; j++)
b[++num] = ch[j];
if(check(ch, b)){
flag = 1;
ans1 = b + 1;
break;
}
}
}
memcpy(ch, cpy, sizeof cpy);
reverse(ch + 1, ch + 1 + n);
memcpy(cpy, ch, sizeof ch);
flag = 0;
for(register int len = 1; len <= n; len++){
if(flag) break;
for(register int i = 1; i + len - 1 <= n; i++){
if(flag) break;
memcpy(ch, cpy, sizeof cpy);
memset(b, 0, sizeof b);
register int num = 0;
for(register int j = i; j <= i + len - 1; j++)
b[++num] = ch[j];
if(check(ch, b)){
flag = 1;
ans2 = b + 1;
break;
}
}
}
reverse(ans2.begin(), ans2.end());
if(ans1.size() < ans2.size()) cout << ans1 << endl;
else if(ans2.size() < ans1.size()) cout << ans2 << endl;
else cout << min(ans1, ans2) << endl;
}
}
注意事项
- (hash)的时候，想要查询某一个区间的字符或者数字(ha[r] - ha[l - 1] * power[r - l + 1])，思想类似差分
- 同样还是(hash)，预处理(power)数组的时候，记得(power[0] = 1)
- 不旦多测要清空，判断字符串是否合法如果出现了修改原数组的情况，也要清空，或者另开一个新数组
- (string)类型之间可以直接按照字典序排序，一个(string)也可以用(reverse)颠倒顺序，像这样(reverse(ans.begin(), ans.end());)
2020.10.26
众所周知
(1<<20=1048576)
没错我就是无脑开了(1e6)
2020.10.21
(150 o90)
(T2dfs)没写出来
还是要练暴力
2020.10.20
晚上把会的分拿到了
没有挂分++
多多少少比自己之前强了
嘿嘿
加油
发现自从开了这玩意就没挂分了开心
虽然还是一如既往的烂
2020.10.18
(T3)理解错题目了，狂敲(4.0k)
于是
导致没时间打别的题了，快乐爆零
前言
这是一个栈
老规矩还是会从下往上更新
感觉开这个坑有点晚了
不过好在大部分出过的错误之前在博客里面都记录过
回去翻翻还是有不错的效果的
明天就第六阶段了
希望不要再挂分了
把会的分数一定拿到
加油！