2017ccpc网赛

自用笔记算法

ccpc网赛

HDU 6150

题目要求

“最小点覆盖集”是个NP完全问题
有一个近似算法是说————
每次选取度数最大的点（如果有多个这样的点，则选择最后一个）
让你构造一个图，使得其近似算法求出来点数是你给定的覆盖点数的至少3倍。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main(){
//    freopen("input.txt","r",stdin);
    int n=141,m=762;
    printf("%d %d\n",n,m);
    int num=31;
    for(int i=1;i<=30;i++){
        int limit=30/i;
        int f=1;
        for(int j=1;j<=limit;j++){
            for(int k=1;k<=i;k++) printf("%d %d\n",f++,num);
            num++;
        }
    }
    printf("30\n");
    for(int i=1;i<=30;i++) printf("%d\n",i);
    return 0;
}

思路

左边n个点（编号较小），
对于每个i∈[1, n]，右边新建n / i 个点，每个点选择左边i个点连一条边（总边数为n^2），使得每个i最多只使得左边每个点的度数+1
这样左边每个点的度数都是<=n的，而右边点每个点的度数会分别是{ 1 } { 2 } { 3 } { 4 } … { n }
这样每次会选右边的点去除，去除之后左边的度数依旧<=右边的度数
于是贪心做法会选择右边，大小为nlogn的点集，
而实际只需要选择左边，大小为n的点集即可。
对于题目要求n设为30即可 计算出n=141 m=762

HDU 6152

题目要求

判断给定的图中有没有大小大于等于3的独立集或大小大于等于3的团

参考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
#include<bits/stdc++.h>
#define maxn 3050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
bool g[maxn][maxn];
int n;
bool check(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(g[i][j]==g[i][k] && g[j][i]==g[j][k] && g[k][i]==g[k][j]) return false;
            }
        }
    }
    return true;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                int x; scanf("%d",&x);
                if(x==1) g[i][j]=g[j][i]=true;
                else g[i][j]=g[j][i]=false;
            }
        }
        if(check())    printf("Great Team!\n");
        else printf("Bad Team!\n");    
    }
    return 0;
}

思路

暴力
注意bool比int占内存少 本题int超内存 而bool比int内存少使用3倍多
也有专门的定理：Ramsey theorem 6个人中至少存在3人相互认识或者相互不认识 n大于等于6直接输出否则暴力

HDU 6153

题目要求

给定两个串，求其中一个串s的每个后缀在另一个串t中出现的次数 相加取mod

参考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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define maxn 1000050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const LL mod=1e9+7;
char s1[maxn],s2[maxn];
int nextt[maxn],extend[maxn];
int len1,len2;
void getnext(char x[],int m){
    nextt[0]=m;
    int j=0;
    while(j+1<m && x[j]==x[j+1]) j++;
    nextt[1]=j;
    int k=1;
    for(int i=2;i<m;i++){
        int p=nextt[k]+k-1;
        int L=nextt[i-k];
        if(i+L<p+1) nextt[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<m && x[i+j]==x[j]) j++;
            nextt[i]=j;
            k=i;
        }
    }
}
void ekmp(char x[],int m,char y[],int n){
    int j=0;
    while(j<n && j<m && x[j]==y[j]) j++;
    extend[0]=j;
    int k=0;
    for(int i=1;i<=n;i++){
        int p=extend[k]+k-1;
        int L=nextt[i-k];
        if(i+L<p+1) extend[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<n && j<m && y[i+j]==x[j]) j++;
            extend[i]=j;
            k=i;
        }
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        scanf("%s%s",s1,s2);
        int len1=strlen(s1);
        int len2=strlen(s2);
        reverse(s1,s1+len1);
        reverse(s2,s2+len2);
        mm(nextt,0),mm(extend,0);
        getnext(s1,len1);
        ekmp(s2,len2,s1,len1);
        LL ans=0;
        for(int i=0;i<len1;i++){
            if(extend[i]){
                LL temp=extend[i]%mod;
                temp=(((temp*(temp+1)/2)%mod)+mod)%mod;  
                ans=(ans+temp)%mod;  
            }
        }    
        printf("%lld\n",ans);
    }
    return 0;
}

思路

扩展kmp
先把2个字符串反转化成前缀问题
对s1求next 对s2进行匹配 ekmp求出来的extend[i]表示s1[i..len1-1]与s2的最长公共前缀
该位置对结果的贡献是1+2+…+extend[i] ==(1+extend[i])*extend[i]/2
每个有贡献的extend累加取mod就是所求

HDU 6156

题目要求

