寒假学习计划

比赛链接

牛客

[A] Convolution

题意

给出一个整数序列,求\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}},答案对998244353取模

题解

2^{xy}=\sqrt{2}^{(x+y)^2-x^2-y^2}

根据上面的式子形式,做NTT

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <complex>
#include <algorithm>

#define IL inline
#define LL long long
#define ULL unsigned LL
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;

#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FD(i,l,r) for(int i=(l);i<=(r);++i)

#define MIN(a, b) ((a)<(b)?(a):(b))
#define MAX(a, b) ((a)>(b)?(a):(b))

template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10) 
// 【注意】如果PRT里面不是UPRT<unsigned long long>(-(ULL)_)而是直接UPRT(-_)则会出问题。比如INT_MIN和LLONG_MIN就打不出来。
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
#define CON constexpr
#define SW(a,b) ({auto _t=a; a=b; b=_t;})

CON LL G(3), MOD(998244353), S2(116195171), S2I(557219762);
CON LL MN(1e6+7);

template <typename T>
T QP(T __a, T __b)
{
    T __ret = 1;
    while (__b)
    {
        if (__b&1)
            __ret = (__ret*__a)%MOD;
        __a *= __a,
        __a %= MOD,
        __b >>= 1;
    }
    return __ret;
}

int re[MN];
void pre(int n)     // 【千万不要忘记!】
{
    int bn = 0;
    while ((1<<bn)<n) ++bn;
    F(i, 0, n)
        re[i] = (re[i>>1]>>1) | ((i&1)<<(bn-1));
}
void ntt(LL *a, int n, int sg) // sg=1:正, sg=-1:逆
{
    F(i, 0, n) if (i < re[i]) SW(a[i], a[re[i]]);
    for (int m=1; m<n; m<<=1)
    {
        LL g = QP(G, (MOD-1) / (m<<1));
        for (int i=0; i<n; i+=m<<1)
        {
            LL t = 1;
            for (int j=0; j<m; ++j, t=t*g%MOD)
            {
                LL x = a[i+j], y = t*a[i+j+m]%MOD;
                a[i+j] = (x+y) % MOD, a[i+j+m] = (x-y+MOD) % MOD;
            }
        }
    }
    if (sg<0)
    {
        LL nn = QP((LL)n, MOD-2);
        std::reverse(a+1, a+n);
        F(i, 0, n)
            (a[i] *= nn) %= MOD;
    }
}


LL a[MN], c[MN];


int main()
{
    _IO
    get(n)

    int mx = 0, x;
    F(i, 0, n)
    {
        sc(x)
        mx = MAX(mx, x);
        (a[x] += QP(S2I, (LL)x*x)) %= MOD;
    }

    mx = mx * 2 + 1;
    int len = 1;
    while (len <= mx) len <<= 1;

    pre(len);  // 【千万不要忘记!】
    ntt(a, len, 1);
    F(i, 0, len)
        c[i] = a[i] * a[i] % MOD;
    ntt(c, len, -1);

    LL ans = 0;
    F(i, 0, len)
        (ans += c[i] * QP(S2, (LL)i*i)) %= MOD;
    PL(ans);

#ifdef _KEVIN
    system("pause");
#endif

    return 0;
}

[C] 酒馆战棋

题意

题目背景:酒馆战棋

对面随从身材全为无限大且不会攻击,我方随从身材为1-1,只有普通和剧毒两种,从左至右依次攻击一轮.

给出对面普通,圣盾,嘲讽,圣盾嘲讽的随从个数,我方带剧毒的随从的位置,求最多最少分别能消灭对方多少随从.

题解

完美团情况:普通破圣盾,剧毒撞普通

辣鸡团情况:剧毒撞圣盾,普通撞普通(是我本人下棋情况了)

然后贪心即可

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;

