A noi week
codeforces round 637div2([Thanks, Ivan Belonogov!])
Final score:
Problem D.
D题的题意是有$n$个八数码管，即每个八数码管由八根LED管组成，可以表示$0-9$这$10$个数字，现在可以任选$k$根LED管点亮，问最大所能表示的数字是几。
思路就是先$dp$记录可行状态，然后再贪心的选取即可。令$dp_{i,j}$代表截止到第$i$个八数码管，还有$j$次点亮的机会的可行性，那么$dp_{n+1,0}=1$，然后倒着$dp$即可。处理完之后对每个八数码管贪心的选取最大的能点亮的数字即可。
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/*
* @author: codancer
* @createTime: 2020-04-24, 00:27:50
*/
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
string lights[20]={"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
string s[20000];
int lastcost;
bool dp[2002][20000];//boolean cost j after approach i
int cost(int a,int b){// the cost of s[a]->lights[b]
int ans=0;
for(int j=0;j<7;j++){
if(s[a][j]>lights[b][j]){
return -1;
}
ans+=lights[b][j]-s[a][j];
}
return ans;
}
int main(){
int n,k;
cin>>n>>k;
rep(i,1,n) cin>>s[i];
dp[n+1][0]=1;
lastcost=0;
fep(i,n,1){
fep(j,lastcost,0){
if(dp[i+1][j]==0) continue;
rep(k,0,9){
int costs=cost(i,k);
if(costs!=-1) dp[i][j+costs]|=dp[i+1][j];
lastcost=max(lastcost,j+costs);
}
}
}
vector<int> ans;
bool ok=1;
rep(i,1,n){
bool found=false;
fep(j,9,0){
int costs=cost(i,j);
if(costs!=-1&&costs<=k){
if(dp[i+1][k-costs]){
ans.pb(j);
k-=costs;
found=true;
break;
}
}
}
if(found==false){
ok=0;
break;
}
}
if(ok){
for(int v:ans) cout<<v;
cout<<endl;
}else{
puts("-1");
}
return 0;
}
Noi online
因为太怂没敢打提高组，打了普及组。比赛的时候提交了两道题，在洛谷上测试了民间数据都通过了。
预计成绩为$200$分。
T1是个简单的二分，考虑每次启用距离山顶最近的魔法机关，然后二分最少次数即可。
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/*
* @author: codancer
* @createTime: time
*/
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 2e5+100;
ll n,L,v,a[N],q,tt,predis[N];
bool cmp(ll x,ll y){
return x>y;
}
int main(){
// freopen("endless.in","r",stdin);
// freopen("endless.out","w",stdout);
scanf("%lld %lld %lld",&n,&L,&v);
rep(i,1,n){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1,cmp);
rep(i,1,n) predis[i]=predis[i-1]+a[i];
scanf("%lld",&q);
while(q--){
scanf("%lld",&tt);
ll l=0;
ll r=n+1;
bool ok=0;
rep(i,1,30){
ll mid=(l+r)/2;
if(predis[mid]+L>tt*v){
r=mid;
ok=1;
}else{
l=mid;
}
}
if(ok){
printf("%lld\n",r);
}else{
puts("-1");
}
}
return 0;
}T3题意是你需要构造$2n$个建筑，前$n$个建筑的高度单调不减，后$n$个建筑的高度单调不增，每个建筑的高度在$[1,m]$内，并且第$x$和第$y$座建筑的高度相同，计算方案数。
长度为$n$的数组，每个数字单调不减的方案书为$C(n+m-1,n)$,讨论$x$和$y$的位置即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/*
* @author: codancer
* @createTime: 2020-04-25, 15:24:40
*/
using namespace std;
typedef long long ll;
const ll mod = 998244353;
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 2e5+100;
ll n,m,x,y;
ll fact[N],inv[N],factinv[N];
void init(){
fact[0]=inv[1]=factinv[0]=inv[0]=fact[1]=factinv[1]=1;
for(int i=2;i<=200010;i++){
fact[i]=(fact[i-1]%mod*i%mod)%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
factinv[i]=factinv[i-1]*inv[i]%mod;
}
}
ll c(ll n,ll m){
return fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
ll solve(ll n,ll m){// the number of lengtn n and each number belongs [1,m]
if(m+n-1<n) return 0;
return c(m+n-1,n);
}
int main(){
// freopen("city.in","r",stdin);
// freopen("city.out","w",stdout);
init();
scanf("%lld%lld%lld%lld",&m,&n,&x,&y);
if(y<=n){
ll left=0;
rep(i,1,m){
ll xx=solve(x-1,i);
ll yy=solve(n-y,m-i+1);
left+=(xx*yy)%mod;
left%=mod;
}
ll right=solve(n,m);
printf("%lld\n", (left*right)%mod);
return 0;
}
if(x>n){
ll left=solve(n,m);
ll right=0;
x=2*n+1-x;
y=2*n+1-y;
swap(x,y);
rep(i,1,m){
ll xx=solve(x-1,i);
ll yy=solve(n-y,m-i+1);
right+=(xx*yy)%mod;
right%=mod;
}
printf("%lld\n", (left*right)%mod);
return 0;
}
ll ans=0;
ll left=0;
ll right=0;
y=2*n+1-y;
rep(i,1,m){
left=solve(x-1,i);
left*=solve(n-x,m-i+1);
left%=mod;
right=solve(y-1,i);
right*=solve(n-y,m-i+1);
right%=mod;
ans+=(left*right)%mod;
ans%=mod;
}
printf("%lld\n",ans);
return 0;
}