浙工业之江学院比赛

自用笔记算法

浙工业之江学院比赛

A

Description

qwb同时也是是之江学院的志愿者，暑期要前往周边地区支教，为了提高小学生的数学水平。她把小学生排成一排，从左至右从1开始依次往上报数。
玩完一轮后，他发现这个游戏太简单了。于是他选了3个不同的数x,y,z；从1依次往上开始报数，遇到x的倍数、y的倍数或z的倍数就跳过。如果x=2,y=3,z=5；
第一名小学生报1，第2名得跳过2、3、4、5、6，报7；第3名得跳过8、9、10，报11。
那么问题来了，请你来计算，第N名学生报的数字是多少？

Input
多组测试数据，处理到文件结束。（测试数据数量<=8000）
每个测试例一行，每行有四个整数x,y,z,N。（ 2≤x,y,z≤107,1≤N≤1017）。

Output
对于每个测试例，输出第N名学生所报的数字，每个报数占一行。

Sample Input
2 3 5 2
6 2 4 10000

Sample Output
7
19999

参考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
using namespace std;
LL x,y,z,n;
LL gcd(LL a,LL b){
    if(b==0) return a;
    return gcd(b,a%b);
}
LL lcm(LL a,LL b){
    return a/gcd(a,b)*b;
}
bool check(LL w){
    LL cnt=w/x+w/y+w/z-w/lcm(x,y)-w/lcm(x,z)-w/lcm(y,z)+w/lcm(lcm(x,y),z);
    if((w-cnt)>=n) return true;
    return false;
}
int main(){
//  freopen("input.txt","r",stdin);
//  ios::sync_with_stdio(false);
//  cin.tie(0),cout.tie(0);
    while(scanf("%lld%lld%lld%lld",&x,&y,&z,&n)!=EOF){
        LL l=1,r=1e18,mid,ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

思路

二分+容斥
容斥的结果为xyz任意的倍数 w-cnt结果为不是xyz的倍数
同样求第i个丑数也可以用此方法

B

Description
做完了辣么多的数学题，qwb好好睡了一觉。但是他做了一个梦：
有一个nm的矩阵，qwb在这个矩阵的左上角(1,1)，终点在右下角(n,m)。
每个格子中有小钱钱，也可能没有，还有可能是要交过路费的，并且行走方向必须是靠近终点的方向。
往下走一次只能走一格，往右走一次可以走一格也可以走到当前列数的倍数格。
比如当前格子是（x,y），那么可以移动到(x+1,y),(x,y+1)或者(x,yk),其中k>1。
qwb希望找到一种走法，使得到达右下角时他能够有最多的小钱钱。
你能帮助他吗？

Input
第一行是测试例数量 T （T<=100），接下来是T组测试数据。
每组测试数据的第一行是两个整数n,m，分别表示行数和列数(1<=n<=20,1<=m<=10000)；
接下去给你一个n*m的矩阵，每个格子里有一个数字 k （-100<=k<=100）代表小钱钱的数量。 ∑nm<=3,000,000

Output
每组数据一行，输出L先生能够获得小钱钱的最大值(可能为负数)。

Sample Input
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10

Sample Output
52

参考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>
#define maxn 100050 
#define inf 0x3f3f3f3f
using namespace std;
int dp[25][maxn];
int a[25][maxn];
int main(){
//  freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>a[i][j];
        }
        memset(dp,-inf,sizeof(dp));
        dp[1][1]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]+=a[i][j];
                if(i<n) dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
                if(j<m) dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
                for(int k=j*2;k<=m;k+=j) dp[i][k]=max(dp[i][k],dp[i][j]);
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

思路

dp
只能往下或往右 典型的dp
注意筛选质数的复杂度即可

C

Description
zjc的ACgirls队的队员最近比较忙，为了能够取得更好的比赛成绩，他们制定了一个m天a掉n题的计划，a掉一题可以是这m天的任何时候。
为了表示对acmer事业的热爱，队长wc要求每天必须至少要ac掉k题，这m天每天ac掉的题数可以用一个m元组表示。
设不同的m元组一共有c个，请问c的末尾有多少个0？（如果c是0，输出0）

Input
多组测试数据，处理到文件结束。（测试例数量<=160000）
输入的每一行是一个测试例，分别是m、n和k（0<=m,n,k<=1e9），含义如前所述。

Output
每组测试例中m元组的数量的末尾0的个数，占一行。

Sample Input
3 11 0
3 11 1
999 99999 4

Sample Output
0
0
5

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL m,n,k;
int main(){
//  freopen("input.txt","r",stdin);
    while(scanf("%lld%lld%lld",&m,&n,&k)!=EOF){
        LL x=m-1,y=n-k*m+m-1;
        if(x>y || y<=0) printf("0\n");
        else{
            LL cnt_2=0,cnt_5=0;
            for(LL i=2;i<=y;i*=2) cnt_2+=y/i-x/i-(y-x)/i;
            for(LL i=5;i<=y;i*=5) cnt_5+=y/i-x/i-(y-x)/i;
            printf("%lld\n",min(cnt_2,cnt_5));
        }
    }
    return 0;
}

思路

组合数学

求末尾的0实际上就是求2和5的个数的最小值
这里用到了求n！末尾0的个数的方法
组合数结果的0等于分子/分母

D

Description
qwb又遇到了一道题目：
有一个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插入这两个数的和，得到新序列。举例说明：
初始：1 2
操作1次：1 3 2
操作2次：1 4 3 5 2
……
请问在操作n次之后，得到的序列的所有数之和是多少

Input
多组测试数据，处理到文件结束（测试例数量<=50000）。
输入为一行三个整数x，y，n，相邻两个数之间用单个空格隔开。（0 <= x <= 1e10, 0 <= y <= 1e10, 1 < n <= 1e10）。

Output
对于每个测试例，输出一个整数，占一行，即最终序列中所有数之和。
如果和超过1e8，则输出低8位。（前导0不输出，直接理解成%1e8）

Sample Input
1 2 2

Sample Output
15

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define LL long long
const LL mod=1e8;
using namespace std;
LL x,y,n;
LL quick_pow(LL a,LL b){
    LL re=1,base=a%(2*mod);
    while(b){
        if(b&1) re=(re*base)%(2*mod);
        base=(base*base)%(2*mod);
        b>>=1;
    }
    return re;
}
int main(){
//  freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(scanf("%lld%lld%lld",&x,&y,&n)!=EOF){
        printf("%lld\n",(x+y)*((quick_pow(3,n)+1)/2)%mod);
    }
    return 0;
}

