头像

南岸以南南岸哀




在线 


最近来访(396)
用户头像
sealt
用户头像
痛苦面具
用户头像
femirins
用户头像
violet_garden
用户头像
benedict
用户头像
Octovolib
用户头像
宇宙有边
用户头像
今天刷题了嘛
用户头像
XinyeChu
用户头像
_wyp_
用户头像
艾久夕
用户头像
梦若浮生
用户头像
垫底抽風
用户头像
笑嘚甜蜜蜜
用户头像
yxc的小迷妹
用户头像
小黄
用户头像
大学才
用户头像
不高兴的兽奶
用户头像
北海没有WA
用户头像
anti-


题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
int f[N][N];
int a[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
             cin>>a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
        }    
    }
    int res=0;

        if(n&1){
            cout<<(f[n][n/2+1]);
        }
        else{
            cout<<max(f[n][n/2],f[n][n/2+1]);
        }

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



寄第一次做传信杯代打就被抓到,无语



分享

今天开始淡算法了,复习六级和期末考了,不过还是会打周赛的




题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

求最大值,根据差分约束,求下限(最短路)

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 3e4+10,M=150010;
typedef pair<int, int> PII;
#define x first
#define y second

int h[N], e[M], ne[M],w[M],idx;
bool st[N];
int dist[N],n,m;
void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    queue<int> q;
    q.push(1);
    st[1]=true;
    dist[1]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof h);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    //for(int i=1;i<=n;i++) cout<<dist[i]<<endl;
    cout<<dist[n];
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 220;
char g[N][N];
int n,m,d1[N][N],d2[N][N];
typedef pair<int, int> PII;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dist[N][N];
void bfs(int sx,int sy,int op){
    memset(dist,0x3f,sizeof(dist));
    queue<PII> q;
    q.push({sx,sy});
    dist[sx][sy]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=t.first+dx[i],ty=t.second+dy[i];
            if(tx<=0||ty<=0||tx>n||ty>m) continue;
            if(g[tx][ty]!='#'&&dist[tx][ty]==0x3f3f3f3f)
            {
                dist[tx][ty]=dist[t.first][t.second]+1;
                q.push({tx,ty});
            }
        }
    }
}
int main()
{
    while(cin>>n>>m){
        memset(d1,0x3f,sizeof(d1));
        memset(d2,0x3f,sizeof(d2));
        int sx,sy,ex,ey;
        for(int i=1;i<=n;i++) cin>>g[i]+1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='Y') sx=i,sy=j;
                if(g[i][j]=='M') ex=i,ey=j;
            }
        }
        bfs(sx,sy,1);
        memcpy(d1,dist,sizeof(dist));
        bfs(ex,ey,2);
        memcpy(d2,dist,sizeof(dist));
        int res=1<<30;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='@') res=min(res,d1[i][j]+d2[i][j]);
            }
        }
        cout<<res*11<<endl;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 4227. 找路

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 220;
char g[N][N];
int n,m,d1[N][N],d2[N][N];
typedef pair<int, int> PII;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dist[N][N];
void bfs(int sx,int sy,int op){
    memset(dist,0x3f,sizeof(dist));
    queue<PII> q;
    q.push({sx,sy});
    dist[sx][sy]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=t.first+dx[i],ty=t.second+dy[i];
            if(tx<=0||ty<=0||tx>n||ty>m) continue;
            if(g[tx][ty]!='#'&&dist[tx][ty]==0x3f3f3f3f)
            {
                dist[tx][ty]=dist[t.first][t.second]+1;
                q.push({tx,ty});
            }
        }
    }
}
int main()
{
    while(cin>>n>>m){
        memset(d1,0x3f,sizeof(d1));
        memset(d2,0x3f,sizeof(d2));
        int sx,sy,ex,ey;
        for(int i=1;i<=n;i++) cin>>g[i]+1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='Y') sx=i,sy=j;
                if(g[i][j]=='M') ex=i,ey=j;
            }
        }
        bfs(sx,sy,1);
        memcpy(d1,dist,sizeof(dist));
        bfs(ex,ey,2);
        memcpy(d2,dist,sizeof(dist));
        int res=1<<30;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='@') res=min(res,d1[i][j]+d2[i][j]);
            }
        }
        cout<<res*11<<endl;
    }
}



题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 15;
char g[N][N];
int n,m;
int dist[N][N];
bool st[N][N];
typedef pair<int, int> PII;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(int x1,int y1,int x2,int y2)
{
    queue<PII> q;
    memset(dist,-1,sizeof(dist));
    memset(st,0,sizeof(st));
    q.push({x1,y1});
    q.push({x2,y2});
    dist[x1][y1]=0;
    dist[x2][y2]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=t.first+dx[i],ty=t.second+dy[i];
            if(tx<=0||ty<=0||tx>n||ty>m||g[tx][ty]=='.') continue;
            if(dist[tx][ty]==-1){
                dist[tx][ty]=dist[t.first][t.second]+1;
                q.push({tx,ty});
                st[tx][ty]=1;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='#'&&dist[i][j]!=-1)
            {
                res=max(res,dist[i][j]);    
            }
            if(g[i][j]=='#'&&dist[i][j]==-1) return 0x3f3f3f3f;
        }
    }
    return res;
}
void solve(int id){
    cin>>n>>m;
    vector<PII> a;
    int cnt=0;
    for(int i=1;i<=n;i++) cin>>g[i]+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='#') a.push_back({i,j}),cnt++; 
        }
    }
    if(a.size()==0){
        printf("Case %d: %d\n",id,-1);
        return ;
    }
    if(cnt<=2){
        printf("Case %d: %d\n",id,0);
        return ;
    }
    int res=0x3f3f3f3f;
    for(int i=0;i<a.size();i++)
    {
        for(int j=i+1;j<a.size();j++)
            {
                res=min(res,bfs(a[i].first,a[i].second,a[j].first,a[j].second));
            }
    }
    if(res==0x3f3f3f3f){
        printf("Case %d: %d\n",id,-1);
    }
    else{
        printf("Case %d: %d\n",id,res);
    }
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        solve(i);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include<string.h>
using namespace std;
const int N = 1e4+10;
typedef pair<string, int> PII;

int primes[100000];
int st[N];
int cnt;
int n;
int st1[N];
unordered_map<string,int> mp;
void count(int n){
    st[1]=true;
    for(int i=2;i<=10000;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=10000/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
void solve()
{
    int a,b;
    cin>>a>>b;
    memset(st1,0,sizeof(st1));
    if(a==b)
    {
        cout<<0<<endl;
        return ;
    }
    string p=to_string(a);
    string qq=to_string(b);
    queue<PII> q;
    q.push({p,0});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.first==qq){
            cout<<t.second<<endl;
            return ;
        }
        for(char i='0';i<='9';i++){
            for(int j=0;j<t.first.size();j++)
            {
                string cc=t.first;
                if(i=='0'&&!j) continue;
                cc[j]=i;
                if(mp[cc]==1&&!st1[stoi(cc)])
                {
                    st1[stoi(cc)]=true;
                    q.push({cc,t.second+1});
                }
            }
        }
    }
    printf("Impossible\n");
}
int main()
{

    int t;
    cin>>t;
    count(N);
    for(int i=0;i<cnt;i++){
        mp[to_string(primes[i])]=1;
    }

    while(t--)
    {
        solve();
    }

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



填空题
题目:8518是一个非常特殊的数.............

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 110;
int a[N][N];
int f[N][N];
char g[N][N];
int n,m;

int main()
{


    for(int j=10;j<=10000;j++)
    {
        string x=to_string(j);
        int res=0;
        for(int i=0;i<x.size();i++)
        {
            res=res*16+(x[i]-'0');
        }
        if(res%j==0){
            cout<<j<<endl;
        }
    }
}

题目:从第一行第一列画一条折现.....

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N][N];
int f[N][N];
char g[N][N];
int n,m;
int main()
{
    int t;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>g[i]+1;

        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                a[i][j]=g[i][j]-'0';
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
        }
        cout<<f[30][60]<<endl;
}

3.将2022拆分成不同的质数的和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
bool check(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}

int main()
{
    int n=2022;
    int res=0;
    for(int i=2;i<2022;i++){
        if(i>n) break;
        if(check(i)&&n-i>=0)
        {
            cout<<(i)<<endl;
            res++;
            n-=i;
        }
    }
    cout<<res;
}

编程题:
6-7语法题
8.

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    string a;
    cin>>a;
    int n=a.size();
    int idx=1000000;
    int l=0,r=0,s=n-1,f=1;
    for(int k=0;k<n;k++){
        if(a[k]!=a[s--]){
            f=0;
            break;
        }
    }
    if(f==1){
        cout<<a;
        return 0;
    }
    for(int k=n/2;k<n-1;k++){
        int i=k-1,j=k+1;
        int flag=1;
        while(i>=0&&j<n){
            if(a[i]!=a[j]){
                flag=0;
                break;
            }
            else{
                i--,j++;
            }
        }
        if(i==0&&j<n&&flag){
            if(k<idx){
                idx=k-1;
                l=0,r=1;
            }
        }
        if(i>0&&j==n&&flag){
            if(k<idx){
                idx=k-1;
                l=1,r=0;
            }
        }
        if(i==0&&j==n&&flag){
            idx==k-1;
            l=r=1;
        }
    }
    if(idx==1000000&&l==0&&r==0){
        for(int k=0;k<n;k++)cout<<a[k];
        for(int k=n-1;k>=0;k--)cout<<a[k];
    }
    else{
        if(l==0&&r==1){
            for(int k=n-1;k>idx;k--)cout<<a[k];
            for(int k=idx;k<n;k++)cout<<a[k];
        }
        if(l==1&&r==0){
            for(int k=0;k<=idx;k++)cout<<a[k];
            for(int k=idx-1;k>=0;k--)cout<<a[k];
        }
        if(l==1&&r==1){
            cout<<a;
        }
    }
    return 0;
}

9.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
long long tr[N];
long long res;
int n,m;
char g[110][110];

bool st[110][110];
int dx[4] = {-1,-1,1,1}, dy[4] = {-1,1,-1,1};
bool check(int x,int y){
    if(x<=0||y<=0||x>n||y>m) return false;
    return true;
}
void dfs(int x,int y,int depth)
{
    int tx1=x+dx[0]*depth,ty1=y+dy[0]*depth;
    int tx2=x+dx[1]*depth,ty2=y+dy[1]*depth;
    int tx3=x+dx[2]*depth,ty3=y+dy[2]*depth;
    int tx4=x+dx[3]*depth,ty4=y+dy[3]*depth;
    if(check(tx1,ty1)==false) return;
    if(check(tx2,ty2)==false) return;
    if(check(tx3,ty3)==false) return;
    if(check(tx4,ty4)==false) return;
    if(g[tx1][ty1]!=g[x][y]) return;
    if(g[tx2][ty2]!=g[x][y]) return;
    if(g[tx3][ty3]!=g[x][y]) return;
    if(g[tx4][ty4]!=g[x][y]) return;
    res++;
    dfs(x,y,depth+1);
    return ;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        cin>>g[i]+1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++){
                dfs(i,j,1);
        }
    }
    cout<<res;
    return 0;

}

10.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
long long tr[N];
long long res;
int n,m;
int a[N];
 int mx=0;
int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c){
    for(int i=x;i<=mx;i+=lowbit(i))
    tr[i]+=c;
}
long long query(int x)  // 返回前x个数的和
{
    long long res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        mx=max(mx,a[i]);
    }

    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        res+=query(mx)-query(a[i]);
        add(x,x);
    }
    cout<<res;
    return 0;

}



题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int a[N][N];
int n,m;
int g[N][N];
int b[N][N];
int cnt[N][N];
bool check(int x,int y){
    if(x<0||y<0||x>=n||y>=m) return false;
    return true;
}
void turn(int x,int y)
{
    if(check(x,y)) g[x][y]^=1;
    if(check(x+1,y)) g[x+1][y]^=1;
    if(check(x-1,y)) g[x-1][y]^=1;
    if(check(x,y+1)) g[x][y+1]^=1;
    if(check(x,y-1)) g[x][y-1]^=1;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
         cin>>a[i][j];
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<1<<m;i++)
    {
        int res=0;
        memcpy(g,a,sizeof(a));
        memset(b,0,sizeof(b));
        int state=i;
        for(int j=0;j<m;j++)
        {
            if(((state>>j)&1)!=g[0][j])
            {
                b[0][j]++;
                res++;
                turn(0,j);
            } 
        }
        for(int j=1;j<n;j++){
            for(int k=0;k<m;k++){
                if(g[j-1][k]!=0){
                    turn(j,k);
                    b[j][k]++;
                    res++;
                }
            }
        }
        bool flag=true;
        for(int j=0;j<n;j++){
            for(int k=0;k<m;k++)
                if(g[j][k]){
                    flag=false;
                    break;
                }
        }
        if(!flag) continue;
        if(ans>=res)
        {
            memcpy(cnt,b,sizeof(b));
            ans=res;
        }
    }
    if(ans==0x3f3f3f3f)
    {
        printf("IMPOSSIBLE");
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<cnt[i][j]<<" ";
        }
        puts("");
    }
}


算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla