8.3 18级牛客多校第八场

比赛过程

  挺难的一场，差点以为要爆零了，刚开始看 I 题是个二分图匹配问题，以为是个网络流签到题，结果各种T，后来转换思路写类拓扑排序，可能是图没建好一直wa，全程懵逼。

题解

I

题意

  每次输入一对数 $x,y$，让你从中二选一，每个数只能选一次，问你最多选多少数。

解法

  把不同的数当成点，把每次输入当成边，答案就是图中总点数减去树形连通块的分量。因为对于树来说，假如有k个点，k-1条边，那么肯定有个点选不了，而如果是环，k个点k条边就都可以选到。（比赛时候脑子瓦特了，可能是受初始想法二分图影响大了）

代码

const int maxn = 2e5 + 5;
vector<int> v[maxn];
int vis[maxn];
bool dfs(int x,int fa){
if(vis[x]) return 1;
vis[x] = 1;
int f = 0;
for(auto i:v[x]){
if(i==fa) continue;
f += dfs(i, x);
}
return f;
}
int main(){
IO;
int T;
cin >> T;
FOR(_,1,T){
int n;
int cnt = 1;
cin >> n;
map<int, int> mp;
FOR(i,1,2*n){
vis[i] = 0;
v[i].clear();
}
FOR(i,1,n){
int x, y;
cin >> x >> y;
if(!mp[x]) mp[x]=cnt++;
if(!mp[y]) mp[y]=cnt++;
v[mp[x]].push_back(mp[y]);
v[mp[y]].push_back(mp[x]);
}
int l = mp.size();
int ans = l;
FOR(i,1,l){
if(!vis[i]){
if(!dfs(i,0)) ans--;
}
}
printf("Case #%d: %dn", _, ans);
}
return 0;
}

K

题意

• 有n种菜，每种菜的数量为 $b_i$, 每个菜的盈利为 $a_i$(可能为负数)。
• 每个顾客必须从第1种菜开始，连续地吃，每种吃一个。
• 保证顾客最多的情况下，盈利最大。

解法

  $b_1$ 就是最大顾客数量。然后求盈利的前缀和，从大到小取即可。学习使用int128。

代码

const int maxn = 1e5 + 5;
__int128_t sum[maxn], ma[maxn];
ll a[maxn], b[maxn], id[maxn];
inline void write(__int128 x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main(){
IO;
int T;
cin >> T;
FOR(_,1,T){
int n;
cin >> n;
FOR(i,1,n) sum[i] = 0;
FOR(i,1,n){
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
if(i==1){
ma[i] = sum[i];
id[i] = i;
}
else{
id[i] = id[i - 1];
ma[i] = ma[i - 1];
if(sum[i]>ma[i]){
ma[i] = sum[i];
id[i] = i;
}
}
}
FOR(i,1,n){
cin >> b[i];
if(b[i] > b[i-1] && i != 1) b[i] = b[i-1];
}
__int128_t ans = 0;
__int128_t di = 0;
for (int i = n;i>=1;){
ll temp = id[i];
ans += ((__int128_t)b[temp] - di) * ma[i];
i = temp - 1;
di = b[temp];
}
printf("Case #%d: %d ", _, b[1]);
write(ans);
cout << endl;
}
return 0;
}

1005

题意

解法

代码

1007

题意

解法

代码

1010

题意

解法

代码

最后

以上就是发嗲汉堡为你收集整理的8.3 18级牛客多校第八场的全部内容，希望文章能够帮你解决8.3 18级牛客多校第八场所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。