首页 > 代码库 > HDU 4909 String 统计+状压
HDU 4909 String 统计+状压
因为连续异或满足区间减法性质,所以可以状压之后用异或来判断是否为符合条件的单词并且存储次数
一开始用map,一直超时。虽然直接用开1<<26的数组内存存的下,但是memset的时间肯定会超,但是只要在每次循环之后把加过的值减掉就可以绕过memset了。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 30000 + 5;char buf[maxn];int len,spos,val[maxn];int mp[1 << 26];bool vis[27];LL solve(int l,int r) { if(l > r) return 0; LL ret = 0; int nowval = 0; mp[0]++; for(int i = l;i <= r;i++) if(val[i] >= 0) { nowval ^= (1 << val[i]); ret += mp[nowval]; mp[nowval]++; } else ret += mp[nowval],mp[nowval]++; nowval = 0; mp[0] = 0; for(int i = l;i <= r;i++) if(val[i] >= 0) { nowval ^= (1 << val[i]); mp[nowval] = 0; } return ret;}int main() { int T; scanf("%d",&T); while(T--) { memset(vis,0,sizeof(vis)); scanf("%s",buf + 1); len = strlen(buf + 1); spos = -1; for(int i = 1;i <= len;i++) { if(buf[i] == ‘?‘) spos = i; //转化成数字 val[i] = buf[i] - ‘a‘; if(buf[i] != ‘?‘) vis[val[i]] = true; } if(spos == -1) cout << solve(1,len) << endl; else { LL ans = solve(1,len); LL rest = solve(1,spos - 1) + solve(spos + 1,len); int cnt = 0; for(int i = 0;i < 26;i++) if(vis[i]) { val[spos] = i; ans += solve(1,len); cnt++; } cout << ans - cnt * rest << endl; } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。