比赛链接:http://codeforces.com/contest/369
369C - Valera and Elections:
这是一个树上问题,用深搜,最开始贪心想得是只加叶子节点,找到一个叶子节点且从根1 ——》 叶子节点有problem edges,就把这个点加入,但后来一直WA,才发现时贪错了,找到的这个叶子节点不一定需要,所以要多记录点信息,参考别人的思想,就是标记每个点是不是需要修,如果一个更深的点需要修,则中间的就不需要了。
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std; const int maxn = 1e5+; vector< pair<int,int> > G[maxn];
bool rep[maxn]; void dfs(int u,int fa,int bef) //bef是从1->u距离u最近的需要修的点,不断更新就行,最开始dfs(1,-1,-1)中bef == 1的原因是一这个点一定不需要修。
{
int sz = G[u].size(); for(int i=; i<sz; i++)
{
pair<int,int> my = G[u][i];
if(my.first == fa) continue; if(my.second == )
{
rep[my.first] = true;
rep[bef] = false;
dfs(my.first,u,my.first);
}
else
dfs(my.first,u,bef);
}
} int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int n;
cin>>n;
for(int i=; i<n; i++)
{
int x,y,t;
scanf("%d %d %d",&x,&y,&t); G[x].push_back(make_pair(y,t));
G[y].push_back(make_pair(x,t));
}
memset(rep,,sizeof(rep));
dfs(,-,); int ans = ;
for(int i=; i<=n; i++)
if(rep[i]) ans++;
cout<<ans<<endl;
for(int i=; i<=n; i++)
if(rep[i]) cout<<i<<" ";
}
Tutorial里面的解法没看懂
369D - Valera and Fools:
只要明白每个situation要么是a[i]到a[n]的连续数列,要么是一个数a[j]+a[i]到a[n]的连续数列,这样情况就少很多,了解了这个,就可以想到用宽搜了
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std; const int maxn = ; int p[maxn];
int sum[maxn];
bool head[maxn];
bool man[maxn]; struct Node
{
int u,v;
int round;
Node(int u=,int v=,int round=): u(u), v(v), round(round) {}
}; int main()
{
// freopen("E:\\acm\\input.txt","r",stdin); int n,k;
cin>>n>>k;
for(int i=; i<=n; i++)
cin>>p[i];
sum[n+] = ;
man[n+] = ;
for(int i=n; i>=; i--)
{
sum[i] = sum[i+] + p[i];
if(p[i]== || man[i+]) man[i] = ;
else man[i] = ;
} memset(head,,sizeof(head)); //标记一个连续数列,让它最多出现一次 int ans = ;
head[] = true; queue< Node > Q;
Q.push(Node(,,)); while(!Q.empty())
{
Node my = Q.front(); Q.pop(); if(my.round >= k) continue;
int u = my.u;
int v = my.v; if(u > n || v > n) continue; if(p[u] > && !man[v])
{
ans ++;
Q.push(Node(u,v+,my.round+));
}
if(sum[v] > && p[u] != && !head[v])
{
ans ++;
head[v] = true;
Q.push(Node(v,v+,my.round+));
}
if(p[u] > && sum[v] > && !head[v+])
{
ans ++;
head[v+] = true;
Q.push(Node(v+,v+,my.round+));
}
}
cout<<ans<<endl;
}
369E - Valera and Queries:
一直没思路,后来看题解知道要有求答案补集,因为正着来区间重复计数很难避免,而反着就是求不与点相交的区间的个数,进一步就是求每一个询问相邻点中区间的个数
用树状数组计数就行
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define SHOW(x) { cerr << ">>> " << #x << " = " << x << endl; } using namespace std; const int maxn = 1e6+;
const int MV = 1e6+; struct BIT
{
int C[maxn]; int lowbit(int x)
{
return x&(-x);
} void init()
{
memset(C,,sizeof(C));
} void add(int x,int a)
{
while(x <= MV)
{
C[x] += a;
x += lowbit(x);
}
} int sum(int x)
{
if(x == ) return ;
int ret = ;
while(x > )
{
ret += C[x];
x -= lowbit(x);
}
return ret;
}
}bit;
//要求一个区间内的线段的个数 struct Node
{
int l,r;
int id;
bool operator < (const Node& rhs) const
{
return r < rhs.r;
}
}I[maxn/],Q[*maxn/]; //就由于一个数组开错了啊
int ans[maxn/]; int main()
{
freopen("E:\\acm\\input.txt","r",stdin);
int n,m;
cin>>n>>m;
bit.init(); for(int i=; i<=n; i++)
{
scanf("%d %d",&I[i].l,&I[i].r);
} int cnt = ;
for(int i=; i<=m; i++)
{
int num;
scanf("%d",&num);
for(int j=; j<=num; j++)
{
int p;
scanf("%d",&p); Q[++cnt].id = i; if(j == )
Q[cnt].l = ;
else
Q[cnt].l = Q[cnt-].r; Q[cnt].r = p;
}
Q[++cnt].id = i;
Q[cnt].l = Q[cnt-].r;
Q[cnt].r = MV;
}
sort(I+,I+n+);
sort(Q+,Q+cnt+); for(int i=; i<=m; i++) ans[i] = n; int pv = ;
for(int i=; i<=cnt; i++)
{
while(pv <= n && I[pv].r < Q[i].r)
{
bit.add(I[pv].l,);
pv++;
}
ans[Q[i].id] -= bit.sum(Q[i].r-) - bit.sum(Q[i].l);
}
for(int i=; i<=m; i++)
printf("%d\n",ans[i]);
}