Shen Huang's Blog
0%

Posted on Edited on

各种wa各种TLE，觉得没有错。

之后发现错了好几处，首先赋值的时候值太大了0x7fffffff可能过INT？然后开小点。

第二个因为10^6的平方用的int，直接超，所以肯定错

不过最后一个没发现导致一直TLE，这个很不爽啊，最后去了for循环里面的判断条件，判断dp这个是不是可以达到的条件，然后就好了，没想到一个if也这么慢啊？其实发现不需要这个条件，就算不可答的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
/*
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 5005
using namespace std;
int X[maxn],Y[maxn];
int dp[2000020];
int main(){
	int t,n;
	long long d;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d%d", &X[i], &Y[i]);
		for (int i = 0; i < 2*X[n-1] + 1; ++i) 
			dp[i] = 0x7fffff;
		dp[X[0]] = 0;
		for (int i = 1; i < n; ++i){
			for (int j = X[i] - 1; j >= X[0]; --j){
					d = (long long)(X[i]-j)*(X[i]-j)+(long long)(Y[0]-Y[i])*(Y[0]-Y[i]);
					if (d > (long long)Y[i]*Y[i]) break;
					dp[X[i]+(X[i]-j)] = min(dp[X[i]+(X[i]-j)] ,dp[j] + 1);
			}
		}
		int ans = maxn * 2;
		for (int j = X[n-1]; j <= 2*X[n-1]; ++j)
			if (dp[j] < ans) ans = dp[j];
		printf("%dn", ans != maxn * 2 ? ans : -1);
	}
	return 0;
}

Posted on Edited on

注意ans不是dp{N},想想就明白，dp[i]表示的是取到第i个的结果，需要的是第i个能够取否则会出现问题。

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
/* 宾馆有个可以伸缩的门，每秒钟可以伸长1个单位，或者缩小1个单位，
 * 或者原地不动。有N个强盗，每个强盗会在t的时间内到达并按，
 * 如果此时门的开方度和他的身材s正好相等，这个强盗就会进来，
 * 然后你就能得到p的加分。
 *
 * 初始状态门是关闭的，让你求出在t时刻得到的最大得分。
 *
 * 分析：按时间从小到大排序，t时间内最大的得分由t之前的时刻决定，满足无后效性，每一个时刻都能得到最优解，满足最有子结构，所以DP。
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 105
#define print() cout<<"-----"<<endl
using namespace std;

struct node{
	int t,p,s;
	bool operator < (const node &u) const{
		return t < u.t;
	}
}p[maxn];
int dp[maxn];
int main(){
	int N, K, T;
	scanf("%d%d%d", &N, &K, &T);
	for(int i = 1;i <= N; ++i)
		scanf("%d", &p[i].t);
	for(int i = 1;i <= N; ++i)
		scanf("%d", &p[i].p);
	for(int i = 1;i <= N; ++i)
		scanf("%d", &p[i].s);
	sort(p+1,p+N+1);
	p[0].s = 0;p[0].t = 0;p[0].p = 0;

	memset(dp,0,sizeof(dp));
	int ans = 0;
	for (int i = 1; i <= N; ++i){
		for (int j = i-1; j >= 0; --j){
			if((dp[j] != 0 || j == 0) && iabs(p[j].s - p[i].s) <= p[i].t - p[j].t){
				dp[i] = max(dp[i],dp[j] + p[i].p);
			}
		}
		ans = max(dp[i],ans);
	}
	printf("%dn", dp[N]);
	return 0;
}

Posted on Edited on

题意：

给你一个有向图，问你最多能添加多少条边使得这个图依然不是强联通的。

做法：

1，求出图中的所有强连通分量

2，把上述的强连通分量缩成一个点。

3，问题现在变成问一个完全图，最少需要去除多少条边使得这个图不强联通，

那么肯定是去除所有强联通分量中含有点数最少的点的所有进边。

复制了一个模板，然后搞定了

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100050//点数
#define M 100050//边数

struct Edge {
    int v;
    int next;
};
Edge edge[M]; //边的集合
int node[N]; //顶点集合
int instack[N]; //标记是否在stack中
int stack[N];
int Belong[N]; //各顶点属于哪个强连通分量
int DFN[N]; //节点u搜索的序号(时间戳)
int LOW[N]; //u或u的子树能够追溯到的最早的栈中节点的序号(时间戳)
int n, m; //n：点的个数；m：边的条数
int cnt_edge; //边的计数器
int Index; //序号(时间戳)
int top;
int Bcnt; //有多少个强连通分量

void add_edge(int u, int v)//邻接表存储
{
    edge[cnt_edge].next = node[u];
    edge[cnt_edge].v = v;
    node[u] = cnt_edge++;
}

void tarjan(int u) {
    int i, j;
    int v;
    DFN[u] = LOW[u] = ++Index;
    instack[u] = true;
    stack[++top] = u;
    for (i = node[u]; i != -1; i = edge[i].next) {
        v = edge[i].v;
        if (!DFN[v])//如果点v没被访问
        {
            tarjan(v);
            if (LOW[v] < LOW[u])
                LOW[u] = LOW[v];
        } else//如果点v已经被访问过
            if (instack[v] && DFN[v] < LOW[u])
            LOW[u] = DFN[v];
    }
    if (DFN[u] == LOW[u]) {
        Bcnt++;
        do {
            j = stack[top--];
            instack[j] = false;
            Belong[j] = Bcnt;
        } while (j != u);
    }
}

void solve() {
    int i;
    top = Bcnt = Index = 0;
    memset(DFN, 0, sizeof (DFN));
    memset(LOW, 0, sizeof (LOW));
    for (i = 1; i <= n; i++)
        if (!DFN[i])
            tarjan(i);
}
int ru[N], chu[N],geshu[N];
int main() {
    int i, j, k, S, K;
    scanf("%d", &S);
    for (K = 1; K <= S; K++) {
        cnt_edge = 0;
        memset(node, -1, sizeof (node)); //记得清空
        scanf("%d%d", &n, &m);
        for (i = 1; i <= m; i++) {
            scanf("%d%d", &j, &k);
            add_edge(j, k);
        }
        solve();
        memset(ru,0,sizeof(ru));
        memset(chu,0,sizeof(chu));
        memset(geshu,0,sizeof(geshu));
        int max=0;
        for (i=1;i<=n;i++){
            geshu[Belong[i]]++;
            if(max<Belong[i])
                max=Belong[i];
            for(j=node[i];j!=-1;j=edge[j].next){
                if(Belong[i]!=Belong[edge[j].v]){
                    chu[Belong[i]]++;
                    ru[Belong[edge[j].v]]++;
                }
            }
        }
        if(max==1){
            printf("Case %d: -1n",K);
            continue;
        }
        int min=999999999;
        for(i=1;i<=max;i++){
            if(chu[i]==0||ru[i]==0){
                if(geshu[i]<min)
                    min=geshu[i];
            }
        }
        int sum;
        sum=n*(n-1);
        sum=sum-m-min*(n-min);
        printf("Case %d: %dn",K,sum);
    //    for (i = 1; i <= n; i++)
    //        printf("%d ", Belong[i]);
    }

}

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
/* 区间dp
 * dp[i][j] 表示字符串的i~j段共有多少个不同子串
 * 那么dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
 * 如果str[i] == str[j], 那么还要加上
 * dp[i][j] = dp[i][j]+dp[i+1][j-1]+1;
 * 要记得加mod否则会WA只是这是为什么呢？因为会出现负数
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define mod 10007
#define maxn 1010
char str[maxn];
int dp[maxn][maxn];
using namespace std;
int main(){
	int t,cas = 0;
	scanf("%d", &t);
	while (cas++ < t){
		scanf("%s", str);
		int len = strlen(str);
		for (int i = 0; i < len; ++i) dp[i][i] = 1;
		for (int i = 0; i < len -1; ++i) 
			if (str[i] == str[i+1]) dp[i][i+1] = 3;
			else dp[i][i+1] = 2;

		for (int s = 2; s < len; ++s)
			for (int i = 0; i < len - s; i++){
				int r = i + s;
				dp[i][r] = (mod + dp[i][r-1] + dp[i+1][r] - dp[i+1][r-1]) % mod;
				if (str[i] == str[r]) 
					dp[i][r] = (mod + dp[i][r] + dp[i+1][r-1] + 1 ) % mod;
			}
		printf("Case %d: %dn", cas, dp[0][len-1]);
	}
	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
74
75
76
77
78
79
80
81
82
83
/* 离线数状数组,先预先处理出1-i的形成的连续段个数，然后将查询区域排序
 * 每次删去不许要的前面部分，因为前面删去的那个数，可能+1或者-1的数在后面
 * 导致对后面有影响把这个影响消去
 *
 * */
