正文 

当前位置： 首页 > 代码 > java教程

2018“百度之星”程序设计大赛-初赛（b）(代码片段)

bobhuang bobhuang     2022-12-23     738

关键词：

degree

 
 Accepts: 1581
 
 Submissions: 3494
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 131072/131072 K (Java/Others)
Problem Description

度度熊最近似乎在研究图论。给定一个有 NN 个点 (vertex) 以及 MM 条边 (edge) 的无向简单图 (undirected simple graph)，此图中保证没有任何圈 (cycle) 存在。

现在你可以对此图依序进行以下的操作：

  1. 移除至多 KK 条边。
  2. 在保持此图是没有圈的无向简单图的条件下，自由的添加边至此图中。

请问最后此图中度数 (degree) 最大的点的度数可以多大呢？

Input

输入的第一行有一个正整数 TT，代表接下来有几笔测试资料。

对于每笔测试资料： 第一行有三个整数 NN, MM, KK。 接下来的 MM 行每行有两个整数 aa 及 bb，代表点 aa 及 bb 之间有一条边。 点的编号由 00 开始至 N - 1N?1。

  • 0 le K le M le 2 imes 10^50≤K≤M≤2×10?5??
  • 1 le N le 2 imes 10^51≤N≤2×10?5??
  • 0 le a, b < N0≤a,b<N
  • 给定的图保证是没有圈的简单图
  • 1 le T le 231≤T≤23
  • 至多 22 笔测试资料中的 N > 1000N>1000
Output

对于每一笔测试资料，请依序各自在一行内输出一个整数，代表按照规定操作后可能出现的最大度数。

Sample Input
2
3 1 1
1 2
8 6 0
1 2
3 1
5 6
4 1
6 4
7 0
Sample Output
2
4

简单图啊， C = V-E

