牛客多校10简单题解_牛客iupc

没有成为DP高手

F.IUPC

题意：有n个题目可以在t时间内解决它们，每个题目只有在$x_i$后才能解决，每个题目只能提交一次，一分钟只能提交一次，再连续的k分钟内只能提交m次
思路：看到n和k的范围很明显的是一个状压DP,
一直到结束也没写出来，赛时考虑的暴力。
对于每分钟，记录到达时的题目的状态$bit1$，那些没做那些做了，状态数为$2^n-1$，还有前k分钟的提交状态$bit2$，状态数为$2^k-1$。这样就可以进行转移，设$f_{i,bit1,bit2}$为每分钟的方案数，分两类暴力转移
1.当前分钟不交题
因为非法的数量即为0，所以直接转移即可
$f_{i,bit1,(bit2<<1)\%(1<<k)}+=f_{i-1,bit1,bi2}$
2.当前分钟提交题目
要保证
当前提交的题目是前面没有做过的
转移后的提交情况状态在二进制下1的数量不超过m个
$f_{i,bit1|(1<<b),(bit2<<1|1)\%(1<<k)}+=f_{i-1,bit1,bi2}$
样例能跑很开心，一交TLE。仔细算一下复杂度在2e9左右。
两个条件全部状压太多了，那么考虑只状压一个。赛时考虑状态做题情况，不知道怎么处理提交情况。提交情况要保证连续k分钟只提交m次，而做题情况只要全部完成即可，所以状压提交状态比较合理。考虑处理做题的状态，我们只需要记录第i分钟做题的数量即可，因为要求的只是方案数量而且每个题只能提交一次。所以我们可以处理出每分钟可以提交的题目的总数$pr{e}_i$，设当前已经做过的题的数量为$cnt$，贡献即为$pr{e}_i-cnt$与前一分钟转移过来的相乘即可
设$f_{i,bit,cnt}$为第i分钟，前k分钟做题状态为$bit$，已经做过的题目数量为$cnt$
1.当前分钟不交题
$f_{i,(bit<<1)\%(1<<k),cnt}+=f_{i-1,bit,cnt}$
2.当前分钟提交题目
要保证
当前提交的题目是前面没有做过的($cnt<pr{e}_i$)
转移后的提交情况状态在二进制下1的数量不超过m个 $getb((bit<<1|1)\%(1<<k))\le m$
$f_{i,(bit<<1|1)\%(1<<k),cnt}+=f_{i-1,bit,cnt}\times (pr{e}_i-cnt)$
最后答案对 $f_{t,bit,n}$求和即可

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=305;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
int n,t,k,m,x[N];
ll f[N][20][(1<<10)];
int getb(int x){
	int res=0;
	for(int i=0;i<k;i++){
		if(x>>i&1){
			res++;
		}
	}
	return res;
}
void solve(){
	cin>>n>>t>>k>>m;
	for(int p,i=0;i<n;i++){
		cin>>p;
		x[p]++;
	}
	for(int i=1;i<=t;i++){
		x[i]+=x[i-1];//处理时间i可以提交的数量 
	}
	f[0][0][0]=1;
	ll ans=0;
	for(int i=1;i<=t;i++){
		for(int cnt=0;cnt<=n;cnt++){
			for(int bit=0;bit<(1<<k);bit++){
				int b1=(bit<<1)%(1<<k),b2=(bit<<1|1)%(1<<k);
				f[i][cnt][b1]+=f[i-1][cnt][bit];//不提交 
				f[i][cnt][b1]%=md;
				if(getb(b2)<=m&&cnt<x[i]){//提交 
					f[i][cnt+1][b2]+=f[i-1][cnt][bit]*1ll*(x[i]-cnt)%md;
					f[i][cnt+1][b2]%=md;
				}
			}
		}
	}
	for(int i=0;i<(1<<k);i++){
		ans=(ans+f[t][n][i])%md;
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}

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

L.Grayscale Confusion

粗略看了看，感觉是直接建图跑拓扑序就扔给队友了最后发现题意读错哈哈哈哈哈
题意：给定n组$(r,g,b)$，要给每一组重新映射一个值$f(r,g,b)$
满足以下条件：
如果 $r<r\prime ,g<g\prime ,b<b\prime$ 则 $f(r,g,b)<f(r\prime ,g\prime ,b\prime )$
问是否在构造出来第一组的值与第二组的值相同
思路：可以先建立出一个有向无环图，然后就可以跑拓扑序了。按照拓扑序去直接构造值一定是符合题目要求的，但是不一定满足第一组的值与第二组的值相同。想一个很简单的情况，第一组和第二组在不同的链上，直接拓扑构造他俩的值不同，但是可以让其中一条链进行整体的加减就有可能满足要求。
整体思路仍然是拓扑序，我们可以先处理以第一，二组为终点的拓扑序得到一个初始的值$f$。
然后去配平第一第二组的$f$,小的值向大增加。这样可以保证现有的大小关系不被破坏。
在去给没有值的点进行符合大小关系的赋值，检查是否满足题目要求即可。

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1500;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
struct graph{
	int cnte,hd[N];
	struct  edge{
		int v,nt;
	}e[N*N];
	void addedge(int v,int u){
		e[++cnte].v=u;
		e[cnte].nt=hd[v];
		hd[v]=cnte;
	}
};
struct aa{
	int r,g,b;
}col[N];
int n,du[N],gre[N],cnt[N];
graph g;
bool cmp(int x,int y){
	if(col[x].r<col[y].r&&col[x].g<col[y].g&&col[x].b<col[y].b){
		return 1;
	}
	return 0;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
        g.hd[i]=0;
		cin>>col[i].r>>col[i].g>>col[i].b;
	}
	if(cmp(1,2)||cmp(2,1)){
		cout<<-1<<endl;
		return ;
	}
    g.cnte=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cmp(i,j)){//i<j
				g.addedge(i,j);
				du[j]++;
			}
		}
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(du[i]==0&&i!=1&&i!=2){
			q.push(i);
			gre[i]=0;
		}
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=g.hd[now];i;i=g.e[i].nt){
			int v=g.e[i].v;
			du[v]--;
			gre[v]=max(gre[v],gre[now]+1);
			if(du[v]==0&&v!=1&&v!=2){
				q.push(v);
			}
		}
	}
	gre[1]=gre[2]=max(gre[1],gre[2]);
	q.push(1);
	q.push(2);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=g.hd[now];i;i=g.e[i].nt){
			int v=g.e[i].v;
			du[v]--;
			gre[v]=max(gre[v],gre[now]+1);
			if(du[v]==0){
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(gre[i]>255){
			cout<<-1<<endl;
			return ;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<gre[i]<<endl;
	}
	return ;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}
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

真正的解法涉及一点数学，下次一定！
暑假训练结束了，感觉对未来又少了一份信心，太棒了。