Shen Huang's Blog
0%

Posted on Edited on

字符串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
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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define MID(x,y) ((x+y)>>1)
#define maxn 2205
#define print() cout<<"------------"<<endl
using namespace std;
char s[20005];
unsigned int hash[maxn],ans[maxn][maxn],h[maxn][maxn];
int seed=13;
pair<int,int> pa[maxn];
int q,n,m;

int binsearch(int val,int l,int r){
	while (l <= r){
		int mid = MID(l,r);
		if(hash[mid] == val) return mid;
		else if(hash[mid] < val) return binsearch(val,mid+1,r);
		else return binsearch(val,l,mid-1);
	}
}

int main (){
	int t,l,r;
	cin>>t;

	while (t--){

		cin>>s;
		n = strlen(s);
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j <= n; ++j)
				ans[i][j] = 0;

		for (int i = 0; i < n; ++i){
			int val = 0;
			for (int j = i; j < n; ++j){
				val = val * seed + s[j];
				h[i][j] = (val & 0x7FFFFFFF);
			}
		}

		for (int len = 1; len <= n; len++){
			m = 0;
			for(int i = 0; i < n-len+1; ++i){
				hash[m++] = h[i][i+len-1];
			}
			sort(hash,hash+m);
			int tmp = 0;
			for (int i = 1; i < m; ++i)
				if(hash[tmp] != hash[i])
					hash[++tmp] = hash[i];
			m = tmp +1;
			for (int i = 0;i < m; ++i) 
				pa[i] = make_pair(-1,-1);
			//cout << "len" << len << endl;
			for (int i = 0; i < n-len+1; ++i)
			{
				//cout << i << endl;
				int val = h[i][i+len-1];
				int pos = binsearch(val,0,m-1);
				r = i + len - 1;
				int le1 = -1,le2 = i + 1;
				//if(pa[pos].first != -1) le1 = pa[pos].first;
				le1 = pa[pos].first+1;
				ans[le1][r] ++;
				ans[le2][r] --;
				pa[pos] = make_pair(i,i+len-1);	
			}
			//cout << len << endl;
		}

		for (int i = 0; i < n; ++i)
			for (int j = 1; j < n; ++j)
				ans[i][j] += ans[i][j-1];

		for (int j = 0; j < n; ++j)
			for (int i = 1; i < n; ++i)
				ans[i][j] += ans[i-1][j];	
		cin>>q;
		for (int i = 0; i < q; ++i)
		{
			scanf("%d%d", &l, &r);
			//cin>>l>>r;
			l--;r--;
			//if(l == r) printf("1n");
			//else 
			printf("%dn", ans[l][r]);	
		}
	}
	return 0;
}

Posted on Edited on

用set进行,加上一个小优化，就可以算最近点对，没有特别的数据

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
#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define maxn 500005
#define ll __int64
using namespace std;

ll x[maxn],y[maxn];
struct node
{
	ll x,y;
	bool operator < (const node &u) const{
		if(x == u.x) return y < u.y;
		return x < u.x;
	}
};
int main()
{
	int t;
	ll n,Ax,Ay,Bx,By,Cx,Cy;
	scanf("%d", &t);
	while (t--){
		set<node> st;
		st.clear();
		cin>>n>>Ax>>Bx>>Cx>>Ay>>By>>Cy;
		//cout<<n<<&#39; &#39;<<Ax<<&#39; &#39;<<Cy<<endl;
		//scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &n, &Ax, &Bx, &Cx, &Ay, &By, &Cy);
		x[0] = 0; y[0] = 0;
		for (int i = 1; i <= n; ++i){
			x[i] = (x[i-1]*Ax + Bx) % Cx;
			y[i] = (y[i-1]*Ay + By) % Cy;
		}
		ll sum = 0;
		node tmp;
		tmp.x = 0; tmp.y =0;
		//st.insert(tmp);
		tmp.x = x[1]; tmp.y= y[1];
		st.insert(tmp);
		ll ans = 1e17;
		//cout << ans << endl;
		for (ll i = 2; i <= n; ++i)
		{
			tmp.x = x[i]; tmp.y = y[i];
			set<node>::iterator it,ii;
			it = st.lower_bound(tmp);	

			for (ii = it; ii != st.end(); ++ii)
			{
				if((ii->x-tmp.x) * (ii->x-tmp.x) >= ans) break;
				ll dis = (ii->x-tmp.x) * (ii->x-tmp.x) + (ii->y-tmp.y) * (ii->y-tmp.y) ;
				ans = min(ans,dis);
			}	
			ii = it;
			while (ii != st.begin())
			{
				ii --;
				if((ii->x-tmp.x) * (ii->x-tmp.x) >= ans) break;
				ll dis = (ii->x-tmp.x) * (ii->x-tmp.x) + (ii->y-tmp.y) * (ii->y-tmp.y) ;
				ans = min(ans,dis);
			}
			sum += ans;
			st.insert(tmp);
		}
		//printf("%I64dn",sum);	
		cout << sum << endl;
	}
	return 0;
}

