codeforces-1132 (div2)
生活随笔
收集整理的這篇文章主要介紹了
codeforces-1132 (div2)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?
A.發現b的個數沒有意義，a不等于d一定不可行，c不管多少都算一個，如果只有c沒有ad也不可行
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 110; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int main(){LL a,b,c,d;scanf("%lld%lld%lld%lld",&a,&b,&c,&d);c = min(c,1ll);if((!a & !d) && c) puts("0");else if(a != d) puts("0");else puts("1");return 0; }A
?
B.顯然求出所有的和，排序之后，查詢的時候減去K大的值就可以了。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 3e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; LL a[maxn]; bool cmp(LL a,LL b){return a > b; } int main(){Sca(N);LL sum = 0;for(int i = 1; i <= N; i ++){Scl(a[i]);sum += a[i];} sort(a + 1,a + 1 + N,cmp);int q = read();while(q--){int t = read();printf("%lld\n",sum - a[t]);}return 0; }B
?
C.顯然可以先算出每個編號的墻被刷的數量以及全刷的話刷的總數，然后枚舉兩面不刷的墻，減去他們的貢獻即可。
唯一的問題在于O(1)求出兩面墻不刷之后刷不上東西的墻，用兩個前綴和分別維護只刷了一發的墻和只刷了兩發的墻，分類討論即可。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 5010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; PII P[maxn]; int pre1[maxn],pre2[maxn]; bool cmp(PII a,PII b){return a.fi < b.fi; } int main(){Sca2(N,M);for(int i = 1; i <= M ; i ++){int l = read(),r = read();P[i].fi = l,P[i].se = r;for(int j = l; j <= r; j ++) a[j]++;}int ans = 0,sum = 0;;for(int i = 1; i <= N ; i ++){pre1[i] = pre1[i - 1]; pre2[i] = pre2[i - 1];if(a[i] == 1) pre1[i]++;if(a[i] == 2) pre2[i]++;if(a[i]) sum++;}sort(P + 1,P + 1 + M,cmp);for(int i = 1; i <= M ; i ++){for(int j = i + 1; j <= M ; j ++){int flag = 0;if(P[i].se < P[j].fi){flag = pre1[P[i].se] - pre1[P[i].fi - 1] + pre1[P[j].se] - pre1[P[j].fi - 1];}else if(P[j].se < P[i].se){flag = pre2[P[j].se] - pre2[P[j].fi - 1] + pre1[P[j].fi - 1] - pre1[P[i].fi - 1] + pre1[P[i].se] - pre1[P[j].se]; }else{flag = pre1[P[j].fi - 1] - pre1[P[i].fi - 1] + pre2[P[i].se] - pre2[P[j].fi - 1] + pre1[P[j].se] - pre1[P[i].se];}ans = max(ans,sum - flag);}}Pri(ans);return 0; }C
?
D.二分 + check，check里面一個優先隊列的小貪心，時間復雜度O(n * (logn) * (logn) )
結果竟然TLE了，一度想找O(n)的check但是因為菜放棄了。
后來發現是在堆比較函數里，形如a.a / a.b < b.a / b.b這樣的操作會提高計算的常數，需要提前計算好答案在比較
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; LL read(){LL x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; struct Node{LL a,b,day;Node(){}Node(LL a,LL b,LL day):a(a),b(b),day(day){}inline friend bool operator < (Node a,Node b){return a.day > b.day;} }node[maxn]; inline bool check(LL x){priority_queue<Node>Q;for(register int i = 1; i <= N ; i ++) Q.push(node[i]);for(register int i = 1; i < K ;i ++){Node u = Q.top(); Q.pop();u.a += x; u.day = u.a / u.b;Q.push(u);if(Q.top().day < i) return false;}return true; } LL solve(){LL l = 0,r = 1ll * K * 1e7 + K;LL ans = -1;while(l <= r){LL m = l + r >> 1;if(check(m)){r = m - 1;ans = m;}else{l = m + 1;}}return ans; } inline bool cmp(Node a,Node b){return a.a / a.b < b.a / b.b; } int main(){Sca2(N,K);for(register int i = 1; i <= N ; i ++) node[i].a = read();for(register int i = 1; i <= N ; i ++){node[i].b = read();node[i].day = node[i].a / node[i].b;} sort(node + 1,node + 1 + N,cmp);Prl(solve());return 0; }D
?
E.感覺像熟悉的背包問題，但是物品的數量和背包的容量大的夸張，所以需要用其他的方法。
對于數量很多這個情況，可以考慮像背包的二進制優化一樣，變為很多更大的小物品并且不影響可以組成的容量種類。
由于背包的容量很大，所以從尋常的迭代查找變成了dfs + 剪枝搜尋的方法，用dfs(i,j)表示當前容量為i并且用到了前j個物品，map<pair<int,LL>,bool>作為vis標記去重之后，再用維護一個物品體積的后綴和方便dfs結束。
雖然這還是TLE了，但是我把所有物品體積從大到小sort了一發就過了
（看了題解似乎有更科學簡單的做法？嗯？？？）
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; LL W; map<LL,LL>P; LL S[maxn],pre[maxn],ans; int top; map<pair<LL,int>,bool>vis; bool cmp2(LL a,LL b){return a > b; } void dfs(LL t,int p){if(vis[mp(t,p)]) return; vis[mp(t,p)] = 1;if(p == top){ans = max(ans,t);return;}if(t + pre[p + 1] <= W){ans = max(ans,t + pre[p + 1]);return;}if(t + S[p + 1] <= W) dfs(t + S[p + 1],p + 1);dfs(t,p + 1); } int main(){Scl(W);top = 0;priority_queue<LL,vector<LL>,greater<LL> >Q;for(int i = 1; i <= 8; i ++){LL x; Scl(x); P[i] = x;if(x) Q.push(i);}while(!Q.empty()){LL u = Q.top(); Q.pop();LL n = P[u] * u;P[u] = 0;LL now = u;while(n >= now){P[now]++;if(P[now] == 1 && now > u) Q.push(now);n -= now;now <<= 1;}P[n]++;if(n > u && P[n] == 1) Q.push(n);while(P[u]--) S[++top] = u;}sort(S + 1,S + 1 + top,cmp2);for(int i = top; i >= 1; i --){pre[i] = S[i] + pre[i + 1];}dfs(0,0);Prl(ans);return 0; }E
?
F.感覺很像區間dp的一道題，實際上確實是區間dp，比較常規的dp[l][r]維護區間內的操作次數最小值。
比較麻煩的是區間的更新，很顯然擴展的時候如果擴展出去的恰好和兩端相等就不需要增加操作次數。
其次如果兩端相等，可以從用中間len - 2長度區間 + 1的次數更新。
當然少不了長區間由左區間合并右區間的操作，顯然如果交界處相等，更新答案是兩者相加的答案 - 1
到了這一步事實上還過不了第一個樣例abaca
需要增加一步，如果l，r之間有一個元素str[i]和str[r]相等，答案更新dp[l][i] + dp[i + 1][r - 1] + dp[r][r] - 1;
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 510; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; char str[maxn]; int dp[maxn][maxn]; int main(){Sca(N);scanf("%s",str + 1);for(int i = 1; i <= N ; i ++) dp[i][i] = 1;for(int len = 2; len <= N ; len++){for(int l = 1; l + len - 1 <= N; l ++){int r = l + len - 1;dp[l][r] = INF;if(str[r] == str[r - 1]) dp[l][r] = min(dp[l][r],dp[l][r - 1]);else dp[l][r] = min(dp[l][r],dp[l][r - 1] + 1);if(str[l] == str[l + 1]) dp[l][r] = min(dp[l][r],dp[l + 1][r]);else dp[l][r] = min(dp[l][r],dp[l + 1][r] + 1);if(str[l] == str[r]) dp[l][r] = min(dp[l][r],dp[l + 1][r - 1] + 1);for(int k = l; k < r; k ++){if(str[k] == str[k + 1]) dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r] - 1);else dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r]);if(str[k] == str[r]) dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r - 1]);}}}Pri(dp[1][N]);return 0; }F
?
G.題意不是很容易懂，反正就是求所有K長度區間內的最長貪心子序列，最長貪心子序列的定義是每個元素后接所有第一個比他大的元素。
顯然dp[i]表示從i出發的最長貪心子序列。手動模擬一下更新的樣例，會發現在j位置更新，就是將k + 1 ~ j 位置的dp[i]全部++；k是左邊第一個dp[k]大于等于dp[j]的位置。
那就線段樹維護幾個區間最大值，再區間更新一下就好了。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 1e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; struct Tree{int l,r,lazy;int Max,dp; }tree[maxn << 2]; void Build(int t,int l,int r){tree[t].l = l; tree[t].r = r;tree[t].lazy = 0;if(l == r){tree[t].Max = a[l];tree[t].dp = 1;return;}int m = l + r >> 1;Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);tree[t].dp = max(tree[t << 1].dp,tree[t << 1 | 1].dp);tree[t].Max = max(tree[t << 1].Max,tree[t << 1 | 1].Max); } int query(int t,int l,int r,int p){if(tree[t].l == tree[t].r){if(tree[t].Max < p) return 0;return tree[t].l;}if(l <= tree[t].l && tree[t].r <= r){if(tree[t << 1 | 1].Max >= p) return query(t << 1 | 1,l,r,p);else return query(t << 1,l,r,p);}int m = (tree[t].l + tree[t].r) >> 1;if(r <= m) return query(t << 1,l,r,p);else if(l > m) return query(t << 1 | 1,l,r,p);else{int ans = query(t << 1 | 1,m + 1,r,p);if(ans) return ans;return query(t << 1,l,m,p);} } void Pushdown(int t){if(tree[t].lazy){tree[t << 1].lazy += tree[t].lazy;tree[t << 1 | 1].lazy += tree[t].lazy;tree[t << 1].dp += tree[t].lazy;tree[t << 1 | 1].dp += tree[t].lazy;tree[t].lazy = 0;} } void update(int t,int l,int r){if(l <= tree[t].l && tree[t].r <= r){tree[t].lazy++;tree[t].dp++;return ;}Pushdown(t);int m = (tree[t].l + tree[t].r) >> 1;if(r <= m) update(t << 1,l,r);else if(l > m) update(t << 1 | 1,l,r);else{update(t << 1,l,m);update(t << 1 | 1,m + 1,r);}tree[t].dp = max(tree[t << 1].dp,tree[t << 1 | 1].dp); } int query(int t,int l,int r){if(l <= tree[t].l && tree[t].r <= r) return tree[t].dp;Pushdown(t);int m = (tree[t].l + tree[t].r) >> 1;if(r <= m) return query(t << 1,l,r);else if(l > m) return query(t << 1 | 1,l,r);else return max(query(t << 1,l,m),query(t << 1 | 1,m + 1,r)); } int main(){Sca2(N,K);for(int i = 1; i <= N ; i ++) Sca(a[i]);Build(1,1,N);for(int i = 2; i <= K - 1; i ++){int p = query(1,1,i - 1,a[i]);// cout << p + 1 << " " << i - 1 << endl;if(p + 1 <= i - 1) update(1,p + 1,i - 1);}for(int i = K; i <= N ; i ++){if(K != 1){int p = query(1,i - K + 1,i - 1,a[i]);if(!p) p = i - K;// cout << p + 1 << " " << i - 1 << endl;if(p + 1 <= i - 1) update(1,p + 1,i - 1);}printf("%d ",query(1,i - K + 1,i));}return 0; }G
?
轉載于:https://www.cnblogs.com/Hugh-Locke/p/10712739.html
總結
以上是生活随笔為你收集整理的codeforces-1132 (div2)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： shell脚本实例
- 下一篇： 婴儿试管一次多少钱啊？