个人空间 - AcWing

术

关注数

粉丝数

阅读量

6007

+关注发消息

离线：3天前

题解 AcWing 3187. 奇怪的数列

术
11天前

                #include <iostream>

using namespace std;
string s;
int n;
int cnt(int u,string str)
{
    u=u+1;
    int res=1;
    for(; u<str.size(); u++)
    {
        if(str[u]==str[u-1])
        {
            res++;
        }
        else
            break;
    }
    return res;
}
int main()
{

    cin>>s;
    cin>>n;
    while(n--)
    {
        string t;
        for(int i=0; i<s.size();)
        {
            int k=cnt(i,s);
            t+=(k+'0');
            t+=s[i];
            i+=k;
        }
        s=t;
    }
    cout<<s;
    //cout<<cnt(0,"1113");

    //cout << "Hello world!" << endl;
    return 0;
}


            

题解 AcWing 3182. 密文搜索

术
11天前

                #include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    map<string,int> mp;
    string str;
    string s;
    cin>>s;
    cin>>n;

    int res=0;
    while(n--){
        cin>>str;
        sort(str.begin(),str.end());
        mp[str]++;
    }

    for(int i=0;i<s.size()-7;i++){ //这里是7 ！！！！！！！！！
        string t=s.substr(i,8);//从i开始长度为8

        sort(t.begin(),t.end());
        res+=mp[t];
    }
    cout<<res;
    //cout << "Hello world!" << endl;
    return 0;
}


            

题解 AcWing 3179. 穿越雷区

术
11天前

                `#include <iostream>
#include <queue>
using namespace std;
const int N=105;
char a[N][N];
int xa,ya,xb,yb;
int dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0};
int n;
bool st[N][N];
struct Edge
{
    int x,y,w;
    Edge(int x,int y,int w)
    {
        this->x=x;
        this->y=y;
        this->w=w;
    }
};
int bfs()
{
    queue<Edge> q;
    q.push(Edge(xa,ya,0));
    st[xa][xb]=true;
    while(!q.empty())
    {
        Edge t=q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            int u=t.x+dx[i],v=t.y+dy[i];
            if(u<=0||u>n||v<=0||v>n)
                continue;
            if(st[u][v])
                continue;
            if(a[t.x][t.y]==a[u][v])
                continue;
            if(a[u][v]=='B') return t.w+1;

            st[u][v]=true;
            q.push(Edge(u,v,t.w+1));
        }
    }
    return -1;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='A')
                xa=i,ya=j;
            if(a[i][j]=='B')
                xb=i,yb=j;
        }
    cout<<bfs();
    //cout << "Hello world!" << endl;
    return 0;
}
`

            

题解 AcWing 3177. Fibonacci数列与黄金分割

术
11天前

                #include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n>20)
    {

        cout<<"0.61803399";
        return 0;
    }
    double res=1;
    for(int i=1;i<=n-1;i++){
        res=1/(res+1);
    }

    printf("%.8lf",res);
    //cout << "Hello world!" << endl;
    return 0;
}


            

题解 AcWing 2560. 矩阵计数

术
11天前

                1.搜索


#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> state;//行状态
int res;
int a[6];//二维数组
void dfs(int u) //第几行
{
    if(u>=n)
    {
        res++;
        return;
    }
    for(int i=0; i<state.size(); i++) //枚举每个状态
    {
        if(u>=2)//已有行数大于3个才判断
        {
            bool flag=true;
            for(int j=0; j<m; j++)
            {
                if(a[u-2]>>j&1&&a[u-1]>>j&1&&state[i]>>j&1)
                {
                    flag=false;
                    break;
                }
            }
            if(!flag) continue;
        }
        a[u]=state[i];
        dfs(u+1);
    }
}
int main()
{
    cin>>n>>m;
    //预处理每一行，将符合要求的行状态放进数组
    for(int i=0; i<1<<m; i++)
    {
        bool flag=true;;
        for(int j=0; j<m-2; j++)
        {
            if(i>>j&1&&i>>j+1&1&&i>>j+2&1)
            {
                flag=false;
                break;
            }
        }
        if(flag)
            state.push_back(i);
    }
    dfs(0);
    cout<<res;
    //cout << "Hello world!" << endl;
    return 0;
}



