2019.10.18 解题报告

2024-01-23 19:54:22

期望得分 : 100+30+30

实际得分：0+0+0

让我们看一下yxj这个沙雕犯了什么错误

2019.10.18 解题报告

 2019.10.18 解题报告

 很好！

nmd，要不是为了不能叫我xf 守寡，我特么（&*）……！&）%￥~R%！

 

2019.10.18 解题报告

 

 

 

T1：不怕噩梦

蚊子最近经常做噩梦，然后就会被吓醒。这可不好。。疯子一直在发愁，然后突然有一天，他发现蚊子其实就是害怕某些事。如果那些事出现在她的梦里，就会害怕。我们可以假定那个害怕的事其实是一个字符串。而她做的梦其实也是一个字符串。

她可以一个晚上一直做梦，所以梦这个字符串会很长，如果其中包含了她所害怕的事情，那么她这天晚上就会害怕。当然一个害怕的事也可能在这天晚上被她梦到很多遍，当然每个晚上也可能有很多种害怕的事都被梦到。

每个害怕的事都有一定的权值。而这天晚上如果梦到了某件事，那么这件事所产生的黑暗效果等于这件事的权值乘以这个害怕的事在梦字符串里的开始位置。如果同样的事梦到了很多遍，那么就重复上面的操作很多遍。当天晚上的黑暗效果总和等于当天所有害怕的事产生的黑暗效果累加到一起。现在疯子想知道蚊子这些天来噩梦的黑暗效果总和是多少。

INPUT (dream.in):

  第1行两个整数N，M代表一共有N天梦和M个害怕的事。

  第2行到第M+1行。每行一个字符串ti,代表第I个害怕的事

  第M+2行到第2M+2行。每行一个整数ai.代表第I个害怕的事权值

  第2M+3行到第N+2M+3行。每行一个字符串si，代表第I天的梦。

OUTPUT(dream.out)

  SUM

  SUM=N天里黑暗效果的总和。

  我们保证每天的黑暗效果都小于maxlongint;

输入样例

  2 2

  abc

  def

  1

  2

  abcdef

  defabc

输出样例

   15

友情提示：

1*1+2*4+1*4+2*1=15

对于数据的把握和时间复杂度的估计是成败的关键。

如果出现一个梦是:ab

而害怕的事有a,b,ab，那么a,b,ab都需要参与计算..

对于30%的数据

N，M<=50

对于所有的数据

  N<=200.M<=200. length(si)<=200.length(ti)<=200.ai<=10.

Solution:

KMP算法的应用，直接求然后跑就行了

Code：