已知函数f(x, k)，如果10进制数x在k进制下是个回文数，那么f(x, k)值为k，否则为1
现给出l, r, x, y, 求出∑∑f(i, j) (l<=i<=r) (x<=j<=y)

参考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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
LL qpow(LL x,LL y){
    LL re=1,base=x;
    while(y){
        if(y&1) re*=base;
        base*=base;
        y>>=1;
    }
    return re;
}
int base[1005];
LL solve(LL num,LL k){
    if(num==0) return 0;
    int top=0;
    while(num){
        base[top++]=num%k;
        num/=k;
    }
    int flag=-1;
    if(top%2==1){
        for(int i=0;i<=top/2;i++){
            if(i==top/2){
                flag=1;
                break;
            }
            else if(base[top/2-(i+1)]>base[top/2+(i+1)]){
                flag=1;
                break;
            }
            else if(base[top/2-(i+1)]<base[top/2+(i+1)]){
                flag=0;
                break;
            }
        }
    }
    else{
        for(int i=0;i<=top/2;i++){
            if(i==top/2){
                flag=1;
                break;
            }
            else if(base[top/2-(i+1)]>base[top/2+i]){
                flag=1;
                break;
            }
            else if(base[top/2-(i+1)]<base[top/2+i]){
                flag=0;
                break;
            }
        }
    }
    LL res=0;
    for(int i=0;i<top/2;i++) res=res*k+base[top-(i+1)];
    if(top%2==1) res=res*k+base[top-top/2-1];
    return res-(1-flag)+qpow(k,top/2)-1;
}
int f=1;
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        cout<<"Case #"<<f++<<": ";
        int L,R,l,r;
        scanf("%d%d%d%d",&L,&R,&l,&r);
        LL ans=0;
        for(int i=l;i<=r;i++){
            LL temp=solve(R,i)-solve(L-1,i);
            ans+=temp*i+(R-L+1-temp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

参考AC代码(数位dp)

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
#include<bits/stdc++.h>
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int base[1005],tmp[1005];
LL dp[105][105][40];
LL dfs(int pos,int start,int limit,int k){
    if(pos<0) return 1;
    if(!limit && dp[pos][start][k]!=-1) return dp[pos][start][k];
    int end=limit?base[pos]:k-1;
    LL res=0;
    for(int i=0;i<=end;i++){
        tmp[pos]=i;
        if(pos==start && i==0) res+=dfs(pos-1,start-1,limit&&i==end,k);
        else if(pos<(start+1)/2){
            if(i==tmp[start-pos]) res+=dfs(pos-1,start,limit&&i==end,k);
        }
        else res+=dfs(pos-1,start,limit&&i==end,k);
    }
    if(!limit) dp[pos][start][k]=res;
    return res;
}
LL solve(LL num,int k){
    int top=0;
    while(num){
        base[top++]=num%k;
        num/=k;
    }    
    return dfs(top-1,top-1,1,k);
}
int f=1;
int main(){
//    freopen("input.txt","r",stdin);
    mm(dp,-1);
    int t; scanf("%d",&t);
    while(t--){
        cout<<"Case #"<<f++<<": ";
        int L,R,l,r;
        scanf("%d%d%d%d",&L,&R,&l,&r);
        LL ans=0;
        for(int i=l;i<=r;i++){
            LL temp=solve(R,i)-solve(L-1,i);
            ans+=temp*i+(R-L+1-temp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

思路

通过计算或者数位dp 算出1-n内的回文串个数 用R-(L-1)就是L到R内的回文串个数 枚举进制计算回文数
答案就是temp×进制+(L到R区间内不是回文的个数) 因为题中不是回文也要加1
计算方法：flag代表能不能构成最大的回文数 若高位比地位大 则不能 例如5421不能构成5441 超出上限 若不能结果-1
第一次计算res是按照奇偶的性质 若修改进制后原本的回文串是奇数位 那么计算所有的奇数回文串 偶数同理
第二次res加上的是位数比他小的回文数(原本是奇那么计算偶 反之同理) 稍加计算就可以得到qpow(k,top/2)-1
数位dp代表的是dp[起点][位置][进制] 数位dp模版 注意for里的计算

本文标题:2017ccpc网赛

文章作者:Hippopmonkey

发布时间:2017-08-20, 11:47:09

最后更新:2017-08-21, 16:00:03

原始链接:http://xuboming8.github.io/2017/08/20/2017ccpc网赛/

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

文章目录
  1. 1. ccpc网赛
    1. 1.1. HDU 6150
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6152
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6153
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6156
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码(计算)
      3. 1.4.3. 参考AC代码(数位dp)
      4. 1.4.4. 思路
|