friends

friends

关注
发信
关注(28)粉丝(399)

2017-10-3 清北刷题冲刺班a.m

P99
zhx

a

【问题描述】
你是能看到第一题的 friends 呢。
——hja
怎么快速记单词呢？也许把单词分类再记单词是个不错的选择。何大爷给
出了一种分单词的方法，何大爷认为两个单词是同一类的当这两个单词的各个
字母的个数是一样的，如 dog 和 god。现在何大爷给了你?个单词，问这里总共
有多少类单词。
【输入格式】
第一行一个整数?代表单词的个数。
接下来?行每行一个单词。
【输出格式】
一行一个整数代表答案。
【样例输入】
3
AABAC
CBAAA
AAABB
【样例输出】
2
【数据范围与规定】
70%的数据，1 ≤ ? ≤ 100。
对于100%的数据，1 ≤ ? ≤ 10000，所有单词由大写字母组成。

#include<iostream>

#include<cstdio>

#include<cstring>

#define mod 100000003

using namespace std;

int su[]={,,,,,,,,,,,,,,,,,,,,,,,,,};

int n,cnt;

bool vis[];

string s;

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("a.in","r",stdin);freopen("a.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        long long now=;

        s="";

        cin>>s;

        int len=s.length();

        for(int j=;j<len;j++)

            now=1LL*now*su[s[j]-'A']%mod;

        if(!vis[now]){

            cnt++;

            vis[now]=;

        }

    }

    printf("%d",cnt);

    fclose(stdin);fclose(stdout);

    return ;

}

100分 唯一分解定理

b

【问题描述】
你是能看到第二题的 friends 呢。
——laekov
长度为?的铁丝，你可以将其分成若干段，并把每段都折成一个三角形。你
还需要保证三角形的边长都是正整数并且三角形两两相似，问有多少种不同的
分法。
【输入格式】
一行一个整数?。
【输出格式】
一行一个整数代表答案对10 9 + 7取模之后的值。
【样例输入 1
6
【样例输出 1】
2
【样例输入 2】
9
【样例输出 2】
6
【样例解释 2】
(1,1,1),(2,2,2);(2,2,2),(1,1,1)算两种方案。
【数据范围与规定】
3。
60%的数据，1 ≤ ? ≤ 1000。
对于100%的数据，1 ≤ ? ≤ 10 6 。

#include<iostream>

#include<cstdio>

using namespace std;

int n;

int main(){

    freopen("b.in","r",stdin);freopen("b.out","w",stdout);

    scanf("%d",&n);

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    if(n==)cout<<;

    fclose(stdin);fclose(stdout);

    return ;

}

30分 打表

/*

    f[g]：以g为周长，并且三边gcd为1的三角形个数

    h[n/g]：把n/g分配给任意多个三角形的方案数

    把x个物品分配给任意多个三角形的方案数为2^(x-1)

*/

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

const int mo=;

int n,cnt,f[maxn],er[maxn],divisor[maxn];

#define inc(a,b) a+=b,(a>=mo ? a-=mo : 0)

int main()

{

    freopen("b.in","r",stdin);

    freopen("b.out","w",stdout);

    scanf("%d",&n);

    for (int a=;a<=n;a++)

        f[a]=f[a-],inc(f[a],a/-a/);

    for (int a=;a*a<=n;a++)

        if (n % a==)

        {

            cnt++;

            divisor[cnt]=a;

            if (a*a!=n)

            {

                cnt++;

                divisor[cnt]=n/a;

            }

        }

    sort(divisor+,divisor+cnt+);

    for (int a=;a<=cnt;a++)

        for (int b=;b<a;b++)

            if (divisor[a] % divisor[b]==) inc(f[divisor[a]],mo-f[divisor[b]]);

    er[]=;

    for (int a=;a<=n;a++)

        er[a]=er[a-],inc(er[a],er[a-]);

    int ans=;

    for (int a=;a<=cnt;a++)

        inc(ans,(long long)f[divisor[a]]*er[n/divisor[a]-]%mo);

    printf("%d\n",ans);

    return ;

}

100分

c

