2018 German Collegiate Programming Contest (GCPC 18)

2022-12-07 20:43:39

建树，求lca

代码：

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

//typedef __int128 bll;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

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

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

#define max3(a,b,c) max(max(a,b), c);

#define min3(a,b,c) min(min(a,b), c);

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

const double PHI=0.61803399;    //黄金分割点

const double tPHI=0.38196601;

template<typename T>

inline T read(T&x){

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

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

        const int maxn = 1e3+;

        string mp[maxn];

        int anc[maxn*maxn][];

        int fa[maxn*maxn];

        vector<int>tree[maxn*maxn];

        int deep[maxn*maxn];

        int vis[maxn][maxn];

        int n,m;

        void bfs(int sx,int sy){

            queue<pii>que;

            que.push(pii(sx,sy));

            vis[sx][sy] = ;

            while(!que.empty()){

                int x = que.front().fi,y = que.front().se;

                que.pop();

                int u = (x-)*m + y;

                if(y<m && mp[x][*y] != '|'){

                    int tx = x,ty = y+;

                    if(vis[tx][ty] == ){

                        vis[tx][ty] = ;

                        int v = (tx-)*m+ty;

                        que.push(pii(tx,ty));

                        tree[u].pb(v);

                        tree[v].pb(u);

                    }

                }

                if(y>&&mp[x][*y-] != '|'){

                    int tx = x,ty = y-;

                    if(vis[tx][ty] == ){

                        vis[tx][ty] = ;

                        int v = (tx-)*m+ty;

                        que.push(pii(tx,ty));

                        tree[u].pb(v);

                        tree[v].pb(u);

                    }

                }

                if(x>&&mp[x-][*y-] != '_'){

                    int tx = x-,ty = y;

                    if(vis[tx][ty] == ){

                        vis[tx][ty] = ;

                        int v = (tx-)*m+ty;

                        que.push(pii(tx,ty));

                        tree[u].pb(v);

                        tree[v].pb(u);

                    }

                }

                if(x < n && mp[x][*y-] != '_'){

                    int tx = x+,ty = y;

                    if(vis[tx][ty] == ){

                        vis[tx][ty] = ;

                        int v = (tx-)*m+ty;

                        que.push(pii(tx,ty));

                        tree[u].pb(v);

                        tree[v].pb(u);

                    }

                }

            }

        }

        void dfs(int x){

            anc[x][] = fa[x];

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

                anc[x][i] = anc[anc[x][i-]][i-];

            }

            for(int i=; i<tree[x].size(); i++){

                if(tree[x][i]!=fa[x]){

                    int y = tree[x][i];

                    fa[y] = x;

                    deep[y] = deep[x]+;

                    dfs(y);

                }

            }

        }

        int lca(int x,int y){

            int dx = x,dy = y;

            if(deep[x] < deep[y]) swap(x,y);

            for(int i=; i>=; i--){

                if(deep[y] <= deep[anc[x][i]])

                    x = anc[x][i];

            }

            int rt;

            if(x==y)rt = x;

            else {

                for(int i=; i>=; i--){

                    if(anc[x][i] != anc[y][i]){

                        x = anc[x][i];

                        y = anc[y][i];

                    }

                }

                rt = anc[x][];

            }

            return deep[dx]+deep[dy] -* deep[rt];

        }

int main(){

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

            cin>>n>>m;

            getline(cin,mp[]);

            for(int i=; i<=n; i++) getline(cin, mp[i]);

            bfs(,);

            dfs();

            int q,la;  ll ans = ;

            scanf("%d", &q);

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

                int x,y;

                scanf("%d%d", &x, &y);

                if(i==) la = (x-)*m + y;

                else {

                    int now = (x-)*m + y;

                    ans += 1ll*lca(la, now);

                    //debug(lca(la,now));

                    la = now;

                }

            }

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

            return ;

}

Battle Royale

求两点不经过圆内的最短路径

代码：

#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)

double dis(double x1, double y1, double x2, double y2) {

    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

}

int main() {

    double x1, x2, y1, y2, ox, oy, r;

    scanf("%lf %lf", &x1, &y1);

    scanf("%lf %lf", &x2, &y2);

    scanf("%lf %lf %lf", &ox, &oy, &r);

    scanf("%lf %lf %lf", &ox, &oy, &r);

    double c = dis(x1, y1, x2, y2);

    double a = dis(ox, oy, x1, y1);

    double b = dis(ox, oy, x2, y2);

    double alpha = acos((a*a + c*c - b*b) / (*a*c));

    double beta = acos((b*b + c*c - a*a) / (*b*c));

    if(alpha > pi/ || beta > pi/) {

        printf("%.10f\n", c);

        return ;

    }

    alpha = acos((a*a +b*b - c*c)/ (*a*b));

    double d = a*b*sin(alpha)/c;

    if(d < r) {

        double aa = acos(r/a);

        double bb = acos(r/b);

        alpha -= aa;

        alpha -= bb;

        printf("%.10f\n", sqrt(a*a - r*r) + sqrt(b*b - r*r) + alpha*r);

    }

    else printf("%.10f\n", c);

    return ;

}

