2020hdu多校第二场比赛及补题

08/10 07:07
阅读数 32

这一场我们队只A了一题

1010 Lead of Wisdom

直接爆搜,但是T了好几发,剪了下枝

如果一个物品的a,b,c,d都比不上另外一个同种物品的a,b,c,d,那这个物品就可以直接淘汰掉了

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct BB{
	long long a,b,c,d;
}bb;
vector<BB> zz[60];
int T,n,k,t;
int order[60];
long long ma = 0;
bool cmp(int a,int b){
	return zz[b].size()>zz[a].size();
}
void dfs(int cen,long long A,long long B,long long C,long long D,long long ss){
	if(cen>k) {
		ma = max(ma,ss); 
		return;
	}
	long long res = 0;
	for(int i = 0;i<zz[order[cen]].size();i++){
		long long da,db,dc,dd;
		da = A+zz[order[cen]][i].a;
		db = B+zz[order[cen]][i].b;
		dc = C+zz[order[cen]][i].c;
		dd = D+zz[order[cen]][i].d;
		res=max(res,(100+da)*(100+db)*(100+dc)*(100+dd));
	}
	if(res == 0){
		dfs(cen+1,A,B,C,D,ss);
	}
	else for(int i = 0;i<zz[order[cen]].size();i++){
		long long da,db,dc,dd,dda,ddb,ddc,ddd;
		da = A+zz[order[cen]][i].a;
		db = B+zz[order[cen]][i].b;
		dc = C+zz[order[cen]][i].c;
		dd = D+zz[order[cen]][i].d;
		bool ok = true;
		for(int j = i+1;j<zz[order[cen]].size();j++){
			dda = A+zz[order[cen]][j].a;
			ddb = B+zz[order[cen]][j].b;
			ddc = C+zz[order[cen]][j].c;
			ddd = D+zz[order[cen]][j].d;
			if(dda>=da&&ddb>=db&&ddc>=dc&&ddd>=dd){
				ok = false;
				break;
			}
		}
		if(ok){
			long long cd = (100+da)*(100+db)*(100+dc)*(100+dd);
			dfs(cen+1,da,db,dc,dd,cd);	
		}
	}
}
int main()
{
	cin>>T;
	while(T--){
		cin>>n>>k;
		ma = 0;
		for(int i = 1;i<=k;i++){
			zz[i].clear();
			order[i] = i;
		}
		for(int i = 1;i <= n;i++){
			cin>>t>>bb.a>>bb.b>>bb.c>>bb.d;
			zz[t].push_back(bb);
		}
		sort(order+1,order+k+1,cmp);
		dfs(1,0,0,0,0,0);
		cout<<ma<<endl;
	}	
	return 0;
}

1006 The Oculus  

F1,F2.....F2000001对2的64次方两两不同余,所以直接用 unsigned long long 自然溢出即可

这题队友写的代码,RE了两发,我比赛时没看这代码,比赛结束后,我发现他数组开的很小,我把数组开大交了一发,然后就A了......

#include <iostream>
#include <cstdio>
#define fuck unsigned long long
using namespace std;
const int MAXN = 1e7+7;
fuck fb[MAXN];
fuck t;
int main(void){
    fb[1] = 1;
    fb[2] = 2;
    for(fuck i=3;i<=MAXN;i++){
        fb[i] = fb[i-1]+fb[i-2];
    }
    cin >> t;
    while(t--){
        fuck a,b,c;
        fuck A=0,B=0,C=0;
        scanf("%lld",&a);
        fuck flag;
        for(fuck i=1;i<=a;i++){
            scanf("%lld",&flag);
            if(flag){
                A += fb[i];
            }
        }
        scanf("%lld",&b);
        for(fuck i=1;i<=b;i++){
            scanf("%lld",&flag);
            if(flag){
                B += fb[i];
            }
        }
        scanf("%lld",&c);
        for(fuck i=1;i<=c;i++){
            scanf("%lld",&flag);
            if(flag){
                C+=fb[i];
            }
        }
        fuck result = A*B;
        fuck last = result - C;
        for(fuck i=1;i<=MAXN;i++){
            if(fb[i] == last){
                printf("%lld\n",i);
                break;
            }
        }
    }
    return 0;
}

  

1012 String Distance

 

比赛时看了这题,没做出来