int T,n,a,b,c,d;
char S[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Work(){
    register int i=0,x=0,A=a,B=b,C=c,D=d,Ans=0;
    for (i=0;i<n;i++){
        x=S[i]-48;
        if (!x){
            if (D)  {D--,C++;   continue;}
            if (C)  continue;
            if (B)  B--,A++;
            continue;
        }
        if (C)  {C--,Ans++; continue;}
        if (D)  {D--,C++;   continue;}
        if (A)  {A--,Ans++; continue;}
        if (B)  B--,A++;
    }
    printf("%d ",Ans);
    Ans=0;  A=a;    B=b;    C=c;    D=d;
    for (i=0;i<n;i++){
        x=S[i]-48;
        if (!x){
            if (C)  continue;
            if (D)  {C++,D--;   continue;}
            if (A)  continue;
            if (B)  {B--,A++;   continue;}
            continue;
        }
        if (D)  {D--,C++;   continue;}
        if (C)  {Ans++,C--; continue;}
        if (B)  {B--,A++;   continue;}
        if (A)  {A--,Ans++; continue;}
    }
    printf("%d\n",Ans);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
        scanf("%s",&S);
        Work();
    }
    return 0;
}

[F] 图与三角形

题意

给出一个完全图,每条边为黑白两种颜色之一,求能构成多少种同色三角形

题解

不合法的三角形一定有一个点连出的两条边颜色不同.

对于每个点,统计出连出了多少白边,多少黑边,然后把不合法的方案数减去即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <queue>
using namespace std;

long long int n, A, B, C, P, D;
long long int ans = 0, low = 0;
int map[10005][10005];

int main(){
    cin >> n;
    cin >> A >> B >> C >> P >> D;
    for (int i = 1; i < n; i++)
        for (int j = i+1; j <= n; j++)
            if ((A*(i+j)*(i+j)+B*(i-j)*(i-j)+C) % P > D) map[i][j] = map[j][i] = 1;
            else map[i][j] = map[j][i] = 0;
    ans = n * (n-1) * (n-2) / 6;
    for (int i = 1; i <= n; i++) {
        long long int num1 = 0, num0 = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (map[i][j] == 1) num1++;
            if (map[i][j] == 0) num0++;
        }
        low += num1 * num0;
    }
    ans -= low / 2;
    cout << ans << endl;
    return 0;
}

[G] 单调栈

题意

有一个1-n的排列,第i位记为a_{i}.定义f(i)为[1,i-1]中a_{i}的前驱对应的f值加1.

现在给出了一个残缺的f序列,要求写出字典序最小的a序列.

题解

贪心.

整个序列开头的f肯定是1,然后统计一下一共有多少个1,假设有k个,则把k,k-1,...,1填充到这些位置上.把第一位去掉,把所有位置的f值减去1,便得到了一个新的序列.重复以上过程不断填充.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;

int T,i,j,s,n;
int a[N],f[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline void Work(int x,int p){
    register int i=0,t=0,s=0;
    if (x>n)    return;
    if (a[x])   {Work(x+1,p);   return;}
    f[x]=1;
    for (i=x;i<=n;i++)  s+=(f[i]==1);
    t=p+s;
    for (i=x;i<=n;i++)
        if (f[i]==1)    a[i]=p+(--s);
    for (i=x;i<=n;i++)  f[i]--;
    Work(x+1,t);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   memset(f,0,sizeof(f));
        for (i=1;i<=n;i++)  f[i]=read();
        memset(a,0,sizeof(a));
        Work(1,1);
        for (i=1;i<n;i++)   printf("%d ",a[i]);
        printf("%d\n",a[n]);
    }
    return 0;
}

[I] 变大!

题意

给出一个序列a,每一次可以对某个位置执行一次操作,假设选择了第i位,则a_{i}=a_{i-1}=a_{i+1}=Max(a_{i},a_{i+1},a_{i+2})

现在进行了k(1\leq k \leq n)次操作,求序列之和的最大值是多少.对于所有的k,都要求出答案.

题解

假设有一段长度为l的序列,根据上面的操作的定义,不难证明,只需要\frac{l}{2}次就可以把这个序列的每一位都变成原序列中的最大值.

定义f[i][j]表示前i位执行了j次操作所能够达到的最大值.执行了一定次数的操作后,序列会变成很多"小块",每一块的值相同.于是可以根据背包的思想进行转移.转移方程为

f[i][k+l]=Max(f[i][k+l],f[j][k]+Max(a_{j+1}^{i})*(i-j))

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;

