分类: acm - CheaSim Blog

[hdoj5559]Frog and String

Frog and String

题意

给定一个字符串的长度和他里面子回文串的个数。

  • 子回文串是连续子串,并且相同的回文串不重复计数
  • 字符串由前$K$个字符构成

题解

构造题嘛,最重要的就是规律啦。

对于构造题,我们就要一步一步来,把题目分段。

  1. 首先对于$K=1$来说,如果$n !=m$的话,无解。
  2. 对于$K=2$来说,这时候爆搜就起作用了,我怎么想也不肯能根据我那只有6长度的字符串想到会存在一个长度为8但是只有7个自回文串的字符串。他就是$AABABBAA$.估计只有搜才能发现这个玩意,之后就会发现只有两个字符,你也能构造一个长度很长,但只有很少的子回文串。$AABABB$这个玩意可以无限重复,但是只有$A,B,AA,BB,ABA,BAB,ABBA,BAAB$这四种玩意。
  3. 对于$K \ge 3$,最好想,就是$ABC$来重复计数,$m-3$个前导$A$

我真是蠢,真的,没有去用爆搜找一下答案,就凭自己的直觉在那里搞来搞去。

+1 $m=2$的时候少考虑了

+1 当$k>m$的时候

+1 单独测试用例 没有print case

+1 特判m==n没有加else if

+1 $k=2,n=m$的时候出现了错误。应该特判的。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
const int maxk = 30;
int n,k,m;
char magic[10] = "ABAABB";
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int T; scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d%d%d",&n,&m,&k);
bool flag = false;
if(n!=m){
if(k==1) flag = true;
if(k==2 && m<8) flag = true;
if(k>=3 && m<=2) flag = true;
if(n<m) flag = true;
if(m==7 && n==8 && k==2){
printf("Case #%d:\n",test_case);
puts("AABABBAA");
continue;
}
}
printf("Case #%d:\n",test_case);
if(flag) puts("Impossible");
else if(n==m){
rep(i,0,n) printf("A");
puts("");
}else if(k==2){
int cnt = m-8;
rep(i,0,cnt) printf("A");
rep(i,0,n-cnt) printf("%c",magic[i%6]);
puts("");
}else{
vector<char> ve;
rep(i,0,m-3) printf("A");
rep(i,0,3) ve.push_back('A'+i);
rep(i,0,n-m+3){
printf("%c",ve[i%3]);
}
puts("");
}
}
return 0;
}

[hdoj6387]AraBellaC

AraBellaC

题意

一段序列中只有$A,B,C$三种字母,这段序列是一段周期序列,并且他的重复序列是这样子的。

  • AAAABBBBCCCCC

他的重复序列由$a$个A,$b$个B,$c$个C组成,并且是有顺序的。

给定以下规则。

  • 给你$m$个位置的值。
  • 其余的位置

问你生成一个序列,使得$a,b,c$的字典序最小,如果没有输出$NO$

题解

二分。

枚举重复序列的长度,那么我们要检验的就是$a,b,c$满足不满足要求。下面就可以用二分来解决。

感觉复杂度有点高。。

我们分别用三个数组存放A,B,C的位置。那么在搜索每个区间内的最后面的一个A,B,C和最前面的一个A,B,C。

之后比较复杂的就是,将一些不对的答案剔除。

因为我们得到了每个字母第一次出现和最后一次出现的位置,我们就可以得到$a,b,c$并且把一些值给剔除。

定义$a_{max},a_{min},b_{max},b_{min},c_{max},c_{min}$分别为他们出现的位置。

  • $a_{max} < b_{min}$ 并且$b_{max} < c_{min}$
  • 可能会存在没有b和c的情况,这种都要舍去。
  • 因为要字典序最小,所以$a$要尽可能的小。

$a=a_{max}-begin+1,b = b_{max}-a_{max}+1,c = len-a-b$

ac代码

[hdoj5881]Tea

Tea

题意

题意有点复杂。给你一壶茶,容量范围为$[L,R]$。之后给你两个杯子。让你从茶壶中往杯子里加茶。结果有以下要求。

  • 经过$ans$次加水,$ans$最小
  • 两个杯子的茶水量相差不超过$1$
  • 茶壶中茶水量最终不超过$1$

题解

贪心。

贪心很好想,就是细节很多。

记录茶杯1为a,茶杯2为b。

  1. 我们首先向a添加$L/2+0.5$的茶水,之后茶壶中还剩下的范围为$[L/2-0.5,R-L/2-0.5]$。如果满足要求,那么$ans$就是$1$。

  2. 之后我们往b添加$L/2-0.5$的茶水,之后茶壶中剩下的范围为$[0,R-L-2]$。如果满足要求,$ans$就是$2$。

  3. 之后我们循环往每个茶杯中加入$2$的水,直到满足要求。

需要注意的是,如果$L=0$的话要特判,还有如果$R<=1$那么就直接满足条件,如果$R<=2$的话只要添加一次。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll l,r;
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>l>>r){
if(r<=1) puts("0");
else if(r<=2) puts("1");
else if(l==0) printf("%lld\n",(r-1)/2+1);
else {
ll temp = r-l-3;
temp = max(0ll,temp);
ll ans = temp/2;
if(ans*2<temp) ans++;
printf("%lld\n",ans+2);
}
}

return 0;
}

[cf-767b]The Queue

The Queue

题意

题意有点复杂,懒得写了。

题解

贪心。

注意的点就是,可以在还没有开始就进入队列进行排队,所以计算的时候虽然是一样的,但还是要注意一下。

特殊情况就是对于在ed以后的人来说,他们就不算了,不算人。

+1 p数组 忘记开long long了。

+1 如果加入时间超过进入时间了就不行了。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
ll st,ed,t;
int n;
const int maxn = 1e5+10;
ll p[maxn];
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
scanf("%lld%lld%lld",&st,&ed,&t);
scanf("%d",&n);
rep(i,0,n) scanf("%lld",p+i),p[i]-=st;
ed -= st;
ll ans = 1e13;
ll wait = 1e14;
int cnt = 0;
rep(i,0,n){
if( (ll)(i+1)*t>ed || p[i]+t>ed) break;
cnt++;
if(p[i] > (ll)(i)*t && p[i]+t<=ed){
ans = p[i]-1;
cout<<ans+st<<'\n';
return 0;
}else{
ll temp = (ll)(i)*t - p[i];
if(wait > temp){
wait = temp;
ans = p[i]-1ll;
}
}
}
ll temp = (ll)(cnt+1)*t; if(temp<=ed) ans = temp-t;
printf("%lld\n",ans+st);

return 0;
}

[cf-767D]Cartons of milk

Cartons of milk

题意

每天喝$k$瓶牛奶,每瓶牛奶都有$s$的保质日期,现在我有$n$瓶牛奶,去商场最多可以买多少瓶牛奶。

条件是每天都要喝$k$瓶牛奶,在最有情况下所有牛奶都不会过期。

题解

贪心,反正所有牛奶的贡献都是1,所以保质期越后面的越好。

计算能买多少瓶就是从第一天开始遍历,能买到就买对应的期限的牛奶。

+1: 中间一个变量爆了int

+1: 有两个变量$n,m$,sort的时候用了$n$,应该用$m$。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m,k;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
int vis[maxm];
int mx[maxm];
struct node{
int id;
int val;
bool operator<(const node &x)const{
return val>x.val;
}
}a[maxn];
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&k);
bool flag = false;
rep(i,0,n){
int x;scanf("%d",&x);
vis[x]++;
}
rep(i,0,m){
int x;scanf("%d",&x);
mx[x]++;
a[i].val = x; a[i].id = i+1;
}
sort(a,a+m);
int ans = 0;
ll now = k;
rep(i,0,maxm){
if(vis[i] > now){
flag = true;
break;
}else{
int temp = min(now-vis[i],(ll)mx[i]);
int t = vis[i] + temp;
ans += temp;
now += k-t;
}
}
if(flag) puts("-1");
else{
printf("%d\n",ans);
rep(i,0,ans){
printf("%d ",a[i].id);
}
puts("");
}

return 0;
}

[uva10479]The Hendrie Sqquence

The Hendrie Sequence

题意

给定一段序列的生成方式,问第$n$个元素是多少。 $0<n<2^{63}$。

  • $H(1) = 0$
  • $H(n) = H(n-1)$中的每个元素$a_i$,那么每个元素就生成一个小子序列$0,0,0,0,0,a_i+1$其中$0$的个数是$a_i$。
  • 除了第一个元素之外的所有元素都要进行这种变化

举个例子,

$H(1) = 0$

$H(2) =0,1$ //$0$变成了$0,1$

$H(4) = 0,1,0,2$ //$0$ 变成了$0,1$, $1$变成了$0,2$

$H(8) = 0,1,0,2,1,0,0,3$ //$0$ 变成了$0,1$, $1$变成了$0,2$ ,$2$变成了$0,0,3$

题解

找规律,我们可以发现每次都变化之后序列的长度都翻了一倍。所以我们单独把他增长的序列拿出来看。可以用心去发现这样一个规律。

  • 定义增长的序列为$b_i$
  • $b_i$是由$1$个$b_{i-1}$,$2$个$b_{i-2}$,$3$个$b_{i-3}$,$4$个$b_{i-4}$…$i$个$b_{0}$ ,再加上一个单独的数字$i$。以此类推出来的。

那么我们就可以从第$n$个元素表示在它属于的那次增长中,它排第几个递归到最初的那几个元素中去,要判断一下范围。

由于题目中的数据比较极限,所以能用unsigned long long 还是用unsigned long long 吧。

如果用unsigned long long。一般数据量输入很小 可以用cin很靠谱。但是要把endl换成’\n’还有输入

1
2
std::ios::sync_with_stdio(false);
cin.tie(0);

或者判断他是$2$的几次幂的时候可以这样子判断最高位的$1$在哪里。

1
2
3
4
ll n; int dep=0;
ll temp = n;
while(temp) temp>>=1,dep++;
dep--;

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
ll n;
ll lie[10][20] ={ {0}, {1}, {0,2}, {1,0,0,3},{0,2,1,1,0,0,0,4}};
ll solve(ll x,int dep){
if(dep<5){
return lie[dep][x];
}
ll st = 0;
rep(i,2,dep+1){
ll temp = pow(2,dep-i-1);
if(i==dep) temp = 1;
if(x<temp*(1ll*i-1ll)+st) return solve((x-st)%temp,dep-i);
st += temp*(ll)(i-1);
}
return dep;
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n && n){
int dep = 0;ll temp = 1;
n--;
ll tn = n;
while(tn) tn/=2,dep++;
temp<<=(dep-1);
n = n - temp;
cout<<solve(n,dep);
cout<<'\n';
}

return 0;
}

[hdoj5505]GT and numbers

GT and numbers

题意

题目意思比较绕,就是给定一个$N$和$M$问至少要多少次下列的操作可以使得$N$等于$M$。

  • 将N乘上一个它的因子(注意$N$也会变)。

题解

由于我们要求$N$转化成$M$,那么其实就是他们的素因子变成相同。

$N = 2^{a_1} * 3^{a_2}5^{a_3}…$

$M = 2^{b_1}*3^{b_2}5^{b_3}…$

那么我们就可以看出 如果要让$a_1=b_1,a_2=b_2,a_3=b_3…$我们需要在他们差距最大的那个素因子中他们相差的倍数的。

$log_2(倍数)$

tip 由于2e63 爆了long long 。所以要用unsigned long long。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef unsigned long long ll;
const int INF = 0x3f3f3f3f;
//head
ll n,m;

int prime[1100000],primesize,phi[11000000];
bool isprime[11000000];
void getlist(int listsize)
{
memset(isprime,1,sizeof(isprime));
isprime[1]=false;
for(int i=2;i<=listsize;i++)
{
if(isprime[i])prime[++primesize]=i;
for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==0)break;
}
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int T; scanf("%d",&T);
getlist(4000000);
while(T--){
scanf("%llu%llu",&n,&m);
ll ans = 0;
bool flag = false;
for(ll i=1;prime[i]<=n;i++){
ll cnt1= 0,cnt2 = 0;
ll t = prime[i];
while(n%t==0) n/=t,cnt1++;
while(m%t==0 && m) m/=t,cnt2++;
if(cnt1>cnt2 ||(cnt1==0 && cnt2>0)){
flag = true;
break;
}
if(cnt1 == 0) continue;
ll temp = cnt2/cnt1;
if(temp*cnt1<cnt2) temp++;
ans = max(temp,ans);
}
if(m>1) flag = true;
if((n==1 && n!=m) || flag){
puts("-1");
}else{
if(ans==0){
puts("0");
continue;
}
ll temp = 1;
int res = 0;
while(temp<ans) temp<<=1,res++;
printf("%d\n",res);
}
}
return 0;
}

[77c Beavermuncher-0xFF树形dp+贪心

C. Beavermuncher-0xFF

题意

给你一颗树,树上的每个节点有$n$个海狸。现在你在节点$root$上你前往下一个节点的条件是下一个节点上面至少有一个海狸,之后你到这个节点之后,你就会吃掉这个海狸。问最多能吃掉多少只海狸。

题解

贪心+树形dp

ac代码

[hdoj4622]Reincarnation 字符串hash+dp

Reincarnation

题意

区间查询不同字符串的数量。

题解

字符串hash+dp思想

我们从$1-len$枚举子串的长度,如果该区间内子串就加1。由于可能会有重复所以记录长度为$x$的子串最后一次出现的$L$。如果子串出现过那么$dp[L][R]-1$。

定义$dp[l][r]$为在$[l,r]$区间内不同子串的数量那么可以得到递推公式

  1. $dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]$

相当于把一个区间拆成三部分,$[l+1][r],[l][r-1],[l+1][r-1]$,这三个区间合并就是前两个集合个数相加之后减掉这两个集合并的部分元素的个数。

妙啊!

之后在预处理枚举出每一种长度的子串,从1循环到Len,如果发生重复那么可以将之前出现的+1操作的$L$到现在操作的$R$减少一个,那么这个区间的不同子串的个数就减少了一个。而且由于是递推的所以所有$[1,2,3,4,5]-L,R$都会减少1.

由于$n\leq 2000$所以可以使用$O(n^2)$的做法。

主要是dp要想明白,如果一旦确定了递推情况,就不用管细枝末节的东西了,直接在区间上减少就可以了,使得每次dp都是正确的。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
typedef unsigned long long ull;
int n;
char s[maxn];
ull base[maxn],has[maxn],pos[maxn];
ull bas = 131;
const int mod = 1e5+7;
struct Hash_table{
int head[mod+2],num;
ull edgenum[maxn];
int next[maxn],close[maxn];
void init(){
num = 0;
memset(head,-1,sizeof(head));
}
int add(ull val,int id){
int u = val % mod;
for(int i=head[u];~i;i=next[i]){
if(val == edgenum[i]){
int temp = close[i]; close[i] = id;
return temp;
}
}
edgenum[num] = val;
close[num] = id;
next[num] = head[u];
head[u] = num++;
return -1;
}
}H;
int dp[maxn][maxn];
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
int T;scanf("%d",&T);
base[0] = 1;
rep(i,1,maxn) base[i] = base[i-1]*bas;
while(T--){
scanf("%s",s+1); int len = strlen(s+1);
memset(dp,0,sizeof(dp));
rep(i,1,len+1) has[i] = has[i-1]*bas + s[i] - 'a' + 1;
for(int x=1;x<=len+1;x++){
H.init();
for(int i=1;i+x-1<=len;i++){
int pos = H.add(has[i+x-1]-base[x]*has[i-1],i);
dp[i][x+i-1]++;
if(pos != -1) dp[pos][x+i-1]--;
}
}
per(i,1,len+1) rep(j,i,len+1)
dp[i][j] += dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
int q;scanf("%d",&q);
while(q--){
int x,y;scanf("%d%d",&x,&y);
printf("%d\n",dp[x][y]);
}
}

return 0;
}

[hdoj6406]Taotao Picks Apple

Taotao Picks Apples

题意

一段序列,从中挑选的子序列是这样规定的

能取就取,而且取得数字一定要比上一次取得数字要大。

已知一段序列,问如果改变序列中的一个数字,那么取得数字的个数是多少。

题解

每次查询将数组分为两部分$[1,p-1],[p+1,n]$,前半部分的最长长度就是可以通过预处理得到。很容易想到先处理出从头到$i$的最大长度$dl[i]$。然后针对后半段,我们要得到的是置换的$q$,然后大于他的第一个数字到末尾的最大长度。

