UOJ Logo admin的博客

博客

再见,OIers,退役是新的开始!

2019-11-18 18:55:54 By admin

去年、今年的这个日子心情都格外沮丧,

不是因为考的好不好,

而是因为你们要走了,

对于一位不是班主任的副科老师而言,

能和你们一起经历一年半的时间,这种经历尤为珍贵,

教育只是一种媒介,

成绩不是最终的目的,

最终影响我们一生的,是透过这种媒介,在追逐目的过程中所产生的思想、情感的共鸣,

今天目送你们退役,

希望你们能开开心心回到教室,

省一就算拿到了也无法让你们永远开心,

这只是当前阶段的最优子问题,

继续DP下去吧,

前方才是最精彩的,

欢迎你们经常回来!

Shaun Han

!!!!!!!!!!!!!本周任务【6月10日—6月16日】

2019-03-22 16:03:44 By admin

【5月27日—6月2日】

  • 每天坚持打1个模板
  • 周六上午测试

0316测试数据、题解、学生代码、标程下载

2019-03-16 11:31:46 By admin

0309课堂代码

2019-03-09 10:47:30 By admin

p2678 rock 跳石头

#include<bits/stdc++.h>
using namespace std;
int L, N, M, a[50050], ans;
int s=1000000001, t;
int main()
{
    cin>>L>>N>>M;
    for(int i=1; i<=N; i++)
    {
        cin>>a[i];
        s=min(s, a[i]-a[i-1]);        //统计答案的下界 
    }
    t=L/(N-M+1);                    //计算答案的上界 
    while(s<=t)                        //在[s,t]范围内折半查找 
    {
        int m=(s+t)>>1;
        int cnt=M, pre=a[0];
        for(int i=1; i<=N; i++)
        {
            if((a[i]-pre)<m)        //跨度不够,移石头 
                cnt--;
            else
                pre=a[i];
        }
        if(cnt>=0)    s=m+1, ans=m;    //当前m可行,在右边查找 
        else        t=m-1;            //当前m不行,在左边查找 
    }
    if(!N)    cout<<L<<endl;            //一个坑,边界情况,N==0 
    else    cout<<ans<<endl;
    return 0;
}

p5021 road 赛道修建

#include<bits/stdc++.h>
using namespace std;
int n, m, s=0x7fffffff, t, head[50001], tot, ans, sum;
int fa[50001], c[50001];
struct edge
{
    int to, val, next;
}E[100001];
void add(int x, int y, int z)
{
    E[++tot].to=y;
    E[tot].val=z;
    E[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    for(int i=head[x]; i; i=E[i].next)
    {
        int y=E[i].to;
        if(y==fa[x]) continue;
        fa[y]=x;
        dfs(y);
    }
}
int dfs2(int x, int mid)
{

    int ans=0;
    multiset<int> tj;
    for(int i=head[x]; i; i=E[i].next)
    {
        int y=E[i].to;
        if(y==fa[x]) continue;
        ans+=dfs2(y, mid);
        if(c[y]+E[i].val>=mid)     ans++;
        else                    tj.insert(c[y]+E[i].val);
    }
    c[x]=0;
    while(!tj.empty())
    {
        int u=*tj.begin();
        tj.erase(tj.begin());
        multiset<int>::iterator p=tj.lower_bound(mid-u);
        if(p==tj.end())
        {
            c[x]=u;
        }
        else
        {
            tj.erase(p);
            ans++;
        }
    }
    tj.clear();
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<n; i++)
    {
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        add(a, b, l);
        add(b, a, l);
        s=min(s, l);
        sum+=l;
    }
    t=sum/m;
    fa[1]=1;
    dfs(1);
    while(s<=t)
    {
        memset(c, 0, sizeof(c));
        int mid=(s+t)>>1;
        if(dfs2(1, mid)>=m)
        {
            ans=mid;
            s=mid+1;
        }
        else t=mid-1;
    }
    printf("%d\n", ans);
    return 0;
}

0302Week01自测T1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long a[1000010], n, K, ans1, ans2;
priority_queue<long long, vector<long long>, less<long long> > Q;
int main()
{
    freopen("jkl.in", "r", stdin);
    freopen("jkl.out", "w", stdout);
    scanf("%lld%lld", &n, &K);
    for(int i=0; i<n; i++)    scanf("%lld", &a[i]), Q.push(a[i]);
    sort(a, a+n);

    for(int i=0, k2=K; k2; i++)
    {
        if(a[i])
        {
            if(k2<=a[i])    ans1+=((a[i]+a[i]-k2+1)*k2/2), k2=0;
            else            ans1+=((a[i]+1)*a[i]/2), k2-=a[i];
        }
    }
    for(int i=1, t; i<=K; i++)
    {
        t=Q.top();
        ans2+=t;
        Q.pop();
        Q.push(t-1);
    }
    printf("%lld %lld\n", ans2, ans1);
    return 0;
}

0302Week01自测T2

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, m, st[100005][65];

int main()
{
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for(ll i=1; i<=n; i++)    scanf("%lld", &st[i][0]);
    for(ll k=1; k<=60; k++)
        for(ll i=1; i<=n; i++)
            st[i][k]=st[st[i][k-1]][k-1];
    for(ll i=1; i<=m; i++)
    {
        ll a, b;
        scanf("%lld%lld", &a, &b);
        for(int i=0; i<63; i++)
        {
            if(b&1) a=st[a][i];
            b>>=1;
        }
        printf("%lld\n", a);
    }
    return 0;
}

0302Week01自测T3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=4e4+5, maxm=2e5+5;
int N, M, mst[maxn], f[maxn], ans;
double tot, avg, min_ans=1e30, dis[maxn], sum[maxn];
struct item
{
    int u, v;
    double d;
    item(int x, int y, double z){u=x, v=y, d=z;}
    friend bool operator<(const item &A, const item &R){ return A.d>R.d; }
};
struct edge
{
    int t; double w; edge * nxt;
    edge(int to, double len, edge * next)
    {
        t=to, w=len, nxt=next;
    }
};
edge *h1[maxn], *h2[maxn];
void add1(int u, int v, double len)
{
    h1[u]=new edge(v, len, h1[u]);
}
void add2(int u, int v, double len)
{
    h2[u]=new edge(v, len, h2[u]);
}
double prim(int x)
{
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<item, vector<item>, less<item> > Q;
    double ret=0;
    int    num=1;
    mst[x]=1;
    for(edge * p=h1[x]; p; p=p->nxt)
        if(p->t!=x) Q.push(item(x, p->t, p->w)), dis[p->t]=min(dis[p->t], p->w);
    while(!Q.empty() && num!=N)
    {
        while(!Q.empty() && mst[Q.top().v])    Q.pop();
        if(Q.empty()) break;
        int t=Q.top().v;
        mst[t]=true, ret+=Q.top().d, num++;
        add2(Q.top().u, Q.top().v, Q.top().d);
        add2(Q.top().v, Q.top().u, Q.top().d);
        Q.pop();
        for(edge *p=h1[t]; p; p=p->nxt)
            if(!mst[p->t] && dis[p->t]>p->w)    Q.push(item(t, p->t, p->w));
    }
    return ret;
}
void dfs(int x)
{
    sum[x]=0;
    for(edge *p=h2[x]; p; p=p->nxt)
    {
        if(p->t==f[x]) continue;
        f[p->t]=x;
        dfs(p->t);
        sum[x]=sum[x]+p->w+sum[p->t]; 
    }
}
int main()
{
    freopen("mokou.in", "r", stdin);
    freopen("mokou.out", "w", stdout); 
    scanf("%d%d", &N, &M);
    for(int i=1, u, v; i<=M; i++)
    {
        double len;
        scanf("%d%d%lf", &u, &v, &len);
        add1(u, v, len), add1(v, u, len);
    }
    tot=prim(1);                            //求MST 
    dfs(1);                                 //dfs求子树路径和 
    for(int i=1; i<=N; i++)                    //枚举每一个路口求权值 
    {
        double e=0, t_sum=0;
        vector<double> t;
        for(edge *p=h2[i]; p; p=p->nxt)
        {
            if(p->t==f[i]) continue;
            t.push_back(sum[p->t]+p->w);
            t_sum+=sum[p->t]+p->w;
        }
        if(tot-t_sum>0)    t.push_back(tot-t_sum);
        avg=tot/(t.size()+1);                //求平均值和方差 
        for(int j=0; j<t.size(); j++)    e+=((t[j]-avg)*(t[j]-avg));
        if(e<min_ans) min_ans=e, ans=i;
    }
    printf("%d\n", ans);
    return 0;
}

travel AC代码(DFS找特定边删除)

2019-03-04 17:41:40 By admin
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MS=500050;
struct edge { int t; edge * nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[MS];
int n, m, f[MS], q[MS], cnt, sp, spi, inc[MS], pmax[MS], tmax[MS];
void add(int u, int v) { h[u]=new edge(v, h[u]); }
void dfs1(int x)
{
    q[++cnt]=x;
    inc[x]=1;
    for(edge * p=h[x]; p && !sp; p=p->nxt)
    {
        if(p->t==f[x])     continue;
        if(inc[p->t])    sp=p->t;
        else            f[p->t]=x, dfs1(p->t);
    }
    if(!sp)    inc[x]=0, cnt--;
}
int clearINC(){ int i=1; while(q[i]!=sp) inc[q[i++]]=0; return i; }
void cut(int u, int v)
{
    edge * p=h[u];
    if(h[u]->t==v) h[u]=h[u]->nxt; else { while(p->nxt->t!=v) p=p->nxt; p->nxt=p->nxt->nxt; } 
}
void dfs3(int x)
{
    //cout<<"here: "<<x<<endl;
    int nextx;
    tmax[x]=inc[x]?0:x;
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(p->t==f[x])     continue;
        if(inc[p->t])    { nextx=p->t; continue; }
        f[p->t]=x;
        dfs3(p->t);
        tmax[x]=max(tmax[x], tmax[p->t]);
    }
    if(inc[x])
    {
        pmax[x]=tmax[f[x]];
        if(pmax[x]<x) pmax[x]=pmax[f[x]];
        //cout<<"Pmax:"<<pmax[x]<<"  nextx:"<<nextx<<"   tmax:"<<" "<<tmax[x]<<endl;
        if((nextx<x || nextx<tmax[x] || (nextx>tmax[x] && nextx<pmax[x]))&&nextx!=sp) f[nextx]=x, dfs3(nextx);
        else cut(x, nextx), cut(nextx, x);
    }
}
void findAndCut(int x)
{
    memset(f, 0, sizeof(f));
    if(q[spi+1]<q[cnt]) f[q[spi+1]]=sp, tmax[sp]=q[cnt], dfs3(q[spi+1]);    else f[q[cnt]]=sp, tmax[sp]=q[spi+1], dfs3(q[cnt]);
}
void dfs2(int x)
{
    printf("%d ", x);
    int c=0, temp[MS];
    for(edge * p=h[x]; p; p=p->nxt) if(p->t!=f[x]) temp[c++]=p->t;
    sort(temp, temp+c);
    for(int i=0; i<c; i++)    f[temp[i]]=x, dfs2(temp[i]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++){ int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); }
    if(n==m){ f[1]=1; dfs1(1); spi=clearINC(); findAndCut(1); }
    memset(f, 0, sizeof(f));
    f[1]=1;
    dfs2(1);
    return 0;
}

0302测试成绩和题解

2019-03-02 18:29:58 By admin

考试源码下载:

链接:https://pan.baidu.com/s/1TY_HgVkR40L_6m-OsNlUrg

提取码:qtiv

name t1 t2 t3 t4 tot
caiyize WWWWWWWTTT MMMMMMMMMM WWWWWWWWWW WWWTTTTTTT 0
chenliutai TTTTTTTTTT TTTTTTTBBB ATTTTTTTTT TTTTTTTTTT 10
chentianran TTTTTTTTTT RRRRRRRRRR ?????????? ?????????? 0
chenyuxin AAAAAAATTT WWAWWAAAWW AWWWWWWWTT AAABBBBBBB 150
cuizixi WWWBBBBBBB ?????????? AWWWWWTBBB ?????????? 10
fanxinzhu ---------- WWTTTTWTTT ?????????? ?????????? 0
gaoqiang WWWWWWWWWT **TTTTTTTT MMMMMMMMMM ?????????? 0
hanyixuan AAAAATTTTT AAAAAAATTT RRRRRRRRRR ?????????? 120
hengqianyi WWWTTTTTTT AAAAAAATTT ?????????? ?????????? 70
qiaosiqi AAATTTTTTT BBBBBBBBBB AWWWWWBBBB ?????????? 40
qiuhuanchao TTTTTTTTTT AATTTTTTTT TTTTTTTTTT TBBBBBBBBB 20
tianjiaqi WWWWWWWWWW AATTTTTTTT AWWWWWBBBB WWWWWWWWWW 30
zhangjianyang AAAAAAABBB AAAAAAATTT AAAAWATTTT AAATTTTTTT 220
zhaoyijie WWWWWWTTTT RRRRRRRRRR ---------- ********** 0
zhaozhengqi ?????????? MMMBBBBBBB ?????????? ?????????? 0

"R=无法运行

T=超时

M=超内存

Y=运行时错误

B=崩溃

A=正确

W=错误的答案

P=得部分分

*=程序无输出

[=缺标准输入

]=无标准输出

?=无程序

^=自定义评测错误

-=编译错误"

题解

1 http://hzwer.com/4605.html

2 http://hzwer.com/4726.html

3 http://hzwer.com/4729.html

4 http://hzwer.com/4727.html

4 我自己写的你或许看得懂的题解

gaoqiang提交文件名不对 qiaosiqi程序没有建子文件夹

你们俩的成绩是我修改后的成绩

模板传送门(完善中)

2019-03-02 09:00:38 By admin
带星号(*)的为参考模板。

PART1 排序

status Name Problem Link
OK(OK==已完成) 快速排序 洛谷P1177
OK 归并排序 同上
OK 堆排序 同上
OK STL优先队列 洛谷P1334

PART2 树及线性区间问题

status Name Problem Link More
OK(OK==已完成) LCA(ST倍增) 洛谷P3379 在线
OK LCA(Tarjan) 同上 离线
OK LCA(树链剖分) 洛谷P3379 我不知道在线离线
OK RMQ(ST表) 洛谷3865
OK 差分计算 洛谷3948
OK 树状数组 洛谷P3374/洛谷P3368 第2题为差分树状数组
OK 线段树 洛谷P3372/洛谷P3373 第二题为二维线段树
OK 树链剖分 洛谷P3384
OK 平衡树Treap 洛谷P3369 数组实现的平衡树
OK 平衡树的STL实现:set和multiset参考1参考2
*OK FHQ-Treap 洛谷P3369 简单全能的平衡树实现参考

PART3 图

status Name Problem Link more
OK(OK==已完成) SP:Floyd n极小时适用
OK SP:Bellman-Ford O(NM)
OK SP:SPFA+SLF+LLL优化 洛谷P3371 可处理负边,检测负环
OK SP:优先队列优化的Dijkstra 洛谷P4779 通常具有最佳效率,适用于非负权图
OK MST:Prim 洛谷P3366 附pair用法
OK MST:Kruskal 同上
OK 拓扑排序 洛谷P1137
OK SCC:Tarjan 洛谷P2002
OK SCC:Kosaraju 洛谷P2002
OK 找负环 洛谷P3385
OK 差分约束 洛谷P1993/洛谷P3275 含讲解
OK 欧拉回路 洛谷P2731/洛谷P1341 简单证明两种算法讲解
OK 割点和桥 洛谷P3388 割点讲解
OK 01最短路 洛谷P1948

