ABC 275 ABCD ( dfs / 递推递归+记忆化搜索)

https://atcoder.jp/contests/abc275/tasks
A - Find Takahashi

题目大意：

求数组最大值的数字下标。

Sample Input 1 
3
50 80 70
Sample Output 1 
2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL maxn=0,idx=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]>maxn) maxn=a[i],idx=i;
        }
        cout<<idx<<endl;
    }
    return 0;
}

B - ABC-DEF

题目大意：

给定ABCDEF，求 (A×B×C)−(D×E×F)%998244353。

Sample Input 1  
2 3 5 1 2 4
Sample Output 1 
22

注意不要%成负的就行，也就是说前面的那个数字必须要+mod，这样才能保证-了之后还是个正数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
const LL mod=998244353;
LL aa[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL a,b,c,d,e,f;
        cin>>a>>b>>c>>d>>e>>f;
        LL sum1=(LL)(a%mod)*(b%mod)%mod*(c%mod)%mod;
        LL sum2=(LL)(d%mod)*(e%mod)%mod*(f%mod)%mod;
        LL ans=(sum1+mod-sum2)%mod;
        //cout<<sum1<<" "<<sum2<<" "<<ans<<endl;
        cout<<ans<<endl;
    }
    return 0;
}

C - Counting Squares

题目大意：

给定一个9*9的字符矩阵，让我们求出正方形（四个角都是由#构成的）的个数。

Sample Input 1 
##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........
Sample Output 1 
2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
PII f[N];
LL sum=0,maxn=0;
char a[M][M];
map<string,LL> mp;
bool check(LL i,LL j,LL xx,LL yy)
{
    if((i-yy)>=1&&(i-yy)<=9&&(j+xx)>=1&&(j+xx)<=9&&(i-yy-xx)>=1&&(i-yy-xx)<=9&&(j+xx-yy)>=1&&(j+xx-yy)<=9)
        return true;
    else return false;
}
bool cmp(PII p,PII q)
{
    if(p.first!=q.first) return p.first<q.first;
    else p.second<q.second;
}
void dfs(LL x,LL y)
{
    for(LL i=x+1;i<=9;i++)
    {
        for(LL j=1;j<=9;j++)
        {
            if(a[i][j]=='#')
            {
                LL xx=i-x,yy=j-y;
                //cout<<xx<<" "<<yy<<" "<<x<<" "<<y<<" "<<i<<" "<<j<<" "<<i-yy<<" "<<j+xx<<" "<<i-yy-xx<<" "<<j+xx-yy<<endl;
                if(check(i,j,xx,yy)&&a[i-yy][j+xx]=='#'&&a[i-yy-xx][j+xx-yy]=='#')
                {
                    f[1]={x,y};
                    f[2]={i,j};
                    f[3]={i-yy,j+xx};
                    f[4]={i-yy-xx,j+xx-yy};
                    sort(f+1,f+1+4,cmp);
                    string c;
                    for(int i=1;i<=4;i++)
                    {
                        //cout<<f[i].first<<" "<<f[i].second<<endl;
                        c+=to_string(f[i].first)+to_string(f[i].second);
                    }
                    //cout<<c<<endl;
                    if(!mp[c])
                    {
                        mp[c]++;
                        sum++;
                    }
                }
            }
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        mp.clear();
        sum=0,maxn=0;
        for(LL i=1;i<=9;i++)
        {
            for(LL j=1;j<=9;j++)
            {
                cin>>a[i][j];
            }
        }
        for(LL i=1;i<=9;i++)
        {
            for(LL j=1;j<=9;j++)
            {
                if(a[i][j]=='#')
                {
                    dfs(i,j);
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

D - Yet Another Recursive Function

题目大意：

f(0)=1.
f(k)=f(⌊k/2⌋)+f(⌊k/3⌋).

给定我们一个n，问我们f(n)是多少？

Sample Input 3 
100
Sample Output 3 
55

• 所以对于状态x，只需要考虑除以了几次2，几次3
  然后很显然2不会超过64次 3也不会
  所以状态数不会超过64*64
  所以是不会爆LL滴

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL n,sum=0;
map<LL,LL> mp;
LL dfs(LL x)
{
    if(x==0) return 1;//递归终点
    //如果已经被标记过，直接返回
    //如果没有被标记过的话，在标记的同时往下搜索
    if(mp[x]) return mp[x];
    else return mp[x]=dfs(x/2)+dfs(x/3);
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n;
        cout<<dfs(n)<<endl;
    }
    return 0;
}