[BZOJ 1086][SCOI2005]王室联邦
最近想捉一下树分块，这道题肯定是要做的啦~
这个题的方法就是蜜汁贪心，在其他树分块的题目中也有应用。
代码：
/**************************************************************
Problem: 1086
User: danihao123
Language: C++
Result: Accepted
Time:16 ms
Memory:880 kb
****************************************************************/
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
int siz=S.size();
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(v==fa){
continue;
}
DFS(v,u);
if((S.size()-siz)>=B){
block_cnt++;
cap[block_cnt]=u;
while(S.size()>siz){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
}
}
S.push(u);
}
int main(){
register int i;
bool OK;
int n,u,v;
scanf("%d%d",&n,&B);
for(i=1;i<=(n-1);i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
if(n<B){
puts("0");
return 0;
}
DFS(1,0);
while(!S.empty()){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
printf("%d\n",block_cnt);
OK=false;
for(i=1;i<=n;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",belong[i]);
}
putchar('\n');
OK=false;
for(i=1;i<=block_cnt;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",cap[i]);
}
putchar('\n');
return 0;
}
[CF 711D]Directed Roads
这个题啊……其实不难。
首先你注意，他告诉你你可以把边弄反。
其次注意，这个图不一定就有一个环。
然后每个环的取反法有[tex]2^x[/tex]种（假设环中有[tex]x[/tex]条边），但是空集不行，全集也不行，因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄，乘法原理乱搞即可。
然后你是不是感觉这个题似曾相识？是的似乎这个题就是NOIP D1T2的翻版。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
register int i;
bool ans=false;
for(i=1;i<=n;i++){
if(!vis[i] && !in[i]){
ans=true;
in[G[i]]--;
vis[i]=true;
G[i]=0;
}
}
return ans;
}
ll dfs(int x,int y){
if(x==y && vis[x]){
return 0;
}else{
vis[x]=true;
return dfs(G[x],y)+1;
}
}
ll pow_mod(ll a,ll b){
if(!b){
return 1;
}else{
ll ans=pow_mod(a,b/2);
ans=ans*ans%MOD;
if(1&b){
ans=(ans*(a%MOD))%MOD;
}
return ans;
}
}
inline ll solve(){
register int i;
register ll Huan,temp=0,ans=1;
while(jianz());
for(i=1;i<=n;i++)
if(!vis[i]){
Huan=dfs(i,i);
temp+=Huan;
ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
}
ans=(ans*pow_mod(2,n-temp))%MOD;
return ans;
}
int main(){
register int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&G[i]);
in[G[i]]++;
}
printf("%I64d\n",solve());
return 0;
}
[BZOJ 4325]斗地主
是的你没有看错！就是这道坑提！
这题基本是个半成品，歧义真的，真的，真的很大。
至于方法？我们注意到同样的牌能一起出就尽可能避免拆开。例如，四带二分成炸弹加两单点（对子）肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解，并据此进行深度限制，再考虑出顺子。
然后，DFS暴搜即可。
顺便讲一下坑点：
- 顺子可以有A。
- 三带一，三带二，四代二都可以有头。但是大小头要区别开。
代码：
/**************************************************************
Problem: 4325
User: danihao123
Language: C++
Result: Accepted
Time:24 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
if(x>ans)
return;
int i,j,rest=0;
memset(cnt,0,sizeof(cnt));
for(i=0;i<=14;i++){
cnt[hand[i]]++;
}
while(cnt[4]>0){
cnt[4]--;
rest++;
if(cnt[2]>=2)
cnt[2]-=2;
else
if(cnt[1]>=2)
cnt[1]-=2;
}
while(cnt[3]>0){
cnt[3]--;
rest++;
if(cnt[2]>0)
cnt[2]--;
else
if(cnt[1]>0)
cnt[1]--;
}
if(hand[0] && hand[1] && cnt[1]>=2)
rest--;
ans=min(ans,cnt[1]+cnt[2]+rest+x);
for(i=3;i<=10;i++){
for(j=i;j<=14 && hand[j];j++){
hand[j]--;
if(j-i+1>=5)
dfs(x+1);
}
while(j>i)
hand[--j]++;
}
for(i=3;i<=12;i++){
for(j=i;j<=14 && hand[j]>=2;j++){
hand[j]-=2;
if(j-i+1>=3)
dfs(x+1);
}
while(j>i)
hand[--j]+=2;
}
for(i=3;i<=13;i++){
for(j=i;j<=14 && hand[j]>=3;j++){
hand[j]-=3;
if(j-i+1>=2)
dfs(x+1);
}
while(j>i)
hand[--j]+=3;
}
}
int main(){
int T,u,v;
register int i;
scanf("%d%d",&T,&n);
while(T--){
ans=n;
memset(hand,0,sizeof(hand));
for(i=1;i<=n;i++){
scanf("%d%d",&u,&v);
if(!u){
if(v==2)
hand[1]++;
else
hand[0]++;
}else{
if(u==1)
hand[14]++;
else
hand[u]++;
}
}
dfs(0);
printf("%d\n",ans);
}
return 0;
}
[BZOJ 1232]安慰奶牛
这题要用到DFS欧拉遍历树（胡编词汇）的一个特征：每一条边都经过2遍。这样似乎每个边度数就可以确定了，然后……
但是，起点也要算啊……
代码：
/**************************************************************
Problem: 1232
User: danihao123
Language: C++
Result: Accepted
Time:248 ms
Memory:2056 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001,maxm=100001;
// Djoin set
int p[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
void union_set(int x,int y){
p[find_set(x)]=find_set(y);
}
bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
// Graph
struct Edge{
int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
return a.d<b.d;
}
int n,m;
int c[maxn];
Edge E[maxm];
int mst(){
register int i,cnt=0,ans=0;
for(i=1;i<=n;i++)
p[i]=i;
sort(E,E+m,cmp);
for(i=0;cnt<(n-1) && i<m;i++){
if(!is_same(E[i].u,E[i].v)){
union_set(E[i].u,E[i].v);
ans+=E[i].d;
cnt++;
}
}
return ans;
}
int main(){
register int i,kkk=0x5fffffff;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&c[i]);
kkk=min(kkk,c[i]);
}
for(i=0;i<m;i++){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
E[i].d+=E[i].d+c[E[i].u]+c[E[i].v];
}
printf("%d\n",kkk+mst());
return 0;
}
[BZOJ 1603]打谷机
啊啊啊啊我又活过来了……
然而这也就是一道脑残题……
代码：
/**************************************************************
Problem: 1603
User: danihao123
Language: C++
Result: Accepted
Time:20 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1001;
struct Edge{
int u,v;
bool type;
};
vector<Edge> edges;
vector<int> G[maxn];
void Add_Edge(int u,int v,bool type){
edges.push_back((Edge){u,v,type});
G[u].push_back(edges.size()-1);
}
bool ans[maxn],vis[maxn];
void dfs(int x){
vis[x]=true;
int i;
for(i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!vis[e.v]){
ans[e.v]=e.type?(!ans[x]):ans[x];
dfs(e.v);
}
}
}
int main(){
register int i;
int n,u,v,d;
scanf("%d",&n);
for(i=0;i<(n-1);i++){
scanf("%d%d%d",&u,&v,&d);
Add_Edge(u,v,(bool)d);
Add_Edge(v,u,(bool)d);
}
dfs(1);
printf("%d\n",ans[n]?1:0);
return 0;
}
[BZOJ 1053]反素数
终于A了……
此题坑点多~
据说只需要预处理12个素数，然而我预处理了4648个……so sad
然后DFS就可以了
我无力吐槽了……我就是智商感人啊
代码：
