首页 技术 正文
技术 2022年11月23日
0 收藏 373 点赞 2,564 浏览 7551 个字

Educational Codeforces Round 39 

D. Timetable

令\(dp[i][j]\)表示前\(i\)天逃课了\(j\)节课的情况下,在学校的最少时间

转移就是枚举第\(i\)天逃了\(x\)节课,然后取当天逃\(x\)节课情况下在学校的最小值即可

view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "\n"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
int n, m, k;
char s[MAXN];
void solve(){
sci(n); sci(m); sci(k);
vi f(k+1,n*m);
f[k] = 0;
for(int d = 1; d <= n; d++){
vi next_f(k+1,n*m);
scs(s+1);
vi A; for(int i = 1; i <= m; i++) if(s[i]=='1') A << i;
vi cost(A.size()+1,n*m);
for(int i = 0; i <= A.size(); i++){
if(i==A.size()) cost[i] = 0;
else for(int j = 0; j <= i; j++) cmin(cost[i],A[A.size() - 1 - i + j] - A[j] + 1);
}
for(int pre = 0; pre <= k; pre++) for(int cur = 0; cur <= min(pre,(int)A.size()); cur++) cmin(next_f[pre-cur],f[pre]+cost[cur]);
f.swap(next_f);
}
cout << *min_element(all(f)) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}

E.  Largest Beautiful Number

考虑从后往前枚举每个位置,判断在这个位置之前全部相同,这个位置比原来小的情况下是否存在合法解即可

特判长度为奇数的情况和小于等于\(1xxxxxx1\)的情况

