先说明情况~~弱弱是从BNUOJ中复制的各位大牛的代码，然后加上自己理解后写的博客~~
各位巨巨如果觉得我代码COPY侵权的话，请在后面留言，我马上扯的。。。
10.4-A
这个题题意绝壁有毒：关键英文表述是这样的：So if creature a doesn't have a trait hi, then all creatures in the competition are without this trait. If creature a has a trait hi, then all creatures in the competition have this trait. Other traits doesn't matter.
重点句子是Other traits doesn't matter.因此只需要管那么些相同的
那么思路很简单啦：状态压缩每个生物的特征（用一个整数表示），然后每次查询时候，比较即可
const int maxn = 100010;
int score[maxn], trait[maxn];
int n, k;
int main() {
// freopen("in", "r", stdin);
while(~scanf("%d %d", &n, &k)) {
int y, f;
memset(trait, 0, sizeof(trait));
for(int i = 0; i < n; i++) {
scanf("%d %d", &score[i], &y);
for(int j = 0; j < y; j++) {
scanf("%d", &f);
trait[i] += (1 << f);
}
}
int m;
scanf("%d", &m);
while(m--) {
int t, a, h;
int cur = 0, ans = 1;
scanf("%d %d", &a, &t);
a--;
for(int i = 0; i < t; i++) {
scanf("%d", &h);
cur += (1 << h);
}
for(int i = 0; i < n; i++) {
if((trait[i] & cur) == (trait[a] & cur) && score[i] > score[a]) {
ans++;
}
}
printf("%d\n", ans);
}
}
return 0;
}10.4-C
这个题自己***，，，把数据开小了RE了一发
关键还是读题的问题：：：：At each turn Cinderella points out one of the bottles. This is the source bottle. Then she selects any number of other bottles and for each bottle specifies the amount of water to be poured from the source bottle to it.
每次选择都会选择一个作为倒出瓶。然后把这个瓶的水任意倒入其他瓶子
那么问题来了：怎么样选择次数最少？
当然是：多于平均数的疯狂输出就好了啊。。。用double，比avg大的话ans++
while(scanf("%d",&n)!=EOF){
ans=avg=0;
for(int i=1;i<=n;i++){
scanf("%lf",&num[i]);
avg+=num[i];
}
avg/=n;
for(int i=1;i<=n;i++)
if (num[i]>avg) ans++;
printf("%d\n",ans);
}10.4-E
n个数中选任意非空子集使得其乘积最大
处理：负数两两相乘才是正的，正数大于1的必须取得（这些都是大家懂得）
细节《1》：所有数的绝对值小于1怎么办
细节《2》：由于是实数类型，一定记得eps
细节《1》的处理：取最小的两个数相乘，与最大的数比大小！（（画个数轴就明白了为什么））
int a[10005];
bool flag[10005];
struct tt
{
double a;
int pos;
}t[10005];
bool cmp(tt a,tt b)
{
return a.a<b.a;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,j,m,T,n,k;
cin>>n;
for (i=1;i<=n;i++)
{
scanf("%lf",&t[i].a);
t[i].pos=i;
}
sort(t+1,t+n+1,cmp);
int cnt=0;
//int cnt1=0;
memset(flag,false,sizeof(flag));
for (i=1;i<=n;i++) if (t[i].a<0) cnt++;
for (i=1;i<=cnt;i++)
if (!flag[i])
if (t[i].a*t[i+1].a>1+1e-6)
{
flag[i]=true;
flag[i+1]=true;
}
for (i=cnt;i<=n;i++)
if (t[i].a>1+1e-6)
flag[i]=true;
cnt=0;
for (i=1;i<=n;i++)
if (flag[i])
{
cnt++;
a[cnt]=t[i].pos;
}
sort(a+1,a+cnt+1);
if (cnt==0)
{
if (n==1)
{
cout<<1<<endl<<1<<endl;
return 0;
} else
{
double tmp=t[1].a*t[2].a;
//cout<<tmp<<endl;
double tmp2=t[n].a;
if (tmp>tmp2+1e-6)
{
int a=t[1].pos;
int b=t[2].pos;
if (a>b)
cout<<2<<endl<<b<<" "<<a<<endl;else
cout<<2<<endl<<a<<" "<<b<<endl;
} else
cout<<1<<endl<<t[n].pos<<endl;
return 0;
}
}
cout<<cnt<<endl;
for (i=1;i<cnt;i++) printf("%d ",a[i]);
printf("%d\n",a[cnt]);
return 0;
}10.4-G
给定一个有向树，问从u到v能否有路径
我群巨给我提供的做法：谢谢群哥的代码
有向边addedge（u，v，1）
添加反向边addedge（v，u，0）
然后dfs跑各点深度存入dep【】
各点离根的距离存入val【】
利用LCA查找的性质就可以想明白了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=100010;
const int M=N*2;
const int DEG=26;
int nedge;
int Prev[M],to[M],dir[M],info[N],val[N],dep[N];
int fa[N][DEG];
int n;
void insert(int u,int v,int d){
nedge++;
to[nedge]=v,dir[nedge]=d,Prev[nedge]=info[u],info[u]=nedge;
}
void init(){
memset(info,0,sizeof(info));
nedge=0;
val[1]=0;
dep[0]=1;
fa[1][0]=0;
fa[0][0]=0;
}
void dfs(int u,int Fa){
dep[u]=dep[Fa]+1;
for(int i=info[u];i;i=Prev[i]){
int v=to[i];
if(v==Fa)continue;
fa[v][0]=u;
val[v]=val[u]+dir[i];
dfs(v,u);
}
}
void prepare(){
dfs(1,0);
for(int i=1;i<DEG;i++)
for(int j=0;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
}
int swim(int u,int Dep){
for(int i=0;i<DEG&&Dep;i++){
if(Dep&1)u=fa[u][i];
Dep>>=1;
}
return u;
}
int lca(int u,int v){
if(dep[u]>dep[v])swap(u,v);
v=swim(v,dep[v]-dep[u]);
if(v==u)return u;
for(int i=DEG-1;i>=0;i--){
if(fa[u][i]==fa[v][i])continue;
u=fa[u][i];
v=fa[v][i];
}
return fa[u][0];
}
int main(){
// freopen("data.in","r",stdin);
while(~scanf("%d",&n)){
int u,v;
init();
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
insert(u,v,1);
insert(v,u,0);
}
prepare();
int Q;
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&u,&v);
int LCA=lca(u,v);
if(val[u]==val[LCA]&&(val[v]-val[LCA]==dep[v]-dep[LCA])){
puts("Yes");
}
else {
puts("No");
}
}
}
return 0;
}
10.4-K
这个题是完美佩服这个作者的思路的
体现了ACM的真谛：暴力模拟保平安
解释题意：先给一篇文章，然后给定删除的k个单词，删除之后，定义P（a）为a词在文章中总词数占的比例，P（a，b）为a和b两个词连起来的次数在文章所有两个连续词出现次数占的比例
#include <map>
#include <set>
#include <utility>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
set<string> b;
vector<string> a;
map<string,int> c;
map<pair<string,string>,int> d;
char s[512001],s1[21],s2[21];
int n,n1,n2;
void read() {
gets(s);
for (int i=0;s[i]!='\0';i++)
if (s[i]>='A'&&s[i]<='Z') s[i]=s[i]-'A'+'a';
for (int i=0;s[i]!='\0';i++)
if (s[i]>='a'&&s[i]<='z') {
int j=i;
while (s[j]>='a'&&s[j]<='z') {
s1[j-i]=s[j];
j++;
}
s1[j-i]='\0';
a.push_back(s1);
i=j-1;
}
}
void cal() {
int n=a.size();
string last="";
for (int i=0;i<n;i++)
if (b.find(a[i])==b.end()){
n1++;
c[a[i]]++;
if (last!="") {
pair<string,string> tmp(last,a[i]);
if (tmp.first>tmp.second) swap(tmp.first,tmp.second);
d[tmp]++;
}
last=a[i];
}
n2=n1-1;
}
double query(char s1[],char s2[]) {
pair<string,string> tmp(s1,s2);
if (tmp.first>tmp.second) swap(tmp.first,tmp.second);
int t1=c[s1],t2=c[s2],t3=d[tmp];
if (t1==0||t2==0||t3==0) return 0;
return ((double)t3/n2)*((double)n1/t1)*((double)n1/t2);
//return (long double)((long long)t3*n1*n1)/((long long)n2*t1*t2);
}
int main() {
a.clear();
b.clear();
c.clear();
d.clear();
scanf("%d",&n);
gets(s);
while (n--) read();
scanf("%d",&n);
while (n--) {
scanf("%s",s1);
b.insert(s1);
}
cal();
scanf("%d",&n);
while (n--) {
scanf("%s%s",s1,s2);
printf("%.9f\n",query(s1,s2));
}
return 0;
}10.5-A
n只蚂蚁，n个食物，走的路线不能交叉，求方案
这个题最难的是建模：不能交叉--怎么定义：路线最短！
拿四个点画画就知道了，不能交叉就是走最短路
那么，转化为二分图中最小权！KM（）算法求最大权！那么只需要建立边长就好了
细节：注意答案是那个作为左边点集！
int nx,ny;
double g[maxn][maxn];
double lx[maxn],ly[maxn];
double slack[maxn];
int linker[maxn];
bool visx[maxn],visy[maxn];
bool DFS(int x){
visx[x]=true;
for(int y=1;y<=ny;y++){
if (visy[y]) continue;
double tmp=lx[x]+ly[y]-g[x][y];
if (fabs(tmp)<eps){
visy[y]=true;
if (linker[y]==-1||DFS(linker[y])){
linker[y]=x;
return true;
}
}
else if (slack[y]>tmp)
slack[y]=tmp;
}
return false;
}
void KM(){
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i=1;i<=nx;i++){
lx[i]=-INF;
for(int j=1;j<=ny;j++)
if (g[i][j]>lx[i])
lx[i]=g[i][j];
}
for(int x=1;x<=nx;x++){
for(int i=1;i<=ny;i++)
slack[i]=INF;
while(1){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if (DFS(x)) break;
double d=INF;
for(int i=1;i<=ny;i++)
if (!visy[i]&&d>slack[i])
d=slack[i];
for(int i=1;i<=nx;i++)
if (visx[i])
lx[i]-=d;
for(int i=1;i<=ny;i++){
if (visy[i]) ly[i]+=d;
else slack[i]-=d;
}
}
}
}
double X1[maxn],X2[maxn],Y1[maxn],Y2[maxn];
int n;
int main(){
//input;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++) scanf("%lf%lf",&X1[i],&Y1[i]);
for(int i=1;i<=n;i++) scanf("%lf%lf",&X2[i],&Y2[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[j][i]=-sqrt((X1[i]-X2[j])*(X1[i]-X2[j])+(Y1[i]-Y2[j])*(Y1[i]-Y2[j]));
nx=ny=n;
KM();
for(int i=1;i<=n;i++)
printf("%d\n",linker[i]);
}
return 0;
}10.5-B
这个题还是题意的阅读：Each country gets several offices that form a connected set.
each pair of countries must have at least one pair of adjacent offices, so that they can raise the wall or the ceiling they share to perform secret pair-wise negotiations just in case they need to.
每个字母必须全部相邻，而且至少跟一个其他的字母相邻
构造题，自己画画就能明白的（n《=50，暴力自己画几个）
int n,a[100];
int main(){
//input;
//output;
int i,j;
for(i=65;i<=122;i++)
if (i>=65&&i<=90) a[i-65]=i;
else if (i>=97&&i<=122) a[i-71]=i;
while(scanf("%d",&n)!=EOF){
printf("2 %d %d\n",n,n);
for(i=0;i<n;i++){
for(j=0;j<n;j++) printf("%c",a[i]);
puts("");
}
puts("");
for(i=0;i<n;i++){
for(j=0;j<n;j++) printf("%c",a[j]);
puts("");
}
//puts("");
}
return 0;
}
/*
n==14时候：
2 14 14
AAAAAAAAAAAAAA
BBBBBBBBBBBBBB
CCCCCCCCCCCCCC
DDDDDDDDDDDDDD
EEEEEEEEEEEEEE
FFFFFFFFFFFFFF
GGGGGGGGGGGGGG
HHHHHHHHHHHHHH
IIIIIIIIIIIIII
JJJJJJJJJJJJJJ
KKKKKKKKKKKKKK
LLLLLLLLLLLLLL
MMMMMMMMMMMMMM
NNNNNNNNNNNNNN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
/*
10.5-I
又是字符串暴力搞法：这题题意很好懂
判断每个有数字的字符串是不是上文出现个全部的（出现过的话补充完整）
细节：每个单词只有三种情况：全小写，首字母大写其余全小写，全部字母大写
上个好懂得代码：
using namespace std;
set<string> d[26][26][35];
bool isabbr(string &s) {
return s.length() >= 3 && isdigit(s[1]);
}
int ablen(string &s) {
if (s.length() == 4)
return (s[1] - '0') * 10 + s[2] - '0';
return s[1] - '0';
}
void Output(string &s) {
if (s.empty())
return;
if (!isabbr(s)) {
// full
printf("%s", s.c_str());
//transform(s.begin(), s.end(), s.begin(), tolower);
for (int i = 0; i < s.length(); ++i)
s[i] = tolower(s[i]);
d[*s.begin() - 'a'][*s.rbegin() - 'a'][s.length()].insert(s);
} else {
set<string> &tr = d[tolower(*s.begin()) - 'a'][tolower(*s.rbegin()) - 'a'][ablen(s) + 2];
if (tr.size() > 1 || tr.empty()) {
printf("%s", s.c_str());
} else {
string re = *tr.begin();
if (isupper(*s.begin()) && islower(*s.rbegin())) {
re[0] = toupper(re[0]);
} else if (isupper(*s.begin()) && isupper(*s.rbegin())) {
for (int i = 0; i < re.length(); ++i)
re[i] = toupper(re[i]);
}
//all lowercase, First Capital Letter, or ALL CAPITAL LETTERS.
printf("%s", re.c_str());
}
}
s = "";
}
void EXEC() {
string t;
char x;
while ((x = getchar()) != EOF) {
if (isalnum(x)) {
t += x;
} else {
Output(t);
printf("%c", x);
}
}
Output(t);
}
int main() {
EXEC();
return 0;
}——————————————————————————————————————————————————————————————
国庆被群巨吊打，被各位网络线上虐成狗，希望提高的多一点，南阳加油！
京公网安备 11010502036488号