# Educational Codeforces Round 39

2022年11月23日
0 收藏 373 点赞 2,776 浏览 7551 个字

Educational Codeforces Round 39

D. Timetable

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 << endlfunction<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

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 << endlfunction<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]\)以子序列的方式出现的次数，考虑转移

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 << endlfunction<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

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 << endlfunction<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;}``

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用