考场代码(已修正沙雕错误）

//kmp
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 250;
int n, m, nxt[N][N], k;
char ch[N];
long long sum;
struct node {
    char ch[N];
    int w, len;
}af[N];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
int main() {
    freopen("dream.in", "r", stdin);
    freopen("dream.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= m; i++) {//第i个害怕的字符串 
        cin >> af[i].ch + 1;
        int len = strlen(af[i].ch + 1);
        af[i].len = len;
        k = 0;
        for(int j = 2; j <= len; j++) {//枚举这个字符串的位置 
            while(k && af[i].ch[j] != af[i].ch[k + 1]) k = nxt[i][k];
            if(af[i].ch[j] == af[i].ch[k + 1]) k++;
            nxt[i][j] = k;
        }
        /*for(int j = 1; j <= len; j++)
            printf("%d ", nxt[i][j]);
        printf("\n");*/
    }
    for(int i = 1; i <= m; i++) af[i].w = read();
    for(int i = 1; i <= n; i++) {//第i个梦 
        cin >> ch + 1;
        int len = strlen(ch + 1);
        for(int j = 1; j <= m; j++) {//第j个害怕的事 
            k = 0;
            for(int o = 1; o <= len; o++) {//梦的位置 
                while(k && ch[o] != af[j].ch[k + 1]) k = nxt[j][k];
                if(ch[o] == af[j].ch[k + 1]) k++;
                if(k == af[j].len) {sum += af[j].w * (o - af[j].len + 1);k = nxt[j][k];/*cout << o - af[j].len + 1 << endl;*/}
            }
        }
    }
    cout << sum << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

T2：那个窗口：

故事的起源不加赘述，那23个路口。

单刀直入，我直接说题的意思。

蚊子和疯子在做一件事，就是他们要在茫茫的大街上找一个出发点，然后从出发点开始，经过上下左右23次拐弯，到达一个他们也不知道的地方。

老城的街道排列的十分有规律，于是疯子和蚊子把老城的街道排布画在了一张地图上。地图上每一个点代表一个地方，而这个地方有一定的憧憬值，疯子希望可以带蚊子走过的二十三个路口的憧憬值总和是所有方案中最大的。

现在我们读入一个矩阵，如果此点为0，则这个点为起点，如果此点为-1，则这个点为障碍点，否则这个数代表憧憬值。注意起点和障碍点是没有憧憬值的，起点只有开始的时候可以达到，不可以再回来。而障碍点根本就不可以走过。这样一来，请你选择合适的路线，使走完23个路口后得到最大的憧憬值，有憧憬值的点可以重复进出，每次可以选择四个方向，上下左右。起点为第0个路口

输入格式:

  第1行两个整数 n,m （茫茫大街的长和宽）

  第2行到第m+1行，每行n个整数 Aij（第I行第j个地点的憧憬值）

输出格式

  一个整数sum （可以得到的最大憧憬值）

INPUT

  4 4

  1 1 1 1

  1 1 0 1

  1 1 1 1

  1 1 1 1

OUTPUT

  23

对于30%的数据，n,m<=50

对于全部数据 n,m<=300

0<n,m<300，每个点的憧憬值可以用longint表示。

Solution：

DP题。因为每个点都可以重复进入，所以我们可以得到方程

F[k][I][j]=max(f[k-1][i-1][j],f[k-1][I+1][j],f[k-1][I][j-1],f[k-1][I][j+1])+a[I][j];

因为有障碍点和出发点，所以我们要做出一定的预处理。

Code:

需要注意~表示不等于-1返回真否则返回假

听说这个地方已经有好多人去问ak的cyh大佬了当然也包括我

//设f[k][i][j]表示前k步走到i j位置的最
//~表示不等于-1返回真否则返回假 
#include <cstdio>
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
const int N = 305;
long long f[N][N][28], n, m, mp[N][N], ans = -0x3f3f3f3f3f;
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
} 
signed main() {
    freopen("corner.in", "r", stdin);
    freopen("corner.out", "w", stdout);
    memset(f, -0x3f, sizeof(f));
    m = read(), n = read();
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++) {
            mp[i][j] = read();
            if(!mp[i][j]) f[i][j][0] = 0;
        }
    for(int k = 1; k <= 23; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(mp[i][j] < 0) continue;
                if(i > 1 && ~mp[i - 1][j]) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + mp[i][j]);
                if(i < n && ~mp[i + 1][j]) f[i][j][k] = max(f[i][j][k], f[i + 1][j][k - 1] + mp[i][j]);
                if(j > 1 && ~mp[i][j - 1]) f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1] + mp[i][j]);
                if(j < m && ~mp[i][j + 1]) f[i][j][k] = max(f[i][j][k], f[i][j + 1][k - 1] + mp[i][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            ans = max(ans, f[i][j][23]);
    cout << ans << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

T3：我们的可可西里

转眼到了2008年的6月9日，盼望已久的高考结束了。我们踏上了向西的旅程（本来是想写西去之路，可是考虑不太妥当）。可可西里，多么诱人的名词，充满了奇幻的色彩和自然的淳朴。从可可西里徒步走回家的决定是在1年半前定下的，而现在，终于可以实现那个钩过手指的预定。我们的可可西里。。。

   在回家的路上，疯子和蚊子看到了许多可爱的藏羚羊，无意之中疯子和蚊子发现藏羚羊的居住地的分布也是有规律的，虽然疯子和蚊子早就听说藏羚羊是一种群体性很强又有超高IQ的动物，但是还是为它们的居住地分布规律感到惊叹。经过细心的观察，疯子和蚊子发现，如果假设一个藏羚羊群体有N只羊，就可以把它们的领地当做一个N*N的方阵，在这个方阵上第I列的第I 行都有一个圣地，它们不会居住在圣地，同时每行每列只能居住一只羚羊。于是他们很快算出一个有N只羊的藏羚羊群体的居住地分布方法数。

      

这是圣地的一种排列方法

　　　　　　　　2019.10.18 解题报告

 一个整数N 代表藏羚羊的个数 INPUT:

OUTPUT:

  一个整数sum代表方法数 

输入样例：

4

输出样例：

9

对于30%的数据，n<=10

对于全部数据 n<=1000

Solution：

出题人思路：

错排问题。

假设我们已经得到f[k-2],f[k-1].现在想求f[k].

1.K可以与从1在K -1 中任意一个棋子I 交换，这样固定了2个棋子，剩下K-2棋子的排列方法数为f[K-2].那么按照这种K和1到K-1中交换棋子可以得到的方案总数为(K-1)*f[K-2];

2.K可以放在1到K-1中的任何一个位置I，并且I 不放到K个位置上，其实这样就等效于f[K-1]种方法，所以这种策略的总和为(K-1)*f[K-1].

所以我们便得到了个递推公式f[K]:=(K-1)*(f[K-1]+f[K-2]);

当然数据范围需要应用到高精度。

推式子也很好推就是这么个东西那你还没推出来


lkx大佬的思路%%%：

f[1]=0,f[2]=1;f[3]=2
f[i]=i*f[i-1]
if(i%2)f[i]--;
else f[i]++;

Code:

艹，大佬各种高精度的板子也是没谁了

lbh大佬代码：

2019.10.18 解题报告
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cassert>
#define int64 long long
using namespace std;
const int B=1000000000;
const int L=9;
inline int intcmp(int a,int b)
{
    if(a>b)
        return 1;
    else
    if(a<b)
        return -1;
    else
        return 0;
}
inline int64 read()
{
   int64 s=0,w=1;
   char ch=getchar();
   while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
   while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct BigInt
{
    vector<int> a;
    BigInt() {}
    BigInt(int n)
    {
        while(n>0)
            a.push_back(n % B),n/=B;
    }
    BigInt(int64 n)
    {
        while(n>0)
            a.push_back(n%B),n/=B;
    }
    inline void clr0()
    {
        while(!a.empty()&&a.back()==0)
            a.pop_back();
    }
    inline BigInt &operator+=(const BigInt &rhs)
    {
        a.resize(max(a.size(),rhs.a.size()));
        int t=0;
        for(int i=0;i<(int)rhs.a.size();i++)
        {
            a[i]+=rhs.a[i]+t;
            t=a[i]>=B;
            a[i]-=B&(-t);
        }
        for(int i=(int)rhs.a.size();t!=0&&i<(int)a.size();i++)
        {
            a[i]+=t;
            t=a[i]>=B;
            a[i]-=B&(-t);
        }
        if(t!=0)
            a.push_back(t);
        return *this;
    }
    inline BigInt &operator-=(const BigInt &rhs)
    {
        a.resize(max(a.size(),rhs.a.size()));
        int t=0;
        for(int i=0;i<(int)rhs.a.size();i++)
        {
            a[i]-=rhs.a[i]+t;
            t=a[i]<0;
            a[i]+=B&(-t);
        }
        for(int i=(int)rhs.a.size();t!=0&&i<(int)a.size();i++)
        {
            a[i] -= t;
            t = a[i] < 0;
            a[i] += B & (-t);
        }
        clr0();
        return *this;
    }
    inline BigInt &operator*=(const BigInt &rhs)
    {
        int na = (int)a.size();
        a.resize(na + rhs.a.size());
        for (int i=na-1;i>=0;i--)
        {
            int ai=a[i];
            int64 t=0;
            a[i]=0;
            for(int j=0;j<(int)rhs.a.size();j++)
            {
                t+=a[i+j]+(int64)ai*rhs.a[j];
                a[i+j]=t%B;
                t/=B;
            }
            for(int j=(int)rhs.a.size();t!=0&&i+j<(int)a.size();j++)
            {
                t+=a[i+j];
                a[i+j]=t%B;
                t/=B;
            }
            assert(t==0);
        }
        clr0();
        return *this;
    }
    inline BigInt &operator/=(const BigInt &rhs)
    {
        return *this=div(rhs);
    }
    inline BigInt &operator%=(const BigInt &rhs)
    {
        return div(rhs),*this;
    }
    inline BigInt &shlb(int l=1)
    {
        if(a.empty())
            return *this;
        a.resize(a.size()+l);
        for(int i=(int)a.size()-1;i>=l;i--)
            a[i]=a[i-l];
        for(int i=0;i<l;i++)
            a[i]=0;
        return *this;
    }
    inline BigInt &shrb(int l=1)
    {
        for(int i=0;i<(int)a.size()-l;i++)
            a[i]=a[i+l];
        a.resize(max((int)a.size()-l,0));
        return *this;
    }
    inline int cmp(const BigInt &rhs) const {
        if (a.size() != rhs.a.size())
            return intcmp(a.size(),rhs.a.size());
        for(int i=(int)a.size()-1;i>=0;i--)
            if(a[i]!=rhs.a[i])
                return intcmp(a[i],rhs.a[i]);
        return 0;
    }
    inline BigInt div(const BigInt &rhs)
    {
        assert(!rhs.a.empty());
        if(rhs>*this)
            return 0;
        BigInt q, r;
        q.a.resize((int)a.size()-(int)rhs.a.size()+1);
        for(int i=(int)a.size()-1;i>(int)a.size()-(int)rhs.a.size();i--)
        {
            r.shlb();
            r+=a[i];
        }
        for(int i=(int)a.size()-(int)rhs.a.size();i>=0;i--)
        {
            r.shlb();
            r+=a[i];
            if(r.cmp(rhs)<0)
                q.a[i]=0;
            else
            {
                int le=0,ri=B;
                while(le!=ri)
                {
                    int mi=(le+ri)/2;
                    if((rhs*mi).cmp(r)<=0)
                        le=mi+1;
                    else
                        ri=mi;
                }
                q.a[i]=le-1;
                r-=rhs*q.a[i];
            }
        }
        q.clr0();
        *this=r;
        return q;
    }
    friend inline BigInt operator+(const BigInt &lhs,const BigInt &rhs)
    {
        BigInt res=lhs;
        return res+=rhs;
    }
    friend inline BigInt operator-(const BigInt &lhs,const BigInt &rhs)
    {
        BigInt res=lhs;
        return res-=rhs;
    }
    friend inline BigInt operator*(const BigInt &lhs,const BigInt &rhs)
    {
        BigInt res=lhs;
        return res*=rhs;
    }
    friend inline BigInt operator/(const BigInt &lhs,const BigInt &rhs)
    {
        BigInt res=lhs;
        return res.div(rhs);
    }
    friend inline BigInt operator%(const BigInt &lhs,const BigInt &rhs)
    {
        BigInt res=lhs;
        return res.div(rhs),res;
    }
    friend inline ostream &operator<<(ostream &out,const BigInt &rhs)
    {
        if(rhs.a.size()==0)
            out<<"0";
        else
        {
            out<<rhs.a.back();
            for (int i=(int)rhs.a.size()-2;i>=0;i--)
                out<<setfill('0')<<setw(L)<<rhs.a[i];
        }
        return out;
    }
    friend inline bool operator<(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)<0;
    }
    friend inline bool operator<=(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)<=0;
    }
    friend inline bool operator>(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)>0;
    }
    friend inline bool operator>=(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)>=0;
    }
    friend inline bool operator==(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)==0;
    }
    friend inline bool operator!=(const BigInt &lhs,const BigInt &rhs)
    {
        return lhs.cmp(rhs)!=0;
    }
};
inline BigInt BigInt_max(BigInt a,BigInt b)
{
    return a>b?a:b;
}
BigInt a[1010];
int main()
{
    freopen("keke.in","r",stdin);
    freopen("keke.out","w",stdout);
    int n=read();
    a[0]=0,a[1]=1,a[2]=2,a[3]=9;
    for(int i=4;i<n;i++)
    a[i]=(a[i-1]+a[i-2])*i;
    cout<<a[n-1];
    return 0;
}
lbh%%%

