总体来说难度适中的一场SRM~

300:BearCries

题意:

给定一个长度为N(N<=200)的字符串 字符串中只含有”;”和”_“两种字符 一个合法的Cry表情为两个”;”中间含有至少一个”_“
一个合法Cry表情为字符串的一个子串(不必在原串中连续)
求题目中给出的字符串分解成若干个合法Cry表情的方案数(原字符串中的每个字符都必须出现在某个Cry表情中 并且只能出现一次)

题解:

问题可以由dp解决
我们考虑状态f[i][j][k]表示当前考虑到第I个字符 前面有J个”;”还未匹配”_“ 有K个”;”已经匹配至少一个”_“
考虑第i+1个字符
若第i+1个字符为; 我们可以分两种情况讨论

1.他和前面的某个已经至少匹配了一个”_“的”;”组合成一个合法的Cry表情
2.他不和前面的”;”匹配 他成为一个新的还未匹配”_“的”;”

若第i+1个字符为_ 我们也可以分两种情况讨论

1.他和前面某个还未匹配”_“的”;”组合成为一个已经匹配至少一个”_“的”;”
2.他和前面某个已经至少匹配一个”_“的”;”组合 仍然为一个至少匹配一个”_“的”;”

到这里问题已经得到解决 答案即为f[n][0][0]

代码:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <set>

using namespace std;

typedef long long LL;

class BearCries
{
    public:
    int count(string s)
    {
        int n=s.size();
        LL f[205][205][205];
        int a[205];
        LL mod=1e9+7;
        int ans;
        for (int i=0;i<n;++i) if (s[i]==';') a[i+1]=1;else a[i+1]=0;
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        for (int i=1;i<=n;++i)
            for (int j=0;j<=n;++j)
                for (int k=0;k<=n;++k)
                {
                    // f[j][k]  j not has k  has
                    if (a[i]==1)
                    {
                        f[i][j+1][k]+=f[i-1][j][k],f[i][j+1][k]%=mod;
                        if (k>=1) f[i][j][k-1]+=k*f[i-1][j][k]%mod,f[i][j][k-1]%=mod;
                    }
                    else
                    {
                        f[i][j][k]+=k*f[i-1][j][k]%mod,f[i][j][k]%=mod;
                        if (j>=1) f[i][j-1][k+1]+=j*f[i-1][j][k]%mod,f[i][j-1][k+1]%=mod;    
                    }
                }
        cout<<f[1][1][0]<<endl;
        ans=f[n][0][0];
        return ans;
    }
};

500: BearDarts

题意:

给定一个含有N(N<=1000)个元素的数组w 求有多少四元组(i,j,p,q)满足

  • i<j<p<q
  • $w[i] \times w[p]$=$w[j] \times w[q]$

题解

为了方便我们令$a=w[i]$ $b=w[j]$ $c=w[p]$ $d=w[q]$
我们先来枚举a和b 那么问题就变成了有多少对(c,d)满足条件
$a \times c$=$b \times d$
于是 $a / b$=$d / c$
于是我们可以枚举a,b,查找后面有多少个数对满足条件啦!
具体实现和我的上一篇日志CF 325 的D题很像,用个map就好啦

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <set>

using namespace std;

typedef long long LL;

class BearDarts
{
    public:
    long long count(vector <int> w)
    {
        int n,a,b,c,d,z;
        map<pair<int,int>,LL> mp;
        LL ans=0;
        n=w.size();
        c=w[n-2];d=w[n-1];
        z=__gcd(c,d);
        mp[make_pair(c/z,d/z)]++;
        for (int i=n-3;i>=1;--i)
        {
            b=w[i];
            for (int j=i-1;j>=0;--j)
            {
                a=w[j];
                //ac=bd
                //a/b=d/c
                z=__gcd(a,b);
                ans+=mp[make_pair(b/z,a/z)];        
            }
            c=w[i];
            for (int j=i+1;j<n;++j)
            {
                d=w[j];
                z=__gcd(c,d);
                mp[make_pair(c/z,d/z)]++;
            }
        }
        return ans;
    }
};

900: BearDestroys

题意:

给一个n$\times$m的方格图(n<=13,m<=30),每个格子可以写E或者S,所以一共有2^(n$\times$m)种图
一个人从(0,0)开始行优先行动 即从(0,0)->(0,m-1)->(1,0)->(1,m-1)->….->(n-1,0)->(n-1,m-1)
每次他到一个格子(i,j) 他执行以下操作:
1.如果该格子已经放置了骨牌 那么不做任何操作去下一格子
2.若该格子没有放置骨牌 该格子写的是E 那么如果他能放置一块1$\times$2的骨牌覆盖(i,j) (i,j+1) 则用1$\times$2的骨牌覆盖(i,j)(i,j+1) 否则如果他能放置一块2$\times$1的骨牌覆盖(i,j) (i+1,j) 则用2$\times$1的骨牌覆盖(i,j) (i+1,j)
3.若该格子没有放置骨牌 该格子写的是S 那么如果他能放置一块2$\times$1的骨牌覆盖(i,j) (i+1,j) 则用2$\times$1的骨牌覆盖(i,j)(i+1,j) 否则如果他能放置一块1$\times$2的骨牌覆盖(i,j) (i,j+1) 则用1$\times$2的骨牌覆盖(i,j) (i,j+1)

直到他到达(n-1,m-1)

一个图的得分为放置的骨牌数量

求这2^(n$\times$m)种图的得分的和对MOD取余

题解:

看到n<=13不难想到要状态压缩,然后我们来分析下放置骨牌的情况
我们考虑一下骨牌占得两个格子的位置 可以发现无论是1$\times$2的骨牌还是2$\times$1的骨牌 两个格子的坐标之和的差总是1

所以我们考虑将方格图分层
比如一个3$\times$4的方格图 可以分为6层(0~5)

0123
1234
2345

于是每层有最多N个元素 我们来对这N个元素进行状态压缩

对于一个状态now 若now的二进制表示第I位为1 则表示该格子已经被骨牌覆盖了 如果为0则为没覆盖

那么考虑dp:
f[i][j]表示到了第I层 第I层的状态为J时候的骨牌数量的总和
g[i][j]表示到了第I层 第I层的状态为J时候这种图的数量

考虑转移的时候比较麻烦 这里考虑从now状态可以转移到哪些next状态
对now状态每一行进行讨论

若now状态第r行为1 此时证明改格子已经被覆盖 那么他填E或S都无所谓 直接转移

接下来就是该格子未被覆盖的情况了

如果现在改格子右方已被覆盖(即next状态第r行为1)

此时无论该格子填E还是填S 他都是被2$\times$1的骨牌覆盖 将next状态第r+1行标志为1进行转移

如果现在该格子右方未被覆盖

此时如果该格子填E那么将next状态第R行标志为1进行转移

此时如果该格子填S那么将next状态第R+1行标志位1进行转移

这样进行转移更新后答案即为f[n+m-1][0]

具体的转移以及边界看代码有一些帮助

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>

using namespace std;

typedef long long LL;

class BearDestroys
{
    public:
    int w,h,mod;
    int f[50][10000];
    int g[50][10000];
    void dfs(int r,int sum,int now,int next,int ff,int gg)
    {
        if (r==h)
        {
            f[sum+1][next]=(f[sum+1][next]+ff)%mod;
            g[sum+1][next]=(g[sum+1][next]+gg)%mod;
            return;
        }
        int c=sum-r;
        if (0<=c&&c<=w-1)
        {
            if (now&(1<<r))
            {
                dfs(r+1,sum,now,next,ff*2%mod,gg*2%mod);
            }
            else
            {
                if ((c==w-1)||(next&(1<<r)))
                {
                    if (r==h-1)
                    {
                        dfs(r+1,sum,now,next,ff*2%mod,gg*2%mod);
                    }
                    else
                    {
                        dfs(r+1,sum,now,next+(1<<(r+1)),(ff*2%mod+gg*2%mod)%mod,gg*2%mod);
                    }
                }
                else
                {
                    if (r==h-1)
                    {
                        dfs(r+1,sum,now,next+(1<<r),(ff*2%mod+gg*2%mod)%mod,gg*2%mod);
                    }    
                    else
                    {
                        dfs(r+1,sum,now,next+(1<<r),(ff+gg)%mod,gg);
                        dfs(r+1,sum,now,next+(1<<(r+1)),(ff+gg)%mod,gg);
                    }
                }    
            }
        }
        else
        {
            dfs(r+1,sum,now,next,ff,gg);
        }
    }
    int sumUp(int W, int H, int MOD)
    {
        w=W;h=H;mod=MOD;
        int s=w-1+h-1;
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        f[0][0]=0;g[0][0]=1;
        for (int i=0;i<=s;++i)
        {
            for (int j=0;j<(1<<h);++j)
            {
                if (f[i][j]==0&&g[i][j]==0) continue;
                dfs(0,i,j,0,f[i][j],g[i][j]);
            }
        }
        return f[s+1][0];
    }
};

