头像

ZCPUZZLE




在线 


最近来访(58)
用户头像
冯适JYW
用户头像
SKG_G
用户头像
Fighting_Peter
用户头像
遇嘛.
用户头像
李培熙
用户头像
閉上眼睛我聽到心跳聲
用户头像
赛亚人
用户头像
yxc
用户头像
陈信长
用户头像
Mallknow
用户头像
Jackyc
用户头像
Bin.
用户头像
22w極
用户头像
zero_78
用户头像
hh666
用户头像
心升明月
用户头像
Tingting
用户头像
EHcg2009
用户头像
lycckky
用户头像
奇策十二


ZCPUZZLE
8分钟前

白送的60分写法

虽然我也参考别人的博客改了好长时间吧

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> a[5010];
int n, m;
int ans[5010], cnt;
bool st[5010];

void dfs(int u, int father)
{
    if(st[u]) return ;

    st[u] = true;
    ans[ ++ cnt] = u;

    for (int i = 0; i < a[u].size(); i ++ )
    {
        int j = a[u][i];
        if(j == father) continue;

        dfs(j, u);
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ )
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for (int i = 1; i <= n; i ++ ) sort(a[i].begin(), a[i].end());

    dfs(1, 0);

    for (int i = 1; i <= cnt; i ++ )
    {
        cout << ans[i] << ' ';
    }

    return 0;
}

正解

自己就先不写正解了
某谷的

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[5010];
int n,m;
int res[5010],ans[5010],tot;
int cir1[5010];
int u1[10010],v1[10010],cnt;
int vis[5010];
int du,dv;
int flag;
struct Edge {
    int from,to;
}e[5010];
void dfs2(int u,int fa) {
    if(vis[u])
        return ;
    vis[u]=1;
    ans[++tot]=u;
    for(int i=0;i<a[u].size();i++) {
        int v=a[u][i];
        if(v==fa)
            continue ;
        dfs2(v,u);
    }
}
void dfs1(int u,int fa) {
    if(vis[u])
        return ;
    vis[u]=1;
    res[++tot]=u;
    for(int i=0;i<a[u].size();i++) {
        int v=a[u][i];
        if(v==fa)
            continue ;
        if((u==du&&v==dv)||(u==dv&&v==du))
            continue ;
        dfs1(v,u);
    }
}
void dfs3(int from,int fa) {
    vis[from]=1;
    for(int i=0;i<a[from].size();i++) {
        int to=a[from][i];
        if(to==fa)
            continue ;
        if(vis[to]) {
            flag=1;
            cir1[to]=1;
            cir1[from]=1;
            u1[++cnt]=from;
            v1[cnt]=to;
            return ;
        }
        dfs3(to,from);
        if(flag&&cir1[to])
            if(cir1[from]) {
                flag=0;
                u1[++cnt]=from;
                v1[cnt]=to;
                return ;
            } else {
                cir1[from]=1;
                u1[++cnt]=from;
                v1[cnt]=to;
                return ;
            }
    }
}
int check() {
    for(int i=1;i<=n;i++) {
        if(res[i]<ans[i])
            return 1;
        else if(res[i]>ans[i])
            return 0;
    }
    return 0;
}
void update() {
    for(int i=1;i<=n;i++) {
        ans[i]=res[i];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++) {
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
        e[i].from=u;
        e[i].to=v;
    }
    for(int i=1;i<=n;i++)
        sort(a[i].begin(),a[i].end());
    if(m==n) {
        dfs3(1,0);
        int flag=1;
        for(int i=1;i<=cnt;i++) {
            du=u1[i];dv=v1[i];
            memset(vis,0,sizeof(vis));
            tot=0;
            dfs1(1,0);
            if(tot<n)
                continue ;
            if(flag) {
                update();
                flag=0;
            }
            if(check())
                update();
        }
        for(int i=1;i<=n;i++) {
            printf("%d ",ans[i]);
        }
    } else {
        dfs2(1,0);
        for(int i=1;i<=n;i++) {
            printf("%d ",ans[i]);
        }
    }
    return 0;
}


新鲜事 原文

ZCPUZZLE
13分钟前
祝大家再快到的CSP-s提高组里面取得好成绩吧,现在自己也不报什么希望了,只希望认真搞完最后的几天,到时候考成啥样是啥样吧,文化课差太多没有听,希望到时候能让我补回来吧, 对自己高中的OI生涯说再见吧,也祝大家能取得一个好成绩


活动打卡代码 AcWing 534. 旅行

ZCPUZZLE
16分钟前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> a[5010];
int n, m;
int ans[5010], cnt;
bool st[5010];

void dfs(int u, int father)
{
    if(st[u]) return ;

    st[u] = true;
    ans[ ++ cnt] = u;

    for (int i = 0; i < a[u].size(); i ++ )
    {
        int j = a[u][i];
        if(j == father) continue;

        dfs(j, u);
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ )
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for (int i = 1; i <= n; i ++ ) sort(a[i].begin(), a[i].end());

    dfs(1, 0);

    for (int i = 1; i <= cnt; i ++ )
    {
        cout << ans[i] << ' ';
    }

    return 0;
}


活动打卡代码 AcWing 133. 蚯蚓

ZCPUZZLE
2小时前
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;

bool cmp(const int &a,const int &b){
    return a>b;
}

priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/v;int tmp;
    for(t0=1;t0<=n;++t0)
        scanf("%d",&now[t0]);
    --t0;t1=t2=0;h=h1=h2=1;
    sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
    int top;
    for(int i=1;i<=m;++i){
        if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
        else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
        else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
        else top=cut2[h2],++h2;
        ;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
        top+=sigma;
        int a1=floor(p*(double)top),a2=top-a1;
        sigma+=q;
        a1-=sigma,a2-=sigma;
        cut1[++t1]=a1,cut2[++t2]=a2;
        if(i%t==0)printf("%d ",top);
    }
    putchar('\n');
    for(int i=h;i<=t0;++i)ans.push(now[i]);
    for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
    for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
    for(int i=1;ans.size();++i){
        if(i%t==0)printf("%d ",ans.top()+sigma);
        ans.pop();
    }
    return 0;
}



ZCPUZZLE
2小时前

暴力写法

某谷居然能拿到90分

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

priority_queue<int> ans;
int n, m, q, u, v, t;
int sum;
double p;
int tot;

int main()
{
    cin >> n >> m >> q >> u >> v >> t;

    p = (double)u / v;

    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        ans.push(x);
    }

    for (int i = 1; i <= m; i ++ )
    {
        int top = ans.top() + sum;
        ans.pop();
        int a1=floor(p*(double)top),a2=top-a1;
        a1 -= sum,a2 -= sum;
        a1 -= q,a2 -= q;
        ans.push(a1),ans.push(a2);
        if(i % t == 0)printf("%d ",top);
        sum += q;
    }

    putchar('\n');

    for(int i = 1; ans.size(); i ++ )
    {
        if(i % t == 0)printf("%d ",ans.top() + sum);
        ans.pop();
    }
    return 0;
}

正解

复制粘贴好
抄这个的 这里

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;

bool cmp(const int &a,const int &b){
    return a>b;
}

priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/v;int tmp;
    for(t0=1;t0<=n;++t0)
        scanf("%d",&now[t0]);
    --t0;t1=t2=0;h=h1=h2=1;
    sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
    int top;
    for(int i=1;i<=m;++i){
        if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
        else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
        else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
        else top=cut2[h2],++h2;
        ;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
        top+=sigma;
        int a1=floor(p*(double)top),a2=top-a1;
        sigma+=q;
        a1-=sigma,a2-=sigma;
        cut1[++t1]=a1,cut2[++t2]=a2;
        if(i%t==0)printf("%d ",top);
    }
    putchar('\n');
    for(int i=h;i<=t0;++i)ans.push(now[i]);
    for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
    for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
    for(int i=1;ans.size();++i){
        if(i%t==0)printf("%d ",ans.top()+sigma);
        ans.pop();
    }
    return 0;
}



ZCPUZZLE
8小时前

题目描述

春春是一名道路工程师,负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。

整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di。 

春春每天可以选择一段连续区间 [L,R],填充这段区间中的每块区域,让其下陷深度减少 1。

在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0。 

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0。

输入样例

6   
4 3 2 5 3 5 

输出样例

9

贪心

填尽可能大的范围, 中间的就相当于白送
可以用差分数组来预处理

数据比较小, 没有优化

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int ans;
int a[N], b[N];

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];

    for (int i = 1; i <= n; i ++ )
    {
        if(b[i] > 0) ans += b[i];
    }

    cout << ans << endl;

    return 0;
}



ZCPUZZLE
8小时前

题目描述

一个吉他手准备参加一场演出。

他不喜欢在演出时始终使用同一个音量,所以他决定每一首歌之前他都要改变一次音量。

在演出开始之前,他已经做好了一个列表,里面写着在每首歌开始之前他想要改变的音量是多少。

每一次改变音量,他可以选择调高也可以调低。

音量用一个整数描述。

输入文件中给定整数 beginLevel,代表吉他刚开始的音量,以及整数 maxLevel,代表吉他的最大音量。

音量不能小于 0 也不能大于 maxLevel。

输入文件中还给定了 n 个整数 c1,c2,c3,…,cn,表示在第 i 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌,你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数:n,beginLevel,maxLevel。

第二行依次为 n 个整数:c1,c2,c3,…,cn。

输出格式

输出演奏最后一首歌的最大音量。

如果吉他手无法避免音量低于 0 或者高于 maxLevel,输出 −1。

数据范围

1 ≤ n ≤ 50,
1 ≤ ci ≤ maxLevel,
1 ≤ maxLevel ≤ 1000,
0 ≤ beginLevel ≤ maxLevel

样例

输入样例1

3 5 10
5 3 7

输出样例1

10

动态规划

f[i, j] 表示第i个歌曲的音量是否能达到j

根据闫式DP分析法可得最后一个不同点是升高或者降低

可以得到状态转移方程f[i, j] = f[i - 1, j + w[i]] 或者 f[i - 1, j - w[i]];

判断转移条件就行, 数据比较小, 随便写

应为数据比较小就不优化了

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, l, r;
int a[N];
int f[N][N];

int main()
{
    cin >> n >> l >> r;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    f[0][l] = 1;

    for (int i = 1; i <= n;  i ++ )
        for (int j = 0; j <= r; j ++ )
        {
            if(f[i - 1][j] == 1)
            {
                if(j + a[i] <= r) f[i][j + a[i]] = 1;
                if(j >= a[i]) f[i][j - a[i]] = 1; 
            }

        }

    for (int i = r; i >= 0; i -- )
    {
        if(f[n][i] == 1)
        {
            cout << i << endl;
            return 0;
        }
    }

    cout << "-1" << endl;

    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

ZCPUZZLE
15小时前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], ne[M], e[M], idx;
int fa[N][16], depth[N];
int q[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)  // 预处理倍增数组
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;  // depth存储节点所在层数
    int hh = 0, tt = 0;
    q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;  // j的第二次幂个父节点
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)  // 返回a和b的最近公共祖先
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

int main()
{
    scanf("%d", &n);
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}



活动打卡代码 AcWing 1128. 信使

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];

int main()
{
    cin >> n >> m;

    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }

    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (d[1][i] == INF)
        {
            res = -1;
            break;
        }
        else res = max(res, d[1][i]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1129. 热浪

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100100;

int n, m;
int S, E;
int h[N], ne[N], e[N], w[N], idx;
bool st[N];
int dist[N];
queue<int> q;

void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    q.push(S);
    st[S] = true;

    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])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

}

int main()
{
    cin >> n >> m >> S >> E;

    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    spfa();

    cout << dist[E] << endl;

    return 0;
}