【问题描述】
你是能看到第三题的 friends 呢。
——aoao
在小学的时候，我们都学过正视图和左视图。现在何大爷用一些小方块摆了
一个图形，并给出了你这个图形的左视图和正视图。现在何大爷希望知道，在给
定正视图和左视图的情况下，原来的立体图形有多少种可能的情况？
【输入格式】
第一行两个整数?,?，代表在左视图和正视图中分别有多少列。
第二?个整数，代表在左视图中从左至右每一列的高度。
第三行?个整数，代表在正视图中从左至有每一列的高度。
【输出格式】
一行一个整数代表答案对10 9 + 9取模之后的值。
【样例输入 1】
2 2
1 1
1 1
【样例输出 1】
7
【样例输入 2】
4 5
5 2 4 1
5 2 4 0 1
【样例输出 2】
429287
【数据规模与约定】
21 ≤ ?,? ≤ 5，每列的最大高度不超过5。
40%的数据，? + ? ≤ 18。
对于100%的数据，1 ≤ ?,? ≤ 50，每列最大高度不超过10000。

#include<iostream>

#include<cstdio>

#define mod 1000000009

#define maxn 51

using namespace std;

int a[maxn],b[maxn],n,m,mx[maxn][maxn],ans,now[maxn][maxn];

int mxx[maxn],mxy[maxn];

bool check(){

    for(int i=;i<=n;i++)

        if(mxx[i]!=a[i])return ;

    for(int i=;i<=m;i++)

        if(mxy[i]!=b[i])return ;

    return ;

}

void dfs(int x,int y){

    if(y==m+&&mxx[x]!=a[x])return;

    if(x==n&&y>&&mxy[y-]!=b[y-])return;

    if(y>m)y=,x++;

    if(x>n){

        if(check())ans++;

        if(ans>=mod)ans-=mod;

        return;

    }

    int mx1,mx2;

    for(int i=;i<=mx[x][y];i++){

        now[x][y]=i;

        mx1=mxx[x];mx2=mxy[y];

        mxx[x]=max(mxx[x],i);

        mxy[y]=max(mxy[y],i);

        dfs(x,y+);

        mxx[x]=mx1;mxy[y]=mx2;

    }

}

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("c.in","r",stdin);freopen("c.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=m;i++)scanf("%d",&b[i]);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            mx[i][j]=min(a[i],b[j]);

    dfs(,);

    printf("%d",ans);

    fclose(stdin);fclose(stdout);

    return ;

}

10分 暴力

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#define LL long long

#ifdef unix

#define RE "%lld"

#else

#define RE "%I64d"

#endif

using namespace std;

const int VAL = , MAXN = , mo = 1e9 + ;

int n, m, a[VAL], b[VAL];

int c[MAXN][MAXN];

void init_c(int n) {

    for (int i = ; i <= n; ++ i)

        c[i][] = c[i][i] = ;

    for (int i = ; i <= n; ++ i)

        for (int j = ; j < n; ++ j)

            c[i][j] = (c[i-][j-] + c[i-][j]) % mo;

}

int modpow(int a, int b) {

    int res = , q = a;

    while (b) {

        if (b & ) res = 1ll * res * q % mo;

        q = 1ll * q * q % mo;

        b >>= ;

    }

    return res;

}

int calc(int n, int m, int nn, int mm, int h) {

    int res = ;

    for (int i = ; i <= nn; ++ i)

        for (int j = ; j <= mm; ++ j) {

            int tmp = 1ll * modpow(h, n * m - (n - i) * (m - j)) * modpow(h+,(n-i)*(m-j)-(n-nn)*(m-mm)) % mo

                      * c[nn][i] % mo * c[mm][j] % mo;

            if ((i + j) & ) res = ((res - tmp) % mo + mo ) % mo;

            else {

                res += tmp; if (res >= mo) res -= mo; }

        }

    return res;

}

int main() {

    freopen("c.in","r",stdin);

    freopen("c.out","w",stdout);

    scanf("%d%d", &n, &m);

    for (int i = , x; i <= n; ++ i)

        scanf("%d", &x), a[x] ++;

    for (int i = , x; i <= m; ++ i)

        scanf("%d", &x), b[x] ++;

    init_c(max(n, m));

    LL res = ;

    int nown = , nowm = ;

    for (int i = ; i >= ; -- i)

       if (a[i] || b[i]) {

            nown += a[i], nowm += b[i];

            res = 1ll * res * calc(nown, nowm, a[i], b[i], i) % mo;

       }

    printf(RE"\n", res);

    return ;

}

100分 容斥原理

05-19 14:48
Powered by LMLPHP ©2024 friends 0.052275