今天有270pt可能是因为数据太水的原因,大佬们都AK了,膜一波
T1
今天第一题就是枚举个全排列,然后输出就好了.
T2
放个题面
FJ将飞盘抛向身高为H(1 <= H <= 1,000,000,000)的Mark，但是Mark被N(2 <= N <= 20)头牛包围。牛们可以叠成一个牛塔，如果叠好后的高度大于或者等于Mark的高度，那牛们将抢到飞盘。
每头牛都一个身高，体重和耐力值三个指标。耐力指的是一头牛最大能承受的叠在他上方的牛的重量和。请计算牛们是否能够抢到飞盘。若是可以，请计算牛塔的最大稳定强度，稳定强度是指，在每头牛的耐力都可以承受的前提下，还能够在牛塔最上方添加的最大重量。
开始想的是一个2n×n 的算法需要一个贪心来搞,事实证明我的贪心是对的,但是在我的搜索中并没有加入这个贪心的排序,挂成70pt了,具体贪心是酱紫的我们假设要决定u,v的顺序显然我们要选取u的承受值-v的重量和v的承受值-u的重量两个中较大的一个比较好,我们根据这个排序,不难得出贪心的做法,接下来搜索就好了,加一个最优性剪枝.
贴下代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define mem(a, b) memset((a), b, sizeof(a))
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
LL read()
{
register LL flag = 1,sum = 0;char c = getchar();
while(!isdigit(c)) { if(c == '-')flag = -1; c = getchar(); }
while(isdigit(c)) { sum = sum * 10 + c - '0'; c = getchar(); }
return sum * flag;
}
const LL INF = 1e14;
const int maxn = 100;
struct T
{
LL h,w,s;
bool operator < (const T&u)const
{
return s+w > u.s+u.w;
}
}a[maxn];
LL n,H,ans;
bool vis[maxn];
int cc = 0;
void dfs(int x, LL hi, LL res,int pos)
{
if(res <= 0 || ans >= res) return;
if(hi >= H) { chkmax(ans, res); return; }
if(x > n) return;
REP(i, pos, n)
{
if(!vis[i])
{
vis[i] = 1;
dfs(x + 1, hi + a[i].h, min(a[i].s, res - a[i].w),i);
vis[i] = 0;
}
}
}
int main()
{
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
n = read(), H = read();
LL sum = 0;
REP(i, 1, n)
{
a[i].h = read(),a[i].w = read(),a[i].s = read();
sum += a[i].s;
}
sort(a + 1, a + n + 1);
if(sum < H) { printf("GCD is too tall\n"); return 0; }
ans = -INF;
dfs(1, 0, INF,1);
if(ans == -INF) printf("GCD is too tall\n");
else printf("%lld\n", ans);
return 0;
}T3
放个题面
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
题意很简单,当时在打暴力的时候在纸上画了一下然后发现了一个性质(规律)当你算出当前的点为根的深度和时,它儿子的答案是可以O(1) 算出来的,具体是这样子的,v为x的儿子,ansv = ansx + n - 2 * size[v]，其中size表示子树大小，这样的话O(n) dfs扫一遍就好了．
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
#define REP(i,a,b) for(register int i = (a),i##_end_ = (b); i <= i##_end_; ++i)
#define DREP(i,a,b) for(register int i = (a),i##_end_ = (b);i >= i##_end_; --i)
#define mem(a,b) memset(a,b,sizeof(a));
LL read()
{
register LL flag = 1,sum = 0;char c = getchar();
while(!isdigit(c)) { if(c == '-')flag = -1; c = getchar(); }
while(isdigit(c)) { sum = sum * 10 + c - '0'; c = getchar(); }
return sum * flag;
}
const int maxn = 2000000+10;
int be[maxn],ne[maxn],to[maxn],e;
int size[maxn],dep[maxn],n;
void add(int x,int y) { to[++e] = y;ne[e] = be[x];be[x] = e; }
void dfs1(int x,int dp)
{
size[x] = 1;dep[x] = dp;
for(int i = be[x]; i; i = ne[i])
{
int v = to[i];
if(!dep[v])dfs1(v,dp+1),size[x]+=size[v];
}
}
LL ans = 0,p;
bool vis[maxn];
void dfs(int x,LL fans)
{
vis[x] = 1;
for(int i = be[x]; i; i = ne[i])
{
int v = to[i];
if(!vis[v])
{
LL res = fans-size[v]+(n-size[v]);
if(ans < res || ans == res && p > v)ans = res,p = v;
dfs(v,res);
}
}
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n = read();
REP(i,1,n-1)
{
int x = read(),y = read();
add(x,y);add(y,x);
}
dfs1(1,1);REP(i,1,n)ans += dep[i];p = 1;
dfs(1,ans);
cout<<p<<endl;
}经验与不足
暴力还是太慢了，虽然T1,T3一下就打完了，但是Ｔ２的暴力打了很久导致大家１０点多就ＡＫ了，蒟蒻还调到１１点，还是太弱了，要好好努力咯．