PART4 数学

status Name Problem Link
OK(OK==已完成) 埃式筛法 洛谷P3912
OK 欧拉线性筛以及欧拉函数 洛谷P3383
OK 拓展欧几里德
OK 快速幂 洛谷P6685
OK 随机数生成

PART5 其它

status Name Problem Link more
OK(OK==已完成) 快读 用于大量数据读入时
OK 并查集 洛谷P3367洛谷P1525
OK 字符串哈希 洛谷P3370LOJ.ac103 参考文章
OK 哈希表 LOJ.ac10034 参考文章
OK KMP算法 洛谷P3375 参考文章1参考文章2
OK Trie字典树 LOJ.ac10049洛谷P2292LOJ.ac10054 参考文章1参考文章2
OK AC自动机 洛谷P3808洛谷P3796洛谷P5357 参考文章1参考文章2
OK 模拟退火 洛谷P1337

省选模板区

status Name Problem Link more
OK(OK==已完成) 可持久化并查集 洛谷P3402
文艺平衡树SPlay 洛谷P3835
可持久化平衡树 洛谷P3391
二分图染色 洛谷P1234
OK 二分图匹配(匈牙利算法) 洛谷P3386 Capella提供
网络流
最小割

2020.12 update by Nw 添加了数学中的代码与一些杂项,所以一些链接中的码风会与其他不同,有问题欢迎反馈

2月15上午课堂笔记(指针链式前向星)

2019-02-15 11:58:29 By admin

指针链式前向星


struct edge
{
    int from, to, val;
    edge * next;
    edge(int u, int v, int d, edge * nxt)
    {
        from=u;
        to=v;
        val=d;
        next=nxt;
    }
}
edge * h[maxn];

void add(int u, int v, int d)
{
    h[u]=new edge(u, v, d, h[u]);
}

spfa template, 不完整


const int max=10001;
const int INF=0x3fffffff;
int dis[maxn], v[maxn];

void bellmanFord(int x)
{
    for(int i=1; i<=n; i++)
        dis[i]=(i==x) ? 0 : INF;
    memset(v, 0, sizeof(v)); //inq
    queue<int> q;
    q.push(x);
    v[x]=1;
    while(!q.empty())
    {
        int from=q.front();
        q.pop();
        v[from]=0;
        for(edge * p=h[p]; p; p=p->next)
        {
            int to=p->to;
            int w =p->w;
            if(dis[from]+w<dis[to])
            {
                dis[to]=dis[from]+w;
                if(!v[to]) q.push(to), v[to]=1;
            }
        }
    }
}

不太好的存边方法

struct edge
{
    int to, val;
    edge(int t, v)
    {
        to=t;
        val=v;
    }
}
vector<edge> h[maxn];

void add(int u, int v, d)
{
    h[u].push_back(edge(v, d));
}

tarjan scc


int cnt, scc_cnt, sccno[maxn], d[maxn], l[maxn];
stack<int> st;
void tarjan(int x)
{
    if(sccno[x] || d[x])    return;
    d[x]=l[x]=++cnt;
    st.push(x);
    for(edge *e=h[x]; e; e=e->next)
    {
        tarjan(e->to);
        if(!sccno[e->to])    l[x]=min(l[x], l[e->to]);
    }
    if(d[x]==l[x])
    {
        scc_cnt++;
        while(Q.top()!=x)
        {
            sccno[st.top()]=scc_cnt;
            st.pop();
        }
        sccno[st.top()]=scc_cnt;
        st.pop();
    }
}


int main()
{
    for(int i=1; i<=n; i++)
        tarjan(i);
}

2月14日课堂笔记:dijkstra算法的队列优化

2019-02-14 20:41:02 By admin

