[原创]2011 Heilongjiang collegiate programming contest 【(7+1)/10】 [补完]

2017-07-14 19:00:51 Tabris_ 阅读数：324

博客爬取于2020-06-14 22:39:42
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75127871

题目链接:
[CDOJ] https://vjudge.net/contest/170394#overview
[hrbust1395~1402(中文题面哦!) ] http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblemVolume

题目其实很简单,可能由于考试周后第一天训练,状态不对吧,题意都搞不清,

再加上C题后台数据应该出了问题卡了好久,在hrbustOJ上能AC…

A UESTC 924 Alphabet Cookies

—————————————————————————————————————————
日常傻逼签到题 不解释

B UESTC 925 Sequential game

—————————————————————————————————————————
同样傻逼签到题 不解释

C UESTC 926 Programming Contest Ranking

—————————————————————————————————————————
模拟题,模拟ICPC赛制的rank,
与现实规则中,多了一条,一血没有罚时的规则

模拟即可

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# include <bits/stdc++.h>
using namespace std;
const int N = 222;
/*********************************************/
int n,m;
struct node {
    char name[22];
    int ac,total,weight;
    bool st[22];
    int att[22];
}p[N];

int blood[N];
int aa[N];

char s[100];
void input(){
    vector<int>v[N];

    for(int i=1;i<=m;i++) blood[i]=333,aa[i]=0;

    for(int i=1;i<=n;i++){
        p[i].total=p[i].weight=p[i].ac=0;
        scanf("%s",p[i].name);
        for(int j=1;j<=m;j++){
            scanf("%s",s);
            int l = strlen(s);
            if(s[l-1]=='-') {
                p[i].st[j]=0;
                continue;
            }

            int &x = p[i].att[j],flag=0,y=0;
            x=0;
            for(int k=0;s[k];k++){
                if(s[k]=='\\'){
                    flag=1;
                    continue;
                }
                if(!flag) x=x*10+s[k]-'0';
                else      y=y*10+s[k]-'0';
            }
            p[i].ac++;
            p[i].total+=y+x*20-20;
            p[i].st[j]=1;
            aa[j]++;
            if(blood[j]>y){
                blood[j]=y;
                v[j].clear();
                v[j].push_back(i);
            }
            else if(blood[j]==y){
                v[j].push_back(i);
            }
        }
    }

    for(int i=1;i<=m;i++)  if(aa[i]) aa[i]=n/aa[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            p[i].weight+=p[i].st[j]*aa[j];

    for(int j=1;j<=m;j++){
        if(blood[j]==333) continue;
        for(int i=0;i<v[j].size();i++)
            p[v[j][i]].total-=p[v[j][i]].att[j]*20-20;
    }
}

bool cmp(node a,node b){
    if(a.ac==b.ac){
        if(a.total==b.total){
            if(a.weight==b.weight)
                return strcmp(a.name,b.name)<0;
            return a.weight>b.weight;
        }
        return a.total<b.total;
    }
    return a.ac>b.ac;
}

int rk[N];
int main(){
    while(~scanf("%d%d",&n,&m)){
        input();
        sort(p+1,p+n+1,cmp);
        rk[1]=1;

        for(int i=1;i<=n;i++){
            if(i>1){
                if(p[i].ac     == p[i-1].ac&&
                   p[i].total  == p[i-1].total&&
                   p[i].weight == p[i-1].weight){
                    rk[i]=rk[i-1];
                }
                else rk[i]=i;
            }
            printf("%*d %*s %*d %*d %*d\n",3,rk[i],20,p[i].name,2,p[i].ac,6,p[i].total,4,p[i].weight);
        }
    }
    return 0;
}

D UESTC 927 Dart game

—————————————————————————————————————————
游戏规则很简单，目标是由 1-20 这些区间组成，中心的红点是50分，中心的绿色环是25分，另外两个环一个是分数乘 3 的区域，一个是分数乘 2 的区域（如右图）。 每个运动员现在有 N 分数，每个运动员的目标是把自己的分数变为0，而方式是通过每投掷一次飞镖，总分减去投掷所得的分数，且每个运动员要保证最后一次投掷的飞镖要落在分数乘2的区域，也就是 Double Ring区域。谁先把自己的分数降低为0 谁先赢。
而你的任务是：
给你一个运动员的起始分数，分数为 N，你需要计算出有多少种投掷飞镖的方式能够把分数降到0. 不同的方式意味着： 两两方式之间至少有一种方式的某个步骤和另一个不同，如果两个方式可以通过改变其中某种方式相应步骤的顺序来使其和另一个方式相同的话，这两种方式算作一种。
例如：N=4， 有四种方式达到 0： 一次（1X2）分， 两次1分加上一次（1X2）分，一次2分加上一次（1X2） 分，两次（1X2） 分。

由于结果可能很大，你需要对结果模上 2011。

首先考虑dp[i],表示从0~i的方案数

那么dp过程中相当于进行完全背包,物品的重量分别是{x∣x∈[1,20],x2∈[1,20],x3∈[1,20],x∈{25,50}}\{x|x\in[1,20], \frac{x}{2}\in[1,20], \frac{x}{3}\in[1,20] , {x}\in \{25,50\} \}

转移过程就是

1
2
3
4
dp1[0]=1;
    for(int i=0;i<v.size();i++)
        for(int j=1;j<N;j++)
            if(j-v[i]>=0)  dp1[j]=(dp1[j]+dp1[j-v[i]])%MOD;

然后要明确,拿分的顺序不影响方案数,所以只要过程中有至少一个2倍的即可

所以考虑两次dp
一次求dp1[],表示所有情况的结果
另一次求dp2[],表示去除2倍的结果

最终结果就是dp1[]-dp2[];

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
# include <bits/stdc++.h>

typedef long long int LL;

using namespace std;

const int N   = 1111;
const int MOD = 2011;

/*********************************************/

int dp1[N],dp2[N],ans[N];

void init(){
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));

    vector<int>v;
    v.push_back(25),v.push_back(50);
    for(int i=1;i<=20;i++){
        v.push_back(i);
        v.push_back(i*2);
        v.push_back(i*3);
    }

    sort(v.begin(),v.end());

    dp1[0]=1;
    for(int i=0;i<v.size();i++)
        for(int j=1;j<N;j++)
            if(j-v[i]>=0)  dp1[j]=(dp1[j]+dp1[j-v[i]])%MOD;

    v.clear();
    v.push_back(25);
    for(int i=1;i<=20;i++){
        v.push_back(i);
        v.push_back(i*3);
    }

    sort(v.begin(),v.end());

    dp2[0]=1;
    for(int i=0;i<v.size();i++)
        for(int j=1;j<N;j++)
            if(j-v[i]>=0)  dp2[j]=(dp2[j]+dp2[j-v[i]])%MOD;

    for(int i=1;i<N;i++) ans[i]=(dp1[i]-dp2[i]+MOD)%MOD;
}