这一场前四题的题目难度还可以 下面为前四题的简易题解


A:Gennady the Dentist

题意:

有N(N<=4000)个孩子去看病 编号从1~n排成一列 每个孩子有三个属性v[i],d[i],p[i]表
v[i]表示孩子哭声的大小
d[i]表示孩子尖叫声的大小
p[i]表示孩子的忍耐度
每次一个孩子进去看病 发出v的哭声 后面排队的第I个孩子受到v-i+1的惊吓 忍耐度减少v-i+1
如果第J个孩子忍耐度<0 就会发出尖叫并离开队伍 对j之后的所有孩子造成d的惊吓
问最后有多少孩子可以看病

题解:

按照题意模拟即可 有两个trick
1:忍耐度有可能超过INT 需要使用LL
2:发出V的哭声时 先是对队伍中所有孩子造成相应影响 接下来在考虑离开队伍造成的位置变化

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

typedef long long LL;

int n;
LL a[5005],b[5005],c[5005];
int dq,now;
vector<int> v;
const int INF=19950920;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
    dq=1;
    while (dq<=n)
    {
        while (dq<=n&&c[dq]<0) dq++;
        if (dq>n) break;
        now=a[dq];
        v.push_back(dq);
        for (int i=dq+1;i<=n;++i)
        {
            if (c[i]>=0)
            {
                c[i]-=now;    
                now--;
                if (now==0) break;
            }
        }
        for (int i=dq+1;i<=n;++i)
        {
            if (c[i]>=0) continue;
            if (c[i]==-INF) continue;
            c[i]=-INF;
            for (int j=i+1;j<=n;++j)
            {
                if (c[j]>=0) c[j]-=b[i]; 
            }    
        }
        dq++;
    }
    printf("%d\n",v.size());
    for (int i=0;i<v.size();++i) printf("%d ",v[i]);    
    return 0;
}

B:Phillip and Trains

题意:

给定一个3*n(n<=100)的方格图,一个人处于最左端要去往最右,格子中有一些长度>=2的地铁,每一秒人与车轮流行动
人:向右走一格 然后选择不动或者向上向下(如果可以)
车:向左走两格
任何时刻人与车不能处于同一格子 问人能不能走到最右

题解:

简单题 f[i][j]表示能否到达(i,j)这个格子
转移:若f[i][j]可达 且当前(i,j+1),(i,j+2),(i,j+3) 没车子 那么f[i][j+1]可达
若f[i][j]可达 且当前(i,j+1),(i-1,j+1),(i-1,j+2),(i-1,j+3)没车子 那么f[i-1][j+1]可达
若f[i][j]可达 且当前(i,j+1),(i+1,j+1),(i+1,j+2),(i+1,j+3)没车子 那么f[i+1][j+1]可达
处理一下最后看f[0][n],f[1][n],f[2][n]能否可达即可

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

typedef long long LL;