有一个细节就是,如果置换的数字小于前面最大的数字,那么就是从前面最大的数字到$[p+1,n]$中间大于这个数字的第一个数字开始。

如果置换的数字大于前面最大的数字,那么答案就是$dl([1,p-1])+1+dr([p+1,n])$这个意思。

寻找第一个比该数字大的最前数字用的是线段树。


+1 判断最大值的时候直接用mmax判断,应该用a[x]判断

+1 得到dr数组的时候范围搞错了,应该是[i,n]的范围内比a[i]大的第一个数字。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5+100;
int n,m;
int a[maxn];
struct Segtree{
int mmax[maxn<<2]={0},id[maxn<<2]={0},cur=0;
void pushup(int rt){
int x = id[rt<<1],y = id[rt<<1|1];
id[rt] = a[x]>a[y]?x:y;
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = a[l];
id[rt] = l;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
pushup(rt);
}
void query1(int val,int L,int R,int l,int r,int rt){
if(l==r){
if(mmax[rt]>val) cur = min(cur,id[rt]);
return;
}
int mid = l+r>>1;
if(L<=l && r<=R){
if(mmax[rt<<1]>val) query1(val,L,R,lson);
else if(mmax[rt<<1|1]>val) query1(val,L,R,rson);
return;
}
if(L<=mid) query1(val,L,R,lson);
if(mid<R) query1(val,L,R,rson);
}
void query2(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
if(mmax[rt]>a[cur]) cur = id[rt];
return;
}
int mid = l+r>>1;
if(L<=mid) query2(L,R,lson);
if(mid<R) query2(L,R,rson);
}
}st;
int dl[maxn],dr[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
rep(i,1,n+1) scanf("%d",a+i);
st.build(1,n,1);
int mx = 0;
memset(dr,0,sizeof(dr));
memset(dl,0,sizeof(dl));
rep(i,1,n+1){
if(a[i]>mx){
mx = a[i];
dl[i] = dl[i-1]+1;
}else{
dl[i] = dl[i-1];
}
}
per(i,1,n+1){
st.cur = n+1;
st.query1(a[i],i,n,1,n,1);
if(st.cur>n) st.cur = 0;
dr[i] = dr[st.cur]+1;
}
while(m--){
int p,q;scanf("%d%d",&p,&q);
int ans = 0; st.cur = 0;
if(p>1) st.query2(1,p-1,1,n,1);
ans += dl[st.cur];
if(q > a[st.cur]) ans ++;
if(q <= a[st.cur]) q = a[st.cur];
st.cur = n+1;
if(p<n) st.query1(q,p+1,n,1,n,1);
if(st.cur<=n) ans += dr[st.cur];
printf("%d\n",ans);
}
}

return 0;
}

[hdoj6376]度度熊剪纸条

度度熊剪纸条

题意

将一段01的序列分成$k$段,将他们重新拼接,问拼接成的纸条中前导0最多有多少个。

  • 拼接不可以改变方向。

题解

我模拟下来就是我们可以将这段序列分成三部分,

比如

11111/0/111/0/1111/0/11111

最前方的1部分和最后方的1部分和中间的1部分。

如果想将中间的1放在前面就必须剪两次,前方和后方的只需要1次。

模拟的话。

  • 我们首先如果第一段不剪,那么就是从后面的中间1和后方1选择,中间1需要剪两次,后方1只要剪一次。

  • 如果第一段剪掉,那么就是选择最大的,在他前面切一刀,把它当做最后的处理,其余的是前面的和后面的剪一刀和中间的剪两刀。

如果$k==0$特殊处理一下。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const int maxn = 1e4+100;
char s[maxn];
int ve[maxn];
int solve(){
bool flag = 0;
int cnt = 0;
int l = 0,r = 0;
int ans = 0;
int j = 0;
int st = 0,ed = n-1;
while(s[st]==1&&st<n)st++;
l = st;
while(s[ed]==1&&st<=ed) ed--;
r = n-ed-1;
rep(i,st,ed+1){
if(s[i] == 1) cnt++;
if(s[i] == 0 && cnt){
ve[++j] = cnt;
cnt = 0;
}
}
if(k==0) return l;
sort(ve+1,ve+j+1);
while(k>2 && j>=1){
ans += ve[j--];
k-=2;
}
if(k==1){
ans += max(l+r,ve[j]);
}else{
ans += max(l+r,max(l+ve[j],r+ve[j]));
}
return ans;
}
char temp[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&k)){
scanf("%s",s);
rep(i,0,n) s[i] -= '0';
printf("%d\n",solve());
}

return 0;
}

[hdoj4628]Pieces

HDU - 6071

题意

将一个字符串每次减少一个子回文串,例子avdffd可以减少dd,就是subsequence。问最少减少几个回文子串可以使得字符串消失。

题解

因为数据量只有16,所以是状压dp。

将每个字符串的位置状态压缩,之后再将回文子串先预处理出来,每次都判断一下是否可以减少回文子串,之后就是状压dp的基本操作了。


有一个检验是否可以减去的好方法

1
2
3
if((S&x)==x)
dfs(S^x);
//表示了x是可以减掉的。

之后预处理的时候将状压的值进行check更加方便。

好久没做状压dp了,居然可以return dp[]这样做,惊奇!

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
char s[30];
int len;
int vis[1<<18];
bool check(int x){
char str[20] = "";int cnt = 0;
rep(i,0,len){
if(((x>>i)&1)==1)
str[cnt++] = s[i];
}
rep(i,0,cnt/2){
if(str[i] != str[cnt-i-1]) return false;
}
return true;
}
int Set[1<<18];
int tot;
int dfs(int S){
if(vis[S]<INF) return vis[S];
rep(i,0,tot) if((S&Set[i]) == Set[i]){
vis[S] = min(dfs(S^Set[i]),vis[S]);
}
return ++vis[S];
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);len = strlen(s);
tot = 0;
int S = (1<<len) - 1;
memset(vis,127,sizeof(vis));
vis[0] = 0;
rep(i,1,S+1){
if(check(i)) Set[tot++] = i;
}
printf("%d\n",dfs(S));
}

return 0;
}

树形dp5题连做

树形dp,3天搞定

A - Information Disturbing

题意

对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求

  • 每条边带权重,切掉的边权重和不大于$m$
  • 切掉的每条边都不能大于一个$ans$

问$ans$最小是多少?

题解

二分+树形dp


+1 ans初始化-1

看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断

1
2
3
4
if(G[head[u]].to == father) 
该节点是叶节点 //在双向边的时候适用
if(head[u]==-1)
该节点是叶节点 //在单向边的时候适用

ac代码

[HDOJ5592] ZYB's Premutation

[HDOJ5592] ZYB’s Premutation

题意

ZYB有一个序列所有的逆序数前缀和,$a_1,a_2,a_3,…,a_n$,他们各个都表示从1到$i$的逆序数的前缀和。

题解

树状数组+二分

首先我们可以倒着看,对于最后一个数字,他的逆序数减前面的逆序数就代表着前面大于他的个数。所以我们就可以把问题转化为,已知数字$a_i$在前$i$个中的位置,求$a_i是多少。

我们可以用树状数组来维护,$sum(i)$表示到$i$代表着$i$是第几个数字,每当一个数字用过之后,他后面的数字都要-1,因为他们的排序相当于减少了一个,第四个数字变成第三个数字。


+n 没有想到这个序列是单调的,所以可以二分。居然想的是怎么让整个数组往前挪。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 1000;
int T,n;
int a[maxn],b[maxn],ans[maxn],bit[maxn];
int lowbit(int x){
return x&-x;
}
int add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int query(int x){
int s = 0;
for(int i=x;i;i-=lowbit(i)){
s += bit[i];
}
return s;
}
int solve(int l,int r,int x){
int ans = 0;
while(l<=r){
int mid = l+r>>1;
int temp = query(mid);
if(temp >= x){
r = mid-1;
ans = mid;
}else{
l = mid+1;
}
}
return ans;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(bit,0,sizeof(bit));
memset(ans,0,sizeof(ans));
rep(i,1,n+1) add(i,1);
rep(i,1,n+1) scanf("%d",a+i);
rep(i,1,n+1) b[i] = a[i] - a[i-1];
per(i,1,n+1){
int pos = i-b[i];
ans[i] = solve(1,n,pos);
add(ans[i],-1);
}
rep(i,1,n+1){
printf("%d%c",ans[i],i==n?'\n':' ');
}
}
return 0;
}

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online

The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online(青岛网络赛)

B.Red Black Tree

题意

题解

ac代码

J.Press the Button

题意

题解

ac代码

H Traveling on the Axis

题意

BOB走在$[1,n]$的路上,每两个点中间都有一个红绿灯,每一秒钟,

  • BOB先观察红绿灯是否绿,绿就走,红就停。
  • 红灯变绿,绿灯变红

$t(p,q)$就是$p$走到$q所需要的时间。

问: BOB从 $\sum^{n-1}{p=0} \sum{q=p+1}^nt(p,q)$的时间总和。

题解

对于第$i$个单独的红绿灯我们可以证明他对答案的贡献是

​ $(i)(len-i+1)(t(i))$

我们对于两个灯进行分析。

01 第一个零要2s,第二个一要1s

10 第一个一要1s,第二个零要1s

00 第一个零要2s,第二个一要2s

11 第一个一要1s,第二个一要2s

综上可以发现,

  • 该灯初始为0,那么他当头的时候贡献为2,如果不当头那么他的贡献就为1,除非跟前者相同。
  • 该灯初始为1,那么他和前一个灯相同时贡献为2,就算变成0了,不在头上的话贡献也为1.

我他妈sb了,不应该看着一段一段的区间,应该把红绿灯作为每一次状态的扩展,从红绿灯这$n$个出发开始计算,不应该考虑一个一个的单位为1的区间。

AC代码

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
// CSL 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
char s[N];
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
ll ans = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) ans += 1LL * (i + 1) * (n - i);
for (int i = 0; s[i]; i++)
{
if (s[i] == '0') ans += n - i;
if (i && (s[i] == s[i - 1])) ans += 1LL * i * (n - i);
//要跟包含前者的可能,要两个相同才能这么加。
}
printf("%lld\n", ans);
}
}
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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e5 + 10;
char s[maxn];
int main(){
#ifdef LOCAL
freopen("h.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);
int len = strlen(s);
ll ans = 0; ll w = 0;
if(s[0]=='1') ans = w = 1;
else ans = w = 2;
rep(i,1,len){
if(s[i]==s[i-1]) w += i*2;
else w += i*1;
if(s[i]=='1') w += 1;
else w += 2;
ans += w;
}
printf("%lld\n",ans);
}

return 0;
}

reference:

https://blog.csdn.net/tianyizhicheng/article/details/82728350

ACM-ICPC 2018 徐州赛区网络预赛

ACM-ICPC 2018 徐州赛区网络预赛

A. Hard to prepare

题意

$n$个人围成环,每个人可以选择$[0,2^k-1]$中的一个数字,要求相邻两人不能同或为0。

题解

递归。

可以YY出,第一个人有$2^k$种选择,之后第2到第$n-1$个人有$2^k-1$种选择,最后一个人可能可以选$2^k-2$,也可能可以选$2^k-1$。这取决于倒数第二个人是否跟第一个人选一样的。这时候我们就可以加上如果第一个人和倒数第二个人选择相同,并且,最后一个人多选了那$2^k-1-(2^k-2)$种,那么他们三个点变成一个点来选择了。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const ll mod = 1e9+7;
ll pow3(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
ll k2,kk2,kk1;
ll solve(int n,int k){
if(k==1) return 2;
if(n==1) return k2;
if(n==2) return k2*kk1%mod;
ll res = (k2*kk2%mod)*pow3(kk1,n-2)%mod;
res = (res+solve(n-2,k))%mod;
return res;
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
k2 = pow3(2,k);
kk1 = (k2-1+mod)%mod;
kk2 = (k2-2+mod)%mod;
printf("%lld\n",solve(n,k));
}

return 0;
}

B.BE,GE or NE

题意

两个人玩游戏,给出$[0,3]$个选项和一个$m$初始值,两个人依次选择,有以下三种选择

  • 选择将值$+a$
  • 选择将值$-b$
  • 选择将值倒过来 $m=-m$

两个人一个想将值变大,一个想让值变小,两个人都知晓所有情况和选项,在最优情况下,问谁赢。

题解

博弈论dp+记忆化搜索

因为数据量很小,范围也在200之间,所以记忆化状态回复的很多。

$dp[pos][val]$表示在pos位置数值是val,之后dp代表的是最优可以赢还是输还是平,分别用2,1,0代表。

之后对于边界值要处理一下。数组存不了负值,我们统一加100处理。


妈的。我看到这个以为是纯博弈论直接人傻了。之后想着能不能记忆化搜索,但是看到$n=1000$还以为他喵的会爆,但是这道题的情况限制在范围$-100到100$,所以情况很少。所以可以直接记忆化,不过对于答案的选择和状态转移我可能还是不会太轻松地做出来,带int的dfs我还是不怎么熟悉,这按道理应该是算是博弈论dp了。从最优状态转移到最优状态。

AC代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int n,m,k,l;
const int maxn = 1e3 + 10;
int a[maxn],b[maxn],c[maxn];
int dp[maxn][220];
// op
int dfs(int pos,int val){
if(pos == n){
if(val >= k){
return 2;
}else if(val > l){
return 1;
}else{
return 0;
}
}
if(dp[pos][val] != -1) return dp[pos][val];
if(pos%2==0){
int res = 0;
int mmin = min(200,val+a[pos]);
int mmax = max(0,val-b[pos]);
if(a[pos]) res = max(res,dfs(pos+1,mmin));
if(b[pos]) res = max(res,dfs(pos+1,mmax));
if(c[pos]) res = max(res,dfs(pos+1,200-val));
return dp[pos][val] = res;
}else{
int res = 2;
int mmin = min(200,val+a[pos]);
int mmax = max(0,val-b[pos]);
if(a[pos]) res = min(res,dfs(pos+1,mmin));
if(b[pos]) res = min(res,dfs(pos+1,mmax));
if(c[pos]) res = min(res,dfs(pos+1,200-val));
return dp[pos][val] = res;
}
}
int main(){
#ifdef LOCAL
freopen("b.in","r",stdin);
#endif // LOCAL
rep(i,0,maxn) rep(j,0,220) dp[i][j] = -1;
scanf("%d%d%d%d",&n,&m,&k,&l);
l += 100; k += 100; m += 100;
rep(i,0,n){
scanf("%d%d%d",a+i,b+i,c+i);
}
int op = dfs(0,m);
if(op==2) puts("Good Ending");
else if(op==1) puts("Normal Ending");
else puts("Bad Ending");
return 0;
}

[hdoj1540]Tunnel Warfare

Tunnel Warfare

题意

在一条线上有二种操作

  • 删掉一个点
  • 恢复一个点

求某一个点和与之相连点的个数。

题解

线段树设左右标志或者是树状数组二分

HDOJ可以线段树+二分。


Cnm hdoj 多组数据不给提示

如果是树状数组500ms,线段树+二分1500ms。

POJ卡了线段树+二分。HDOJ没有写多组输入害得我WA成sb了。

垃圾HDOJ还造假数据,毁坏多个碉堡。也是服了。

WA代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int sum[maxn<<3],vis[maxn],last[maxn];
int n,q;
void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
sum[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
pushup(rt);
}
void update(int val,int p,int l,int r,int rt){
if(l==r && l==p){
sum[rt] = val;
return;
}
int mid = l+r>>1;
if(p <= mid) update(val,p,lson);
if(mid < p) update(val,p,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[rt];
}
int mid = l+r>>1;
int ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
bool check(int l,int r){
if(query(l,r,1,n,1) == r-l+1) return true;
return false;
}
int solve1(int l,int r,int rt){
int mid;int st = n;
while(l<=r){
mid = l+r>>1;
if(check(mid,r)) r = mid-1,st = mid;
else l = mid+1;
}
return st;
}
int solve2(int l,int r,int rt){
int mid ;int ed = n;
while(l<=r){
mid = l+r>>1;
if(check(l,mid)) l = mid+1,ed = mid;
else r = mid-1;
}
return ed;
//cout<<ed<<' ';
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&q)){
build(1,n,1);
rep(i,1,n+1) vis[i] = 1;
int top = 0;
while(q--){
char op[20];
scanf("%s",op);
if(op[0] == 'D'){
int x; scanf("%d",&x);
update(0,x,1,n,1);
last[top++] = x;
}else if(op[0] == 'R'){
int x =last[--top];
update(1,x,1,n,1);
}else{
int x;scanf("%d",&x);
if(query(x,x,1,n,1)==0){
puts("0");
continue;
}
printf("%d\n",solve2(x,n,x)-solve1(1,x,x)+1);
}
}
}