woc，是个什么玩意，当时高精不是这么学的啊！我还是太菜了

2019.10.18 解题报告
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
long long ans;
int n,l;
int f[1001][10001];
void suan(int b) {
    for(int i=1; i<=10000; i++)
        f[l][i]=f[l-1][i]*b;
    for(int i=1; i<=10005; i++)
        if(f[l][i]>=10) {
            f[l][i+1]+=f[l][i]/10;
            f[l][i]%=10;
        }
    return ;
}
int main() {
    freopen("keke.in","r",stdin);
    freopen("keke.out","w",stdout);
    int n;
    cin>>n;
    f[1][1]=0,f[2][1]=1,f[3][1]=2;
    for(l=4; l<=n; l++) {
        suan(l);
        if(l%2)f[l][1]--;
        else f[l][1]++;
    }
    for(int i=1; i<=10005; i++)
        if(f[n][i]>=10) {
            f[n][i+1]+=f[n][i]/10;
            f[n][i]%=10;
        }
    int t=10000;
    bool a=false;
    if(n==1) {
        cout<<0;
        fclose stdin;
        fclose stdout;
        return 0;
    }
    while(t) {
        if(f[n][t]==0&&!a) {
            t--;
            continue;
        } else {
            a=true;
            cout<<f[n][t];
        }
        t--;
    }
    fclose stdin;
    fclose stdout;
    return 0;
}
lkx%%%

谢谢收看， 祝身体健康！

上一篇：在mysql上需要大于20位的整数时该怎么办？


下一篇：C或C中的大整数