头像

tzz1011




离线:4天前



tzz1011
6天前

img.jpg

题目要求如图,有没有什么比较好的算法呢,菜鸡的我不太会

题目输出对应紫色方格的坐标位置(红色方框左上角为原点)和缩放比例



活动打卡代码 AcWing 901. 滑雪

tzz1011
8天前
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

const int N = 310;
int h[N][N];
int f[N][N];
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if(v != -1) return v;//这个点走过的话直接返回这个点的值

    v = 1;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
        {
            v = max(v, dp(a, b) + 1);
        }
    }

    return v;
}
int main()
{
    scanf("%d %d", &n, &m);

    memset(f, -1, sizeof(f));

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &h[i][j]);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            ans = max(ans, dp(i, j));
        }
    }

    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 902. 最短编辑距离

tzz1011
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    for (int i = 0; i <= m; i++) f[0][i] = i; //a的0个字母与b的前i个字母比较
    for (int i = 0; i <= n; i++) f[i][0] = i; //a的前i个字母与b的0个字母比较

    for(int i = 1; i<= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

tzz1011
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int  N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = m; j > 0; j--)
            for (int k = 0; k < s[i]; k++)
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}



tzz1011
1个月前

版本一

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N], a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int len = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;//相当于(l + r + 1) / 2;
            cout << mid << endl;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];

        cout << len << " " << a[i] << endl;
    }

    cout << len << endl;
    system("pause");
    return 0;
}

版本二

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> q;
    for (int i = 0; i < n; i++) cin >> a[i];

    q.push_back(a[0]);//模拟堆栈
    for (int i = 1; i < n; i++)
    {
        if (a[i] > q.back()) q.push_back(a[i]);
        else
        *lower_bound(q.begin(), q.end(), a[i]) = a[i];
    }

    cout << q.size() << endl;
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

tzz1011
2个月前

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20000;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b; 
        }
    }

    n = cnt;

    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j],f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

tzz1011
2个月前

、、、

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=20000;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin >> n >> m;
int cnt = 0;
for(int i = 1;i <= n;i )
{
int a,b,s;
cin >> a >> b >> s;
int k = 1;
while(k <= s)
{
cnt
;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if(s > 0)
{
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}

n = cnt;

for(int i = 1; i <= n; i ++)
    for(int j = m; j >= v[i]; j --)
        f[j] = max(f[j],f[j - v[i]] + w[i]);

cout << f[m] << endl;
return 0;

}
、、、



活动打卡代码 AcWing 840. 模拟散列表

tzz1011
2个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=1e5+3;
int e[N],q[N],ne[N],idx;

void insert(int tmp){
    int k=(tmp%N+N)%N;
    e[idx]=tmp,ne[idx]=q[k],q[k]=idx++;
}

int find(int tmp){
    int k=(tmp%N+N)%N;
    for(int i=q[k];i!=-1;i=ne[i])
        if(e[i]==tmp)
            return true;

    return false;
}

int main(){
    int n;
    string op;
    cin>>n;

    memset(q,-1,sizeof q);

    int t;
    while(n--){
        cin>>op;
        cin>>t;
        if(op=="I"){
            insert(t);
        }
        else {
            find(t)?cout<<"Yes":cout<<"No";
            cout<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 395. 冗余路径

tzz1011
3个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> E[5010];
int n, m;
int dfn[5010], low[5010], timestamp;
int stk[5010], top;
int id[5010], dcc_cnt;
vector<pair<int, int>> brige;
int du[5010];

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;
    for (int i = 0; i < E[u].size(); i ++)
    {
        int v = E[u][i];
        if (!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                brige.push_back({u, v});
        }
        else if (v != fa)
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        dcc_cnt ++;
        int y;
        do {
            y = stk[top --];
            id[y] = dcc_cnt;

        } while (y != u);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    tarjan(1, -1);

    for (auto x : brige)
    {
        int a = x.first, b = x.second;
        du[id[a]] ++, du[id[b]] ++;
    }

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++)
        cnt += (du[i] == 1);

    cout << (cnt + 1) / 2 << endl;

    return 0;
}


活动打卡代码 AcWing 367. 学校网络

tzz1011
4个月前
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

const int N = 101;
vector<int> E[N], DAGE[N];
int dfn[N], low[N], timestamp;
stack<int> stk;
bool instk[N];
int color[N];
int cnt;
int chu[N], ru[N];

int n;

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk.push(u);
    instk[u] = true;
    for (int i = 0; i < E[u].size(); i ++)
    {
        int v = E[u][i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (low[u] == dfn[u])
    {
        cnt ++;
        while (1)
        {
            int v = stk.top();
            stk.pop();
            instk[v] = false;
            color[v] = cnt;
            if (v == u) break;
        }
    }

}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        int x;
        while (1)
        {
            cin >> x;
            if (x == 0) break;
            E[i].push_back(x);
        }
    }

    for (int i = 1; i <= n; i ++)
        if (!dfn[i])
            tarjan(i);


    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j < E[i].size(); j ++)
        {
            int v = E[i][j];
            if (color[i] != color[v])
            {
                DAGE[color[i]].push_back(color[v]);
                ru[color[v]] ++;
                chu[color[i]] ++;
            }
        }
    }


    int c = 0, r = 0;
    for (int i = 1; i <= cnt; i ++)
    {
        if (!chu[i]) c ++;
        if (!ru[i]) r ++;
    }

    cout << r << endl;

    if (cnt == 1)
        cout << 0 << endl;
    else
        cout << max(r, c) << endl;




    return 0;
}