int main(){
    init();int n;
    while(~scanf("%d",&n)&&n) printf("%d\n",ans[n]);
    return 0;
}

E UESTC 928 Similar Word

—————————————————————————————————————————
给你两个字符串,问你循环之后能不能相等,最开始相等不算

其实就是最小表示法

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
# include<stdio.h>
# include<string.h>
# include<iostream>
using namespace std;
char a[150000];
char bb[150000];
int n;
int minRepresentation(char b[])
{
    int l=n;
    int i = 0, j = 1, k = 0, t;
    while(i < l && j < l && k < l) {
        t = b[(i + k) >= l ? i + k - l : i + k] - b[(j + k) >= l ? j + k - l : j + k];
        if(!t) k++;
        else{
            if(t > 0) i = i + k + 1;
            else j = j + k + 1;
            if(i == j) ++ j;
            k = 0;
        }
    }
    return (i < j ? i : j);
}
int main()
{
    while(~scanf("%s%s",a,bb))
    {
        if(strcmp(a,bb)==0)
        {
            printf("no\n");
            continue;
        }
        if(strlen(a)!=strlen(bb))
        {
            printf("no\n");
            continue;
        }
        int flag=0;
        n=strlen(a);
        int posa=minRepresentation(a);
        int posb=minRepresentation(bb);
        for(int i=0;i<n;i++)
        {
            if(a[posa]!=bb[posb])flag=1;
            posa++;
            posb++;
            posa%=n;
            posb%=n;
        }
        if(flag==0)
        printf("yes\n");
        else printf("no\n");
    }
}

F UESTC 929 Post office

—————————————————————————————————————————
有n个村庄,有q次询问,每次询问在第i个到第j个村庄找一个位置作为邮局,使得第i个到第j个村庄到邮局的距离和最小,输出这个值

