蓝桥云课—全新算法赛内测赛2
A 新一与基德的身高大战
A思路：
我们想要得到n个孩子的身高和最大，那么父亲和母亲的身高我们要最好是偶数，因为这样我们就可以不用担心下取整了，不然会少0.5，所以我们只要最优考虑得到的是偶数就可以了，不是很难想，还有一个坑就是不能将所有身高加在一起再除以2，我们是俩俩生一个孩子，这样不久相当于一群生一个孩子了吗？？？
A代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
ll ans=0;
int cnt1=0;
int cnt2=0;
cin>>n;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
ans+=x;
if(x%2){
cnt1++;
}
}
for(int i=1;i<=n;i++){
ll x;
cin>>x;
ans+=x;
if(x%2){
cnt2++;
}
}
cout<<(ans-abs(cnt1-cnt2))/2<<endl;
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
B 肖恩的投球游戏加强版
B思路：
很可惜这个题我错了，看上边的图这其实就是一个简单的差分加上前缀和的应用，但是我没有写对，也没找出来哪里错了，然后我就又重新写了一遍。
找到错误了，原本是n行m列，输出变成了n行n列，一个字母之差！！！！
B代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long intt;
intt a[N][N];
intt b[N][N];
void insert(intt x1,intt y1,intt x2,intt y2,intt c)
{ //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
void solve(){
intt n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
intt x;
cin>>x;
insert(i,j,i,j,x);
}
}
while(q--){
intt x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j] = a[i - 1][j] + a[i][j - 1] + b[i][j] - a[i - 1][j - 1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
return 0;
}
C 体育健将
C思路：
刚开始看到这个题这不就很明显的01背包问题嘛，后来一看数据范围就把我劝退了，后来看这个题竟然有知识点标签，诶？直接往那方面想不就好了，这就是一个贪心题，记住最后一个比赛咱们是可以不用算休息时间的！
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node
{
int a,b,c;
}x[N];
bool cmp(node x,node y){
return x.c<y.c;
}
void solve(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>x[i].a;
}
for(int i=1;i<=n;i++){
cin>>x[i].b;
x[i].c=x[i].a+x[i].b;
}
sort(x+1,x+n+1,cmp);
int res=0;
int cnt=0;
for(int i=1;i<=n;i++){
if(k<=0){
break;
}
else{
if(k>=x[i].c||k>=x[i].a){
cnt++;
k-=x[i].c;
}
}
}
cout<<cnt<<endl;
}
int main(){
int t;
t=1;
while(t--){
solve();
}
return 0;
}
D 小桥的奇异旋律
D思路：
看起来像一个前缀和的应用，我们只需要看看前缀和变成正负正负正负或者负正负正负正....的最小改变次数即可。比较两次取最小值。
看了网友的代码！我发现这个题模拟就可以实现！！！
D代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100010],n,a1,a2;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int fla=1;ll all=0;
for(int i=1;i<=n;i++){
all+=a[i];
if(fla>0){
if(all<=0){
a1+=1-all;
all=1;
}
}
else {
if(all>=0){
a1+=all+1;
all=-1;
}
}
fla=-fla;
}
fla=-1;all=0;
for(int i=1;i<=n;i++){
all+=a[i];
if(fla>0){
if(all<=0){
a2+=1-all;
all=1;
}
}
else {
if(all>=0){
a2+=all+1;
all=-1;
}
}
fla=-fla;
}
cout<<min(a1,a2)<<endl;
return 0;
}
E 区间or划分
E思路：
好吧这个题涉及到位运算了，事实上位运算一直学的都不太好，大家还是看看网上大佬的代码和解释吧
樱花树下的邂逅的思路和代码：
简单枚举一下，或运算相当于不进位加法，划分区间后或再求和只会更大，或者等于整个区间或，所以这题最小值是确定值，我们必须把二进制表示下1的位置相同的要放到同一区间。
E代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<sstream>
#include<cmath>
#include<list>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#define bitcnt(x) (__builtin_popcountll(x))//ll二进制数中1的个数
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n;
cin>>n;
vector<int> a(n+1);
vector<int> s(n+1);
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]|a[i];
int res=s[n];
int k=0;
int all=0;
for(int i=n;i>=2;i--){
all|=a[i];
// if((all+s[i-1])==s[n]) k+=1;
if((all&s[i-1])==0) k++;
}
cout<<res<<" "<<k+1<<endl;
return 0;
}
F 忙碌的Alice
F思路+代码：
首先第一步就是要建图，这一点不用说比较好建，因为我们需要以0点对其他点进行最短路径的更新，这点是一定要注意的，更新完最短路径之后，便是可以进行二分来找到第k小的d(i,j)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e4 + 10, M = 1e6 + 10;
LL n, m, k;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int dist1[N], dist2[N];
bool st[N];
LL get(int x) // 小于等于 x 的有几个
{
LL res = 0;
for (int i = 1; i <= n; ++ i )
{
int l = 1, r = n;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (dist2[mid] + dist1[i] <= x)
l = mid;
else
r = mid - 1;
}
if (dist2[l] + dist1[i] <= x)
res += l;
if (res >= k)
return res;
}
return res;
}
void add(int h[], int a, int b, int c) // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int h[], int dist[]) // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 0});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
memset(h1, -1, sizeof h1);
memset(h2, -1, sizeof h2);
while (m -- )
{
int op, a, b, c;
cin >> op >> a >> b >> c;
add(h1, a, b, c);
if (!op)
add(h1, b, a, c);
add(h2, b, a, c);
if (!op)
add(h2, a, b, c);
}
memset(dist1, 0x3f, sizeof dist1);
dist1[0] = 0;
memset(dist2, 0x3f, sizeof dist2);
dist2[0] = 0;
dijkstra(h1, dist1);
dijkstra(h2, dist2);
sort(dist1 + 1, dist1 + n + 1);
sort(dist2 + 1, dist2 + n + 1);
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (get(mid) < k)
l = mid;
else
r = mid - 1;
}
cout << l + 1 << endl;
return 0;
}