return 0;
}

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 5e4+20;
int bit[maxn];
int lowbit(int x){
return x&-x;
}
int query(int x){
int ans = 0;
for(int i = x;i;i-=lowbit(i)){
ans += bit[i];
}
return ans;
}
int query(int l,int r){
return query(r)-query(l-1);
}
void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int solve_left(int l,int r){
int mid = l+r>>1;int ans = r;
while(l<=r){
mid = l+r>>1;
if(query(mid,r)==r-mid+1) r = mid-1,ans = mid;
else l = mid+1;
}
return ans;
}
int solve_right(int l,int r){
int mid,ans = l;
while(l<=r){
mid = l+r>>1;
if(query(l,mid)==mid-l+1) l=mid+1,ans = mid;
else r = mid-1;
}
return ans;
}
int vis[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF){
stack<int> st;
memset(bit,0,sizeof(bit));
memset(vis,0,sizeof(vis));
rep(i,1,n+1) add(i,1);
while(m--){
char op[20];scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
st.push(x);
if(vis[x]) continue;
vis[x] = 1;
add(x,-1);
}else if(op[0]=='Q'){
int x;scanf("%d",&x);
if(query(x,x)==0) puts("0");
else printf("%d\n",solve_right(x,n)-solve_left(1,x)+1);
}else{
add(st.top(),1);
vis[st.top()] = 0;
st.pop();
}
}
}

return 0;
}

[kuangbin带你飞7]线段树

kuangbin带你飞7

前言

作为一名acm选手,不能连线段树都不会,练就完事了。而且我越发觉得在赛场上不能卡机,中档题才是区分牌子的题目。只有慢慢思索的题目才能真正地提高自己,立下一个flag,每十天完成一个kuangbin专题。现在时间9/6。必须在9/16完成这个线段树专题,就算是困死也得完成。

感想

  1. 左右区间还是注意一下,保不准出题人恶趣味。

  2. 初始化不能想当然$n$多大树多大,有可能他是一个范围,$n$只是代表着式子的个数罢了。

  3. 数组居然还是又一次忘记开4倍。

  4. lazy数组忘记初始化,或者lazy可以为0但是还是初始化为0了。

A.敌兵布阵

题意

这如果我没有记错,应该是人生中第一个线段树题目,很是经典。单点修改,区间查询。

题解

线段树。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
int T,n;
int sum[maxn<<2],lazy[maxn<<2],a[maxn];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt]){
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt]*(len/2);
sum[rt<<1|1] += lazy[rt]*(len-len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
sum[rt] = a[l];
return ;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
sum[rt] += val*(r-l+1);
return ;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return sum[rt];
pushdown(rt,r-l+1);
int mid = l+r>>1;
int ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d",&n);
rep(i,1,n+1) scanf("%d",a+i);
build(1,n,1);
char op[20];
printf("Case %d:\n",test_case);
while(scanf("%s",op) && op[0]!='E'){
if(op[0]=='A' || op[0] =='S'){
int l,val;scanf("%d%d%d",&l,&val);
if(op[0] == 'A') update(val,l,l,1,n,1);
else update(-val,l,l,1,n,1);
}else{
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",query(l,r,1,n,1));
}
}
}

return 0;
}

B.I Hate It

题意

单点修改,区间最值。

题解

线段树。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 10;
int n,m;
int mmax[maxn<<2],a[maxn];
void pushup(int rt){
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = a[l];
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int p,int l,int r,int rt){
if(l==r && l==p){
mmax[rt] = val;
return;
}
int mid = l+r>>1;
if(p <= mid) update(val,p,lson);
if(mid < p) update(val,p,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return mmax[rt];
int mid = l+r>>1;
int ans = 0;
if(L <= mid) ans = max(ans,query(L,R,lson));
if(mid < R) ans = max(ans,query(L,R,rson));
return ans;
}
int main(){
#ifdef LOCAL
freopen("b.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
rep(i,1,n+1) scanf("%d",a+i);
build(1,n,1);
rep(i,0,m){
char op[20];int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[0] == 'Q'){
printf("%d\n",query(x,y,1,n,1));
}else{
update(y,x,1,n,1);
}
}
}
return 0;
}

C - A Simple Problem with Integers

题意

区间查询,区间修改。

题解

线段树

lazy需也要开两倍

AC代码

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
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
ll sum[maxn<<2],a[maxn],lazy[maxn<<2];
int n,q;
void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,ll len){
if(lazy[rt]){
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt]*(len-len/2);
sum[rt<<1|1] += lazy[rt]*(len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
if(l==r){
sum[rt] = a[l];
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(ll val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
sum[rt] += val*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("c.in","r",stdin);
#endif
scanf("%d%d",&n,&q);
rep(i,1,n+1) scanf("%lld",a+i);
build(1,n,1);
rep(i,0,q){
char op[20];int a,b,c;
scanf("%s",op);
if(op[0] == 'C'){
scanf("%d%d%d",&a,&b,&c);
update(c,a,b,1,n,1);
}else{
scanf("%d%d",&a,&b);
printf("%lld\n",query(a,b,1,n,1));
}
}
return 0;
}

D - Mayor’s posters

题意

贴线段,每次贴都会覆盖掉前面的线。问贴到最后能看到多少种不同的线。

题解

线段树+离散化

覆盖线段的范围是1e8,无法建树所以需要离散化,把线段长度按照排序的顺序重新赋值。由于有$2n$个长度所以记得$maxn$要开两倍。

区间修改,单点查询。

AC代码

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
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 20;
int vis[maxn],lx[maxn],rx[maxn],lazy[maxn<<2],mmax[maxn<<2];
int T,n;
void pushdown(int rt){
if(lazy[rt]){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
mmax[rt<<1] = mmax[rt<<1|1] = lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
mmax[rt] = 0;
return ;
}
int mid = l+r>>1;
build(lson); build(rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
mmax[rt] = val;
return ;
}
pushdown(rt);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
}
int query(int p,int l,int r,int rt){
if(l==r && l==p){
return mmax[rt];
}
int mid = l+r>>1;
pushdown(rt);
if(p <= mid) return query(p,lson);
if(mid < p) return query(p,rson);
}
int main(){
#ifdef LOCAL
freopen("d.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
vector<int>x;
rep(i,1,n+1){
int l,r;scanf("%d%d",lx+i,rx+i);
x.push_back(lx[i]);x.push_back(rx[i]);
}
sort(x.begin(),x.end());
x.erase(unique(x.begin(),x.end()),x.end());
rep(i,1,n+1){
lx[i] = lower_bound(x.begin(),x.end(),lx[i])-x.begin()+1;
rx[i] = lower_bound(x.begin(),x.end(),rx[i])-x.begin()+1;
}
int len = x.size();
build(1,len,1);
rep(i,1,n+1){
update(i,lx[i],rx[i],1,len,1);
}
memset(vis,0,sizeof(vis));
int ans = 0;
rep(i,1,len+1){
int x = query(i,1,len,1);
if(vis[x] == 0){
ans ++;
vis[x] = 1;
}
}
printf("%d\n",ans);
}
return 0;
}

E - Just a Hook

题意

区间修改,区间查询

题解

线段树

ac代码

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<cstring>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int sum[maxn<<2],a[maxn],lazy[maxn<<2];
int n,q,T;
void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt]){
lazy[rt<<1] = lazy[rt];
lazy[rt<<1|1] = lazy[rt];
sum[rt<<1] = lazy[rt]*(len-len/2);
sum[rt<<1|1] = lazy[rt]*(len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
sum[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
sum[rt] = val*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("e.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d%d",&n,&q);
build(1,n,1);
rep(i,0,q){
int l,r,val; scanf("%d%d%d",&l,&r,&val);
update(val,l,r,1,n,1);
}
printf("Case %d: The total value of the hook is %d.\n",test_case,query(1,n,1,n,1));
}
return 0;
}

F.Count the Colors

题意

在一条线上区间涂颜色。

问所有颜色出现的区间块的数量。

题解

线段树+懒惰标记

需要注意的是,$n$不代表着数据的范围,8000才是数据的范围,并且由于区块间有空隙,所以离散化还有点不好做。虽然数据也只有8000。注意的是初始化的范围要覆盖到8000,不能以为到$n$就好了。


+5 $n$当坐范围

+3 误以为build函数能够初始化所有的点,但其实是要memset(vis,-1,sizeof(vis));

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head -------------------------
const int maxn = 8e3+10;
int n;
int a[maxn<<2],lazy[maxn<<2],ans[maxn<<2],id[maxn<<2],vis[maxn<<2];
void pushdown(int rt){
if(lazy[rt]!=-1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
a[rt<<1] = a[rt<<1|1] = lazy[rt];
lazy[rt] = -1;
}
}
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
a[rt] = -1;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
a[rt] = val;
lazy[rt] = val;
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
void query(int l,int r,int rt){
if(l==r){
vis[l] = a[rt];
return;
}
int mid = l+r>>1;
pushdown(rt);
query(lson);
query(rson);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF){
build(1,8000,1);
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
memset(id,0,sizeof(id));
rep(i,1,n+1){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
if(l>=r) continue;
update(x,l+1,r,1,8000,1);
}
query(1,8000,1);
int last = -1;
//int i = 1;
rep(i,1,maxn){
while(vis[i]==-1) i++,last=-1;
if(i>=maxn) break;
if(vis[i] != last){
last = vis[i];
ans[vis[i]]++;
}
}
rep(i,0,8000+1){
if(ans[i]==0) continue;
printf("%d %d\n",i,ans[i]);
}
puts("");
}
return 0;
}

G.Balanced Lineup

题意

求区间最大值和最小值的差

题解

可以用ST表预处理,也可以用树状数组或者是线段树,线段树的常数比较大,但他们的复杂度均是$O(nlogn)$

AC代码

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<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+20;
int mmax[maxn],mmin[maxn];
int a[maxn];
int n,q;
int lowbit(int x){
return x&-x;
}
void update(int x){
for(int i=x;i<=n;i+=lowbit(i)){
mmax[i] = a[i];
mmin[i] = a[i];
for(int j=1;j<lowbit(i);j<<=1){
mmax[i] = max(mmax[i],mmax[i-j]);
mmin[i] = min(mmin[i],mmin[i-j]);
}
}
}
int query_min(int l,int r){
int res = INF;
while(r>=l){
res = min(a[r],res);
r--;
for(;r-lowbit(r)>=l;r-=lowbit(r))
res = min(mmin[r],res);
}
return res;
}
int query_max(int l,int r){
int res = -INF;
while(r>=l){
res = max(a[r],res);
r--;
for(;r-lowbit(r)>=l;r-=lowbit(r))
res = max(mmax[r],res);
}
return res;
}
int solve(int l,int r){
return query_max(l,r)-query_min(l,r);
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d%d",&n,&q);
rep(i,1,n+1) mmin[i]=INF,mmax[i]=-INF;
rep(i,1,n+1){
scanf("%d",a+i);
update(i);
}
while(q--){
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",solve(l,r));
}
return 0;
}

H.Can you answer the queries?

题意

区间数字根号,区间查询数字和。

题解

线段树+智力门槛

因为所有数字最多根号8次就会变成1。所以我们只需要处理一下当数字为1就不用再更新区间内的数了。


acm还是靠智力和眼力啊,我想了半天都没想出来什么数学方法,原来只需要看出规律和找到最关键的突破点就ok了。

+1超时忘记开4倍数组了。。

+1 虚伪的看到了提醒要注意l,r的大小关系,妈的,这都卡,是不是人啊。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int n,q;
ll sum[maxn<<2],mmax[maxn<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
ll x;scanf("%lld",&x);
mmax[rt] = sum[rt] = x;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int L,int R,int l,int r,int rt){
if(mmax[rt]==1) return;
if(l==r){
mmax[rt] = sqrt(mmax[rt]);
sum[rt] = sqrt(sum[rt]);
return;
}
int mid = l+r>>1;
if(L<=mid) update(L,R,lson);
if(mid<R) update(L,R,rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return sum[rt];
int mid = l+r>>1;
ll ans = 0;
if(L<=mid) ans += query(L,R,lson);
if(mid<R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int test_case = 1;
while(~scanf("%d",&n)){
build(1,n,1);
scanf("%d",&q);
printf("Case #%d:\n",test_case++);
while(q--){
int l,r,op;scanf("%d%d%d",&op,&l,&r);
if(l>r){
int temp = l;
l = r;
r = temp;
}
if(op==0){
update(l,r,1,n,1);
}else{
printf("%lld\n",query(l,r,1,n,1));
}
}
puts("");
}
return 0;
}

I Tunnel Warfare(前面写过了)

题意

题解

ac代码

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>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 5e4+20;
int bit[maxn];
int lowbit(int x){
return x&-x;
}
int query(int x){
int ans = 0;
for(int i = x;i;i-=lowbit(i)){
ans += bit[i];
}
return ans;
}
int query(int l,int r){
return query(r)-query(l-1);
}
void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int solve_left(int l,int r){
int mid = l+r>>1;int ans = r;
while(l<=r){
mid = l+r>>1;
if(query(mid,r)==r-mid+1) r = mid-1,ans = mid;
else l = mid+1;
}
return ans;
}
int solve_right(int l,int r){
int mid,ans = l;
while(l<=r){
mid = l+r>>1;
if(query(l,mid)==mid-l+1) l=mid+1,ans = mid;
else r = mid-1;
}
return ans;
}
int vis[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF){
stack<int> st;
memset(bit,0,sizeof(bit));
memset(vis,0,sizeof(vis));
rep(i,1,n+1) add(i,1);
while(m--){
char op[20];scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
st.push(x);
if(vis[x]) continue;
vis[x] = 1;
add(x,-1);
}else if(op[0]=='Q'){
int x;scanf("%d",&x);
if(query(x,x)==0) puts("0");
else printf("%d\n",solve_right(x,n)-solve_left(1,x)+1);
}else{
add(st.top(),1);
vis[st.top()] = 0;
st.pop();
}
}
}
return 0;
}

J.Assign the task

题意

dfs序+线段树模板题

题解

同上


+1 lazy数组没有初始化,没适应无build建树

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int T,n,clk;
int on[maxn],in[maxn],ind[maxn],a[maxn<<2],lazy[maxn<<2];
vector<int> G[maxn];
void init(){
clk = 0;
memset(on,0,sizeof(on));
memset(in,0,sizeof(in));
memset(ind,0,sizeof(ind));
memset(a,-1,sizeof(a));
memset(lazy,-1,sizeof(lazy));
rep(i,0,n+1) G[i].clear();
}
void dfs(int u,int fa){
for(auto v:G[u]){
if(v==fa) continue;
in[v] = ++clk;
dfs(v,u);
}
on[u] = clk;
}
void pushdown(int rt){
if(lazy[rt]!=-1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
a[rt<<1] = a[rt<<1|1] = lazy[rt];
lazy[rt] = -1;
}
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
a[rt] = val;
return ;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
int query(int p,int l,int r,int rt){
if(l==r && p==l) return a[rt];
int mid = l+r>>1;
pushdown(rt);
if(p<=mid) return query(p,lson);
else return query(p,rson);
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d",&n);
init();
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
G[v].push_back(u);
ind[u]++;
}
int root = 0;
rep(i,1,n+1) if(ind[i]==0){
root = i;
break;
}
in[root] = ++clk;
dfs(root,-1);
int q;scanf("%d",&q);
printf("Case #%d:\n",test_case);
while(q--){
char op[20];int x,y;
scanf("%s",op);
if(op[0]=='C'){
scanf("%d",&x);
printf("%d\n",query(in[x],1,n,1));
}else{
scanf("%d%d",&x,&y);
update(y,in[x],on[x],1,n,1);
}
}
}

return 0;
}

K.Transformation

题意

有四种操作。

  1. 将$[l,r]$区间的数字加上$val$.
  2. 将$[l,r]$区间的数字乘上$val$
  3. 将$[l,r]$区间的数字变成$val$
  4. 求区间$[l,r]$内所有数字$[1,2,3]$次方的和。

题解

线段树

对于线段树的懒惰标记和取模运算细节要求很高。

相信对于sum数组的转化大家都能够推得出来,但是关于pushdown的操作是另有玄机。