Coolest Ski Route

按拓扑序转移

代码：

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

// #pragma GCC diagnostic error "-std=c++11"

// #pragma comment(linker, "/stack:200000000")

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

//typedef __int128 bll;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

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

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

#define max3(a,b,c) max(max(a,b), c);

#define min3(a,b,c) min(min(a,b), c);

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

const double PHI=0.61803399;    //黄金分割点

const double tPHI=0.38196601;

template<typename T>

inline T read(T&x){

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

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

            const int maxn = 1e3+;

            vector<pii>mp[maxn];

            queue<int>p,que;

            int n,m;

            int in[maxn];

            int dp[maxn];

            void topo(){

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

                    if(in[i] == )p.push(i);

                }

                while(!p.empty()){

                    int u = p.front();p.pop();

                    que.push(u);

                    for(int i=; i<mp[u].size(); i++){

                        int v = mp[u][i].fi;

                        in[v]--;

                        if(in[v] == ) p.push(v);

                    }

                }

            }

 int main(){

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

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

                int u,v,w;

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

                mp[u].pb(pii(v,w));

                in[v]++;

            }

            topo();

            int mx = ;

            while(!que.empty()){

                int u = que.front(); que.pop();

                for(int i=; i<mp[u].size(); i++){

                    int v = mp[u][i].fi,c = mp[u][i].se;

                    dp[v] = max(dp[v], dp[u] + c);

                    mx = max(mx, dp[v]);

                }

            }

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

            return ;

}

Down the Pyramid

求区间交集

代码：

#include<bits/stdc++.h>

#define pb push_back

#define int long long

using namespace std;

const int maxn=3e5+;

const int mod=1e9++;

int32_t main()

{

    int n; cin>>n;

    int ans=1e9+;

    int l=;

    int r=1e9+;

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

    {

        int x; cin>>x;

        if(l>x)

        {

            cout<<<<endl; return ;

        }

        int q=x-r;

        int p=x-l;

        if(p>x) p=x;

        if(q<) q=;

        //cout<<q<<"  "<<p<<endl;

        l=q;

        r=p;

        ans=min(ans,r-l+);

    }

    cout<<ans<<endl;

}

Expired License

乘1e5再算

代码：

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

// #pragma GCC diagnostic error "-std=c++11"

// #pragma comment(linker, "/stack:200000000")

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

//typedef __int128 bll;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

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

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

#define max3(a,b,c) max(max(a,b), c);

#define min3(a,b,c) min(min(a,b), c);

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

const double PHI=0.61803399;    //黄金分割点

const double tPHI=0.38196601;

template<typename T>

inline T read(T&x){

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

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

            const int maxn = 1e5;

            int gcd(int a, int b){

                if(b == )return a;

                return gcd(b, a % b);

            }

            bool check(int x){

                if(x == ) return false;

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

                    if(x % i==)return false;

                }

                return true;

            }

int main(){

         //  cout<<gcd(5 ,10)<<endl;

            int T;  scanf("%d", &T);

            double a,b;

            int n,m;

            while(T--){

                scanf("%lf%lf", &a, &b);

                a += 5e-;

                b += 5e-;

                n = (int)(a * maxn );

                m = (int)(b * maxn);

                //cout<<n<<" "<<m<<endl;

                int q = __gcd(n, m);

                n = n/q;

                m = m/q;

               // cout<<n<<" "<<m<<endl;

                if(n == m) printf("2 2\n");

                else if(check(n) && check(m)){

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

                }

                else puts("impossible");

            }

            return ;

}

Fighting Monsters

代码：

#include<bits/stdc++.h>

#define pb push_back

#define int long long

using namespace std;

const int maxn=1e6+;

const int mod=1e9+;

vector<int> vs[maxn];

int32_t main()

{

    int n; cin>>n;

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

    {

        int x; cin>>x; vs[x].push_back(i);

    }

    int l=;

    int r=;

    if(vs[].size()>=)

    {

        cout<<vs[][]<<" "<<vs[][]<<endl;

        return ;

    }

    while()

    {

        if(l>1e6||r>1e6)

        {

            break;

        }

        int k=l+r;

        l=r;

        r=k;

        //cout<<l<<" "<<r<<endl;

        if(vs[l].size()&&vs[r].size())

        {

            cout<<vs[l][]<<" "<<vs[r][]<<endl;

            return ;

        }

    }

    cout<<"impossible"<<endl;

}

