以后争取补题不看别人代码，只看思路，今天就是只看思路补完的题，有点小激动。
A. Valera and Plates
水题，贪心地先放完第一种食物，在考虑第二种。
居然被卡了一会，心态要蹦 :(；
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
cin>>n>>m>>k;
int cnt1=,cnt2=;
for(int i=;i<=n;i++)
{
int g; scanf("%d",&g);
if(g==) cnt1++;
else cnt2++;
}
int ans=;
if(m<=cnt1) ans+=cnt1-m,m=;
else k+=(m-cnt1);
ans+=max(,cnt2-k);
cout<<ans<<endl;
}
B. Valera and Contest
题目大意：给你n个数，你不知道第i个是多少，但是你知道里面数的最大值和最小值，所有数的和，
以及前k大个数的和，让你构造出这n个数。
思路：按平均数来构造，有余数补上，有一点wa了一次，取膜的时候没有考虑k==n的情况，用0取了膜，
以后不能犯这个错误了！！！
#include<bits/stdc++.h>
using namespace std;
int n,k,l,r,sa,sk;
int ans[];
int main()
{
cin>>n>>k>>l>>r>>sa>>sk;
int g=sk/k,sg=sk%k;
int now=;
for(int i=;i<=k;i++)
{
ans[i]=g;
if(i<=sg) ans[i]++;
now+=ans[i];
}
if(k<n)
{
int ssum=sa-sk;
g=ssum/(n-k),sg=ssum%(n-k);
for(int i=;i<=n-k;i++)
{
ans[i+k]=g;
if(i<=sg) ans[i+k]++;
}
} for(int i=;i<=n;i++) printf("%d%c",ans[i],i==n? '\n':' ');
return ;
}
C. Valera and Elections
题目大意：有一棵树，有些边有问题，需要修复，修复的方法就是选出节点的子集，每个选中的节点
修复这个节点到 1 节点的所有有问题的边，问你最少需要选几个节点。
思路：还是比较好想的，直接从1开始dfs，用数组ans保存答案，top为其栈顶，每次dfs到一个节点，
先记录当前栈顶的值，回溯回来后，看当前栈顶是不是和第一次进入的时候一样，如果一样说明，
这个节点的下面没有有问题的边，如果这个节点通向其父节点的边是有问题的那么这个节点一定要选，
如果当前栈顶和第一次进入的时候不一样，说明这个节点的子节点中已经有一个作为答案了，
当前节点不需要选。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N=1e5+;
vector<pii> e[N];
int n,tot=,ans[N];
void dfs(int u,int p,int pe)
{
int now=tot;
for(int i=;i<e[u].size();i++)
{
pii to=e[u][i];
if(to.fi==p) continue;
dfs(to.fi,u,to.se);
}
if(pe== && tot==now) ans[++tot]=u;
}
int main()
{
cin>>n;
for(int i=;i<n;i++)
{
int from,to,op;scanf("%d%d%d",&from,&to,&op);
e[from].pb(mk(to,op));
e[to].pb(mk(from,op));
}
dfs(,-,-);
cout<<tot<<endl;
for(int i=;i<=tot;i++) printf("%d%c",ans[i],i==tot?'\n':' ');
return ;
}
D. Valera and Fools
题目大意：有n个笨蛋站在一排，每个人手里都有枪，他们的编号分别为1->n，每个人都有一个打死人
的概率(0-100)%，现在进行k轮游戏，每一轮，除编号最小的人朝编号第二小的人开枪，其他人都向
编号最小的人开枪，问你k轮之中有几种不同的情形，即活着的人不同的情况。
QAQ 不会写啊，知道是dp也不会写，看来我dp还是太弱了，该写写dp的专题了！！！
思路：我们首先要明确一点，第三大编号即以上的人一定是活着的，那么我们用dp[ i ][ j ]，表示到达
最小编号为i 第二小编号为 j 的情形 最少需要几轮游戏。初始状态 dp[ 1 ][ 2 ]=0，这样就能写出状态
转移方程了。
#include<bits/stdc++.h>
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
int n,k,dp[N][N],p[N],mx[N];//mx[i] 表示i及以后概率的最大值。
int main()
{
cin>>n>>k;
for(int i=;i<=n;i++) scanf("%d",&p[i]);
for(int i=n;i>=;i--) mx[i]=max(mx[i+],p[i]);
memset(dp,inf,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
if(dp[i][j]>=inf) continue;
if(mx[j]> && p[i]<) dp[j][j+]=min(dp[j][j+],dp[i][j]+);
if(p[i]> && mx[j]!=) dp[i][j+]=min(dp[i][j+],dp[i][j]+);
if(mx[j]> && p[i]>) dp[j+][j+]=min(dp[j+][j+],dp[i][j]+);
}
}
int ans=;
for(int i=;i<=n+;i++)//i,j如果大于n说明 只剩一个人或者没有人或者。
{
for(int j=i+;j<=n+;j++)
{
if(dp[i][j]<=k) ans++; }
}
printf("%d\n",ans);
return ;
}
E. Valera and Queries
题目大意：给你n条线段，然后又m组询问，每一组询问有cnt[ i ]个数，问你这些线段中有多少是
覆盖了这里面任意一个点的，覆盖1个2个...都可以。
一看就知道是线段树(树状数组)的题目，可是不会写啊！！
思路：我们可以很巧妙地转换一下，求覆盖的线段，可以先求一个点都没有覆盖的线段，然后总的
减去就好了，这样问题就变成了，给你的cnt[ i ]个点相邻的两个之间有多少条线段。这样我们就能用
树状数组了，先将线段按 r 值排序，注意如果是保存前缀，一定是要用 r 值排序的。每个树状数组的
节点保存，所管理的区域范围内的 l 的值，并将 l 值排好序。找位于相邻两点之间的线段数量时，
树状数组每个节点lower_bound一下就好了。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=*1e5+;
int n,m,top=,x[N];//x 保存r的值，离散化的时候去重，排序。
vector<int> bt[N],o[N];
pii p[N];
bin_search(int tar)// 离散化，r真正地值查找对应的编号。
{
int l=,r=top;
while()
{
int mid=(l+r)>>;
if(x[mid]==tar) return mid;
else if(x[mid]<tar) l=mid+;
else r=mid-;
}
}
int low_bit(int u){return u&-u;}
void build()
{
for(int i=;i<top;i++)
{
int up=low_bit(i);
for(int j=i;j>i-up;j--)
{
for(int k=;k<o[j].size();k++)
{
int now=o[j][k];
bt[i].pb(now);
}
}
sort(bt[i].begin(),bt[i].end());
}
}
int query(int u,int l)
{
int sum=;
while(u>)
{
int c=upper_bound(bt[u].begin(),bt[u].end(),l)-bt[u].begin();
sum+=bt[u].size()-c;
u-=low_bit(u);
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=;i<n;i++)
{
scanf("%d%d",&p[i].fi,&p[i].se);
x[top++]=p[i].se;
}
sort(x,x+top);
top=unique(x,x+top)-x;
for(int i=;i<n;i++)
{
int g=bin_search(p[i].se);
o[g].pb(p[i].fi);
}
build();
int sum=,q,p;
while(m--)
{
sum=;p=;
int cnt; scanf("%d",&cnt);
for(int i=;i<=cnt;i++)
{
scanf("%d",&q);
int pos=lower_bound(x+,x+top,q)-x;
pos--;
sum+=query(pos,p);
p=q;
}
sum+=query(top-,p);
printf("%d\n",n-sum);
}
return ;
}
ps: e题网上的作法貌似比我的快，用的也是树状数组，不过他是把题目原来的线段和后来两点间的
线段保存在一起，最后一起离线处理，把所有线段都按 l 的大小降序（如果 l 一样,r小的优先），这样
从头往后扫，这样就保证了后面的线段的 l 值不会大于前面的，这样只要看 r 值就行了，r的个数
保存在树状数组中。