首先他的顺序很重要。得先将lazy[1]递推下去,也就是操作3把数字变成$val$,之后再进行乘法和加法的操作。对于乘法很重要的一点是你在lazy[2]标记递推的时候,其实你把子树中的加法也相当于乘了$val$,所以递推不仅要递推乘法标记,还要递推加法标记。


+3 更新Pushdown中你也要更新lazy数组的值

+1 更新的次序也有关系

+1初始化 有的要1.

+1 少写一个|1 rt[rt<<1|1]写成了rt<<1

+10000 有一个r-l+1写错了,下次写成 len 。不然很容易出错妈了个鸡

AC代码

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
165
166
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
template <typename T>
inline bool read (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return 0; //EOF
while (c != '-' && (c < '0' || c > '9') ) {
if((c = getchar()) == EOF) return 0;
}
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll maxn = 1e5 + 20;
const ll mod = 1e4 + 7;
ll pp[mod+20][4],sum[4][maxn<<2];
ll lazy[maxn<<2][4];
int n,m,x,y,val;
void init(){
memset(sum,0,sizeof(sum));
memset(lazy,0,sizeof(lazy));
rep(i,0,maxn){
lazy[i][2] = 1;
}
}
void pushup(int rt){
rep(i,1,4){
sum[i][rt] = (sum[i][rt<<1] + sum[i][rt<<1|1])%mod;
}
}
void pushdown(int rt,ll len){
if(lazy[rt][3]){
ll c = lazy[rt][3]%mod;
lazy[rt<<1][1] = lazy[rt<<1|1][1] = 0;
lazy[rt<<1][2] = lazy[rt<<1|1][2] = 1;
lazy[rt<<1][3] = lazy[rt<<1|1][3] = c;
sum[1][rt<<1] = c*(len-len/2);
sum[1][rt<<1|1] = c*(len/2);
sum[2][rt<<1] = pp[c][2]*(len-len/2)%mod;
sum[2][rt<<1|1] = pp[c][2]*(len/2)%mod;
sum[3][rt<<1] = pp[c][3]*(len-len/2)%mod;
sum[3][rt<<1|1] = pp[c][3]*(len/2)%mod;
lazy[rt][3] = 0;
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
}
}
if(lazy[rt][2]!=1){
ll c = lazy[rt][2]%mod;
rep(i,1,4){
sum[i][rt<<1] *= pp[c][i];
sum[i][rt<<1|1] *= pp[c][i];
}
rep(i,1,3){
lazy[rt<<1][i] = (lazy[rt<<1][i]%mod)*c%mod;
lazy[rt<<1|1][i] = (lazy[rt<<1|1][i]%mod)*c%mod;
}
lazy[rt][2] = 1;
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
}
}
if(lazy[rt][1]){
ll c = lazy[rt][1]%mod;
lazy[rt<<1][1] += c;
lazy[rt<<1|1][1] += c;
lazy[rt<<1][1] %= mod;
lazy[rt<<1|1][1] %= mod;
sum[3][rt<<1] += 1ll*3*sum[2][rt<<1]%mod*c%mod + c*c%mod*c%mod*(len-len/2)%mod + 3*sum[1][rt<<1]%mod*c%mod*c%mod;
sum[3][rt<<1|1] += 1ll*3*sum[2][rt<<1|1]%mod*c%mod + 3*sum[1][rt<<1|1]*c%mod*c%mod + c*c%mod*c%mod*(len/2)%mod;
sum[2][rt<<1] += 1ll*2*sum[1][rt<<1]%mod*c%mod + c*c%mod*(len-len/2)%mod;
sum[2][rt<<1|1] += 1ll*2*sum[1][rt<<1|1]%mod*c%mod + c*c%mod*(len/2)%mod;
sum[1][rt<<1] += c*(len-len/2);
sum[1][rt<<1|1] += c*(len/2);
lazy[rt][1] = 0;
}
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
lazy[rt<<1|1][i] %= mod;
lazy[rt<<1][i] %= mod;
}
}
void update(int op,ll c,ll L,ll R,ll l,ll r,ll rt){
if(L<=l && r<=R){
if(op==1){
sum[3][rt] += 1ll*3*sum[2][rt]*c%mod+1ll*3*sum[1][rt]*c%mod*c%mod+c*c%mod*c%mod*(r-l+1)%mod;
sum[2][rt] += sum[1][rt]%mod*c%mod*2%mod+c*c%mod*(r-l+1)%mod;
sum[1][rt] += 1ll*(r-l+1)*c%mod;
lazy[rt][1] += c;
lazy[rt][1] %= mod;
}else if(op==2){
rep(i,1,4) sum[i][rt] *= pp[c][i];
lazy[rt][2] *= c;
lazy[rt][2] %= mod;
lazy[rt][1] *= c;
lazy[rt][1] %= mod;
}else{
rep(i,1,4) sum[i][rt] = pp[c][i]*(r-l+1)%mod;
lazy[rt][3] = c;
lazy[rt][1] = 0;lazy[rt][2] = 1;
}
rep(i,1,4) sum[i][rt] %= mod;
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L<=mid) update(op,c,L,R,lson);
if(mid<R) update(op,c,L,R,rson);
pushup(rt);
}
ll query(int op,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[op][rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L<=mid) (ans += query(op,L,R,lson)%mod)%=mod;
if(mid<R) (ans += query(op,L,R,rson)%mod)%mod;
pushup(rt);
return ans%mod;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
//freopen("2.out","w",stdout);
#endif
rep(i,1,mod+1) pp[i][1] = i%mod;
rep(i,1,mod+1){
rep(j,2,4){
pp[i][j] = (ll)pp[i][j-1]*i%mod;
}
}
while(~scanf("%d%d",&n,&m)){
init();
rep(i,0,m){
int op;read(op); read(x);read(y);read(val);
if(op==4){
printf("%lld\n",query(val,x,y,1,n,1));
}else{
update(op,val,x,y,1,n,1);
}
}
}
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
#endif
return 0;
}

L - Vases and Flowers

题意

做过 在我之前博客里面有。

题解

做过


+2 忘记掉可能初始不能放在A点,所以要加入一个全局变量flag,初始化maxl。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,now,maxl,maxr,flag;
const int maxn = 5e4+20;
int sum[maxn<<2],lazy[maxn<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt] != -1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
sum[rt<<1] = lazy[rt]*(len-len/2);
sum[rt<<1|1] = lazy[rt]*(len/2);
lazy[rt] = -1;
}
}
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
sum[rt] = 0;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
pushup(rt);
}
void update1(int p,int l,int r,int rt){
if(now == 0) return;
int len = r-l+1;
if(sum[rt] == len) return;
if(l>=p && sum[rt] == 0 && len <= now){
now -= len;
sum[rt] = len;
lazy[rt] = 1;
if(flag == 0)
maxl = l,flag = 1;
maxr = max(maxr,r);
return;
}
pushdown(rt,len);
int mid = l+r>>1;
if(p<=mid) update1(p,lson);
update1(p,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = 0;
int temp = sum[rt];
sum[rt] = 0;
return temp;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
int ans = 0;
if(L<=mid) ans += query(L,R,lson);
if(mid<R) ans += query(L,R,rson);
pushup(rt);
return ans;
}
int main(){
#ifdef LOCAL
freopen("l.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
int m;scanf("%d%d",&n,&m);
build(1,n,1);
rep(i,0,m){
int op,x,y;scanf("%d%d%d",&op,&x,&y);
x++;
if(op==1){
now = y;
maxl = x;maxr = x;flag = 0;
update1(x,1,n,1);
if(now == y)
puts("Can not put any one.");
else
printf("%d %d\n",maxl-1,maxr-1);
}else{
y++;
printf("%d\n",query(x,y,1,n,1));
}
}
puts("");
}
return 0;
}

M - 约会安排

题意

对每一次查询寻找$val$长度的最前面空闲时间并占据他。

  • 如果是女神来查询,那么空闲的时间也包括基友的时间
  • 如果是基友来查询,那么只有空闲的时间可以选择
  • 如果想要学习$[l,r]$,那么$[l,r]$之间的时间都会被清空。

题解

线段树的区间合并。

这里由于要维护两个线段树,所以用结构体来构造树,不过确实使用结构体封装之后复用性高了很多。

  • 定义三个量$ll,rr,mm$分别表示从区间$[L,R]$最左边开始的最长长度和从区间最右边开始的最长长度和区间内横跨中点的最长长度。
  • 定义$maxlen$来表示区间内最长的长度来剪枝。

这样就可以更新了。

一棵树代表屌丝+女神占有的,一棵树代表女神占有的。

查询分为三种方向

  • 先查询左边开始的长度是否大于$val$,如果大于返回$L$,或者是递归左子树。
  • 再查询中间的部分长度是否大于$val$,如果大于返回$mid-rr[lc]+1$就是中点减掉从左半部分右边的长度。
  • 再查询递归右子树。

+1 区间合并中 更新父节点必须每个都更新,所以有时候你在return 之前也要更新一下。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head ----------------------------------------
const int maxn = 1e6+20;
int T,n,m;
struct sgt{
int maxlen[maxn<<2];
int ll[maxn<<2],rr[maxn<<2],mm[maxn<<2];
int lazy[maxn<<2];
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
ll[rt] = rr[rt] = 0;
mm[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
}
void init(){
lazy[1] = 1;
}
void pushup(int l,int r,int rt){
if(lazy[rt]>=0){
maxlen[rt] = ll[rt] = rr[rt] = mm[rt] = (lazy[rt]?(r-l+1):0);
}else{
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
ll[rt] = ll[lc];
if(ll[lc]==(mid-l+1)) ll[rt] += ll[rc];
mm[rt] = rr[lc] + ll[rc];
rr[rt] = rr[rc];
if(rr[rc] == r-mid) rr[rt] += rr[lc];
maxlen[rt] = max(maxlen[lc],max(maxlen[rc],mm[rt]));
}
}
void pushdown(int rt){
if(lazy[rt]>=0){
int lc=rt<<1,rc=rt<<1|1;
lazy[lc] = lazy[rc] = lazy[rt];
lazy[rt] = -1;
}
}
int query(int val,int l,int r,int rt){
pushup(l,r,rt);
//cout<<l<<' '<<r<<' '<<" ";
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
if(val>maxlen[rt]) return 0;
if(ll[rt] >= val) return l;
pushdown(rt);
pushup(rson);
int temp = query(val,lson);
if(temp) return temp;
if(mm[rt] >= val) return mid-rr[lc]+1;
return query(val,rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
pushup(l,r,rt);
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
else pushup(lson);
if(mid<R) update(val,L,R,rson);
else pushup(rson);
pushup(l,r,rt);
}
}all,ns;
char op[20];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
printf("Case %d:\n",test_case);
scanf("%d%d",&n,&m);
//all.build(1,n,1); ns.build(1,n,1);
all.init(); ns.init();
while(m--){
scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
printf("%d,let's fly\n",ans);
}else{
puts("fly with yourself");
}
}else if(op[0]=='N'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(!ans) ans = ns.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
ns.update(0,ans,ans+x-1,1,n,1);
printf("%d,don't put my gezi\n",ans);
}else{
puts("wait for me");
}
}else{
int x,y;scanf("%d%d",&x,&y);
all.update(1,x,y,1,n,1);
ns.update(1,x,y,1,n,1);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}

return 0;
}

Reference:https://www.cnblogs.com/DSChan/p/4861977.html

N.picture

题意

求多个矩形周长的并

题解

扫描线+线段树


这道题目没有离散化$X$坐标就可以做。而且例子也只有一个。。

ac代码

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 2e4+100;
struct node{
int lx,rx,y;
int f;
node(){}
node(int _lx,int _rx,int _y,int _f){
lx = _lx; rx = _rx; y = _y; f = _f;
}
bool operator<(const node &s) const{
return y<s.y;
}
}L[maxn<<2];
int sum[maxn<<2],lb[maxn<<2],rb[maxn<<2],seg[maxn<<2];
int flag[maxn<<2];
void pushup(int rt,int l,int r){
if(flag[rt]){
sum[rt] = r-l+1;
lb[rt] = rb[rt] = 1;
seg[rt] = 2;
}else if(l==r){
sum[rt] = lb[rt] = rb[rt] = seg[rt] = 0;
}else{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
lb[rt] = lb[rt<<1];
rb[rt] = rb[rt<<1|1];
seg[rt] = seg[rt<<1] + seg[rt<<1|1];
if(lb[rt<<1|1]&&rb[rt<<1]) seg[rt]-=2;
}
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
flag[rt] += val;
}else{
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
pushup(rt,l,r);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(~scanf("%d",&n)){
int cnt = 0;
int maxl = INF; int maxr = -INF;
rep(i,0,n){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
L[++cnt] = node(x1,x2,y1,1);
L[++cnt] = node(x1,x2,y2,-1);
maxl = min(maxl,x1);
maxr = max(maxr,x2);
}
sort(L+1,L+1+cnt);
int res = 0;
int last = 0;
rep(i,1,cnt+1){
update(L[i].f,L[i].lx,L[i].rx-1,maxl,maxr,1);
res += abs(sum[1]-last);
res += seg[1] * (L[i+1].y-L[i].y);
last = sum[1];
}
printf("%d\n",res);
}

return 0;
}

[hdoj5521]Meeting

Meeting

题意

将图分成$m$个块,每个块中的点到块中点的需要的时间为$E_i$。Bessie在点1,Elsie在点$n$,问他们在最短的时间走到可以到哪一个点会和。点可以在不同的块中。

题解

如果想要每个点都建边,无疑会爆空间。我们可以看出每个点都分配到几个块,而每个块又有几个点。那么我们可以将块看做点,连接着块中的点,这样每个块的边从$O(n^2)$变成了$O(n)$。


我tmWA了20发,就是因为以前都是将点做标记,但是这次是块也要做标记,不然每块会浪费很多时间。而且因为只要该点是最优的,那么该块也是最优的了(因为该点到该块的距离为0)。

AC代码

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
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define pb push_back
const int maxn = 1e5 + 10;
ll val[maxn];
ll cnt1[maxn],cnt2[maxn];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//head
int T,n,m;
ll ans[maxn];
int vis[maxn];
struct node{
ll t;
int id;
node(){}
node(ll a,int b):t(a),id(b){}
bool operator<(const node&x) const{
return t > x.t;
}
};
void bfs(int rt,ll *cnt,vector<int>B[],vector<int>E[]){
cnt[rt] = 0;
priority_queue<node > q;
memset(vis,0,sizeof(vis));
int use[maxn];
memset(use,0,sizeof(use));
q.push(node(0,rt));
while(!q.empty()){
int u = q.top().id; q.pop();
for(auto bk:B[u]){
if(use[bk]) continue;
use[bk] = 1;
for(auto v: E[bk]){
if(cnt[u]+val[bk]>=cnt[v]) continue;
cnt[v] = cnt[u] + val[bk];
q.push(node(cnt[v],v));
}
}
}
}
int main(){
#ifdef LOCAL
freopen("m.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
memset(cnt1,127,sizeof(cnt1));
memset(cnt2,127,sizeof(cnt2));
scanf("%d%d",&n,&m);
vector<int> B[n+1];
vector<int> E[m+1];
rep(i,1,n+1) B[i].resize(5);
rep(i,1,m+1) E[i].resize(5);
rep(i,1,m+1){
val[i] = read(); int s = read();
rep(j,0,s){
int x = read();
E[i].pb(x);B[x].pb(i);
}
}
bfs(1,cnt1,B,E); bfs(n,cnt2,B,E);
ll mmin = 0xfffffff;
rep(i,1,n+1){
ans[i] = max(cnt1[i],cnt2[i]);
if(ans[i]<mmin) mmin=ans[i];
}
if(mmin != 0xfffffff)
printf("Case #%d: %lld\n",test_case,mmin);
else{
printf("Case #%d: Evil John\n",test_case);
continue;
}
int cnt = 0;
ll res[maxn];
rep(i,1,n+1){
if(ans[i]==mmin)
res[cnt++] = i;
}
rep(i,0,cnt){
printf("%d%c",res[i],i==cnt-1?'\n':' ');
}
}
}

[nowcoder3]补题向

J.Coloring Tree

题意

给一棵树,每个节点从$[1,k]$选择一种颜色染。定义树的颜色值为两个相同颜色节点之间的最小值。问如果一棵树的颜色值为$D$,那么它有多少种染色方式。

题解

Reference:https://www.nowcoder.com/discuss/88556?type=101&order=0&pos=1&page=1

本地能过就是能过

