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..