|
|
摘要: 題目大意：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;
}
|