ABC 417
|
比赛,题解
|

996 字
|
22 分钟

A

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int n, a, b;
signed main() {
    n=read(), a=read(), b=read();
    string s;
    cin>>s;
    for(int i=a;i<n-b;i++) printf("%c",s[i]);
    return 0;
}

B

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=105;
int n, m, a[N], b[N];
signed main() {
    n=read(), m=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,m) b[i]=read();
    rep(i,1,m) {
        rep(j,1,n) if(a[j]==b[i]) {
            a[j]=0;
            break;
        }
    }
    rep(i,1,n) if(a[i]) printf("%d ",a[i]);
    return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2e5+5;
int n, a[N];
unordered_map<int,int> mp;
signed main() {
    n=read();
    rep(i,1,n) a[i]=read(), ++mp[i-a[i]];
    ll ans=0;
    rep(i,1,n) ans+=mp[a[i]+i];
    cout<<ans; 
    return 0;
}

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)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=1e4+5, lim=1000;
int n, q, p[N], a[N], b[N], sb[N];
int f[N][lim+5];
int dfs(int i,int x) {
    if(f[i][x]!=1e9+7) return f[i][x];
    if(i==n) return f[i][x]=x;
    if(p[i+1]>=x&&x+a[i+1]<=lim) f[i][x]=dfs(i+1,x+a[i+1]);
    else f[i][x]=dfs(i+1,max(x-b[i+1],0));
    return f[i][x];
}
void init() {
    rep(i,0,n) rep(j,0,lim) f[i][j]=1e9+7;
    rep(i,0,lim) dfs(0,i);
}
signed main() {
    n=read();
    rep(i,1,n) p[i]=read(), a[i]=read(), b[i]=read(), sb[i]=sb[i-1]+b[i];
    init();
    q=read();
    while(q--) {
        int x=read();
        if(x<=lim) printf("%d\n",dfs(0,x));
        else {
            int l=0, r=n;
            while(l<r) {
                int mid=(l+r)>>1;
                if(x-sb[mid]<=lim) r=mid; else l=mid+1;
            }
            if(x-sb[l]<=lim) {
                cout<<dfs(l,x-sb[l])<<endl;
            } else {
                printf("%d\n",x-sb[n]);
            }
        }
    }
    return 0;
}

E

没想到是水题。

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=1005;
int T, n, m, X, Y;
int a[N][N];
int fg;
bool v[N];
vector<int> ans;
void dfs(int x) {
    // printf("x=%d\n",x);
    if(x==Y) {
        ans.pb(x);
        fg=1;
        return;
    }
    for(int i=1;i<=n;i++) if(!v[i]&&a[x][i]) {
        v[i]=1;
        dfs(i);
        v[i]=0;
        if(fg) {
            break;
        }
    }
    if(fg) ans.pb(x);
}
void solve() {
    n=read(), m=read(), X=read(), Y=read();
    rep(i,1,n) {
        v[i]=0;
        rep(j,1,n) a[i][j]=0;
    } 
    rep(i,1,m) {
        int x=read(), y=read();
        a[x][y]=a[y][x]=1;
    }
    fg=0;
    ans.clear();
    v[X]=1;
    dfs(X);
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x<<" ";
    cout<<endl;
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

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

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

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=1005;
int T, n, m, X, Y;
int a[N][N];
int fg;
bool v[N];
vector<int> ans;
void dfs(int x) {
    // printf("x=%d\n",x);
    v[x]=1;
    if(x==Y) {
        ans.pb(x);
        fg=1;
        return;
    }
    for(int i=1;i<=n;i++) if(!v[i]&&a[x][i]) {
        dfs(i);
        if(fg) {
            break;
        }
    }
    if(fg) ans.pb(x);
}i
void solve() {
    n=read(), m=read(), X=read(), Y=read();
    rep(i,1,n) {
        v[i]=0;
        rep(j,1,n) a[i][j]=0;
    } 
    rep(i,1,m) {
        int x=read(), y=read();
        a[x][y]=a[y][x]=1;
    }
    fg=0;
    ans.clear();
    dfs(X);
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x<<" ";
    cout<<endl;
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

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}
$$

线段树维护转移即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2e5+5;
const ll mod=998244353;
int n, m, a[N];
namespace seg {
    ll t[N<<2], tag[N<<2];
    void pushup(int x) { t[x]=(t[x<<1]+t[x<<1|1])%mod; }
    void maketag(int x,int l,int r,ll d) {
        t[x]=(r-l+1)*d%mod;
        tag[x]=d;
    }
    void pushdown(int x,int l,int r) {
        if(tag[x]!=-1) {
            int mid=(l+r)>>1;
            maketag(x<<1,l,mid,tag[x]);
            maketag(x<<1|1,mid+1,r,tag[x]);
            tag[x]=-1;
        }
    }
    void build(int x=1,int l=1,int r=n) {
        tag[x]=-1;
        if(l==r) { t[x]=a[l]; return; }
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void upd(int L,int R,ll d,int x=1,int l=1,int r=n) {
        if(L<=l&&r<=R) {
            maketag(x,l,r,d);
            return;
        }
        int mid=(l+r)>>1;
        pushdown(x,l,r);
        if(L<=mid) upd(L,R,d,x<<1,l,mid);
        if(R>mid) upd(L,R,d,x<<1|1,mid+1,r);
        pushup(x);
    }
    ll query(int L,int R,int x=1,int l=1,int r=n) {
        if(L<=l&&r<=R) return t[x];
        int mid=(l+r)>>1;
        pushdown(x,l,r);
        ll res=0;
        if(L<=mid) res=query(L,R,x<<1,l,mid);
        if(R>mid) (res+=query(L,R,x<<1|1,mid+1,r))%=mod;
        return res;
    }
}
ll fp(ll a,ll b) {
    ll c=1;
    for(;b;a=a*a%mod,b>>=1) if(b&1) c=c*a%mod;
    return c;
}
signed main() {
    n=read(), m=read();
    rep(i,1,n) a[i]=read();
    seg::build();
    rep(i,1,m) {
        int L=read(), R=read();
        ll res=seg::query(L,R)*fp(R-L+1,mod-2)%mod;
        // cout<<res<<endl;
        seg::upd(L,R,res);
    }
    rep(i,1,n) printf("%lld ",seg::query(i,i));
    return 0;
}

G

不会

DP搜索数学期望树论线段树贪心
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