285484026

CCPC-Wannafly Winter Camp Day1 Div2
爬爬爬山题解:因为我们往海拔高的走体力会下降,往海拔低的点走体力会上升,所以我们可以理解为体力势能[你到某座山的体...
扫描右侧二维码阅读全文
28
2019/01

CCPC-Wannafly Winter Camp Day1 Div2

爬爬爬山
题解:
因为我们往海拔高的走体力会下降,往海拔低的点走体力会上升,所以我们可以理解为体力势能[你到某座山的体力仅仅和这座山与第一座山的相对高度差]于是有一些山的海拔过高,如果我们不削就永远到达不了。于是我们在建图的时候如果要到达的点的高度过高就将这条上山的单向边权值变大,图建好了以后跑dij就好了。这个题目可能爆int所以得用long long
证明:
显然我们从起点到终点的路径上每个点只会出现一次,于是我们上文所写的建图,只用去这个点的时候付出相应的代价。

#include <bits/stdc++.h>

const long long MAXN = 500005,INF = (long long)100000000000LL;

using namespace std;

long long n,m,k,e;
long long h[MAXN],dist[MAXN],head[MAXN];
bool vis[MAXN];

pair<long long,long long> v;

struct node{
    long long v,c,next;
}edge[MAXN];

inline void addedge(long long u,long long v,long long c){
    edge[++e] = (node){v,c,head[u]};head[u] = e;
}

inline void init()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    
    for(int i = 1;i <= n;i++)
        scanf("%lld",&h[i]);
    
    long long u,v,c;
    for(int i = 1;i <= m;i++){
        scanf("%lld %lld %lld",&u,&v,&c);
        if(h[u]-h[1] > k) addedge(v,u,c+(h[u]-h[1]-k)*(h[u]-h[1]-k));
        else addedge(v,u,c);
        if(h[v]-h[1] > k) addedge(u,v,c+(h[v]-h[1]-k)*(h[v]-h[1]-k));
        else addedge(u,v,c);
    }
    
}

priority_queue<pair<long long,long long> >Q;
inline void dij(){
    for(int i = 1;i <= n;i++) dist[i] = INF;
    Q.push(make_pair(0,1) );dist[1] = 0;
    while(!Q.empty())
    {
        pair<long long,long long> x = Q.top();Q.pop();
        long long u = x.second;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u];i;i = edge[i].next){
            int v = edge[i].v;
            if(!vis[v] && dist[v] > dist[u] + edge[i].c){
                dist[v] = dist[u] + edge[i].c;
                Q.push(make_pair(-dist[v],v));
            }
        }
    }
    printf("%lld\n",dist[n]);
}

int main()
{
    init();
    
    dij();
    
    return 0;
}

吃豆豆

题解:设dpi[k]为到点(i,j)用k的时间能吃到的最多的豆子。那么状态转移方程就是dpi[k]=max(dpi[k-1],dpi-1[k-1],dpi[k-1],dpi[k-1],dpi[k-1])+k%Ti == 0 ? 1 : 0

#include <bits/stdc++.h>

const int MAXN = 20,INF = 10000000;

using namespace std;

int n,m,c,xs,ys,xt,yt;
int T[MAXN][MAXN],dp[MAXN][MAXN][20000];

inline void init()
{
    scanf("%d %d %d",&n,&m,&c);
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            scanf("%d",&T[i][j]);
    
    scanf("%d %d %d %d",&xs,&ys,&xt,&yt); 
    
    for(int i = 0;i <= n + 1;i++)
        for(int j = 0;j <= m + 1;j++)
            for(int k = 0;k < 20000;k++)
                dp[i][j][k] = -INF;
    
    dp[xs][ys][0] = 0;
}

inline int Max(int x,int y,int k){
    int tmp = dp[x][y][k-1];
    tmp = max(tmp,dp[x-1][y][k-1]);
    tmp = max(tmp,dp[x][y-1][k-1]);
    tmp = max(tmp,dp[x+1][y][k-1]);
    tmp = max(tmp,dp[x][y+1][k-1]);
    return tmp;
}

int main()
{
    init();
    
    for(int k = 1;k < 20000;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++){
                dp[i][j][k] = Max(i,j,k) + (k%T[i][j] == 0 ? 1 : 0);
            }

    for(int i = 1;i < 20000;i++)
        if(dp[xt][yt][i] >= c){
            printf("%d",i);
            break;
        }     
    
    return 0;
}

