2018 ACM-ICPC Nanjing Online

Posted on | In , ,

补题进度：7/8(12)
原题场
单向边看成双向边，打的我心态爆炸了自闭了

题目链接

A. An Olympian Math Problem

  • 签到，打表和猜结论都可以看出答案是显然的
  • 当然推公式是很好推的。
    $\sum_{i=1}^{i=n-1}i·i!$
    $=\sum_{i=1}^{i=n-1}(i+1)!-i!$
    $=n!-1$
    $=n-1$

B. The writing on the wall Problem

题意

求 $nm$ 的矩阵上有 $k$ 个位置为0，求不含0的子矩阵数量。
$(k,n\le10^5,m\le10)$

题解

  • 这道题怎么计算可以保证不重不漏难点，这道题需要有强大的分析问题能力，以及不断的尝试自己的想法。
  • 预处理每个1右边可以延伸的最长1的长度。
  • 枚举每一列的每一行，考虑每个位置的贡献，是一个柱的形状，单调队列维护即可。
  • 贡献怎么算，观察可知，设当前枚举到第i行，前i-1行的贡献为sum
  • 若当前位置1的延伸长度大于前面的，贡献则为sum+当前位置延伸1的数量
  • 若当前位置1的延伸长度小于前面的，贡献为减去前面i-1行中大于当前行的贡献。
  • 注意每次都要更新sum值。

C. GDY

  • 按题意模拟即可

D. Jerome’s House

留坑

E. AC Challenge

题意

给出一系列物品和物品获得之间的依赖关系，物品获得的价值和物品本身的属性和获得的顺序有关。求最大收益。
$(n\le20)$

题解

  • 数据范围可知状压dp或者爆搜
  • 考虑依赖关系可以用二进制位0/1表示
  • dp[i]: 二进制状态为i的最大值
  • 转移：对每个i，考虑其中为1的位，并且由其它为1的位的和转移而来
  • 这样转移是不会出现问题的，因为对于任意状态i，其中的一位二进制为1的，剩下的数一定小于i，必定是先前已经更新了的
  • 时间复杂度$(n·2^n)$
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+7;

int n, fac[(1<<21)+100];
ll dp[(1<<21)+100], a[maxn], b[maxn];
int cnt[(1<<21)+100];

void init()
{
    for(int i=0;i<(1<<20);i++)
    {
        int k=i;
        int num=0;
        for(int j=0;j<20;j++)
            if((1<<j) & k)  num++;
        cnt[i]=num;
    }
}

