JXUFE_2017_寒假训练_warming_up_解题报告

发表于 | 分类于 |

传送门

思路

A

思路是这样的，考虑每个人都要被干掉，自己的战斗力先算上

然后对于每条边，边所连接的两人总有一个被先干掉，边必然会产生一个贡献

边的贡献取连接的两人中战斗力较小的就好了

我模拟了这个过程，写麻烦了，将就看233333

B

这题是算贡献的

假设S串不同，我们移动T串，易知T串的每个字符和S串的每个字符都对应了一次

然后S串每次循环时情况一样

所以我们开一个26的桶，统计一下T中每个字母的频数

遍历一边S串求出一次的贡献，总贡献就是一次贡献的n倍

然后该模多少模一下就好了

C

这题有个小坑，给的是站点，但票务计算要计算站区间233333

考虑到数据范围贼小，暴力模拟一下就好了

P.S. 大数据范围需要区间修改线段树了，在此不赘述

D

我都不知道我的做法对不对233333

时间复杂度是$O(nlog_2^2n)$

首先需要给所有的订单排序，结束时间早的放前面，结束时间相同要求时间短的放前面

然后我们考虑类似于$O(nlog_2n)$的$LIS$的做法来DP

假设$dp[i]$表示完成了i个任务最快需要多久

对于每一个任务，我们算出它的最晚进行时间，也就是令$T_e=T_2-T_1$

然后假设当前最多完成了$m$个任务，

如果$dp[m]<=T_e$，那么最多完成的任务数($m$)+1，同时记下这个任务

如果不行，我们需要知道完成几个任务之后可以完成当前任务

这里需要二分一下，然后我们与此同时还要记下前$i$个已完成的任务的$T_1$最大值，考虑可修改，于是树状数组

自此整道题需要重新思考

我们重新定义$dp[i]$为完成了前i个任务最快情况下第$i$个任务的所需时间

然后用树状数组统计前缀和，这样二分的时候复杂度是$O(log_2^2n)$

与此同时我们依然需要树状数组维护前$m$个任务的前缀最大值，这个维护也是$O(log^2_2n)$

继续刚才的思路，如果这个任务可以再已有的基础上继续完成，我们就继续完成就好了

否则的话二分出一个$k$，使得前k个任务的完成时间不大于$T_e$

同时前$k+1$个任务的完成时间大于$T_e$

然后我们用当前任务和前$k+1$个任务比较，如果当前任务的所需时间小于前$k+1$个任务的中最大的那个任务的所需时间，我们就用当前任务去更新

这样下去，最后统计得出的$m$为我们最多能送出多少份订单

输出$n-m$就是最少会收到多少份差评了

思路较复杂，运气好，用了两个树状数组硬莽过去了

E

注意到一个事实，我们对于一个$x$位数，决定它是不是回文数的只是后$\frac{x}{2}$位

因此我们发现最多从$n$向下枚举到$n-10^5$左右就能得到答案，暴力就好了呀

F

DFS直接暴力，剪剪枝就可以剪过去了

G

考虑自己的排名很小的情况，可以直接优先队列模拟

那么自己排名很大的时候，我们可以用二分去逼近

二分逼近到某一时刻正在安检和已经安检完毕的人刚好小于$x$

且下一时刻正在安检和已经安检完毕的人数不小于$x$

然后我们对每个门计算一下它目前安检的进度，拿优先队列跑若干轮就解决了

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct node
{
    int to;
    LL cost;
};
queue<int> q;
vector<node> g[1005];
int tot[1005];
int i,j,k,l,m,n;
LL a[1005];
LL ans;
 
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    scanf("%d",&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(a[x]<a[y] || (a[x]==a[y] && x>y)){k=x;x=y;y=k;}
        struct node t;
        t.to=y;t.cost=a[y];
        tot[y]++;
        g[x].push_back(t);
    }
    while(!q.empty())q.pop();
    for(i=1;i<=n;i++)
        if(tot[i]==0){q.push(i);tot[i]=-1;}
    while(!q.empty())
    {
        k=q.front();q.pop();
        ans+=a[k];
        for(i=0;i<g[k].size();i++)
        {
            j=g[k][i].to;
            tot[j]--;
            ans+=g[k][i].cost;
            if(tot[j]==0){q.push(j);tot[j]=-1;}
        }
    }
    printf("%lld",ans);
    return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const LL mod=1e9+7;

char s1[1000005],s2[1000005];
LL a[30];
LL i,n;

int main()
{
    gets(s1+1);gets(s2+1);
    n=strlen(s1+1);
    for(i=1;i<=n;i++)a[s1[i]-64]++;
    LL ans=0;
    for(i=1;i<=n;i++)
        ans+=a[s2[i]-64];
    ans*=n;
    printf("%lld",ans%mod);
    return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[105];
int i,j,k,l,m,n;

int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n-1;i++)a[i]=k;
    while(m--)
    {
        k=2000;
        int x,y;
        scanf("%d%d",&x,&y);
        for(i=x;i<=y-1;i++)k=min(k,a[i]);
        if(k<1){printf("No\n");continue;}
        printf("Yes\n");
        for(i=x;i<=y-1;i++)a[i]--;
    }
    return 0;
}

D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
const int maxn=100005;

struct node
{
    LL num;
    int pos;
    node(LL num=0,int pos=0):num(num),pos(pos){}
    bool operator > (const struct node p)const
    {return num>p.num || (num==p.num && pos<p.pos);}
}ma[maxn],f[maxn];
struct wm
{
    LL ne,en;
    bool operator < (const struct wm p)const
    {return en<p.en || (en==p.en && ne<p.ne);}
}a[maxn];

