[20181106][模拟赛]

题面

T1

思路

直接预处理出两个数组，然后用树状数组维护一下就行了。注意树状数组开两倍空间

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
map<int,int>ma;
const int N = 200000 + 100;
int mod;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int f[N],g[N];
int ls;
int tmp[N * 2];
ll qm(ll x,int y) {
    if(x == 0) return 0;
    ll ans = 1;
    x %= mod;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) ans = ans * x % mod;
    return ans;
}
int now;
int n;
void lisan() {
    sort(tmp + 1,tmp + ls + 1);
    tmp[0] = -1;
    for(int i = 1;i <= ls;++i) {
        if(tmp[i] != tmp[i-1]) 
            ma[tmp[i]] = ++now;
    }
    for(int i =1 ;i <= n;++i) {
        f[i] = ma[f[i]];
        g[i] = ma[g[i]];
    }
}
int tree[N * 10];
void add(int pos,int c) {
    while(pos <= now) {
        tree[pos] += c;
        pos += pos & -pos;
    }
}
int query(int pos) {
    int ans = 0;
    while(pos >= 1) {
        ans += tree[pos];
        pos -= pos & -pos;
    }
    return ans;
}
int main() {
    freopen("calc.in","r",stdin);
    freopen("calc.out","w",stdout);
    n = read();
    mod = read();
    for(int i = 1;i <= n;++i) {
        int k = read();
        f[i] = qm(i,k);
        g[i] = qm(k,i);
        tmp[++ls] = f[i];
        tmp[++ls] = g[i];
    }
    lisan();
    ll ans = 0;
    for(int i = n;i >= 1;--i) {
        ans += query(f[i] - 1);
        add(g[i],1);
    }
    cout<<ans;
    return 0;
}
/*
5 10000
3 1 5 4 2
*/

T2

思路

显然需要二分一下最小的有效值。然后当当前的防御力不够的时候，贪心的将当前点之后的第R个点的攻击力加上相差的值。容易证明这种贪心是对的。

这里的r是longlong类型的，结果二分的时候的mid是int类型的。然后死循环。。。。。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 500000 + 100;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int n;
int R;
ll K;
ll a[N];
ll sum[N],fy[N],tmp[N];
void pre() {
    for(int i = 1;i <= n;++i)
        sum[i] = sum[i-1] + a[i];
    for(int i = 1;i <= n;++i)
        fy[i] = sum[min(n,i + R)] - sum[max(1,i - R) -1];
}
int check(ll x) {
    memset(tmp,0,sizeof(tmp));
    ll re = 0,now = 0;
    for(int i = 1;i <= n;++i) {
        if(i - R >= 1) now -= tmp[i-R-1];
        ll z = x - fy[i] - now;
        if(z <= 0) continue;
        tmp[min(n,i + R)] += z;
        re += z;
        now += z;
        if(re > K) return 0;
    }
    return 1;
}
int main() {
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n = read(), R = read(),K = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    pre();
    ll r = 0;
    for(int i = 1;i <= n;++i) r = max(r,fy[i] + K);
    ll l = 0;
    ll ans = 0;
    while(l <= r) {
        ll mid = (l + r) >> 1;//!!!!
        if(check(mid)) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    cout<<ans;
    return 0;
}
/*
5 0 6
5 4 3 4 9
*/

T3

思路

考虑用并查集。发现w比k小，所以先预处理出来，然后再查询，将边排个序，给并查集赋个权值表示这个联通块的大小，然后在合并的时候统计最大联通块就行了。

用tmp[0]记录tmp数组的个数，结果二分的时候查询到了0这个位置。。。。。。。。。。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
queue<int>q;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node {
    int u,v,nxt,w;
}e[N << 1];
int head[N],ejs;
int n,m,Q;
void add(int u,int v,int w) {
    e[++ejs].v = v; e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
namespace BF1 {
    int ans[N],vis[N],tmp[N];
    int bfs(int U,int x) {
        while(!q.empty()) q.pop();
        q.push(U);
        vis[U] = 1;
        int re = 0;
        while(!q.empty()) {
            int u = q.front();q.pop();
            for(int i = head[u];i;i = e[i].nxt) {
                if(e[i].w > x) continue;
                int v = e[i].v;
                re += e[i].w;
                if(!vis[v]) q.push(v),vis[v] = 1;
            }
        }
        return re>>1;
    }
    int solve(int x) {
        memset(vis,0,sizeof(vis));
        int re = 0;
        for(int i = 1;i <= n;++i)
            if(!vis[i])
                re = max(re,bfs(i,x));
        return re;
    }
    int find(int x) {
        int l = 0,r = tmp[0];
        int re = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(tmp[mid] <= x) re = mid,l = mid + 1;
            else r = mid - 1;
        }
        return re;
    }
    void Main() {
        int NAME = 0;
        for(int i = 1;i <= m;++i) {
            int u = read(),v = read(),w = read();
            add(u,v,w);
            add(v,u,w);
            tmp[++tmp[0]] = w;
            NAME = max(NAME,w);
        }
        sort(tmp + 1,tmp + tmp[0] + 1);
        for(int i = 1; i <= tmp[0]; ++i) {
            ans[i] = solve(tmp[i]);
        }
        for(int i = 1;i <= Q;++i)
            printf("%d\n",ans[find(read())]);
    }
}
namespace BF2 {

    int fa[N],siz[N];
    bool cmp(node x,node y) {
        return x.w < y.w;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void uni(int x,int y) {
        x = find(x),y = find(y);
        if(rand() & 1) swap(x,y);
        fa[x] = y;
        siz[y] += siz[x];
        siz[x] = 0;
    }
    int tmp[N],ans[N];
    int query(int x) {
        int l = 1,r = tmp[0];
        int re = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(tmp[mid] <= x) re = mid,l = mid + 1;
            else r = mid - 1;
        }
        return re;
    }
    void Main() {
        for(int i = 1;i <= n;++i) fa[i] = i;
        for(int i = 1;i <= m;++i) e[i].u = read(),e[i].v = read(),e[i].w = read();
        sort(e + 1,e + m + 1,cmp);
        int now = 1;
        e[0].w = -1;
        for(int i = 1;i <= m;++i) {
            if(e[i].w != e[i-1].w) tmp[++tmp[0]] = e[i].w;
        }
        for(int i = 1;i <= tmp[0];++i) {
            ans[i] = ans[i-1];
            int x = tmp[i];
            while(e[now].w <= x && now <= m) {
                int k1 = find(e[now].u),k2 = find(e[now].v);
                if(k1 == k2) {
                    ans[i] = max(ans[i],siz[k2] + e[now].w);
                    siz[k2] += e[now].w;
                }
                else {
                    siz[k1] += e[now].w;
                    ans[i] = max(ans[i],siz[k1] + siz[k2]);
                    uni(k1,k2);
                }
                ++now;
            }
        }
        while(Q--) {
            int x = read();
            printf("%d\n",ans[query(x)]);
        }
    }
}
int main() {
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    srand(time(0));
    n = read(), m = read(),Q = read();

    BF2::Main();
    return 0;
}
/*
5 5 3
1 2 5
2 3 6
3 4 4
3 5 2
4 5 3
7
5
3



6  6 10
1 2 3
1 3 4
2 3 4
2 5 5 
5 3 3