2014
02-10

Candidate superkey

A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry’s values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey. (A proper subset of a superkey is a set of attributes that is formed by removing one or more attributes from the superkey.)

The input file contains several test cases. Each test case begins with two integers n and m ( 2<=n<=30, 1<=m<=10 ), which indicate the size of the table. Then n lines follow, each line contains m uppercase letters (‘A’-'Z’) to represent one entry.

The input file contains several test cases. Each test case begins with two integers n and m ( 2<=n<=30, 1<=m<=10 ), which indicate the size of the table. Then n lines follow, each line contains m uppercase letters (‘A’-'Z’) to represent one entry.

2 3
ABC
ABC
2 1
A
B
3 3
ABC
ACD
BBE

0
1
2

这题实际上是一个01背包问题。开始的时候把被抓的概率作为花费乘以100、1000甚至1000000来运算，结果不是wa就是tle。。。。

后来上网看了题解，发现这是很巧妙的01背包问题。解决问题的时候是要把不被抓到的概率作为价值，而抢到的钱作为花费，求出在安全概率最高的情况下所抢到的钱。

#include<cstdio>
#include<iostream>
using namespace std;
const int N=110;
const int M=100001;
double safety[N],bag[M];
int money[N];
int sum,n;

void beibao()
{
int i,j;
for(i=0;i<=sum;i++)
bag[i]=0.0;
bag[0]=1.0;
for(i=1;i<=n;i++)
for(j=sum;j>=money[i];j--)
{
bag[j]=bag[j]>(bag[j-money[i]]*safety[i])?bag[j]:(bag[j-money[i]]*safety[i]);
}
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double p;
scanf("%lf%d",&p,&n);
int i,j;
sum=0;
for(i=1;i<=n;i++)
{
scanf("%d%lf",&money[i],&safety[i]);
safety[i]=1.0-safety[i];
sum+=money[i];
}
beibao();
p=1.0-p;
for(i=sum;bag[i]<p;i--);
printf("%d/n",i);
}
return 0;
}

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

3. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}