|
|
摘要: 题目大意：16个人举行宴席，4人一桌，一共5次。（严重不符合客观事实。。）求怎样安排才能使每次吃饭时，每个人的同桌都是不同的人。也就是说吃完5次饭下来，每个人都认识其他人了。。有人帮你算好了前3次的情况，你需要接着算出余下的2次，当然也有可能算不出来。思路：暴搜，位操作辅助。ps：此题描述得不大清楚，导致屡次wa。注意：1.多case2.如果有解，需要打印5行。3.如果无解，只需要打印“... 阅读全文
摘要: 这题很有意思哇。给出一个这样的东西：A---+ | +---:\ : >o---:\ +---:/ : )---?&... 阅读全文
这题好题啊，网上也有很多解题报告的呢，哥也是看了才懂写的。。 直接贴代码。这个代码不咋地呢。 分数规划用迭代法500+ms，用二分法就2000+ms了。可见差异还是挺大的，还是迭代法好。 膜拜下分数规划算法的创始人 
 #include <stdio.h>
#include <math.h>
#include <string.h>
int X[1024], Y[1024], Z[1024], N, from[1024];
char mst[1024];
double D[1024], rate;
  struct  {
 double w, cost, len;
 } E[1024][1024];
double prim(double L)
{
int i, j;
double res, cost, len;
for (i = 0; i < N; i++)
for (j = i; j < N; j++)
E[i][j].w = E[j][i].w = E[i][j].cost - E[i][j].len * L;
  for (i = 0; i < N; i++) {
D[i] = E[0][i].w;
from[i] = 0;
 }
memset(mst, 0, N);
mst[0] = 1;
res = cost = len = 0;
for (i = 0; i < N - 1; i++) {
double min_d;
int min_i;
min_d = 1e50;
for (j = 0; j < N; j++) {
if (!mst[j] && D[j] < min_d) {
min_d = D[j];
min_i = j;
}
}
mst[min_i] = 1;
res += min_d;
cost += E[min_i][from[min_i]].cost;
len += E[min_i][from[min_i]].len;
for (j = 0; j < N; j++) {
if (!mst[j] && E[min_i][j].w < D[j]) {
D[j] = E[min_i][j].w;
from[j] = min_i;
}
}
}
rate = cost / len;
return res;
}
void solve()
{
/**//*
double l, r, m;
l = 0;
r = 1000;
while (r - l > 0.0001) {
m = (r + l) / 2;
if (prim(m) > 0)
l = m;
else
r = m;
}
*/
double r;
int i, j;
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
double dx, dy;
dx = (double)X[i] - X[j];
dy = (double)Y[i] - Y[j];
E[i][j].cost = E[j][i].cost = fabs((double)Z[i] - Z[j]);
E[i][j].len = E[j][i].len = sqrt(dx*dx + dy*dy);
}
}
rate = 0;
do {
r = rate;
prim(rate);
} while (fabs(r - rate) > 0.0001);
printf("%.3f\n", rate);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
while (1) {
scanf("%d", &N);
if (!N)
break;
for (i = 0; i < N; i++)
scanf("%d%d%d", &X[i], &Y[i], &Z[i]);
solve();
}
return 0;
}
题目大意：
A,B两个sb比赛吃葡萄，葡萄上有编号1,2,....100，得分是每个人吃过葡萄的编号的乘积。
比如吃了 2, 5, 10 号葡萄，分数就是 2*5*10 = 100。
葡萄吃完后，两个人报自己的分数。当然，可以虚报。
如果某个人报的分数是吃不出来的，那就算他作弊，另外一个人赢。
如果两个人报的分数有冲突，则分数低的赢。
如果两个人报的分数没有冲突，则分数高的赢。
思路：
枚举每个人吃葡萄的所有情况。。
#include <stdio.h>
#include <string.h>
__int64 val2;
char used[101];
int dfs(__int64 val, int idx, int flag)
{
if (val == 1 || val == 0) {
if (!flag)
return 1;
return dfs(val2, 100, 0);
}
for ( ; idx > 1; idx--) {
if (!(val % idx) && !used[idx])
break;
}
if (idx == 1)
return 0;
used[idx] = 1;
if (dfs(val / idx, idx - 1, flag))
return 1;
used[idx] = 0;
if (dfs(val, idx - 1, flag))
return 1;
return 0;
}
int can(__int64 val, int flag)
{
memset(used, 0, sizeof(used));
return dfs(val, 100, flag);
}
int main()
{
__int64 a, b, r;
while (scanf("%I64d%I64d", &a, &b) != EOF) {
if (a > b) {
r = a;
a = b;
b = r;
}
val2 = b;
if (!can(a, 0))
r = b;
else if (!can(b, 0))
r = a;
else if (can(a, 1))
r = b;
else
r = a;
printf("%I64d\n", r);
}
return 0;
}
题目大意：
给出一个分数，比如1498/902。求出当分母分别为1, 2, ....的时候，最接近1498/902的分数。
比如：
当分母为1的时候，最接近1498/902的分数为 1/1。
当分母为2的时候，最接近1498/902的分数为 3/2。
当分母为3的时候，最接近1498/902的分数为 5/3。
。。。
思路：
不要用高精度哦，直接模拟分数的操作最好了。
#include <stdio.h>
#include <math.h>
struct frac {
__int64 up, down;
};
__inline __int64 gcd(__int64 a, __int64 b)
{
__int64 r;
if (a < b) {
r = a;
a = b;
b = r;
}
while (1) {
r = a % b;
if (!r)
return b;
a = b;
b = r;
}
}
__inline struct frac frac_init(__int64 up, __int64 down)
{
__int64 r, s;
struct frac f;
r = up ? gcd(up, down) : 1;
if (r < 0)
r = -r;
f.up = up / r;
f.down = down / r;
return f;
}
__inline struct frac frac_sub(struct frac fa, struct frac fb)
{
return frac_init(fa.up*fb.down-fa.down*fb.up, fa.down*fb.down);
}
__inline __int64 frac_cmp(struct frac fa, struct frac fb)
{
return frac_sub(fa, fb).up;
}
__inline struct frac frac_abs(struct frac f)
{
if (f.up < 0)
f.up = -f.up;
return f;
}
int main()
{
__int64 up, down;
struct frac target, min_dis, f, dis;
while (scanf("%I64d%I64d", &up, &down) != EOF) {
target = frac_init(up, down);
min_dis.down = 1;
min_dis.up = (__int64)1e15;
for (down = 1; down <= target.down; down++) {
up = (down*target.up)/target.down;
if (((down*target.up)%target.down)*2 >= target.down)
up++;
f = frac_init(up, down);
dis = frac_abs(frac_sub(f, target));
if (frac_cmp(dis, min_dis) < 0) {
printf("%I64d/%I64d\n", f.up, f.down);
min_dis = dis;
}
}
printf("\n");
}
return 0;
}
题目大意：
有一群学生，其中有些人是相互认识的。将学生分为两组，这两组的人数最大只能相差1。
定义一个学生的“孤独指数”为组内他不认识的人的人数。
问怎么分组，才能使这两组中最孤独学生的“孤独指数”最小。
思路：
想不到算法，于是看Discuss。原来是用枚举。。
暴力枚举每一种分组情况，求该情况下“最孤独学生的孤独指数”。
据说数据很弱，N最大才是4，囧。所以0msAC。
#include <stdio.h>
unsigned __int64 map[64];
int N;
int bit_cnt[256];
__inline int calc_cnt(unsigned __int64 val)
{
return bit_cnt[((char *)&val)[0]] +
bit_cnt[((char *)&val)[1]] +
bit_cnt[((char *)&val)[2]] +
bit_cnt[((char *)&val)[3]] +
bit_cnt[((char *)&val)[4]] +
bit_cnt[((char *)&val)[5]] +
bit_cnt[((char *)&val)[6]] +
bit_cnt[((char *)&val)[7]];
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline int max(int a, int b)
{
return a < b ? b : a;
}
int main()
{
int i, j, k, l, r, arr[64], min_val;
unsigned __int64 mask;
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 0; i < 256; i++) {
k = 0;
for (j = i; j; j &= j - 1)
k++;
bit_cnt[i] = k;
}
while (scanf("%d%d", &j, &k) != EOF) {
while (k--) {
scanf("%d", &i);
map[j] |= (unsigned __int64)1 << i;
}
if (j > N)
N = j;
}
for (i = 1; i <= N; i++)
map[i] |= (unsigned __int64)1 << i;
min_val = N;
for (i = 1; i <= N/2; i++)
arr[i] = i;
while (1) {
mask = 0;
for (i = 1; i <= N/2; i++)
mask |= (unsigned __int64)1 << arr[i];
l = r = N;
for (i = 1; i <= N; i++) {
if (mask & ((unsigned __int64)1 << i))
l = min(calc_cnt(map[i] & mask), l);
else
r = min(calc_cnt(map[i] & ~mask), r);
}
i = max(N/2 - l, N - N/2 - r);
if (i < min_val)
min_val = i;
for (i = N/2; i >= 1 && arr[i] == N + i - N/2; i--);
if (!i)
break;
arr[i]++;
for (j = 1; j + i <= N/2; j++)
arr[j + i] = arr[i] + j;
}
printf("%d\n", min_val);
return 0;
}
|