所以就可以这样拆边了，只和度数有关

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define num first
#define id second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=2e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int d[N];
int main()

    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    
        memset(d,0,sizeof d);
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=0,x,y;i<m;i++) cin>>x>>y,d[x]++,d[y]++;
        int ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans,n-1-max(0,m-d[i]-k));
        printf("%d
",ans);
    
    return 0;

rect

 
 Accepts: 1682
 
 Submissions: 3028
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 131072/131072 K (Java/Others)
Problem Description

度度熊有一个大小为 MX imes MYMX×MY 的矩形，左下角坐标为 (0, 0)(0,0)，右上角坐标为 (MX, MY)(MX,MY)。此矩形内有 NN 个整数坐标的点 (x_i, y_i)(x?i??,y?i??)，x_ix?i?? 彼此不重复，y_iy?i?? 彼此也不重复。

现在要从每一个点画出一条线段，满足下列条件：

  • 线段起点为坐标点，终点在矩形范围的四个边界之一上。
  • 线段彼此不能交叉。

现在要让画出的线段的长度总和最小，请输出这个最小的长度总和值。

Input

输入的第一行有一个正整数 TT，代表接下来有几笔测试资料。

对于每笔测试资料： 第一行有三个整数 MXMX, MYMY 以及 NN。 接下来的 NN 行每行有两个正整数 x_ix?i?? 及 y_iy?i??。

  • 2 le MX, MY le 10^62≤MX,MY≤10?6??
  • 0 le N le 10^50≤N≤10?5??
  • 如果 i e ji≠j，则保证 x_i e x_jx?i??≠x?j?? 及 y_i e y_jy?i??≠y?j??
  • 0 < x_i < MX0<x?i??<MX
  • 0 < y_i < MY0<y?i??<MY
  • 1 le T le 201≤T≤20
  • 至多 22 笔测试资料中的 N > 1000N>1000
Output

对于每一笔测试资料，请依序各自在一行内输出一个整数，代表可能的最小长度和。

Sample Input
2
4 4 1
2 2
10 7 3
6 3
2 6
9 5
Sample Output
2
5

限制条件比较多，x_ix?i?? 彼此不重复，y_iy?i?? 彼此也不重复。

所以最小值就可以了

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define num first
#define id second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=2e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int d[N];
int main()

    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    
        int mx,my,n;
        cin>>mx>>my>>n;
        ll sum=0;
        for(int i=0,x,y; i<n; i++)
        
            cin>>x>>y;
            int t=min(x,mx-x);
            t=min(t,y);
            t=min(my-y,t);
            sum+=t;
        
        cout<<sum<<"
";
    
    return 0;

p1m2

 
 Accepts: 1003
 
 Submissions: 4595
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 131072/131072 K (Java/Others)
Problem Description

度度熊很喜欢数组！！

我们称一个整数数组为稳定的，若且唯若其同时符合以下两个条件：

  1. 数组里面的元素都是非负整数。
  2. 数组里面最大的元素跟最小的元素的差值不超过 11。

举例而言，[1, 2, 1, 2][1,2,1,2] 是稳定的，而 [-1, 0, -1][?1,0,?1] 跟 [1, 2, 3][1,2,3] 都不是。

现在，定义一个在整数数组进行的操作：

  • 选择数组中两个不同的元素 aa 以及 bb，将 aa 减去 22，以及将 bb 加上 11。

举例而言，[1, 2, 3][1,2,3] 经过一次操作后，有可能变为 [-1, 2, 4][?1,2,4] 或 [2, 2, 1][2,2,1]。

现在给定一个整数数组，在任意进行操作后，请问在所有可能达到的稳定数组中，拥有最大的『数组中的最小值』的那些数组，此值是多少呢？

Input

输入的第一行有一个正整数 TT，代表接下来有几组测试数据。

对于每组测试数据： 第一行有一个正整数 NN。 接下来的一行有 NN 个非负整数 x_ix?i??，代表给定的数组。

  • 1 le N le 3 imes 10^51≤N≤3×10?5??
  • 0 le x_i le 10^80≤x?i??≤10?8??
  • 1 le T le 181≤T≤18
  • 至多 11 组测试数据中的 N > 30000N>30000
Output

对于每一组测试数据，请依序各自在一行内输出一个整数，代表可能到达的平衡状态中最大的『数组中的最小值』，如果无法达成平衡状态，则输出 -1?1。

Sample Input
2
3
1 2 4
2
0 100000000
Sample Output
2
33333333

不是加1和减1，但是其实就是每次把数-1，那么一定可以的啊，不存在-1

所以直接二分ans，因为操作次数越多，一定是可以做到的，我是个啥子，一小心爆了ll，现在我们需要做的就是每个数变到目标数需要进行的操作及操作数

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define num first
#define id second
#define ll long long
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=3e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int a[N],n;
int la(int x)

    ll s1=0,s2=0;
    for(int i=0; i<n; i++)
    
        if(a[i]>x+1)s2+=(a[i]-x)/2;
        else s1+=max(0,x-a[i]);
    
    return s2>=s1;

int main()

    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    
        cin>>n;
        for(int i=0; i<n; i++)cin>>a[i];
        int l=0,r=1e9,ans=0;
        while(l<=r)
        
            int mi=(l+r)/2;
            if(la(mi)) ans=mi,l=mi+1;
            else r=mi-1;
        
        cout<<ans<<"
";
    
    return 0;

 


2018“百度之星”程序设计大赛-初赛（a）(代码片段)

度度熊拼三角  Accepts:2536  Submissions:4433 TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:65536/65536K(Java/Others)ProblemDescription度度熊有 NN 根木棒，每根木棒的长度为a_ia? 查看详情

2018“百度之星”程序设计大赛-初赛（a）(代码片段)

第二题还算手稳+手快？最后勉强挤进前五百（期间看着自己从两百多掉到494名）1001 度度熊拼三角  （hdoj6374）链接：http://acm.hdu.edu.cn/showproblem.php?pid=6374签到题 题意：给n根木棒求可以拼出的周长最长的三角形可以... 查看详情

2018“百度之星”程序设计大赛-初赛（a）度度熊学队列listrope(代码片段)

c++list使用1#include<cstdio>2#include<cstdlib>3#include<cmath>4#include<cstring>5#include<time.h>6#include<string>7#include<set>8#include<map>9#include< 查看详情

2021年百度之星·程序设计大赛-初赛二1001签到（找规律，快速幂）(代码片段)

problem签到Accepts:6141Submissions:13643TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给a,ba,b，每次a,ba,b会变为a+b,a-ba+b,a−b，问kk次之后变成了哪两个数 查看详情

2017"百度之星"程序设计大赛-初赛（a）

2017"百度之星"程序设计大赛-初赛（A）hdu6108   求出n-1的因子个数即可#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#definerep(i,a,b)for(inti=a;i<=b;++i)#de 查看详情

2017"百度之星"程序设计大赛-初赛（b）小小粉丝度度熊

ProblemDescription度度熊喜欢着喵哈哈村的大明星——星星小姐。为什么度度熊会喜欢星星小姐呢？首先星星小姐笑起来非常动人，其次星星小姐唱歌也非常好听。但这都不是最重要的，最重要的是，星星小姐拍的一手好代码！于是... 查看详情

hdu6114chess组合数（2017"百度之星"程序设计大赛-初赛（b））

ChessTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):513    AcceptedSubmission(s):319ProblemDescription車是中国象棋中的一种棋 查看详情

