A-小乔与小灰灰
题面：
小乔和小灰灰是好朋友，现在如果一个字符串中同时出现子序列“XiaoQiao”和“XiaoHuiHui”，那么小乔和小灰灰都会感到开心。
输入：
输入包含一行一个字符串S
字符串中仅包含大写字母和小写字母
输出：
如果这个串会让小乔和小灰灰都感到开心，那么输出“Happy”，否则输出“emm”。
样例数据
样例输入1： XiaoQiaoheHuiHui
样例输出1： Happy
样例输入2： Xiaohuihuihexiaoqiao
样例输出2： emm
签到题，按下标匹配。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a < c; a++)
using namespace std;
const int LIM = 1001;
char x[10] = {'X','i','a','o','Q','i','a','o'};
char h[20] = {'X','i','a','o','H','u','i','H','u','i'};
char s[LIM];
int main()
{
int k1 = 0;
int k2 = 0;
scanf("%s", &s);
int len = strlen(s);
rep(i, 0, len)
{
if(s[i] == x[k1]) k1++;
if(s[i] == h[k2]) k2++;
}
if (k1 == 8 && k2 == 10) cout << "Happy";
else cout << "emm";
return 0;
}B-牛能和小镇
题面：
在牛国有n个小镇编号1,2,3…n−1,n。用二维平面来表示每个小镇的位置，第i个小镇的位置为(xi,yi)。牛能做为牛国的国王，决定给小镇之间建设一些道路，以便于任意小镇之间都能相互到达，在第i个小镇和第j个小镇之间建设一条道路的花费如下，请让总花费尽量小。(1<=n,x,y<=1e5)
输入：
第一行输入一个整数n
接下来n行每行两个整数xi,yi表示第i个小镇的坐标。
输出：
输出一个整数表示最小花费。
样例数据
样例输入 3 1 4 2 8 3 6
样例输出 252
读体面感觉就很像最小生成树。要计算一颗最小生成树就要得到各边权，将原题公式转化一下可以得到如下形式：
如果设
那么i,j两点间的距离就可以抽象为|Vi-Vj|。算出每个点的V值然后贪心连边就行了。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)
using namespace std;
typedef long long ll;
const int LIM = 100001;
int n;
ll x, y, ans;
ll v[LIM];
int main()
{
get(n);
rep(i, 1, n)
{
lget(x); lget(y);
v[i] = x*x*y + y*y*(y - 2*x);
}
sort(v+1, v+n+1);
rep(i, 1, n-1)
ans += v[i+1] - v[i];
cout << ans;
return 0;
} 赛时这题还是很艰辛的，一眼看出了它是最小生成树，然后就开始硬套板子，死活套不出来。赛后发现可以根据题目特性来贪心，时空都相当优，这个故事告诉我们做题不能囿于模板，题是死的但人应该是活的。
C-装备合成
题面：
牛牛有x件材料a和y件材料b，用2件材料a和3件材料b可以合成一件装备，用4件材料a和1件材料b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。
输入：
输入包含t组数据
第一行一个整数t(1<=t<=10000)
接下来t行每行两个整数x,y(1<=x,y<=1e9)
输出：
每组数据输出一个整数作为答案
样例数据
样例输入 5 4 8 7 6 8 10 100 4555 45465 24124
样例输出 2 2 3 50 13917
考虑最简单的情况：假设装备1做了i件，那么装备2最多做min[(x-2i)/4, y-3i]件。此时所求的就是max(i+ min[(x-2i)/4, y-3i])。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)
using namespace std;
typedef long long ll;
int t;
ll x, y;
int main()
{
get(t);
while(t--)
{
ll res = 0;
lget(x);lget(y);
rep(i, 1, x)
if (res < i + min((x-2*i)/4, y-3*i))
res = i + min((x-2*i)/4, y-3*i);
printf("%lld\n", res);
}
return 0;
}但是问题来了，这题直接枚举会超时，考虑优化算法。
令x=45465, y=24124打表发现答案存在单峰极值，于是可以用三分算法。
三分算法是一种针对凸性函数极值问题的算法。在区间[l, r]中令m1=l+(r-l)/3，
m2=r-(r-l)/3，即取⅓与⅔位置的值。如果f(m1)>f(m2)，区间变为[l, m2]，反之变为[m1, r]，即保留较大值所在的区间。重复上述操作直到区间足够小。
那么思路就很明确了，此处的凸性函数就是f(i) = i+ min[(x-2i)/4, y-3i] 。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)
using namespace std;
typedef long long ll;
int t;
ll x, y;
int main()
{
get(t);
while(t--)
{
lget(x);lget(y);
ll l = 0, r = min(x/2, y/3);
while(r-l > 15)//此处取一个枚举不超时的区间大小就行
{
ll m1 = l+(r-l)/3;
ll m2 = r-(r-l)/3;
if (m1 + min((x-2*m1)/4,y-3*m1) > m2 + min((x-2*m2)/4,y-3*m2)) r = m2;
else l = m1;
}
ll res = 0;
rep(i, l, r) res = max(res, i+min((x-2*i)/4,y-3*i));
printf("%lld\n", res);
}
return 0;
}D-取石子游戏
题面：
小灰灰和小乔在玩取石子游戏，一堆里有n个石子，小灰灰和小乔轮流操作，小灰灰先手，每次操作的人可以进行以下操作：
假设当前石子数量为k，如果k>=2，那么将石子分为f(k)和k−f(k)两堆，然后选择其中任意一堆石子取走。否则当前操作的人输。其中f(k)=x，x为满足满足x∗2<=k的最大整数。
小灰灰和小乔都非常聪明，所以都会采用最优的策略，你知道最后小灰灰和小乔谁能赢得游戏吗？
输入描述:
输入共包含t组数据
第一行一个整数t(1<= t <= 100000)，表示测试用例的组数
接下来t行每行一个整数n(1<=n<=1e18)。
输出描述:
对于每组案例，如果小灰灰赢，输出“XiaoHuiHui”，否则输出“XiaoQiao”
样例数据
样例输入 10 1 2 3 4 5 6 7 8 9 10
样例输出 XiaoQiao XiaoHuiHui XiaoHuiHui XiaoQiao XiaoQiao XiaoQiao XiaoHuiHui XiaoHuiHui XiaoHuiHui XiaoHuiHui
这题挺有意思的。样例已经把规律告诉你了，真正的难点在1e18的数据范围上。
当n=1时是必败态；而2×1与2×1+1可以通过一次操作转化到n=1，把锅甩给对面，属于必胜态，而 2×2、2×2+1、2 × 3通过1次操作转换n=2或3，属于必败态….
以此类推，胜与败的是作为不断增长的区间来出现的，增长与2的幂次有关。为了在合理时间内快速查询到n的状态，可以先初始化每个胜/败区间的头下标与尾下标，然后对于每个n去二分查找它属于哪一个区间并判胜负。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)
using namespace std;
typedef long long ll;
const int LIM = 1000;
int cnt, t;
ll f[LIM], l[LIM];//f为首l为尾
int main()
{
f[++cnt] = 1; l[cnt] = 1;//初始化败
f[++cnt] = 2; l[cnt] = 3;//初始化胜
while(l[cnt] <= 1e18)
{
cnt++;
f[cnt] = l[cnt-1] + 1;
if(cnt%2 != 0)//败区间
l[cnt] = l[cnt-1]*2;
else//胜区间
l[cnt] = l[cnt-1]*2 + 1;
}
get(t);
while(t--)
{
ll n;
lget(n);
int p = upper_bound(f+1, f+1+cnt, n)- f - 1;//二分答案
if(p%2 != 0) printf("XiaoQiao\n");
else printf("XiaoHuiHui\n");
}
return 0;
}
在扒榜的时候还看见一个大佬的代码，时空都很优，可惜我没读明白，这里还是贴一下。
//作者牛客id:zzuacmer
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)
using namespace std;
typedef long long ll;
int t;
ll n;
int main()
{
cin >> t;
while(t--)
{
lget(n);
ll x = 3;
while(n > x) x = x*4 + 1;
if (n > x/2) puts("XiaoHuiHui");
else puts("XiaoQiao");
}
return 0;
}感觉原理上跟我的方法一样，就是不太看得懂
评论
还没有任何评论，你来说两句吧!