2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

时间：2023-08-26 12:57:50

2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

A Secret of Chocolate Poles

思路:暴力枚举黑巧克力的个数和厚黑巧克力的个数

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

LL C(int n, int m) {

    LL res = ;

    if(n-m < m) m = n-m;

    for (int i = ; i <= m; i++) {

        res *= (n-i+);

        res /= i;

    }

    return res;

}

int main() {

    int l, k;

    LL res = ;

    scanf("%d %d", &l, &k);

    LL ans = ;

   for (int i = ; i <= ; i++) {

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

            if(j*k + (i-j) + i- <= l) {

                ans += C(i, j);

            }

        }

   }

   printf("%lld\n", ans);

    return ;

}

B Parallel Lines

思路:预处理+暴力

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

int a[], b[];

pii p[];

pii delta[];

int tmp[][];

piii T[];

int t[];

int vv[];

int main() {

    int m;

    scanf("%d", &m);

    for (int i = ; i <= m; i++) scanf("%d %d", &p[i].fi, &p[i].se);

    int cnt = ;

    for (int i = ; i <= m; i++) {

        for (int j = ; j <= m; j++) {

            if(i == j) continue;

            int x = p[i].fi - p[j].fi;

            int y = p[i].se - p[j].se;

            int d = __gcd(x, y);

            x /= d;

            y /= d;

            if(x >  && y < ) x = -x, y = -y;

            T[++cnt].fi.fi = x;

            T[cnt].fi.se = y;

            T[cnt].se = cnt;

            tmp[i][j] = cnt;

        }

    }

    sort(T+, T++cnt);

    int now = ;

    t[T[].se] = now;

    for (int i = ; i <= cnt; i++) {

        if(T[i].fi.fi == T[i-].fi.fi && T[i].fi.se == T[i-].fi.se) {

            t[T[i].se] = now;

        }

        else {

            t[T[i].se] = ++now;

        }

    }

    for (int i = ; i <= m; i++) {

        for (int j = ; j <= m; j++) {

            tmp[i][j] = t[tmp[i][j]];

        }

    }

    int up = (<<m)-;

    int ans = ;

    for (int i = ; i <= up; i++) {

        if(__builtin_popcount(i) == m/ && (up^i) < i) {

            int tot = , cnt = ;

            for (int j = ; j < m; j++) if((i&(<<j)) == ) a[++tot] = j+; else b[++cnt] = j+;

            do {

                int res = ;

                for (int i = ; i <= tot; i++) {

                   res += vv[tmp[a[i]][b[i]]];

                    vv[tmp[a[i]][b[i]]]++;

                }

                for (int i = ; i <= tot; i++) vv[tmp[a[i]][b[i]]]--;

                ans = max(ans, res);

            }

            while(next_permutation(a+, a++tot));

//            cout<<ans<<endl;

        }

    }

    printf("%d\n", ans);

    return ;

}

C Medical Checkup

思路:模拟

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

ll a[maxn];

ll mol,den;

int main()

{

    ll n,t;

    scanf("%lld%lld",&n,&t);

    for(int i=;i<n;i++) scanf("%lld",&a[i]);

    ll pre1=,pre2=;

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

    {

//        pre1+=a[i];

        den=max(a[i],den);

        mol=t-pre1-a[i]>= ? t-pre1-a[i]:-den;

        pre1+=a[i];

        printf("%lld\n",mol/den+);

    }

}

D Making Perimeter of the Convex Hull Shortest

E Black or White

F Pizza Delivery

思路:先分别求出每个点到1和2的最短路d1[i], d2[i],

对于一条边u->v, 如果d1[v] + d2[u] + w < 1到2最短路径, 那么肯定是HAPPY

否则看这条边是不是1到2的所有最短路径所构成的无向图中的桥, 如果是桥, 删去后最短路肯定变大, 是SAD, 否则最短路径肯定不变, 是SOSO

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const int N = 1e5  + ;

const LL INF = 0x3f3f3f3f3f3f3f3f;

vector<pii> g[N], rg[N], tg[N];

int ans[N], u[N], v[N], w[N], low[N], dfn[N], tot = ;

pii fa[N];

LL d1[N], d2[N];

priority_queue<pli, vector<pli>, greater<pli> > q;

void Dij1(int s) {

    mem(d1, INF);

    d1[s] = ;

    q.push({, s});

    while(!q.empty()) {

        pli p = q.top();

        q.pop();

        int u = p.se;

        if(p.fi > d1[u]) continue;

        for (pii to : g[u]) {

            int v = to.fi;

            int w = to.se;

            if(d1[u] + w < d1[v]) {

                d1[v] = d1[u] + w;

                q.push({d1[v], v});

            }

        }

    }

}

void Dij2(int s) {

    mem(d2, INF);

    d2[s] = ;

    q.push({, s});

    while(!q.empty()) {

        pli p = q.top();

        q.pop();

        int u = p.se;

        if(p.fi > d2[u]) continue;

        for (pii to : rg[u]) {

            int v = to.fi;

            int w = to.se;

            if(d2[u] + w < d2[v]) {

                d2[v] = d2[u] + w;

                q.push({d2[v], v});

            }

        }

    }

}

void tarjan(int u, pii o) {

    low[u] = dfn[u] = ++tot;

    fa[u] = o;

    for (pii p: tg[u]) {

        int v = p.fi;

        if(!dfn[v]) {

            tarjan(v, {u, p.se});

            low[u] = min(low[u], low[v]);

        }

        else if(v != o.fi) low[u] = min(low[u], dfn[v]);

    }

}

