道心破�??
A. Sasha and Array Coloring
题面
显然取一大一小染一种颜色作差
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
int a[N];
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int cnt=0;
for(int i=1,j=n;i<=j;i++,j--)
{
cnt+=a[j]-a[i];
}
cout<<cnt<<'\n';
}
return 0;
}B. Long Long
题面
很明显最大的和就是所有数的绝对值的和
最小操作数就是连续的非全零的非正数段的个数，统计一下就行
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
ll sum=0;
ll cnt=0;
a[0]=1;
a[n+1]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=abs(a[i]);
}
int j=1;
for(int i=1;i<=n;i++)
{
if(a[i]<=0)
{
cnt++;
int j=i;
bool flag=false;
for(j=i;j<=n;j++)
{
if(a[j]>0)
break;
}
for(int k=i;k<j;k++)
{
if(a[k]!=0)
{
flag=true;
break;
}
}
if(!flag)
cnt--;
i=j-1;
}
}
cout<<sum<<' '<<cnt<<'\n';
}
return 0;
}C. Sum in Binary Tree
题面
就是从底向跟的遍历
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
ll n;
cin>>n;
ll sum=0;
while(n)
{
sum+=n;
n/=2;
}
cout<<sum<<'\n';
}
return 0;
}D. Apple Tree
题面
需要统计每点的子树的叶子个数
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
// typedef long long ll;
#define int long long
const int N=2e5+5;
vector<int>s[N],k[N];
bitset<N>vis,v;
vector<int>root;
int countt[N];
void dfs(int x)
{
if(vis[x])
return;
vis[x]=1;
for(auto it:k[x])
{
if(vis[it])
continue;
s[x].push_back(it);
dfs(it);
}
}
int Dfs(int x)
{
if(s[x].size()==0)
{
countt[x]=1;
return countt[x];
}
for(auto it:s[x])
{
countt[x]+=Dfs(it);
}
return countt[x];
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
memset(countt,0,sizeof(countt));
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
k[u].push_back(v);
k[v].push_back(u);
}
dfs(1);
int q;
cin>>q;
Dfs(1);
while(q--)
{
int x,y;
cin>>x>>y;
cout<<countt[x]*countt[y]<<'\n';
}
for(int i=1;i<=n;i++)
{
s[i].clear();
k[i].clear();
}
vis.reset();v.reset();
}
return 0;
}简化后的代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
vector<int>s[N];
int cnt[N];
int dfs(int x,int f)
{
if(s[x].size()==1&&s[x][0]==f)
{
cnt[x]++;
return cnt[x];
}
for(auto it:s[x])
{
if(it!=f)
cnt[x]+=dfs(it,x);
}
return cnt[x];
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
s[i].clear();
cnt[i]=0;
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
s[u].push_back(v);
s[v].push_back(u);
}
dfs(1,0);
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
cout<<cnt[x]*cnt[y]<<'\n';
}
}
return 0;
}E. Tracking Segments
����
��������ҵĶ���д��
֮ǰд����
#include<bits/stdc++.h>
using namespace std;
int main()
{
int l=1,r=q,ans=-1;
while(l<r)
{
int mid=(l+r)>>1;
if(judge(mid))
{
r=mid;
ans=mid;
}
else
l=mid+1;
}
}֮ǰ��д��A�������⣬��֪������д����
����һ��д�����ܹ�
AC���룺
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<pair<int,int>>s(m);
for(int i=0;i<m;i++)
cin>>s[i].first>>s[i].second;
int q;
cin>>q;
vector<int>p(q);
for(int i=0;i<q;i++)
cin>>p[i];
int l=1,r=q,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
vector<int>sum(n+1,-1);
for(int i=0;i<mid;i++)
sum[p[i]]=1;
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]+=sum[i-1];
bool flag=false;
for(int i=0;i<m;i++)
{
if(sum[s[i].second]-sum[s[i].first-1]>0)
{
flag=true;
break;
}
}
if(flag)
{
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
cout<<ans<<'\n';
}
return 0;
}