#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 100005
using namespace std;
int n,m;
int num[maxn],c[maxn],pos[maxn],ans[maxn];
bool isgroup[maxn];
struct node {
	int l,r,id;

}p[maxn];
bool cmp(node a,node b){
	if(a.l == b.l) return a.r < b.r;
	else return a.l < b.l;
}
inline int lowbit(int x){return x&(-x);}
inline int query(int x){
	int ret = 0;
	while (x){
		ret += c[x];
		x -= lowbit(x);
	}
	return ret;
}
inline void update(int x,int val){
	while (x <= n){
		c[x] += val;
		x += lowbit(x);
	}
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i){
			scanf("%d", &num[i]);
			pos[num[i]] = i;
		}
		for (int i = 0; i < m; ++i){
			scanf("%d%d", &p[i].l, &p[i].r);
			p[i].id = i;
		}
		sort(p,p+m,cmp);
		memset(c,0,sizeof(c));memset(isgroup,0,sizeof(isgroup));
		for (int i = 1; i <= n; ++i){
			int cnt = 0;
			if (isgroup[num[i]-1]) cnt++;
			if (isgroup[num[i]+1]) cnt++;
			if (cnt == 0) update(pos[num[i]],1);
			else if (cnt == 2) update(pos[num[i]],-1);
			isgroup[num[i]] = 1;
		}
		int cnt = 1;
		for (int i = 0; i < m; ++i){
			while (cnt < p[i].l) {
				if (pos[num[cnt]-1] > cnt && num[cnt] > 1)
					update(pos[num[cnt]-1],1);
				if (pos[num[cnt]+1] > cnt && num[cnt] < n)
					update(pos[num[cnt]+1],1);
				cnt ++;
			}
			ans[p[i].id] = query(p[i].r) - query(p[i].l-1);
		}
		for (int i = 0; i < m; ++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
28
/* 找规律发现只跟右下角的那个硬币有关
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
int main(){
	int t,n,m,a;
	scanf("%d", &t);
	while (t--){
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j){
				scanf("%d", &a);
			}
		if(a) printf("Alicen");
		else printf("Bobn");
	}
	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
/* dp[i]的意思是一直到i的时候有多少种可能性
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define mod 10007
using namespace std;
int main(){
	int dp[10100];
	char s[10100];
	int t,cas=1;
	scanf("%d", &t);
	while(t--){
		scanf("%s", s);
		int len = strlen(s);
		dp[0] = 1;
		for (int i = 1; i < len; ++i){
			dp[i] = dp[i-1];
			if(i >= 3 && s[i] == 'e' && s[i-1] == &#39;h&#39; &&
				s[i-2] == 'e' && s[i-3] == &#39;h&#39;){
					dp[i] = (dp[i]+dp[i-3])%mod;
			}
		}
		printf("Case %d: %dn", cas++, dp[len-1]);
	}
	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
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
/* 先把相邻的东东全部搞出来，然后搜索白色有多少块（不算一个的），黑色有多少块
 * 然后比较如果黑色的两块以内直接写出答案，否则如果白色连在一起则只要两次
 * 否则需要3次
 * */
#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;
vector <int>v[40];
inline void v_pb(int a,int b){
	v[a].push_back(b);
}
int num[40];
queue<int>q;
bool vis[40];
bool bfs(int s,int flag){
	while(!q.empty()) q.pop();
	q.push(s);
	int cnt = -1;
	while(!q.empty()){
		int k = q.front(); q.pop();
		cnt++;
		for (int i = 0; i < v[k].size(); i++){
			int d = v[k][i];
			if (!vis[d] && num[d] == flag){
				vis[d] = 1;
				q.push(d);
			}
		}
	}
	if(flag == 0 && cnt == 0)return 1;
	return 0;
}

int main(){
    v_pb(1,2);v_pb(1,3);v_pb(1,17);v_pb(1,18);v_pb(1,20);v_pb(1,13);
    v_pb(2,1);v_pb(2,3);v_pb(2,4);v_pb(2,7);v_pb(2,12);v_pb(2,13);
    v_pb(3,1);v_pb(3,2);v_pb(3,4);v_pb(3,5);v_pb(3,20);
    v_pb(4,2);v_pb(4,3);v_pb(4,5);v_pb(4,6);v_pb(4,7);v_pb(4,8);
    v_pb(5,3);v_pb(5,4);v_pb(5,6);v_pb(5,20);v_pb(5,21);v_pb(5,24);
    v_pb(6,4);v_pb(6,5);v_pb(6,8);v_pb(6,9);v_pb(6,24);
    v_pb(7,2);v_pb(7,4);v_pb(7,8);v_pb(7,10);v_pb(7,12);
    v_pb(8,4);v_pb(8,6);v_pb(8,7);v_pb(8,9);v_pb(8,10);v_pb(8,11);
    v_pb(9,6);v_pb(9,8);v_pb(9,11);v_pb(9,24);v_pb(9,26);v_pb(9,27);
    v_pb(10,7);v_pb(10,8);v_pb(10,11);v_pb(10,12);v_pb(10,14);v_pb(10,16);
    v_pb(11,8);v_pb(11,9);v_pb(11,10);v_pb(11,16);v_pb(11,27);
    v_pb(12,2);v_pb(12,7);v_pb(12,10);v_pb(12,13);v_pb(12,14);v_pb(12,15);
    v_pb(13,12);v_pb(13,15);v_pb(13,2);v_pb(13,1);v_pb(13,17);
    v_pb(14,10);v_pb(14,12);v_pb(14,15);v_pb(14,16);v_pb(14,30);
    v_pb(15,12);v_pb(15,13);v_pb(15,14);v_pb(15,30);v_pb(15,32);v_pb(15,17);
    v_pb(16,10);v_pb(16,11);v_pb(16,14);v_pb(16,27);v_pb(16,29);v_pb(16,30);
    v_pb(17,1);v_pb(17,18);v_pb(17,19);v_pb(17,13);v_pb(17,15);v_pb(17,32);
    v_pb(18,1);v_pb(18,17);v_pb(18,19);v_pb(18,20);v_pb(18,22);
    v_pb(19,17);v_pb(19,18);v_pb(19,31);v_pb(19,22);v_pb(19,23);v_pb(19,32);
    v_pb(20,1);v_pb(20,3);v_pb(20,5);v_pb(20,18);v_pb(20,21);v_pb(20,22);
    v_pb(21,5);v_pb(21,20);v_pb(21,22);v_pb(21,24);v_pb(21,25);
    v_pb(22,19);v_pb(22,18);v_pb(22,20);v_pb(22,21);v_pb(22,23);v_pb(22,25);
    v_pb(23,19);v_pb(23,22);v_pb(23,25);v_pb(23,28);v_pb(23,31);
    v_pb(24,5);v_pb(24,6);v_pb(24,9);v_pb(24,21);v_pb(24,25);v_pb(24,26);
    v_pb(25,21);v_pb(25,22);v_pb(25,23);v_pb(25,24);v_pb(25,26);v_pb(25,28);
    v_pb(26,9);v_pb(26,24);v_pb(26,25);v_pb(26,27);v_pb(26,28);
    v_pb(27,9);v_pb(27,11);v_pb(27,16);v_pb(27,26);v_pb(27,28);v_pb(27,29);
    v_pb(28,25);v_pb(28,26);v_pb(28,27);v_pb(28,29);v_pb(28,31);v_pb(28,23);
    v_pb(29,16);v_pb(29,27);v_pb(29,28);v_pb(29,30);v_pb(29,31);
    v_pb(30,14);v_pb(30,15);v_pb(30,16);v_pb(30,29);v_pb(30,31);v_pb(30,32);
    v_pb(31,28);v_pb(31,29);v_pb(31,30);v_pb(31,32);v_pb(31,23);v_pb(31,19);
    v_pb(32,30);v_pb(32,31);v_pb(32,15);v_pb(32,19);v_pb(32,17);
	int t;
	scanf("%d", &t);
	for (int cas = 1; cas <= t; cas++){
		printf("Case %d: ", cas);
		int black = 0,white = 0;
		for (int i = 1; i <= 32; ++i){
			scanf("%d", &num[i]);
			if(num[i]) black ++;
		}
		if (black == 0) {puts("0");continue;}
		memset(vis,0,sizeof(vis));
		black = 0;
		for (int i = 1; i <= 32; ++i){
			if (!vis[i]){
				vis[i] = 1;
				if (num[i]){
					black ++;
					bfs(i,1);
				}else {
					white ++;
					if(bfs(i,0)) white --;
				}
			}
		}
		if(black <= 2) printf("%dn", black);
		else if (white == 1) puts("2");
		else puts("3");
	}
	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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/* HDU 4637 
 * 我们可以把雨滴看做静止不动，然后maze（这题的那个人）
 * 就是往左上方运动就可以了，计算出maze能跑到的最远的点，
 * 然后就是求起点和终点所构成的线段与每个雨滴交的时间，
 * 注意题目说每个雨滴可能会相交，所以我们对于每个雨滴算出相交的区间，
 * 然后对这些区间进行合并并且计算答案。
 * */
#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 EPS 1e-8
#define pii pair <double,double>
#define X first
#define Y second 
#define pb push_back
using namespace std;

inline int dcmp(double x){
	if (iabs(x) < EPS) return 0;
	else return (x > 0)? 1 : -1;
}
struct point{
	double x,y;
	point(){}
	point(double x,double y):x(x),y(y){}
	double operator *(const point &u)const{
		return x*u.x+y*u.y;
	}
	point operator - (const point &u)const{
		return point(x-u.x,y-u.y);
	}
	point operator + (const point &u)const{
		return point(x+u.x,y+u.y);
	}
	point operator * (const double &u)const{
		return point(x * u,y * u);
	}
}s,e;
int cases,n;
double v1,v2,v,t,T,x,ans;
inline double dou(double x){
	return x * x;
}
inline double cross(point o,point a,point b){
	return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
} 
inline double dis(point a,point b){
	return sqrt(dou(a.x-b.x)+dou(a.y-b.y));
}
inline bool SegIntersect(point a,point b,point l,point r){//两条线段相交 不考虑共线
	return cross(a,b,l) * cross(a,b,r) < EPS && 
		cross(l,r,a) * cross(l,r,b) < EPS;
}
inline double intersect(point a,point b,point l,point r){//两直线相交求交点的x
	double ret = a.x;
	double t = ((a.x-l.x) * (l.y-r.y) - (a.y-l.y) * (l.x-r.x)) /
			((a.x-b.x) * (l.y - r.y) - (a.y-b.y)*(l.x-r.x));
	return ret + (b.x-a.x)*t;
}
vector <double> vec;
vector <pii> res;
struct rain{
	point o,a,b,c;
	double r,h;
	void readin(){
		scanf("%lf%lf%lf%lf", &o.x, &o.y, &r, &h);
		a = o;b = o;c = o;
		a.x -= r;b.x += r;
		c.y += h;
	}
	bool inside(point p){//点是否再雨滴里面
		return (dis(o,p) - EPS < r && p.y - EPS < o.y)
			|| (p.y - EPS > o.y && cross(c,a,p) > -EPS 
				&& cross(c,p,b) > -EPS );
	}

	void intersectC(){//与雨滴半园的交点 求 交点
		point b = s, d = e - s;
        double A = d * d;
        double B = (b - o) * d * 2;
        double C = (b - o) * (b - o) - r * r;
        double dlt = B * B - 4 * A * C;
        if (dlt < -EPS) return;

        if (dlt < EPS) dlt = 0;		//消除dlt负数零的情况
        else dlt = sqrt(dlt);

        double t = (-B - dlt) / (2 * A);
        point tp = b + d * t;
        if (tp.x - EPS < s.x && tp.x + EPS > e.x && tp.y - EPS < o.y)	//因为是半圆，注意把没用的点判掉
            vec.pb(tp.x);

        t = (-B + dlt) / (2 * A);
        tp = b + d * t;
        if (tp.x - EPS < s.x && tp.x + EPS > e.x && tp.y - EPS < o.y)
            vec.pb(tp.x);
    }

	void intersectT(){//与雨滴三角形的交点求交点
		double x;
		if (SegIntersect(a,c,s,e)){
			x = intersect(a,c,s,e);
			if (x - EPS > e.x && x + EPS < s.x)
				vec.pb(x);
		}
		if (SegIntersect(b,c,s,e)){
			x = intersect(b,c,s,e);
			if (x - EPS > e.x && x + EPS < s.x)
				vec.pb(x);
		}
	}

	void solve(){
		vec.clear();
		intersectC();
		intersectT();
		if (inside(s)) vec.pb(s.x);
		if (inside(e)) vec.pb(e.x);
		sort(vec.begin(),vec.end());
		int cnt = unique(vec.begin(),vec.end()) - vec.begin();
		if (cnt >= 2)//取最大最小的两个点作为这个区域的时间段的两个端点
			res.pb(make_pair(vec[0],vec[cnt-1]));
	}
}p;

int main(){
	int _,cases=0;
	scanf("%d", &_);
	while (_--){
		scanf("%lf%lf%lf%lf%lf", &v1, &v2, &v, &t, &x);
		s.x = x; s.y = 0;
		T = v1 * t / (v2 - v1) + t;
		e.x = x - T*v1; e.y = T*v;
		scanf("%d", &n);
		res.clear();
		ans = 0;
		for (int i = 0; i < n; ++i){
			p.readin();
			p.solve();
		}
		sort(res.begin(),res.end());
		double r = e.x;
		int sz = res.size();
		for (int i = 0; i < sz; ++i){
			if (res[i].X - EPS < r && r - EPS < res[i].Y){
				ans += res[i].Y - r;
				r = res[i].Y;
			}
			else if (r - EPS < res[i].X){
				ans += res[i].Y - res[i].X;
				r = res[i].Y;
			}
		}
		printf("Case %d: %.4fn", ++cases, ans / v1);
	}
	return 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;
}