好吧,我并没有写代码,所以思路和代码可能有点细微的差别

村庄的位置时升序的

考虑每次查询的i,j

很容易发现,在第i个和第j个间任选一个位置做邮局对于村庄i,j是一样的
那么对于第i+1个和第j-1个同理,
…

所以能够确定的是邮局位置找中间的那个村庄就行了,(偶数个的话中间两个都一样

然后在计算结果的时候,我们可以先处理一个前缀和,然后能做到O(1)

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
# include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int n;
ll sum[150000];
ll a[150000];
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        for(int i=0;i<n;i++)
        {
            if(i==0)sum[i]=a[i];
            else sum[i]=sum[i-1]+a[i];
        }
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            if((y-x+1)%2==1)
            {
                int mid=(x+y)/2;
                ll num=(y-x+1)/2;
                ll output=a[mid]*num-(sum[mid-1]-sum[x-1]);
                output+=(sum[y]-sum[mid])-a[mid]*num;
                printf("%lld\n",output);
            }
            else
            {
                int mid=(x+y)/2;
                ll num=(y-x+1)/2-1;
                ll output=a[mid]*num-(sum[mid-1]-sum[x-1]);
                output+=(sum[y]-sum[mid])-a[mid]*(num+1);
                mid=(x+y)/2+1;
                num=(y-x+1)/2;


                ll output2=a[mid]*num-(sum[mid-1]-sum[x-1]);
                output2+=(sum[y]-sum[mid])-a[mid]*(num-1);
                printf("%lld\n",min(output,output2));
            }
        }
    }
}

G UESTC 930 Lucky Boy

—————————————————————————————————————————
平面上有n个点,
两个人可以拿在同一条直线上的点,
能拿3个及以上的点或者最后一个点的人获胜.

首先考虑如果有3个点以上在一条直线的情况先手必胜,
所以特判就好,

做法是枚举两个点间的斜率,对于点x,y,z 如果xy的斜率和xz的斜率相等可以了

剩下的就是普通的情况了,当然两点一定贡献,

所以剩下的就等价于一个n个石子最多取2个石子的巴士博弈

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>
typedef long long int LL;
using namespace std;

const int N = 10000 +7;

map<int,map<int,int> >mmp;

int x[N],y[N];

int main() {
    int n;
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)           scanf("%d%d",&x[i],&y[i]);

        int flag = 0,xx,yy,t; // equal;
        for(int i=1; i<=n; i++) {
            mmp.clear();
            for(int j=1; j<=n; j++) {
                if(i==j) continue;
                if(x[i]==x[j]&&y[i]==y[j]) flag=1;
                xx=x[i]-x[j];
                yy=y[i]-y[j];
                if(xx<0) xx*=-1,yy*=-1;
                t=__gcd(xx,yy);
                xx/=t,yy/=t;
                if(mmp[xx][yy]) flag=1;
                mmp[xx][yy]=1;
            }
        }
        if(flag ) {
            printf("a");
        } else {
            if(n%(3)==0) printf("b");
            else         printf("a");
        }
        puts(" is the lucky boy.");
    }
    return 0;
}

H UESTC 931 Car race game

—————————————————————————————————————————
XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛，这种的比赛规模很大，涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛，XianGe幻想着有许多人参赛，那是人山人海啊，不过XianGe只允许最多100000人参加比赛。
这么大规模的比赛应该有技术统计，在XianGe的比赛中所有车辆的起始点可能不同，速度当然也会有差异。XianGe想知道比赛中会出现多少次超车（如果两辆车起点相同速度不同也算发生一次超车）。

首先对x排序,
然后x小的如果速度比x大的大就能超车了

排完序之后用BIT维护一下就好了

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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1000000 +7;

struct node{
    int x,v;
}a[N];

bool cmp(node a,node b){
    if(a.x==b.x) return a.v<b.v;
    return a.x>b.x;
}

int sum[N];
# define lowbit(x) (x&-x)
void update(int i,int v){
    for(;i<N;i+=lowbit(i)) sum[i]+=v;
}
int getSum(int i){
    int ans = 0; for(;i;i-=lowbit(i)) ans+=sum[i];
    return ans;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].v);

        sort(a+1,a+n+1,cmp);
        LL mx = 0;
        for(int i=1;i<=n;i++){
            mx += getSum(a[i].v-1);
            update(a[i].v,1);
        }

        printf("%lld\n",mx);
    }
    return 0;
}