int main() {

    int n, m;

    scanf("%d %d", &n, &m);

    for (int i = ; i <= m; i++) {

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

        g[u[i]].pb({v[i], w[i]});

        rg[v[i]].pb({u[i], w[i]});

    }

    Dij1();

    Dij2();

    for (int i = ; i <= m; i++) {

        if(d1[v[i]] + w[i] + d2[u[i]] < d1[]) ans[i] = ;

        else if(d1[u[i]] + w[i] + d2[v[i]] == d1[]) {

            tg[u[i]].pb({v[i], i});

            tg[v[i]].pb({u[i], i});

        }

    }

    tarjan(, {, });

    for (int v = ; v <= n; v++) {

        int u = fa[v].fi;

        int id = fa[v].se;

        if(low[v] > dfn[u]) ans[id] = ;

    }

    for (int i = ; i <= m; i++) {

        if(ans[i] == ) puts("HAPPY");

        else if(ans[i] == ) puts("SAD");

        else puts("SOSO");

    }

    return ;

}

G Rendezvous on a Tetrahedron

思路:将立体问题转换成平面问题

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

char s[];

int w, l;

double f1(double x, double c) {

    return sqrt()*x + c;

}

double f2(double x, double c) {

    return -sqrt()*x + c;

}

int solve() {

    scanf("%s", s);

    scanf("%d %d", &w, &l);

    if(s[] == 'B') w += ;

    else if(s[] == 'C') w += ;

    double y = l * sin(w*pi/180.0);

    double x = - l * cos(w*pi/180.0);

    while(y > *sqrt()) y -= *sqrt();

    while(x > ) x -= ;

    while(x < ) x += ;

    if( <= x && x < ) {

        if( <= y  && y <= sqrt()) {

            if(y > f1(x, ) && y > f2(x, sqrt())) return ;

            else if(y < f1(x, ) && y < f2(x, sqrt())) return ;

            else if(y > f1(x, ) && y < f2(x, sqrt())) {

                if(y > sqrt()/2.0) return ;

                else return ;

            }

            else {

                if(y > sqrt()/2.0) return ;

                else return ;

            }

        }

        else {

            if(y > f1(x, sqrt()) && y > f2(x, *sqrt())) return ;

            else if(y < f1(x, sqrt()) && y < f2(x, *sqrt())) return ;

            else if(y > f1(x, sqrt()) && y < f2(x, *sqrt())) {

                if(y > sqrt()*3.0/2.0) return ;

                else return ;

            }

            else {

                if(y > sqrt()*3.0/2.0) return ;

                else return ;

            }

        }

    }

    else {

        if( <= y  && y <= sqrt()) {

            if(y > f1(x, -sqrt()) && y > f2(x, *sqrt())) return ;

            else if(y < f1(x, -sqrt()) && y < f2(x, *sqrt())) return ;

            else if(y > f1(x, -sqrt()) && y < f2(x, *sqrt())) {

                if(y > sqrt()/2.0) return ;

                else return ;

            }

            else {

                if(y > sqrt()/2.0) return ;

                else return ;

            }

        }

        else {

            if(y > f1(x, ) && y > f2(x, *sqrt())) return ;

            else if(y < f1(x, ) && y < f2(x, *sqrt())) return ;

            else if(y > f1(x, ) && y < f2(x, *sqrt())) {

                if(y > sqrt()*3.0/2.0) return ;

                else return ;

            }

            else {

                if(y > sqrt()*3.0/2.0) return ;

                else return ;

            }

        }

    }

}

int main() {

    if(solve() == solve()) puts("YES");

    else puts("NO");

    return ;

}

H Homework

I Starting a Scenic Railroad Service

思路:

第一种就是求对于每个区间,有多少个区间与他相交, 取最大值, 这个用容斥做

第二种贪心求,每次从优先队列里取出右端点最靠前的,与当前区间左端点比较

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const int N = 2e5 + , M = 1e5 + ;

pii a[N];

int n, bit[M], btt[M];

priority_queue<int, vector<int>, greater<int> > q;

void add(int x, int ty) {

    if(ty == ) {

        while(x < M) bit[x]++, x += x&-x;

    }

    else {

        while(x < M) btt[x]++, x += x&-x;

    }

}

int sum(int x, int ty) {

    int ans = ;

    if(ty == ) {

        while(x) ans += bit[x], x -= x&-x;

    }

    else {

        while(x) ans += btt[x], x -= x&-x;

    }

    return ans;

}

int main() {

    scanf("%d", &n);

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

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

    }

    sort(a+, a++n);

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

        if(q.empty()) q.push(a[i].se);

        else {

            int p = q.top();

            if(a[i].fi >= p) {

                q.pop();

                q.push(a[i].se);

            }

            else q.push(a[i].se);

        }

    }

    int ans2 = q.size(), ans1 = ;

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

        add(a[i].se, );

        add(a[i].fi, );

    }

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

        int t = n- - sum(a[i].fi, );

        t -= (n - sum(a[i].se-, ));

        ans1 = max(ans1, t);

//        cout << a[i].fi << " " << a[i].se << " " << t << endl;

    }

    printf("%d %d\n", ans1+, ans2);

    return ;

}

J String Puzzle

K Counting Cycles

相关文章