写题记录2

记录一些不太会的题目

1

原题：UVA658

这题我们首先想到是先状压，再建图，求个最短路，但是会发现建图的话最坏情况点能达到 $2^n$ 级别，这空间可能过不去。于是我们转换成类BFS+SPFA的方式，即每次更新节点的时候都把可能的边转换遍历一次（反正最多才100），再在这个所谓的隐式图上跑个SPFA就好了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 2e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;

int n,m,cost[120],vis[N],dis[N];
string op[120],to[120];
queue<int> qu;

bool check(int now,string s){
  for(int i = 0;i < s.size();i++){
    int sta = (now&(1<<i));
    if(s[i] == '-' and sta) return false;
    if(s[i] == '+' and !sta) return false;
  }
  return true;
}

int change(int now,string s){
  int ans = 0;
  for(int i = 0;i < s.size();i++){
    int old = now&(1<<i);
    if(s[i] == '0' and old) ans += (1<<i);
    if(s[i] == '+') ans += (1<<i);
  }
  return ans;
}

void spfa(int st){
  memset(vis,0,sizeof(vis));
  for(int i = 0;i < (1<<n);i++) dis[i] = 1e9;
  dis[st] = 0;
  qu.push(st);vis[st] = 1;
  while(!qu.empty()){
    int now = qu.front();vis[now] ^= 1;qu.pop();
    for(int i = 1;i <= m;i++){
      if(check(now,op[i])){
			int nex = change(now,to[i]);
			if(dis[nex] > dis[now]+cost[i]){
			  dis[nex] = dis[now] + cost[i];
			  if(!vis[nex]) qu.push(nex),vis[nex] = 1;
				}
      }
    }
  }
}

int main(){
  // freopen("input.txt","r",stdin);
  int kase = 1;
  while(cin>>n>>m and n){
    for(int i = 1;i <= m;i++){
      cin>>cost[i]>>op[i]>>to[i];
    }
    spfa((1<<n)-1);
    printf("Product %d\n",kase++);
    if(dis[0] == 1e9) cout<<"Bugs cannot be fixed."<<endl;
    else printf("Fastest sequence takes %d seconds.\n",dis[0]);
    cout<<endl;
  }
  return 0;
}

2

Online Judge

题意：给了36张牌，分成9堆，每次都可以取两张位于堆顶且大小相同的牌，问取到一张不剩的概率

发现自己的概率还停留在高中的sb思维。。。只会无脑求出符合题意的事件次数除以总事件数，然而在这里肯定不行，复杂度太大。

于是我们就得转换一下思路，我这里用了字符串表示状态套一层unordered_map当数组用，用 $dp(sta)$ 表示在sta下满足题意的概率，那么对于从状态 $s_1\rightarrow s_2$ ，令p为转移到 $s_2$ 的概率，那么显然 $s_2$ 对 $dp(s_1)$ 的贡献就为 $dp(s_2)\times p$ ，再写一下记忆化搜索就好了。

同时还要注意一下输入的问题,题目要求连续输入多个数据且中间没有间隔,学到了一个方法就是写一个bool函数,同时也注意到cin>>这个表达式也是有返回值的。。。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;

stack<int> qu[20];
string ca;
dd ans;
unordered_map<string,dd> vis;
int n,fac[100];

dd dfs(string sta){
  if(sta == "000000000"){return 1.0;}
  if(vis.count(sta)) return vis[sta];
  int cnt = 0;
  for(int i = 1;i <= 9;i++){
    if(qu[i].empty()) continue;
    for(int j = i+1;j <= 9;j++){
      if(qu[j].empty()) continue;
      if(qu[i].top() == qu[j].top()) cnt++;
    }
  }
  if(cnt == 0) return 0.0;
  for(int i = 1;i <= 9;i++){
    if(qu[i].empty()) continue;
    for(int j = i+1;j <= 9;j++){
      if(qu[j].empty()) continue;
      int a = qu[i].top(),b = qu[j].top();
      if(a == b){
	qu[i].pop();qu[j].pop();
	string nex = sta;
	nex[i-1] = sta[i-1]-1;
	nex[j-1] = sta[j-1]-1;
	vis[sta] += dfs(nex)/dd(cnt);
	qu[i].push(a);qu[j].push(b);
      }
    }
  }
  return vis[sta];
}

