POI2010 Antisymmetry

  • 用HASH去维护一下就好了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #define ll long long
    #define ull unsigned long long
    #define ms(x,y) memset(x,y,sizeof(x))
    const int M=514514;
    struct Hash
    {
        ull h[M],base=131,P[M];
        void init(char s[M])
        {
            int n=strlen(s+1);
            P[0]=1;
            for(int i=1;i<=n;i++) P[i]=P[i-1]*base,h[i]=h[i-1]*base+s[i];
        }
        ull calc(int l,int r) {return h[r]-h[l-1]*P[r-l+1];}
    }h1,h2;
    int n;
    char s1[M],s2[M];
    int main()
    {
    	// freopen("a.in","r",stdin);
    	// freopen("a.out","w",stdout);
    	scanf("%d",&n);
        scanf("%s",s1+1);
        for(int i=1;i<=n;i++) s2[i]='0'+((s1[n-i+1]-'0')^1);
        h1.init(s1),h2.init(s2);
        ll ans=0;
        for(int i=1;i<n;i++)
        {
            int d=min(i,n-i);
            int L=1,R=d,res=0;
            while(L<=R)
            {
                int mid=(L+R)>>1;
                if(h1.calc(i-mid+1,i)==h2.calc(n-i-mid+1,n-i)) res=mid,L=mid+1;
                else R=mid-1;
            }
            ans+=res;
        }
        cout<<ans;
        return 0;
    }

B. Bovine Genomics

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#define ull unsigned long long
using namespace std;
const int MAXN = 504;
const int bass = 233;
int n,m;
ull p[MAXN],h[3][MAXN][MAXN];
char s[3][MAXN][MAXN];
void init(){
	p[0] = 1;
	for(int i = 1; i < MAXN; i++){
		p[i] = p[i - 1] * bass;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			h[1][i][j] = h[1][i][j - 1] * bass + (ull)s[1][i][j];
			h[2][i][j] = h[2][i][j - 1] * bass + (ull)s[2][i][j];
		}
	}
}
ull get_hash(int id,int pos,int l,int r){
	return h[id][pos][r] - h[id][pos][l - 1] * p[r - l + 1];
}
bool check(int mid){
	set<ull> st1,st2;
	int flag = 0;
	for(int i = 1; i + mid - 1 <= m; i++){
		st1.clear(),st2.clear();
		for(int j = 1; j <= n; j++){
			ull hsh1 = get_hash(1,j,i,i + mid - 1);
			ull hsh2 = get_hash(2,j,i,i + mid - 1);
			st1.insert(hsh1);
			st2.insert(hsh2);
		}
		int f2 = 1;
		for(ull u : st1){
			if(st2.count(u)){
				f2 = 0;
				break;
			}
		}
		flag |= f2;
	}
	return flag;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> (s[1][i] + 1);
	}
	for(int i = 1; i <= n; i++){
		cin >> (s[2][i] + 1);
	}
	init();
	int l = 0,r = m;
	int ans = 1e9;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			r = mid - 1;
			ans = mid;
		}
		else{
			l = mid + 1;
		}
	}
	cout << ans << endl;
}

C. friends

  • HASH
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    const int maxn = 2e6+26;
    const ull base = 2333;
    ull Hash[maxn],Pow[maxn];
    char s[maxn];
    map<ull,int> vis;
    ull cal(int l,int r) {
    	if(r < l) return 0;
    	return Hash[r] - Hash[l-1]*Pow[r-l+1];
    }
    bool s2;
    int main() {
    	int len;
    	cin >> len;
    	scanf("%s",s+1);
    	if(len%2==0||len==1) {
    		puts("NOT POSSIBLE");
    		return 0;
    	}
    	int k = (len+1)>>1;
    	Pow[0] = 1;
    	for(int i = 1; i <= len; ++i) {
    		Hash[i] = Hash[i-1]*base+(ull)s[i];
    		Pow[i] = Pow[i-1]*base;
    	}
    	int pos = -1;
    	for(int i = 1; i <= len; ++i) {
    		ull val1,val2;
    		if(i < k) {
    			val2 = cal(k+1,len);
    			val1 = cal(i+1,k)+cal(1,i-1)*Pow[k-i];
    		} else if(i == k) {
    			val1 = cal(1,k-1);
    			val2 = cal(k+1,len);
    		} else {
    			val1 = cal(1,k-1);
    			val2 = cal(i+1,len)+cal(k,i-1)*Pow[len-i];
    		}
    		if(val1 == val2) {
    			if(pos != -1 && !vis[val1]) {
    				puts("NOT UNIQUE");
    				return 0;
    			} else pos = i,vis[val1] = 1;
    		}
    	}
    	if(pos != -1) {
    		for(int i = 1; i<=len && k>1; ++i) {
    			if(i == pos) continue;
    			putchar(s[i]);
    			k--;
    		}
    	} else puts("NOT POSSIBLE");
    	return 0;
    }