view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "\n"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
int n;
string s;
void solve(){
cin >> s;
function<bool(void)>check = [&](){
string str(s.size(),'0');
str.front() = str.back() = '1';
return str >= s;
};
if(s.size()&1 or check()){
for(int i = 1; i <= (s.size()&1 ? s.size() - 1 : s.size() - 2); i++) cout << 9;
cout << endl; return;
}
vi cnt(10,0);
for(int i = 0; i < s.size(); i++) cnt[s[i]-'0'] ^= 1;
for(int i = s.size() - 1; ~i; i--){
cnt[s[i]-'0'] ^= 1;
for(char c = s[i] - 1; c >= '0'; c--){
cnt[c-'0'] ^= 1;
int tot = accumulate(all(cnt),0);
if(tot>s.size()-i-1){
cnt[c-'0'] ^= 1;
continue;
}
string str(s);
s[i] = c;
int cur = i;
for(int j = 0; j < s.size()-i-1-tot; j++) s[++cur] = '9';
for(int j = 9; ~j; j--) if(cnt[j]) s[++cur] = j + '0';
cout << s << endl;
return;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
int tt; for(cin >> tt; tt--; solve());
return 0;
}

F. Fibonacci String Subsequences

\(dp[i][l][r]\)表示\(f(i)\)中子串\(s[l:r]\)以子序列的方式出现的次数,考虑转移

对于一般情况,可以考虑把\(s[l:r]\)分成\(s[l:k]\)和\(s[k+1:r]\),然后分别在\(f(i-1)\)和\(f(i-2)\)中找

其次考虑\(s[l:r]\)全在\(f(i-1)\)或\(f(i-2)\)中,如果\(r=n-1\),那么在\(f(i-1)中找到\)\(s[l:r]\)出现次数之后由于后面可以随便选,乘上\(2^{fib(i-2)}\)即可,否则只算左边一部分,对于\(l=0\)的情况类似处理即可

view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "\n"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e2+7;
const int MOD = 1e9+7;
LL ksm(LL a, LL b){
LL ret = 1;
while(b){
if(b&1) ret = ret * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ret;
}
int n, x, fib[MAXN], f[MAXN][MAXN][MAXN];
string s;
int dp(int x, int l, int r){
int &ret = f[x][l][r];
if(~ret) return ret;
if(x==0) return (ret = ((l==r) and s[l]=='0'));
if(x==1) return (ret = ((l==r) and s[l]=='1'));
ret = 0;
if(r==n-1) ret = (ret + 1ll * dp(x-1,l,r) * ksm(2,fib[x-2])) % MOD;
else ret = (ret + 1ll * dp(x-1,l,r)) % MOD;
if(l==0) ret = (ret + 1ll * dp(x-2,l,r) * ksm(2,fib[x-1])) % MOD;
else ret = (ret + 1ll * dp(x-2,l,r)) % MOD;
for(int i = l; i < r; i++) ret = (ret + 1ll * dp(x-1,l,i) * dp(x-2,i+1,r)) % MOD;
return ret;
}
void solve(){
cin >> n >> x >> s;
fib[0] = fib[1] = 1;
for(int i = 2; i < MAXN; i++) fib[i] = (fib[i-1] + fib[i-2]) % (MOD - 1);
memset(f,255,sizeof(f));
cout << dp(x,0,n-1) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}

G. Almost Increasing Array

假设没有删一个数的条件的话,就是把原序列\(A\)中的所有\(A[i]\)变成\(A[i]-i\),然后算最长非降子序列

现在考虑枚举删掉的数为\(A[k]\),那么对于\(k\)之前的数\(A[i]\)来说,需要减去\(i\),对于\(k\)之后的数\(A[j]\)来说,需要减去\(j-1\)

那么之需要知道以\(k-1\)为结尾的最长非降子序列的长度和大于\(k\)的部分中起始值大于等于\(A[k-1]\)的最长非降子序列即可

那么可以用线段树来维护

view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "\n"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 4e5+7;
int n, A[MAXN];
struct SegmentTree{
int l[MAXN<<2], r[MAXN<<2], maxx[MAXN<<2];
#define ls(rt) rt << 1
#define rs(rt) rt << 1 | 1
#define pushup(rt) maxx[rt] = max(maxx[ls(rt)],maxx[rs(rt)])
void build(int L, int R, int rt = 1){
l[rt] = L; r[rt] = R;
maxx[rt] = 0;
if(L+1==R) return;
int mid = (L + R) >> 1;
build(L,mid,ls(rt)); build(mid,R,rs(rt));
}
void modify(int pos, int x, int rt = 1){
if(l[rt] + 1 == r[rt]){
maxx[rt] = x;
return;
}
int mid = (l[rt] + r[rt]) >> 1;
if(pos<mid) modify(pos,x,ls(rt));
else modify(pos,x,rs(rt));
pushup(rt);
}
int qmax(int L, int R, int rt = 1){
if(L>=r[rt] or l[rt]>=R) return 0;
if(L<=l[rt] and r[rt]<=R) return maxx[rt];
return max(qmax(L,R,ls(rt)),qmax(L,R,rs(rt)));
}
}ST;
int f[MAXN];
void solve(){
sci(n);
vi vec;
for(int i = 1; i <= n; i++) sci(A[i]), A[i] -= i, vec << A[i] << A[i] + 1;
sort(all(vec)); vec.erase(unique(all(vec)),vec.end());
auto ID = [&](int x){ return lower_bound(all(vec),x) - vec.begin() + 1; };
ST.build(0,vec.size()+1);
for(int i = 1; i <= n; i++){
int x = ID(A[i]);
f[i] = ST.qmax(0,x+1) + 1;
ST.modify(x,f[i]);
}
int ret = f[n-1];
ST.build(0,vec.size()+1);
for(int i = n; i >= 2; i--){
ret = max(ret,f[i-1]+ST.qmax(ID(A[i-1]),vec.size()+1));
int x = ID(A[i]+1);
ST.modify(x,ST.qmax(x,vec.size()+1)+1);
}
cmax(ret,ST.qmax(0,vec.size()+1));
cout << n - 1 - ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141002.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站