Last Update: July, 2018
First time post a codeforces contest.
Don’t know how to do the last one.. emm…
Save this for later
Since this is only a Div 2, so I won’t include much explanation(took me centuries to finish). Typesetting is to0 hard…
A:
Just do it
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; int N; map<string,int> mp1,mp2; int main(){ FAST_IO cin>>N; for(int i = 1; i <= N; i++){ string s; cin>>s; mp1[s]++; } for(int i = 1; i <= N; i++){ string s; cin>>s; mp2[s]++; } int ans = 0; ans += abs(mp2["M"] - mp1["M"]); string s = "S"; for(int i = 0; i <= 3; i++){ ans += abs(mp2[s] - mp1[s]); s.insert(s.begin(),'X'); } s = "L"; for(int i = 0; i <= 3; i++){ ans += abs(mp2[s] - mp1[s]); s.insert(s.begin(),'X'); } cout<<ans / 2<<endl; return 0; }
B:
A problem that requires you to think about the invariants in the sum of lights on and off.
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; int N,M; int a[maxn],sum_off,sum_on,rang[maxn]; int main(){ FAST_IO cin>>N>>M; for(int i = 1; i <= N; i++) cin>>a[i]; a[N + 1] = M; for(int i = 1; i <= N + 1; i++){ rang[i] = a[i] - a[i - 1]; } for(int i = 1; i <= N + 1; i++){ if(i % 2 == 1) sum_on += rang[i]; else sum_off += rang[i]; } int maxx = sum_on,tmp = 0,sum = 0; for(int i = 1; i <= N + 1; i++){ if(i % 2 == 1) sum += rang[i]; else sum_off -= rang[i]; tmp = sum_off + sum - 1; maxx = max(maxx,tmp); } cout<<maxx<<endl; return 0; }
C:
Using BIT or Segment Tree to transform the original problem into another dimension.
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; int N; vector<pll> v; ll cnt[maxn]; int main(){ FAST_IO cin>>N; for(int i = 1; i <= N; i++){ ll a,b; cin>>a>>b; v.push_back(pll(a,1)); v.push_back(pll(b + 1,-1)); } sort(v.begin(),v.end()); ll f = 0; for(int i = 0; i < v.size(); i++){ f += v[i].second; if(i < v.size() - 1){ if(v[i].first != v[i + 1].first){ cnt[f] += v[i + 1].first - v[i].first; } } } for(int i = 1; i <= N; i++) cout<<cnt[i]<<" "; cout<<endl; return 0; }
D:
Simple Combinatoric Problem
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e3 + 10; ll mod = 998244353; ll C[maxn][maxn],dp[maxn],a[maxn]; int N; int main(){ FAST_IO cin>>N; for(int i = 0; i <= 1000; i++){ C[i][0] = C[i][i] = 1; for(int j = 1; j < i; j++){ C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } for(int i = 1; i <= N; i++) cin>>a[i]; dp[N + 1] = 1; for(int i = N; i ; i--){ if(a[i] <= 0) continue; for(int j = i + a[i] + 1; j <= N + 1; j++){ dp[i] = (dp[i] + dp[j] * C[j - 1 - i][a[i]]) % mod; } } ll sum = 0; for(int i = 1; i <= N; i++) sum = (sum + dp[i]) % mod; cout<<sum<<endl; return 0; }
E:
Use Edge Biconnected Component to make the original graph into a tree, and find the diameter of the tree.
#pragma GCC optimize(2) #include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; int head[maxn<<1],ver[maxn<<1],nxt[maxn<<1]; int dfn[maxn],low[maxn],tot,num; bool bridge[maxn<<1]; int c[maxn],pre[maxn<<1]; int tot_bridge,N,M; int dcc; bool instac[maxn]; stack<int> S; vector<int> G[maxn]; void addedge(int x,int y){ ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot; } void tarjan(int x,int fa){ dfn[x] = low[x] = ++num; S.push(x); for(int i = head[x]; i; i = nxt[i]){ int v = ver[i]; if(v == fa) continue; if(!dfn[v]){ tarjan(v,x); low[x] = min(low[x],low[v]); } else low[x] = min(low[x],dfn[v]); } if(low[x] == dfn[x]){ int tmp; dcc++; do{ tmp = S.top(); S.pop(); c[tmp] = dcc; } while(!S.empty() && tmp != x); } } int ans,dp[maxn][2]; void dfs(int u,int fa){ for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; if(v == fa) continue; dfs(v,u); if(dp[u][1] < dp[v][1] + 1){ dp[u][0] = dp[u][1]; dp[u][1] = dp[v][1] + 1; } else dp[u][0] = max(dp[u][0],dp[v][1] + 1); } ans = max(ans,dp[u][1] + dp[u][0]); } int main(){ FAST_IO cin>>N>>M; for(int i = 1; i <= M; i++){ int u,v; cin>>u>>v; addedge(u,v); addedge(v,u); } for(int i = 1; i <= N; i++) if(!dfn[i]) tarjan(i,0); for(int i = 1; i <= N; i++){ for(int j = head[i]; j; j = nxt[j]){ int u = ver[j]; if(c[i] != c[u]){ G[c[i]].push_back(c[u]); } } } dfs(1,0); cout<<ans<<endl; return 0; }
F:
The condition of one occurrence is that the previous occurrence of the current number is not in the range l….r. Therefore, we can sort the queries, and use a Segment Tree to query the minimum occurrence index within the range l….r and see if it is less than the left bound l.
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; #define inf 0x7f7f7f7f int N,Q; int a[maxn],pos[maxn]; pii tree[maxn<<2]; void build(int cur,int l,int r){ if(l == r) { tree[cur] = make_pair(inf,l); return ; } int mid = (l + r) >> 1; build(cur<<1,l,mid); build(cur<<1|1,mid + 1,r); tree[cur] = min(tree[cur<<1],tree[cur<<1|1]); } void update(int cur,int l,int r,int a,int b,int delta){ if(a <= l && r <= b){ tree[cur].first = delta; return; } int mid = (l + r) >> 1; if(a <= mid) update(cur<<1,l,mid,a,b,delta); if(b > mid) update(cur<<1|1,mid + 1,r,a,b,delta); tree[cur] = min(tree[cur<<1],tree[cur<<1|1]); } pii query(int cur,int l,int r,int a,int b){ if(a <= l && r <= b){ return tree[cur]; } int mid = (l + r) >> 1; auto st = make_pair(inf,-1); if(a <= mid) st = min(st,query(cur<<1,l,mid,a,b)); if(b > mid) st = min(st,query(cur<<1|1,mid + 1,r,a,b)); return st; } struct que{ int l,r,id; que(int a = 0,int b = 0,int c = 0):l(a),r(b),id(c){} }; vector<que> quer; int ans[maxn]; bool cmp(que a,que b){ return a.r < b.r; } int main(){ memset(pos,-1,sizeof(pos)); FAST_IO cin>>N; for(int i = 1; i <= N; i++) cin>>a[i]; cin>>Q; for(int i = 1; i <= Q; i++){ int l,r; cin>>l>>r; quer.push_back(que(l,r,i)); } sort(quer.begin(),quer.end(),cmp); int lst = 0; build(1,1,N); for(int i = 0; i < quer.size(); i++){ int l = quer[i].l; int r = quer[i].r; for(int j = lst + 1; j <= r; j++){ if(pos[a[j]] != -1) update(1,1,N,pos[a[j]],pos[a[j]],inf); update(1,1,N,j,j,pos[a[j]]); pos[a[j]] = j; } auto it = query(1,1,N,l,r); if(it.second == -1 || it.first >= l ) ans[quer[i].id] = 0; else ans[quer[i].id] = a[it.second]; lst = r; } for(int i = 1; i <= Q; i++) cout<<ans[i]<<endl; return 0; }
G:
Seems like a Tree-DP, don’t know how to do it for now. Save this for later..