2.状态压缩dp  三维

f(i,j,k)表示已经将前i列摆好，第i列状态为j，第i-1列状态为k

状态转移
f(i,j,k)=sum(f(i-1,k,u))


#include <iostream>
#include <vector>
using namespace std;
const int N=35;
vector<int> state;
int n,m;
int f[N][N][N];//已经摆好前i列，第i列状态为j，第i-1列状态为k
int main()
{
    cin>>n>>m;
    for(int i=0; i<1<<n; i++) //预处理每一列
    {
        bool flag=true;
        for(int j=0; j<n-2; j++)
        {
            if(i>>j&1&&i>>j+1&1&&i>>j+2&1)
            {
                flag=false;
                break;
            }
        }
        if(flag)
            state.push_back(i);
    }
    //前2列，初始化为1，因为不会有xxx出现
    for(int i=0; i<state.size(); i++)
    {
        for(int j=0; j<state.size(); j++)
        {
            f[1][i][j]=1;
        }
    }
    //
    for(int i=2; i<m; i++)//从第3列开始，只有此时才会出现不符合条件的情况
    {
        for(int j=0; j<state.size(); j++)//第i列
        {
            for(int k=0; k<state.size(); k++)//i-1
            {
                for(int u=0; u<state.size(); u++)//i-2
                {
                    if(!(state[j]&state[k]&state[u]))
                        f[i][j][k]+=f[i-1][k][u];
                }
            }

        }
    }
    int res=0;
    for(int i=0; i<state.size(); i++)
    {
        for(int j=0; j<state.size(); j++)
        {
            res+=f[m-1][i][j];
        }
    }
    if(m==1) cout<<state.size();
    else
    cout<<res;
    return 0;
}


            

题解 AcWing 3176. 扫地机器人

术
12天前

                #include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int n,k;
int a[N];
int ans[N];
//区间大小为m,起点为l
int check(int m){
    int l=0;
     for(int i=1;i<=k;i++){
        if(a[i]-m<=l){//m大小的区间，是否可以全部清理
            if(a[i]<=l) l=a[i]+m-1;//若机器人在l范围内，则机器人向右最远的点为下一个l
            else l=a[i]+m-(a[i]-l);//若不在边界内，
        }
        else return false;
     }
     if(l>=n) return true;
     else return false;
}
int main()
{
    cin>>n>>k;
    int res=0;
    for(int i=1; i<=k; i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+k+1);
    //找符合条件的最小区间大小

    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(!check(mid)) l=mid+1;
        else r=mid;
    }
    cout<<2*(l-1);
    //cout << "Hello world!" << endl;
    return 0;
}


            

题解 AcWing 2548. 大胖子走迷宫

术
12天前

                #include <iostream>
#include <queue>
using namespace std;
const int N=305;
int n,k;
char g[N][N];
bool st[N][N];
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
int d[3]= {2,1,0};
struct Edge
{
    int x;
    int y;
    int time;
    Edge(int x,int y,int time)
    {
        this->x=x;
        this->y=y;
        this->time=time;
    }
};
//三维 bfs
int bfs()
{
    queue<Edge> q;
    //Edge e=Edge(3,3,0);
    q.push(Edge(3,3,0));
    st[3][3]=true;

    while(!q.empty())
    {
        //将原点加入队列，即静止不动

        Edge t=q.front();
        q.pop();
        if(t.time/k<2)
            q.push(Edge(t.x,t.y,t.time+1));

        for(int i=0; i<4; i++)
        {
            int a=t.x+dx[i];
            int b=t.y+dy[i];

            int fat=t.time/k>=2?0:d[t.time/k];//有多胖
            if(a-fat<=0||a+fat>n||b-fat<=0||b+fat>n)
                continue;//弱国超出迷宫界限
            if(st[a][b])
                continue;

            //判断所占区域是否有障碍物

            bool flag=false;
            for(int u=a-fat; u<=a+fat; u++)
            {
                for(int v=b-fat; v<=b+fat; v++)
                {
                    if(g[u][v]=='*')
                        flag=true;
                }
            }
            if(flag)
                continue;

            if(a==n-2&&b==n-2)
                return t.time+1;
            st[a][b]=true;
            //加入队列
            q.push(Edge(a,b,t.time+1));
        }
    }

}
int main()
{
    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        for(int j=0; j<s.size(); j++)
        {
            g[i+1][j+1]=s[j];
        }
    }

    cout<<bfs();

    return 0;
}


            

题解 AcWing 1242. 修改数组

术
18天前

                1. set做法，超时




#include <iostream>
#include <set>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
set<int> st;
//找未出现最小整数
int fun(int i)
{
    set<int>::iterator it=st.begin();
    int k=a[i];
    while(st.find(k)!=st.end())
    {
        k++;
    }
    st.insert(k);
    a[i]=k;
}
int main()
{
    cin>>n;

    for(int i=0; i<n; i++)
        cin>>a[i];
    st.insert(a[0]);
    for(int i=1;i<n;i++){
        fun(i);
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";

    //cout << "Hello world!" << endl;
    return 0;
}



2.并查集


#include <iostream>

using namespace std;
const int N=1e6+5;
int n;
int p[N];
//并查集，将相等的数看作属于一个集合
int fin(int x)
{
    if(x!=p[x])
    p[x]=fin(p[x]);
    return p[x];
}
int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=N;i++) p[i]=i;//第一次出现，父节点是本身

    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        x=fin(x);
        cout<<x<<" ";
        p[x]=x+1;//每有一个相同的数，集合父节点加1
    }
    return 0;
}


            

题解 AcWing 2879. 画中漂流

术
18天前

                
1. dfs做法，会超时，通过两组数据


#include <iostream>

using namespace std;
int d,t,m;
long long res;
const int mod=1e9+7;
void dfs(int u,int k,int len)//u是花了多少力气，k是花了多少时间
{
    if(k==t&&u==m){//必须hua完力气
        res++;
        return;
    }

    if(u<m){//u小于m才可以花力气
        dfs(u+1,k+1,len+1);
    }
    if(len>1)//len大于1，才可以不花力气
    dfs(u,k+1,len-1);
}
int main()
{
    cin>>d>>t>>m;
    dfs(0,0,d);
    if(d+m*2<t)
    {
        cout<<"0";
    }
    else
    cout<<res%mod;

    //cout << "Hello world!" << endl;
    return 0;
}



2. dp，dp[i][j]表示花费时间i，花费体力j的方案数；
转移方程 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]//即第i秒用体力和不用体力的方案数 相加



#include <iostream>

using namespace std;
int d,t,m;
const int N=3005;

const int mod=1e9+7;
long long dp[N][N];

int main()
{
    cin>>d>>t>>m;
    dp[0][0]=1;

    for(int i=1; i<=t; i++)
    {
        for(int j=0; j<=m; j++) //花费体力j
        {
            int length=d+j-(i-j);
            if(length<=0)
                continue; //判断是否可到达此状态, 核心！！  若前i秒使用j体力会死， 不管在哪个时间划j次，都会死，则不可到达，即方案数为0
                //这样只需
            if(j!=0)
                dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;//前i秒花费j体力的前提下，  第i秒 划+不划
            else
                dp[i][j]=(dp[i-1][j])%mod;//
        }
    }
    cout<<dp[t][m];
    //cout << "Hello world!" << endl;
    return 0;
}


            

题解 AcWing 2875. 超级胶水

术
18天前

                #include <iostream>
using namespace std;
const int N=1e5+5;
int n;
int a[N];

int main()
{
    cin>>n;
    unsigned long long res=0;
    int sum=0;
    //不管怎么合并，a[i]都要乘后面的所有数~~~~~~

    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=0; i<n; i++)
    {
        sum-=a[i];
        res+=(long long )a[i]*sum;
    }
    cout<<res;
    //cout << "Hello world!" << endl;
    return 0;
}


            

0 评论

0 评论

0 评论

0 评论

2 评论

0 评论

0 评论

0 评论

0 评论

0 评论