multi多校-2

自用笔记算法

muti多校-2

HDU 6045

题目要求

A和B两个人答题 每题有ABC三个选项 给出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
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define maxn 80050
#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;}
char a[maxn],b[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,x,y;
        cin>>n>>x>>y;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        int num1=0;
        for(int i=1;i<=n;i++) if(a[i]==b[i]) num1++;
        int num2=n-num1;
        if(x+y<=num1*2+num2 && num2>=abs(x-y)) cout<<"Not lying"<<endl;
        else cout<<"Lying"<<endl;
    }    
    return 0;
}

思路

找出A和B位置相同的个数num1 不相同的个数num2
有两个限制条件：A和B最多答对的题目个数为2*num1+num2 相同位置都可对 不同位置只可对一个
另一个为abs(x-y)为A和B至少答题不一样的个数 它必须小于等于总得不同题个数num2

HDU 6055

题目要求

给出二维坐标系上一些整点 判断他们可以形成多少正多边形

参考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
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define maxn 450
#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 vis[maxn][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 n;
    while(cin>>n){
        mm(vis,0);
        for(int i=0;i<n;i++){
            int x,y;
            cin>>x>>y;
            vis[x+100][y+100]=1;
        }
        int sum=0;
        for(int i=0;i<202;i++){
            for(int j=0;j<202;j++){
                if(!vis[i][j]) continue;
                vis[i][j]=0;
                for(int k=i;k<202;k++){
                    for(int p=j+1;p<202;p++){
                        if(!vis[k][p]) continue;
                        int xx=k-i,yy=p-j;
                        if(vis[i+yy][j-xx] && vis[i+xx+yy][j+yy-xx]) sum++;
                    }
                }
                vis[i][j]=1;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

思路

由于必须为整点 所以只能为正方形
把题目要求的-100到100扩大到0到200 同时数组多开2倍
暴力枚举2个点判断剩下2个点是否可行

HDU 6047

题目要求

给出数组a和数组b 每次可以在数组b中选取一个数字(选取过的数字不可再选) 在数组a范围b[i]到末尾的数字中选取a[i]-i最大的数字放到末尾
重复以下步骤直到数组b被用完 问添加到末尾的数字总和最大是多少

参考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
41
42
43
44
45
46
#include<bits/stdc++.h>
#define maxn 250050
#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;}
LL a[maxn],b[maxn];
LL Max[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 n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]-=i;
        }
        for(int i=1;i<=n;i++) cin>>b[i];
        sort(b+1,b+1+n);
        mm(Max,0),Max[n]=a[n];
        for(int i=n-1;i>=1;i--) Max[i]=max(Max[i+1],a[i]);
        LL ans=Max[b[1]]%mod;
        LL temp=(Max[b[1]]-(n+1))%mod;
        for(int i=2;i<=n;i++){
            LL x=max(Max[b[i]],temp);
            ans=(ans+x%mod)%mod;
            temp=max(temp,x-(n+i));
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

贪心 维护最大值
b数组从小到大排序 从最小的开始选取 可以确保选取区间最大
temp维护所有添加数字的最大值 Max记录原数组的后缀最大值
记录值时直接-i方便后续维护

本文标题:multi多校-2

文章作者:Hippopmonkey

发布时间:2017-08-01, 23:59:53

最后更新:2017-08-02, 10:34:06

原始链接:http://xuboming8.github.io/2017/08/01/multi多校-2/

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

文章目录
  1. 1. muti多校-2
    1. 1.1. HDU 6045
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6055
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6047
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|