首页 > 其他 > 详细

【考试记录】20180920

时间:2018-09-23 00:37:45      阅读:224      评论:0      收藏:0      [点我收藏+]

T1(Loj2333):

铁路沿线N个车站,车分三种:快,慢,次快车。慢车走1个站花A单位时间,每站都停;快车走1个站花费B单位时间,只在M个站停,停靠站输入给出(起点1和终点N必停);次快

车走1个站花费C单位时间,一共在K个站停,且必须在快车停靠站停,剩下K-M个停靠站随意建造。速度A,B,C满足B<C<A。求如何建造次快车停靠站使得在T分钟内能到

达的车站尽量多。(所有移动均为单向,1->N方向)

(到达:停靠在此站。每个车站单独计数,即统计有几个车站从1走到该车站花费T分钟以内。)

N<=10^9,M<=K<=3000。

 

题解:

第一遍看根本没看懂,JOI考的都是读题能力么……

看懂的话应该很快发现由于B<C<A,整个图被快车站分成了M-1个块。

修建的任意一个次快车站只能影响到它所在的块内在它后面的车站。

(块外的车站可以通过快车走到,并且不影响次快车在该块内的修建(所有快车停靠站都是次快车停靠站)为什么还要走次快车?)

显然,已知速度,时间,每个块内修建a个次快车站的贡献是可以计算的。

那显而易见的得到O(M*K^2)的dp,dp[i][j]表示处理到第i个块,一共修建了j个次快车站时能到达的最多车站。

枚举该块内修建了k个转移即可。

好像过不了,考虑优化。

容易发现一个块内每放一个车站的贡献值是递减的。(V不变,T减少,S便减少)

由此产生一个很重要的推论:一个块内按贡献值从大到小排序依次修建,一定是合法的。

(不会出现一个块内修建第K个的贡献比第K-j个贡献大的情况,否则你没修建到第K-j个怎么修建第K个?)

那么既然每个块互不影响,所有块均满足该推论。

于是可以将所有块内修建第i个块的贡献值扔到一个优先队列里,每次操作取出队首,在此修建,累加答案,并将其出队。操作K次得到答案。

复杂度O(K*log(MK))。

这题想了30min,标程写了1h-,对拍写了2h+写挂了,最后直接交标程A了,我尼玛……

 

代码:

 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
#define MAXN 3005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long long

priority_queue<ll> q;
ll S[MAXN],sgo[MAXN][MAXN];
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c==-)
            f=-1;
    for(;isdigit(c);c=getchar())
        x=x*10+c-0;
    return x*f;
}

int main(){
    ll N=read(),M=read(),K=read();K-=M;
    ll A=read(),B=read(),C=read(),T=read();
    for(ll i=1;i<=M;i++) S[i]=read();
    sort(S+1,S+1+M);
    for(ll i=1;i<=M;i++){
        if(i==1) continue;
        //cout<<i<<endl;
        ll slen=S[i-1]-1;ll stim=T-(slen*B);
        //cout<<stim<<endl;
        if(stim<0) break;
        //cout<<stim<<endl;
        sgo[i][0]=stim/A;
        ll sum=sgo[i][0];
        //cout<<sum<<":"<<S[i-1]<<":"<<S[i]<<endl;
        if(sum+S[i-1]>=S[i]){
            sgo[i][0]-=(sum+S[i-1]-S[i]+1);
            sgo[i][0]=max(sgo[i][0],(ll)0);
            //cout<<i<<":"<<sgo[i][0]<<" ";
            continue;
        }
        //cout<<i<<":"<<sgo[i][0]<<" ";
        for(ll j=1;j<=K;j++){
            if(stim<(sum+1)*C) break; 
            sgo[i][j]=(stim-(sum+1)*C)/A+1;
            sum+=sgo[i][j];
            if(sum+S[i-1]>=S[i]){
                sgo[i][j]-=(sum+S[i-1]-S[i]+1);
                sgo[i][j]=max(sgo[i][j],(ll)0);
                //cout<<sgo[i][j]<<" ";
                break;
            }
            //cout<<sgo[i][j]<<" ";
        }
        //cout<<endl;
    }
    ll ans=0;
    for(ll i=2;i<=M;i++){
        if((S[i]-1)*B>T) break;
        ans++;
    }
    //cout<<ans<<endl;
    for(ll i=1;i<=M;i++){
        //cout<<i<<":"<<sgo[i][0]<<endl;
        ans+=sgo[i][0];
        //cout<<ans<<endl;
    }
    //cout<<ans<<endl;
    for(ll i=1;i<=M;i++)
        for(ll j=1;j<=K;j++)
            q.push(sgo[i][j]);
    for(ll i=1;i<=K;i++){ans+=q.top();q.pop();}
    printf("%lld\n",ans);
    //cout<<ans<<endl;
    /*
    for(ll i=1;i<=M;i++){
        if(S[i]==1) continue;
        ll slen=S[i-1]-1;ll stim=slen*B;
        ll st=T-stim;ll sgo[0]=st/A,cnt=0;
        if(st<0) break;
        for(ll k=0;k<=K;k++) dp[i][k]=dp[i-1][k]+sgo[0]+1;
        ll num=sgo[0];
        if(num>=S[i]-S[i-1]-1) continue;
        for(ll k=1;k<=K;k++){
            sgo[k]=(st-(sgo[i-1]*C))/A;
            num+=sgo[k],cnt++;
            if()
        }
        for(ll k=1;k<=K;k++){
            for(ll l=1;l<=k;l++){
                
                sgo=
                dp[i][k]=dp[i-1][k]+
            }
        }
    }*/
    return 0;
}
/*
12 3 4
10 1 2
30
1
11
12
*/

 

 

