山东省第八届ACM省赛 fireworks

迟来的祝福,新年快乐.

Link

要登录

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3895.html

Type: 杨辉三角<-组合数学,逆元

题意

假设x位置有一个烟花,则每秒烟花都会分裂到x+1与x-1这两个位置.

给你n个烟花的初始位置xi和个数ci,问你T秒后,位置w上的烟花个数有多少个.

题解

画一下样例的图会发现很像杨辉三角,我们可以将每个初始点分开计算,最后的结果就是所有初始点分裂后落在目标点的烟花个数和.
但我们发现它们的初始值大小与杨辉三角不同,并且比杨辉三角多了许多0, 然后我们考虑如何解决这两个情况.

(1) 初始值ci,因为只有一个初始点,这点和杨辉三角一样.所以答案是

ans(原杨辉三角在该位置的结果)*ci

(2) 中间有0,这点好想,我们只需要通过推导公式将实际坐标转换为逻辑坐标即可.

然后我们分情况讨论,我们在图上可以发现

(1) 当 分裂次数目标位置和原位置的距离差 同奇偶时该位置结果为0.
(2) 当距离大于T+1时(即杨辉三角第T行值的个数),永远不可能分裂到.

因为只需要考虑最后一次分裂的结果,所以只需要计算杨辉三角第T行即可,即 C(T,0~T)
预处理组合公式我们用 组合数学 性质4那个公式.
所以我们需要预处理一下1~1e5的逆元,将除法转换为乘法.
最后答案就是

ans=Sigma(i=1~n,c*C[实际位置] | 根据情况忽略i)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int maxn = 1e5+7;

LL C[maxn];
///逆元
LL inv[maxn];
void init_(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(MOD-MOD/i)*1ll*inv[MOD%i]%MOD;
    }
}

///快速幂模求逆元,调动方式quick_mod(i,MOD-2)
//这里我们用预处理.
LL quick_mod(LL x, int n){
    LL ret = 1;
    while(n){
        if(n & 1) ret = ret * x % MOD;
        x = x * x %MOD;
        n >>= 1;
    }
    return ret;
}

void init(int t){
    C[0]=1;
    for(int i=1;i<=t;++i){
        C[i]=C[i-1]*(t-i+1)*1ll%MOD*inv[i]%MOD;
        //printf("Num: %d %lld, INV: %lld\n",i,C[i],inv[i]);
    }
}
//判断是否同奇同偶
bool same(int x,int y){
    if((x&1)^(y&1)) return false;
    return true;
}

int query(int t,int d){
    if(t&1){
        return t/2-d/2;
    }
    return t/2+(d-1)/2;
}

int main(){
    init_();
    int n,T,w;
    while(~scanf("%d%d%d",&n,&T,&w)){
        init(T);
        LL ans=0;
        for(int i=1;i<=n;++i){
            int x,c;
            scanf("%d%d",&x,&c);
            int dist=abs(x-w);
            if(!same(T+1,dist) && dist<T+1){
                ans=(ans+c*C[query(T+1,dist)]%MOD)%MOD;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}

第八届ACM省赛 K CF

CF

sdut 3903

Time Limit: 1000MS
Memory Limit: 65536KB

Problem Description

LYD loves codeforces since there are many Russian contests. In an contest lasting for T minutes there are n problems, and for the ith problem you can get aiditi points, where ai indicates the initial points, di indicates the points decreased per minute (count from the beginning of the contest), and ti stands for the passed minutes when you solved the problem (count from the begining of the contest).
Now you know LYD can solve the ith problem in ci minutes. He can’t perform as a multi-core processor, so he can think of only one problem at a moment. Can you help him get as many points as he can?

Input

The first line contains two integers n,T(0≤n≤2000,0≤T≤5000).
The second line contains n integers a1,a2,..,an(0<ai≤6000).
The third line contains n integers d1,d2,..,dn(0<di≤50).
The forth line contains n integers c1,c2,..,cn(0<ci≤400).

Output

Output an integer in a single line, indicating the maximum points LYD can get.

Example Input

3 10
100 200 250
5 6 7
2 4 10

Example Output

254

题意

有 n 道题目,每一道题都有一个初始分值 ai ,每个单位时间这道题的分数便会减少 di ,而我们可以在 ci 时间内做出这道题而得到分数,求在时间 T 内最多可以获得的分数。

题解

首先可以感觉出这是道0-1背包问题,然后我们需要知道,当我们做题时,会一两个角度来选择题目,其一是选择做题速度最快的,其二是选择做分值降低速度最快的.那么我们的衡量标准就可以看成先做单位时间内做题最多的那道.
然后我们根据上述规则排一下序.
在用排序后的数组进行0-1背包.在背包过程中记录最大值,即为最后的结果.

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000;

struct pro{
    int a,d,c;
    //按单位时间内减少分值排序
    bool operator <(const pro &pt)const{
        return 1.0*d/c>(1.0*pt.d/pt.c);
    }
};

int n,T;
pro p[maxn];
int dp[5010];
int main(){
    while(~scanf("%d%d",&n,&T)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].a);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].d);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].c);
        }
        sort(p,p+n);
        int mx=-1;
        for(int i=0;i<n;++i){
            for(int j=T;j>=0;--j){
                if(j>=p[i].c){
                    dp[j]=max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].d);
                }
                mx=max(mx,dp[j]);
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}

第八届ACM省赛 Quadrat 找规律

原题连接: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/problemlist/cid/2164

B题

题意: 求数位为n位的所有数字(0~9..9(n个9))中,各个数位与其平方%10^n所得数的各个数位之差不超过d的数的个数.

注: 所有的数位之差是循环的,比如9和1差2.

首先打表(不过我认为这道题是数位dp,但我不会):

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int num[5]={1,10,100,1000,10000};
int a[15][15];
void init(){
    memset(a, 0, sizeof(a));
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j <= 9; ++j){
            a[i][j] = abs(i-j);
            if(a[i][j] > 5) a[i][j] = 10 - a[i][j];
        }
    }
}

bool judge(int i,int digit,int d){
    int res=i*i;
    for(int j=1;j<=digit;++j){
        int b=i%10;
        int c=res%10;
        i/=10;res/=10;
        if(a[b][c]>d) return false;
    }
    return true;
}

int check(int nb,int d){
    int cnt=0;
    for(int i=0;i<num[nb];++i){
        if(judge(i,nb,d))
            cnt++;
    }
    return cnt;
}

int main(){
    init();
    for(int i=1;i<=4;++i){
        printf("%d:",i);
        for(int j=0;j<4;++j){
            printf(" %d",check(i,j));
        }
        printf("\n");
    }
    return 0;
}

发现dp[i][j]=dp[i-1][j]*(2*j+1)

Code:

#include<cstdio>
#include<algorithm>
using namespace std;

long long dp[19][4];

void init(){
    dp[1][0]=4;dp[1][1]=4;
    dp[1][2]=8;dp[1][3]=8;
    for(int i=2;i<=18;++i){
        for(int j=0;j<4;++j){
            dp[i][j]=dp[i-1][j]*(2*j+1);
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d %d",&n,&d);
        printf("%lld\n",dp[n][d]);
    }
    return 0;
}