拆拆拆数
题解:如果A和B互质直接输出,如果不互质随机两个合法方案输出就好了

#include <bits/stdc++.h>

int T;
long long A,B;
long long ans1,ans2;

inline long long gcd(long long a,long long b){
    return b ? gcd(b,a%b) : a;
}

int main()
{
    srand(time(0));
    scanf("%d",&T);
    while(T--){
        scanf("%lld %lld",&A,&B);
        ans1 = gcd(A,B);
        if(ans1 == 1){
                printf("1\n%lld %lld\n",A,B);
        }
        else {
            ans1 = rand();ans2 = rand();
            while(ans1 <= 1 || ans2 <= 1 || A-ans1 <= 1 || B-ans2 <= 1){
                ans1 = rand();ans2 = rand();
            }
            
            while(!(gcd(ans1,B-ans2) == 1 && gcd(A-ans1,ans2) == 1)){
                ans1 = rand();ans2 = rand();
                while(ans1 <= 1 || ans2 <= 1 || A-ans1 <= 1 || B-ans2 <= 1){
                ans1 = rand();ans2 = rand();
                }    
            }
            
            printf("2\n%lld %lld\n%lld %lld\n",ans1,B-ans2,A-ans1,ans2);

        }
    }
    return 0; 
}

流流流动
题解:
首先有这样一个3n+1猜想,然后已经验证了在我们正常可以接触到的数据范围内的所有的数都会在有限次变换以后变成1,这就代表不存在某一个数字会在变换的时候陷入循环,那么按照本题目建图建出来的一定是一棵树。于是进行简单的树上dp就可以解决了。

设dp[x][0]为不取点x的情况,在x的子树中可以获得的最大权值
设dp[x][1]为取点x的情况下,在x的子树中可以获得的最大权值 
dp[x][1] += max(dp[v][0],dp[v][1] - d[min(x,v)]);
dp[x][0] += max(dp[v][1],dp[v][0]);
#include <bits/stdc++.h>

#define pb push_back

const int MAXN = 10000;

using namespace std;

int n;
int sum,f[MAXN],d[MAXN],vis[MAXN],dp[MAXN][3];

vector<int>E[MAXN];

void dfs(int x)
{
    vis[x] = true;
    dp[x][1] = f[x];
    for(int i = 0;i < E[x].size();i++){
        int v = E[x][i];
        if(!vis[v])
        {
            dfs(v);
            dp[x][1] += max(dp[v][0],dp[v][1] - d[min(x,v)]);
            dp[x][0] += max(dp[v][1],dp[v][0]);
        }
    }
}

int main()
{
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++)
        scanf("%d",&f[i]);
    
    for(int i = 1;i <= n;i++)
        scanf("%d",&d[i]);
    
    for(int i = 2;i <= n;i++){
        if(i%2) {
            if(3*i+1 <= n){
                E[i].pb(3*i+1);
                E[3*i+1].pb(i);
            }
        }
        else {
            E[i].pb(i/2);
            E[i/2].pb(i);
        }
    }
    
    for(int i = 1;i <= n;i++)
        if(!vis[i]){
            dfs(i);
            sum += max(dp[i][0],dp[i][1]);
        }
    
    printf("%d\n",sum);
    
    return 0;
}

夺宝奇兵

题意:
wls所在的王国有n个居民(不包括wls),他们共有m件神奇的宝物。
对于第i件宝物,wls可以花费$a_i$
的金币把它从原来的主人那里买过来。
请问wls最少要准备多少金币,才能使他成为宝物最多的人(wls的宝物件数严格比其他所有人多)?
题解:
我们枚举一个X,代表别的居民最多拥有的宝物数量为X,那么我们就把大于X的最便宜的宝物全部收购,然后如果我们拥有的宝物数量还不是最多的,就买别人还拥有的宝物中最便宜的宝物
Div2:只用直接排序就好了

#include <bits/stdc++.h>

const int MAXN = 1005;

using namespace std;

long long n,m,tmp;
long long a[MAXN],c[MAXN],Max,cnt[MAXN],sum[MAXN],num[MAXN];

long long d[MAXN][MAXN];

vector<long long>Q;

inline bool cmp(const long long &A,const long long &B){
    return A > B;
}

