muti多校-5

自用笔记算法

muti多校-5

HDU 6085

题目要求

有n个小孩和m个糖果 每个小孩有Ai的钱 每个糖果值Bi的钱 小孩只会买一种糖果
给出q次询问 每次询问包含一个k 问有多少个小孩买糖果满足余下k的钱 最后的结果mod2

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define maxn 50050
using namespace std;
bitset<maxn>a,b,ans,bb;
void solve(int maxk){
    bb.reset(),ans.reset();
    for(int i=maxk;i>=0;i--){
        ans[i]=(bb&(a>>i)).count()&1;
        if(b[i]){
            for(int j=0;j<maxn;j+=i) bb.flip(j);
        }
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        a.reset(),b.reset();
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        int maxk=0;
        for(int i=0;i<n;i++){
            int x; 
            scanf("%d",&x);
            a.set(x);
        }
        for(int i=0;i<m;i++){
            int x; 
            scanf("%d",&x);
            b.set(x);
            maxk=max(maxk,x);
        }
        solve(maxk);
        while(q--){
            int x; scanf("%d",&x);
            puts(ans[x]?"1":"0");
        }
    }
    return 0;
}

思路

压位操作 理解后补上

HDU 6090

题目要求

给定n个点，m条边，让你安排点和边构成一个无向图。dis(i,j)，表示i到j最小的边数，如果无法到达，dis(i,j)为n,问每个点到其他所有的点的最小dis之和

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t; cin>>t;
    while(t--){
        LL n,m;
        cin>>n>>m;
        if(m>=n*(n-1)/2LL) cout<<n*(n-1)<<endl;
        else if(m>n-1) cout<<2LL*n*n-2LL*n-2LL*m<<endl;
        else cout<<n*n*n-n*n-n*(m*m+m)+2LL*m*m<<endl;
    }
    return 0;
}

思路

考虑贪心地一条一条边添加进去。
当m≤n−1时，我们需要最小化距离为n的点对数，所以肯定是连出一个大小为m+1的联通块，剩下的点都是孤立点。在这个联通块中，为了最小化内部的距离和，
肯定是连成一个菊花的形状，即一个点和剩下所有点直接相邻。
当m>n−1时，肯定先用最开始n-1条边连成一个菊花，这时任意两点之间距离的最大值是2。因此剩下的每一条边唯一的作用就是将一对点的距离缩减为1。
这样我们就能知道了最终图的形状了，稍加计算就能得到答案。要注意m有可能大于 n(n-1)/2
若点边关系为n(n-1)/2<=m说明每一个点可以直接连接任意一点，则距离和为n(n-1)
若点边关系为(上不满足)m>n-1不是等于，在菊花形状上加边，每加一条边距离减2
若点边关系为（上不满足）m<=n-1有几个孤立点y(y=n-(m+1))则，孤立点距离和为yn(n-1)+(n-y)yn,相连点，只有一点可直达其它
点，则距离和为m+m+2m(m-1)

HDU 6092

题目要求

T组测试，接下来一行n和m，下面一行m+1个数字代表B（0~m）求A序列，Bi 代表A序列中的所有子集之和为i的有Bi个，A序列总和为m，n个元素

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define maxn 10050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[55],b[maxn],dp[maxn];
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=m;i++) scanf("%d",&b[i]);
        mm(dp,0),dp[0]=1;
        int num=0;
        for(int i=1;i<=m;i++){
            int x=b[i]-dp[i];
            if(x<=0) continue;
            for(int j=1;j<=x;j++){
                a[++num]=i;
                for(int k=m;k>=i;k--) dp[k]+=dp[k-i];
            }
            if(num>=n) break;
        }
        for(int i=1;i<=n;i++){
            if(i==1) printf("%d",a[i]);
            else printf(" %d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

思路

dp[i]表示数组a中组合数为i的个数 通过逆序更新 类似于01背包
如果bi是数组b中除了b0以外第一个值不为0的位置 那么i就是数组a中的最小数 在a中加入该数字 并且更新dp
接着再在b中继续寻找第一个不为0的数字直到数组a的大小达到n

HDU 6095

题目要求

任意两个人相比,相差大于K,分低的淘汰,否则两人都有可能赢,剩下的继续比,问有最多多少人可能赢?

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int a[maxn];
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t; cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        int ans=1;
        for(int i=n-1;i>=1;i--){
            if(a[i+1]-a[i]<=k) ans++;
            else break;
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

签到题
排序后逆序遍历 i-1和i的位置比 如果差值小于等于k 那么ans++ 否则break 后面的数字与i的差值都会大于k无法获胜

本文标题:muti多校-5

文章作者:Hippopmonkey

发布时间:2017-08-09, 23:38:21

最后更新:2017-08-10, 01:11:42

原始链接:http://xuboming8.github.io/2017/08/09/muti多校-5/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. muti多校-5
    1. 1.1. HDU 6085
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6090
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6092
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6095
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|