谁能知道我为啥超时10%有重赏

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3 + 10;
int n,k,D,tot;
const ll mod = 1e9 + 7;
struct node{
int next,to;
}G[maxn<<1];
int head[maxn],vis[maxn],cnt[maxn];
void add(int u,int v){
G[tot].to = v;
G[tot].next = head[u];
head[u] = tot++;
}
ll ans = 1;
ll pow3(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
ll bfs(int rt,int ds){
queue<pII> q;
ll ans = 0;
q.push(make_pair(rt,0));vis[rt] = rt; ans = cnt[rt]%mod;
while(!q.empty()){
int u = q.front().fi; int d = q.front().se; q.pop();
if(d >= ds) break;
cnt[u]--;
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]==rt) continue;
vis[v] = rt;
q.push(make_pair(v,d+1));
}
}
return ans;
}
inline int read()
{
int x=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9'){if(c=='-')flag=1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return flag?-x:x;
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&k,&D);
rep(i,0,n-1){
int u,v; u =read();v= read();
add(u,v); add(v,u);
}
ll ans1 = 1,ans2 = 1;
rep(i,1,n+1) cnt[i] = k;
queue<int>q;
memset(vis,0,sizeof(vis));
q.push(1);int sign[maxn]={0};sign[1] = 1;
while(!q.empty()){
int u = q.front();q.pop();
ans1 = ans1*bfs(u,D)%mod;
for(int i= head[u];~i;i=G[i].next){
int v = G[i].to;
if(sign[v]) continue;
sign[v] = 1;
q.push(v);
}
}
rep(i,1,n+1) cnt[i] = k;
memset(sign,0,sizeof(sign));
q.push(1); sign[1] =1;
while(!q.empty()){
int u = q.front();q.pop();
ans2 = ans2*bfs(u,D+1)%mod;
for(int i= head[u];~i;i=G[i].next){
int v = G[i].to;
if(sign[v]) continue;
sign[v] = 1;
q.push(v);
}
}
printf("%lld\n",(ans1-ans2+mod)%mod);
return 0;
}

真丶AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3 + 10;
int n,k,D,tot;
const ll mod = 1e9 + 7;
struct node{
int next,to;
}G[maxn<<1];
int head[maxn],vis[maxn],cnt[maxn],dis[maxn][maxn];
void add(int u,int v){
G[tot].to = v;
G[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u,int fa,int rt){
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v == fa) continue;
dis[v][rt] = dis[u][rt]+1;
dfs(v,u,rt);
}
}
ll solve(int d){
queue<int>q;
rep(i,1,n+1) cnt[i] = k;
ll ans = 1;
q.push(1);
memset(vis,0,sizeof(vis));vis[1] = 1;
while(!q.empty()){
int u = q.front();q.pop();
ll res = 0;
rep(v,1,n+1) if(v!=u) cnt[v] -= (dis[u][v]<d);
if(cnt[u] <= 0) return 0;
ans = ans*cnt[u]%mod;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(dis[1][u]+1 == dis[1][v]){
q.push(v);
}
}
}
return ans;
}
inline int read()
{
int x=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9'){if(c=='-')flag=1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return flag?-x:x;
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&k,&D);
rep(i,0,n-1){
int u,v; u = read(); v = read();
add(u,v); add(v,u);
}
rep(i,1,n+1) dfs(i,-1,i);
printf("%lld\n",(solve(D)-solve(D+1)+mod)%mod);
return 0;
}

2018 ICPC南京赛区网络赛

ACM-ICPC 2018 南京赛区网络预赛

A. An Olympian Math Problem

题意

$S=1×1!+2×2!+⋯+(n - 1) \times (n-1)!(n−1)×(n−1)!$问$Smodn$是多少。

题解

思维题,打表题?答案就是$n-1$证明如下。

看到$n-1$很不爽,那就加一个$(n-1)!$就凑好了。

$S+1!+2!+…+(n-1)!=2!+3!+…+n!$

之后再减掉。

$S=n!-1!$那么对$n$取余$S modn=-1modn=n-1$搞定。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T;
ll n;
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
printf("%lld\n",n-1);
}
return 0;
}

B. The writing on the wall

E. AC Challenge

题意

做题目,要按照一定顺序做题目,每个题目有两个值$a,b$,表示做了题目后增加$t*a+b$。

题解

状态压缩+剪枝+拓扑排序。

因为$n$的数据量小于$20$所以可以使用状态压缩。

$S$表示已经做的题目。

$vs$数组存储已知做题的最大值。如果做同样的题值比较小就减掉。

AC代码

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 30;
struct noddde{
int next,to;
}G[maxn*maxn*3];
int head[maxn],ind[maxn];
ll a[maxn],b[maxn];
int cnt;
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
int n;
ll ans = 0;
ll vis[maxn];
ll vs[1<<22];
void dfs(int u,int t,ll temp,int S){
ans = max(ans,temp);
if(vs[S] > temp) return;
vs[S] = temp;
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
ind[v]--;
}
rep(i,1,n+1){
if(ind[i] == 0 && vis[i]==0){
vis[i] = 1;
dfs(i,t+1,temp+a[i]*t+b[i],S|(1<<i));
vis[i] = 0;
}
}
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
ind[v]++;
}
}
int main(){
#ifdef LOCAL
freopen("e.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n+1){
int s;scanf("%lld%lld%d",&a[i],&b[i],&s);
rep(j,0,s){
int u;scanf("%d",&u);
add(u,i);ind[i]++;
}
}
rep(i,1,n+1){
if(ind[i]==0){
ind[i]++;
add(0,i);
}
}
ans = 0;
dfs(0,1,0,0);
printf("%lld\n",ans);
return 0;
}

G. Lpl and Energy-saving Lamps

题意

一个人去给所有房间换灯泡,每个月都会获得$m$个灯泡,每个房间有$a_i$个灯泡,之后以能换就换的态度每个月从第一个房间开始换,没有能换的房间就停止,把灯泡留到下一个月。换过灯泡就不用再换了。问给定月份中已经换好的房间数和当月剩下的灯泡数。

题解

线段树维护一个区间最小值。

由于线段树遍历是从前往后的,就不用担心顺序问题。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int day[maxn],remain[maxn];
int a[maxn],Min[maxn<<2],ask[maxn];
int n,m,now,ans;
void pushup(int rt){
Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
Min[rt] = a[l];
return;
}
int mid = (l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int l,int r,int rt){
if(Min[rt] > now) return;
if(l==r){
now -= Min[rt];
ans ++;
Min[rt] = INF;
return;
}
int mid = (l+r)>>1;
update(lson);
update(rson);
pushup(rt);
}
int main(){
#ifdef LOCAL
freopen("g.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,1,n+1) scanf("%d",a+i);
int maxq = 0;int q;
scanf("%d",&q);
rep(i,0,q){
scanf("%d",ask+i);
maxq = max(maxq,ask[i]);
}
build(1,n,1);
rep(i,1,maxq+1){
now += m;
update(1,n,1);
day[i] = ans;remain[i] = now;
}
rep(i,0,q){
printf("%d %d\n",day[ask[i]],remain[ask[i]]);
}

return 0;
}

I. Skr

题意

给定一个由数字构成的字符串,$n\leq 2000000$。问回文串加起来有多少?

题解

两种做法:

  1. 马拉车+hash
  2. 回文树+dfs

AC代码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
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define ULL unsigned long long
#define ll long long
const int maxn=4000000+40;
const int mod=1e9+7;
ULL P = 1313131;
ULL sqr[maxn/2],has[maxn/2],V[maxn];
ll ha[maxn/2],tmp[maxn/2];
int Laxt[maxn],Next[maxn],cnt=0;

const int MOD = 2000007;

bool _insert(ULL Now)
{
int u=Now%MOD;
for(int i=Laxt[u];i;i=Next[i]){
if(V[i]==Now) return true;
}
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
V[cnt]=Now;
return false;
}
ll ans=0;
void _hash(int x,int y){
ULL Now=has[y]-has[x-1]*sqr[y-x+1];
if(!_insert(Now))
{
ans+=((ha[y]-ha[x-1]*tmp[y-x+1]%mod)%mod+mod)%mod;
ans%=mod;
}
}
int r[maxn];
char c[maxn];
void _malacher()
{
int R=0,Mid=0,Len;

scanf("%s",c+1);
Len=strlen(c+1);
sqr[0]=tmp[0]=1;
has[0]=ha[0]=0;
for(int i=1;i<=Len;i++){
sqr[i]=sqr[i-1]*P;
has[i]=has[i-1]*P+c[i];
tmp[i]=tmp[i-1]*10%mod;
ha[i]=(ha[i-1]*10+c[i]-'0')%mod;
}

for(int i=1;i<=Len;++i) {
_hash(i,i);
if(R>i) r[i]=min(r[2*Mid-i],R-i);
while(i+r[i]+1<=Len&&c[i+r[i]+1]==c[i-r[i]-1]){
_hash(i-r[i]-1,i+r[i]+1);
r[i]++;
}
if(i+r[i]>R) {
R=i+r[i];
Mid=i;
}
}

cnt=0;Mid=0;R=0;
memset(Laxt,0,sizeof(Laxt));
memset(r,0,sizeof(r));
for(int i=2;i<=Len;++i) {
if(R>i) r[i]=min(r[2*Mid-i],R-i+1);
while(i+r[i]<=Len&&c[i+r[i]]==c[i-r[i]-1]) {
_hash(i-r[i]-1,i+r[i]);
++r[i];
}
if(i+r[i]-1>R) {
R=i+r[i]-1;
Mid=i;
}
}
printf("%lld\n",ans);
}
int main()
{
_malacher();
return 0;
}

AC代码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
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int MAXN=2005005;
const ll MOD=1000000007ll;

ll pow(ll a,ll b){
ll t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%MOD;
y=y*y%MOD; b=b>>1;
}
return t;
}

int len[MAXN];
int nxt[MAXN][15];
int fail[MAXN];
int num[MAXN];
int cnt[MAXN];
int last;
int S[MAXN];
int tot;
int N;

int new_node(int l){
cnt[tot]=0;
num[tot]=0;
len[tot]=l;
return tot++;
}

void init_tree(){
tot=0;
new_node(0);
new_node(-1);
last=0;
N=0;
S[N]=-1;
fail[0]=1;
}

int get_fail(int x){
while(S[N-len[x]-1]!=S[N])
x=fail[x];
return x;
}

void add_char(int c){
c-='0';
S[++N]=c;
int cur=get_fail(last);
if(!nxt[cur][c]){
int now=new_node(len[cur]+2);
fail[now]=nxt[get_fail(fail[cur])][c];
nxt[cur][c]=now;
num[now]=num[fail[now]]+1;
}
last=nxt[cur][c];
cnt[last]++;
}


ll jans=0;
ll oans=0;

void dfs1(int x,ll fa){
for(int i=1;i<=9;i++){
if(nxt[x][i]){
ll cur;
if(len[nxt[x][i]]==1){
jans+=i;
cur=i;
jans%=MOD;
}
else{
cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
jans=(jans+cur%MOD)%MOD;
jans%=MOD;
}
dfs1(nxt[x][i],cur%MOD);
}
}
}

void dfs2(int x,ll fa){

for(int i=1;i<=9;i++){
if(nxt[x][i]){
ll cur;
cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
oans=(oans+cur%MOD)%MOD;
dfs2(nxt[x][i],cur%MOD);
}
}
}


char str[MAXN];

int main(){
scanf("%s",str);
int N1 = strlen(str);
init_tree();
for(int i=0;i<N1;i++)
add_char(str[i]);
dfs1(1,0);
dfs2(0,0);
printf("%lld\n",(jans%MOD+oans%MOD)%MOD);
return 0;
}

L. Magical Girl Haze

题意

给定一个图,问从$1$走到$n$如果可以选择$k$条路为$0$,那么最短的路径是多少。

题解

分层图最短路+堆优化dijistra

每使用一次道路为0,就进入$step+1$的路径比较。比较好的dp思维。对于pair使用了一个小trick,负值就可以不用手写greater和重载小于了。但是现场赛应该还是手写node算了。

dp转移两种状态.

  • $dp[v][step+1] = min(dp[v][step+1],dp[u][step])$
  • $dp[v][step] = min(dp[v][step],dp[u][step]+val(u,v))$

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define mp make_pair
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int T,n,m,k,cnt;
struct node{
int to,next,val;
}G[maxn<<1];
int head[maxn];
ll dp[maxn][13],done[maxn][13];
void add(int u,int v,ll val){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].val = val;
head[u] = cnt++;
}
void dijstra(){
priority_queue<pair<ll,pair<int,int> > > pq;
pq.push(mp(0,mp(1,0)));
dp[1][0] = 0;
while(!pq.empty()){
int u = pq.top().se.fi;
ll dis = pq.top().fi;
int step = pq.top().se.se;
pq.pop();
if(done[u][step]) continue;
done[u][step] = 1;
if(u == n){
printf("%lld\n",-dis);return;
}
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;ll val = G[i].val;
if(step<k && !done[v][step+1] && dp[v][step+1]<dis){
dp[v][step+1] = dis;
pq.push(mp(dis,mp(v,step+1)));
}
if(!done[v][step] && dp[v][step]<dis+val){
dp[v][step] = dis+val;
pq.push(mp(dp[v][step],mp(v,step)));
}
}
}
}
void init(){
memset(head,-1,sizeof(int)*(n+2));
cnt = 0;
memset(done,0,sizeof(done));
rep(i,1,n+1) rep(j,0,k+1) dp[i][j] = -1e16;
}
int main(){
#ifdef LOCAL
freopen("l.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
init();
rep(i,0,m){
int u,v;ll val;scanf("%d%d%lld",&u,&v,&val);
add(u,v,-val);
}
dijstra();
}
return 0;
}

八数码问题

八数码问题

前提知识 康拓展开

用途

相当于hash存储序列,使用更加小的空间来存储排列。

公式

$X = a_n*(n-1)!+a_{n-1}(n-2)+…+a_10!$,$a_i$表示当前未出现的数字是排在第几个元素。$0 \leq a_i < i,1 \leq i \leq n$

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fac[maxn];
fac[0] = 1;
rep(i,1,max) fac[i] = fac[i-1]*i;
int cantor(){
int ans = 0;
rep(i,0,maxn){
int cnt = 0;
for(int k=i+1;k<maxn;k++){
if(vis[k]<vis[i]) cnt++;
}
ans += fac[n-i]*cnt;
}
return ans;
}

reference:https://blog.csdn.net/cyningsun/article/details/6797128

[hdoj4616] Game

Game

题意

给一颗树,已知每个点有权值和陷阱,你不能往回走,如果走过$c$个陷阱或者无路可走就结束,可以从任一点开始走,问能获得多少权值。

题解

树形dp。

$dp[i][j][0/1]$是在以$i$为终点,经过$j$个陷阱,$1$代表起点有陷阱,$0$代表起点没有陷阱。
转移方程

  • $dp[u][j][0]=max(dp[u][j][0],dp[v][j][0]+val[v])$
  • $dp[u][j][1]=max(dp[u][j][1],dp[v][j][1]+val[v])$ 其中$j>0$因为起点有陷阱。

答案就是枚举每个根节点中子树进入和出去,特判一下链的组成

  • 起点为trap和起点不为trap组成,路线是从trap出发到另一个起点。
  • 起点都不是trap,那么这时候就要求$j_1+j_2<c$,因为路线走到一半就可能到了trap为$c$卡主,不能走了。
  • 两个起点都为trap,那么无所谓只需要$j_1+j_2 \leq c$就可以了。

