题目传送门
三种情况，没有重叠，有重叠，都重叠
开个二维数组，记录每一种字母的位置
扫描字符串找到位置最靠后的字母
题解的方法还没搞懂
设置一个数组，保存俩个数之间的关系，需要排序，没有要求，要不排序
1.把需要排序的区间范围从小到大排序，保证所有要排序的区间是增的
2.处理不需要排序区间，如果有一个不排序区间完全位于排序区间=>NO
3.已经有了一对非排序，跳出，可以变为非排序的，变化，同时看他前面和他是什么关系
？？？Cmp比较函数出现了问题？？为啥下面的不行
stl sort严格弱序传送门
严格弱序：
C++都定义了 “<”操作符，这就是一个严格弱序，而“<=”就不是一个严格弱序
对于内置类型我们自然可以有<、>、=来判断两个值的大小关系，而对于自定义的类类型，为它定义三种比较操作符是没有必要的，只用一个严格弱序（这里就用<为例）就可以表示两个元素三种大小关系
a 小于 b $a < b$
a 大于 b $b < a$
a 等于 b $!(a < b) $&&$ !(b < a)$
严格弱序的三条要求
- 两个关键字不能同时“严格弱序”于对方
- 如果a“严格弱序”于b，且b“严格弱序”于c，则a必须“严格弱序”于c
- 如果存在两个关键字，任何一个都不“严格弱序”于另一个，则这两个关键字是相等的。
1.两个关键字不能同时“<=”于对方
显然有a<=b,b<=a，a，b相等时成立**(不满足弱序的第一条)
2.如果存在两个关键字，**任何一个都不“<=”于另一个**，则这两个关键字是相等的。
**a不小于等于b，且b也不小于等于a，也就是a>b且b>a，这明显是一个伪命题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool Cmp1(Pos a,Pos b)
{
if(a.l < b.l) return true;
else if(a.l == b.l)
{
if(a.r <= b.r) return false;
else return true;
}
else return false;
}
bool Cmp2(Pos a,Pos b)
{
if(a.l <= b.l) return true;
else return false;
}
|
sort排序误区 传送门
1.sort需要迭代器是随机访问迭代器。如果使用list容器，可以使用list容器自带的sort成员函数，而不要使用使用这个泛型算法的sort。
2.sort的加比较函数的重载版本：sort（begin,end,comp），需要comp编译时不能被改变符号名。类成员函数无法作为比较函数，但是可以使用比较类或者重载类的比较运算符。一般采用的方法时定义comp为全局的函数，或者C++ 11可以使用lambda表达式。详情可以参考[1].
3.comp函数的书写需要注意严格弱序规则。所谓严格弱序规则，简单来讲就是只用一个严格弱序就能区分两个关键字的大小。比如 x大于y可以用y<x来表示，x小于y可以用x<y来表示,x等于y可以用 !(x<y) && !(y<x) 来表示。x和y的三种大小关系可以只用一个<就能区分了 。但是如果只使用<=,就x等于y就无法表示。
题目代码：
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
|
struct Pos
{
int l,r;
};
Pos a1[MAX];
Pos a0[MAX];
int a[MAX];
int book[MAX][MAX];
bool Cmp(Pos a,Pos b)
{
if(a.l < b.l) return true;
else if(a.l == b.l)
{
if(a.r <= b.r) return true;
else return false;
}
else return false;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
Pos temp;
int t,l,r;
int cnt1 = 0;
int cnt0 = 0;
while(M--)
{
cin >> t >> l >> r;
temp.l = l;
temp.r = r;
if(t == 1)
{
a1[cnt1] = temp;
cnt1++;
}
else
{
a0[cnt0] = temp;
cnt0++;
}
}
sort(a1,a1+cnt1,Cmp);
fill(a+1,a+N+1,1);
for(int i = 0;i < cnt1;++i)
{
for(int j = a1[i].l;j <= a1[i].r;j++)
{
if(!book[j][j+1]) a[j] = a[j-1]+1;
if(j != a1[i].r) book[j][j+1] = 1;
}
}
int flag = 1;
for(int i = 0;i < cnt0;++i)
{
int j = 0;
for(j = a0[i].l;j < a0[i].r;++j)
{
if(a[j] > a[j+1])
{
book[j][j+1] = 2;
break;
}
else if(book[j][j+1] == 0 && book[j-1][j] != 2)
{
a[j] = a[j+1]+1;
book[j][j+1] = 2;
break;
}
else if(book[j][j+1] == 0 && book[j-1][j] == 2)
{
int k = j;
book[j][j+1] = 2;
a[k] = a[k+1]+1;
while(k--)
{
if(k == 0) break;
a[k] = max(a[k+1]+1,a[k]);
if(book[k-1][k] != 2)
break;
}
break;
}
}
if(j == a0[i].r)
{
flag = 0;
break;
}
}
if(flag)
{
cout << "YES" <<endl;
for(int i = 1;i <= N;i++)
{
cout << a[i];
if(i != N) cout << " ";
else cout <<endl;
}
}
else cout << "NO" <<endl;
return 0;
}
|
题目代码:
tsize：节点对于ans的贡献值，包括自己
dp：节点的ans
$$
dp_n = tsize_n + \sum dp_i (i \in n的子树)
$$
那么我们每次dp过程可以把root换到n的一个儿子节点to上面
1：先把to儿子从n上砍掉
1
2
3
| dp[n] -= dp[to];
dp[n] -= tsize[to];
tsize[n] -= tsize[to];
|
2：在to这个root上添加n这个儿子
1
2
3
| tsize[to] += tsize[n];
dp[to] += dp[n];
dp[to] += tsize[n];
|
所有的节点当一次root就算出来了
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
|
vector<int> edge[MAX];
LL tsize[MAX];
LL dp[MAX];
LL ans = 0;
LL caculatesize(int n,int v)
{
tsize[n] = 1;
for(int i = 0;i < edge[n].size();i++)
{
if(edge[n][i] == v) continue;
tsize[n] += caculatesize(edge[n][i],n);
}
return tsize[n];
}
LL firstdp(int n,int v)
{
dp[n] = tsize[n];
for(int i = 0;i < edge[n].size();i++)
{
if(edge[n][i] == v) continue;
dp[n] += firstdp(edge[n][i],n);
}
return dp[n];
}
void dfs(int n,int v)
{
ans = max(ans,dp[n]);
for(int i = 0;i < edge[n].size();i++)
{
if(edge[n][i] == v) continue;
int to = edge[n][i];
dp[n] -= dp[to];
dp[n] -= tsize[to];
tsize[n] -= tsize[to];
tsize[to] += tsize[n];
dp[to] += dp[n];
dp[to] += tsize[n];
dfs(to,n);
dp[to] -= tsize[n];
dp[to] -= dp[n];
tsize[to] -= tsize[n];
tsize[n] += tsize[to];
dp[n] += tsize[to];
dp[n] += dp[to];
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
M = N - 1;
int l,r;
while(M--)
{
cin >> l >> r;
edge[l].push_back(r);
edge[r].push_back(l);
}
caculatesize(1,-1);
ans = firstdp(1,-1);
dfs(1,-1);
cout << ans <<endl;
return 0;
}
|
