2017 ccpc wfin-女生赛

自用笔记算法

2017 ccpc wfin-女生赛

HDU 6023

题意

模拟acm ranklist

参考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
#include<bits/stdc++.h>
using namespace std;
int Hash[1020];
int lazy[1020];
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        getchar();
        memset(Hash,0,sizeof(Hash));
        memset(lazy,0,sizeof(lazy));
        int cnt=0,pen=0;
        for(int i=1;i<=m;i++){
            string s;
            getline(cin,s);
            int x=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0');
            if(Hash[x]==0){
                if(s[11]=='A'&&s[12]=='C'){
                    Hash[x]=1;
                    cnt++;
                    pen+=lazy[x]+(s[6]-'0')*60+(s[8]-'0')*10+s[9]-'0';
                }
                else lazy[x]+=20;
            }
        }
        printf("%d %d\n",cnt,pen);
    }
    return 0;
}

思路&注意事项

某一题A过之后再提交错误不会计入罚时

HDU 6024

题意

一条直线上有n个点 给出n个点的坐标和权值
每个点的价值分成两部分 如果选择该点 那么该点的cost为它的权值
否则cost为在它左边离他最近的点和它的距离差

参考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 LL long long
#define maxn 3050
using namespace std;
struct node{
    LL cost,dir;
}no[maxn];
LL dist[maxn],dp[maxn];
int cmp(node a,node b){
    return a.dir<b.dir;
}
int main(){
//    freopen("input.txt","r",stdin);
      int n;
      while(scanf("%d",&n)!=EOF){
          for(int i=0;i<n;i++) scanf("%lld%lld",&no[i].dir,&no[i].cost);
          sort(no,no+n,cmp);
          memset(dp,0,sizeof(dp));
          dist[0]=0;
          no[n].dir=no[0].dir;
          no[n].cost=0;
          for(int i=1;i<=n;i++) dist[i]=dist[i-1]+no[i].dir-no[0].dir;
          dp[0]=no[0].cost;
          for(int i=1;i<=n;i++){
              dp[i]=dp[i-1]+no[i].cost;
            for(int j=0;j<=i-1;j++){
                LL ans=dist[i-1]-dist[j]-(i-1-j)*(no[j].dir-no[0].dir);
                dp[i]=min(dp[i],dp[j]+ans+no[i].cost);
            }    
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}

思路&注意事项

dp
先将每个点升序排列
预处理前n项和可以快速求出x-y的距离差
dp方程如代码所示

HDU 6025

题意

一个数组删除某个数后求出最大gcd

参考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
#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
int a[maxn];
int l[maxn],r[maxn];
int ans;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        ans=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        l[1]=a[1];
        for(int i=2;i<=n;i++) l[i]=gcd(l[i-1],a[i]);
        r[n]=a[n];
        for(int i=n-1;i>=1;i--) r[i]=gcd(r[i+1],a[i]);
        ans=max(r[2],l[n-1]);
        for(int i=2;i<n;i++) ans=max(ans,gcd(l[i-1],r[i+1]));
        printf("%d\n",ans);
    }
    return 0;
}

思路&注意事项

先预处理出每个点左边的最大gcd和最小gcd
遍历删除的数字 每次求出该数字左边的最大gcd和右边的最大gcd求max即可

HDU 6026

题意

一张图删除一些边后变成一棵树 要求：
有n-1条边
根到每个点的距离都等于原图中根到每个点的最短距离
求出删除后有多少种不同的形态

