作者：mthp | 来源：互联网 | 2023-09-25 18:48
搞了好久才把大部分题目题解看完了，真是太弱了。A题简单暴力题一个一个匹配，对应位置字母要么相同，要么是..B题给定一个矩阵，左下角(0,0)，右上角(n,m)，取4个不同的点连成一段折线
搞了好久才把大部分题目题解看完了，真是太弱了。
A题简单暴力题一个一个匹配，对应位置字母要么相同，要么是'.'.
B题给定一个矩阵，左下角(0,0)，右上角(n, m)，取4个不同的点连成一段折线，要有最长的折线长度。
排除n == 0 和m == 0 ，剩下的情况中总共由4中情况：
枚举一下就可以了
1. (0,0)->(n,m)->(0, m)->(n, 0)
2. (0,0)->(n,m)->(n, 0)->(0, m)
3.(n,m-1)->(0,0)->(n,m)->(0,1)
4.(0,m-1)->(n,0)->(0,m)->(n,1)
代码：
1 //Template updates date: 20140718
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include <string>
11 #include
12 #include <set>
13 #include
View Code
C题:有n种卡片，每种m张,魔术师每次从中选取n张然后给观众选取，自己再从中选出一张，问最后选得的和观众相同的概率是多少？
分析：由于最后选得的相同的卡片肯定是n种中一种，而且是哪种不重要，这样只需考虑，该种卡片在选出的n张牌占多少？
选出卡片中该种有i张，然后最后魔术师和观众选中该种卡片，这样概率就是：C(m,i)*C((n-1)m, n-i)*(i/n)^2/C(nm,n) 1<=i<=min(n, m)
由于对应n种卡片都是上面这样计算的，所以上面结果*n就是最后结果了。
最后计算时候可以用log这样乘除法转化为+，-,对于概率计算很方便，对结果取一下e^ans放就可以了。
1 //Template updates date: 20140718
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include <string>
11 #include
12 #include <set>
13 #include
View Code
D题：有k件衣服，每件必须先后并且连续经过3种操作，洗涤，烘干，折叠，分别由3种机器来完成，其中机器数目为n1,n2,n3,一个机器只能同时对一件衣服进行对应操作。其中衣服完成每种操作的时间为t1,t2,t3.求最后完成所有衣服3种操作的最短时间。
分析：由于每种操作最多可能处理ni件衣服所以第ni+1件衣服和第1件衣服的开始处理时间必须相差ti，根据这个可以推理最终完成时间。
代码：
//Template updates date: 20140718
#include
#define esp 1e-6
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(x) (x&(-x))
#define mp(a, b) make_pair((a), (b))
#define bit(k) (1<<(k))
#define iin freopen("pow.in", "r", stdin);
#define oout freopen("pow.out", "w", stdout);
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout);
#define bug puts("********))))))");
#define Inout iin oout
#define inout in out
#define SET(a, v) memset(a, (v), sizeof(a))
#define SORT(a) sort((a).begin(), (a).end())
#define REV(a) reverse((a).begin(), (a).end())
#define READ(a, n) {REP(i, n) cin>>(a)[i];}
#define REP(i, n) for(int i = 0; i <(n); i++)
#define VREP(i, n, base) for(int i = (n); i >= (base); i--)
#define Rep(i, base, n) for(int i = (base); i <(n); i++)
#define REPS(s, i) for(int i = 0; (s)[i]; i++)
#define pf(x) ((x)*(x))
#define mod(n) ((n))
#define Log(a, b) (log((double)b)/log((double)a))
#define Srand() srand((int)time(0))
#define random(number) (rand()%number)
#define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector VII;
typedef vectorint> VIII;
typedef VI:: iterator IT;
typedef map<string, int> Mps;
typedef map<int, int> Mpi;
typedef map<int, PII> Mpii;
typedef mapint> Mpiii;
int n, n1, n2, n3, t1, t2, t3;
const int maxn = 10000 + 100;
int w[maxn];
int main() {
scanf("%d%d%d%d%d%d%d", &n, &n1, &n2, &n3, &t1, &t2, &t3);
Rep(i, 1, n+1) {
int c = 0;
if(i > n1) c = max(c, w[i-n1]+t1);
if(i > n2) c = max(c, w[i-n2]+t2);
if(i > n3) c = max(c, w[i-n3]+t3);
w[i] = c;
if(i == n)
cout<endl;
}
return 0;
}
View Code
E题：给定3个串s1,s2,s3,对每一个l(1<=l<=min(|s1|,|s2|,|s3|))求三元组(i,j,k)的个数，三元组是指满足
##：s1[i,i+l-1], s2[j,j+l-1],s3[k,k+l-1]是完全相同字符串的条件。
分析：表示知道用后缀数组处理，然后就不知道怎么做了，看了题解还是有点不明白，先留个坑，
UPD:终于吧这道题弄懂了。
分析：题目是要统计对于长度为l的字串，三元组的(i, j, k)的个数，其中满足上面##的条件。很巧妙的用到了并查集的，我们可以利用后缀数组求出h数组。
将LCP值相同的对应的h下标，也就是h值相同的下标集中存储，然后按照h从大到小,依次将h数组中位于相邻位置，且LCP>=当前h值的下标用并查集合并在一起。
对于并查集中根节点rt, cnt[0][rt], cnt[1][rt], cnt[2][rt]表示LCP大于当前的h值中，所有的子串中出自第1,2,3个的有多少个，每次合并之前减去之前的值，利用合并之后的cnt数组进行更新。
代码：
1 #include
2 #define in freopen("solve_in.txt", "r", stdin);
3 #define bug(x) printf("Line #%d: >>>>><<<\n", (x));
4 typedef long long LL;
5
6 using namespace std;
7 const LL M = 1000000007;
8
9 const int maxn = 3*(int)1e5+1000;
10 int s[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], h[maxn], rk[maxn];
11 int n;
12 char str[3][maxn];
13 LL cnt[3][maxn];
14 int fa[maxn];
15 int slen[3];
16 int res[maxn];
17
18 vector<int> g[maxn];
19
20 void buildSa(int m)
21 {
22 int *x = t, *y = t2;
23 for(int i = 0; i 0;
24 for(int i = 0; i ;
25 for(int i = 1; i 1];
26 for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
27
28 for(int k = 1; k <= n; k <<= 1)
29 {
30 int p = 0;
31 for(int i = n-k; i i;
32
33 for(int i = 0; i 0;
34 for(int i = 0; i if(sa[i] >= k) y[p++] = sa[i]-k;
35 for(int i = 0; i ;
36 for(int i = 1; i 1];
37
38 for(int i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
39 swap(x, y);
40 p = 1;
41 x[sa[0]] = 0;
42 for(int i = 1; i )
43 x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k] ? p-1 : p++;
44 if(p >= n) break;
45 m = p;
46 }
47 }
48 void getHeight()
49 {
50 int j, k = 0;
51 h[0] = 0;
52 for(int i = 0; i i;
53 for(int i = 0; i )
54 {
55
56 if(k) k--;
57 if(rk[i] == 0)
58 continue;
59 j = sa[rk[i]-1];
60 while(s[i+k] == s[j+k]) k++;
61 h[rk[i]] = k;
62 }
63 }
64 int findset(int x)
65 {
66 return x == fa[x] ? x : fa[x] = findset(fa[x]);
67 }
68 void Union(int x, int y)
69 {
70 int fx = findset(x);
71 int fy = findset(y);
72 if(fx == fy)
73 return;
74 for(int i = 0; i <3; i++)
75 cnt[i][fx] += cnt[i][fy];
76 fa[fy] = fx;
77 }
78
79 void init()
80 {
81 for(int i = 0; i )
82 {
83 fa[i] = i;
84 }
85 int base = 0;
86 for(int k = 0; k <3; k++)
87 {
88 for(int j = 0; j )
89 cnt[k][j+base+k] = 1;
90 base += slen[k];
91 }
92 }
93
94 void solve()
95 {
96 LL ans = 0;
97 for(int i = n-1; i > 0; i--)
98 {
99 int sz = g[i].size();
100 for(int j = 0; j )
101 {
102 int v = g[i][j];
103 int x = findset(sa[v-1]);
104 int y = findset(sa[v]);
105 ans -= cnt[0][x]*cnt[1][x]%M*cnt[2][x]%M;
106 if(ans <0)
107 ans += M;
108 ans -= cnt[0][y]*cnt[1][y]%M*cnt[2][y]%M;
109 if(ans <0)
110 ans += M;
111 Union(x, y);
112 x = findset(x);
113 ans = (ans+cnt[0][x]*cnt[1][x]%M*cnt[2][x]%M)%M;
114
115 }
116
117 res[i] = ans;
118 }
119
120 int len = min(slen[0], min(slen[1], slen[2]));
121 for(int i = 1; i <= len; i++)
122 printf("%d%c", res[i], i == len ? '\n' : ' ');
123 }
124 int main()
125 {
126
127 scanf("%s%s%s", str[0], str[1], str[2]);
128 for(int k = 0; k <3; k++)
129 {
130 for(int i = 0; str[k][i]; i++)
131 {
132 s[n++] = str[k][i] - 'a' + 1;
133 slen[k]++;
134 }
135 s[n++] = 30+k;
136 }
137 s[n++] = 0;
138 init();
139 buildSa(60);
140 getHeight();
141 for(int i = 1; i )
142 if(h[i])
143 g[h[i]].push_back(i);
144 solve();
145 return 0;
146 }
View Code
思路很类似的一道题：
F题：给定一个数组a[1...n]，为1....n的数的排列， n<=300000,是否存在两个数a，b，a+b/2在这数组中位于这两个数之间。实际就是判断是否三个数构成等差数列。
分析：这题要用线段树+hash来维护，首先容易知道，a,b,c构成等差那么 a，b之差与b,c之差是相等的，那么过程是这样的依次每次取出一个数a[i]，然后把a[i]和n-a[i]+1插入到两棵线段树中；如果不存在两个数与a[i]构成等差数列，例如数组中10个元素，对于2,5,8，5不能和2,8构成等差，2,8在数组中位置要么在5前面，要么在5后面，如果2,8在前面，那么将2,8以及10-2+1 = 9,10-8+1=3插入后，两棵线段树相应位置均会被增加相同元素，这样对应的线段树就应该都是序列2...8,那么比较两棵线段树相应区间hash值就可以了。同样对于2,8出现在5后面也可以判断。
一旦遇到hash值不同的情况说明存在等差数列。
代码：
1 //Template updates date: 20140718
2 #include
3 #define esp 1e-6
4 #define inf 0x3f3f3f3f
5 #define pi acos(-1.0)
6 #define pb push_back
7 #define lson l, m, rt<<1
8 #define rson m+1, r, rt<<1|1
9 #define lowbit(x) (x&(-x))
10 #define mp(a, b) make_pair((a), (b))
11 #define bit(k) (1<<(k))
12 #define iin freopen("pow.in", "r", stdin);
13 #define oout freopen("pow.out", "w", stdout);
14 #define in freopen("solve_in.txt", "r", stdin);
15 #define out freopen("solve_out.txt", "w", stdout);
16 #define bug puts("********))))))");
17 #define Inout iin oout
18 #define inout in out
19
20 #define SET(a, v) memset(a, (v), sizeof(a))
21 #define SORT(a) sort((a).begin(), (a).end())
22 #define REV(a) reverse((a).begin(), (a).end())
23 #define READ(a, n) {REP(i, n) cin>>(a)[i];}
24 #define REP(i, n) for(int i = 0; i <(n); i++)
25 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)
26 #define Rep(i, base, n) for(int i = (base); i <(n); i++)
27 #define REPS(s, i) for(int i = 0; (s)[i]; i++)
28 #define pf(x) ((x)*(x))
29 #define mod(n) ((n))
30 #define Log(a, b) (log((double)b)/log((double)a))
31 #define Srand() srand((int)time(0))
32 #define random(number) (rand()%number)
33 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
34
35 using namespace std;
36 typedef long long LL;
37 typedef unsigned long long ULL;
38 typedef vector<int> VI;
39 typedef pair<int,int> PII;
40 typedef vector VII;
41 typedef vectorint> VIII;
42 typedef VI:: iterator IT;
43 typedef map<string, int> Mps;
44 typedef map<int, int> Mpi;
45 typedef map<int, PII> Mpii;
46 typedef mapint> Mpiii;
47
48 const int maxn = 300000 + 100;
49 const int L = 100003;
50
51 LL b[maxn];
52
53 int n;
54 int a[maxn];
55 LL ans;
56 struct SegTree {
57 LL h[maxn<<2];
58 void build(int l, int r, int rt) {
59 if(l == r) {
60 h[rt] = 0;
61 return;
62 }
63 int m = (l+r)>>1;
64 build(lson);
65 build(rson);
66 }
67 void PushUp(int l, int r, int rt) {
68 int m = (l+r)>>1;
69 int ll = r-m;
70 h[rt] = h[rt<<1]*b[ll]+h[rt<<1|1];
71 }
72 void update(int l, int r, int rt, int pos) {
73 if(pos == l && pos == r) {
74 h[rt] = b[1];
75 return;
76 }
77 int m = (l+r)>>1;
78 if(pos <= m)
79 update(lson, pos);
80 else update(rson, pos);
81 PushUp(l, r, rt);
82 }
83 void query(int L, int R, int l, int r, int rt) {
84 if(L > R)
85 return;
86 if(L <= l && R >= r) {
87 ans = ans*b[r-l+1]+h[rt];
88 return;
89 }
90 int m = (l+r)>>1;
91 if(L <= m)
92 query(L, R, lson);
93 if(R > m)
94 query(L, R, rson);
95 }
96 } t1, t2;
97 int main() {
98
99 scanf("%d", &n);
100 b[0] = 1;
101 Rep(i, 1, n+1) {
102 scanf("%d", a+i);
103 b[i] = b[i-1]*L;
104 }
105 t1.build(1, n, 1);
106 t2.build(1, n, 1);
107 Rep(i, 1, n+1) {
108 int v = a[i];
109 int l = min(v-1, n-v);
110 ans = 0;
111 t1.query(v-l, v-1, 1, n, 1);
112 LL tmp = ans;
113 ans = 0;
114 t2.query(n-v-l+1, n-v, 1, n, 1);
115 if(tmp != ans) {
116 puts("YES");
117 return 0;
118 }
119 t1.update(1, n, 1, v);
120 t2.update(1, n, 1, n-v+1);
121 }
122 puts("NO");
123 return 0;
124 }
View Code
京公网安备 11010802041100号