int main()
{
    int s, x;
    init();
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%lld%lld%d", &a[i], &b[i], &s);
        int num=0;
        while(s--)
        {
            scanf("%d", &x);
            x--;
            num+=(1<<x);
        }
        fac[i]=num;
    }
    memset(dp, -1, sizeof(dp));
    for(int i=0;i<n;i++) {
        if(!fac[i]) dp[1<<i]=1LL*a[i]+1LL*b[i];
    }
    ll ans=0;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++) {
            if((1<<j) & i){
                if( (i^fac[j]) == (i-fac[j]) ){
                    if( dp[i^(1<<j)]  != -1)
                    {
                        dp[i] = max(dp[i], dp[i^(1<<j)] + cnt[i]*a[j]+b[j]);
                        ans=max(ans, dp[i]);
                    }
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

F. An Easy Problem On The Trees

留坑

G. Lpl and Energy-saving Lamps

题意

一排房间装着灯，每月买新的节能灯替换，每次找最前面的能完整替换的房间完整替换，求过程。

题解

  • 线段树维护最小值和修改即可
  • 最对只会修改$n\log n$次
  • 时间复杂度$O(n\log n)$
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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5+7;
const int maxm = 100+7;

int n, m, a[maxn], q, d, ans1[maxn], ans2[maxn];

struct node{
    int l,r,minx,a;
}t[maxn<<2];

void build(int x,int l,int r)
{
    t[x].l=l, t[x].r=r;
    if(l==r){
        t[x].minx=t[x].a=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    t[x].minx=min(t[x<<1|1].minx, t[x<<1].minx);
    return;
}

void update(int x,int pos)
{
    int l=t[x].l, r=t[x].r;
    if(l==r)
    {
        t[x].minx=t[x].a=1e9;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(x<<1, pos);
    else update(x<<1|1, pos);
    t[x].minx=min(t[x<<1].minx, t[x<<1|1].minx);
    return;
}

int query(int x,int val)
{
    int l=t[x].l, r=t[x].r;
    if(t[x].minx>val) return  0;
    if(l==r)
    {
        return l;
    }
    if(t[x<<1].minx<=val)  return query(x<<1, val);
    else return query(x<<1|1, val);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    ll res=0, now;
    int cnt=0;
    for(int i=1;i<=100000;i++)
    {

        if(t[1].minx == 1e9)
        {
            ans1[i]=cnt;
            ans2[i]=now;
            continue;
        }
        now=res+m;
        while(now>=t[1].minx)
        {
            int p=query(1, now);
            now-=a[p];
            update(1, p);
            cnt++;
        }
        ans1[i]=cnt;
        ans2[i]=now;
        res=now;
    }
    scanf("%d", &q);
    while(q--)
    {
        int x;
        scanf("%d", &x);
        printf("%d %d\n", ans1[x], ans2[x]);
    }
    return 0;
}

H. Set

留坑

I. Skr

题意

求一个数字串中所有本质不同的回文子串之和。

题解

待补

J. Sum

题意

求某个积性函数的前缀和
$(n\le10^7)$

题解

  • 观察题目函数$f()$定义，可以$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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int maxn = 2e5+7;

const int N = 2e7+110;
int phi[N], tot, prime[N], check[N];  //tot计数，表示prime[N]中有多少质数
int ans[N];

void init(){
    memset(check, 0, sizeof(check));
    for(int i=2;i<N;i++)
    {
        if(!check[i]) {prime[tot++]=i; ans[i]=2;}
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>N) break;
            check[i*prime[j]]=1;
            if(i%prime[j] == 0) {
                if(i%(prime[j]*prime[j]) == 0) ans[i*prime[j]]=0;
                else ans[i*prime[j]]=ans[i]/2;
                break;
            }
            else{
                    ans[i*prime[j]]=ans[i]*2;
            }
        }
    }
    ans[1]=1;
    for(int i=1;i<N;i++)
        ans[i]+=ans[i-1];
}

int main()
{
    init();
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
}

K. The Great Nim Game

留坑

L. Magical Girl Haze

题意

可以将k条边的权值变为0，求从1到n的最短路径。

题解

  • 直接分层最短路，暴力dij找出所有状态即可
  • 时间复杂度$O(nk\log n)$
  • 怎么宛如一个zz啊，单向边弄成双向的，自闭了一个下午。
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 8e5+7;
const int N=1e5+100, K=12;

struct HeapNode{
    HeapNode(ll _d, ll _u, ll _k) : d(_d), u(_u), k(_k) {}
    ll d; int u, k;
    bool operator < (const HeapNode &x) const {
        return d>x.d || (d==x.d && (u < x.u || (u==x.u && k<x.k)));
    }
};

int T, n, m, k, u, v;
int head[maxn], nxt[maxn], to[maxn] , tot;
ll d[N][K], w[maxn], c;
bool vis[N][K];


void addedge(int u,int v,ll c)
{
    to[++tot]=v;
    w[tot]=c;
    nxt[tot]=head[u];
    head[u]=tot;
}

void dij()
{
    fill(d[0], d[0]+K*N, INF);
    memset(vis, 0, sizeof(vis));
    priority_queue<HeapNode>q;
    q.push({0, 1, 0});
    d[1][0]=0;
    while(!q.empty())
    {
        HeapNode now=q.top();
        q.pop();
        if(vis[now.u][now.k]) continue;
        vis[now.u][now.k]=1;
        for(int i=head[now.u]; i; i=nxt[i])
        {
            int v=to[i];
            if(now.k < k && d[v][now.k+1] > d[now.u][now.k])
            {
                d[v][now.k+1]=d[now.u][now.k];
                q.push({d[v][now.k+1], v, now.k+1});
            }
            if(d[v][now.k] > d[now.u][now.k] + w[i])
            {
                d[v][now.k]=d[now.u][now.k] + w[i];
                q.push({d[v][now.k], v, now.k});
            }
        }
    }

}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        memset(head, 0, sizeof(head));
        memset(nxt, 0, sizeof(nxt));
        memset(to, 0, sizeof(to));
        tot=0;
        scanf("%d%d%d", &n, &m, &k);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld", &u, &v, &c);
            addedge(u, v, c);
        }
        dij();
        ll ans=INF;
        for(int i=0;i<=k;i++)
            ans=min(ans, d[n][i]);
        printf("%lld\n", ans);
    }
    return 0;
}