int i,k,m,n;
LL sum[maxn];
LL b[maxn];

void csum(int po,LL nu)
{
    while(po<=n)
    {
        sum[po]+=nu;
        po+=lowbit(po);
    }
}

void cmax(int po)
{
    while(po<=n)
    {
        f[po]=ma[po];
        for(int i=1;i<lowbit(po);i<<=1)
            if(f[po-i]>f[po])f[po]=f[po-i];
        po+=lowbit(po);
    }
}

void change(int po,LL nu)
{
    csum(po,nu-b[po]);
    b[po]=nu;
    ma[po]=node(nu,po);
    cmax(po);
}

LL findsum(int x)
{
    LL aa=0;
    while(x>0)
    {
        aa+=sum[x];
        x-=lowbit(x);
    }
    return aa;
}

struct node findmax(int x)
{
    struct node tt=node(0,0);
    while(x>0)
    {
        if(f[x]>tt)tt=f[x];
        x-=lowbit(x);
    }
    return tt;
}

int find(LL o)
{
    int l=1,r=m;
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        if(findsum(mid)>o)r=mid;else l=mid;
    }
    if(findsum(l)>o)l--;
    if(l<m && findsum(l+1)<=o)l++;
    return l;
}

int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld%lld",&a[i].ne,&a[i].en);
    sort(a+1,a+n+1);
    m=1;change(1,a[1].ne);
    for(i=2;i<=n;i++)
    {
        LL temp=a[i].en-a[i].ne;
        LL tot=findsum(m);
        if(temp>=tot)
        {
            m++;
            change(m,a[i].ne);
            continue;
        }
        k=find(temp)+1;
        struct node tt=findmax(k);
        if(tt.num>a[i].ne)change(tt.pos,a[i].ne);
    }
    printf("%d",n-m);
    return 0;
}

E

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int a[15];
int n,m,k,i;
bool f;

int main()
{
    scanf("%d",&n);
    while(n>0)
    {
        m=n;k=0;
        while(m>0)
        {
            k++;
            a[k]=m%10;m/=10;
        }
        f=true;
        for(i=1;i<=k;i++)
            if(a[i]!=a[k+1-i]){f=false;break;}
        if(f)break;
        n--;
    }
    printf("%d",n);
    return 0;
}

F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct node
{
    int len,num;
    node(int len=0,int num=0):len(len),num(num){}
}dp[105][11];

struct edge
{
    int to,cost;
    edge(int to=0,int cost=0):to(to),cost(cost){}
};
vector<edge> g[105];
bool vis[105];
int i,j,k,l,m,n,st,en,p;
int a1,a2;

void DFS(int x,int y,int tot)
{
    if(y>p || vis[x] || tot>a1 || (x==en && y<p))return;
    if(x==en && y==p)
    {
        if(tot>a1)return;
        if(tot==a1){a2++;return;}
        a1=tot;a2=1;
        return;
    }
    vis[x]=true;
    for(unsigned int t=0;t<g[x].size();t++)DFS(g[x][t].to,y+1,tot+g[x][t].cost);
    vis[x]=false;
}

int main()
{
    while(scanf("%d%d%d%d%d",&n,&p,&st,&en,&m)==5)//p steps
    {
        for(i=1;i<=n;i++)g[i].clear();
        while(m--)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            g[x].push_back(edge(y,z));
        }
        memset(vis,0,sizeof(vis));
        a1=1<<29;a2=0;
        DFS(st,1,0);
        if(a1==1<<29)printf("-1\n");else printf("%d %d\n",a1,a2);
    }
    return 0;   
}

G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
LL a[1005];
int i,j,k,l,m,n,T;
LL x,y,z;
LL sum,tot,ans;

struct node
{
    LL en;
    int pos;
    bool operator < (const struct node p)const
    {return en>p.en || (en==p.en && pos>p.pos);}
};

LL cal(LL t)
{
    LL o=0;
    for(int i=1;i<=n;i++)
        if(t%a[i]==0)o+=t/a[i];else o+=t/a[i];
    o+=n;
    return o;
}

priority_queue<node> q;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%lld",&n,&z);
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        x=0;y=z*a[1];
        while(y-x>1)
        {
            LL mid=(x+y)>>1;
            if(cal(mid)>=z)y=mid;else x=mid;
        }
        if(cal(y)>=z)x=y-1;else x=y;
        tot=cal(x);ans=1e18;
        while(!q.empty())q.pop();
        if(z>n)
        {
            for(i=1;i<=n;i++)
            {
                struct node t;
                if(x%a[i]==0)y=x+a[i];
                else y=(x/a[i]+1)*a[i];
                t.en=y;t.pos=i;
                q.push(t);
            }
            while(tot<z-1)
            {
                tot++;
                struct node te=q.top();
                q.pop();
                te.en+=a[te.pos];
                q.push(te);
            }
        }else
        {
            for(i=1;i<=n;i++)
            {
                struct node t;
                if(x%a[i]==0)y=x+a[i];
                else y=(x/a[i]+1)*a[i];
                if(i>=z)y=0;
                t.en=y;t.pos=i;
                q.push(t);
            }
        }
        sum=1005;
        while(sum--)
        {
            struct node te=q.top();q.pop();
            te.en+=a[te.pos];
            ans=min(ans,te.en);
            q.push(te);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多