GPS

Hyper Illuminati

1^(n-1) + 2^(n-1) + ... + s^(n-1) = m

代码：

#include<bits/stdc++.h>

#define pb push_back

#define int long long

using namespace std;

const int maxn=1e6+;

const int mod=1e9+;

vector<int> vs[maxn];

int32_t main()

{

    int n; cin>>n;

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

    {

        int x=i*(i+)*(*i+)/;

        if(x<n)

        {

            continue;

        }

        if(n==x)

        {

            cout<<<<" "<<i<<endl;

            return ;

        }

        if(x>n)

        {

            break;

        }

    }

    for(int p=;p<=;p++)

    {

        int ans=;

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

        {

            int t=;

            for(int c=;c<p;c++)

            {

                t*=i;

            }

            ans+=t;

            if(ans<n) continue;

            else if(ans==n)

            {

              cout<<p<<" "<<i<<endl;

              return ;

            }

            else

            {

                break;

            }

        }

    }

    cout<<"impossible"<<endl;

}

It's Time for a Montage

代码：

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

// #pragma GCC diagnostic error "-std=c++11"

// #pragma comment(linker, "/stack:200000000")

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

//typedef __int128 bll;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

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

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

#define max3(a,b,c) max(max(a,b), c);

#define min3(a,b,c) min(min(a,b), c);

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

const double PHI=0.61803399;    //黄金分割点

const double tPHI=0.38196601;

template<typename T>

inline T read(T&x){

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

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

        const int maxn = 1e3+;

        int h[maxn],v[maxn],dif[maxn];

        int n;

        bool check(int x){

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

                if(dif[i] + x > ) return true;

                else if(dif[i] + x < )return false;

            }

            return true;

        }

int main(){

        scanf("%d", &n);

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

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

        for(int i=; i<=n; i++) dif[i] = h[i] - v[i];

        int ans = ;

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

            if(check(i)){ans = i;break;}

        }

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

        return ;

}

Jigsaw Puzzle

模拟

代码：

#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 pdd pair<long double, long double>

#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 = 3e5 + ;

int a[N][];

int t[N*][];

vector<int> vc;

int main() {

    int n;

    scanf("%d", &n);

    int st = -;

    int tmp[];

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

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

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

            if(a[i][j]) {

                int tmp = a[i][j];

                if(t[tmp][]) t[tmp][] = i;

                else t[tmp][] = i;

            }

        }

        swap(a[i][], a[i][]);

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

            if(!a[i][j] && !a[i][(j+)%]) st = i;

        }

    }

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

        if(!a[st][j] && !a[st][(j+)%]) {

            tmp[] = tmp[] = ;

            tmp[] = a[st][(j+)%];

            tmp[] = a[st][(j+)%];

            break;

        }

    }

    if(~st);

    else return *puts("impossible");

    vc.pb(st);

    for (int j = ; j < ; j++) a[st][j] = tmp[j];

    while(true) {

        int now = vc.back();

        if(!a[now][]) break;

        int id = a[now][];

        int nx;

        if(t[id][] == now) nx = t[id][];

        else nx = t[id][];

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

            if(a[nx][j] == id) {

                tmp[] = a[nx][j];

                tmp[] = a[nx][(j+)%];

                tmp[] = a[nx][(j+)%];

                tmp[] = a[nx][(j+)%];

                break;

            }

        }

        for (int j = ; j < ; j++) a[nx][j] = tmp[j];

        if(a[nx][]) return *puts("impossible");

        vc.pb(nx);

    }

    int m = (int)vc.size();

    if(n%m) return *puts("impossible");

    if(n == m) {

        for (int i = ; i < n; i++) if(a[vc[i]][]) return *puts("impossible");

    }

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

        int now = vc[i-m];

        if(!a[now][]) return *puts("impossible");

        int id= a[now][];

        int nx;

        if(t[id][] == now) nx = t[id][];

        else nx = t[id][];

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

            if(a[nx][j] == id) {

                tmp[] = a[nx][j];

                tmp[] = a[nx][(j+)%];

                tmp[] = a[nx][(j+)%];

                tmp[] = a[nx][(j+)%];

                break;

            }

        }

        for (int j = ; j < ; j++) a[nx][j] = tmp[j];

        if(i%m ==  && a[nx][]) return *puts("impossible");

        if(i%m == m- && a[nx][]) return *puts("impossible");

        if(i%m >  && (a[nx][] != a[vc[i-]][] || a[nx][] == )) return *puts("impossible");

        if(i >= n-m && a[nx][]) return *puts("impossible");

        if(i < n-m && a[nx][] == ) return *puts("impossible");

        vc.pb(nx);

    }

    printf("%d %d", n/m, m);

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

        if(i%m == ) printf("\n");

        printf("%d ", vc[i]);

    }

    return ;

}