T2(Loj2334):

给你一个N*M的矩阵,将其划分成两块使得两块中的极差(max-min)最大者最小。划分不能出现“突出”或“凹陷”。

原句:对于每一行/列,如果我们将这一行/列单独取出,这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。

N,M<=2000。

 

题解:

看懂了非常好做,考点依旧是读题。

根据题意第一个国家只可能处在第二个的左上,右上,左下,右下。

那么每个方向二分答案求解即可。

但如果看了上一题的时间花费就知道我已经没时间写这题了……

 

代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
#define MAXN 3005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long long

int N,M,maxn,minn;
int A[MAXN][MAXN];
int tmp[MAXN][MAXN];
inline int read(){
    int x=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c==-)
            f=-1;
    for(;isdigit(c);c=getchar())
        x=x*10+c-0;
    return x*f;
}

bool check(int x){
    int pos=M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=pos;j++)
            if(A[i][j]-minn>x)
                {pos=j-1;break;}
        for(int j=pos+1;j<=M;j++)    
            if(maxn-A[i][j]>x) 
                return 0;
    }
    return 1;
}

void sswap(){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            tmp[j][N-i+1]=A[i][j];
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++)
            A[i][j]=tmp[i][j];
    return;    
}

int main(){
    N=read(),M=read();
    maxn=-INF,minn=INF;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            A[i][j]=read();
            maxn=max(maxn,A[i][j]);
            minn=min(minn,A[i][j]);
        }
    int mans=INF;
    for(int i=1;i<=4;i++){
        int l=0,r=maxn-minn,ans=-INF;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        mans=min(ans,mans);
        sswap();swap(N,M);
    }
    printf("%d\n",mans);
    return 0;
    
}

 

T3(Loj2325):

bzoj4832升级版,攻击次数从50变为10^18(炉石传说没有外挂),求期望对998244353取模的值。

 

题解:

弱化版题目没什么问题吧……不管用什么奇怪的顺序转移应该都是能A的。

多说一句,如果直接预处理dp[i][j][k][l]表示还剩i次攻击,剩余1,2,3血奴隶主的个数分别为j,k,l个,

每次从还剩i-1次攻击转移过来(也就是反向建拓扑图)的话,可以通过T极大的数据。

然后我们发现这个题的攻击次数是10^18。

(一回合打50火妖法还能够到(还把我超生德直接打死),但这尼玛10^18难不成要无限回合火球法?)

再枚举N进行转移显然不可取,所以进行矩阵优化。

容易发现总状态数为固定的165个。(模型:0,1,2,3每种k个和为7,k可以为0)

那么我们将每种状态当做一个3位的7进制数,所有状态排成一列,形成一个1*165的初始矩阵。

状态间互相转移的路径是相同的,每次转移的概率也是相同的,

那么可以构造一个165*165的转移矩阵,答案相当于初始矩阵*(转移矩阵^N)。

使用矩阵快速幂即可。(需要卡常)

但165*165不好转移呼脸状态,再加1维变为166*166即可。

 

代码:

(Loj这会鸽了,明天填坑吧……)

 

【考试记录】20180920

原文:https://www.cnblogs.com/YSFAC/p/9689899.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!