心路历程:我一开始想的是二维dp转移方程,但是只能对一个根节点求值,因为子节点也有可能走根节点那条路径,没有想到树形dp对于求解问题这么灵活,答案不一定一定是dp数组中的元素,而可以是通过拼接数组中元素来构成答案。而且我想法是从根节点走到叶子节点,而不是从子树节点出发到根节点,还是too young啊。之后我拼接了自己的垃圾二维dp,发现因为在迷宫中你碰到$c$个陷阱之后就不能走了,但是我这个二维数组不能转移方程。我两条链拼接的时候会多加几个节点,因为左右两个链如果加起来为$c$之后,其中一条链到了trap点,就不能再走了。所以才要三维数组。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
struct node{
int next,to;
}G[maxn<<1];
int head[maxn],trap[maxn],val[maxn],dp[maxn][4][2];
int cnt,T,n,c,ans;
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
void init(){
cnt = 0;
memset(head,-1,sizeof(int)*(n+2));
memset(trap,0,sizeof(int)*(n+2));
memset(dp,0,sizeof(dp));
ans = 0;
}
void dfs1(int u,int fa){
dp[u][trap[u]][trap[u]] = val[u];
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(fa == v) continue;
dfs1(v,u);
for(int j=0;j<=c;j++){
for(int k=0;k+j<=c;k++){
ans = max(ans,dp[u][j][1]+dp[v][k][1]);
if(j) ans = max(ans,dp[u][j][1]+dp[v][k][0]);
if(k) ans = max(ans,dp[u][j][0]+dp[v][k][1]);
if(j+k<c) ans = max(ans,dp[u][j][0]+dp[v][k][0]);
}
}
for(int j=0;j+trap[u]<=c;j++){
dp[u][j+trap[u]][0] = max(dp[u][j+trap[u]][0],dp[v][j][0]+val[u]);
if(j) dp[u][j+trap[u]][1] = max(dp[u][j+trap[u]][1],dp[v][j][1]+val[u]);
}
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&c);
init();
rep(i,0,n) scanf("%d%d",&val[i],&trap[i]);
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(0,-1);
printf("%d\n",ans);
}
return 0;
}

[hdoj1556]Color the ball

Color the ball

题意

给定$n$次操作,吧$l,r$区间内+1,最后问每个点是多少。

题解

树状数组骚操作。

既然我单点更新只能更新一个点,那么我就更新$l$点加上1,之后$r+1$的点减1,那么我对于在区间中的点,求得就是他之前$l$出现的次数。

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 1e5 + 10;
int bit[maxn];
int lowbit(int x){return x&-x;}
void update(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int sum(int x){
int res = 0;
for(int i=x;i;i-=lowbit(i)){
res += bit[i];
}
return res;
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
while(scanf("%d",&n) && n){
memset(bit,0,sizeof(int)*(n+1));
rep(i,0,n){
int a,b;scanf("%d%d",&a,&b);
update(a,1);update(b+1,-1);
}
rep(i,1,n+1){
printf("%d%c",sum(i),i==n?'\n':' ');
}
}
return 0;
}

[hdoj4661] Message Passing

HDOJ 4661: Message Passing

题意

每个人拥有一个信息,也可以传给另外一个人他拥有的所有信息。现在给定一个联络树,问至少多少次传递可以让所有人拥有所有信息。

题解

可以看出至少要$(n-1)*2$次传递,因为每个人都至少传出一次,传入一次。而怎么可以最少传递呢?我们可以假设根为中心,先将所有信息传递给他,之后再从他传递回来。这里有一点很巧妙,传入和传出的可能种类是一样的,所以我们只需要计算一次传入,平方后便是该点为中心的方案数。

因为子节点必须先传给父节点信息以免漏传,所以传入的方案数是满足一种拓扑排序的。那么可以看我之前的一篇博客,计算拓扑排序对一个点进行计算的。

那么怎么从已知的父节点的$f(root)$传递到子节点$f(v)$呢?

$s(i)$表示以$i$为根节点的子节点数目。

我们假设子节点$s(v)=q$,那么如果子节点变成根节点后,子节点的$s(v)=n$,而原来的父节点$f(u)$变成了$n-q$个子节点数目了。于是通过公式

$f(root)=(f(root)-1)!/s(1)/s(2)/…/s(n)$

我们可以推导出$f(v) = f(u) * s(q)/s(n-q)$

搞定!

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e6 + 10;
const ll mod = 1e9 + 7;
struct node{
int to,next;
}G[maxn<<1];
int head[maxn],pre[maxn],q[maxn],vis[maxn];
ll f[maxn],sz[maxn],fac[maxn];
int cnt,n,T;
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
void init(){
cnt = 0;
rep(i,0,n+1){
head[i] = -1;
q[i] = 0;
f[i] = 1;
vis[i] = 0;
sz[i] = 0;
}
}
ll pow3(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
fac[0] = 1;
rep(i,1,maxn){
fac[i] = fac[i-1]*i % mod;
}
while(T--){
scanf("%d",&n);
init();
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
int l = 0,r = 0;vis[1] = 1;q[0] = 1;
while(l<=r){
int u = q[l++];
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]) continue;
pre[v] = u;
vis[v] = 1;
q[++r] = v;
}
}
per(i,1,n){
sz[q[i]] ++;
sz[pre[q[i]]] += sz[q[i]];
}
sz[1] ++;
ll cnt = fac[n];
rep(i,1,n+1) cnt = (cnt*pow3(sz[i],mod-2))%mod;
ll ans = 0;
ans = cnt*cnt %mod;f[1] = cnt;
rep(i,1,n){
ll cur = f[pre[q[i]]];
cur = cur*sz[q[i]] %mod;
cur = cur*pow3(n-sz[q[i]],mod-2)%mod;
f[q[i]] = cur;
ans = (ans + cur*cur%mod) % mod;
}
printf("%lld\n",ans);
}
return 0;
}

[UVA11174] Stand in a line

Stand in a line

题意

给定$n-1​$组关系,节点$a​$不能站在节点$b​$的前面,使得$n​$站成一行,问有多少种站法。

题解

树形dp + 组合数学

  1. 先建树,把没有父亲的节点都并入$0$节点,这样我们就有一颗完整的树了。
  2. 寻找规律,假设$f[i]$为以$i$为根节点的方案数,那么当每增加一颗子树的时候,他的组合是相当于有一个有拓扑排序方案和另外一个拓扑排序方案相组合。

我们可以这样想像,假设拓扑排序是不存在的,这些点的排序忽略,那么点可以看做是同样颜色的点,那么$x_1,x_2$个数的点排列的排列数为$(x_1+x_2)! /(x_1! * x_2!)$。而这些点其实是不一样的,他们有自身的拓扑排序顺序,于是答案就是$f(x_1) f(x_2) (x_1+x_2)!/(x1! * x_2!)$。

  1. 于是乎,我们先处理好每个节点的子节点(包含他自身),可以用拓扑排序直接做,不用递归,当然也可以递归,于是就是相当于从子树开始处理,把所有子树的节点数的阶乘除掉就可以了。

简单写一下从递推到通向。$c_i$表示是$root$的子节点,$s(i)$表示$i$节点的子节点数。

$f(root) = f(c1)f(c2)…f(c_k)*((s(root)-1)!/s(c_1)!/s(c_2)!/…/s(c_k)!)$

$f(c_1)=f(x_1)f(x_2)…f(x_z)*((s(c_1)-1)!/s(x_1)!/s(x_2)!/…/s(x_z)!)$

$s(c_1)和s(c_1-1)$可以约掉。而且到叶子节点$f(x_1)$都变成$1$了$s(x_1)$也变成了0.

$f(root)=(s(root)-1)!/s(1)/s(2)/…/s(n)$

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4 + 10;
const ll mod = 1e9 + 7;
int T,n,m,cnt;
struct node{
int to,next;
}G[maxn<<1];
int head[maxn],vis[maxn],sz[maxn],q[maxn],pre[maxn];
ll fac[maxn],f[maxn];
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
void init(){
cnt = 0;
rep(i,0,n+1){
vis[i] = 0;
head[i] = -1;
sz[i] = 0;
pre[i] = 0;
f[i] = 1;
}
}
ll pow3(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
a = a*a % mod;
b>>=1;
}
return res;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
fac[0] = 1;
rep(i,1,maxn){
fac[i] = fac[i-1]*i%mod;
}
while(T--){
scanf("%d%d",&n,&m);
init();
rep(i,0,m){
int u,v;scanf("%d%d",&v,&u);
add(u,v);vis[v] = 1;
}
rep(i,1,n+1) if(!vis[i]) add(0,i);
memset(vis,0,sizeof(vis));
vis[0] = 1;
int l=0,r=0; q[0] = 0;vis[0] = 1;
while(l<=r){
int u = q[l++];
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]) continue;
pre[v] = u;
vis[u] = 1;
q[++r] = v;
}
}
per(i,1,n+1){
sz[q[i]]++;
sz[pre[q[i]]] += sz[q[i]];
}
sz[0]++;
ll res = 0;
ll cnt = fac[n];
rep(i,1,n+1) cnt = cnt*pow3(sz[i],mod-2)%mod;
printf("%lld\n",cnt);
}
return 0;
}

Reference:https://blog.csdn.net/xiao_k666/article/details/78609562

[nowcoder2] 补题向

A.run

题意

白云可以跑$k$米或者走$1$米,但不能连续跑,问到达终点有多少种方案。

题解

1步2步上楼梯的加强版。典型的dp题。

  • $dp[i][0/1]$表示第$i$米最终是走还是跑的方案数

转移方程

  • $dp[i][0] = dp[i-1][1]+dp[i-1][0]$
  • $dp[i][1] = dp[i-1][0]$

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
ll dp[maxn][2];
ll pre[maxn];
int q;
ll k;
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
scanf("%d%lld",&q,&k);
dp[0][0] = 1;
rep(i,1,maxn){
if(i>=k){
dp[i][1] = dp[i-k][0] % mod;
}
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % mod;
pre[i] = pre[i-1] + (dp[i][0] + dp[i][1]) % mod;
pre[i] %= mod;
}
rep(i,0,q){
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",(pre[r]-pre[l-1]+mod)%mod);
}
return 0;
}

D.Money

题意

白云可以在一个商店里卖或者买商品,但白云只能带一个商品。问最多能赚多少钱在最少的交易下。

题解

dp

$dp[i][0]$表示在$i$最后一次交易是买入的最优值,$dp[i][1]$表示在$i$最后一次交易是卖出的最优值。转移方程。

  • 在$[1,i-1]$中卖出的最优值后在$i$买入或者不买入中取最好值。$dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i])$
  • 在$[1,i-1]$买入的最优值后在$i$卖出或者不卖中取最大值。$dp[i][1] = max(dp[i-1][1],dp[i-1][1]+a[i])$

只有由于要求最小交易次数,用pair<ll,int>来表示,第一个是金钱,第二个是交易次数,求最小次数,所以用min,并且把金钱变成负值,就可以相当于反向取最大了。

AC代码copydls的

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
ll a[maxn];
int T,n;
pair<ll,int> dp[maxn][2];
ll inf = 1ll<<60;
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,1,n+1) scanf("%lld",a+i);
dp[0][0] = make_pair(0,0);
dp[0][1] = make_pair(inf,0);
rep(i,1,n+1){
dp[i][0] = min(dp[i-1][0],make_pair(dp[i-1][1].fi-a[i],dp[i-1][1].se+1));
dp[i][1] = min(dp[i-1][1],make_pair(dp[i-1][0].fi+a[i],dp[i-1][0].se+1));
}
printf("%lld %d\n",-dp[n][0].fi,dp[n][0].se);
}
return 0;
}

贪心做法

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
vector<ll> a;
ll inf = 1ll<<50;
int n;
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;
scanf("%d",&T);
while(T--){
a.clear();
scanf("%d",&n);
a.push_back(inf);
rep(i,1,n+1){
ll x; scanf("%lld",&x);
a.push_back(x);
}
a.push_back(-1);
a.erase(unique(a.begin(),a.end()),a.end());
int len = a.size();
int down = -1;int cnt = 0;ll ans = 0;
rep(i,1,len-1){
if(a[i] <a[i-1] && a[i]<a[i+1]){
down = i;
}
if(a[i]>a[i+1]&&a[i]>a[i-1]){
cnt+=2;
ans += a[i]-a[down];
}
}
printf("%lld %d\n",ans,cnt);
}
return 0;
}

G transform

题意

白云要把一个数轴上的箱子中的产品搬到一个箱子点上,每个箱子都有一个价值,每次搬一个产品从箱子$a$到$b$上都要花费$2*abs(x[a]-x[b])$的力气,问在$T$总力气下,可以获得多少价值。

题解

二分+前缀数组

首先我们可以确定放箱子肯定是选择一定的区间内,因为每搬一个产品,肯定是越近消耗得越好,区间中只有左端点和右端点可能没搬完。

区间中,把所有产品集中到产品中位数,即改点左边的产品和右边的产品数量接近一致。便体力消耗最小。

难点

对于前缀数组的处理,我们用$suma$表示前缀产品和,$sumt$表示前缀对于假设运送产品到0点的和。$sumt[r]-sumt[l-1]$表示$[l,r]$移动到0点所需要的力气。

  • 那么如果我们将产品$[l,r]$运送到点$l$的消耗相当于把$[l,r]$中的元素都先运送到$l$中之后再把$l$中的元素送到0,进行减一哈,就是答案。$ans = sumt[r]-sumt[l-1]-(suma[r]-suma[l-1])*x[l]$
  • 将产品$[l,r]$运送到$r$点,相当于我们先把$[l,r]$转移到$r$上面之后再统一移动到0点。$ans+sumt[r]-sumr[l-1]=(suma[r]-suma[l-1])*x[r]$。

之后枚举每个$l$的每个$r$和每个$r$的每个$l$,枚举的时候固定$l$或者$r$是消耗完全的。

二分又一个小套路。

1
2
3
4
5
6
7
8
9
10
11
int l,r,mid,ans;
l = 1,r = maxn;
while(l<=r){
mid = (l+r)>>1;
if(check()){
ans = mid;l=mid+1; //避免了重复枚举Mid嘞。
}else{
r = mid-1;
}
}
printf("%d\n",ans);

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e5 + 10;
ll n,T;
ll x[maxn],a[maxn],suma[maxn],sumt[maxn];
ll getl(ll l,ll r){
return (sumt[r]-sumt[l-1]) - (suma[r]-suma[l-1])*x[l];
}
ll getr(ll l,ll r){
return (suma[r]-suma[l-1])*x[r] - (sumt[r]-sumt[l-1]);
}
bool check(ll ans){
ll l,r,mid,mida;
mida = ans/2+1;
l = r = mid = 1;
while(1){
while(r<=n && suma[r]-suma[l-1]<ans) r++;
while(mid<r && suma[mid]-suma[l-1]<mida) mid++;
if(r>n || mid>r) break;
ll temp = suma[r]-suma[l-1]-ans;
if(getr(l,mid)+getl(mid,r)-temp*(x[r]-x[mid]) <= T) return true;
l++;
}
l = r = mid = n;
while(1){
while(l>=1 && suma[r]-suma[l-1]<ans) l--;
while(mid>l && suma[r]-suma[mid-1]<mida) mid--;
if(l<1 || mid<l) break;
ll temp = suma[r] - suma[l-1] - ans;
if(getr(l,mid)+getl(mid,r)-temp*(x[mid]-x[l])<=T) return true;
r--;
}
return false;
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%lld%lld",&n,&T); T>>=1;
rep(i,1,n+1) scanf("%lld",x+i);
rep(i,1,n+1){
scanf("%lld",a+i);
suma[i] = suma[i-1] + a[i];
sumt[i] = sumt[i-1]+a[i]*x[i];
}
ll l,r,mid,ans;
l = 1;r = suma[n];
while(l<=r){
mid = (l+r)>>1;
if(check(mid)){
ans = mid;l = mid+1;
}else {
r = mid-1;
}
}
printf("%lld\n",ans);
return 0;
}

https://www.nowcoder.com/discuss/88268?type=101&order=1&pos=4&page=1

https://www.cnblogs.com/Flower-Z/p/9528057.html

H.travel

题意

给定一棵树,树上每个点有一个$val$,从树上走三次,不能走重复的点,问能获得的最大价值是多少。

题解

树形dp

$f[i][j]$表示以$i$为根的子树选了$j$条路径的最大权值和。(也是包含$i$点)

$g[i][j]$表示以$i$为根的子树选了$j$条路径加上一条包含$i$到根节点链的最大权值。

根据题意可以知道,如果我们$i$是竖直链,那么加入一个没有竖直链的。

  • $g[u][i] = max(g[u][i],f[v][x]+g[u][i-x])$
  • $g[u][i] = max(g[u][i],g[v][x]+f[v][i-x])$

如果$i$不是竖直链

  • $f[u][i]=max(f[u][i],f[v][x]+f[u][i-x])$

