ABC 417

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int n, a, b;
25
signed main() {
26
    n=read(), a=read(), b=read();
27
    string s;
28
    cin>>s;
29
    for(int i=a;i<n-b;i++) printf("%c",s[i]);
30
    return 0;
31
}

B

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=105;
25
int n, m, a[N], b[N];
26
signed main() {
27
    n=read(), m=read();
28
    rep(i,1,n) a[i]=read();
29
    rep(i,1,m) b[i]=read();
30
    rep(i,1,m) {
31
        rep(j,1,n) if(a[j]==b[i]) {
32
            a[j]=0;
33
            break;
34
        }
35
    }
36
    rep(i,1,n) if(a[i]) printf("%d ",a[i]);
37
    return 0;
38
}

C

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=2e5+5;
25
int n, a[N];
26
unordered_map<int,int> mp;
27
signed main() {
28
    n=read();
29
    rep(i,1,n) a[i]=read(), ++mp[i-a[i]];
30
    ll ans=0;
31
    rep(i,1,n) ans+=mp[a[i]+i];
32
    cout<<ans;
33
    return 0;
34
}

D

太人机了，又在这种题上降智。

对于给定的 $X$ 可以 $O(n)$ 处理掉，但 $O(nQ)$ 就爆炸。

注意到 $P_i,A_i,B_i$ 值域都不大。如果 $X$ 大于 ${P_i}$ 的值域 $500$ ，它一定会一直往下掉，直到落入 $[0,500]$ 。这个范围不大，我们可以直接预处理这部分的答案。这时候，我们需要直到当前打完了前几关，求出 $\sum_{i=1}^k B_i$ 后二分查找即可。然后此时我们需要 $f(i,j)$ 表示，打完了前 $i$ 关，此时体力为 $j$ ，通关后的体力值。限制一下 $j$ 的范围，状态数 $O(nD)$ ，可以接受。记忆化搜索即可。

赛时先用了很麻烦的普通 DP，细节没调好认为假了，改来改去成了记忆化搜索，还忘了限制 $j$ 的大小，竟然可以通过。

其实就是个类似背包的平凡东西。

复杂度 $O(Q+nD)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=1e4+5, lim=1000;
25
int n, q, p[N], a[N], b[N], sb[N];
26
int f[N][lim+5];
27
int dfs(int i,int x) {
28
    if(f[i][x]!=1e9+7) return f[i][x];
29
    if(i==n) return f[i][x]=x;
30
    if(p[i+1]>=x&&x+a[i+1]<=lim) f[i][x]=dfs(i+1,x+a[i+1]);
31
    else f[i][x]=dfs(i+1,max(x-b[i+1],0));
32
    return f[i][x];
33
}
34
void init() {
35
    rep(i,0,n) rep(j,0,lim) f[i][j]=1e9+7;
36
    rep(i,0,lim) dfs(0,i);
37
}
38
signed main() {
39
    n=read();
40
    rep(i,1,n) p[i]=read(), a[i]=read(), b[i]=read(), sb[i]=sb[i-1]+b[i];
41
    init();
42
    q=read();
43
    while(q--) {
44
        int x=read();
45
        if(x<=lim) printf("%d\n",dfs(0,x));
46
        else {
47
            int l=0, r=n;
48
            while(l<r) {
49
                int mid=(l+r)>>1;
50
                if(x-sb[mid]<=lim) r=mid; else l=mid+1;
51
            }
52
            if(x-sb[l]<=lim) {
53
                cout<<dfs(l,x-sb[l])<<endl;
54
            } else {
55
                printf("%d\n",x-sb[n]);
56
            }
57
        }
58
    }
59
    return 0;
60
}

E

没想到是水题。

场上卡点写完了爆搜，只 T 了 8 个点。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=1005;
25
int T, n, m, X, Y;
26
int a[N][N];
27
int fg;
28
bool v[N];
29
vector<int> ans;
30
void dfs(int x) {
31
    // printf("x=%d\n",x);
32
    if(x==Y) {
33
        ans.pb(x);
34
        fg=1;
35
        return;
36
    }
37
    for(int i=1;i<=n;i++) if(!v[i]&&a[x][i]) {
38
        v[i]=1;
39
        dfs(i);
40
        v[i]=0;
41
        if(fg) {
42
            break;
43
        }
44
    }
45
    if(fg) ans.pb(x);
46
}
47
void solve() {
48
    n=read(), m=read(), X=read(), Y=read();
49
    rep(i,1,n) {
50
        v[i]=0;
51
        rep(j,1,n) a[i][j]=0;
52
    }
53
    rep(i,1,m) {
54
        int x=read(), y=read();
55
        a[x][y]=a[y][x]=1;
56
    }
57
    fg=0;
58
    ans.clear();
59
    v[X]=1;
60
    dfs(X);
61
    reverse(ans.begin(),ans.end());
62
    for(auto x:ans) cout<<x<<" ";
63
    cout<<endl;
64
}
65
signed main() {
66
    T=read();
67
    while(T--) solve();
68
    return 0;
69
}

