A：
从最左边向右的牛，和最右边向左的牛中取影响最小的先挤奶。一直比下去。
code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 200010
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000000007;
const double EPS=1e-7;
int n;
int a[N],l[N],r[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
l[i]+=l[i-1]+(a[i]==0);
r[i]+=r[i-1]+(a[i]==1);
}
int L,R;
for(int i=1;i<=n;i++) if(a[i]==1){
L=i;
break;
}
for(int i=n;i>=1;i--) if(a[i]==0){
R=i;
break;
}
ll ans=0;
for(int i=L,j=R;i<j;){
while(i<=n && a[i]!=1) i++;
while(j>=1 && a[j]!=0) j--;
if(i>=j || i==n+1 || j==0) break;
ans+=min(l[j]-l[i],r[j]-r[i-1]);
if(l[j]-l[i]<r[j]-r[i-1]) i++;
else j--;
}
cout<<ans<<endl;
return 0;
}
B:
这题应该改成D题的。。。总感觉这场难度顺序放错了。。
这题的做法是这样的。
黄点是人在的位置，蓝点是不可经过的点。
对于(x,y)这个蓝点，如果在它右边的Y+1的地方，x-1及以下的位置有蓝点的话，那么这两个蓝点就能形成一条封锁线。
封锁线以下的区域是不可能走到的（即灰色段）。如果封锁线组成的分锁链能完全分隔(1,1)和(n,n)那么就无法到达，否则答案必然是2*n-2。
封锁线可以用有向边表示。
所以我们从左下的蓝点开始，从左往右连，从下往上连，到右上的蓝点。如果存在那么一条路径，能从左下的蓝点走到右上的蓝点，那么说明能分隔开。这里的左下指的是（x==n || y==1），右上(x==1 || y==n)，必须是这样在左下边界的蓝点走到右上边界的蓝点才能完全分隔开(1,1)和(n,n)。
上面说的是以y坐标为基准的情况，x的也类似处理。
最后封锁链可能类似这样：
图画的丑了点。。。不喜勿喷。。。
code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 100010
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000000007;
const double EPS=1e-7;
map<int,set<PI > > line[2];
vector<int> e[N];
bool vis[N];
void dfs(int u){
vis[u]=true;
for(int i=0;i<e[u].size();i++)
if(!vis[e[u][i]]) dfs(e[u][i]);
}
void solve(int op){
map<int,set<PI > >::iterator i;
set<PI >::iterator j,k;
for(i=line[op].begin();i!=line[op].end();i++){
int cur=i->first;
for(j=line[op][cur].begin();j!=line[op][cur].end();j++){
set<PI > &next=line[op][cur+1];
k=next.lower_bound((PI){j->first-1,0});
if(k!=next.end()){
if(op==0) // down to up
e[k->second].push_back(j->second);
else //left to right
e[j->second].push_back(k->second);
}
}
}
}
int main(){
int n,m,s=0,t;
scanf("%d%d",&n,&m);
t=m+1;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
line[0][x].insert((PI){y,i});
line[1][y].insert((PI){x,i});
if(x==n || y==1) e[t].push_back(i);
if(x==1 || y==n) e[i].push_back(s);
}
solve(0);
solve(1);
dfs(t);
if(vis[s]) puts("-1");
else printf("%d\n",2*n-2);
return 0;
}
C:
显然增加一个点的val，深度和它同奇偶的子树中的点也会+val，非同奇偶的则-val。
然后时间戳重标记树，维护奇偶两个树状数组，区间更新，点查询即可。
code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 200010
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000000007;
const double EPS=1e-7;
class BIT{
public:
int n,sum[N];
void init(int n){
this->n=n;
fill(sum+1,sum+n+1,0);
}
void add(int i,int x){
for(;i>=1;i-= -i&i){
sum[i]+=x;
}
}
void update(int l,int r,int x){
if(r<l) return ;
add(l-1,-x);
add(r,x);
}
int query(int i){
int ans=0;
for(;i<=n;i+= -i&i){
ans+=sum[i];
}
return ans;
}
}T[2];
int val[N],l[N],r[N],h[N],Time;
vector<int> e[N];
void dfs(int u,int far,int step){
l[u]=++Time;
h[u]=step;
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==far) continue;
dfs(v,u,step+1);
}
r[u]=Time;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",val+i);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,-1,0);
T[0].init(n);
T[1].init(n);
while(m--){
int op,x,c;
scanf("%d%d",&op,&x);
if(op==1){
scanf("%d",&c);
T[h[x]%2].update(l[x],r[x],c);
T[(h[x]%2)^1].update(l[x],r[x],-c);
}else{
int ans=T[h[x]%2].query(l[x])+val[x];
printf("%d\n",ans);
}
}
return 0;
}
D:
dp[i][val] 表示以第i个数结尾，构造出的和为val的方案数。
ans=sum｛dp[i][0] ｝
每次转移后，还需要让dp[i][a]++和dp[i][-a]++，这相当于设置一个新的起点。
code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 1024
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000000007;
const double EPS=1e-7;
int dp[N][20010];
int main(){
int n,a,ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a);
for(int j=0;j<=20000;j++) if(i-1>=0){
dp[i][j]+=dp[i-1][j-a];
dp[i][j]+=dp[i-1][j+a];
dp[i][j]%=MOD;
}
ans+=dp[i][10000];
ans%=MOD;
dp[i][10000+a]++;
dp[i][10000-a]++;
}
printf("%d\n",ans);
return 0;
}