2018CCPC网络赛

A - Buy and Resell

The Power Cube is used as a stash of Exotic Power. There are

n

InputThere are multiple test cases. The first line of input contains a positive integer $T$ OutputFor each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.Sample Input

Sample Output

16 4
5 2
0 0

Hint

In the first case, he will buy in 1, 2 and resell in 3, 4. 
         
  profit = - 1 - 2 + 10 + 9 = 16
In the second case, he will buy in 2 and resell in 4. 
         
  profit = - 5 + 10 = 5
In the third case, he will do nothing and earn nothing. 
         
  profit = 0

利用pq贪心去看看那天选择了

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define val first
#define pos second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
struct T
{
    int v,cnt;
    friend bool operator <(T a,T b)
    {
        if(a.v==b.v) return a.cnt<b.cnt;
        return a.v>b.v;
    }
};
priority_queue<T>Q;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        ll ans=0,cnt=0;
        for(int i=1,x,y; i<=n; i++)
        {
            cin>>x;
            if(!Q.empty())
            {
                y=Q.top().v;
                if(y<x)Q.pop(),ans+=x-y,Q.push({x,1});
            }
            Q.push({x,0});
        }
        while(!Q.empty())cnt+=Q.top().cnt,Q.pop();
        cout<<ans<<" "<<cnt*2<<"
";
    }
    return 0;
}

CF上的神仙代码

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define val first
#define pos second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
multiset<pll> pq,se1,se2;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        pq.clear(),se1.clear(),se2.clear();
        cin>>n;
        for(int i=1,x,y; i<=n; i++)
        {
            cin>>x;
            pq.insert({x, i});
            y=(*pq.begin()).val;
            if(y<x)
            {
                if(se2.empty()||(*se2.begin()).val>y)
                {
                    se1.insert(*pq.begin());
                    pq.erase(pq.begin());
                    se2.insert({x,i});
                    pq.erase(pq.find({x,i}));
                }
                else
                {
                    pq.insert(*se2.begin());
                    se2.erase(se2.begin());
                    se2.insert({x,i});
                    pq.erase(pq.find({x,i}));
                }
            }
            else if(!se2.empty()&&(*se2.begin()).val < x)
            {
                pq.insert(*se2.begin());
                se2.erase(se2.begin());
                se2.insert({x,i});
                pq.erase(pq.find({x,i}));
            }
        }
        ll a=0;
        for(auto X:se1)a-=X.val;
        for(auto X:se2) a+=X.val;
        cout<<a<<" "<<se1.size()+se2.size()<<endl;
    }
    return 0;
}

C - Dream

HDU - 6440

Freshmen frequently make an error in computing the power of a sum of real numbers, which usually origins from an incorrect equation

(m + n)^{p} = m^{p} + n^{p}

(m + n) p = m p + n p

(m + n)^{p} = m^{p} + n^{p}

a p = {1, a p - 1 \cdot a, p = 0 p > 0

(m + n)^{p} = m^{p} + n^{p}

Hint

Hint for sample input and output:
From the table we get

0 + 1 = 1

InputThe first line of the input contains an positive integer $T (T \leq 30)$ OutputFor each test case, you should print $2 p$ Sample Input

1
2

Sample Output

构造一个群满足上述条件

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int a[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int p;
        cin>>p;
        for(int i=0; i<p; i++)
        {
            for(int j=0; j<p; j++)
                cout<<" "<<(i+j)%p;
            cout<<"
";
        }
        for(int i=0; i<p; i++)
        {
            for(int j=0; j<p; j++)
                cout<<" "<<(i*j)%p;
            cout<<"
";
        }
    }
    return 0;
}

E - GuGu Convolution

HDU - 6442

As a newbie, XianYu is now learning generating function!
Given a series

{a} = (a_{0}, a_{1}, a_{2}, \dots)

Hint

First Sample:

1! (\frac{1^{0}}{0!} \frac{{\sqrt{1}}^{1}}{1!} + \frac{1^{1}}{1!} \frac{0}{0!}) = 1 \sqrt{1}

InputThere is an integer $T$ OutputLet $\sum_{i = 1}^{q} a_{i} \sqrt{b_{i}}$ Sample Input

3
1 1 1 7
523 12 2 2100
1 1 1000000000000000000 998244353

Sample Output

1 1 1
1 2092 3
1 121099884 1

公式变换，然后作差

为了避免求逆出现问题，*2又/2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>v;
bool f[1000];
int la(int n)
{
    if(n==1) return 1;
    int res=1;
    for(auto i:v)
    {
        if(n%i==0)
        {
            int num=0;
            while(n%i==0)
            {
                n/=i;
                if(num&1) res*=i;
                num++;
            }
        }
        if(i*i>n) break;
    }
    return res;
}

ll qmi(ll p,ll q,ll n,ll mod,ll B)
{
    ll a=1,b=1,t1,t2;
    while(n)
    {
        if (n&1)
        {
            t1=(a*p+b*q%mod*B)%mod;
            t2=(a*q+b*p)%mod;
            a=t1;
            b=t2;
        }
        t1=(p*p+q*q%mod*B)%mod;
        t2=(p*q*2)%mod;
        p=t1;
        q=t2;
        n>>=1;
    }
    return b;
}
int main()
{
    for(int i=2; i<1000; i++)
        if(!f[i])
        {
            v.push_back(i);
            for (int j=i+i; j<1000; j+=i) f[j]=1;
        }
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    ll n,A,B,p,ans;
    cin>>T;
    while(T--)
    {
        cin>>A>>B>>n>>p;
        p*=2;
        ans=(qmi(A,1,n,p,B)-qmi(A,-1,n,p,B)+p)%p;
        ans/=2,p/=2;
        int k=la(B);
        cout<<1<<" "<<ans*k%p<<" "<<B/k/k<<"
";
    }
}