inline void init()
{
    scanf("%lld %lld",&n,&m);
    
    long long v,c; 
    
    for(int i = 1;i <= m;i++){
        scanf("%lld %lld",&c,&v);
        d[v][++cnt[v]] = c;
    }
    
    for(int i = 1;i <= n;i++) {
        Max = max(Max,cnt[i]);
        sort(d[i]+1,d[i]+cnt[i]+1,cmp);
    }

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= cnt[i];j++){
            sum[j] += d[i][j];
            if(d[i][j]) num[j]++;
        }
    }
    
    for(int i = Max-1;i >= 1;i--){
        sum[i] += sum[i+1];
        num[i] += num[i+1];
    }
    
}

int main()
{
    init();
    long long ans = 1;
    ans <<= 60;
    
    for(int i = 0;i <= Max;i++)
    {
        tmp = 0;
        tmp += sum[i+1];
        if(num[i+1] <= i){
            long long need = 1;
            need += i - num[i+1];
            if(Q.size() >= need){
                for(int i = 0;i < need;i++){
                    tmp += Q[i];
                }
                ans = min(tmp,ans);
            }
        }
        else ans = min(tmp,ans);
        for(int j = 1;j <= n;j++)
            if(d[j][i+1]) Q.push_back(d[j][i+1]);
        sort(Q.begin(),Q.end());
    }
    
    printf("%lld\n",ans);
    
    return 0;
}

Div1:可以用权值线段树来加速

#include <bits/stdc++.h>

const int MAXN = 1000000;

#define lson o<<1,L,M
#define rson o<<1|1,M+1,R

using namespace std;

long long n,m,Max,ans,tmp,tmp1,tmp2,top,x;
long long Hash[MAXN],sum1[MAXN],sum2[MAXN];

vector<long long>d1[MAXN],d2[MAXN];

struct node{
    long long sum,num;
}T[MAXN];

inline long long read()
{
    long long x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
} 

inline bool cmp(const long long &A,const long long &B){
    return A > B;
}

inline void init()
{
    n = read();m = read();
    
    long long a,c;
    
    for(int i = 1;i <= m;i++){
        a = read();c = read();
        d1[c].push_back(a);
        Hash[++top] = a;
    }
    
    sort(Hash+1,Hash+top+1);
    top = unique(Hash+1,Hash+top+1) - Hash;
    top--;
    
    for(int i = 1;i <= n;i++)
        if(d1[i].size())
            sort(d1[i].begin(),d1[i].end(),cmp);
    
    for(int i = 1;i <= n;i++)
        for(int j = 0;j < d1[i].size();j++){
            sum1[j+1] += d1[i][j];
            sum2[j+1]++;
            Max    = max(Max,(long long)d1[i].size());
            d2[j+1].push_back(d1[i][j]);
        }
    
    for(int i = Max-1;i >= 1;i--){
        sum1[i] += sum1[i+1];
        sum2[i] += sum2[i+1];
    }
}

void update(int o,int L,int R){
    if(L == R){
        T[o].num++;
        T[o].sum += Hash[x];
        return;
    }
    int M = L + R >> 1;
    if(x <= M) update(lson);
    else update(rson);
    
    T[o].num = T[o<<1].num + T[o<<1|1].num;
    T[o].sum = T[o<<1].sum + T[o<<1|1].sum;
    
}

void query(int o,int L,int R){
    if(L == R){
        tmp1 += tmp2*Hash[L];
        return;
    }
    int M = L + R >> 1;
    if(tmp2 <= T[o<<1].num) query(lson);
    else {
        tmp1 += T[o<<1].sum;
        tmp2 -= T[o<<1].num;
        query(rson);
    }
}

int main()
{
    init();
    ans = sum1[1];
    for(int i = 0;i <= Max;i++){
        tmp1 = sum1[i+1];tmp2 = sum2[i+1]; 
        if(tmp2 + T[1].num > i) {
            tmp2 = i - sum2[i+1] + 1;
            if(tmp2 > 0) query(1,1,top);
            ans = min(ans,tmp1);
        }
        for(int j = 0;j < d2[i+1].size();j++){
            x = lower_bound(Hash+1,Hash+top+1,d2[i+1][j]) - Hash;
            update(1,1,top);
        }
    }
    
    printf("%lld\n",ans);
    
    return 0;
} 
Last modification:January 31st, 2019 at 11:40 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment