《Codeforces Round #737 (Div. 2)》

2024-02-25 18:38:30

A：排序之后以某个点为分界线肯定是最优的。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;

int a[N];
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int n;scanf("%d",&n);
        double sum = 0;
        for(int i = 1;i <= n;++i) scanf("%d",&a[i]),sum += a[i];
        sort(a + 1,a + n + 1);
        double ans = -INF,pre = 0;
        for(int i = 1;i < n;++i) {
            pre += a[i];
            sum -= a[i];
            double ma = pre / i + sum / (n - i);
            ans = max(ans,ma);
        }
        printf("%.10f\n",ans);
    }

   // system("pause");
    return 0;
}

View Code

B：如果考虑去拆分这个数组然后再重组，个人觉得比较难做。

因为最后它肯定是整个数组排序好后的顺序，那么我们就可以从数值上进行考虑。

我们从小到大添加元素。

即第一次放入1，如果它的后一位刚好是下一位值即（1或者2），那么我们就放入下一位且不增加要分割的数组数量。

这样最后判断需要的数组数量是否 <= k即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;

int a[N],b[N],cnt[N];
bool vis[N];
vector<int> vec[N];
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int n,k;scanf("%d %d",&n,&k);
        for(int i = 1;i <= n;++i) scanf("%d",&a[i]),b[i] = a[i];
        sort(b + 1,b + n + 1);
        int len = unique(b + 1,b + n + 1) - b - 1;
        for(int i = 1;i <= n;++i) {
            cnt[i] = vis[i] = 0;
            vec[i].clear();
            a[i] = lower_bound(b + 1,b + len + 1,a[i]) - b;
        }
        for(int i = 1;i <= n;++i) {
            vec[a[i]].push_back(i);
        }
        int st,ty = 1,sz = 0,tot = 0;
        while(sz < n) {
            for(auto v : vec[ty]) {
                if(!vis[v]) {
                    ++tot;
                    ++sz;
                    vis[v] = 1;
                    st = v;
                    cnt[ty]++;
                    while(1) {
                        int f = 0;
                        while(cnt[ty] < vec[ty].size() && st < n) {
                            if(a[st + 1] == ty) {
                                st++,cnt[ty]++,sz++;
                                vis[st] = 1;
                            }
                            else break;
                        }
                        while(cnt[ty] == vec[ty].size() && st < n) {
                            if(a[st + 1] == ty + 1) {
                                ++ty;
                                st++,cnt[ty] = 1,sz++;
                                vis[st] = 1;
                                f = 1;
                            }
                            else break;
                        }
                        if(f == 0) break;
                    }
                }
                //printf("ty is %d cnt is %d vec is %d\n",ty,cnt[ty],vec[ty].size());
                if(cnt[ty] == vec[ty].size()) ty++;
            }
        }
        if(tot <= k) printf("YES\n");
        else printf("NO\n");
    }

   // system("pause");
    return 0;
}
/*
30
5 2
4 6 5 6 7
5 3
2 1 1 2 3


*/

View Code

C：这题个人感觉并不是很难，我们对题目的两种分开来考虑。(等于和大于的情况)。

对于等于的情况，我们类似dp处理下来就行。

对于大于的情况，我们枚举每个二进制位作为最高的大于位，即对于这一位 all & = 1,all ^ = 0

可以发现要满足all & = 1且all ^ = 0，那么该位所有都要 = 1，且n 不是偶数，不然all ^ = 1。

那么对于每一位的方案数 = dp[前面几位都相同的方案数] * (2 ^ (后面几位)) ^ n

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 2e5 + 5;
const int M = 1e3 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;

LL f[N],inv[N];
int n,k;
LL quick_mi(LL a,LL b) {
    LL re = 1;
    while(b) {
        if(b & 1) re = re * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return re;
}
void init() {
    f[0] = 1;
    for(int i = 1;i < N;++i) f[i] = f[i - 1] * i % Mod;
    inv[N - 1] = quick_mi(f[N - 1],Mod - 2);
    for(int i = N - 2;i >= 0;--i) inv[i] = inv[i + 1] * (i + 1) % Mod;
}
LL C(LL n,LL m) {
    return f[n] * inv[n - m] % Mod * inv[m] % Mod;
}
LL ans = 0;
int a[N];
void dfs(int x,int up,LL ma1,LL ma2) {
    if(x == n + 1) {
        if(ma1 >= ma2) ans++;
        return ;
    }
    for(int i = 0;i <= up;++i) {
        a[x] = i;
        if(x == 1) dfs(x + 1,up,i,i);
        else dfs(x + 1,up,ma1 & i,ma2 ^ i);
    }
}
int main() {
    init();
    int ca;scanf("%d",&ca);
    while(ca--) {
        scanf("%d %d",&n,&k);
        LL cnt0 = 0;//all 0
        for(int i = 0;i < n;i += 2) {
            cnt0 = (cnt0 + C(n,i)) % Mod;
        }
        LL sum = 1,ma = 0;
        for(int i = k - 1;i >= 0;--i) {
            LL pre = sum * cnt0 % Mod;
            if(n & 1) pre = (pre + sum) % Mod;
            else {
                LL ta = quick_mi(2,i);
                LL tmp = quick_mi(ta,n);
                ma = (ma + sum * tmp % Mod) % Mod;
            }
            sum = pre;
        }
        ans = 0;
        //dfs(1,quick_mi(2,k) - 1,1,0);
        printf("%lld\n",(sum + ma) % Mod);
    }

   // system("pause");
    return 0;
}
/*
30
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
*/

View Code

D:首先有个很直白的dp转移。

枚举i,j 得 dp[i] = dp[j] + i - j - 1 = i - 1 + dp[j] - j。

我们可以发现，贡献dp[j] - j 对于后面的所有i都是固定的。

那么我们就可以不去枚举j，只需要维护每个点上的最优的dp[j] - j即可。

但是这样我们需要去找到能转移到的位置，因为l,r都非常大，单纯操作很难实现。

所以用线段树，每次区间更新即可。

这里我们对所有点离散化，很显然的是每次更新的区间一定是以这些点某个为起点，某个为终点的一段区间。

线段树的节点要比3 * 10^ 5 稍微大一点。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 3e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int b[N << 1],tot = 0;
pii dp[N];//以i结尾的最小代价
struct PT{int id,L,r;}p[N];
vector<pii> vec[N];
vector<int> tmp;
struct Node{
    int L,r;
    pii mi,tag;
}node[M << 2];
void Pushup(int idx) {
    node[idx].mi = min(node[idx << 1].mi,node[idx << 1 | 1].mi);
}
void Pushdown(int idx) {
    if(node[idx].tag.first != INF) {
        node[idx << 1].mi = min(node[idx << 1].mi,node[idx].tag);
        node[idx << 1 | 1].mi = min(node[idx << 1 | 1].mi,node[idx].tag);
        node[idx << 1].tag = min(node[idx << 1].tag,node[idx].tag);
        node[idx << 1 | 1].tag = min(node[idx << 1 | 1].tag,node[idx].tag);
        node[idx].tag = pii{INF,0};
    }
}
void build(int L,int r,int idx) {
    node[idx].L = L,node[idx].r = r;
    node[idx].mi = pii{0,0},node[idx].tag = pii{INF,0};
    if(L == r) return ;
    int mid = (L + r) >> 1;
    build(L,mid,idx << 1);
    build(mid + 1,r,idx << 1 | 1);
    Pushup(idx);
}
void update(int L,int r,int idx,int val,int x) {
    if(node[idx].L >= L && node[idx].r <= r) {
        node[idx].mi = min(node[idx].mi,pii{val,x});
        node[idx].tag = min(node[idx].tag,pii{val,x});
        return ;
    }
    Pushdown(idx);
    int mid = (node[idx].L + node[idx].r) >> 1;
    if(mid >= L) update(L,r,idx << 1,val,x);
    if(mid < r) update(L,r,idx << 1 | 1,val,x);
    Pushup(idx);
}
pii query(int L,int r,int idx) {
    if(node[idx].L >= L && node[idx].r <= r) {
        return node[idx].mi;
    }
    int mid = (node[idx].L + node[idx].r) >> 1;
    pii ans = pii{INF,0};
    Pushdown(idx);
    if(mid >= L) ans = min(ans,query(L,r,idx << 1));
    if(mid < r) ans = min(ans,query(L,r,idx << 1 | 1));
    return ans;
}
int main() {
    int n,m;scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;++i) {
        scanf("%d %d %d",&p[i].id,&p[i].L,&p[i].r);
        b[++tot] = p[i].L;
        b[++tot] = p[i].r;
    }
    sort(b + 1,b + tot + 1);
    int len = unique(b + 1,b + tot + 1) - b - 1;
    for(int i = 1;i <= m;++i) {
        p[i].L = lower_bound(b + 1,b + len + 1,p[i].L) - b;
        p[i].r = lower_bound(b + 1,b + len + 1,p[i].r) - b;
        vec[p[i].id].push_back(pii{p[i].L,p[i].r});
    }
    //
    build(1,len,1);
    pii aw = pii{INF,0};
    for(int i = 1;i <= n;++i) {
        if(vec[i].size() == 0) continue;
        pii ans = pii{INF,0};
        for(auto v : vec[i]) {
            pii ma = query(v.first,v.second,1);
            if(ma.first < ans.first) ans = ma;
        }
        dp[i] = pii{ans.first + i - 1,ans.second};
        if(dp[i].first + n - i < aw.first) aw = pii{dp[i].first + n - i,i};
        for(auto v : vec[i]) {
            update(v.first,v.second,1,dp[i].first - i,i);
        }
    }
    printf("%d\n",aw.first);
    int st = aw.second + 1,ed = n;
    while(1) {
        for(int i = st;i <= ed;++i) {
            tmp.push_back(i);
        }
        st--;
        if(st == 0) break;
        ed = st - 1,st = dp[st].second + 1;
    }
    sort(tmp.begin(),tmp.end());
    for(int i = 0;i < tmp.size();++i) printf("%d%c",tmp[i],i == tmp.size() - 1 ? '\n' : ' ');
   // system("pause");
    return 0;
}
/*
10 10
1 1 3
2 3 5
3 6 7
4 6 8
5 5 6
6 1 9
1 5 6
8 1 7
9 6 9
6 2 10

68166 18
63298 985738188 992689056
2203 355239844 696319075
8854 595993093 799280088
26427 538844623 918748563
41682 556502456 619066716
10941 457988803 701375665
64736 344985083 352248221
16859 202018126 980132185
59044 188592792 388482952
8573 137177925 713474029
9776 520666123 812428119
5240 228179880 426886254
50918 716581051 901242637
67 205173754 748344203
51782 660629372 952279338
41380 404316378 896291922
56074 870784325 959859425
38627 265452519 524380796
*/

View Code

码农公寓

相关文章