Codeforces Global Round 16

链接

A. Median Maximization

链接

题目大意：给定两个正整数 n 和 s。找到一个由 n 个非负整数（不一定是不同的）组成的数组的最大可能中位数，使得其元素的总和等于 s。

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ;
cin>>n;
while(n -- )
{
int a, b ;
cin>>a>>b;
int z;
if(a % 2 == 1 ) a +=1, z =a / 2 ;
else a +=2 , z =a - a / 2 ;
cout <<b/z<<endl;
}
return 0 ;
}

B. MIN-MEX Cut

链接

题目大意：将字符串切分 ， 字符串的值为0 1 2 中最小的没有出现的数字，求最小的值

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ;
cin>>n;
while(n -- )
{
string a ;
cin>>a ;
int x1 = 0 ,x0 = 0 ;
for(int i = 0 ; i <a.length() ; i ++ )
{
if(a[i] =='1')
{
x1 ++ ;
while(a[i] == '1') i ++ ;
i -- ;
}
else
{
x0 ++ ;
while(a[i] =='0') i ++ ;
i-- ;
}
}
if(x0 ==
0 ) cout<<"0"<<endl;
else if(x1 == 0 ) cout<<"1"<<endl;
else if(x0 == 1 ) cout<<"1"<<endl;
else cout<<"2"<<endl;
}
}

C. MAX-MEX Cut

链接

题目大意两行字符， 将字符串切分 ， 字符串的值为0 1 2 中最小的没有出现的数字，求最大的值。
如果上下不同则值为2 ， 如果上下相同， 同为1 时向后看一个， 如果下一位相同为0 ， 则两位放在一起值为2 。如果相同为0 ， 向后看一位， 相同为1答案加2 ，不同加1

#include <bits/stdc++.h>
using namespace std;
int main()
{
int _ ;
cin>>_;
while(_ -- )
{
int n ;
cin>>n;
string a , b ;
cin>>a>>b;
int res = 0;
for(int i =0 ; i < n ; i ++ )
{
if(a[i] == b[i] && a[i]== '0')
{
if(a[i + 1] ==b[i + 1 ] && a[i + 1 ] == '1')
{
res +=2;
i++ ;
}
else res +=1 ;
}
else if(a[i] == b[i]
&& a[i] == '1')
{
if(a[i + 1 ]== b[i + 1 ] && a[i + 1 ] =='0')
{
res += 2 ;
i++;
}
}
else if(a[i] != b[i ]) res += 2 ;
}
cout<<res<<endl;
}
return 0 ;
}

D1. Seating Arrangements (easy version)

链接

求正序对，暴力枚举

#include <bits/stdc++.h>
using namespace std;
const int N = 310 ;
int n , m ;
int a[N] ;
int main()
{
int _;
cin>>_;
while(_ -- )
{
cin>>n>>m;
for(int i = 0 ; i < m; i ++ ) cin>>a[i];
int res =
0 ;
for(int i = 0 ; i < m;i ++ )
{
for(int j = i + 1 ; j < m ; j ++ )
{
if(a[i] <a[j]) res ++ ;
}
}
cout<<res<<endl;
}
return 0 ;
}

D2. Seating Arrangements (hard version)

链接

d1 的升级版
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int ,int > PII;
int t ;
int n , m ;
int main()
{
cin>>t;
while(t -- )
{
cin>>n>>m;
vector<PII >all(n * m ) ;
for(int i = 0 ; i < n * m ; i
++ )
{
cin>>all[i].first;
all[i].second = i ;
}
sort(all.begin() , all.end()) ;
for(int i = 0 ; i < n * m
; i ++ )
{
all[i].second *=-1;
//cout<<all[i].second;
}
long long
ans = 0;
for(int i = 0 ; i < n ; i ++
)
{
sort(all.begin() + i * m
, all.begin() + i * m + m ) ;
for(int j = 0 ; j < m ; j ++ )
{
for(int k = j + 1 ; k < m ; k ++ )
{
if(all[j + i * m ].second > all[k + i * m ].second) ans ++ ;
}
}
}
cout<<ans<<endl;
}
return 0 ;
}

E. Buds Re-hanging

链接

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+ 10;
vector<int>all[N] ;
int ans ;
int n , m ;
int a , b ;
void init()
{
for(int i = 0 ;i <= n ; i ++ ) all[i].clear() ;
ans = 0 ;
}
int dfs(int u , int k )
{
int cnt =0 ;
for(auto f :all[u])
{
if(f == k ) continue ;
cnt += dfs(f , u ) ;
}
if(cnt != 0 )
{
ans += cnt - 1 ;
return 0;
}
else return 1;
}
int main()
{
int _ ;
cin>>_;
while(_ -- )
{
init() ;
cin>>n;
for(int i = 0 ; i < n - 1 ; i ++ )
{
cin>>a>>b;
all[a].push_back(b);
all[b].push_back(a) ;
}
dfs(1 , -1 ) ;
cout<<ans + 1
<<endl;
}
return
0 ;
}

待更新

最后

以上就是唠叨雨为你收集整理的Codeforces Global Round 16Codeforces Global Round 16的全部内容，希望文章能够帮你解决Codeforces Global Round 16Codeforces Global Round 16所遇到的程序开发问题。

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