2021NowCoder寒假算法基础集训营6

机器人

image.png
20的20次方太大，要用到__int128

#include<bits/stdc++.h>
using namespace std;
struct node{
    __int128 a,b;
}t[30];
inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

bool cmp(node x,node y){
    return x.b+x.a*y.b<y.b+y.a*x.b;
}
int main(){
    __int128 n,x;
    n=read();
    x=read();
    for(int i=1;i<=n;i++){
        t[i].a=read();
        t[i].b=read();
    }
    sort(t+1,t+1+n,cmp);
    for(int i=1;i<=n;i++){
        x=t[i].a*x+t[i].b;
    }
    write(x);
    return 0;
}

组合数问题
先通过打表求出前几项
再利用oeis得出规律 https://oeis.org/A070775
找出公式

image.png
n/=4;
涉及到快速幂，逆元，因为n可能为奇数，存在相减情况，最后结果(ans%mod+mod)%mod;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
ll power(ll a,ll b){
    ll ans=1%mod;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans%mod;
}
int main(){
    ll n;
    cin>>n;
    n/=4;
    ll x=power(-4,n);
    ll y=power(16,n);
    ll x1=((x%mod)*((power(2,mod-2)%mod)%mod))%mod;
    ll y1=((y%mod)*((power(4,mod-2)%mod)%mod))%mod;
    ll res=(x1+y1)%mod;
    cout<<(res%mod+mod)%mod<<endl;
    
    return 0;
}

贪吃蛇
BFS板子

#include<bits/stdc++.h>
using namespace std;
char mp[500][500];
typedef struct node
{
    int x;
    int y;
    int s;//表示这是第几步可以走到
}KK;
int vis[500][500];//标记数组防止走重复
int Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main(){
    KK que[500];//创建队列
    int n,m;
    cin>>n>>m;
    int xs,ys,xe,ye;
    cin>>xs>>ys>>xe>>ye;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
        }
    }
    int head=0,tail=0;
    que[head].x=xs;
    que[head].y=ys;
    que[head].s=0;
    vis[xs][ys]=1;
    tail++;
    int flag=0;
    while(head<tail){
        for(int i=0;i<4;i++){
            int tx=que[head].x+Next[i][0];
            int ty=que[head].y+Next[i][1];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            if(mp[tx][ty]=='.'&&vis[tx][ty]==0)//如果可以走
            {
                //入队
                que[tail].x=tx;
                que[tail].y=ty;
                que[tail].s=que[head].s+1;//步数加一
                vis[tx][ty]=1;//标记已经走过
                tail++;//队尾后移
            }
            if(tx==xe&&ty==ye)//判断是否走到终点
            {
                flag=1;
                break;
            }
            
        }
        if(flag==1)
            break;
        head++;//扩展完毕的点出队
    }
    if(flag==1)
        cout<<que[tail-1].s*100<<endl;
    else 
        cout<<-1<<endl;
    return 0;
}

系数

image.png
题目最后都要
因为后一部分结果是零 image.png
所以因为n,m都比较大，所以可以用到算法
[(-1)^(2n-k) * lucas(2n,k,3)]%3
当k为奇数的时候要特殊处理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fac[10];
ll p=3;
void init(){
    fac[0]=1;
    for(ll i=1;i<p;i++)
        fac[i]=fac[i-1]*i%p; 
}
ll power(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll C(ll n,ll m){
    if(n<m)
        return 0;
    return fac[n]*power(fac[m]*fac[n-m],p-2,p)%p;
}
ll lucas(ll n,ll m){
    if(m==0)
        return 1;
    return (C(n%p,m%p)*lucas(n/p,m/p))%p;
}
int main(){
    init();
    ll t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        ll res=lucas(2*n,k);
        if(k&1) res = (3 - res) % 3;
        cout<<res<<endl; 
    }
  
    return 0;
}