2018 German Collegiate Programming Contest (GCPC 18)

Attack on Alpha-Zet

建樹，求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_queuetypedef 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; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; 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=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x=f?-x:x; }/*-----------------------showtime----------------------*/const int maxn = 1e3+9;string mp[maxn];int anc[maxn*maxn][25];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] = 1;while(!que.empty()){int x = que.front().fi,y = que.front().se;que.pop();int u = (x-1)*m + y;if(y<m && mp[x][2*y] != '|'){int tx = x,ty = y+1;if(vis[tx][ty] == 0){vis[tx][ty] = 1;int v = (tx-1)*m+ty;que.push(pii(tx,ty));tree[u].pb(v);tree[v].pb(u);}}if(y>1&&mp[x][2*y-2] != '|'){int tx = x,ty = y-1;if(vis[tx][ty] == 0){vis[tx][ty] = 1;int v = (tx-1)*m+ty;que.push(pii(tx,ty));tree[u].pb(v);tree[v].pb(u);}}if(x>1&&mp[x-1][2*y-1] != '_'){int tx = x-1,ty = y;if(vis[tx][ty] == 0){vis[tx][ty] = 1;int v = (tx-1)*m+ty;que.push(pii(tx,ty));tree[u].pb(v);tree[v].pb(u);}}if(x < n && mp[x][2*y-1] != '_'){int tx = x+1,ty = y;if(vis[tx][ty] == 0){vis[tx][ty] = 1;int v = (tx-1)*m+ty;que.push(pii(tx,ty));tree[u].pb(v);tree[v].pb(u);}}}}void dfs(int x){anc[x][0] = fa[x];for(int i=1; i<=22; i++){anc[x][i] = anc[anc[x][i-1]][i-1];}for(int i=0; i<tree[x].size(); i++){if(tree[x][i]!=fa[x]){int y = tree[x][i];fa[y] = x;deep[y] = deep[x]+1;dfs(y);}}}int lca(int x,int y){int dx = x,dy = y;if(deep[x] < deep[y]) swap(x,y);for(int i=22; i>=0; i--){if(deep[y] <= deep[anc[x][i]])x = anc[x][i];}int rt;if(x==y)rt = x;else {for(int i=22; i>=0; i--){if(anc[x][i] != anc[y][i]){x = anc[x][i];y = anc[y][i];}}rt = anc[x][0];}return deep[dx]+deep[dy] -2* deep[rt];}int main(){//scanf("%d%d", &n, &m);cin>>n>>m;getline(cin,mp[0]);for(int i=0; i<=n; i++) getline(cin, mp[i]);bfs(1,1);dfs(1);int q,la; ll ans = 0;scanf("%d", &q);for(int i=1; i<=q; i++){int x,y;scanf("%d%d", &x, &y);if(i==1) la = (x-1)*m + y;else {int now = (x-1)*m + y;ans += 1ll*lca(la, now);//debug(lca(la,now));la = now;}}printf("%I64d\n", ans);return 0; } View Code 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) / (2*a*c));double beta = acos((b*b + c*c - a*a) / (2*b*c));if(alpha > pi/2 || beta > pi/2) {printf("%.10f\n", c);return 0;}alpha = acos((a*a +b*b - c*c)/ (2*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 0; } View Code 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_queuetypedef 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; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; 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=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x=f?-x:x; }/*-----------------------showtime----------------------*/const int maxn = 1e3+9;vector<pii>mp[maxn];queue<int>p,que;int n,m;int in[maxn];int dp[maxn];void topo(){for(int i=1; i<=n; i++){if(in[i] == 0)p.push(i);}while(!p.empty()){int u = p.front();p.pop();que.push(u);for(int i=0; i<mp[u].size(); i++){int v = mp[u][i].fi;in[v]--;if(in[v] == 0) p.push(v);}}}int main(){scanf("%d%d", &n, &m);for(int i=1; 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 = 0;while(!que.empty()){int u = que.front(); que.pop();for(int i=0; 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 0; } View Code Down the Pyramid 求區間交集 代碼： #include<bits/stdc++.h> #define pb push_back #define int long long using namespace std; const int maxn=3e5+10; const int mod=1e9+10+7; int32_t main() {int n; cin>>n;int ans=1e9+10;int l=0;int r=1e9+10;for(int i=1;i<=n;i++){int x; cin>>x;if(l>x){cout<<0<<endl; return 0;}int q=x-r;int p=x-l;if(p>x) p=x;if(q<0) q=0;//cout<<q<<" "<<p<<endl;l=q;r=p;ans=min(ans,r-l+1);}cout<<ans<<endl; } View Code 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_queuetypedef 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; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; 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=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x=f?-x:x; }/*-----------------------showtime----------------------*/const int maxn = 1e5;int gcd(int a, int b){if(b == 0)return a;return gcd(b, a % b);}bool check(int x){if(x == 1) return false;for(int i=2; i*i <= x; i++){if(x % i==0)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-6;b += 5e-6;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 0; } View Code Fighting Monsters 代碼： #include<bits/stdc++.h> #define pb push_back #define int long long using namespace std; const int maxn=1e6+10; const int mod=1e9+7; vector<int> vs[maxn]; int32_t main() {int n; cin>>n;for(int i=1;i<=n;i++){int x; cin>>x; vs[x].push_back(i);}int l=1;int r=1;if(vs[1].size()>=2){cout<<vs[1][0]<<" "<<vs[1][1]<<endl;return 0;}while(1){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][0]<<" "<<vs[r][0]<<endl;return 0;}}cout<<"impossible"<<endl; } View Code 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+10; const int mod=1e9+7; vector<int> vs[maxn]; int32_t main() {int n; cin>>n;for(int i=1;i<=1e6;i++){int x=i*(i+1)*(2*i+1)/6;if(x<n){continue;}if(n==x){cout<<3<<" "<<i<<endl;return 0;}if(x>n){break;}}for(int p=4;p<=64;p++){int ans=0;for(int i=1;i<=1e6;i++){int t=1;for(int c=1;c<p;c++){t*=i;}ans+=t;if(ans<n) continue;else if(ans==n){cout<<p<<" "<<i<<endl;return 0;}else{break;}}}cout<<"impossible"<<endl; } View Code 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_queuetypedef 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; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; 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=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x=f?-x:x; }/*-----------------------showtime----------------------*/const int maxn = 1e3+9;int h[maxn],v[maxn],dif[maxn];int n;bool check(int x){for(int i=1; i<=n; i++){if(dif[i] + x > 0) return true;else if(dif[i] + x < 0)return false;}return true;} int main(){scanf("%d", &n);for(int i=1; i<=n; i++) scanf("%d", &h[i]);for(int i=1; i<=n; i++) scanf("%d", &v[i]);for(int i=1; i<=n; i++) dif[i] = h[i] - v[i];int ans = 0;for(int i=0; i<=maxn; i++){if(check(i)){ans = i;break;}}printf("%d\n", ans);return 0;} View Code 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); //headconst int N = 3e5 + 10; int a[N][4]; int t[N*2][2]; vector<int> vc; int main() {int n;scanf("%d", &n);int st = -1;int tmp[4];for (int i = 1; i <= n; i++) {for (int j = 0; j < 4; j++) {scanf("%d", &a[i][j]);if(a[i][j]) {int tmp = a[i][j];if(t[tmp][0]) t[tmp][1] = i;else t[tmp][0] = i;}}swap(a[i][0], a[i][2]);for (int j = 0; j < 4; j++) {if(!a[i][j] && !a[i][(j+1)%4]) st = i;}}for (int j = 0; j < 4; j++) {if(!a[st][j] && !a[st][(j+1)%4]) {tmp[0] = tmp[1] = 0;tmp[2] = a[st][(j+2)%4];tmp[3] = a[st][(j+3)%4];break;}}if(~st);else return 0*puts("impossible");vc.pb(st);for (int j = 0; j < 4; j++) a[st][j] = tmp[j];while(true) {int now = vc.back();if(!a[now][2]) break;int id = a[now][2];int nx;if(t[id][0] == now) nx = t[id][1];else nx = t[id][0];for (int j = 0; j < 4; j++) {if(a[nx][j] == id) {tmp[0] = a[nx][j];tmp[1] = a[nx][(j+1)%4];tmp[2] = a[nx][(j+2)%4];tmp[3] = a[nx][(j+3)%4];break;}}for (int j = 0; j < 4; j++) a[nx][j] = tmp[j];if(a[nx][1]) return 0*puts("impossible");vc.pb(nx);}int m = (int)vc.size();if(n%m) return 0*puts("impossible");if(n == m) {for (int i = 0; i < n; i++) if(a[vc[i]][3]) return 0*puts("impossible");}for (int i = m; i < n; i++) {int now = vc[i-m];if(!a[now][3]) return 0*puts("impossible");int id= a[now][3];int nx;if(t[id][0] == now) nx = t[id][1];else nx = t[id][0];for (int j = 0; j < 4; j++) {if(a[nx][j] == id) {tmp[1] = a[nx][j];tmp[2] = a[nx][(j+1)%4];tmp[3] = a[nx][(j+2)%4];tmp[0] = a[nx][(j+3)%4];break;}}for (int j = 0; j < 4; j++) a[nx][j] = tmp[j];if(i%m == 0 && a[nx][0]) return 0*puts("impossible");if(i%m == m-1 && a[nx][2]) return 0*puts("impossible");if(i%m > 0 && (a[nx][0] != a[vc[i-1]][2] || a[nx][0] == 0)) return 0*puts("impossible");if(i >= n-m && a[nx][3]) return 0*puts("impossible");if(i < n-m && a[nx][3] == 0) return 0*puts("impossible");vc.pb(nx);}printf("%d %d", n/m, m);for (int i = 0; i < n; i++) {if(i%m == 0) printf("\n");printf("%d ", vc[i]);}return 0; } View Code 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); //headconst int N = 66, M = 2e3 + 5; const int INF = 0x3f3f3f3f; const double eps = 5e-6; int a[N], n, g; bool dp[M][N]; int main() {scanf("%d %d", &n, &g);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);dp[0][0] = true;for (int i = 1; i <= n; i++) {for (int j = M-1; j >= a[i]; j--) {for (int k = n; k >= 1; k--) {dp[j][k] |= dp[j-a[i]][k-1];}}}double ans = -1;for (int j = g-10; j < M; j++) {for (int i = 1; i <= n; i++) {if(dp[j][i]) {if(j+10-g <= 5*(i+1)) ans = max((j+10.0-g)/(double)(i+1), ans);}}}if(ans < -0.5) printf("impossible");else printf("%.9f\n", ans);return 0; } View Code Logic Puzzle 模擬： 代碼： #include<bits/stdc++.h> using namespace std; #define pb push_backconst int N = 110; int a[N][N]; int h, w; bool vis[N][N]; int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; int main() {scanf("%d %d", &h, &w);for (int i = 0; i <= h+1; i++) {for (int j = 0; j <= w+1; j++) {scanf("%d", &a[i][j]);}}bool f = false;for (int i = 0; i <= h+1; i++) {for (int j = 0; j <= w+1; j++) {int cnt = 0;for (int ii = -1; ii <= 1; ii++) {for (int jj = -1; jj <= 1; jj++) {int x = i + ii;int y = j + jj;if(1 <= x && x <= h && 1 <= y && y <= w) {if(vis[x][y]) cnt++;}}}int res = a[i][j] - cnt;int x = i+1, y = j+1;if(1 <= x && x <= h && 1 <= y && y <= w) {if(res < 0 || res > 1) {f = true;break;}else if(res == 1){vis[x][y] = true;}}else {if(res != 0) {f = true;break;}}}}if(f) puts("impossible");else {for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++){if(vis[i][j]) putchar('X');else putchar('.');}puts("");}}return 0; } View Code 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 = 505, M = 1e6 + 10, MM = 1e5 + 10, 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[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; void init() {for (int i = 0; i < N*N; i++) fa[i] = i, s[i].insert(i); } int get_id(int x, int y) {return (x-1)*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 = 1; 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 = 0; j < 4; j++) {int xx = x + dir[j][0];int yy = y + dir[j][1];if(xx < 1 || xx > m || yy < 1 || 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 = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {scanf("%d", &h[i][j]);vc[h[i][j]].pb({i, j});}}for (int i = 1; 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 = 1; 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 0; } View Code

轉載于:https://www.cnblogs.com/widsom/p/10290561.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的2018 German Collegiate Programming Contest (GCPC 18)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。