对不起,我编不下去了。就是瞎几把转移转移。能转移的状态就都转移了就行了。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e5 + 10;
struct node{
int to,next;
}G[maxn<<1];
int head[maxn];
ll f[maxn][4],g[maxn][4];
int n,cnt;
ll val[maxn];
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int u,int fa){
ll best[4][3] = {0}; ll temp[4][3] = {0}; ll last[4][3] = {0};
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==fa) continue;
dfs(v,u);
memset(temp,0,sizeof(temp));
memset(best,0,sizeof(best));
rep(x,0,4){
temp[x][0] = f[v][x];
temp[x][1] = g[v][x];
}
rep(x,0,4) rep(y,0,4-x) rep(p,0,3) rep(q,0,3-p)
best[x+y][q+p] = max(best[x+y][p+q],last[x][p]+temp[y][q]);
memcpy(last,best,sizeof(best));
}
rep(x,0,4) f[u][x] = max(f[u][x],best[x][0]);
rep(x,1,4) rep(y,0,3) f[u][x] = max(f[u][x],val[u]+best[x-1][y]);
rep(x,0,4) rep(y,0,2) g[u][x] = max(g[u][x],val[u]+best[x][y]);
}
int main(){
#ifdef LOCAL
freopen("h.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n+1) scanf("%lld",val+i);
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,-1);
printf("%lld\n",f[1][3]);
return 0;
}
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
//dls队伍代码,感觉比标程的容易懂一点。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N=410000;
vector<int> go[N<<1];
int n,w[N];
long long dp[N][4][2];
void treedp(int k1,int k2){
long long f[4][3];
long long pre[4][3];
memset(f,0x00,sizeof f);
for (int i=0;i<go[k1].size();i++){
int j=go[k1][i];
if (j!=k2){
treedp(j,k1);
memcpy(pre,f,sizeof f);
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
for (int c=0;c<3;c++)
for (int d=0;d<2;d++){
if (a+b>3||c+d>2) continue;
f[a+b][c+d]=max(f[a+b][c+d],pre[a][c]+dp[j][b][d]);
}
}
}
for (int i=0;i<4;i++){
dp[k1][i][0]=max(dp[k1][i][0],f[i][0]);
dp[k1][i][1]=max(dp[k1][i][1],f[i][1]+w[k1]);
if (i<3){
for (int a=0;a<2;a++)
for (int b=a+1;b<3;b++)
dp[k1][i+1][a]=max(dp[k1][i+1][a],f[i][b]+w[k1]);
}
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=1;i<n;i++){
int k1,k2; scanf("%d%d",&k1,&k2);
go[k1].push_back(k2);
go[k2].push_back(k1);
}
treedp(1,0);
long long ans=0;
for (int i=0;i<=3;i++) ans=max(ans,dp[1][i][0]);
printf("%lld\n",ans);
}

I.Car

题意

给定一个长度为$n$的正方形,在上面放车。车有如下性质

  • 速度一样
  • 不能改变方向
  • 起点都在矩阵的边缘

题解

3

奇数点特判一下,免得减了两次。题解也是经验所得,莫得证明。

AC代码

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 1e5 + 10;
int col[maxn],row[maxn];
int main(){
#ifdef LOCAL
freopen("i.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
int ans = 2*n;
if(n%2) ans--;
rep(i,0,m){
int x,y;scanf("%d%d",&x,&y);
row[x] = 1;col[y]=1;
}
rep(i,1,n+1){
if(row[i]) ans--;
if(col[i]) ans--;
}
if(n%2 && row[(n+1)/2]==1 && col[(n+1)/2]) ans++;
printf("%d\n",ans);
return 0;
}

J.Farm

题意

有一块$nm$的田,里面每一个土地都种$a[i][j]$的植物,每一种植物都有专属化肥,如果用错化肥就挂了。问在进行$T$次区间浇化肥后,挂了过多少个植物。

题解

我一开始想的是能不能统计一下前缀和,如果加入的肥料和是植物种类的倍数就是对的。但是需要随机算法,避免出题人卡。毕竟是假算法。还是乖乖按照标答思路来。。


将化肥按照二进制分为肯定对植物不好和可能对植物好。如

$a$植物代号是101010,那么检查每一位的时候,101011肯定对它不好,101110在检查前几位的时候可能对它好。

分辨植物是否死亡就看。

  • 他加入对它好的次数是不是总的施在他身上的次数。如果不等,说明有其他不好的施肥了,那他就挂了。
  • 他加入对它不好的次数存不存在,如果有,那他也挂了。

还有一个细节,定义数组更加环保和不可能爆空间。之后可以定义

1
2
3
int f[maxn];
#define id(x,y) (x-1)*m+y
// f[x][y] = f[id(x,y)]

还有一个细节就是前缀和你如果想要改变一个区间的前缀和,那就

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void add(int x1,int x2,int y1,int y2){
f[id(x1,y1)]++;
if(x2<n) f[id(x2+1,y1)]--;
if(y2<m) f[id(x1,y2+1)]--;
if(x2<n && y2<m) f[id(x2+1,y2+1)]++;
}
void gen(int *s){
for(int i = 1;<=n;i++){
for(int j=1;j<=m;j++){
if(i>1) s[id(x,y)]+=t[id(x-1,y)];
if(j>1) s[id(x,y)]+=s[id(x,y-1)];
if(i>1&&j>1) s[id(x,y)]-=s[id(x-1,y-1)];
}
}
}

AC代码

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
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int read() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
#define id(x,y) (x-1)*m+y
const int maxn = 1e6 + 1000;
int n,m,T;
int ans[maxn];
int s[maxn],x1[maxn],x2[maxn],y1[maxn],y2[maxn],kind[maxn],a[maxn];
void add(int k,int *f){
int a,b,c,d;
a=x1[k]; b=x2[k]; c=y1[k]; d=y2[k];
f[id(a,c)]++;
if(b<n) f[id(b+1,c)]--;
if(d<m) f[id(a,d+1)]--;
if(b<n&&d<m) f[id(b+1,d+1)]++;
}
void gen(int *f){
rep(i,1,n+1) rep(j,1,m+1){
if(i>1) f[id(i,j)] += f[id(i-1,j)];
if(j>1) f[id(i,j)] += f[id(i,j-1)];
if(i>1&&j>1) f[id(i,j)] -= f[id(i-1,j-1)];
}
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&T);
rep(i,1,n+1) rep(j,1,m+1) a[id(i,j)] = read();
rep(i,0,T){
x1[i]=read();y1[i]=read();x2[i]=read();y2[i]=read();kind[i]=read();
add(i,s);
}
gen(s);
rep(bit,0,21){
int f[maxn] ={0};
rep(i,0,T){
if(kind[i]>>bit & 1){
add(i,f);
}
}
gen(f);
rep(i,1,n+1) rep(j,1,m+1){
if(a[id(i,j)]>>bit & 1){
if(f[id(i,j)]!=s[id(i,j)])
ans[id(i,j)] = 1;
}else if(f[id(i,j)]){
ans[id(i,j)] = 1;
}
}
}
int res = 0;
rep(i,1,n+1) rep(j,1,m+1){
if(ans[id(i,j)]) res++;
}
printf("%d\n",res);
return 0;
}

偷窥到大佬还有用树状数组做的。先copy一下代码。

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
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e6+5;
const int MOD=(int)1e9+7;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
vector<int>p[MAXN];
vector<pii>ve[MAXN];
int n,m;
void add(int x,int y,int z){
for(int i=x;i<=n;i+=i&-i){
for(int j=y;j<=m;j+=j&-j){
p[i][j]+=z;
}
}
}
int query(int x,int y){
int re=0;
for(int i=x;i;i-=i&-i){
for(int j=y;j;j-=j&-j){
re+=p[i][j];
}
}
return re;
}
void add(int a,int b,int x,int y,int f){
add(a,b,f);
add(x+1,y+1,f);
add(a,y+1,-f);
add(x+1,b,-f);
}
void init(){
for(int i=1;i<=n;i++)p[i].resize(m+1);
}
struct node{
int a,b,x,y,k;
void scan(){
a=read();b=read();x=read();y=read();k=read();
}
};
vector<node>op[MAXN];

int main()
{
int q;
n=read();m=read();q=read();
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;x=read();
ve[x].push_back(mp(i,j));
}
}
for(int i=1;i<=q;i++){
node now;
now.scan();
op[now.k].push_back(now);
add(now.a,now.b,now.x,now.y,1);
}
int ans=0;
for(int i=1;i<=n*m;i++){
// debug(i);
if(!ve[i].empty()){
for(auto opi:op[i])add(opi.a,opi.b,opi.x,opi.y,-1);
for(auto x:ve[i])if(query(x.fi,x.se))ans++;
for(auto opi:op[i])add(opi.a,opi.b,opi.x,opi.y,1);
//debug(ans);
}
}
printf("%d\n",ans);
return 0;
}

[nowcoder1] J.Different Integers

[nowcoder1]J. Different Integers

题意

给出一段序列$a_1,a_2,…,a_n$,和$l,r$,求区间$[1,l],[r,n]$中不同数字的个数。

题解

树状数组+倍增序列

将查询的$l,r$转化为查询序列$[r,l+n]$中不同中数字的个数。

使用$pre[]$数组维护一个前缀不同种类数字的个数。针对查询就是$pre[r]-pre[l-1]$再加上同时出现在$[1,l-1]$和$[l,r]$上的元素,因为在计算$pre[r]$的时候对于和$[1,l-1]$序列中相同的元素是剔除的,但是减掉之后是需要再加上去的。

对于查询$a[l,…,r]$和$a[1,…,l-1]$内同时出现数字的种类,可以使用树状数组来进行维护。$bit[i]$表示$a[i]$已经在$1,…,l$出现过了。

先对区间查询进行离线排序操作,对于左端每次右移把对应的数的下一个位置加入到树状数组中即可。(嘤嘤嘤?)

tips:处理每个位置数字下一次出现位置的方式很巧妙哦!

1
2
3
4
5
6
7
8
9
10
11
12
//last 记录上一个出现该数字的位置
//nxt 记录下一个出现该数字的位置
rep(i,1,n+1){
if(!vis[a[i]]){
vis[a[i]] = 1;
pre[i] = pre[i-1]+1;
}else{
pre[i] = pre[i-1];
}
if(last[a[i]]) nxt[last[a[i]]] = i;
last[a[i]] = i;
}

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 10;
int a[maxn],last[maxn],nxt[maxn],vis[maxn],pre[maxn],bit[maxn];
int n,q;
struct node{
int l,r,id;
bool operator<(const node& x){
return l < x.l;
}
}ask[maxn];
int lowbit(int x){return x&-x;}
void update(int x,int val){
for(int i=x;i<=n*2;i+=lowbit(i)){
bit[i] += val;
}
}
int query(int x){
int s = 0;
for(int i=x;i;i-=lowbit(i)){
s += bit[i];
}
return s;
}
int query(int l,int r){
return query(r) - query(l-1);
}
void init(){
memset(vis,0,sizeof(vis));
memset(last,-1,sizeof(last));
memset(nxt,-1,sizeof(nxt));
memset(bit,0,sizeof(bit));
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&q)){
init();
rep(i,1,n+1) scanf("%d",&a[i]),a[i+n] = a[i];
rep(i,1,n+n+1){
if(!vis[a[i]]){
pre[i] = pre[i-1] + 1;
vis[a[i]] = 1;
}else{
pre[i] = pre[i-1];
}
if(~last[a[i]]) nxt[last[a[i]]] = i;
last[a[i]] = i;
}
rep(i,0,q){
int l,r;scanf("%d%d",&l,&r);
int temp = l;l = r;r = temp + n;
ask[i].l = l;ask[i].r = r;ask[i].id = i;
}
sort(ask,ask+q);
int nowl = 1;
int ans[maxn];
rep(i,0,q){
while(nowl < ask[i].l){
if(~nxt[nowl])update(nxt[nowl],1);
nowl++;
}
ans[ask[i].id] = pre[ask[i].r] - pre[ask[i].l-1] +query(ask[i].l,ask[i].r);
}
rep(i,0,q) printf("%d\n",ans[i]);
}
return 0;
}

Reference:https://www.nowcoder.com/discuss/87249?type=101&order=0&pos=12&page=1

[hdoj6438]Buy and Resell

[hdoj6438]Buy and Resell

题意

给定$n$个城市和无限制的初始金钱你可以在每个城市里

  • 以$a_i$的价格买个商品
  • 以$a_i$的价格卖出商品
  • 啥都不做

问最多能赚多少钱?

题解

贪心 + 数据结构

假设每个城市都卖出商品。那么之前买入的最便宜的商品来卖。对于买卖次数就将假设买入的商品记录为两种

  • $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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T,n;
ll ans = 0;
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
priority_queue<pII>pq; ans = 0;int cnt = 0;
scanf("%d",&n);
rep(i,0,n){
int x;scanf("%d",&x);
pq.push(make_pair(-x,1));
pq.push(make_pair(-x,2));
ll temp = x + pq.top().fi;
if(pq.top().se == 1) cnt+=2;
ans += temp;
pq.pop();
}
printf("%lld %d\n",ans,cnt);
}
return 0;
}

[hdoj6447] YJJ's Salesman

[hdoj6447] YJJ’s Salesman

题意

给定一个地图,只能向右或者向上走,地图上有很多点,有以下条件

  • 每个点有钱$val$
  • 你只能从该点的左下方进入点才可以拿钱。

问最多能获得多少钱。

题解

dp + 树状数组优化

单dp就是$O(n^2)$的复杂度。但是题目数据范围$1e5$所以不行。只有树状数组优化了。

树状数组处理的是$dp[i]$代表着以$i$点为重点的权值。

并且由于$x,y$范围是$1e9$所以必须离散化。

有一步我看了好久代码才看懂。在dp方程转移的时候,先对于$x$进行排列,之后在之后更大的$x$再更新之后的dp数组,保证每一次update的dp数组都是最优的。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
struct node{
int x,y,val;
bool operator <(const node& t)const{
return x < t.x;
}
}a[maxn];
int T,n,tot;
int bit[maxn],dp[maxn];
int lowbit(int x){
return x&-x;
}
void update(int x,int val){
for(int i=x;i<=tot;i+=lowbit(i)) bit[i] = max(bit[i],val);
}
int query(int x){
int s = 0;
for(int i=x;i;i-=lowbit(i)){
s = max(s,bit[i]);
}
return s;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
vector<int> v;
memset(bit,0,sizeof(bit));
scanf("%d",&n);
rep(i,0,n){
int x,y,v;scanf("%d%d%d",&x,&y,&v);
a[i].x = x;a[i].y = y;a[i].val = v;
}
rep(i,0,n) v.push_back(a[i].y);
sort(v.begin(),v.end());
sort(a,a+n);
v.erase(unique(v.begin(),v.end()),v.end());
tot = v.size();
rep(i,0,n) a[i].y = lower_bound(v.begin(),v.end(),a[i].y) - v.begin() + 1;
rep(i,0,n) dp[i] = a[i].val;
int ans = 0;int pos = 0;
rep(i,0,n){
while(pos < i && a[pos].x < a[i].x){
update(a[pos].y,dp[pos]);
pos ++;
}
dp[i] = query(a[i].y-1) + a[i].val;
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}

51Nod-1593 公园晨跑

51Nod-1593 公园晨跑

题意

给定一个环,环上有$n$个点,每个点有一个权值$h$代表着如果从$i$到$j$的话,你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。

题解

线段树维护区间最大最小值的坐标和特判相同处理。

首先,面对环和方向性,我们可以把环拆成链式。形成一个$[1,n] \cup [1.n]$的区间对于$X,Y$的查找可以看成两种情况,

  • 一种是$X\leq Y$,那么我们寻找的范围就是$[Y+1,X+n-1]$。
  • 对于$X>Y$的情况,我们寻找的范围就是$[Y+1,X-1]$。

定义$d[x]$为$x$点到第一个点的距离(线性)。

对于给定的两个点$X,Y$,我们获得的权值是确定的,为$d[Y]-d[X]+2h[X]+2h[Y]$,我们可以将这个算式分为$X$部分和$Y$部分。于是我们就可以将式子转化为

$target = (d[Y]+2h[Y]) - (d[X]-2h[X])$

这个式子求最大值,就是对于每个点求第一部分的最大值和第二部分的最小值。之后由于$X != Y$,所以对于线段树维护的是区间内最大最小值的坐标。当坐标相同时,寻找次一级的最小值或者次一级的最大值。

AC代码(要加入读入优化)

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const ll INF = 1e11;
//head
const int maxn = 2e5 + 10;
ll h[maxn],d[maxn],A[maxn],B[maxn];
int mmax[maxn<<2],mmin[maxn<<2];
template <class T>
bool read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
else if(c == EOF) return 0;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
return 1;
}
inline int Max(int a,int b){
return A[a] > A[b] ? a : b;
}
inline int Min(int a,int b){
return B[a] < B[b] ? a : b;
}
inline ll Mmax(ll a,ll b){
return a>b?a:b;
}
int m,n;
void pushup(int rt){
mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = l;
mmin[rt] = l;
return ;
}
int mid = (r+l)>>1;
build(lson);build(rson);
pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) return mmax[rt];
int mid = (l+r) >> 1;
ll res = 0;
if(L <= mid) res = Max(res,query_max(L,R,lson));
if(mid < R) res = Max(res,query_max(L,R,rson));
return res;
}
int query_min(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) return mmin[rt];
int mid = (l+r) >> 1;
ll res = 0;
if(L <= mid) res = Min(res,query_min(L,R,lson));
if(mid < R) res = Min(res,query_min(L,R,rson));
return res;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,2,n+2) read(d[i]),d[n+i] = d[i];
rep(i,2,n*2+1) d[i] += d[i-1];
rep(i,1,n+1){
ll hh;read(hh);
h[i] = h[i+n] = hh;
}
A[0] = -INF;B[0] = INF;
rep(i,1,n+n+1){
A[i] = 2*h[i] + d[i];
B[i] = d[i] - 2*h[i];
}
build(1,n*2,1);
while(m--){
int l,r;read(l);read(r);
if(l<=r){
int st = query_max(r+1,l+n-1,1,2*n,1);
int ed = query_min(r+1,l+n-1,1,2*n,1);
ll ans;
if(st == ed){
int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
}else ans = A[st] - B[ed];
printf("%lld\n",ans);
}else{
int st = query_max(r+1,l-1,1,2*n,1);
int ed = query_min(r+1,l-1,1,2*n,1);
ll ans;
if(st == ed){
int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
}else ans = A[st] - B[ed];
printf("%lld\n",ans);
}
}
return 0;
}