markdown 现场教学笔记

点我到百度

sjakdhfjk

kasljdf

ksdaf

  • sadkf
  • asdfa
  • asdf
  1. sak
  2. ksl
  3. sda
10 10 10 
210 5454 545

内嵌代码abcde就是这个样子

这是引用某位大神的话:dsjlakfaskldjfkladsjfkl

img


$ 2^x + 3^{50} $

$ x_1+x_2+x_3 $

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=10010;
const ll  INF=0x3fffffffffffffff;
ll dis[maxn];
bool v[maxn];
int n, m, s;
struct my_pair
{
    int v;
    ll  d;
    my_pair(int x, ll y){ v=x, d=y; }
    bool operator<(my_pair r) const
    {
        return d>r.d;
    }
};

struct edge
{
    int to, next;
    ll val;
}E[maxn*2];

int cnt, h[maxn];

void add(int u, int v, ll d)
{
    E[++cnt].to=v;
    E[cnt].val=d;
    E[cnt].next=h[u];
    h[u]=cnt;
}

void dijkstra(int x)
{
    memset(v, 0, sizeof(v));
    for(int i=1; i<=n; i++)
        dis[i]= (i==x) ? 0 : INF;
    priority_queue<my_pair, vector<my_pair>, less<my_pair> > pq;
    pq.push(my_pair(x, dis[x]));

    while(!pq.empty())
    {
        int r=pq.top().v;
        ll rdis=pq.top().d;
        cout<<"haha "<<rdis<<endl;
        pq.pop();
        if(v[r])     continue;
        else        v[r]=true;        
        for(int i=h[r]; i; i=E[i].next)
        {
            int y=E[i].to;
            if(rdis+E[i].val<dis[y])
            {
                dis[y]=rdis+E[i].val;
                pq.push(my_pair(y, dis[y]));
            }    
        }
    }
}


int main()
{
    cin>>n>>m>>s;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        ll d;
        cin>>u>>v>>d;
        add(u, v, d);
        add(v, u, d);
    }
    dijkstra(s);
    for(int i=1; i<=n; i++)
        cout<<dis[i]<<endl;
    return 0;
}

//bft
void bft(int x)
{
    memset(visit, 0, sizeof(visit));
    queue<int> Q;
    Q.push(x);
    while(!Q.empty())
    {
        int p=Q.front();
        Q.pop();
        visit[p]=true;
        cout<<p;
        for(int i=h[p]; i; i=E[i].next)
        {
            int y=E[i].to;
            if(visit[y]) continue;
            Q.push(y);
        }
    }
}

//dft
void dft(int x)
{
    visit[x]=true;
    for(int i=h[x]; i; i=E[i].next)
    {
        int y=E[i].to;
        if(visit[y]) continue;
        dfs(y);
    }
}

二期同学必读:使用指针建立单向链表的程序样例

2018-12-18 18:57:43 By admin
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node{
    int val;
    node * next;
};
//两种获取对象内属性的方式:
//1. 通过对象获取
//   node a;
//   a.val=7;
//2. 通过指向对象的指针获取
//   node *p=a;        //p是对象a的指针(地址)
//   p->val=8;
//   或者(*p).val=8; 
int main(){
    int n;
    cin>>n;
    node * head=NULL, *p=NULL;        //局部变量,一定要设置初始值为NULL(空指针) 
    for(int i=0; i<n; i++){
        if(p==NULL)                    //如果p为空指针,需要建立第一个结点,且为头结点 
            head=p=new node;
        else{
            p->next=new node;        //新建一个结点,接在p->next上 
            p=p->next;                //使p指针指向新建的结点 
        }
        cin>>(p->val);                //读入val存入结点中 
    }
    p=head;                            //p指针重新指向头指针 
    while(p){                        //只要指针不为NULL,说明结点存在 
        cout<<p->val<<endl;
        p=p->next;                    //移动p到下一个结点 
    }
    return 0;
}

12月28日课堂内容补充

共 17 篇博客