int T,i,j,k,n,l,Ans,s;
int a[N],f[N][N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();
        for (i=1;i<=n;i++)  a[i]=read();
        memset(f,0,sizeof(f));
        for (i=1;i<=n;i++){
            s=a[i];
            for (j=i-1;j>=0;j--){
                l=(i-j)/2;
                for (k=0;k+l<=n;k++)
                    f[i][k+l]=Max(f[i][k+l],f[j][k]+(i-j)*s);
                s=Max(s,a[j]);
            }
        }
        for (i=1;i<n;i++)   printf("%d ",f[n][i]);
        printf("%d\n",f[n][n]);
    }
    return 0;
}

[K] 最大权值排列

题意

对于一个长度为n的序列A,定义其权值f(A)

f(A)=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\sum_{k=i}^{j}A_{k}}{j-i+1}

现在给出了n,要求给出一个1-n的排列P,使得f(P)尽可能地大.给出字典序最小的那个.

题解

找规律后不难发现,把较大的数尽量往中间放就行了.

代码

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

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i += 2) printf("%d ", i);
    if (n % 2) for (int i = n - 1; i >= 2; i -= 2) printf("%d ", i);
    else for (int i = n; i >= 2; i -= 2) printf("%d ", i);
    return 0;
}

[L] 你吓到我的马了.jpg

题意

给出一个棋盘,棋盘上有一些障碍.棋盘上还有一个中国象棋中的马(也就是说可以被蹩马腿).现在要求求出这个马跳到棋盘上每一个地方分别最少需要几步.障碍不能通过.

题解

BFS

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <queue>
using namespace std;

int n, m, ans[105][105], map[105][105], stx, sty;
char s[105];

