ABC416
|
比赛,题解
|

1135 字
|
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 eb emplace_back
#define ef emplace_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, l, r;
string s;
signed main() {
    n=read(), l=read(), r=read();
    cin>>s;
    int fg=1;
    rep(i,l-1,r-1) if(s[i]!='o') fg=0;
    puts(fg? "Yes":"No");
    return 0;
}

B

想死了。

自己的做法是这样的。肉眼看出我们可以在每个#两边极远处的.放o，单调栈出来加上一堆判断就行。

因为实现不好导致浪费了 50min……

#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 eb emplace_back
#define ef emplace_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;
}
string s;
int n, l[105], r[105];
int top, st[105];
signed main() {
    cin>>s;
    n=s.size();
    s=" "+s;
    rep(i,1,n) {
        while(top&&s[st[top]]!='#') {
            --top;
        }
        l[i]=st[top];
        st[++top]=i;
    }
    top=0;
    per(i,n,1) {
        while(top&&s[st[top]]!='#') --top;
        r[i]=st[top];
        st[++top]=i;
    }
    int cnt=0, L=0, R=n;
    rep(i,1,n) if(s[i]=='#') {
        if(!l[i]) l[i]=0;
        if(!r[i]) r[i]=n+1;
        int fg=1;
        rep(j,l[i]+1,i) if(s[j]=='o') fg=0;
        if(fg&&s[l[i]+1]!='#') s[l[i]+1]='o', cnt++;
        fg=1;
        rep(j,i,r[i]-1) if(s[j]=='o') fg=0;
        if(fg&&s[r[i]-1]!='#') s[r[i]-1]='o', cnt++;
    }
    if(!cnt) {
        rep(i,1,n) {
            if(s[i]=='.') s[i]='o';
            break;
        }
    }
    // cout<<s;
    for(auto x:s) if(x!=' ') printf("%c",x);
    return 0;
}

事实上，答案不唯一，是不是极远处根本无所谓，所以直接在每个#后面的.放o就能满足条件。

在最前面加上一个字符#即可。

给出题解代码吧，太耻辱了……

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<char> t(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '#') {
            cout << '#';
        } else if (i == 0 || s[i - 1] == '#') {
            cout << 'o';
        } else {
            cout << '.';
        }
    }
    cout << endl;
    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 eb emplace_back
#define ef emplace_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, k, x;
string s[20];
vector<string> ans;
void dfs(int now,string t) {
    if(now==k) {
        ans.eb(t);
        return;
    }
    rep(i,1,n) {
        dfs(now+1,t+s[i]);
    }
}
signed main() {
    n=read(), k=read(), x=read();
    rep(i,1,n) cin>>s[i];
    dfs(0,"");
    sort(ans.begin(),ans.end());
    cout<<ans[x-1];
    return 0;
}

D

注意到 $A_i,B_i \in [0,M)$，那么当且仅当 $A_i + B_i \ge M$，会让答案减小一个定值 $M$。问题转化为对于尽可能多的 $A_i$，找 $B_j$ 与其匹配，满足 $A_i+B_j \ge M$。

显然较大的 $A_i$ 更易满足条件。从大到小考虑，用std::multiset维护 ${B_i}$，找到大于等于 $M-A_i$ 的最小的 $B_j$。如果不存在，那么取最小值一定最优。

#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 eb emplace_back
#define ef emplace_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=3e5+5;
int T, n, mod, a[N], b[N];
multiset<int> s;
void solve() {
    s.clear();
    n=read(), mod=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) b[i]=read(), s.insert(b[i]);
    sort(a+1,a+n+1);
    ll ans=0;
    per(i,n,1) {
        auto p=s.lower_bound(mod-a[i]);
        if(p!=s.end()) {
            ans+=(a[i]+(*p))%mod;
            s.erase(p);
        } else {
            ans+=a[i]+(*s.begin());
            s.erase(s.begin());
        }

    }
    cout<<ans<<endl;
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

E

Trick 都忘光了……

没有机场怎么做？先跑 $\text{Floyd}$。对于加边操作，枚举 $(i,j)$，用 $d(i,x)+z+d(y,j)$ 和 $d(i,y)+z+d(x,j)$ 更新 $d(i,j)$ 即可。

有机场怎么办？建一个虚点。机场到达虚点需要时间 $T$，虚点到达任何机场需要时间 $0$。这样就能描述从某点到机场，再中转其他点，再到另一个点的过程。

建立机场，拿着这两条边更新即可。

