概述
A-Median Maximization
题意
给出n和s，求n个数字和为s的情况下，求中位数的最大值。
思路
签到题，贪心，中位数前面全为0，后面都平均下来，如果不是整数，那么就在给后面让它最大
代码
当时是用的隐藏掉的部分，因为时间不等人，分情况百分百对就没有考虑那么多了...好吧是我菜了
inline void Case_Test()
{
cin>>n>>s;
//if (n%2==1) n-=n/2;
//else n-=(n-1)/2;
n-=(n-1)/2;
cout<<s/n<<endl;
}B-MIN-MEX Cut
题意
MEX就是没出现的最小数字，给一个01串，可以将这个字符串求最小的MEX和是多少。
思路
我们可以看出，如果有"01"的话，那么就是2，这样划不来，实际上我们可以将一个"01"直接分成"0"和"1"，这样的话答案只贡献了1(1+0)，因为MEX("1")=0，那么我们就将1分割开来，看有多少个"01"，但是最后要取min(2,ans)，因为答案最多才是2，不可能比2还多，因为我们什么也不选，选择原串才到2，只出现了01，MEX(s)=2
代码
inline void Case_Test()
{
cin>>s;
l=s.length();
ans=0;
if (s[0]=='1') ans+=0,pre=1;
else ans+=1,pre=0;
//cout<<ans<<" "<<pre<<endl;
for (int i=1;i<l;i++)
{
tmp=s[i]-'0';
if (tmp==pre) continue;
if (tmp==1) // tmp=0
ans+=0,pre=1;
else //tmp = 1
ans+=1,pre=0;
}
cout<<min(ans,2)<<endl;
}C-MAX-MEX Cut
题意
给出一个两行的字符串，跟B很像，可以将原串分为若干个两行子串，求最大的MEX和，好吧，大致是这个意思。
思路
这个两行好难打，还得用latex，我还是简单写吧，还是按照B题一样看，一行一行相邻的比较，大致就是遇到一列是"01"的话就直接ans+=2，因为贪心嘛，要求最大的MEX和，那么遇到能凑2的就凑2...然后我当时做题，就是前一列是{00,01,11}和后一列是{00,01,11}一共三三得九种情况，然后判断，大致就能贪心出来了，比如如果前一列是"00"后一列是"11"，那么这个时候能凑出2了，然后清零（具体清零操作就是pre=-1）
但是注意一点，如果是"00"遇到"01"，我这里wa了一发，就是这时候得分开算，ans+=3，因为可以分成两个，前面"00"贡献是1后面的"01"贡献是2。
代码
inline void Case_Test()
{
int ans=0;
cin>>n>>s1>>s2;
for (int i=0;i<n;i++)
a[i]=s1[i]+s2[i]-'0'-'0';
pre=a[0];
if (a[0]==1) ans+=2,pre=-1;
//for (int i=0;i<n;i++) cout<<a[i]<<" ";
//cout<<endl;
for (int i=1;i<n;i++)
{
int t=a[i];
//cout<<i<<" "<<a[i]<<" "<<pre<<endl;
if (pre==-1)
{
pre=t;
if (t==1) pre=-1,ans+=2;
continue;
}
if (pre==0)
{
if (a[i]==0) ans+=1;
if (a[i]==1) ans+=3,pre=-1;
if (a[i]==2) ans+=2,pre=-1;
}
else if (pre==1)
{
ans+=2;
pre=-1;
}
else if (pre==2)
{
if (a[i]==0||a[i]==1) ans+=2,pre=-1;
else pre=2;
}
//cout<<i<<" "<<ans<<endl;
}
if (pre==0) ans++;
if (pre==1) ans+=2;
//cout<<pre<<endl;
cout<<ans<<endl;
}
D1-Seating Arrangements (easy version)
题意
给出一个n和m，在这个题目n=1，是简单版本。然后一共有n*m个座位，每个人都有一个视力值，视力小的坐前面，然后问不方便值是多少，不方便值就是越过有人坐的位置，每个人进入座位的顺序都是按照读入的顺序。
思路
当n=1,m最大也才300，那么我们可以按照一边读入一边来算前面有多少，直接暴力两层循环搞定，重点是在第二题D2
代码
inline void Case_Test()
{
cin>>n>>m;
ans=0;
for (int i=1;i<=n*m;i++)
{
cin>>a[i];
for (int j=1;j<i;j++)
if (a[i]>a[j]) ans++;
}
cout<<ans<<endl;
}D2-Seating Arrangements (hard version)
题意
题意就是如D2，具体就是看原题吧
思路
按照第一题的思路，我们来想第二题的暴力思路，然后想办法优化降时间复杂度，这里直接讲吧。
因为要求最小，所以按照模拟，每个进入顺序都会进入到一个固定的位置，假如有相同的，那么先进入的会进入到后面的座位，因为如果相反，那么下一个相同的数会跨过ta，ans++。所以我们用结构体，然后sort一遍（手写cmp）得到每个人应该到的位置，最后循环来进一步判断。
struct node
{
int v,pos;
}b[N];
int n,m,t,x,y;
struct carry
{
int v,x,y;
}a[N];
int ans,tmp;
vector<int> v[301];
inline bool cmp(node x,node y)
{
if (x.v==y.v) return x.pos<y.pos;
return x.v<y.v;
}暴力：一个二维数组a[i][j]来表示位置，每进入一个人就填入它，然后循环模拟前面有多少个，这样的时间复杂度是O(n^3)，不太现实，所以我们来降一个时间复杂度。因为每一行都是升序的，所以我们就用二分来看，但是如果是数组的话没进入就是0的话就不太行，所以换一种容器，我第一个想到的是set，set可以插入，插入后是有序的，但是我不知道可以这样...
set<int> s[n];我后面想的是vector容器，但是插入的话又不能有序插入，所以...我上网搜了，可以这样：
v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v);这样我们就能模拟每一个v[x]（x代表x排/行）中的几个人，视力是多少，当每次进入一个人的时候，就先提取出它应该在哪个x行，然后用二分(O(logn))判断在哪一个位置（前面有多少个） ，所以一共时间复杂度是O(Tn^2logn)
for (int i=1;i<=n*m;i++)
{
x=a[i].x;
tmp=lower_bound(v[x].begin() , v[x].end() , a[i].v)-v[x].begin();
ans+=tmp;
v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v);
//cout<<i<<" "<<tmp<<endl;
}代码
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<deque>
#include<vector>
#include<iostream>
#include<map>
#include<unordered_map>
#include<set>
#include<iomanip>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define endl "n"
#define debug(a) cout<<#a<<"="<<a<<endl;
#define eps 1e-8
using namespace std;
ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const int inf=0x3f3f3f3f;
const int N = 90007;
struct node
{
int v,pos;
}b[N];
int n,m,t,x,y;
struct carry
{
int v,x,y;
}a[N];
int ans,tmp;
vector<int> v[301];
inline bool cmp(node x,node y)
{
if (x.v==y.v) return x.pos<y.pos;
return x.v<y.v;
}
inline void Case_Test()
{
cin>>n>>m;
for (int i=1;i<=n*m;i++)
{
cin>>a[i].v;
b[i].v=a[i].v;
b[i].pos=i;
}
sort(b+1,b+1+n*m,cmp);
x=n;y=m;
for (int i=n*m;i>=1;i--)
{
t=b[i].pos;
a[t].x=x;
a[t].y=y;
y--;
if (y==0) y=m,x--;
}
//for (int i=1;i<=n*m;i++) cout<<a[i].v<<" "<<a[i].x<<" "<<a[i].y<<endl;
ans=0;
for (int i=1;i<=300;i++) v[i].clear();
for (int i=1;i<=n*m;i++)
{
x=a[i].x;
tmp=lower_bound(v[x].begin() , v[x].end() , a[i].v)-v[x].begin();
ans+=tmp;
v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v);
//cout<<i<<" "<<tmp<<endl;
}
cout<<ans<<endl;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("IO\in.txt","r",stdin);
freopen("IO\out.txt","w",stdout);
clock_t start, end;
start = clock();
#endif
IOS
int _=1;
cin>>_;
while (_--)
{
Case_Test();
}
#ifndef ONLINE_JUDGE
end = clock();
cout << endl << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "sn";
#endif
}E-Buds Re-hanging
题意
给出一个树，你可以将芽连上别的顶点（这个顶点不能是自己这一支，实际上就是保证还是一棵树），求问经过若干个操作后最少的叶子树是多少。
思路
曹佬：dfs找芽，叶，其他。找到芽之后直接把芽断开。答案是芽上的叶子+其他叶子-芽数。注意特判根
代码
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<deque>
#include<vector>
#include<iostream>
#include<map>
#include<unordered_map>
#include<set>
#include<iomanip>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define endl "n"
#define debug(a) cout<<#a<<"="<<a<<endl;
#define eps 1e-8
using namespace std;
ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const int inf=0x3f3f3f3f;
const int N = 2e5+1;
struct node
{
int to,next;
}edge[N<<1|1];
int head[N],cnt;
inline void add(int x,int to)
{
edge[++cnt].to=to;
edge[cnt].next=head[x];
head[x]=cnt;
}
int u,v,n,num_ya,num_ye,ans;
inline int dfs(int x,int pre)
{
bool ya=true;
int cnt=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==pre) continue;
int t=dfs(y,x);
//t=0 wu t=1 ye t=2 ya
if (t==0) ya=false;
if (t!=2) cnt++;
//cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl;
}
//cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl;
if (cnt&&ya&&x!=1)
{
num_ya++;
ans+=cnt;
return 2;
}
//ya
if (cnt==0&&x!=1) return 1;
//ye
if (x==1&&cnt==0) cnt++;
//cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl;
num_ye+=cnt;
return 0;
//wu
}
inline void Case_Test()
{
cin>>n;
memset(head,0,sizeof(head));
for (int i=1;i<n;i++)
{
cin>>u>>v;
add(u,v);add(v,u);
}
ans=0;num_ya=0;num_ye=0;cnt=0;
dfs(1,-1);
cout<<max(1,ans-num_ya+num_ye)<<endl;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("IO\in.txt","r",stdin);
freopen("IO\out.txt","w",stdout);
clock_t start, end;
start = clock();
#endif
IOS
int _=1;
cin>>_;
while (_--)
{
Case_Test();
}
#ifndef ONLINE_JUDGE
end = clock();
cout << endl << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "sn";
#endif
}F-Points Movement
待补
总结
这一场上了大分+178，马上1500了，小号也1404，冲冲冲！
最后
以上就是谦让人生为你收集整理的Codeforces Global Round 16 A-E 部分题解的全部内容，希望文章能够帮你解决Codeforces Global Round 16 A-E 部分题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复