int T,n,m;
char s[3][500];
bool dp[3][500],ans;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        scanf("%s",s[0]);
        scanf("%s",s[1]);
        scanf("%s",s[2]);
        for (int i=n;i<=400;++i) s[0][i]=s[1][i]=s[2][i]='.';
        memset(dp,false,sizeof(dp));
        if (s[0][0]=='s') dp[0][0]=true;
        if (s[1][0]=='s') dp[1][0]=true;
        if (s[2][0]=='s') dp[2][0]=true;
        for (int j=0;j<n;++j)
            for (int i=0;i<3;++i)
            {
                if (!dp[i][j]) continue;
                //zou dao i j+1
                //j s
                if (s[i][2*j+j+1]!='.') continue;
                if ((s[i][2*j+j+1]=='.')&&(s[i][2*j+j+2]=='.')&&(s[i][2*j+j+3]=='.')) dp[i][j+1]=true;
                if (i>0)
                    if ((s[i-1][2*j+j+1]=='.')&&(s[i-1][2*j+j+2]=='.')&&(s[i-1][2*j+j+3]=='.')) dp[i-1][j+1]=true;
                if (i<2)
                    if ((s[i+1][2*j+j+1]=='.')&&(s[i+1][2*j+j+2]=='.')&&(s[i+1][2*j+j+3]=='.')) dp[i+1][j+1]=true;
            }
        ans=false;
        if (dp[0][n-1]) ans=true;
        if (dp[1][n-1]) ans=true;
        if (dp[2][n-1]) ans=true;
        if (ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
} 

C:Alice, Bob, Oranges and Apples

题意:

你有两个二元组(x1,y1),(x2,y2),每次你可以选择两种操作:
A:(x1,y1),(x2,y2)—>(x1,y1),(x1+x2,y1+y2)
B:(x1,y1),(x2,y2)—>(x1+x2,y1+y2),(x2,y2)
初始为(1,0)和(0,1)现在要求给出一个操作序列 使得达到最终态:x1+x2=n y1+y2=m
(n,m<=1e18)

题解:

很有趣的一道题 首先先来看无解的情况
若gcd(n,m)!=1 则一定无解

我们接下来看有解的情况

考虑一个2$\times$2的矩阵
$((x1,x2),(y1,y2))$
考虑B操作
$((x1,x2),(y1,y2)) \times ((1,0),(1,1)) = ((x1+x2,x2),(y1+y2,y2))$
我们令B=((1,0),(1,1))
考虑A操作
$((x1,x2),(y1,y2)) \times ((1,1),(0,1)) = ((x1,x1+x2),(y1,y1+y2))$
我们令A=((1,1),(0,1))
那么考虑一个函数F
$F(((x1,x2),(y1,y2))) = (y1+y2)/(x1+x2)$

那么考虑一个状态S $F(BS)=(x1+x2+y1+y2)/(x1+x2)=F(s)+1$
所以若$F(BS)=m/n$ $F(s)=(m-n)/n$
所以若$F(AS)=m/n$ $F(s)=m/(n-m)$
这样我们就可以知道对于任意时刻:
-若m>n 那么第一步肯定是B 状态变为(n,m-n)
-若n>m 那么第一部肯定是A 状态变为(n-m,m)

//Latex的矩阵太难打啦!原谅我这个公式写的这么low吧。。用笔写一下就好啦!

这样问题就变成了类似于求GCD得辗转相除 问题就得到完满解决啦

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <vector>

using namespace std;

typedef long long LL;

LL n,m;
int main()
{
    scanf("%I64d%I64d",&n,&m);
    if (__gcd(n,m)!=1)
    {
        printf("Impossible\n");
        return 0;
    }
    while (n!=m)
    {
        if (n>m)
        {
            printf("%I64dA",(n-1)/m);
            n-=(n-1)/m*m;
        }
        else
        {
            printf("%I64dB",(m-1)/n);
            m-=(m-1)/n*n;
        }
    }
    return 0;
}

//此问题在具体数学中出现过 见具体数学第121页


D:Lizard Era: Beginning

题意:

有N个任务(N<=25)需要去完成 你有三个伙伴A,B,C 第N个任务带A去A的好感度会增加A[I] B,C同理
每个任务必须恰好带两个伙伴去完成 求一个方案使得所有任务完成后A,B,C三人的好感度相同,若存在多解输出好感度最大的

题解:

看N<=25不难想到搜索 然而3^n依然太大
于是考虑折半搜索
3^(n/2)大概是1000000左右 可以接受
现在的问题就变成了合并前后状态(a1,b1,c1)与(a2,b2,c2)使得$a1+a2=b1+b2=c1+c2$
整理一下可以得到$a2-b2=b1-a1,a2-c2=c1-a1$
所以只需要满足上面这两个要求就可以满足合并后三人好感度相同的要求
不难想到于是问题变成前半部分直接搜索得到(a1,b1,c1)这样的三元组 将它映射到三元组(a1-b1,a1-c1,a1)
后半部分直接搜索得到(a2,b2,c2)三元组后 查找前半部分存在的三元组(b2-a2,c2-a2,x)中x的最大值
于是我们用个map存一下三元组(a1-b1,a1-c1)这样的状态对应的最大的a1即可
//一开始我没有搜索而是用$3^n$这样表示的状态 然而这样需要乘以10的分解复杂度就TLE了QAQ

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

typedef long long LL;

int n;
LL sum,ansx,ansy,ans=-1e18;
LL a[30],b[30],c[30];
LL dq,aa,bb,cc;
map<pair<LL,LL>,LL> mp;
map<pair<LL,LL>,LL> mp2;
struct Node
{
    LL x,y;
    friend bool operator > (Node a,Node b)
    {
        return a.x>b.x;
    }
}now;
LL f[30];
int nn;
void dfs(int x,LL aa,LL bb,LL cc,LL i)
{
    if (x==nn+1)
    {
        if (mp.count(make_pair(aa-bb,aa-cc))==0)
        {
            mp[make_pair(aa-bb,aa-cc)]=aa;
            mp2[make_pair(aa-bb,aa-cc)]=i;
        }
        else    
        if (mp[make_pair(aa-bb,aa-cc)]<aa) 
        {
            mp[make_pair(aa-bb,aa-cc)]=aa;
            mp2[make_pair(aa-bb,aa-cc)]=i;
        }
        return;
    }
    dfs(x+1,aa+a[x],bb+b[x],cc,i*3);
    dfs(x+1,aa,bb+b[x],cc+c[x],i*3+1);
    dfs(x+1,aa+a[x],bb,cc+c[x],i*3+2);
}
void Dfs(int x,LL aa,LL bb,LL cc,LL i)
{
    if (x==n+1)
    {
        if (mp.count(make_pair(bb-aa,cc-aa))==0) return;
        dq=aa+mp[make_pair(bb-aa,cc-aa)];
        if (dq>ans)
        {
            ans=dq;
            ansx=mp2[make_pair(bb-aa,cc-aa)];
            ansy=i;
        }
        return;
    }
    Dfs(x+1,aa+a[x],bb+b[x],cc,i*3);
    Dfs(x+1,aa,bb+b[x],cc+c[x],i*3+1);
    Dfs(x+1,aa+a[x],bb,cc+c[x],i*3+2);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
    nn=n/2;
    //0:12   1:23  2:13
    dfs(1,0,0,0,0);
    Dfs(nn+1,0,0,0,0);
    if (ans==-1e18) printf("Impossible\n");
    else
    {
        dq=ansx;
        for (int j=nn;j>=1;--j)
        {
            f[j]=dq%3;
            dq/=3;
        }
        dq=ansy;
        for (int j=n;j>=nn+1;--j)
        {
            f[j]=dq%3;
            dq/=3;

        }
        for (int j=1;j<=n;++j)
        {
            if (f[j]==0) cout<<"LM"<<endl;
            if (f[j]==1) cout<<"MW"<<endl;
            if (f[j]==2) cout<<"LW"<<endl;
        }
    }
    return 0;
}

目前自己存在的问题:

  • 题目能想出来的变多了 但是反应还是慢 像CF TC这样的比赛总会出现最后想出来写不完的情况 区域赛就会出现罚时太多或者写不完的情况
  • 写的还是不够准 很多时候调试时间过长 平时还好在区域赛会出现占用机时过长的情况(现在我们训练经常是我在写旁边ckg检查,这样消耗了两个人的资源很不划算)
  • 在有时间压力的情况下 心理状态极其不稳定 出的错也就更多

解决方案

  • 继续做CF DIV1 C 和 TC 500
  • 做一些代码量题 增加读代码能力
  • 做一些限时训练 若没完成要对自己有惩罚

暂时先这样吧

一直想弄一个blog 在这里总算是暂时完工了

我在这里大概会发一些题解与自己的总结&计划

马上就要开始Regional了 要好好努力了啊

希望这里可以一直保持更新~