A. Sasha and Array Coloring
题目链接
题目大意：将数组分为若干个集合每个集合非空，求每个集合内最大和最小元素之差的和的最大值
数组排序后将最大和最小元素划为一个集合，次大次小一个集合，依次类推
// Problem: A. Sasha and Array Coloring
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int T;
void output(vector<int> q)
{
for(int i=0;i<q.size();i++){
cout<<q[i]<<" ";
}
cout<<endl;
}
int main()
{
cin>>T;
while(T--)
{
int n;
cin>>n;
vector<int> q;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
q.push_back(x);
}
sort(q.begin(),q.end());
// output(q);
int sum=0;
int r=q.size()-1;
int l=0;
for(l=0;l<=r;l++,r--)
{
sum+=q[r]-q[l];
}
cout<<sum<<endl;
}
return 0;
}
B. Long Long
题目链接
题目大意：给定一个整数序列，每次可以将一个连续的区间符号取反，求最少需要几步可以将所有负数变为正数。因为要求在有限步内最大的和，所以转化为将所有的负数转化为正数。
首先考虑0换号无所谓，所以先把0筛掉，接着求连续负数的字段有多少个即可。
// Problem: B. Long Long
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=2e5+10;
int T;
int a[N];
int main()
{
cin>>T;
while(T--)
{
int n;
int cnt=0;
LL sum=0,res=0;
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(x)
{
a[cnt++]=x;
sum+=abs(x);
}
}
vector<int> q;
if(cnt!=0)
{
q.push_back(a[0]<0?1:0);//将所有的连续负数子段用1表示，正数字段用0表示，连续负数字段的个数即为vector中的前缀和
for(int i=1;i<cnt;i++)
{
if((a[i]<0&&q[q.size()-1])||(a[i]>0&&q[q.size()-1]==0)) continue;
else
{
if(a[i]<0&&q[q.size()-1]==0) q.push_back(1);
else if(a[i]>0&&q[q.size()-1]==1) q.push_back(0);
}
}
}
for(int i=0,len=q.size();i<len;i++){
res+=q[i];
}
cout<<sum<<" "<<res<<endl;
}
return 0;
}
C. Sum in Binary Tree
题目链接
大意：求二叉树中到指定节点的路径的所有结点的序号之和
二叉树一个节点的父节点就是当前节点除2，左右孩子均是如此。那么不断除2直至为1所得到的结果序列就是二叉树从根节点到指定节点的路径。
// Problem: C. Sum in Binary Tree
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int T;
int main()
{
cin>>T;
while(T--)
{
LL t;
cin>>t;
LL res=0;
while(t)
{
res+=t;
t/=2;
}
cout<<res<<endl;
}
return 0;
}
D. Apple Tree
大意：一个苹果树只有两个叶子节点，可以通过摇晃苹果树来得到苹果
每次摇晃有以下两种情况：
- 若其为叶子节点则直接掉落
- 否则有一个孩子就落到孩子节点上。(多个孩子则随机到一个孩子中)
思路：由于是一棵树且只有两个叶子节点，则只有一个点有分叉的结点其余均只有一个孩子，接下来只需递归的确定以每个结点为根的子树有多少个叶子节点即可。答案只可能有1，2，4三种情况。
// Problem: D. Apple Tree
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=2e5+10;
vector<int> g[2<<17];
int ch[2<<17];
int dfs(int u,int p)
{
bool fla=false;//判断是否为非叶子结点
for(int v:g[u])
{
if(v!=p)
{
fla=true;
ch[u]+=dfs(v,u);
}
}
if(!fla) ch[u]=1;//只有叶子结点时fla才会保持false的状态
return ch[u];
}
int main()
{
int T; cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=0;i<n;i++) g[i].clear();
memset(ch,0,sizeof(ch));
for(int i=1;i<n;i++)
{
int u,v; cin>>u>>v;
u--,v--;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0,-1);
int m; cin>>m;
for(int i=0;i<m;i++)
{
int a,b; cin>>a>>b;
cout<<(LL)ch[--a]*ch[--b]<<endl;
}
}
return 0;
}
E. Tracking Segments
题目链接
大意：给定一个长度为n初始值全为0的序列a和m个区间,再给定q个步骤\(x_i\)\((1<=i<=q)\) 依次将\(a[x_i]\) 变为1，问最小要到第几步在m个区间内会有一个区间出现1的个数大于0的个数的情况。
二分答案
// Problem: E. Tracking Segments
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
int T;
int n,m,q;
int sl[N],sr[N];
int a[N],x[N];
int s[N];
bool check(int mid)
{
for(int i=0;i<mid;i++)
{
a[x[i]-1]=1;
}
for(int i=0;i<n;i++)
{
s[i+1]=s[i]+a[i];
}
for(int i=0;i<m;i++)
{
int cnt=s[sr[i]]-s[sl[i]-1];
if(cnt>(sr[i]-sl[i]+1)-cnt)
{
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>sl[i]>>sr[i];
}
cin>>q;
for(int i=0;i<q;i++)
{
cin>>x[i];
}
int l=0,r=q+1;
while(l<r)
{
for(int i=0;i<n;i++) a[i]=0;
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(r==q+1) r=-1;
cout<<r<<endl;
}
return 0;
}
F1. Omsk Metro (simple version)
题目链接
大意：给定一棵树初始时只有一个根节点权值为1，每一次会发生两种操作中的一种：
- 结点\(v_i\)后按序号加一个权重为x的结点
- 询问从根节点到指定结点是否存在一子段使得这个子段的节点的权重和为指定的k
分析：
- 权值\(x\in\{-1,1\}\) 可以得出结论是路径上最大字段和和最小字段和之间任意整数均可取到，因为可以取空，所以0也可以取到。
- 由于起点固定，所以最大最小子段只需要和0比较而不需要和之前子段的最大最小子段和比较
// Problem: F1. Omsk Metro (simple version)
// Contest: Codeforces - Codeforces Round 881 (Div. 3)
// URL: https://codeforces.com/contest/1843/problem/F1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=2e5+10;
int q,n;
vector<int> g[N];
int x[N],u[N],v[N],k[N];
int MX[N],MN[N];
void dfs(int u,int p,int mx,int mn)
{
mx=max(mx+x[u],0);
mn=min(mn+x[u],0);
MX[u]=mx,MN[u]=mn;
if(p!=-1)
{
MX[u]=max(MX[u],MX[p]);
MN[u]=min(MN[u],MN[p]);
}
for(int V:g[u]) dfs(V,u,mx,mn);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T; cin>>T;
while(T--)
{
cin>>q;
n=0;
x[0]=1;
g[0].clear();
int sz=0;
for(int i=0;i<q;i++)
{
char op[2];
cin>>op;
if(op[0]=='+')
{
int v,val;
cin>>v>>val;
g[--v].push_back(++n);
g[n].clear();
x[n]=val;
}
else
{
cin>>u[sz]>>v[sz]>>k[sz];
u[sz]--,v[sz]--;
sz++;
}
}
dfs(0,-1,0,0);
for(int i=0;i<sz;i++)
{
if(MN[v[i]]<=k[i]&&k[i]<=MX[v[i]]) puts("yes");
else puts("no");
}
}
return 0;
}