2016程序设计实习实验班免修考试(算法)

2017年2月10日6,4190

02:热血格斗场

#include <set>
#include <cstdio>
#include <iostream>
using namespace std;
int n;
int id[100005],v[100005];
set<pair<int, int> >st;
int main()
{
    scanf("%d", &n);
    st.insert(make_pair(1000000000,1));
    st.insert(make_pair(-1000000000,1));
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &id[i], &v[i]);
        auto l = st.lower_bound(make_pair(v[i], id[i])), r = l;
        l--;
        if(v[i] - (l->first) <= (r->first) - v[i])
            printf("%d %d\n", id[i], l->second);
        else printf("%d %d\n", id[i], r->second);
        st.insert(make_pair(v[i], id[i]));
    }
    return 0;
}

#include <set>

#include <cstdio>

#include <iostream>

using namespace std;

int n;

int id[100005],v[100005];

set<pair<int, int> >st;

int main()

{

scanf("%d", &n);

st.insert(make_pair(1000000000,1));

st.insert(make_pair(-1000000000,1));

for(int i = 1; i <= n; i++)

{

scanf("%d%d", &id[i], &v[i]);

auto l = st.lower_bound(make_pair(v[i], id[i])), r = l;

l--;

if(v[i] - (l->first) <= (r->first) - v[i])

printf("%d %d\n", id[i], l->second);

else printf("%d %d\n", id[i], r->second);

st.insert(make_pair(v[i], id[i]));

}

return 0;

}

05:MPI Maelstrom

#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 1000000000
using namespace std;
int read()
{
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == 'x')return -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x;
}
int n, m;
int dis[105][105];
int main()
{
    scanf("%d", &n);
    memset(dis, 127/3, sizeof(dis));
    for(int i = 2; i <= n; i++)
        for(int j = 1; j < i; j++)
        {
            int x = read();
            if(x != -1)dis[i][j] = dis[j][i] = x;
        }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, dis[1][i]);
    cout << ans << endl;
    return 0;
}

#include <set>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#define inf 1000000000

using namespace std;

int read()

{

int x = 0; char ch = getchar();

while(ch < '0' || ch > '9'){if(ch == 'x')return -1; ch = getchar();}

while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}

return x;

}

int n, m;

int dis[105][105];

int main()

{

scanf("%d", &n);

memset(dis, 127/3, sizeof(dis));

for(int i = 2; i <= n; i++)

for(int j = 1; j < i; j++)

{

int x = read();

if(x != -1)dis[i][j] = dis[j][i] = x;

}

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);

int ans = 0;

for(int i = 1; i <= n; i++)

ans = max(ans, dis[1][i]);

cout << ans << endl;

return 0;

}

06:Ultra-QuickSort

