期望得分：40+80+30=150

实际得分：80+70+0=150

 

T1

LYK loves string(string)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

LYK喜欢字符串，它认为一个长度为n的字符串一定会有n*(n+1)/2个子串，但是这些子串是不一定全部都不同的，也就是说，不相同的子串可能没有那么多个。LYK认为，两个字符串不同当且仅当它们的长度不同或者某一位上的字符不同。LYK想知道，在字符集大小为k的情况下，有多少种长度为n的字符串，且该字符串共有m个不相同的子串。

由于答案可能很大，你只需输出答案对1e9+7取模后的结果即可。

 

输入格式(string.in)

一行3个数n,m,k。

 

输出格式(string.out)

    一行，表示方案总数。

 

输入样例

2 3 3

 

输出样例

6

 

样例解释

共有6种可能，分别是ab,ac,ba,bc,ca,cb。

 

数据范围

对于20%的数据：1<=n,k<=5。

对于40%的数据：1<=n<=5,1<=k<=1000000000。

对于60%的数据：1<=n<=8,1<=k<=1000000000。

对于100%的数据：1<=n<=10,1<=m<=100,1<=k<=1000000000。

 

Hint

本题非常easy。

 

k再大也没有用，最多就用n种字符，最后乘个组合数即可

搜索出用i（i<=n）种字符，有m种不同子串的字符串的个数 f[i]

ans= Σ f[i]*C(k,i)

 

搜索的时候每次只往后扩增一个新字母

即 若当前字母为i，下一个字母的范围为[1,i+1]

设字符集大小为S

这样对于搜出的每种方案 * S的阶乘 即为 用 S 种 字符的答案

 

判断一个字符串内有多少种不同的字串时，用哈希

 

#include
      
       #include
       
        using namespace std;typedef long long LL;const int mod=1e9+7;int n,m;int a[11];LL has[11],b[11];int f[11]; int inv[11];LL Pow(LL a,int b){    LL res=1;    for(;b;a*=a,b>>=1)        if(b&1) res*=a;    return res;}void dfs(int now,int cnt,int lim){    if(cnt>lim || n-now+1
        
         >=1)        if(b&1) res=1LL*res*a%mod;    return res;}int main(){    freopen("string.in","r",stdin);    freopen("string.out","w",stdout);     int k;    scanf("%d%d%d",&n,&m,&k);    int t=min(n,k);    for(int i=1;i<=t;++i) dfs(1,0,i);    LL bit=1;    for(int i=1;i<=t;++i)     {        inv[i]=pow(i,mod-2);        bit*=i;        f[i]=f[i]*bit%mod;    }    int ans=0;    for(int i=1;i<=t;++i) ans=(ans+1LL*f[i]*getC(k,i)%mod)%mod;    printf("%d",ans); }
        
       
      

 

考场80分找规律代码

#include
      
       #include
       
        using namespace std;const int mod=1e9+7;typedef long long LL;int main(){    freopen("string.in","r",stdin);    freopen("string.out","w",stdout);    int n,m,k;    scanf("%d%d%d",&n,&m,&k);    if(m
        
         n*(n+1)/2)  cout<<0;    else if(n==m) cout<
        
       
      

 

T2

LYK loves graph(graph)

Time Limit:2000ms   Memory Limit:128MB

 

题目描述

LYK喜欢花花绿绿的图片，有一天它得到了一张彩色图片，这张图片可以看做是一张n*m的网格图，每个格子都有一种颜色去染着，我们用-1至n*m-1来表示一个格子的颜色。特别地，-1代表这个颜色是黑色，LYK不喜欢黑色！

LYK想将剪下这张图片中的一张子图片来（四联通块），使得这个子图片不存在黑色的格子，并且至少有k个不同的颜色。

但是每个格子有自己的脾气，特别的，第i行第j列这个格子如果被LYK选中了，LYK需要花费相应的代价。LYK想花费尽可能少的代价来剪下一张满足自己要求的图片。

 

输入格式(graph.in)

    第一行三个整数，n,m,k.

    接下来n行，每行m个数，表示图片中每个格子的颜色，每个数在-1到n*m-1之间。

　　接下来n行，每行m个数，表示选择每个位置所需要的代价。

 

输出格式(graph.out)

一行，表示最小代价和。

 

输入样例

3 3 3

0 0 1

2 3 3

-1 2 1

3 1 5

4 10 1

9 3 4

 

输出样例

7

 

数据范围

对于20%的数据：1<=n,m,k<=4。

对于另外30%的数据：不同的颜色数<=10（不包括-1）。

对于再另外30%的数据：1<=n<=2，1<=m<=15。

对于100%的数据：1<=n,m<=15，1<=k<=7，1<=ai,j<=100000。

数据保证一定有解。

 

听到标算的我一口老血喷了出来。。。

 

首先这题肯定是斯坦纳树（除非你想写插头DP）

但是颜色总数高达225种，没法状态压缩

但是询问只要求有7种颜色，所以就可以大开脑洞：

 

把225种颜色随机映射成7种颜色，然后做斯坦纳树！！！

 

我们来分析分析它的正确率：

首先可以肯定的是我们算出的答案只会大于等于最优解

因为原本不同的颜色可能被随机映射为相同的颜色，原本相同的颜色随机映射后一定不同

对于最优解中的7种颜色来说,

每种颜色都有7种映射方案，所以一共有7^7种映射方案

而只有这7种颜色映射玩之后还是7种颜色，才有可能算出最优解，这种情况一共有 7! 种

所以随机映射做斯坦纳树一次 的 正确率 为 7！/  7^7  ≈ 0.006 = 0.6% 

错误率=99.4%

那么如果随机映射做斯坦纳树T次，错误率就是 99.6%  ^ T 

如果T=400，错误率 ≈ 9%

那么正确率  ＝ 91%

你还可以再多做几遍，正确率还是蛮高的。。。。。。

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
            #include
           
            using namespace std;#define N 16 int n,m,k;int col[N][N],val[N][N];int a[N*N],mp[N*N];int ncol[N][N];int dp[N][N][1<<7];struct node{ int x,y; node(int x=0,int y=0):x(x),y(y) {}};queue
            
             q;bool vis[N][N];int dx[4]={-1,0,1,0};int dy[4]={ 0,1,0,-1};int ans=2e9;void read(int &x){ x=0; int f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } x*=f;}void spfa(int s){ node now; int sx,sy,nx,ny; while(!q.empty()) { now=q.front(); q.pop(); sx=now.x; sy=now.y; vis[sx][sy]=false; for(int i=0;i<4;++i) { nx=sx+dx[i]; ny=sy+dy[i]; if(nx<=0 || nx>n || ny<=0 || ny>m || ncol[nx][ny]==-1) continue; if(dp[nx][ny][s]>dp[sx][sy][s]+val[nx][ny]) { dp[nx][ny][s]=dp[sx][sy][s]+val[nx][ny]; if(!vis[nx][ny]) q.push(node(nx,ny)),vis[nx][ny]=true; } } }}void Steiner(){ memset(dp,63,sizeof(dp)); int oo=dp[0][0][0]; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(ncol[i][j]!=-1) dp[i][j][1<
            
           
          
         
        
       
      

 

期望80实际70暴力

说好的不包括-1呢。。。

不过没判-1拿了30里面的20，这数据准是随机的。。。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 16int n,m,k;int col[16][16],val[16][16];bool tag;int num,first[N*N];int dx[4]={-1,0,1,0};int dy[4]={
    0,1,0,-1};void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;}void init(){    read(n); read(m); read(k);    memset(first,-1,sizeof(first));    for(int i=1;i<=n;++i)        for(int j=1;j<=m;++j)        {            read(col[i][j]);            if(col[i][j]==-1) tag=true;            else if(first[col[i][j]]==-1) first[col[i][j]]=num++;        }    for(int i=1;i<=n;++i)        for(int j=1;j<=m;++j)            read(val[i][j]);}bool inmap(int x,int y){    if(!x || !y || x>n || y>m) return false;    return true;}bool ok(int s){    int cnt=0;    for(int i=1,bit=1;i<=30;++i,bit<<=1) cnt+=bool(s&bit);    return cnt>=k;}namespace force1{    bool use[5][5];    bool vis[5][5];        int sum,ans;        bool use_col[N*N];        void dfs2(int x,int y)    {        sum++;        vis[x][y]=true;        int nx,ny;        for(int i=0;i<4;++i)        {            nx=x+dx[i]; ny=y+dy[i];            if(inmap(nx,ny) && !vis[nx][ny] && use[nx][ny]) dfs2(nx,ny);        }    }        bool connect()    {        int sx=0,sy=0,tot=0;        for(int i=1;i<=n;++i)            for(int j=1;j<=m;++j)                if(use[i][j])                {                    tot++;                    if(!sx) sx=i,sy=j;                }        sum=0;        memset(vis,false,sizeof(vis));        dfs2(sx,sy);        return sum==tot;    }        void judge()    {        if(!connect()) return;        int cnt=0,ccnt=0;        memset(use_col,0,sizeof(use_col));        for(int i=1;i<=n;++i)            for(int j=1;j<=m;++j)                if(use[i][j])                 {                    if(col[i][j]==-1) return;                    cnt+=val[i][j];                    if(!use_col[col[i][j]])                    {                        use_col[col[i][j]]=true;                        ccnt++;                    }                }        if(ccnt
           
            q; bool vis[N][N]; void spfa(int s) { node now; int nx,ny; while(!q.empty()) { now=q.front(); q.pop(); vis[now.x][now.y]=false; for(int i=0;i<4;++i) { nx=now.x+dx[i]; ny=now.y+dy[i]; if(!inmap(nx,ny)) continue; if(f[now.x][now.y][s]+val[nx][ny]
           
          
         
        
       
      

 

T3

LYK loves rabbits(rabbits)

Time limit:1000ms     Memory limit:128MB

 

题目描述

LYK喜欢兔子，它在家中养了3只兔子。

有一天，兔子不堪寂寞玩起了游戏，3只兔子排成一排，分别站在a,b,c这3个位置。

游戏的规则是这样的，重复以下步骤k次：选择两个不同的兔子A和B，假如它们位于X与Y，A可以从X跳到Y+Y-X处，但是跳跃时是不允许一下子跳过两只兔子的，也就是说第三只兔子不在[min{X,Y+Y-X},max{X,Y+Y-X}]处。

现在3只小兔子的位置分别到了x,y,z(3只兔子长得一样，即三只兔子跳完之后的顺序可以变化)处，但是它们忘记一开始是怎么跳的了，想让你帮它们还原跳法。但这个问题非常easy，于是LYK要求你输出方案总数。

保证答案有解。

由于答案巨大，你只需输出答案对1e9+7取模后的结果就可以了。

 

输入格式(rabbits.in)

第一行3个数a,b,c。

第二行3个数x,y,z。

第三行一个数k。

数据保证3只兔子的起始位置a,b,c严格递增且3只兔子最终的位置x,y,z严格递增。

 

输出格式(rabbits.out)

一行表示方案总数。

 

输入样例1

0 2 5

0 2 5

2

 

输出样例1

3

 

输入样例2

0 2 4

0 2 4

2

 

输出样例2

2

 

样例解释

对于样例1：共有3种跳法，第一次跳完后的位置分别是{0,-2,5},{4,2,5},{0,8,5}。

 

数据范围

对于10%的数据k=1。J

对于30%的数据k<=10。

对于另外20%的数据a=x,b=y,c=z。

对于再另外20%的数据a-b=b-c。

对于再再另外20%的数据a,b,c与x,y,z之间不超过10步可达。

对于100%的数据k<=100,|a|,|b|,|c||x|,|y|,|z|<=10^18。

 

如果能由外往里跳，那么只能跳一个

中间那个可以往外跳，有向左和向右两种方式

所以跳的路径是一棵二叉树

设起始位置在A号节点，终止位置在B号节点

令f[i][j][k] 表示A 和 LCA的距离为i，B 和 LCA的距离为j，还剩下k步可以跳的方案数

一、对于一般的一对A和B（不在根节点，且LCA不是A或B）来说，有两种决策：

1、A向上跳，跳到 i-1 j  k-1

2、A向下跳，A往左往右跳一个样，跳到 i+1 j k-1，方案数*2

二、若A是LCA

如果B也是LCA，即A和B在同一个位置，那可以

1、A往上跳，跳到 i j+1 k-1

2、A往下跳，跳到 i+1 j k-1 方案数*2

如果B不是LCA，

1、A往上跳，跳到 i j+1 k-1

2、A往下跳，跳到非B所在的子树 i+1 j k-1；跳到B所在的子树 i j-1 k-1

注意，A有可能是二叉树的根节点，这样A不能向上跳

此时i=0，j>B的深度，特判这种情况

 

#include
      
       #include
       
        using namespace std;typedef long long LL;const int mod=1e9+7;#define N 101LL a0[N],b0[N],c0[N];LL x0[N],y0[N],z0[N];int f[N][N][N];int k1,k2;int dfs(int i,int j,int k){    if(!i && !j && !k) return 1;    if(i+j>k) return 0;    if(!i && j>k2) return 0;    if(f[i][j][k]!=-1) return f[i][j][k];    if(!i)     {        if(!j) f[i][j][k]=(dfs(0,1,k-1)+dfs(1,0,k-1)*2%mod)%mod;        else f[i][j][k]=((dfs(0,j+1,k-1)+dfs(0,j-1,k-1))%mod+dfs(1,j,k-1))%mod;    }    else f[i][j][k]=(dfs(i-1,j,k-1)+dfs(i+1,j,k-1)*2%mod)%mod;     return f[i][j][k];}int main(){    freopen("rabbits.in","r",stdin);    freopen("rabbits.out","w",stdout);    int k;    scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a0[0],&b0[0],&c0[0],&x0[0],&y0[0],&z0[0]);    scanf("%d",&k);    bool root=false;    while(k1
       
      

 

考场爆零原因：用%d读long long

 

Summary

1、本场考试150分虽然是rank3，但150分的有8个，T3直接输出1拿到10分就可以脱颖而出

2、考场上的一分钟都不能放弃，到了最后也要垂死挣扎，特判之类的东西全打上，多扑腾会儿

3、T1正解是搜索，我在考场上是打表找规律，只找全了n<=6的，>6的只找到了m等于能取到的最大值和次大值的规律，期望是40分，结果后面60%的数据有40%的数据m是最/次大值，这就多得了40分，考场上还觉得没有什么用犹豫了好久才打上，所以如果写的是特判之类的，不要放过任何对的idea，说不定你就判到了数据呢。（对于这种搜索题数据为梯度内极端数据可能性比较大）

4、T2暴力80分，因为实际数据与题面中的数据描述不符，拿了70分，那个正解随机性算法是当时的我无论如何也想不到的，在这种情况下，一定要拿满暴力分

5、一定要特别注意long long的读入与输出，不仅仅是lld与I64d的问题，考场上用%d读long long，自己造的小数据没有问题，测试数据全>int。这种蠢到不能再蠢得问题不能出现第二次

6、加强搜索，T1竟然没看出来是道搜索题

7、谁说随机性的、正确率不是100%的算法就不可能成为正解了？在大量的操作下，错误率大大的降低。要注重一些非完美算法，也多思考一些非完美的解题思路（毕竟目前对我来说省选及以上难度比赛中想出正解的概率是很小的），不一定非要是有名字的算法呀！！