字符串距离问题,见https://www.cnblogs.com/ruanbaitql/p/13373305.html

1007 In Search of Gold

树形dp,比赛时根本不知道怎么做

一开始想用dp[ i ][ j ]表示以 i 为根节点的子树,用了 j 条a边,经过 i 节点的最长的链最小是多少

后来发现递推太难了

dp[son]不能递推dp[father],father最优时,son不一定最优,father的最优态不一定是son的最优态转移过来的

 

可以想到再开一个 F [ i ][ j ], 表示以 i 为根节点的子树,用 j 条a边时,子树里离根节点 i 最远的节点到根节点 i 的距离,

这样F[son]可以递推dp[father]了,但dp[father]最优了,dp[son]不是最优,还有可能超过dp[father], 所以F[son]虽然能推出最优的dp[father],但不能推出最优的max(dp[son],dp[father])。。。

 

正确做法是二分答案,把它变成一个判断性问题,假设最长链长度小于等于ans,判断是否成立 

 

 

这次我们递推的时候,不需要递推出最优的max(dp[son],dp[father]),我们只要在dp[son]<=ans的前提下,递推最优的dp[father]和F[father]

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 7;
const long long INF = 1e18 + 7;
int n, K;
struct EDGE {
	int to, next;
	long long a, b;
}edge[MAXN * 2];
int head[MAXN], tot;
void add(int u, int v, long long a, long long b) {
	tot++;
	edge[tot].to = v;
	edge[tot].a = a;
	edge[tot].b = b;
	edge[tot].next = head[u];
	head[u] = tot;
}
long long F[MAXN][23];//F[i][j]表示以i为根节点,用了j条a边,离根节点最远的节点到根节点的距离
int son[MAXN];
void dfs(int s, int f, long long ans) {
	son[s] = 1;
	for (int i = head[s]; i; i = edge[i].next) {
		int po = edge[i].to;
		if (po == f) continue;
		long long a = edge[i].a, b = edge[i].b;
		dfs(po,s,ans);
		son[s] += son[po];
		for (int k = min(K, son[s] - 1); k >= 0; k--) {//遍历体积
			bool flag = false;
			for (int x = max(0, k - (son[s]-son[po]-1) ); x <= son[po] && x <= k; x++) {
				//每个决策选个最优
				long long mi;
				if (x == max(0, k - (son[s] - son[po] - 1))) { //第一个决策
					if (x == 0) mi = F[po][x] + b;
					else if (x > son[po] - 1) mi = F[po][x - 1] + a;
					else mi = min(F[po][x] + b, F[po][x - 1] + a);
					if (F[s][k - x] + mi <= ans) {//判断这情况会不会使dp[father]超过ans
						flag = true;
						F[s][k] = max(F[s][k - x], mi);
					}
					else F[s][k] = INF;
				}
				else if (x > son[po] - 1) mi = F[po][x - 1] + a;
				else mi = min(F[po][x] + b, F[po][x - 1] + a);
				if (F[s][k - x] + mi <= ans) {
					flag = true;
					F[s][k] = min(F[s][k],max(F[s][k - x], mi));//更新f[s][k]
				}
			}
			if (!flag) {//没一个决策能选的
				F[s][k] = INF;
			}
		}
	}
}


bool check(long long ans) {
	dfs(1, 0, ans);
	//cout << F[1][K] << endl;
	if (F[1][K] > ans) return false;
	return true;
}
int main()
{
	//freopen("1007.in", "r", stdin);
	int T;
	int u, v;
	long long a, b;
	cin >> T;
	while (T--) {
		tot = 0;
		cin >> n >> K;
		for (int i = 1; i <= n; i++) {
			head[i] = 0;
		}
		for (int i = 1; i < n; i++) {
			scanf("%d%d%lld%lld", &u, &v, &a, &b);
			add(u, v, a, b);
			add(v, u, a, b);
		}
		long long l = 1, r, mid;
		r = (long long)n * (long long)1e9;
		while (l < r) {
			for (int i = 1; i <= n; i++) 
				for (int k = 0; k <= K; k++)
					F[i][k] = 0;		
			mid = l + r >> 1;
			if (check(mid)) r = mid;
			else l = mid + 1;
		}
		cout << l << endl;
	}
	return 0;
}

  

1001 Total Eclipse

 

还没补...

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部