C - Multiple Gift

題解

首項(xiàng)是X，每次乘個(gè)2，暴力統(tǒng)計(jì)

代碼

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 2005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;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); } int64 X,Y;int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifread(X);read(Y);int l = 1;while(X <= Y / 2) {++l;X *= 2;}out(l);enter; }

D - Wide Flip

題解

從大到小枚舉K（也可以二分）
如果\(2K <= N\)，此時(shí)\(K\)一定合法
否則看前\(K\)個(gè)和后\(K\)個(gè)交出來的中間一段，這段的前面和后面1和0是可以單個(gè)位置隨便改的（用一次K + 1的區(qū)間再用一次K的區(qū)間）
只要看中間一段是不是全1或者全0即可

代碼

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 2005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;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); } char s[1000005]; int sum[100005],N; int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifscanf("%s",s + 1);N = strlen(s + 1);for(int i = 1 ; i <= N ; ++i) {sum[i] = sum[i - 1];if(s[i] == '1') sum[i]++;}for(int K = N ; K >= 1 ; --K) {int r = K;int l = N - K + 1;if(l > r) {out(K);enter;return 0;}if(sum[r] - sum[l - 1] == 0 || sum[r] - sum[l - 1] == r - l + 1) {out(K);enter;return 0;}} }

E - Papple Sort

題解

只要每次把靠邊的一個(gè)字符的匹配點(diǎn)找出來同樣后移然后一起刪除即可
就是討論一下
...A...A...B...B..
A要和這個(gè)一對B交換兩次
B如果要過去也要換兩次，所以都一樣
A..B..A..B
A要和B換一次，如果B到外面也是和A換一次，所以都一樣
樹狀數(shù)組維護(hù)一下前綴有多少數(shù)即可

代碼

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 200005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;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); } char s[MAXN]; int N; vector<int> c[30]; bool vis[MAXN]; int tr[MAXN]; void Init() {scanf("%s",s + 1);N = strlen(s + 1); } int lowbit(int x) {return x & -x;} void Insert(int x,int v) {while(x <= N) {tr[x] += v;x += lowbit(x);} } int Query(int x) {int res = 0;while(x > 0) {res += tr[x];x -= lowbit(x);}return res; } void Solve() {int cnt = 0;for(int i = N ; i >= 1 ; --i) {c[s[i] - 'a'].pb(i);}for(int i = 0 ; i < 26 ; ++i) {if(c[i].size() & 1) ++cnt;}if(cnt >= 2) {puts("-1");return;}for(int i = 1 ; i <= N ; ++i) Insert(i,1);int64 ans = 0;int k = 0;for(int i = N ; i >= 1 ; --i) {if(vis[i]) continue;int t = c[s[i] - 'a'].back();c[s[i] - 'a'].pop_back();if(t == i){ ++k;continue;}ans += Query(t - 1) + k;vis[t] = 1;Insert(t,-1);}out(ans);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

F - Christmas Tree

題解

啊這個(gè)只要dp一下第一個(gè)值再二分。。。二分判的方法是……
woc這不NOIPD1T3啊怎么一模一樣啊

代碼

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 100005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;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; struct node {int to,next; }E[MAXN * 2]; int head[MAXN],sumE; int dp[MAXN],A,lim,res; int val[MAXN],tot; bool vis[MAXN]; void add(int u,int v) {E[++sumE].to = v;E[sumE].next = head[u];head[u] = sumE; } void Init() {read(N);int a,b;for(int i = 1 ; i < N ; ++i) {read(a);read(b);add(a,b);add(b,a);}} void dfs(int u,int fa) {int son = 0;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != fa) {dfs(v,u);++son;dp[u] += dp[v];}}dp[u] -= son / 2;if(son % 2 == 0 && fa) dp[u]++; } struct BIT {int tr[MAXN],s;void clear() {for(int i = 1 ; i <= s ; ++i) tr[i] = 0;}int lowbit(int x) {return x & -x;}int query(int x) {int res = 0;while(x > 0) {res += tr[x];x -= lowbit(x);}return res;}void insert(int x,int v) {while(x <= s) {tr[x] += v;x += lowbit(x);}}int find_max() {int L = 1,R = s;int x = query(s);if(x == 0) return 0;while(L < R) {int m = (L + R + 1) >> 1;if(query(m - 1) != x) L = m;else R = m - 1;}return L;} }BST; void calc(int u,int fa) {for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != fa) {calc(v,u);}}tot = 0;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != fa) {val[++tot] = dp[v];}}if(!tot) {dp[u] = 1;++res;return;}BST.clear();sort(val + 1,val + tot + 1);for(int i = 1 ; i <= tot ; ++i) vis[i] = 1;BST.s = tot;int p = 0;for(int i = tot ; i >= 1 ; --i) {if(!vis[i]) continue;while(p < i && val[p + 1] + val[i] <= lim) {++p;BST.insert(p,1);}if(p >= i) BST.insert(i,-1);int t = BST.find_max();if(t) {vis[t] = 0;vis[i] = 0;BST.insert(t,-1);--res;}}if(fa) {dp[u] = 1;++res;for(int i = 1 ; i <= tot ; ++i) {if(vis[i]) {if(val[i] + 1 > lim) break;dp[u] += val[i];--res;break;}}} } bool check(int m) {lim = m;res = 0;calc(1,0);return res <= A; } void Solve() {dfs(1,0);out(dp[1]);space;A = dp[1];int L = 1,R = N - 1;while(L < R) {int mid = (L + R) >> 1;if(check(mid)) R = mid;else L = mid + 1;}out(R);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

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

總結(jié)

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

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