#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[500005], b[500005], t[500005];
vector<int>ve;
void add(int x)
{
    for(int i = x; i <= n; i += i&(-i))
        t[i]++;
}
int query(int x)
{
    int ans = 0;
    for(int i = x; i; i -= i&(-i))
        ans += t[i];
    return ans;
}
int main()
{
    while(scanf("%d", &n))
    {
        if(n == 0)break;
        ve.clear();
        memset(t, 0 , sizeof(t));
        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &a[i]);
            ve.push_back(a[i]);
        }
        sort(ve.begin(), ve.end());
        for(int i = 1; i <= n; i++)
            b[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1;
        long long ans = 0;
        for(int i = 1; i <= n; i++)
        {
            add(b[i]);
            ans += i - query(b[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

#include <set>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n;

int a[500005], b[500005], t[500005];

vector<int>ve;

void add(int x)

{

for(int i = x; i <= n; i += i&(-i))

t[i]++;

}

int query(int x)

{

int ans = 0;

for(int i = x; i; i -= i&(-i))

ans += t[i];

return ans;

}

int main()

{

while(scanf("%d", &n))

{

if(n == 0)break;

ve.clear();

memset(t, 0 , sizeof(t));

for(int i = 1; i <= n; i++)

{

int x;

scanf("%d", &a[i]);

ve.push_back(a[i]);

}

sort(ve.begin(), ve.end());

for(int i = 1; i <= n; i++)

b[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1;

long long ans = 0;

for(int i = 1; i <= n; i++)

{

add(b[i]);

ans += i - query(b[i]);

}

cout << ans << endl;

}

return 0;

}

08:Drainage Ditches

#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 1000000000
using namespace std;
int n, m, cnt;
int h[205], last[205], q[205];
struct edge{
    int to, next, v;
}e[1005];
void insert(int u, int v, int w)
{
    e[++cnt] = (edge){v, last[u], w}; last[u] = cnt;
    e[++cnt] = (edge){u, last[v], 0}; last[v] = cnt;
}
bool bfs()
{
    int head = 0, tail = 1;
    memset(h, -1, sizeof(h));
    q[0] = 1; h[1] = 0;
    while(head != tail)
    {
        int now = q[head]; head++;
        for(int i = last[now]; i; i = e[i].next)
            if(e[i].v && h[e[i].to] == -1)
            {
                h[e[i].to] = h[now] + 1;
                q[tail++] = e[i].to;
            }
    }
    return h[m] != -1;
}
int dfs(int x, int f)
{
    int w, used = 0;
    if(x == m)return f;
    for(int i = last[x]; i; i = e[i].next)
        if(h[e[i].to] == h[x] + 1)
        {
            w = dfs(e[i].to, min(e[i].v, f - used));
            used += w;
            e[i].v -= w; e[i ^ 1].v += w;
            if(used == f)return used;
        }
    if(!used)h[x] = -1;
    return used;
}
int main()
{
    while(scanf("%d%d", &n ,&m) != EOF)
    {
        memset(last, 0, sizeof(last));
        cnt = 1;
        for(int i = 1; i <= n; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
        }
        int ans = 0;
        while(bfs())
            ans += dfs(1, inf);
        cout << ans << endl;
    }
    return 0;
}

#include <set>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#define inf 1000000000

using namespace std;

int n, m, cnt;

int h[205], last[205], q[205];

struct edge{

int to, next, v;

}e[1005];

void insert(int u, int v, int w)

{

e[++cnt] = (edge){v, last[u], w}; last[u] = cnt;

e[++cnt] = (edge){u, last[v], 0}; last[v] = cnt;

}

bool bfs()

{

int head = 0, tail = 1;

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

q[0] = 1; h[1] = 0;

while(head != tail)

{

int now = q[head]; head++;

for(int i = last[now]; i; i = e[i].next)

if(e[i].v && h[e[i].to] == -1)

{

h[e[i].to] = h[now] + 1;

q[tail++] = e[i].to;

}

return h[m] != -1;

}

int dfs(int x, int f)

{

int w, used = 0;

if(x == m)return f;

for(int i = last[x]; i; i = e[i].next)

if(h[e[i].to] == h[x] + 1)

{

w = dfs(e[i].to, min(e[i].v, f - used));

used += w;

e[i].v -= w; e[i ^ 1].v += w;

if(used == f)return used;

}

if(!used)h[x] = -1;

return used;

}

int main()

{

while(scanf("%d%d", &n ,&m) != EOF)

{

memset(last, 0, sizeof(last));

cnt = 1;

for(int i = 1; i <= n; i++)

{

int u, v, w;

scanf("%d%d%d", &u, &v, &w);

insert(u, v, w);

}

int ans = 0;

while(bfs())

ans += dfs(1, inf);

cout << ans << endl;

}

return 0;

}

« 2016 ACM / ICPC Asia Regional Qingdao Online 2015程序设计实习实验班免修考试(校内) »

hzwer.com _ Home | http://hzwer.com

2016程序设计实习实验班免修考试(算法)

02:热血格斗场

05:MPI Maelstrom

06:Ultra-QuickSort

08:Drainage Ditches

分类目录

热门文章

Myfriends

近期评论