武汉工程大学GPLT选拔补题
链接：https://ac.nowcoder.com/acm/contest/9143/I
来源：牛客网
L2-1 特殊的沉重球
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
StarrySky 在初入精灵宝可梦世界探索的时候，偶遇了一只野生的卡比兽，可是，StarrySky 扔完了手上的精灵球都不能捕捉成功，只好狠下心来让自己当时首发的路卡利欧使用出波导弹打死了它。
后来，StarrySky 发现了一个特殊的精灵球，叫作沉重球，它的特性是：当捕捉体重较大的宝可梦时，会增加成功率。
当发现沉重球之后，StarrySky 突然好后悔，如果在当时用沉重球捕捉卡比兽的话，或许局面就会完全不一样了。
抬头望天，晴空万里，一辆辆缆车在不远处滑过，上面的训练家以及他的宝可梦在友好的玩耍嬉闹，欣赏风景。
StarrySky 突发奇想，如果沉重球再特殊一点呢？
如果一个沉重球的最大承重为 w，只要放入其中的宝可梦的总重量不超过 w，不论几只宝可梦都可以放进去，然后再用缆绳挂起这个沉重球滑行，那个感觉似乎十分不错。
现在 StarrySky 手中有 n 只宝可梦，宝可梦的体重为 cic_ici，问至少需要多少个特殊的沉重球才能装下这 n 只宝可梦？
输入描述:
第一行输入两个正整数 n, w，表示宝可梦的数量以及每个特殊沉重球的最大承重。
第二行输入 n 个正整数c1,c2,...,cnc_1, c_2, ..., c_nc1,c2,...,cn，依次表示 n 只宝可梦的重量。
输出描述:
一行一个正整数，表示能够装下这 n 只宝可梦的最少的特殊沉重球的数量。
示例1
输入
复制
5 1996
1 2 1994 12 29
输出
复制
2
说明
第一个沉重球放入第 1, 2, 4, 5 只宝可梦，第二个沉重球放入第 3 只宝可梦，这种方法只需要 2 个沉重球。
放法不唯一，比如，也可以将第 2 只宝可梦放入第二个沉重球，但无论如何，该样例的最少所需的沉重球数量为两个。
备注:
用dfs暴力选择最优的
#include<bits/stdc++.h>
using namespace std;
int a[30], sum[30];
int n, w, ans;
void dfs(int x, int cnt);
int main()
{
cin >> n >> w;//数量和最大承受重量
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
sort(a + 1, a + 1 + n, greater<int>());
ans = n;
dfs(1, 0);
cout << ans << endl;
return 0;
}
void dfs(int x, int cnt)//cnt沉重球数量
{
if (cnt >= ans) return;//ans沉重球最少数量
if (x > n) {//全部选完
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++) {
if (a[x] + sum[i] <= w) {//如果全部都不能，则到下面cnt++
sum[i] += a[x];
dfs(x + 1, cnt);
sum[i] -= a[x];
}
}
sum[cnt + 1] = a[x];
dfs(x + 1, cnt + 1);
sum[cnt + 1] = 0;
}链接：https://ac.nowcoder.com/acm/contest/9143/J
来源：牛客网
L2-2 又见火车入栈
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述
StarrySky 最近沉迷的精灵宝可梦即将增加两张新地图：铠之孤岛，冠之雪原。
为了迎接新世界的到来，StarrySky 整天守在木杆镇的车站等待着通往新区域的火车。
为了消磨时间，StarrySky 依次记录下了一天当中火车进站、出站的情况。根据观察发现，木杆镇的火车站与 IvyHole 的算法世界中的“栈”有着异曲同工之妙，即：标号为 i 的火车进站之后，如果后续有标号为 j 的火车进站，则 i 这列火车不可能在 j 这列火车之前出站，再用四个字简单概括一下就是：先进后出。
在 StarrySky 的记录中，in 表示有火车进站，out 表示有火车出站，且所有记录全都合法，即：当火车站内没有火车时，不可能出现 out 记录，但是在所有记录结束时，车站内有可能依旧停留有火车。
为了方便表示，根据进站顺序给每列火车唯一标号，例如：第一个 in 表示标号为 1 的火车进站，第二个 in 表示标号为 2 的火车进站，此时如果有 out 记录，则表示标号为 2 的火车出站，出站后火车站内只剩下标号为 1 的火车，...，以此类推处理火车记录，就可以得知一整天的火车进出站情况。
为了考验 IvyHole 的能力，在上述记录的基础上，StarrySky 提出了询问，在处理完第 x 条记录后，火车站内剩余的火车中，第 y 个进入火车站的火车编号是多少？StarrySky 保证了询问一定合法，即：如果第 x 条记录后火车站内只剩下了 k 辆火车，则 k > 0 且 y≤ky \leq ky≤k.
由于 IvyHole 近期忙于 OJ 平台的维护，所以将这个问题抛给了你，希望你代替 IvyHole 回答 StarrySky 的问题。
输入描述:
第一行输入一个正整数 n，表示这一天内 StarrySky 记录的数目。
接下去 n 行，每行一个火车进出站的记录，即：每行输入 in 或者 out 表示火车进出站情况，且记录一定合法。
第 n + 2 行一个正整数 q，表示 StarrySky 的询问次数。
接下去 q 行，每行两个正整数 x, y，表示询问在处理完第 x 条记录后，火车站内剩余的火车中，第 y 个进入火车站的火车编号是多少？保证询问一定合法。
输出描述:
一共 q 行，依次表示每一个询问的答案。
示例1
输入
复制
8
in
out
in
in
out
in
out
out
3
1 1
3 1
6 2
输出
复制
1
2
4
说明
第一条记录后车站内火车情况：1
第二条记录后车站内火车情况：空
第三条记录后车站内火车情况：2
第四条记录后车站内火车情况：2, 3
第五条记录后车站内火车情况：2
第六条记录后车站内火车情况：2, 4
第七条记录后车站内火车情况：2
第八条记录后车站内火车情况：空
备注:
20%20%20% 的评测用例，1≤n,q≤1001 \leq n, q \leq 1001≤n,q≤100 且询问中的 x 升序。
20%20%20% 的评测用例，1≤n,q≤20001 \leq n, q \leq 20001≤n,q≤2000 且询问中的 x 升序。
20%20%20% 的评测用例，1≤n,q≤20001 \leq n, q \leq 20001≤n,q≤2000，对询问中的 x 不做特殊要求。
40%40%40% 的评测用例，1≤n,q≤10000001 \leq n, q \leq 10000001≤n,q≤1000000，对询问中的 x 不做特殊要求。
把所有的进出站情况先存起来，然后根据x先后顺序排序把编号找出来，最后输出
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct pre{
int x;
int y;
int pos;//询问的先后顺序
int posy;//第y个车的编号
}qry[N];
int stk[N];
bool a[N];
int main()
{
int n,q;
scanf("%d",&n);
char ch[10];
for(int i=1;i<=n;i++){
scanf("%s",ch);
if(ch[0]=='i')a[i]=true;
else a[i]=false;
}
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d%d",&qry[i].x,&qry[i].y);
qry[i].pos=i;
}
sort(qry,qry+q,[](const pre &a,const pre &b){return a.x<b.x;});
int top=0;
for(int i=1,j=0,z=1;i<=n;i++){
if(a[i]){
stk[top++]=z++;
}
else top--;
while(qry[j].x==i){//同一个x可能询问多次
qry[j].posy=stk[qry[j].y-1];
j++;
}
}
sort(qry,qry+q,[](const pre &a,const pre &b){return a.pos<b.pos;});
for(int i=0;i<q;i++){
printf("%d\n",qry[i].posy);
}
}
链接：https://ac.nowcoder.com/acm/contest/9143/K
来源：牛客网
L2-3 新旷野地带
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
StarrySky 最近迷上了精灵宝可梦，在这款游戏中有一块区域称作旷野地带，在这片地带中分布有若干个极巨化坑，会有极巨化宝可梦在其中出没。
StarrySky 想要集齐图鉴，尤其是收集极巨化宝可梦，所以就需要常年来回奔波于各个极巨化坑之间。又由于这些极巨化坑的分布十分不规律，再加之总是出现雷雨、沙尘暴、暴风雪等天气降低能见度，StarrySky 总是在旷野地带迷路。
终于，StarrySky 忍受不了这个设定，决定破解这个游戏，自己重新设计一个旷野地带。
假设新旷野地带由 n 行 m 列组成，其中的每一个位置（如：i 行 j 列）都可以放置极巨化坑。现在 StarrySky 手中有 k 个极巨化坑有待放置，同时，为了不让极巨化坑的分布过于密集，他决定每一行、每一列最多同时放置一个极巨化坑，如：已经在 i 行 j 列放置了一个极巨化坑，那么，在第 i 行的其它位置不能再出现极巨化坑，同理，在第 j 列的其它位置也不能再出现极巨化坑。
k 个极巨化坑可以不全放入旷野地带，但是旷野地带中必须至少存在一个极巨化坑，StarrySky 现在想要知道一共有多少种放置方案，这个数量可能很大，所以请你给出答案对 1e9 + 7 取模后的结果。
输入描述:
一行三个由空格隔开的正整数 n, m, k，表示新旷野地带由 n 行 m 列组成，手中有 k 个可选择放置的极巨化坑。
输出描述:
一行一个整数，表示满足题意的放置方案的数量对 109+710^9+7109+7 取模后的结果。
示例1
输入
复制
2 2 2
输出
复制
6
说明
6 种放置方案如下：
只在 (1, 1) 上放一个；
只在 (1, 2) 上放一个；
只在 (2, 1) 上放一个；
只在 (2, 2) 上放一个；
在 (1, 1), (2, 2) 上各放一个；
在 (1, 2), (2, 1) 上各放一个。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+10;
const ll mod=1e9+7;
ll f[N],inv[N];
ll pw(ll x,ll y){
ll ans=1;
x%=mod;
while(y>0){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void ini(ll n){
f[0]=1;
for(ll i=1;i<=n;i++){
f[i]=f[i-1]*i%mod;
inv[i]=pw(f[i],mod-2);
}
inv[0]=pw(1,mod-2);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
ll n,m,k;
cin>>n>>m>>k;
ini(max(n,m));
ll ans=0;
for(ll i=1;i<=k;i++){
if(i>n||i>m)break;
ll t=f[n]*f[m]%mod*inv[i]%mod*inv[n-i]%mod*inv[m-i]%mod;
ans=(ans+t)%mod;
}
cout<<ans<<endl;
}
投递蚂蚁集团等公司10个岗位 >