2021年百度之星·程序设计大赛-初赛二1004净化（模拟）(代码片段)

problemsolution//1004#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constLLmod=998244353;constintmaxn=1e5+10;LLa[maxn];intmain() ios::sync_with_stdio(0),cin.tie( 查看详情

2020百度之星程序设计大赛初赛二(代码片段)

A.Poker(Hdu????)题目大意给定n个币，每次投至少m个，当投(x)个时，给回(lfloorx imes(1-p\%)floor)。问你最多能投多少次。解题思路很显然每次投(m)元是最优的，因为但凡投(m+1)元，给回的钱数不可能会增加二，要不不变要不减少。每次... 查看详情

2017"百度之星"程序设计大赛-初赛（a）

小C的倍数问题ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P... 查看详情

2017"百度之星"程序设计大赛-初赛（b）度度熊的交易计划

n个村庄m条带权路，权值为花费，村庄可以造东西卖东西，造完东西可以换地方卖，给出每个村庄造东西花费a和最多个数b、卖东西价值c和最多个数d，求最大收益。裸的费用流。然而还WA了一发。很好。建源向每个村庄连边(b,a)... 查看详情

hdu6119小小粉丝度度熊预处理+尺取法（2017"百度之星"程序设计大赛-初赛（b））

小小粉丝度度熊TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1572    AcceptedSubmission(s):513ProblemDescription度度熊喜欢着喵哈 查看详情

2021年百度之星·程序设计大赛-初赛二1005水题（贪心结论）(代码片段)

problemsolution开始还以为是CF987E，但是奇偶性并不一样，，结果是个贪心乱搞。。样例都没过交了能过，醉了。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;intmain() ios::sync_with_stdio(0),ci 查看详情

2021年百度之星·程序设计大赛-初赛二1002随机题意（区间贪心）(代码片段)

problem随机题意Accepts:1411Submissions:3641TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给一个整数数组a_1,a_2,\\cdots,a_na1​,a2​,⋯,an​和kk，你想要找到一个最大的值xx，使 查看详情

2018“百度之星”程序设计大赛-初赛（a）1004/hdu6377度度熊看球赛dp递推

度度熊看球赛ProblemDescription世界杯正如火如荼地开展！度度熊来到了一家酒吧。有N对情侣相约一起看世界杯，荧幕前正好有2×N个横排的位置。所有人都会随机坐在某个位置上。当然，如果某一对情侣正好挨着坐，他们就会有说... 查看详情

2022百度之星程序设计大赛-初赛-第二场1001和(代码片段)

problemsolution题意：给出长为n的序列，q次询问区间是否存在<=k个数之和>=x。n,q<1e5，k<10.思路：因为要和>=x，所以让和尽可能大，即判断区间中最大的k个数之和是否大于x即可。即区间最... 查看详情

2017"百度之星"程序设计大赛-初赛（a）小c的倍数问题

ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P进制下，一个正... 查看详情

hdu5253连接的管道(kruskal)(百度之星程序设计大赛-初赛)

连接的管道TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1323    AcceptedSubmission(s):519ProblemDescription老Jack有一片农田 查看详情