这玩意的复杂度是多少呢？看上去是 $O(nm)$ 的，虽说很难到达这个上界。

如何优化？直接 DFS 的思路是对的，我们只要保证每条边只会被搜到一次能过。上面代码标记已经搜过的点有个致命的问题，如果搜索节点 $i$ 失败，那么搜索节点 $i+1$ 的时候，如果再次搜到节点 $i$ ，那么就一定失败，否则不优。

太久不写代码导致的，可恶。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=1005;
25
int T, n, m, X, Y;
26
int a[N][N];
27
int fg;
28
bool v[N];
29
vector<int> ans;
30
void dfs(int x) {
31
    // printf("x=%d\n",x);
32
    v[x]=1;
33
    if(x==Y) {
34
        ans.pb(x);
35
        fg=1;
36
        return;
37
    }
38
    for(int i=1;i<=n;i++) if(!v[i]&&a[x][i]) {
39
        dfs(i);
40
        if(fg) {
41
            break;
42
        }
43
    }
44
    if(fg) ans.pb(x);
45
}i
46
void solve() {
47
    n=read(), m=read(), X=read(), Y=read();
48
    rep(i,1,n) {
49
        v[i]=0;
50
        rep(j,1,n) a[i][j]=0;
51
    }
52
    rep(i,1,m) {
53
        int x=read(), y=read();
54
        a[x][y]=a[y][x]=1;
55
    }
56
    fg=0;
57
    ans.clear();
58
    dfs(X);
59
    reverse(ans.begin(),ans.end());
60
    for(auto x:ans) cout<<x<<" ";
61
    cout<<endl;
62
}
63
signed main() {
64
    T=read();
65
    while(T--) solve();
66
    return 0;
67
}

F

不会搞期望了……

初读题面时没有很认真，竟然没看出来是道期望题，还以是为某种高妙的数数。

Uniformly randomly意为均匀随机。

设随机变量 $X_{i,j}$ 表示进行完了前 $i$ 个操作，位置 $j$ 上石头的数量。

显然有

E(X_{i,j}) = \begin{cases}E(X_{i-1,j}) \quad j \notin [L_i,R_i] \\ \frac{1}{R_i-L_i+1} E \left(\sum_{k=L_i}^{R_i} X_{i-1,k} \right) = \frac{1}{R_i-L_i+1} \sum_{k=L_i}^{R_i} E(X_{i-1,k}) \quad j \in [L_i,R_i]\end{cases}

线段树维护转移即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=2e5+5;
25
const ll mod=998244353;
26
int n, m, a[N];
27
namespace seg {
28
    ll t[N<<2], tag[N<<2];
29
    void pushup(int x) { t[x]=(t[x<<1]+t[x<<1|1])%mod; }
30
    void maketag(int x,int l,int r,ll d) {
31
        t[x]=(r-l+1)*d%mod;
32
        tag[x]=d;
33
    }
34
    void pushdown(int x,int l,int r) {
35
        if(tag[x]!=-1) {
36
            int mid=(l+r)>>1;
37
            maketag(x<<1,l,mid,tag[x]);
38
            maketag(x<<1|1,mid+1,r,tag[x]);
39
            tag[x]=-1;
40
        }
41
    }
42
    void build(int x=1,int l=1,int r=n) {
43
        tag[x]=-1;
44
        if(l==r) { t[x]=a[l]; return; }
45
        int mid=(l+r)>>1;
46
        build(x<<1,l,mid);
47
        build(x<<1|1,mid+1,r);
48
        pushup(x);
49
    }
50
    void upd(int L,int R,ll d,int x=1,int l=1,int r=n) {
51
        if(L<=l&&r<=R) {
52
            maketag(x,l,r,d);
53
            return;
54
        }
55
        int mid=(l+r)>>1;
56
        pushdown(x,l,r);
57
        if(L<=mid) upd(L,R,d,x<<1,l,mid);
58
        if(R>mid) upd(L,R,d,x<<1|1,mid+1,r);
59
        pushup(x);
60
    }
61
    ll query(int L,int R,int x=1,int l=1,int r=n) {
62
        if(L<=l&&r<=R) return t[x];
63
        int mid=(l+r)>>1;
64
        pushdown(x,l,r);
65
        ll res=0;
66
        if(L<=mid) res=query(L,R,x<<1,l,mid);
67
        if(R>mid) (res+=query(L,R,x<<1|1,mid+1,r))%=mod;
68
        return res;
69
    }
70
}
71
ll fp(ll a,ll b) {
72
    ll c=1;
73
    for(;b;a=a*a%mod,b>>=1) if(b&1) c=c*a%mod;
74
    return c;
75
}
76
signed main() {
77
    n=read(), m=read();
78
    rep(i,1,n) a[i]=read();
79
    seg::build();
80
    rep(i,1,m) {
81
        int L=read(), R=read();
82
        ll res=seg::query(L,R)*fp(R-L+1,mod-2)%mod;
83
        // cout<<res<<endl;
84
        seg::upd(L,R,res);
85
    }
86
    rep(i,1,n) printf("%lld ",seg::query(i,i));
87
    return 0;
88
}

G

不会

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区