Posted on Edited on 
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
/* HDU 4630 2013多校第三场J题 离线 数状数组
 * 算区间最大值得时候因为是从后往前所以算从头到此处的最大值树状数组可以处理
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 500005

using namespace std;
int num[maxn],ans[maxn],n;
int big[maxn],pre[maxn];
struct node{
	int l,r,id;
	bool operator < (const node &u) const{
		return l > u.l;
	}
}p[maxn];
inline int lowbit(int x) {return x&(-x);} 
inline void update(int x,int val){
	while(x<=n){
		big[x] = max(big[x],val);
		x += lowbit(x);
	}
}
inline int query(int x){
	int ret = 0;
	while(x){
		ret = max(ret,big[x]);
		x -= lowbit(x);
	}
	return ret;
}
int main(){
	int t,q;
	cin >> t;
	while (t--){
		cin >> n;
		for (int i = 1; i <= n; ++i){
			scanf("%d", &num[i]);
		} 
		scanf("%d", &q);
		for (int i = 0; i < q; ++i){
			scanf("%d%d", &p[i].l, &p[i].r);
			p[i].id = i + 1;
		}
		sort(p,p+q);
		int k = 0;
		memset(big,0,sizeof(big));memset(pre,0,sizeof(pre));
		for (int i = n; i >= 1; --i){
			for (int j = 1; j*j <= num[i]; ++j){
				if (num[i] % j == 0){
					if (pre[j]) update(pre[j],j);
					pre[j] = i;
					if (j*j == num[i]) continue;
					if (pre[num[i]/j]) update(pre[num[i]/j],num[i]/j);
					pre[num[i]/j] = i;
				}
			}
			for(;p[k].l == i;k++) ans[p[k].id] = query(p[k].r);
		}
		for (int i = 1; i <= q; ++i){
			printf("%dn", ans[i]);
		}
	}

	return 0;
}

Posted on Edited on 
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
/* HDU 4627 2013多校第三场G
 * 简单题 分成奇数和能被四整除和的偶数
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
int main(){
	int t;
	scanf("%d", &t);
	long long n,ans;
	while (t--){
		scanf("%I64d", &n);
		if (n == 2) ans = 1;
		else if (n & 1) ans = n/2*(n/2+1);
		else if((n>>1) & 1) ans = (n/2+2)*(n/2-2);
		else ans = (n/2-1)*(n/2+1);
		cout << ans << endl;
	}
	return 0;
}

Posted on Edited on

多校H，状态压缩Dp，先预处理出所有的回文串，然后枚举

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
/*
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
int dp[1<<17];
char str[30],ss[30];
int n,m,len;
void init()
{
	memset(dp,0x3f,sizeof(dp));
	for (int i = 1; i < (1<<len); i++){
		int num = 0, flag = 1;
		for (int j = 0; j < len; j++){
			if (i & (1<<j)) ss[num++] = str[j];
		} 
		ss[num] = 0;
		for (int j = 0; j < num; j++){
			if (ss[j] != ss[num-j-1]) flag = 0;
		}
		if(flag) dp[i] = 1;
	}
}
int main(){
	int t;
	cin >> t;
	while (t--){
		scanf("%s",str);
		len = strlen(str);
		init();
		dp[0] = 0;
		for (int i = 1; i < (1<<len); i++){
			for (int j = i; j > 0; j = (j-1) & i)
				dp[i] = min(dp[i],dp[i^j]+dp[j]);
		}
		cout << dp[(1<<len)-1] << endl;
    }
    return 0;
    
}

Posted on Edited on

主要是先把方差公式划简一下，然后进行分割，在哪一块割多少刀。

然后一开始出现用方格作为单位的时候出现不能计算x1==x2之类的情况，解决的办法就是做线段的分割，把坐标作为单位

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
/* POJ 1191 黑书p116 例题 主要是判断如何切 dp数组的维数开得很多
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 22
#define INF 1e8
int map[maxn][maxn];
int s[9][9][9][9],dp[16][9][9][9][9];
using namespace std;

int solve(int k,int x1,int y1,int x2,int y2){
	int Min = INF;
	for (int a = x1; a < x2; ++a)
		Min = min(Min,min(dp[k-1][x1][y1][a][y2]+s[a][y1][x2][y2],
					dp[k-1][a][y1][x2][y2]+s[x1][y1][a][y2]));
	for (int a = y1; a < y2; ++a)
		Min = min(Min,min(dp[k-1][x1][y1][x2][a]+s[x1][a][x2][y2],
					dp[k-1][x1][a][x2][y2]+s[x1][y1][x2][a]));
	return Min;

}

int main(){
	int n;
	while(~scanf("%d", &n)){
	memset(map,0,sizeof(map));
	for (int i = 1; i <= 8; ++i)
		for (int j = 1; j <= 8; ++j)
		{
			scanf("%d", &map[i][j]);
			map[i][j] += map[i-1][j] + map[i][j-1] -map[i-1][j-1];
			//cout<<map[i][j]<<endl;
		}
	for (int x1 = 0; x1 < 8; ++x1)
		for (int y1 = 0; y1 < 8; ++y1)
			for (int x2 = x1 + 1; x2 <= 8; ++x2)
				for (int y2 = y1 + 1; y2 <= 8; ++y2){
					s[x1][y1][x2][y2] = map[x2][y2] + 
					 map[x1][y1] - map[x1][y2] - map[x2][y1];
					dp[1][x1][y1][x2][y2] = s[x1][y1][x2][y2] * s[x1][y1][x2][y2];
					s[x1][y1][x2][y2] = dp[1][x1][y1][x2][y2];
				}
	for (int k = 2; k <=n; ++k)
	 for (int x1 = 0; x1 < 8; ++x1)
	  for (int y1 = 0; y1 < 8; ++y1)
	   for (int x2 = x1 + 1; x2 <= 8; ++x2)
	    for (int y2 = y1 + 1; y2 <= 8; ++y2){
			dp[k][x1][y1][x2][y2] = solve(k,x1,y1,x2,y2);
			//cout<<dp[k][x1][y1][x2][y2]<<endl;
		}
	double ans = 1.0 * dp[n][0][0][8][8] / n - 1.0 * map[8][8] * map[8][8] / n / n;
	printf("%.3fn", sqrt(ans));
	}
	return 0;
}

Posted on Edited on

第一道二分图匹配，求的是最小点覆盖=最大匹配数。用匈牙利跑一遍

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
/*POJ 3041 二分图匹配第一题
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 555
int n, k, a, b;
bool map[maxn][maxn],v[maxn];
int link[maxn];

bool dfs(int x)
{
	int i;
	for(i = 1; i <= n; i++){
		if(!v[i] && map[x][i]){
			v[i] = 1;
			if(link[i]==0 || dfs(link[i]))
			{
				link[i] = x;
				return true;	
			}
		}
	}
	return false;
}

int main()
{
	memset(link,0,sizeof(link));
	memset(map,0,sizeof(map));
	scanf("%d%d", &n, &k);
	for (int i = 0; i < k; ++i)
	{
		scanf("%d%d", &a, &b);
		map[a][b]=1;
	}
	int ans=0;
	for (int i = 1; i <= n; ++i)
	{
		memset(v,0,sizeof(v));
		if(dfs(i)){
			ans++;
		}
	}
	printf("%dn", ans);
	return 0;
}
就行

Posted on Edited on

算是一个Trie的模板，挺好的，记录出现次数

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
/* HDU 3724 Encoded Barcodes 字典树 
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
const int Max_Node = 2000*30+10;
const int Child_Num = 26; 
struct Trie{
	int chd[Max_Node][Child_Num];//每个节点的儿子，状态转移
	int val[Max_Node];//记录关键数据
	int ID[128];//字母对应的ID
	int sz;//已使用节点个数
	void Initialize(){//初始化，计算字母对应的儿子ID，如&lsquo;a&rsquo;->0
		for(int i = 0; i < Child_Num; i ++){
			ID[i+'a']=i;
		}
	}
	void Reset(){//重新建树时需要先Rest
		memset(chd[0],0,sizeof(chd[0]));
		memset(val,0,sizeof(val));
		sz=1;
	}
	void Insert(char *s,int key) {//将权值为key的字符串插入到Trie
		int p = 0;
		for( ; *s; s ++){
			int c = ID[*s];
			if(!chd[p][c]){
				memset(chd[sz],0,sizeof(chd[sz]));
				chd[p][c] = sz ++;
			}
			p = chd[p][c];
			val[p] ++;
		}
	}
	int Find(char *s){
		int p = 0;
		for( ; *s;s ++)
		{
			int c = ID[*s];
			if(!chd[p][c]) return 0;
			else p = chd[p][c];
		}
		return val[p];
	}
}T;
int main(){
	int n,m,k,ret;
	char s[1000],find[1000];
	while(cin>>n>>m)
	{
		ret=0;
		T.Reset();
		T.Initialize();	
		for	(int i=0;i<n;i++)
		{
			scanf("%s",s);
			T.Insert(s,0);	
		}
		double val[8];
		for(int i=0;i<m;i++)
		{
			scanf("%d",&k);
			for (int j = 0; j < k; ++j)
			{
				int ans=0;int i2=1<<6;
				scanf("%lf",&val[0]);
				for(int l=1;l<8;l++)
				{
					scanf("%lf",&val[l]);
					double tmp=val[l]/val[0];
					if(tmp<=2.4&&tmp>=1.6){
						ans+=i2;
					}
					i2/=2;
				}
				find[j]=ans;
			}
			find[k]=0;
			ret+=T.Find(find);
		}

		printf("%dn",ret);
	}
}

Posted on Edited on

主要是看看这个点有没有被覆盖过了，如果有，看能不能找到增广路。

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
/* 2010 天津 赛区 J题 匹配的题（新生赛2的J当时是自己把匹配个YY出来了）
 * 其实就是一个DFS嘛
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
#define maxn 100
struct node{
	int l,r;
}p[maxn];
int ma[100005];
int vis[100005];
int ans[maxn],cnt=0;
bool dfs(int x)
{
	for(int i=p[x].l;i<=p[x].r;i++)
	{
		if(!vis[i]){
			vis[i]=1;
			if(ma[i]==-1||dfs(ma[i])){
				ma[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		cnt=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%d%d",&p[i].l,&p[i].r);
		memset(ma,-1,sizeof(ma));
		for(int i=n-1;i>=0;i--)
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i)){
				ans[cnt++]=i;
			}
		}
		printf("%dn",cnt);
		if(cnt==0) continue;
		for(int i=cnt-1;i>0;i--)
		{
			printf("%d ",ans[i]+1);
		}
		printf("%dn",ans[0]+1);
	}
	return 0;
}

Posted on Edited on

这题也是比赛的时候过得，用java的大数写的，推出之间的递推的一个关系式，然后``就是java了

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
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner (new BufferedInputStream(System.in));
		BigInteger ans,tmp;
		BigInteger mod = BigInteger.valueOf(10).pow(100);
		int N;
		while(in.hasNext())
		{
			N = in.nextInt();
			tmp = BigInteger.valueOf(1);
			ans = BigInteger.valueOf(1);
			for(int i = 1; i<=N/2;i++)
			{
				BigInteger s=BigInteger.valueOf(N-2*i+1);
				BigInteger t=BigInteger.valueOf(i);
				tmp=tmp.multiply(s).multiply(s.add(BigInteger.valueOf(1)))
				.divide(t).divide(t.add(BigInteger.valueOf(1)));
				ans=ans.add(tmp);				
			} 			
			System.out.println(ans.mod(mod));
		} 	
	}

}