参考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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define LL long long
#define maxn 55
const LL mod= 1e9+7;
using namespace std;
int vis[maxn],dist[maxn];
int in[maxn];
char s[maxn][maxn];
int n;
void spfa(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=0;i<n;i++){
            int w=s[now][i]-'0';
            int to=i;
            if(w==0) continue;
            if(dist[now]+w<dist[to]){
                dist[to]=dist[now]+w;
                if(!vis[to]){
                    vis[to]==1;
                    q.push(to);
                }
            }
        }
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++) scanf("%s",s[i]);
        memset(vis,0,sizeof(vis));
        memset(dist,inf,sizeof(dist));
        memset(in,0,sizeof(in));
        vis[0]=1,dist[0]=0;
        spfa();    
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) continue;
                int val = s[i][j]-'0';
                if(val==0) continue;
                if(dist[i]+val == dist[j]) in[j]++;
            }
        }       
        LL ans=1;
        for(int i=0;i<n;i++){
            if(in[i]==0) continue;
            ans=(ans*(LL)in[i])%mod;
//            ans = ans* (LL)in[i]%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

思路&注意事项

类似于树上求最短路
先预处理出根到所有结点的最短路放到dist里
接着计算每个点的度
度的计算方法为：若该点有n条可以到达它的路线 那么它的入度就加n
最后把所有点的入度相乘即可得到最后树有多少种状态 入度为0跳过

HDU 6027

题意

计算表达式

参考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
#include<bits/stdc++.h>
#define LL long long
const LL mod=1e9+7;
using namespace std;
int n,k;
LL f(int m){
    LL x=1;
    for(int i=1;i<=k;i++){
        x*=m;
        x%=mod;
    }
    return x%mod;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        LL sum=0;
        for(int i=1;i<=n;i++){
            sum+=f(i)%mod;
        } 
        printf("%lld\n",sum%mod);
    }
    return 0;
}

思路&注意事项

水题
注意取模 开LL即可

HDU 6029

题意

每次可以进行两种操作：
把该点和前面所有的点相连
该点与前面所有的点不连接

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int num=1;
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++){
            int x;
            scanf("%d",&x);
            if(x==2||num==0) num++;
            else num--;
        }
        if(num==0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

思路&注意事项

模拟题
num表示不匹配点的个数
若执行第二步操作或者前面n-1个点已经构成完全联通图 则num++
否则不匹配的点个数减1

HDU 6030

题意

一串项链有红色珠子和蓝色珠子
要求有多少种类型的搭配满足：
任意连续质数串中的红色数量不小于蓝色

参考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
#include<bits/stdc++.h>
#define LL long long
#define maxn 3050
using namespace std;
struct Matrix
{
    LL matrix[3][3];
};
int n=3;    
LL MOD=1e9+7;
Matrix E;
void initE()    
{
    memset(E.matrix,0,sizeof(E.matrix)); 
    E.matrix[0][0]=E.matrix[0][2]=E.matrix[1][0]=E.matrix[2][1]=1;
}
Matrix operator*(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            c.matrix[i][j] = 0;
            for (k=0;k<n;k++)
                    c.matrix[i][j]+=(a.matrix[i][k]*b.matrix[k][j]);
            c.matrix[i][j]%=MOD;
        }
    }
    return c;
}
Matrix operator^(Matrix a,LL x) 
{ 
     Matrix p = E,q = a; 
     while (x>=1) 
     { 
         if(x%2==1) 
             p = p*q; 
         x/=2; 
         q = q*q; 
     } 
     return p; 
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        initE();
        LL k;
        scanf("%lld",&k);
        if(k==2){
            printf("3\n");
            continue;
        }
        E=E^(k-3);
        LL ans=(E.matrix[0][0]*3+E.matrix[0][1]*2+E.matrix[0][2])%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

思路&注意事项

打表发现规律f(n)=f(n-1)+f(n-3)
使用矩阵快速幂求得即可
注意初始化的矩阵为三维

本文标题:2017 ccpc wfin-女生赛

文章作者:Hippopmonkey

发布时间:2017-05-08, 13:42:21

最后更新:2017-10-27, 10:47:16

原始链接:http://xuboming8.github.io/2017/05/08/2017-ccpc-wfin-女生赛/

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

文章目录
  1. 1. 2017 ccpc wfin-女生赛
    1. 1.1. HDU 6023
      1. 1.1.1. 题意
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路&注意事项
    2. 1.2. HDU 6024
      1. 1.2.1. 题意
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路&注意事项
    3. 1.3. HDU 6025
      1. 1.3.1. 题意
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路&注意事项
    4. 1.4. HDU 6026
      1. 1.4.1. 题意
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路&注意事项
    5. 1.5. HDU 6027
      1. 1.5.1. 题意
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路&注意事项
    6. 1.6. HDU 6029
      1. 1.6.1. 题意
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路&注意事项
    7. 1.7. HDU 6030
      1. 1.7.1. 题意
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路&注意事项
|