855C Helga Hufflepuff’s Cup
传送门
题意：对一棵树上的n个点染色，有m种颜色，对于颜色k，最多染x个，并且每一个与颜色为k的节点相连的点的颜色必须小于k
很明显是一道树形dp的题啦，一开始只开了二维，记录取k/不取k，发现转移不动，然后意识到每个节点有三种情况：取k，小于k，大于k，并且我们还要记录当前有几个节点颜色为k，并且已经限定了x≤10，自然开三维去转移就好，比如dp[i][j][l]就代表第i个节点染色情况为j时有l个节点颜色为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
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define il inline
#define mod 1000000007
vector<int> g[maxn];
ll dp[maxn][3][15];
int n,num;
ll m,k;
void dfs(int x,int fa){
dp[x][0][0]=k-1;
dp[x][2][0]=m-k;
dp[x][1][1]=1;
for(auto i:g[x]){
if(i!=fa){
dfs(i,x);
ll tmp[15][3]={0};
for (int j = 0; j <=num ; ++j) {
for (int l = 0; l <=j ; ++l) {
tmp[j][0]+=(dp[i][0][l]+dp[i][1][l]+dp[i][2][l])*dp[x][0][j-l];
tmp[j][0]%=mod;
tmp[j][1]+=dp[i][0][l]*dp[x][1][j-l];
tmp[j][1]%=mod;
tmp[j][2]+=(dp[i][2][l]+dp[i][0][l])*dp[x][2][j-l];
tmp[j][2]%=mod;
}
}
for (int j = 0; j <=num ; ++j) {
dp[x][0][j]=tmp[j][0];
dp[x][1][j]=tmp[j][1];
dp[x][2][j]=tmp[j][2];
}
}
}
}
int main() {
int x;
cin>>n>>m;
for (int i = 0; i <n-1 ; ++i) {
int u,v;
cin>>u>>v;
g[v].push_back(u);
g[u].push_back(v);
}
cin>>k>>x;
num=x;
dfs(1,0);
ll ans=0;
for (int i = 0; i <=x ; ++i) {
ans+=dp[1][2][i]+dp[1][0][i]+dp[1][1][i];
ans%=mod;
}
cout<<ans%mod;
return 0;
}
|
（貌似HDU也有一道类似思路的题）
1172A Nauuo and Cards
传送门
题意：你手里有n张牌，场上有n张牌，每张牌的值在0~n，每次可以从手中选择一张牌放在场上牌堆的最后，并且把第一张取走，询问最少多少次可以使得场上的顺序为1-n。
很明显答案是有上界的，最差就是把n张都取走，然后依次放置，而对于初始每一张牌，假设其值为i，位置为p[i]，那么将其移动到正确位置需要p[i]-i+n+1次，显然取max(p[i]-i+n+1)次就可以完成目标。
但是仍然存在存在更优方案的情况，不如考虑1 2 3，如果我们按照上面的方法，是4，但是显然答案是0。很容易联想到如果我们可以1,2,3……n的放置，那么我们就没必要用上面的取法，而这种情况需要从场上的末尾开始向前存在i ,i-1,i-2,……1，并且我们每次可以把末尾牌面+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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define rep(i,m,n) for(int (i)=(m);(i)<=(n);(i)++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int a[maxn],b[maxn];
int pos[maxn];
int main() {
IOS
int n;
cin>>n;
int ans=0;
rep(i,1,n)cin>>a[i];
rep(i,1,n){cin>>b[i];pos[b[i]]=i;}
if(pos[1]!=0){
int i;
for (i = 2; pos[i]-pos[1]==i-1 ; ++i){}
if(pos[i-1]==n){
int j;
for (j = i; j<=n&&pos[j]<=j-i ; ++j){}
if(j>n){
cout<<n-i+1;
return 0;
}
}
}
rep(i,1,n)ans=max(ans,pos[i]-i+n+1);
cout<<ans;
return 0;
}
|
1151C Problem for Nazar
传送门
题意：每次从奇数列和偶数列取2的幂次个数写到黑板上，比如1 | 2 4 | 3 5 7 9 | 6 8 10……,询问区间[l,r]的和。
上午刚学了数位dp，直接就想到了前缀和相减的思路。对于前i个，虽然看起来计算挺麻烦，但是不难发现
- 奇数列中，前i项和为i*i
- 偶数列中，前i项和为i*(i+1)
那么我们只需要去找前i个数中有多少奇数和多少偶数就好了。
（日常瞎**取模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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define mod 1000000007
ll calc(ll x){
int cnt=1;
ll l=1,lr=0ll,r=0ll;
while(x>=l){
int fl=0;
if(cnt==1&&x>=l){
fl=1;
x-=l;
lr+=l;
l*=2;
}else if(cnt==0&&x>=l){
fl=1;
x-=l;
r+=l;
l*=2;
}
cnt++;
cnt%=2;
if(!fl)break;
}
if(!cnt)r+=x;
else lr+=x;
lr%=mod;
r%=mod;
return ((lr*lr)%mod+(r*(r+1))%mod)%mod;
}
int main() {
ll l,r;
cin>>l>>r;
cout<<((calc(r)-calc(l-1))%mod+mod)%mod;
return 0;
}
|