#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 eb emplace_back
#define ef emplace_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 ll inf=1e15;
const int N=505;
int T, n, m, k, Q;
ll f[N][N];
vector<int> ap;
void Floyd() {
    rep(k,1,n+1) rep(i,1,n+1) rep(j,1,n+1) {
        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    }
}
signed main() {
    n=read(), m=read();
    rep(i,1,n+1) {
        rep(j,1,n+1) f[i][j]=inf;
        f[i][i]=0;
    }
    rep(i,1,m) {
        int x=read(), y=read(), z=read();
        f[x][y]=f[y][x]=min(f[x][y],1ll*z);
    }
    k=read(), T=read();
    rep(i,1,k) {
        int x=read();
        f[x][n+1]=T, f[n+1][x]=0;
        // ap.eb(x);
    }
    for(auto x:ap) for(auto y:ap) f[x][y]=f[y][x]=min(f[x][y],1ll*T);
    Floyd();
    Q=read();
    while(Q--) {
        int op=read();
        if(op==1) {
            int x=read(), y=read(), z=read();
            rep(i,1,n+1) rep(j,1,n+1) f[i][j]=min({f[i][j],f[i][x]+z+f[y][j],f[i][y]+z+f[x][j]});
        }
        if(op==2) {
            int x=read();
            f[x][n+1]=T, f[n+1][x]=0;
            rep(i,1,n+1) rep(j,1,n+1) {
                f[i][j]=min(f[i][j],f[i][x]+T+f[n+1][j]);
                f[i][j]=min(f[i][j],f[i][n+1]+f[x][j]);
            }
        }
        if(op==3) {
            ll ans=0;
            rep(i,1,n) rep(j,1,n) if(f[i][j]<1e15) ans+=f[i][j];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

F

桑之未落，其叶沃若。

不难发现，对于一棵子树，其根节点只有三种情况。

  1. 不在任何一条链中。
  2. 在一条链的末端。
  3. 在一条链的中间。

考虑子树合并的过程：以 $y$ 为根的子树加入以 $x$ 为根的子树。前者链数为 $j$，后者链数为 $i$。

如果不连接 $x,y$，那么新子树的链数就是 $i+j$。我们取其最大值即可。

如果连接 $x,y$，那就要分两种情况。

  1. $x$ 在一条链的末端。此时链数为 $i+j \in [1,k]$。
  2. $x$ 在一条链的中间。此时链数为 $i+j-1 \in [1,k]$。

都要求 $y$ 必须在一条链的末端。

因此，设 $f(x,i,0/1/2)$ 表示，以 $x$ 为根的子树，选出了 $i$ 条链，其中 $x$ 的情况是 无限制/必须在链的末端/必须在链的中间，所能得到的最大收益。

转移就是朴素的树上背包，比上述讨论多了在不连接的情况下，对应状态的继承。具体细节见代码。

为啥 $0$ 状态时这个意思呢？相当于包含了情况 1 并取了个 $\max$，便于转移。

#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 eb emplace_back
#define ef emplace_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 inf=1e18;
int n, k, a[N];
ll f[N][6][3], g[6][3];
vector<int> p[N];
void dfs(int x,int fa) {
    rep(i,0,k) rep(j,0,2) f[x][i][j]=-inf;
    f[x][0][0]=0;
    for(auto y:p[x]) if(y!=fa) {
        dfs(y,x);
        rep(i,0,k) {
            g[i][0]=f[x][i][0];
            g[i][1]=f[x][i][1];
            g[i][2]=f[x][i][2];
        }
        for(int i=0;i<=k;i++) for(int j=0;j<=k;j++) {
            if(i+j<=k) {
                g[i+j][0]=max(g[i+j][0],f[x][i][0]+f[y][j][0]);
                // 无限制，随便转移，反正不连接
                g[i+j][1]=max({g[i+j][1],f[x][i][1]+f[y][j][0],f[x][i][0]+a[x]+f[y][j][1]});
                // 不连接，x要求1状态，y无所谓
                // 连接不再赘述
                g[i+j][2]=max(g[i+j][2],f[x][i][2]+f[y][j][0]);
                // 不连接，同上
            }
            if(i+j-1>0&&i+j-1<=k) g[i+j-1][2]=max(g[i+j-1][2],f[x][i][1]+f[y][j][1]);
            // 连接，会共用一条链。要求二者都得在末端
        }
        rep(i,0,k) {
            f[x][i][0]=g[i][0];
            f[x][i][1]=g[i][1];
            f[x][i][2]=g[i][2];
        }
    }
    rep(i,1,k) f[x][i][1]=max(f[x][i][1],f[x][i-1][0]+a[x]);
    rep(i,0,k) f[x][i][0]=max({f[x][i][0],f[x][i][1],f[x][i][2]});
}
signed main() {
    n=read(), k=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n-1) {
        int x=read(), y=read();
        p[x].eb(y);
        p[y].eb(x);
    }
    dfs(1,0);
    ll ans=0;
    rep(i,0,k) ans=max(ans,f[1][i][0]);
    printf("%lld\n",ans);
    return 0;
}

G

不会。

DP图论最短路树形DP背包贪心
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