WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
CCPC 2018中国大学生程序设计竞赛 – 网络选拔赛
CCPC 2018中国大学生程序设计竞赛 – 网络选拔赛

1001 Buy and Resell

http://acm.hdu.edu.cn/showproblem.php?pid=6438

一件商品在n天中有不同价值a_1, a_2, \cdots , a_n。第i天可以以a_i价格买入一件商品或者a_i价格卖出一件商品或者什么也不做。
问:通过n天的操作,最多可以获利多少钱,同时保证获利最大的情况下,最少进行多少次买入卖出操作。

经过手玩可以发现,模拟的过程中一天如果确认购买商品,那么就不会改变了。只有某一天我想要卖出商品时,可以会存在后期有价格更高的日子导致今天不卖或者今天反而买入的情况。
所以,可以使用两个维护商品价值最小值的优先队列:一个队列存储所有没有考虑状态的日子,另一个存储所有当前认为这天卖出商品的日子。
如果到了第i天,商品价值为a_i,没有考虑状态的日子队列中商品最小值为u,日子为D_u,认为卖出日子队列中商品最小值为v,日子为D_v
我们发现,如果令当前天卖出,D_u天买入,我们可以增加获利a_i-u,但是增加两次操作。如果令当前天卖出,D_v天不再卖出,我们可以增加获利a_i-v,操作数不变。
1. 如果a_i-ua_i-v不同且较大值大于0,那么我们让当前天卖出,并进行较大值的那种操作。
2. 如果相同且均大于0,考虑到操作数最少,我们要撤销D_v卖出,改为当前天卖出操作。
3. 如果两种操作都不能获利,那么我们就把当前天扔进未考虑队列中,等待之后处理。
像这样贪心模拟之后输出答案即可。

/**
* Author : WNJXYK
* Date : 20180825
* Problem : 1001
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n;
struct Node{
    LL v;
    int i;
    friend bool operator < (const Node &a, const Node &b){
        if (a.v!=b.v) return a.v>b.v;
        return a.i>b.i;
    }
} node[MAXN];
int idx[MAXN];

LL ans=0; int ops=0;
priority_queue<Node> fre, sel;

inline bool Buy(int i){
    if (fre.size()==0) return true;
    Node x=fre.top(); fre.pop();
    if (x.v<node[i].v){
        ops+=2; ans=ans+node[i].v-x.v;
        sel.push(node[i]);
        //printf("Buy %d Sell %d\n", x.i, i);
        return false;
    }else fre.push(x);
    return true;
}

inline bool Resel(int i){
    if (sel.size()==0) return true;
    Node x=sel.top(); sel.pop();
    if (x.v<node[i].v){
        ans=ans+node[i].v-x.v;
        fre.push(x); sel.push(node[i]);
        //printf("Cancel %d Sell %d\n", x.i, i);
        return false;
    }else sel.push(x);
    return true;
}

inline void solve(int T){
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
        scanf("%lld", &node[i].v), node[i].i=i;

    ans=ops=0;
    while(!fre.empty()) fre.pop();
    while(!sel.empty()) sel.pop();
    for (int i=1; i<=n; i++){
        bool flag=true;
        if (sel.size()>0 && fre.size()>0 && sel.top().v<=fre.top().v) flag=Resel(i);
        if (flag) flag=Buy(i);
        if (flag) flag=Resel(i);
        if (flag) fre.push(node[i]);
    }

    printf("%lld %d\n", ans, ops);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

1003 Dream

http://acm.hdu.edu.cn/showproblem.php?pid=6440

在模P空间下构造一个加法&乘法的代数系统,使得其满足(n+m)^p=n^p+m^p

经过一番思考,发现这个式子本来就是成立的?(n+m)^p \equiv n+m \equiv n^p+m^p,所以直接输出就行了。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define sz sizeof
#define pb push_back

int ans[1100][1100];

void output(int p) {
    for(int i = 0; i < p; ++i) {
        for(int j = 0; j < p; ++j) {
            if(j)
                printf(" ");
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int t; scanf("%d", &t);
    for(int i = 1; i <= t; ++i) {
        int p; scanf("%d", &p);
        for(int i = 0; i < p; ++i)
            for(int j = 0; j < p; ++j)
                ans[i][j]= (i + j) % p;
        output(p);
        for(int i = 0; i < p; ++i)
            for(int j = 0; j < p; ++j)
                ans[i][j] = (i * j) % p;
        output(p);
    }
    return 0;
}

1004 Find Integer

http://acm.hdu.edu.cn/showproblem.php?pid=6441

给定A, n,求一组满足要求的B, C,使得A^n + B^n = C^n成立。

可以很容易的知道,当n=0n\geq 3的时候是没有解的,直接输出-1~-1即可。
1. 当n=1的时候,令B=1, C=A+1即可。
2. 当n=2的时候,我们可以用平方差公式得到A^2=C^2-B^2=(C+B)(C-B)
A的奇偶情况讨论一下就行: A为奇数,C=\frac{A^2+1}{2}, B=\frac{A^2-1}{2}; A为偶数,C=\frac{\frac{A^2}{2}+2}{2},B=\frac{\frac{A^2}{2}-2}{2}

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define lowbit(x) x&-x
#define mp make_pair

using namespace std;

const int MOD = 1000000007;
const int N = 1000010;
const int M = 100010;
const int INT_INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
struct Point{
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
};
typedef Point Vector;

LL Abs(LL x) { if(x > 0) return x; return -x; }
LL Gcd(LL m, LL n) { LL r = m%n; while(r) { m = n; n = r; r = m%n; } return n; }
LL Pow(LL m, LL n) { LL ans = 1; while(n) { if(n&1) ans = ans*m%MOD; n >>= 1; m = m*m%MOD; } return ans; }

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, a;
        scanf("%d%d", &n, &a);
        if(n == 0) printf("-1 -1\n");
        else if(n == 1) printf("1 %d\n", a+1);
        else if(n == 2) {
            LL tmp = 1LL*a*a;
            if(a%2 == 1) printf("%lld %lld\n", (tmp-1)/2, (tmp+1)/2);
            else printf("%lld %lld\n", (tmp/2-2)/2, (tmp/2+2)/2);
        }
        else printf("-1 -1\n");
    }
}

1005 GuGu Convolution

给定A, B, n,求\sum_{i=0}^{n} C_n^iA^{n-i} \sqrt{B}^i [i\equiv1(MOD~2)]
我们发现这就是消除了偶数项的二项式展开,我们可以考虑两个二项式相加消除偶数项:\frac{(A+\sqrt{B})^n+(A-\sqrt{B})^n}{2}
又因为我们要求的是带\sqrt{B}项的,所以只需要算(A+\sqrt{B})^n,保留p+q\sqrt{B}中的q\sqrt{B}即可。
所以,使用快速幂计算这个带根号的数字即可。

/**
* Author : WNJXYK
* Date : 20180825
* Problem : 1005
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

LL n;
LL A, B, P;
LL t, b;
LL ans[2], mul[2], tmp[2];
inline void multi(LL numA[], LL numB[]){
    tmp[0]=1LL*numA[0]*numB[0]%P+1LL*numA[1]*numB[1]%P*b%P;
    tmp[1]=1LL*numA[0]*numB[1]%P+1LL*numA[1]*numB[0]%P;
    numA[0]=tmp[0]%P; numA[1]=tmp[1]%P;
}

inline void solve(int T){
    scanf("%lld%lld%lld%lld", &A, &B, &n, &P);

    t=b=1;
    for (LL i=2; i*i<=B; i++){
        if (B%i==0){
            int c=0;
            while(B%i==0) B/=i, ++c;
            for (int j=1; j+j<=c; j++) t=t*i%P;
            if (c&1) b=b*i;
        }
    }
    b*=B; t%=P;

    ans[0]=1; ans[1]=0;
    mul[0]=A%P; mul[1]=t%P;
    while(n){
        if (n&1LL) multi(ans, mul);
        n>>=1LL; multi(mul, mul);
    }

    printf("1 %lld %lld\n", ans[1]%P, b);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

1007 Neko’s loop

http://acm.hdu.edu.cn/showproblem.php?pid=6444

给定一个数列A_0, A_1, \cdots, A_{n-1},到达一个位置即获得此位置的数值(可以重复获得)。问:选择一个开始点,每次可以从x跳到(x+K)\%n,至多跳m步的最大获利是多少。

我们发现,这种每次可以从x跳到(x+K)\%n的跳法,会将原序列分成若干个不相交的环。每个环上我们只需要处理出不超过m步的最大连续子序列。如果m大于环的长度l且环权值和为正,我们可以先绕环贪心的走max(m/l-1, 0),然后用剩余的步数做一个最大字段和,否则直接做一个最大字段和即可。

/**
* Author : WNJXYK
* Date : 20180825
* Problem : 1007.cpp
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e4+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, K;
LL S, M, num[MAXN];
bool vis[MAXN];

int tot;
LL val[MAXN*4], sum[MAXN*4];
LL gAns=0;

list<int> Q;

void calc(int x){
    LL cir=0, ans=0, rate=0, m=M;
    // Gen Circle
    for (tot=0; vis[x]==false; x=(x+K)%n) val[++tot]=num[x], vis[x]=true;
    //for (int i=1; i<=tot; i++) printf("%lld ", val[i]); printf(" #\n");
    // Repeat Circle
    for (int i=1; i<=tot; i++) cir+=val[i];
    if (cir>0){
        LL g=max(0LL, m/tot-1);
        rate+=g*cir, m-=g*tot;
    }
    //printf("Rate:%lld\n", rate);
    // Double Circle
    for (int i=1; i<=tot; i++) val[i+tot+tot+tot]=val[i+tot+tot]=val[i+tot]=val[i]; tot*=4;
    // DP
    sum[0]=0; for (int i=1; i<=tot; i++) sum[i]=sum[i-1]+val[i];
    // Special
    while(!Q.empty()) Q.pop_back();
    Q.push_front(0);
    for (int i=1; i<=tot; i++){
        while(!Q.empty() && sum[Q.front()] > sum[i]) Q.pop_front();
        Q.push_front(i);
        while(!Q.empty() && i-Q.back()>m) Q.pop_back();
        ans=max(ans, sum[i]-sum[Q.back()]);
    }
    //cout<<m<<" "<<ans<<endl;
    // Check
    gAns=min(gAns, S-ans-rate);
}

inline void solve(int T){
    scanf("%d%lld%lld%d", &n, &S, &M, &K); gAns=S;
    for (int i=0; i<n; i++) scanf("%lld", &num[i]);
    for (int i=0; i<n; i++) vis[i]=false;
    for (int i=0; i<n; i++) if (!vis[i]) calc(i);
    printf("Case #%d: %lld\n", T, max(0LL, gAns));
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

1009 Tree and Permutation

http://acm.hdu.edu.cn/showproblem.php?pid=6446

答案为\sum_{i=1}{n}\sum_{j=1}{n}Dist(i, j) (n-1)!,所以我们只需要统计树上任意两点的距离之和即可。我们考虑统计每一条边的贡献,每一条边会被计算它左边点数乘右边点数次,DFS统计即可。

/**
* Author : WNJXYK
* Date : 20180825
* Problem : 1009
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=1e9+7;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n;

struct Edge{
    int v, nxt, len;
    Edge(){}
    Edge(int v0, int n0, int l0){
        v=v0;
        nxt=n0;
        len=l0;
    }
}e[MAXN*2+5];
int head[MAXN], nume;

inline void addEdge(int u, int v, int w){
    e[++nume]=Edge(v, head[u], w);
    head[u]=nume;
    e[++nume]=Edge(u, head[v], w);
    head[v]=nume;
}

LL ans, cnt[MAXN];
void dfs(int x, int from){
    cnt[x]=1;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (v==from) continue;
        LL w=e[i].len;
        dfs(v, x);
        cnt[x]+=cnt[v];
        ans=(ans+w*cnt[v]%MOD*(1LL*n-cnt[v])%MOD)%MOD;
    }
}

LL fac[MAXN];
inline void solve(){
    memset(head, 0, sizeof(head)); nume=0;

    for (int i=1; i<n; i++){
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        addEdge(x, y, w);
    }

    ans=0;
    dfs(1, 0);
    ans=ans*fac[n-1]%MOD;
    ans=ans*2LL%MOD;

    printf("%lld\n", ans);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    fac[0]=1; for(int i=1; i<MAXN; i++) fac[i]=fac[i-1]*i%MOD;
    while(scanf("%d", &n)!=EOF) solve();
    return 0;
}

1010 YJJ’s Salesman

http://acm.hdu.edu.cn/showproblem.php?pid=6447

给定一张网格图,可以从(x, y)走到(x+1, y), (x, y+1), (x+1, y+1),但只有去往(x+1, y+1)的时候才可以获得(x+1, y+1)这个位置的权值。问从(0, 0)出发的最大能获得权值和是多少。

我们先对X轴排序,现在对于每一个格子,我们可以考虑的获得权值转移过来的节点只有排序在当前节点之前(X轴坐标小于自己)且Y轴坐标小于自己的格子。这是一个区间,所以我们可以考虑使用线段树表示X坐标小于当前格子的所有格子中Y坐标等于p的最大权值和。
那么转移就相当于线段树上的区间查询,修改是单点修改。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define lowbit(x) x&-x
#define mp make_pair

using namespace std;

const int MOD = 1000000007;
const int N = 100010;
const int M = 100010;
const int INT_INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
struct Point{
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
};
typedef Point Vector;

LL Abs(LL x) { if(x > 0) return x; return -x; }
LL Gcd(LL m, LL n) { LL r = m%n; while(r) { m = n; n = r; r = m%n; } return n; }
LL Pow(LL m, LL n) { LL ans = 1; while(n) { if(n&1) ans = ans*m%MOD; n >>= 1; m = m*m%MOD; } return ans; }

struct node{
    int x, y, v;
}f[N];
int tr[N<<2], seq[N], dp[N];

int cmp(const node&a, const node&b) { return a.x < b.x; }

void update(int rt, int l, int r, int x, int y) {
    if(l == r) {
        tr[rt] = max(tr[rt], y); return ;
    }
    int mid = (l+r)/2;
    if(x <= mid) update(lson, x, y);
    else update(rson, x, y);
    tr[rt] = max(tr[rt<<1], tr[rt<<1|1]);
}

int query(int rt, int l, int r, int s, int t) {
    if(s<=l && r<=t) return tr[rt];
    int mid = (l+r)/2, ans = 0;
    if(s <= mid) ans = query(lson, s, t);
    if(t > mid) ans = max(ans, query(rson, s, t));
    return ans;
}

void init() {
    memset(tr, 0, sizeof(tr));
}

int main() {
    //freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        init();
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &f[i].x, &f[i].y, &f[i].v);
            seq[i] = f[i].y;
        }
        sort(f+1, f+n+1, cmp);
        sort(seq+1, seq+n+1);
        for(int i = 1; i <= n; i++) f[i].y = lower_bound(seq+1, seq+n+1, f[i].y)-seq;
        for(int i = 1; i <= n; i++) {
            if(f[i].x != f[i-1].x) {
                int j = i-1;
                while(j && f[j].x == f[i-1].x) {
                    update(1, 1, n, f[j].y, dp[j]);
                    j--;
                }
            }
            int ans = 0;
            if(f[i].y > 1) ans = query(1, 1, n, 1, f[i].y-1);
            dp[i] = ans+f[i].v;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);
        printf("%d\n", ans);
    }
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

CCPC 2018中国大学生程序设计竞赛 – 网络选拔赛
1001 Buy and Resell http://acm.hdu.edu.cn/showproblem.php?pid=6438 一件商品在$n$天中有不同价值$a_1, a_2, \cdots , a_n$。第$i$天可以以$a_i$价格买入一件商品或者以$a_i$价格卖…
扫描二维码继续阅读
2018-08-25
<--! http2https -->