C - Splitting Pile

枚舉從哪里開始分的即可

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 200005 #define eps 1e-12 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } int N; int64 s[MAXN]; void Solve() {read(N);for(int i = 1 ; i <= N ; ++i) read(s[i]);for(int i = 1 ; i <= N ; ++i) s[i] += s[i - 1];int64 ans = abs(s[N] - 2 * s[1]);for(int i = 1 ; i < N ; ++i) {ans = min(ans,abs(s[N] - 2 * s[i]));}out(ans);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve(); }

D - Fennec VS. Snuke

看樹上這段鏈從Fennec開始數(shù)第K / 2和K / 2+1的邊斷開之后，分成的兩個(gè)子樹哪個(gè)結(jié)點(diǎn)多
Fennec只有當(dāng)節(jié)點(diǎn)數(shù)大于Snuke才會(huì)勝利

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 100005 #define eps 1e-12 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } struct node {int to,next; }E[MAXN * 2]; int head[MAXN],sumE,N; int dep[MAXN],fa[MAXN],siz[MAXN]; void add(int u,int v) {E[++sumE].to = v;E[sumE].next = head[u];head[u] = sumE; } void dfs(int u) {dep[u] = dep[fa[u]] + 1;siz[u] = 1;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != fa[u]) {fa[v] = u;dfs(v);siz[u] += siz[v];}} } void Solve() {read(N);int u,v;for(int i = 1 ; i < N ; ++i) {read(u);read(v);add(u,v);add(v,u);}dfs(1);int t = dep[N] / 2 - 1;u = N;while(t--) {u = fa[u];}if(N - siz[u] > siz[u]) puts("Fennec");else puts("Snuke"); } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve(); }

E - Awkward Response

如果不為1后面接的只有0的形式，那么問(wèn)出第一個(gè)\(10^k\)為N則證明數(shù)字有k位，然后可以通過(guò)二分，判斷中間值是否小于當(dāng)前值可以把mid擴(kuò)大10倍，這樣可以知道中間值的字典序是否大于還是小于n，因?yàn)殚L(zhǎng)度相等字典序順序就是大小順序，所以可行
如果是1后面接的只有0，那么問(wèn)出第一個(gè)合法的k個(gè)9，這個(gè)數(shù)就是\(10^{k - 1}\)

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 100005 #define eps 1e-12 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } bool Query(int64 t) {putchar('?');space;out(t);enter;fflush(stdout);char s[5];scanf("%s",s);return s[0] == 'Y'; } void Solve() {int64 v = 1;bool f = 0;for(int i = 1 ; i <= 10 ; ++i) {if(!Query(v)) {f = 1;v /= 10;break;}v *= 10;}if(!f) {v = 1;for(int i = 1 ; i <= 10 ; ++i) {if(Query(v * 10 - 1)) {putchar('!');space;out(v);enter;return;}v *= 10;}}int64 L = v,R = min(v * 10 - 1,(int64)1e9);while(L < R) {int64 mid = (L + R + 1) >> 1;if(!Query(mid * 10)) L = mid;else R = mid - 1;}putchar('!');space;out(L + 1);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve(); }

F - Mole and Abandoned Mine

為啥算完2s跑出來(lái)不到0.1s？？？
atc擴(kuò)充我的想象力系列？？？
這個(gè)就是把這唯一一條路徑挑出來(lái)，肯定是希望這條路徑和路徑上每個(gè)點(diǎn)上掛的一個(gè)聯(lián)通塊價(jià)值最大，然后用總路徑價(jià)值減掉
然后dp[i][S]表示當(dāng)前走到第i個(gè)點(diǎn)，已經(jīng)擴(kuò)充的點(diǎn)集是S，就是每次路徑往下走一個(gè)點(diǎn)，或者擴(kuò)充一個(gè)包括i其余的點(diǎn)不在S中的點(diǎn)集即可，復(fù)雜度\(O(N\times 3^{N})\)
然后我過(guò)于智障寫錯(cuò)了好幾遍，cao

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define MAXN 10005 #define eps 1e-12 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } int N,M; struct node {int to,next,val; }E[1005]; int sumE,head[25],pos[(1 << 15) + 5]; int f[16][(1 << 15) + 5],h[16][(1 << 15) + 5],sum[(1 << 15) + 5]; void add(int u,int v,int c) {E[++sumE].to = v;E[sumE].next = head[u];E[sumE].val = c;head[u] = sumE; } inline int lowbit(int x) {return x & (-x); } void Init() {read(N);read(M);int u,v,c;for(int i = 1 ; i <= M ; ++i) {read(u);read(v);read(c);add(u,v,c);add(v,u,c);h[u][1 << v - 1] = c;h[v][1 << u - 1] = c;}for(int i = 1 ; i <= N ; ++i) {for(int j = 1 ; j < (1 << N) ; ++j) {if(lowbit(j) == j) continue;h[i][j] = h[i][j - lowbit(j)] + h[i][lowbit(j)];}}for(int i = 1 ; i <= N ; ++i) pos[(1 << i - 1)] = i;for(int i = 1 ; i < (1 << N) ; ++i) {sum[i] = sum[i - lowbit(i)] + h[pos[lowbit(i)]][i - lowbit(i)];} } void Solve() {for(int i = 1 ; i <= N ; ++i) {for(int j = 0 ; j < (1 << N) ; ++j) {f[i][j] = -1e9;}}f[1][1] = 0;for(int j = 0 ; j < (1 << N - 1) ; ++j) {for(int i = 1 ; i <= N ; ++i) {int S = j << 1 | 1;if(!(S & (1 << i - 1))) continue;int L = S ^ (1 << i - 1);for(int T = L; T ; T = (T - 1) & L) {if(f[i][S ^ T] >= 0)f[i][S] = max(f[i][S],f[i][S ^ T] + sum[T ^ (1 << i - 1)]);}if(f[i][S] >= 0) {for(int k = head[i] ; k ; k = E[k].next) {int v = E[k].to;if(!(S & (1 << v - 1))) {f[v][S ^ (1 << v - 1)] = max(f[v][S ^ (1 << v - 1)],f[i][S] + E[k].val);}}}}}out(sum[(1 << N) - 1] - f[N][(1 << N) - 1]);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

轉(zhuǎn)載于:https://www.cnblogs.com/ivorysi/p/10507718.html

總結(jié)

以上是生活随笔為你收集整理的【AtCoder】ARC078的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。