reference:https://blog.csdn.net/ZLH_HHHH/article/details/74887389

nowcoder6 C.Generation I

Generation I

题解

首先放$k$种数字的情况,有$A_n^k$中可能。

由于操作后,前面的球就无法放置,就可以第一个放置该数字的点来确定该结果的区别。相当于将$k$种放在$n$个格子里面。使用隔板法$n\choose k$。

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll mod = 998244353;
int T;
const int maxn = 1e6 + 10;
ll cur,p[maxn],q[maxn],inv[maxn];
ll n,m;
ll C(ll n,ll k){
return p[n]*q[k]%mod*q[n-k]%mod;
}
ll c(ll n,ll k){
if(n<maxn) return C(n,k);
if(!k) return 1;
return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;
}
void init(){
p[0] = p[1] = q[0] = q[1] = inv[0] = inv[1] = 1;
for(ll i = 2;i<maxn;i++){
inv[i] = (mod-mod/i)*inv[mod%i]%mod;
q[i] = q[i-1]*inv[i]%mod;
p[i] = p[i-1] * i % mod;
}
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
init();
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%lld%lld",&n,&m);
ll len = min(n,m);
ll ans = 0;
cur = 1;
for(ll i = 1;i<=len;i++){
ans = (ans + (c(m,i)*p[i]%mod)*c(n-1,i-1)%mod)%mod;
}
printf("Case #%d: %lld\n",test_case,ans);
}
return 0;
}

[POJ3264]Balanced Lineup

[POJ3264]Balanced Lineup

题意

给一个数列,求数列中$l,r$范围内最大值和最小值的差。

题解

st表模板题。求两次rmq即可。

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
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
int n,q;
int st[maxn][32-__builtin_clz(maxn)];
int st2[maxn][32-__builtin_clz(maxn)];
int h[maxn];
int ST(){
int l = 31 - __builtin_clz(n);
rep(i,0,n) {st[i][0] = h[i];st2[i][0] = h[i];}
rep(j,0,l) rep(i,0,n-(1<<j)+1){
st[i][j+1] = max(st[i][j],st[i+(1<<j)][j]);
st2[i][j+1] = min(st2[i][j],st2[i+(1<<j)][j]);
}
}
int max_rmq(int l,int r){
int k = 31 - __builtin_clz(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int min_rmq(int l,int r){
int k = 31 - __builtin_clz(r-l+1);
return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int main(){
#ifdef LOCAL
freopen("shui.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&q)){
rep(i,0,n) scanf("%d",&h[i]);
ST();
while(q--){
int l,r;scanf("%d%d",&l,&r);
l--,r--;
printf("%d\n",max_rmq(l,r)-min_rmq(l,r));
}
}
return 0;
}

2018 Multi-University Training Contest 8 D.Parenth

2018 Multi-University Training Contest 8 D.Parentheses Matrix

传送门

题目大意

一个由左括号和右括号组成的矩阵,定义矩阵的权值是矩阵中匹配的行数和列数的和。

题解

一道比较典型的构造题。

如果行数或者列数是奇数那么矩阵显然是奇数的行或列匹配不了。

(())

(())

(())

当情况很多有两个变量的时候我们可以假设一个变量小于另一个变量,假设$h\leq m$。

构造过程还是题解比较清晰。

首先,第一行、最后一列中最多只有一个能够匹配,第一列、最后一行也只有一个能够匹配(考 虑右上角和左下角的括号选取方法),故答案不会超过 w+h−2。 当 h = 2 时,每一列可以构造一对匹配,这样答案已经到达上界。 当 h = 4 时,可以如下构造:

( ( ( ( ( (

) ) ) ) ) )

( ( ( ( ( (

) ) ) ) ) )

这样答案是 w+h−3。

若存在更优的答案,则必有一个边界能够匹配,不妨设是第一列。这样,就已 经有除第一行以外的两行(右括号开头的行)不匹配了,而第一行和最后一列中至少有一个不匹配, 因此最优解不会超过 w+h−3。

当 h≥6 时,可以如下构造:

( ( ( ( ( ( ( (

( ) ( ) ( ) ( )

( ( ) ( ) ( ) )

( ( ( ( ) ) ) )

( ( ) ( ) ( ) )

) ) ) ) ) ) ) )

答案是 w+h−4。同理可证明不存在更优的方法。

在实际操作的时候如果$h>m$可以将矩阵反转一下。就ok了。

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int t,h,w;
char g[300][300];
int main(){
#ifdef LOCAL
freopen("d.in","r",stdin);
#endif
scanf("%d",&t);
while(t--){
bool flag = 0;
scanf("%d%d",&h,&w);
if(h&1){
rep(i,0,h){
rep(j,0,w){
g[i][j] = (j<w/2 ? '(' : ')');
}
}
}else if(w&1){
rep(i,0,h){
rep(j,0,w){
g[i][j] = (i<h/2 ? '(' : ')');
}
}
}
else{
if(h>w){
int temp = h;
h = w;
w = temp;
flag = 1;
}
if(h==2){
rep(i,0,w){
g[0][i] = '(';
g[1][i] = ')';
}
}else if(h == 4){
rep(i,0,w){
g[0][i] = '(';
g[1][i] = (i<w/2 ? ')' : '(');
g[2][i] = (i<w/2 ? '(' : ')');
g[3][i] = ')';
}
}else{
rep(i,0,h){
rep(j,0,w){
if(i==0 || j==0) g[i][j] = '(';
else if(i == h-1 || j == w-1) g[i][j] = ')';
else if((i^j)&1) g[i][j] = ')';
else g[i][j] = '(';
}
}
}
}
if(flag){
rep(j,0,w){
rep(i,0,h){
putchar(g[i][j]);
}
puts("");
}
}else{
rep(i,0,h){
rep(j,0,w){
putchar(g[i][j]);
}
puts("");
}
}
}
return 0;
}

A. Rikka with Nash Equilibrium

A. Rikka with Nash Equilibrium

题解:

神仙dp题

将数字从大到小一次排列,从大往小取.

  • 构造一个三维$dp[now][j][k]​$,表示放入$now​$数字的时候有$i​$行和$j​$列有数字下的情况。为了防止数字成为平衡位置,每次放置的位置都要放置在之前放置元素所在的列或者行上,如果不这么放置的话,他就会成为剩下当前行和当前列最大的(就没能有比他大的数字了)。

  • 初始化,因为第一个数字可以任意存放所以$dp[0][1][1]=m*n$。

  • 转移方程:

    1. 该点放置位置上行和列都有元素,那就是有$i$列和$j$行可以存放。剩下的位置是$j*k-i+1$

      ,$dp[next][j][k]+=dp[now][j][k]*(jk-i+1)$

    2. 该点放置位置上列已经有元素了,但是行上没有元素,从位置的行数减一转移加了一行$dp[next][j][k]+=dp[now][j-1][k]*j(n-i+1)$

    3. 同理如果行有元素的话。$dp[next][j][k]+=dp[now][j][k-1]*i(m-j+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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 88;
int t,m,n;
ll mod;
ll dp[2][maxn][maxn];
inline ll add(ll a, ll b){
return (a+b>mod)?(a+b)%mod:a+b;
}
inline ll mul(ll a,ll b){
return a*b>mod?(a*b)%mod:a*b;
}
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
scanf("%d",&t);
while(t--){
scanf("%d%d%lld",&n,&m,&mod);
memset(dp,0,sizeof(dp));
dp[0][1][1] = n*m;
int now = 0;
rep(i,2,m*n+1){
int nxt = now^1;
memset(dp[nxt],0,sizeof(dp[nxt]));
rep(j,0,n+1){
rep(k,0,m+1){
if(dp[now][j][k]){
ll tot = j*k - i + 1;
dp[nxt][j][k] = add(dp[nxt][j][k],dp[now][j][k]*tot);
dp[nxt][j+1][k] = add(dp[nxt][j+1][k],mul(dp[now][j][k],1ll*k*(n-j)));
dp[nxt][j][k+1] = add(dp[nxt][j][k+1],mul(dp[now][j][k],1ll*j*(m-k)));
//cout<<dp[now][j][k];
}
}
}
now = nxt;
}
printf("%lld\n",dp[now][n][m]);
}
return 0;
}

杭电多校Age_of_Moyu

Age of Moyu

题解

标程的set+bfs貌似有漏洞。

1
2
3
4
5
6
7
5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
1 4 3

这个数据就可以hack掉了。

所以我果断copy了dls队伍的代码。(用边做)

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
inline char inputchar()
{
return getchar();
}
inline void inputnum(int &ret)
{
char ch = inputchar();
while(ch < '0' || ch > '9')
ch = inputchar();
ret = ch - '0';
ch = inputchar();
while(ch >= '0' && ch <= '9')
{
ret = ret * 10 + ch - '0';
ch = inputchar();
}
}
const int MAXN = 101010, MAXM = 202020;
int n, m;
class Edge
{
public:
int to, c, next;
}e[MAXM * 2];
int en, head[MAXN];
int dis[MAXM];
deque<int> q;
void insert()
{
int u, v, c;
// scanf("%d%d%d", &u, &v, &c);
inputnum(u);
inputnum(v);
inputnum(c);
e[++en].to = v;
e[en].c = c;
e[en].next = head[u];
head[u] = en;
e[++en].to = u;
e[en].c = c;
e[en].next = head[v];
head[v] = en;
}
bool solve()
{
if(scanf("%d%d", &n, &m) != 2)
return false;
memset(head, -1, (n + 2) * sizeof(int));
en = 1;
for(int i = 1; i <= m; i++)
insert();
memset(dis, 1, (m + 2) * sizeof(int));
for(int i = head[1]; i > 0; i = e[i].next)
dis[i / 2] = 1, q.push_back(i / 2);
while(!q.empty())
{
int now = q.front();
q.pop_front();
for(int i = head[e[now * 2].to]; i > 0; i = e[i].next)
if(e[i].c == e[now * 2].c)
{
if(dis[i / 2] > dis[now])
dis[i / 2] = dis[now], q.push_front(i / 2);
}
else
{
if(dis[i / 2] > dis[now] + 1)
dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
}
for(int i = head[e[now * 2 + 1].to]; i > 0; i = e[i].next)
if(e[i].c == e[now * 2 + 1].c)
{
if(dis[i / 2] > dis[now])
dis[i / 2] = dis[now], q.push_front(i / 2);
}
else
{
if(dis[i / 2] > dis[now] + 1)
dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
}
}
int ans = MAXM;
for(int i = head[n]; i > 0; i = e[i].next)
if(ans > dis[i / 2])
ans = dis[i / 2];
if(ans == MAXM)
ans = -1;
printf("%d\n", ans);
return true;
}
int main()
{
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
while(solve());
return 0;
}

时间卡的非常紧。优化了很多终于2.4s过了。

$$O(n^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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1e5 + 10;
int n,m,ans,cnt;
int head[maxn],dis[maxn<<1];
struct Edge{
int to,next,idx;
}G[maxn<<2];
void add(int u,int v,int id){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].idx = id;
head[u] = cnt++;
}
deque<int> q;
void bfs(){
for(int i = head[1];~i;i=G[i].next) dis[i/2] = 1,q.push_back(i/2);
while(!q.empty()){
int now = q.front();
q.pop_front();
for(int i = head[G[now*2].to];~i;i=G[i].next){
if(G[i].idx == G[now*2].idx){
if(dis[i/2] > dis[now]){
dis[i/2] = dis[now];q.push_front(i/2);
}
}else{
if(dis[i/2] > dis[now] + 1){
dis[i/2] = dis[now]+1;q.push_back(i/2);
}
}
}
for(int i = head[G[now*2+1].to];~i;i=G[i].next){
if(G[i].idx == G[now*2+1].idx){
if(dis[i/2] > dis[now]){
dis[i/2] = dis[now];q.push_front(i/2);
}
}else{
if(dis[i/2] > dis[now]+1){
dis[i/2] = dis[now]+1;q.push_back(i/2);
}
}
}
}
ans = INF;
for(int i = head[n];~i;i=G[i].next){
if(ans > dis[i/2]) ans = dis[i/2];
}
}
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
memset(head,-1,sizeof(int)*(n+2));cnt = 0;
rep(i,0,m+2) dis[i] = INF;
rep(i,0,m){
int u,v,id;read(u);read(v);read(id);
add(u,v,id);add(v,u,id);
}
bfs();
printf("%d\n",ans==INF?-1:ans);
}
return 0;
}

Appleman_and_Tree

Appleman and Tree

链接

如果觉得我的题解看不懂可以去看 大佬的题解

题目大意

将一颗树节点染成白色或者黑色,减去几条变使得每个联通分支都有一个黑色节点,问有多少种减边方案。


题解

树状dp+dfs

下次看到两种状态加点的。dp应该想到用2维。

  1. 定义$dp[i][j]$表示点$i$在以点$i$为根的子树去掉点$i$所在的联通快有黑点$1$和无黑点$0$的方案数
  2. 假设点$u$,首先如果$u$是黑色,那么$$dp[i][1]=1$$,否则$dp[i][0]=1$。
    1. 点$u$加入一个子树$v$。假设原来$u$没有黑点。
      1. 如果加入的$v$是有黑点的,有两种选择,切断边$u$还是没有黑点,方案数$dp[u][0]=dp[u][0]*dp[v][1]$,不切断边$u$就产生了黑点$dp[u][1]=dp[u][0]*dp[v][1]$
      2. 如果加入的$v$是无黑点的,只能选择不切断。方案数$dp[u][0]=dp[u][0]*dp[v][0]$
    2. 点$$u$$加入一个子树$v$。假设原来$u$有黑点。
      1. 如果加入的$v$是有黑点的,只能选择切断,方案数$dp[u][1]=dp[u][1]*dp[v][1]$
      2. 如果加入的点$v$是无黑点的,只能选择切断,因为不能产生无黑点的联通分支,方案数$dp[u][1]=dp[u][1]*dp[v][0]$

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
struct node{
int to,next;
}G[maxn<<1];
int cnt;
ll dp[maxn][2];
int head[maxn];
void add(int from,int to){
G[cnt].to = to;
G[cnt].next = head[from];
head[from] = cnt++;
}
int n;
void dfs(int u,int fa){
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
if(v == fa) continue;
dfs(v,u);
dp[u][1] = dp[u][1]*dp[v][1]%mod + dp[u][0]*dp[v][1]%mod + dp[u][1]*dp[v][0]%mod;
dp[u][1] %= mod;
dp[u][0] = dp[u][0]*dp[v][0]%mod + dp[u][0]*dp[v][1]%mod;
dp[u][0] %= mod;
}
}
int main(){
#ifdef LOCAL
freopen("B.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n){
int v; scanf("%d",&v);
add(i,v);add(v,i);
}
rep(i,0,n){
scanf("%d",&dp[i][1]);
if(dp[i][1]==0) dp[i][0] = 1;
}
dfs(0,-1);
cout<<dp[0][1]<<endl;
return 0;
}