G - Neko's loop

HDU - 6444

Neko has a loop of size

n

InputThe first line contains only one integer $T (T \leq 50)$ OutputFor each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer.Sample Input

Sample Output

Case #1: 0
Case #2: 2

求一个环的最大值，有两种情况，用滑窗维护下吧

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e4+10;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;
ll a[MAX];
ll sum[MAX];
int v[MAX];
vector<ll>p;
deque<int>que;
ll cal(ll m)
{
    int len=p.size();
    for(int i=0; i<len; i++)p.push_back(p[i]);          //扩大2倍
    for(int i=0; i<p.size(); i++)sum[i]=(i==0?p[i]:sum[i-1]+p[i]);
    int y=m%len;
    ll ans=0;
    while(!que.empty())que.pop_back();
    for(int i=0,R=0; i<len; i++)        //先走m/len圈
    {
        while(!que.empty()&&que.back()<i)que.pop_back();
        while(R<=i+y-1)
        {
            while(!que.empty()&&sum[que.front()]<=sum[R])que.pop_front();
            que.push_front(R);
            R++;
        }
        int x=que.back();
        ll res=max(0ll,sum[x]-(i==0?0:sum[i-1]));
        ans=max(ans,res+max(0ll,m/len*sum[len-1]));
    }
    if(m>=len)              //先找到最大值所需步数x，再走(m-x)/len圈
    {
        while(!que.empty())que.pop_back();
        for(int i=0,R=0; i<len; i++)
        {
            while(!que.empty()&&que.back()<i)que.pop_back();
            while(R<=i+len-1)
            {
                while(!que.empty()&&sum[que.front()]<=sum[R])que.pop_front();
                que.push_front(R);
                R++;
            }
            int x=que.back();
            ll res=max(0ll,sum[x]-(i==0?0:sum[i-1]));
            ans=max(ans,res+max(0ll,(m-(x-i+1))/len*sum[len-1]));
        }
    }
    return ans;
}
int main()
{
    int T,cas=1;
    cin>>T;
    while(T--)
    {
        ll n,s,m,k;
        scanf("%lld%lld%lld%lld",&n,&s,&m,&k);
        for(int i=0; i<n; i++)scanf("%lld",&a[i]);
        for(int i=0; i<n; i++)v[i]=0;
        ll ans=s;
        for(int i=0; i<n; i++)
        {
            if(v[i])continue;
            p.clear();
            int j=i;
            while(v[j]==0)      //找出循环节里的数并计算答案
            {
                v[j]=1;
                p.push_back(a[j]);
                j=(j+k)%n;
            }
            ans=min(ans,max(s-cal(m),0ll));
        }
        printf("Case #%d: %lld
",cas++,ans);
    }
    return 0;
}

I - Tree and Permutation

HDU - 6446

There are

N

InputThere are 10 test cases at most.
The first line of each test case contains one integer $N$ OutputFor each test case, print the answer module $10^{9} + 7$ Sample Input

Sample Output

16
24

求出两两间距离之和，在n!个排列里，两两相邻是(n-1)!

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define v first
#define w second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
vector<pair<int,int> > tree[N];
ll dp[N],sum[N];//统计每个点子树所包含点的个数
int n;
void dfs(int cur,int fa)
{
    sum[cur] = 1;
    for(int i = 0; i<tree[cur].size(); i++)
    {
        int son=tree[cur][i].v;
        ll len=tree[cur][i].w;
        if(fa==son)continue;
        dfs(son,cur);
        sum[cur]+=sum[son];
        dp[cur]+=dp[son]+sum[son]*(n-sum[son])%MD*len%MD;
        dp[cur]%=MD;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        ll ans=2;
        memset(dp,0,sizeof(dp)),memset(sum,0,sizeof(sum));
        for(int i = 1,u,v,w; i<n; i++)
        {
            ans=ans*i%MD;
            scanf("%d%d%d",&u,&v,&w);
            tree[u].push_back({v,w});
            tree[v].push_back({u,w});
        }
        dfs(1,0);
        for(int i=1; i<=n; i++)tree[i].clear();
        printf("%d
",ans*dp[1]%MD);
    }
    return 0;
}

J - YJJ's Salesman

HDU - 6447

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city A to southeastern city B. Let us assume that A is

(0, 0)

InputThe first line of the input contains an integer $T$ OutputThe maximum of dollars YJJ can get.Sample Input

Sample Output

离散化就可以用数据结构去维护这个dp了

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct T
{
    int x,y,v;
} t[N];
bool cmp(T a, T b)
{
    return a.x<b.x;
}
int a[N],c[N];
int tot;
void update(int i, int val)
{
    for(; i<=tot; i+=i&(-i))c[i]=max(c[i], val);
}
int query(int i)
{
    int res=0;
    for(; i>0; i-=i&(-i))res = max(res, c[i]);
    return res;
}
int dp[N];
int main()
{
    int T,n;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; i++)scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].v);
        tot=0,memset(c,0,sizeof c);
        for(int i=0; i<n; i++)a[tot++]=t[i].y;
        sort(a,a+tot);
        tot=unique(a,a+tot)-a;
        for(int i=0; i<n; i++)t[i].y=lower_bound(a,a+tot,t[i].y)-a+1;
        sort(t,t+n,cmp);
        for(int i=0; i<n; i++) dp[i]=t[i].v;
        int pos=0,ans=0;
        for(int i=0; i<n; i++)
        {
            while(pos<i&&t[pos].x<t[i].x)update(t[pos].y,dp[pos]),pos++;
            dp[i]=query(t[i].y-1)+t[i].v,ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}