早早地水完了三道题，pt1000用的是dfs，开始做的时候误认为复杂度最多就O(2^25)，结果被一组O(2*3^16)的数据接近1e8给cha了。继续努力。
pt250：求两个串的前缀组成的不同串数目。set搞定。
/*
*Author: Zhaofa Fang
*Created time: 2013-07-10-18.54
*Language: C++
*/
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std; typedef long long ll;
#define DEBUG(x) cout<< #x << ':' << x << endl
#define FOR(i,s,t) for(int i = (s);i <= (t);i++)
#define FORD(i,s,t) for(int i = (s);i >= (t);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPD(i,n) for(int i=(n-1);i>=0;i--)
#define PII pair<int,int>
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps 1e-8 class TopFox{
public :
int possibleHandles(string f, string g){
set<string>S;
int lenf = f.length();
int leng = g.length();
REP(i,lenf){
REP(j,leng){
string tmp = "";
REP(k,i+)tmp += f[k];
REP(k,j+)tmp += g[k];
S.insert(tmp);
}
}
return S.size();
}
};
250
pt500：给定一幅图的连接情况，要求相邻两个点的差不大于d，求点之间的最大差。
可以对每个点进行bfs，比较直观。也有一些人用的是floyd，道理一样的。
/*
*Author: Zhaofa Fang
*Created time: 2013-07-10-18.54
*Language: C++
*/
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std; typedef long long ll;
#define DEBUG(x) cout<< #x << ':' << x << endl
#define FOR(i,s,t) for(int i = (s);i <= (t);i++)
#define FORD(i,s,t) for(int i = (s);i >= (t);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPD(i,n) for(int i=(n-1);i>=0;i--)
#define PII pair<int,int>
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps 1e-8 class Egalitarianism{
public :
bool vist[];
int mon[];
bool OK;
int bfs(int s,vector <string> isFriend, int d){
int n = isFriend.size();
queue<int>Q;
Q.push(s);
int ans = -;
memset(vist,,sizeof(vist));
mon[s] = ;
vist[s] = ;
while(!Q.empty()){
int now = Q.front();
Q.pop();
REP(i,n){
if(isFriend[now][i] == 'Y' && !vist[i]){
Q.push(i);
mon[i] = mon[now] + d;
vist[i] = ;
ans = max(ans,mon[i]);
}
}
}
REP(i,n)if(!vist[i])return -;
return ans;
}
int maxDifference(vector <string> isFriend, int d){
int n = isFriend.size();
int ans = -;
REP(i,n)ans = max(bfs(i,isFriend,d),ans);
return ans;
}
};
500
pt1000：给定一组数kind[],从中取K个，取得的数为found[]，能有多少种可能。其中一组sample如下：
|
||||||||
正解dp。很简单的转移-__-。
/*
*Author: Zhaofa Fang
*Created time: 2013-07-10-18.54
*Language: C++
*/
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std; typedef long long ll;
#define DEBUG(x) cout<< #x << ':' << x << endl
#define FOR(i,s,t) for(int i = (s);i <= (t);i++)
#define FORD(i,s,t) for(int i = (s);i >= (t);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPD(i,n) for(int i=(n-1);i>=0;i--)
#define PII pair<int,int>
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps 1e-8 ll C[][]; void pre(){
C[][] = C[][] = ;
FOR(i,,){
C[i][] = ;
FOR(j,,i)C[i][j] = C[i-][j-] + C[i-][j];
}
}
class Excavations2{
public :
int ff[];
ll dp[][];
ll count(vector <int> kind, vector <int> found, int K){
pre();
int len = kind.size();
memset(ff,,sizeof(ff));
REP(i,len)ff[kind[i]]++;
memset(dp,,sizeof(dp));
int n = found.size();
FOR(i,,ff[found[]]){
dp[][i] = C[ff[found[]]][i];
}
FOR(i,,n){
FOR(j,,K){
FOR(k,,ff[found[i-]])
dp[i][j] += dp[i-][j-k]*C[ff[found[i-]]][k];
}
}
return dp[n][K];
}
}; //int main(){
// //freopen("in","r",stdin);
// //freopen("out","w",stdout);
//
// return 0;
//}
1000