思路

推出公式
注意里公式/2 所以快速幂里的mod应扩大2倍(合理的任意倍数均可)

E

Description
qwb和李主席打算平分一堆宝藏，他们想确保分配公平，可惜他们都太懒了，你能帮助他们嘛？

Input
输入包含多组测试数据，处理到文件结束。
每组测试数据的第一行是一个正整数N(0 <= N <=36 )表示物品的总个数.。
接下来输入N个浮点数(最多精确到分)，表示每个物品的价值V（0<V<=1e9）。

Output
对于每组测试数据，输出能够使qwb和李主席各自所得到的物品的总价值之差的最小值（精确到分），每组测试数据输出占一行。

Sample Input
3 0.01 0.1 1
2 1 1

Sample Output
0.89
0.00

参考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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL inf = 1e18;
double a[40];
double fi[1<<19],se[1<<19];
int cnt1,cnt2;
double sum=0,ans;
int n;
void dfs(int st,int ed,double sum,int flag){
    if(flag==1){
        if(st==ed+1){
            fi[cnt1++]=sum;
            return ;
        }
        dfs(st+1,ed,sum,flag);
        dfs(st+1,ed,sum+a[st],flag);
    }   
    if(flag==2){
        if(st==ed+1){
            se[cnt2++]=sum;
            return ;
        }
        dfs(st+1,ed,sum,flag);
        dfs(st+1,ed,sum+a[st],flag);
    }
}
int main(){
//  freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        sum=0;
        cnt1=0,cnt2=0;
        ans=(double)inf;
        for(int i=1;i<=n;i++){
            scanf("%lf",&a[i]);
            sum+=a[i];
        }
        dfs(1,n/2,0,1);
        dfs(n/2+1,n,0,2);
        sort(fi,fi+cnt1);
        sort(se,se+cnt2);
        for(int i=0;i<cnt1;i++) ans=min(ans,fabs(sum-2*fi[i]));
        for(int i=0;i<cnt2;i++) ans=min(ans,fabs(sum-2*se[i]));
        for(int l=0,r=cnt2; l<cnt1 && r>0;l++){
            while(r>1 && fi[l]+se[r-1]>sum/2.0) r--;
            ans=min(ans,fabs(sum-2*(fi[l]+se[r])));
            ans=min(ans,fabs(sum-2*(fi[l]+se[r-1])));
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}

思路

把物品分为前半部分和后半部分 对两部分进行dfs 求出所有组合的大小
取物品只有三种情况：全在前半部分 全在后半部分 两部分均有
前2种方法暴力 最后一种情况贪心
l枚举前半部分的起点 计算出后半部分的r的右边界
贪心确保枚举下一个l时候 前半部分减少 后半部分只需从上次的r开始计算即可 无需从头遍历 因为只有从该位置向左才能确保后半部分
减少以满足差值最小
计算r时 r停留在最后一个满足l+r大于sum/2.0的位置 所以第一个满足和第一个不满足的位置都需要计算更新min

F

Description
qwb has a lot of coins. One day, he decides to play a game with his friend using these coins. He first puts some of his coins into M piles, each of which is composed of Ni (1<=i<=M) coins. Then, the two players play the coin game in turns. Every step, one can remove one or more coins from only one pile. The winner is the one who removes the last coin.
Then comes the question: How many different ways the first player can do that will ensure him win the game?

Input
Input contains multiple test cases till the end of file. Each test case starts with a number M (1 <= M<= 1000) meaning the number of piles. The next line contains M integers Ni (1 <= Ni <= 1e9, 1 <= i<= M) indicating the number of coins in pile i.

Output
For each case, put the method count in one line.
If the first player can win the game, the method count is the number of different ways that he can do to ensure him win the game, otherwise zero.

Sample Input
3
1 2 3
1
1

Sample Output
0
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
#include<bits/stdc++.h>
using namespace std;
int a[1050]; 
int main(){
//  freopen("input.txt","r",stdin);
    int m;
    while(scanf("%d",&m)!=EOF){
        int cnt=0;
        for(int i=1;i<=m;i++){
            scanf("%d",&a[i]);
            cnt^=a[i];
        }
        if(cnt==0) printf("0\n");
        else{
            int flag,ans=0;
            for(int i=1;i<=m;i++){
                flag=cnt^a[i];
                if(flag<a[i]) ans++;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

思路

尼姆博弈的变形
只需要确保异或值为0即可

G

Description
某一天，qwb去WCfun面试，面试官问了他一个问题：把一个正整数n拆分成若干个正整数的和，请求出这些数乘积的最大值。
qwb比较猥琐，借故上厕所偷偷上网求助，聪明的你能帮助他吗?

Input
第一行为一个正整数T.(T<=100000)
接下来T行，每行一个正整数n(n<=1e9)，意义如题目所述。

Output
每一行输出一个整数，表示乘积的最大值，由于答案可能很大，请将答案对109+7取模后输出。

Sample Input
2
2
5

Sample Output
2
6

参考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
#include<bits/stdc++.h>
#define LL long long
const LL mod =1e9+7;
using namespace std;
LL solve(LL a,LL b){
    LL re=1,base=a%mod;
    while(b!=0){
        if(b&1) re=(re*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return re;
} 
int main(){
//  freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        LL n;
        scanf("%lld",&n);
        if(n==1){
            printf("1\n");
            continue;
        }
        if(n==2){
            printf("2\n");
            continue;
        }
        LL k=n/3;
        if(n%3==0) printf("%lld\n",solve(3,k));
        else if(n%3==1) printf("%lld\n",(solve(3,k-1)*4)%mod);
        else if(n%3==2) printf("%lld\n",(solve(3,k)*2)%mod);
    }
    return 0;
}

思路

确保分出来的数字3最多 2其次即可
快速幂

H(最小瓶颈路变形)

参考上一篇博客

J

Description
qwb最近在做一个群众收入统计。ta非常懒，以至于忘记了今天领导要来视察。所以急忙催下属去做统计。
在接下来长度为n的时间里,每个单位时间都有事情发生,可能会发下以下两种事件：
1 下属递交了一份调查报告，由于太匆忙，上面只有一个整数x，代表一个居民的收入。
2 领导来视察了，领导会来询问，收入在区间[l,r]内的居民的平均收入，qwb需要给出回答。
qwb非常讨厌小数，所以qwb上报时都会省略小数部分。如果上报时统计的人数为0，qwb就暴露了他偷懒的事情，他就会zhizhiwuwu。

Input
多组测试数据，处理到文件末尾。
每组测试数据的第一行为一个正整数n(0<=100000),确保所有的n的和不超过300000
接下来n行，
当第一个数为0时，代表操作1，后面跟着一个整数x(0<=x<=1000000)，意义如题目所述。
当第一个数为1时，代表操作2，后面跟着两个整数l，r(0<=l<=r<=1000000)，意义如题目描述。

Output
对于每一个领导的询问，给出一个回答，如果统计区间的人数为零，则输出”zhizhiwuwu”。（不带引号）
每个测试例之后输出一个空行。

Sample Input
3
0 1
0 3
1 1 3
2
0 1
1 2 2

Sample Output
2

zhizhiwuwu

参考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
#include<bits/stdc++.h>
#define LL long long
#define maxn 1000050
using namespace std;
LL m[maxn],p[maxn];
int lowbit(LL x){
    return x&(-x);
}
void update(LL x,LL add,LL *a){
    while(x<=maxn){
        a[x]+=add;
        x+=lowbit(x);
    }
}
LL sum(LL x,LL *a){
    LL ans=0;
    while(x>0){
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
//  freopen("input.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(m,0,sizeof(m));
        memset(p,0,sizeof(p));
        for(int i=1;i<=n;i++){
            int id; scanf("%d",&id);
            if(id==0){
                LL x; scanf("%lld",&x);
                x++;
                update(x,x-1,p);
                update(x,1,m);  
            }
            else{
                LL x,y;
                scanf("%lld%lld",&x,&y);
                x++,y++;
                LL num1=sum(y,p)-sum(x-1,p);
                LL num2=sum(y,m)-sum(x-1,m);
                if(num2==0) printf("zhizhiwuwu\n");
                else printf("%lld\n",num1/num2);
            }
        }
        printf("\n");
    }
    return 0;
}

思路

树状数组
2个树状数组分别维护收入和人数
注意：本题收入为0额外判断 所以整个树状数组右移1 把0空出来
所以显示出来所有的数值均加1 但是更新的数值仍然为x-1

K

Description
qwb遇到了一个问题：将分数a/b化为小数后，小数点后第n位的数字是多少？
做了那么多题，我已经不指望你能够帮上他了。。。

Input
多组测试数据，处理到文件结束。（测试数据<=100000组）
每组测试例包含三个整数a，b，n，相邻两个数之间用单个空格隔开，其中0 <= a <1e9，0 < b < 1e9，1 <= n < 1e9。

Output
对于每组数据，输出a/b的第n位数，占一行。

Sample Input
1 2 1
1 2 2

Sample Output
5
0

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL x,mod,n;
LL quick_pow(LL a,LL b){
    LL re=1,base=a%mod;
    while(b){
        if(b&1) re=(re*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return re;
}
int main(){
//  freopen("input.txt","r",stdin);
    while(scanf("%lld%lld%lld",&x,&mod,&n)!=EOF){
        printf("%lld\n",x*quick_pow(10,n-1)%mod*10/mod);
    }
    return 0;
}

思路

求第k位小数：
把该数扩大(k-1)倍除以除数的余数*10再除以除数就是答案

M

Description
某一天，qwb正在上数据结构课。老师在讲台上面讲着二叉树，qwb在下面发着呆。
突然qwb想到一个问题：对于一棵n个无编号节点，m个叶子的有根二叉树，有多少种形态呐？你能告诉他吗？

Input
多组输入，处理到文件结束,大约有104组数据。
每一组输入一行，两个正整数n,m(0≤m≤n≤50),意义如题目所述。

Output
每一行输出一个数，表示相应询问的答案,由于答案可能很大，请将答案对109+7取模后输出。

Sample Input
4 2
10 5

Sample Output
6
252

参考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 LL long long
#define maxn 55
using namespace std;
const LL mod = 1e9+7;
int n,m;
LL dp[maxn][maxn];
void solve(){
    dp[0][0]=1,dp[1][1]=1,dp[2][1]=2;
    for(int i=3;i<maxn;i++){
        for(int j=1;j<i;j++){
            int x=0,y=i-1;
            for(;x<y;x++,y--){
                for(int k=0;k<=j;k++) dp[i][j]=(dp[i][j]+2*(dp[x][k]*dp[y][j-k]%mod)%mod)%mod;
            }
            if(x==y){
                for(int k=0;k<=j;k++) dp[i][j]=(dp[i][j]+dp[x][k]*dp[y][j-k]%mod)%mod;
            }
        }
    }
}
int main(){
//  freopen("input.txt","r",stdin);
    solve();
    while(scanf("%d%d",&n,&m)!=EOF){
        printf("%lld\n",dp[n][m]);
    }   
    return 0;
}

思路

二叉树的类型是典型的卡特兰数问题
加了叶子节点的限制 dp即可

本文标题:浙工业之江学院比赛

文章作者:Hippopmonkey

发布时间:2017-06-11, 15:10:20

最后更新:2017-06-11, 16:20:53

原始链接:http://xuboming8.github.io/2017/06/11/浙工业之江学院比赛/

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

文章目录
  1. 1. 浙工业之江学院比赛
    1. 1.1. A
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. B
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. C
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
    4. 1.4. D
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
    5. 1.5. E
      1. 1.5.1. 参考AC代码
      2. 1.5.2. 思路
    6. 1.6. F
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
    7. 1.7. G
      1. 1.7.1. 参考AC代码
      2. 1.7.2. 思路
    8. 1.8. H(最小瓶颈路变形)
    9. 1.9. J
      1. 1.9.1. 参考AC代码
      2. 1.9.2. 思路
    10. 1.10. K
      1. 1.10.1. 参考AC代码
      2. 1.10.2. 思路
    11. 1.11. M
      1. 1.11.1. 参考AC代码
      2. 1.11.2. 思路
|