queue <int> l;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        for (int j = 0; j < m; j++) {
            if (s[j] == 'M') { map[i][j+1] = 0; stx = i; sty = j+1; }
            if (s[j] == 'X') { map[i][j+1] = -1; }
            if (s[j] == '.') { map[i][j+1] = 1; }
        }
    }
    for (int i = 1; i <= n; i++) map[i][0] = map[i][m+1] = -1;
    for (int i = 1; i <= m; i++) map[0][i] = map[n+1][i] = -1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ans[i][j] = 99999;
    ans[stx][sty] = 0;
    l.push(stx * 1000 + sty);
    while(!l.empty()) {
        int a = l.front();
        int x = a/1000, y = a%1000;
        //printf("%d %d\n", x, y);
        //int k; scanf("%d", &k);
        l.pop();
        if (x > 2) if (map[x-1][y] != -1) {
            if (y > 1) if (map[x-2][y-1] == 1 && ans[x-2][y-1] > ans[x][y] + 1) {
                ans[x-2][y-1] = ans[x][y] + 1;
                int aimx = x - 2, aimy = y - 1;
                l.push(aimx * 1000 + aimy);
            }
            if (y < m) if (map[x-2][y+1] == 1 && ans[x-2][y+1] > ans[x][y] + 1) {
                ans[x-2][y+1] = ans[x][y] + 1;
                int aimx = x - 2, aimy = y + 1;
                l.push(aimx * 1000 + aimy);
            }
        }
        if (x > 1) {
            if (y > 2) if (map[x][y-1] != -1) if (map[x-1][y-2] == 1 && ans[x-1][y-2] > ans[x][y] + 1) {
                ans[x-1][y-2] = ans[x][y] + 1;
                int aimx = x - 1, aimy = y - 2;
                l.push(aimx * 1000 + aimy);
            }
            if (y < m-1) if (map[x][y+1] != -1) if (map[x-1][y+2] == 1 && ans[x-1][y+2] > ans[x][y] + 1) {
                ans[x-1][y+2] = ans[x][y] + 1;
                int aimx = x - 1, aimy = y + 2;
                l.push(aimx * 1000 + aimy);
            }
        }
        if (x < n) {
            if (y > 2) if (map[x][y-1] != -1) if (map[x+1][y-2] == 1 && ans[x+1][y-2] > ans[x][y] + 1) {
                ans[x+1][y-2] = ans[x][y] + 1;
                int aimx = x + 1, aimy = y - 2;
                l.push(aimx * 1000 + aimy);
            }
            if (y < m-1) if (map[x][y+1] != -1) if (map[x+1][y+2] == 1 && ans[x+1][y+2] > ans[x][y] + 1) {
                ans[x+1][y+2] = ans[x][y] + 1;
                int aimx = x + 1, aimy = y + 2;
                l.push(aimx * 1000 + aimy);
            }
        }
        if (x < n - 1) if (map[x+1][y] != -1) {
            if (y > 1) if (map[x+2][y-1] == 1 && ans[x+2][y-1] > ans[x][y] + 1) {
                ans[x+2][y-1] = ans[x][y] + 1;
                int aimx = x + 2, aimy = y - 1;
                l.push(aimx * 1000 + aimy);
            }
            if (y < m) if (map[x+2][y+1] == 1 && ans[x+2][y+1] > ans[x][y] + 1) {
                ans[x+2][y+1] = ans[x][y] + 1;
                int aimx = x + 2, aimy = y + 1;
                l.push(aimx * 1000 + aimy);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            if (ans[i][j] != 99999) printf("%d ", ans[i][j]);
            else printf("-1 ");
        cout << endl;
    }
    return 0;
}

[M] 自闭

题意

一些人在刷一些题,不同的通过情况会产生不同的自闭点数,求最后每个人的自闭点数.

题解

模拟

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;

int i,j,n,m,w;
int Ans[N],f[N][N],v[N],ed[N],t[N],s[N],k[N];

vector <int> Q[N][N];

struct Data{
    int x,y,r;
}a[N];

inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Ready(){
    register int i=0,j=0,sum=0;
    for (i=1;i<=w;i++){
        if (a[i].r==1)  f[a[i].x][a[i].y]=1;
        v[a[i].x]=1;
    }
    for (i=1;i<=n;i++)
        if (!v[i])  Ans[i]=998244353,ed[i]=1;
    //  1
    for (i=1;i<=n;i++){
        if (ed[i])  continue;
        for (j=1;j<=m;j++)
            if (f[i][j])    goto END;
        Ans[i]=1000000; ed[i]=1;
        END:;
    }   //  2
    for (i=1;i<=n;i++){
        sum=0;
        if (ed[i])  continue;
        for (j=1;j<=m;j++)  sum+=f[i][j];
        if (sum==m) Ans[i]=0,ed[i]=1;
    }   //  3
}

inline void Work(){
    register int i=0,j=0,x=0,y=0;
    for (i=1;i<=w;i++)
        if (a[i].r) t[a[i].y]=1;
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)
            s[j]+=f[i][j];
    for (j=1;j<=m;j++){
        if (!t[j])  continue;
        for (i=1;i<=n;i++){
            if (ed[i])  continue;
            if (!f[i][j])   Ans[i]+=20;
            if (!f[i][j] && s[j]>=(n/2))    Ans[i]+=10;
        }
    }   //  4&5

    for (i=1;i<=w;i++){
        if (ed[a[i].x]) continue;
        Q[a[i].x][a[i].y].push_back(a[i].r);
    }

    for (i=1;i<=n;i++){
        if (ed[i])  continue;
        memset(k,0,sizeof(k));
        for (j=1;j<=m;j++){
            x=0;
            for (auto p : Q[i][j]){
                if (p)  {
                    k[j]=Max(k[j],x);   x=0;
                }   else x++;
            }
            k[j]=Max(k[j],x);
        }
        for (j=1;j<=m;j++){
            Ans[i]+=k[j]*k[j];
            if (!f[i][j])   Ans[i]+=k[j]*k[j];
        }
    }   //  6&7
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();   w=read();
    for (i=1;i<=w;i++){
        a[i].x=read();  a[i].y=read();  a[i].r=read();
    }
    Ready();    Work();
    for (i=1;i<=n;i++)  printf("%d\n",Ans[i]);
    return 0;
}

[N] 合并!

题意

有一行长度为n石子堆,第i堆有一个重量a_{i}.每一次可以把相邻两堆石子合并,并得到a_{i}a_{i+1}的分数,新的石子堆的重量为a_{i}+a_{i+1}.求最后合并成一堆后,能拿到的最大分数是多少.

题解

推导后不难发现,答案是每一堆石子重量两两之积的总和.

代码

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

int s[2005], n;

long long int ans = 0;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        for (int j = 1; j < i; j++) ans += s[i] * s[j];
    }
    cout << ans << endl;
    return 0;
}
说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...