I UESTC 932 Jiulianhuan

—————————————————————————————————————————
相信大家都玩过九连环的游戏 ，九连环的规则是 ：
1第一个环可以在任何时候挂到柄上或者从柄上摘下
2在任何时候，你只能操作一个环
3如果前k-2个环都没有在柄上，并且第k-1个环在柄上，这时如果第k个环在柄上的话，可以把它摘下来，如果它不在柄上，可以把它挂上去

给定一个数n，n不大于10的8次方，你的任务是输出从柄上摘下n个环需要的最小操作次数，测试数据不超过100组。

终于理解了九连环怎么玩之后,手动模拟的了一下,
发现最后变成
0000011
1111100(长度为n)
的时候需要的次数均是2i−12^{i-1}的
而接下来需要的操作相当于长度为n-2时的操作,

所以有了递推式

f[i]=f[i−2]+2i−1f[1]=1f[2]=2f[i]=f[i-2]+2^{i-1}\\f[1]=1\\f[2]=2

然后构造矩阵就行了
[f[i+2]f[i+1]f[i]2i+2]×[0100101000001002]=[f[i+3]f[i+2]f[i+1]2i+3]\left[\begin{array}{cc} f[i+2]&&f[i+1]&&f[i]&&2^{i+2} \end{array}\right]\times \left[\begin{array}{cc} 0&&1&&0&&0 \\1&&0&&1&&0 \\0&&0&&0&&0 \\1&&0&&0 &&2 \end{array}\right] = \left[\begin{array}{cc}f[i+3]&&f[i+2]&&f[i+1]&&2^{i+3}\end{array}\right]

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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
const int N = 222;
const int MOD = 10007;
/*********************************************/
const int M = 4;

struct Matrix{
    LL m[M][M];
    void clear0(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=0;
    }
    void clearE(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=(i==j);
    }
};


Matrix operator * (Matrix &a,Matrix &b){
    Matrix c;c.clear0();

    for(int k=0;k<M;k++)
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
    return c;
}

Matrix operator ^ (Matrix &a,LL b){
    Matrix c;c.clearE();
    while(b){
        if(b&1)  c=c*a;
        b>>=1,a=a*a;
    }
    return c;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        Matrix a,b;
        a.clear0(),b.clear0();

        a.m[0][0]=5;
        a.m[0][1]=2;
        a.m[0][2]=1;
        a.m[0][3]=8;

        b.m[0][1]=1;
        b.m[1][0]=b.m[1][2]=1;
        b.m[3][0]=1,b.m[3][3]=2;

        b=b^(n-1);
        a=a*b;

        printf("%lld\n",a.m[0][2]);
    }
    return 0;
}

J UESTC 933 The minimum square sum

—————————————————————————————————————————

给定你一个质数p (p < 10^8)，请你确定最小的x^2 + y^2 (其中x, y都是正数)，使得x^2 + y^2 = 0 (mod p)

首先根据p为素数,能想到i*i%p的循环节是p.

所以说如果选择数的话 一定在这个循环节里面,

然后能想到$ii+jj=p那么结果就是p如果找不到则只能是那么结果就是p 如果找不到 则只能是pp+pp$

然后想到枚举平方数找存不存在$ii+jj=p $ ,复杂度为O(sqrt(n))O(sqrt(n)) 1e8差不多能过
然后写出了下列代码,就TLE了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <bits/stdc++.h>

typedef long long int LL;

using namespace std;

int main(){
    LL n;
    while(~scanf("%lld",&n)){
        LL mi = n*n+n*n;
        for(LL i=1;i*i<n;i++){
            LL t = n-i*i;
            LL tt = sqrt(t+1.0);
            if(t == tt*tt){
                mi = n;
                break;
            }
        }
        printf("%lld\n",mi);
    }
    return 0;
}

最后贯彻**“遇事不决先打表”**这个思想，发现，如果素数形如4*k+3这种，结果就是p∗p+p∗pp*p+p*p 否则就是pp

1
2
3
4
5
6
7
8
9
10
11
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
int main() {
    LL n;
    while(~scanf("%lld",&n)) {
        if(n%4==3) printf("%lld\n",n*n*2);
        else       printf("%d\n",n);
    }
    return 0;
}