Kitchen Cable Chaos

dp[i][j]:和为i且线段个数为j是否存在

代码：

#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 pdd pair<long double, long double>

#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 = , M = 2e3 + ;

const int INF = 0x3f3f3f3f;

const double eps = 5e-;

int a[N], n, g;

bool dp[M][N];

int main() {

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

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

    dp[][] = true;

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

        for (int j = M-; j >= a[i]; j--) {

            for (int k = n; k >= ; k--) {

                dp[j][k] |= dp[j-a[i]][k-];

            }

        }

    }

    double ans = -;

    for (int j = g-; j < M; j++) {

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

            if(dp[j][i]) {

                if(j+-g <= *(i+)) ans = max((j+10.0-g)/(double)(i+), ans);

            }

        }

    }

    if(ans < -0.5) printf("impossible");

    else printf("%.9f\n", ans);

    return ;

}

Logic Puzzle

模拟：

代码：

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = ;

int a[N][N];

int h, w;

bool vis[N][N];

int dir[][] = {, , , , , -, -, };

int main() {

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

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

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

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

        }

    }

    bool f = false;

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

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

            int cnt = ;

            for (int ii = -; ii <= ; ii++) {

                for (int jj = -; jj <= ; jj++) {

                    int x = i + ii;

                    int y = j + jj;

                    if( <= x && x <= h &&  <= y && y <= w) {

                        if(vis[x][y]) cnt++;

                    }

                }

            }

            int res = a[i][j] - cnt;

            int x = i+, y = j+;

            if( <= x && x <= h &&  <= y && y <= w) {

                if(res <  || res > ) {

                    f = true;

                    break;

                }

                else if(res == ){

                    vis[x][y] = true;

                }

            }

            else {

                if(res != ) {

                    f = true;

                    break;

                }

            }

        }

    }

    if(f) puts("impossible");

    else {

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

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

                if(vis[i][j]) putchar('X');

                else putchar('.');

            }

            puts("");

        }

    }

    return ;

}

Mountaineers

按高度从小到大启发式合并并查集，合并并查集时更新答案为当前高度

代码：

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define y1 y11

#define pb push_back

#define pii pair<int, int>

const int N = , M = 1e6 + , MM = 1e5 + , NN = N*N;

int fa[NN], sz[NN];

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

vector<pii> vc[M];

int x1[MM], y1[MM], x2[MM], y2[MM], ans[MM];

set<int> s[NN], que[NN];

map<int, int> mp[NN];

int dir[][] = {, , , , -, , , -};

void init() {

    for (int i = ; i < N*N; i++) fa[i] = i, s[i].insert(i);

}

int get_id(int x, int y) {

    return (x-)*n + y;

}

int Find(int x) {

    if(x == fa[x]) return x;

    else return fa[x] = Find(fa[x]);

}

void Merge(int x, int y, int h) {

    x = Find(x);

    y = Find(y);

    if(x == y) return ;

    if(s[x].size() < s[y].size()) {

        fa[x] = y;

        for(int a : s[x]) {

            s[y].insert(a);

            for (int b : que[a]) {

                if(s[y].find(b) != s[y].end() && mp[a].find(b) == mp[a].end()) {

                    mp[a][b] = h;

                    mp[b][a] = h;

                }

            }

        }

    }

    else {

        fa[y] = x;

        for(int a : s[y]) {

            s[x].insert(a);

            for (int b : que[a]) {

                if(s[x].find(b) != s[x].end() && mp[a].find(b) == mp[a].end()) {

                    mp[a][b] = h;

                    mp[b][a] = h;

                }

            }

        }

    }

}

void solve() {

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

        for (pii p : vc[i]) {

            int x = p.fi;

            int y = p.se;

            int id = get_id(x, y);

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

                int xx = x + dir[j][];

                int yy = y + dir[j][];

                if(xx <  || xx > m || yy <  || yy > n) continue;

                if(h[xx][yy] <= i) {

                    Merge(id, get_id(xx, yy), i);

                }

            }

        }

    }

}

int main() {

    int q;

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

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

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

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

            vc[h[i][j]].pb({i, j});

        }

    }

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

        scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);

        if(x1[i] == x2[i] && y1[i] == y2[i]) {

            ans[i] = h[x1[i]][y1[i]];

        }

        else {

            int id1 = get_id(x1[i], y1[i]);

            int id2 = get_id(x2[i], y2[i]);

            que[id1].insert(id2);

            que[id2].insert(id1);

        }

    }

    init();

    solve();

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

        if(ans[i]) printf("%d\n", ans[i]);

        else printf("%d\n", mp[get_id(x1[i], y1[i])][get_id(x2[i], y2[i])]);

    }

    return ;

}

码农公寓

相关文章