D. 似乎在梦中见过的样子

  • KMP 的 高级应用
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    int p[21000],bak[21000];
    char st[21000];
    int main()
    {
        scanf("%s",st+1);int n=strlen(st+1);
        int k;
        scanf("%d",&k);
        int ans=0;
        bak[0]=999999999;
        for(int t=1;t<=n;t++)
        {
            p[t]=t-1;bak[t]=999999999;
            for(int i=t+1;i<=n;i++)
            {
                int j=p[i-1];
                while(st[j+1]!=st[i]&&j!=(t-1)) j=p[j];
                if(st[j+1]==st[i]) j++;
                p[i]=j;
                bak[i]=bak[j];
                if(p[i]-t+1>=k) bak[i]=min(bak[i],p[i]-t+1);
                if(bak[i]>=k&&2*bak[i]<=i-t) ans++;
            }
        }
        printf("%d\n",ans);
        return 0;
    }

E. 关键位置操作

  1. 直接用线段树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include<bits/stdc++.h>
    #define ls (root<<1) 
    #define rs (root<<1|1)
    #define mid (l+r>>1)
    #define min(a,b) (a<b?a:b)
    using namespace std;
    const int Maxn=2e6+5;
    inline int R()
    {
    	char c;int sign=1,res=0;
    	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res+=c-'0';
    	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    	return res*sign;	
    }
    #define int long long 
    int a[Maxn],n,m,sum[Maxn*4],N=1,NN=0,ADD[Maxn*4],size[Maxn*4];
    void add(int root,int val)
    {
    	sum[root]+=size[root]*val;
    	ADD[root]+=val;
    }
    void pushdown(int root)
    {
    	if(ADD[root])
    	{
    		add(ls,ADD[root]);
    		add(rs,ADD[root]);
    		ADD[root]=0;
    	}
    }
    void build(int root,int deep,int sur)
    {
    	if(deep==NN) 
    	{
    		sum[root]=a[sur];
    		size[root]=(sur<=n);
    		return;
    	}
    	build(ls,deep+1,sur);
    	build(rs,deep+1,sur+(1<<deep));
    	sum[root]=sum[ls]+sum[rs];
    	size[root]=size[ls]+size[rs];
    }
    void modify(int root,int deep,int arr,int sur,int value)
    {
    	if(deep==arr&&sur!=0) return;
    	pushdown(root);
    	if(deep==arr) return add(root,value);
    	if(sur&1) modify(rs,deep+1,arr,sur>>1,value);
    	else  modify(ls,deep+1,arr,sur>>1,value);
    	sum[root]=sum[ls]+sum[rs];
    }
    int query(int root,int deep,int arr,int sur)
    {
    	if(deep==arr&&sur!=0) return 0;
    	pushdown(root);
    	if(deep==arr) return sum[root];
    	if(sur&1) return query(rs,deep+1,arr,sur>>1);
    	else return query(ls,deep+1,arr,sur>>1);
    }
    signed main()
    {
    	n=R();m=R();
    	while(N<=n) N<<=1,NN++; 
    	for(int i=1;i<=n;i++) a[i]=R();
    	build(1,0,1);
    	int op,p,k,pre=0;
    	while(m--)
    	{
    		op=R();p=R();k=R();
    		if(op==1)//修改 
    		{
    			int v=R();
    			if(k!=0)modify(1,0,min(NN,p),k-1,v);
    			else modify(1,0,min(NN,p),(1<<(min(NN,p)))-1,v);
    		}
    		else if(k!=0)printf("%lld\n",pre=query(1,0,min(NN,p),k-1));
    		else printf("%lld\n",pre=query(1,0,min(NN,p),(1<<(min(NN,p)))-1));
    	}
    }
  2. 字典树逆推
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #define nn 1000010
    #define ll long long
    using namespace std;
    int read() {
    	int re = 0;
    	bool sig = false;
    	char c = getchar();
    	while(c < '0' || c > '9') {
    		if(c == '-')
    			sig = true;
    		c = getchar(); 
    	}
    	while(c >= '0' && c <= '9')
    		re = (re << 1) + (re << 3) + c - '0',
    		c = getchar();
    	return sig ? -re : re;
    }
    int trie[nn][3] , num[nn];
    ll a[nn] , tag[nn] , dat[nn];
    int n , m;
    void build() {
    	int top = 1;
    	for(int i = 1 ; i <= n ; i++) {
    		int tmp = i;
    		int p = 1;
    		while(tmp != 0) {
    			if(trie[p][tmp & 1] == 0)
    				trie[p][tmp & 1] = ++top;
    			p = trie[p][tmp & 1];
    			tmp >>= 1;
    		}
    		a[p] = dat[p] = read();
    		num[p]++;
    	}
    	
    }
    void dfs(int p) {
    	if(p == 0)return;
    	dfs(trie[p][0]);
    	dfs(trie[p][1]);
    	dat[p] += dat[trie[p][0]] + dat[trie[p][1]];
    	num[p] += num[trie[p][0]] + num[trie[p][1]];
    	tag[p] = 0;
    }
    inline void spread(int p) {//懒标记下传
    	if(p == 0) {
    		tag[p] = 0;
    		return;
    	}
    	if(tag[p] != 0) {
    		tag[trie[p][0]] += tag[p];
    		dat[trie[p][0]] += num[trie[p][0]] * tag[p];
    		if(a[trie[p][0]] != -1)
    			a[trie[p][0]] += tag[p];
    		
    		tag[trie[p][1]] += tag[p];
    		dat[trie[p][1]] += num[trie[p][1]] * tag[p];
    		if(a[trie[p][1]] != -1)
    			a[trie[p][1]] += tag[p];
    	}
    	tag[p] = 0;
    }
    void change(int x , int y , ll v , int p) {//修改,使用递归的方式,有助于更新dat值
    	if(x == 0) {
    		if(a[p] != -1)
    			a[p] += v;
    		dat[p] += v * num[p];
    		tag[p] += v;
    		return;
    	}
    	
    	spread(p);
    	change(x - 1 , y >> 1 , v , trie[p][y & 1]);
    	if(y == 0 && a[p] != -1) {
    		a[p] += v;
    	}
    	dat[p] = dat[trie[p][0]] + dat[trie[p][1]];
    	if(a[p] != -1)
    		dat[p] += a[p];
    }
    int query() {//查询
    	int x = read() , y = read();
    	ll res = 0;
    	int p = 1;
    	y %= (1 << x);
    	for(int i = 1 ; i <= x ; i++) {
    		spread(p);
    		if(y == 0)
    			res += dat[p] - dat[trie[p][0]] - dat[trie[p][1]];
    		p = trie[p][y & 1];
    		y >>= 1;
    	}
    	res += dat[p];
    	printf("%lld\n" , res);
    	return res;
    }
    int main() {
    	memset(a , -1 , sizeof(a));//值为-1代表该结点没有数字
    	n = read();	m = read();
    	build();
    	dfs(1);
    	ll lastans = 0;
    	for(int i = 1 ; i <= m ; i++) {
    		int op;
    		op = read();
    		//op = (op + lastans) % 2 + 1;
    		if(op == 1) {
    			int x , y , v;
    			x = read();	y = read();	v = read();
    			change(x , y % (1 << x) , (ll)v , 1);
    		}
    		else
    			lastans = query();
    			
    	}
    	return 0;
    }