bool read(){
  for(int i = 1;i <= 9;i++){
    while(!qu[i].empty()) qu[i].pop();
  }
  for(int i = 1;i <= 9;i++){
    for(int j = 1;j <= 4;j++){
      if(!(cin>>ca)) return false;
      if(ca[0] == 'J') qu[i].push(11);
      else if(ca[0] == 'Q') qu[i].push(12);
      else if(ca[0] == 'K') qu[i].push(13);
      else if(ca[0] == 'A') qu[i].push(14);
      else if(ca[0] == 'T') qu[i].push(10);
      else {qu[i].push(ca[0]-'0');}      
    }
  }
  return true;
}

int main(){
  // freopen("input.txt","r",stdin);
  while(read()){
    vis.clear();
    printf("%.6f\n",dfs("444444444"));    
  }
  return 0;
}

3

原题：UVA1660

题意：给出n个点的无向图 $(n\le50)$ ，求最少删除多少个点，使整张图不联通

我们可以先选出两个点 $s,t$ ，整张图不联通只需要使 $s,t$ 不联通，等价于一个二分图划分，我们把其他点拆点，再连边，最后跑个Dinic求最小割后取最小值即可。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;

string pa;
int head[N],n,m,s,t,vis[N],d[N],cur[N],cnt=1,u,v,a[10000],b[10000];
ll w;
struct node{
  int to,nex;
  ll cap,flow;
}edge[N];

void add_edge(int u,int v,ll w){
  edge[++cnt].to = v;
  edge[cnt].cap = w;
  edge[cnt].flow = 0;
  edge[cnt].nex = head[u];
  head[u] = cnt;
  edge[++cnt].to = u;
  edge[cnt].cap = 0;
  edge[cnt].flow = 0;
  edge[cnt].nex = head[v];
  head[v] = cnt;
}

bool bfs(){
  for(int i = 1;i <= (2*n+5);i++) vis[i] = 0;
  queue<int> qu;  
  qu.push(s);
  d[s] = 0;
  vis[s] = 1;
  cur[s] = head[s];
  while(!qu.empty()){
    int now = qu.front();qu.pop();
    for(int i = head[now];i;i = edge[i].nex){
      int nex = edge[i].to;
      if(!vis[nex] and edge[i].cap > edge[i].flow){
	vis[nex] = 1;
	cur[nex] = head[nex];
	d[nex] = d[now] + 1;
	qu.push(nex);
	if(nex == t) return 1;
      }
    }
  }
  return 0;
}

ll dfs(int x,ll a){
  if(x == t or a == 0) return a;
  ll flow = 0,f;
  for(int i = cur[x];i and a;i = edge[i].nex){
    cur[x] = i;
    int nex = edge[i].to;
    if(d[x]+1 == d[nex] and edge[i].cap > edge[i].flow){
      f = dfs(nex,min(a,edge[i].cap-edge[i].flow));
      edge[i].flow += f;
      edge[i^1].flow -= f;
      flow += f;
      a -= f;
    }
  }
  return flow;
}

int read(){
  int x=0,f=1;char ch='[';
  while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}
  while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}

int main(){
  // freopen("input.txt","r",stdin);
  while(cin>>n>>m){
    for(int i = 1;i <= m;i++){
      a[i] = read()+1;b[i] = read()+1;
    }
    int ans = inf;
    for(s = 1;s <= n;s++){
      for(t = 1;t <= n;t++){
	if(s == t) continue;
	memset(head,0,sizeof(head));
	cnt = 1;
	for(int i = 1;i <= n;i++){
	  if(i == s or i == t) add_edge(i,i+n,inf-1);
	  else add_edge(i,i+n,1);
	}
	for(int i = 1;i <= m;i++){
	  add_edge(a[i]+n,b[i],inf-1);
	  add_edge(b[i]+n,a[i],inf-1);
	}
	int flow = 0;
	while(bfs()){
	  flow += dfs(s,inf);
	}
	ans = min(ans,flow);
      }
    }
    if(ans > n) ans = n;
    cout<<ans<<endl;
  }
  return 0;
}

init0xyz的自留地

1

2

3

写题记录1