首页 > 其他 > 详细

2018CCPC吉林赛区

时间：2019-10-19 23:15:46      阅读：56      评论：0      收藏：0      [点我收藏+]

传送门

A - The Fool

整除分块即可。

B - The World

模拟即可。

C - Justice

题意：
给出\(n\)个数\(k_i\)，每个数的权值为\(\frac{1}{2^{k_i}}\)。
现在问能否将这些数划分为两个集合，使得每个集合里面数的权值和不小于\(\frac{1}{2}\)。
若合法，输出任意一种方案。

思路：

  • 对于两个相同的\(k\)，一定能够合并为\(k-1\)。
  • 直接数组存储显然存不下，我们可以直接合并到\(k-x\)，满足\(k-x\)存在，也就是说我们每次将\(a_i\)减小到\(a_{i-1}\)，时间复杂度最多为\(O(logn)\)。
  • 模拟这个过程就行了，后面输出方案的时候找到一个阀值即可。

说起来感觉比较简单，写起来没那么简单，细节很多。。后面寻找方案的时候也套了个二分（可能我姿势水平太低了）。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n;
pii a[N], b[N], c[N];
int Case;
int bel[N], ans[N];

bool ok(int x, int y) {
    while(x != 1 && y >= 2) {
        --x; y /= 2;
    }
    if(x == 1) return true;
    return false;
}

void run() {
    ++Case;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].fi;
        a[i].se = i;
        bel[i] = ans[i] = 0;
    }
    sort(a + 1, a + n + 1);
    int tot = 0;
    for(int i = 1, j; i <= n; i = j) {
        j = i;
        while(j <= n && a[i].fi == a[j].fi) ++j;
        b[++tot] = MP(a[i].fi, j - i);
        for(int k = i; k < j; k++) bel[k] = tot;
    }
    b[0] = MP(1, 0);
    for(int i = 0; i <= tot; i++) c[i] = b[i];
    for(int i = tot; i > 0; i--) {
        int x = b[i].se;
        int now = b[i].fi, pre = b[i - 1].fi;
        while(now != pre && x >= 2) {
            x /= 2;
            --now;
        }       
        if(now == pre) b[i - 1].se += x;
    }
    cout << "Case " << Case << ": ";
    if(b[0].se >= 2) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
        return;
    }
    if(a[1].fi == 1) {
        ans[a[1].se] = 1;
        for(int i = 1; i <= n; i++) {
            cout << ans[i];
        }
        cout << '\n';
        return;
    }
    int need = 0, t = 0;
    for(int i = tot; i > 0; i--) {
        int x = c[i].se;
        int now = c[i].fi, pre = c[i - 1].fi;
        if(ok(now, x)) {
            int l = 1, r = x + 1, mid;
            while(l < r) {
                mid = (l + r) >> 1;
                if(ok(now, mid)) r = mid;
                else l = mid + 1;
            }
            t = tot + 1, need = r; break;
        }
        while(now != pre && x >= 2) {
            x /= 2;
            --now;
        }
        if(now != pre) x = 0;
        int k1 = c[i - 1].fi, k2 = c[i - 1].se + x;
        if(ok(k1, k2)) {
            int l = x, r = k2 + 1, mid;
            while(l < r) {
                mid = (l + r) >> 1;
                if(ok(k1, mid)) r = mid;
                else l = mid + 1;
            }
            need = r - x; t = i; break;
        }
        c[i - 1].se += x;
    }
    for(int i = 1; i <= n; i++) {
        if(bel[i] >= t) {
            ans[a[i].se] = 1; 
        } else if(bel[i] == t - 1 && need) {
            ans[a[i].se] = 1; --need;
        } else ans[a[i].se] = 0;
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

?
有一种更加简单优美的做法：并查集+优先队列。
并查集就维护合并路径，还是比较巧妙。
细节见代码：


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n;
int a[N];
int Case;

int f[N];
int find(int x) {
    return f[x] == x ? f[x] : f[x] = find(f[x]);
}
void run() {
    cout << "Case " << ++Case << ": ";
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i <= n; i++) {
        f[i] = i;
    }
    priority_queue <pii> q;
    for(int i = 1; i <= n; i++) {
        q.push(pii(a[i], i));
    }
    while(!q.empty() && q.top().fi > 1) {
        pii now = q.top(); q.pop();
        if(q.empty()) break;
        if(now.fi != q.top().fi) continue;
        pii cur = q.top(); q.pop();
        int fx = find(now.se), fy = find(cur.se);
        if(fx < fy) swap(fx, fy);
        f[fx] = fy;
        q.push(pii(now.fi - 1, fy));
    }
    if(q.size() <= 1) {
        cout << "NO" << '\n';
    } else {
        cout << "YES" << '\n';
        for(int i = 1; i <= n; i++) {
            if(find(i) == q.top().se) cout << 1;
            else cout << 0;
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

D - The Moon

数学期望，就考虑几种情况就行，倒着来推，递推式详见代码：(因为有\(1.5\%\)，所以是千分位)


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e3+5;
typedef double db;
int t,p;
db f[MAXN];
db g(int x){
    return f[min(x,1000)];
}
int main() {
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++){
        scanf("%d",&p);
        f[1000] = 100.0/p;
        for(int i=995;i>=20;i-=5)
            f[i] = (p/100.0)*(i/1000.0) + (p/100.0)*((1000-i)/1000.0)*(1+g(i+20)) + (100-p)/100.0*(1+g(i+15));
        printf("Case %d: %.7f\n",kase,f[20]);
    }
    return 0;
}

F - The Hermit

仔细分析一下题目条件就很好做了，每一个位置答案为\(a_i-2\)。

H - Lovers

题意：
一开始有\(n\)个空串\(s_1,s_2,\cdots,s_n\)，然后执行\(m\)次操作，操作分为两种：

  • \(w\ l\ r\ d:\)给\(l\)到\(r\)位置上的所有子串两边加上\(d\)，相当于\(s_i\)变为\(ds_id,l\leq i\leq r\)；
  • \(q\ l\ r:\)询问\(\sum_{i=l}^r value*(s_i)(mod\ 10^9+7)\)。

思路：
硬核线段树。
考虑若对一个位置施加一次操作，结果为：
\[ 10\cdot d\cdot sum_2+10\cdot sum+d \]
其中\(sum\)表示对应区间的答案和，\(sum_2\)表示对应区间的\(\sum 10^{len_i}\)。
三个的含义分别是头、中、尾部。
手玩一下，发现如果施加三次操作，结果将变为：
\[ 10^3\cdot sum_2\cdot [d_3d_2d_1]+10^3\cdot sum+[d_1d_2d_3] \]
那么我们可以发现，我们维护懒标记时，可以单独维护\([d_1\cdots d_n],[d_n\cdots d_1],10^{len}\)，这样懒标记的更新也很好更新，懒标记下传时直接对应乘起来即可。
其中\([d_1d_2\cdots d_n]\)表示\(value(d_1d_2\cdots d_n)\)。

一开始细节没有想清楚，感觉还是有点遗憾。
注意一下\(sum_2\)的更新。
详见代码：


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 1e9 + 7;

int Case;
int n, m;
int sum[N << 2], sum2[N << 2];
int llz[N << 2], rlz[N << 2], lenlz[N << 2];
char s[10];

void push_up(int o) {
    sum[o] = (sum[o << 1] + sum[o << 1|1]) % MOD;
    sum2[o] = (sum2[o << 1] + sum2[o << 1|1]) % MOD;
}

void upd(int son, int fa, int l, int r) {
    sum[son] = (1ll * lenlz[fa] * sum2[son] % MOD * llz[fa] % MOD + 
                1ll * lenlz[fa] * sum[son] % MOD + 
                1ll * rlz[fa] * (r - l + 1) % MOD) % MOD;
    sum2[son] = 1ll * lenlz[fa] * lenlz[fa] % MOD * sum2[son] % MOD;
    llz[son] = (1ll * llz[fa] * lenlz[son] % MOD + llz[son]) % MOD;
    rlz[son] = (1ll * rlz[son] * lenlz[fa] % MOD + rlz[fa]) % MOD;
    lenlz[son] = 1ll * lenlz[son] * lenlz[fa] % MOD;
}

void push_down(int o, int l, int r) {
    if(lenlz[o] > 1) {
        int mid = (l + r) >> 1;
        upd(o << 1, o, l, mid);
        upd(o << 1|1, o, mid + 1, r);
        lenlz[o] = 1;
        llz[o] = rlz[o] = 0;
    }
}

void build(int o, int l, int r) {
    llz[o] = rlz[o] = 0;
    lenlz[o] = 1;
    if(l == r) {
        sum[o] = 0; sum2[o] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1|1, mid + 1, r);
    push_up(o);
}

void update(int o, int l, int r, int L, int R, int d) {
    if(L <= l && r <= R) {
        sum[o] = (1ll * sum[o] * 10 % MOD + 1ll * d * (r - l + 1) % MOD + 1ll * 10 * d * sum2[o] % MOD) % MOD;
        sum2[o] = 1ll * sum2[o] * 100 % MOD;
        
        llz[o] = (1ll * lenlz[o] * d % MOD + llz[o]) % MOD;
        rlz[o] = (1ll * rlz[o] * 10 + d) % MOD;
        lenlz[o] = 1ll * lenlz[o] * 10 % MOD;
        return;
    }
    push_down(o, l, r);
    int mid = (l + r) >> 1;
    if(L <= mid) update(o << 1, l, mid, L, R, d);
    if(R > mid) update(o << 1|1, mid + 1, r, L, R, d);
    push_up(o);
}

int query(int o, int l, int r, int L, int R) {
    if(L <= l && r <= R) {
        return sum[o];
    }
    push_down(o, l, r);
    int mid = (l + r) >> 1, res = 0;
    if(L <= mid) res = (res + query(o << 1, l, mid, L, R)) % MOD;
    if(R > mid) res = (res + query(o << 1|1, mid + 1, r, L, R)) % MOD;
    return res;
}

void run() {
    ++Case;
    cout << "Case " << Case << ":" << '\n';
    cin >> n >> m;
    build(1, 1, n);
    while(m--) {
        cin >> s;
        int l, r, d;
        if(s[0] == 'w') {
            cin >> l >> r >> d;
            update(1, 1, n, l, r, d);
        } else {
            cin >> l >> r;
            int ans = query(1, 1, n, l, r);
            cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

I - Strength

游戏王，憨憨贪心，分两种情况就行。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5+5;
int t,n,m,a[MAXN],b[MAXN],c[MAXN];
multiset<int> st;
bool vis[MAXN];
int main(){
    cin>>t;
    for(int kase=1;kase<=t;kase++){
        cin>>n>>m;
        for(int i=1;i<=n;i++)vis[i]=0;
        st.clear();
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=m;i++)cin>>b[i];
        int k=0;
        for(int i=1;i<=m;i++){
            int x;
            cin>>x;
            if(x==1)st.insert(b[i]);
            else c[++k] = b[i];
        }
        sort(a+1,a+1+n);
        sort(c+1,c+1+k);
        ll ans=0;
        for(int i=1;i<=n;i++){
            auto it = st.lower_bound(a[i]);
            if(*it == a[i]){
                st.erase(it);
                vis[i]=1;
            }else if(it!=st.begin()){
                it--;
                st.erase(it);
                vis[i]=1;
            }
        }
        ll sum = 0;
        if(st.size()==0){
            int j=1;
            for(int i=n;i>=1;i--){
                if(vis[i])continue;
                if(j<=k)sum += max(0,a[i] - c[j++]);
                else sum += a[i];
            }
        }
        ans = sum;
        int j=1;
        sum=0;
        for(int i=n;i>=1&&j<=k;i--){
            sum += max(0,a[i]-c[j++]);
        }
        ans=max(ans,sum);
        cout<<"Case "<<kase<<": "<<ans<<'\n';
    }
    return 0;
}

2018CCPC吉林赛区

原文：https://www.cnblogs.com/heyuhhh/p/11706054.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！